Polynomial Commitment using IPA(Inner Product Argument) explained to beginner.

Introduction

The Inner Product Argument (IPA) is a cryptographic technique used to prove statements about the inner product "z," which is a scalar resulting from the dot product of two vectors "a" and "b" without revealing the actual vectors.

Inner product/dot product is a.b = z

There are different variants of IPA, the main focus of this blog is where the "a" is a secret vector.

IPA for polynomial commitments

Inner product arguments can serve as a valuable tool for polynomial commitments. To provide a brief introduction to polynomial commitment, it involves the prover committing to a polynomial and subsequently proving to the verifier the polynomial's behaviour at various points, all without actually disclosing the polynomial itself.

Now let's say there is a polynomial f with coefficients which can be converted to a vector.

Vector f:

f = (f₀, f₁, ..., fₙ)

Function f(x):

f(x) = f₀ + f₁x + f₂x² + ... + fₙxⁿ

Notice: the inner product.

f(s) = ⟨f, (1, s, s², ..., sⁿ)⟩

Before diving into the main setup, it's essential to grasp the concept of Pedersen commitment.

Pedersen commitment allows us to commit to a value "x" by multiplying it with a point "G," where "G" is a point on an elliptic curve with an unknown discrete log.

The commitment of "x" is represented as "x⋅G" (which means "x" multiplied with point "G").

The Pedersen commitment used in this blog possesses the properties of both binding and non-hiding.

Binding indicates that once a commitment is made to a value, it can't be revealed as a different value.

Non-hiding implies that the value "x" itself isn't hidden; it's just a part of the commitment.

Setup(1st Iteration)

In our protocol, the prover holds a secret vector(polynomial coefficients) a = (a₁, a₂, a₃, a₄), known only to them. The rest of the parameters are shared knowledge:

G = (G₁, G₂, G₃, G₄): A basis used for Pedersen hashing.
A = ⟨a, G⟩: A commitment to vector a.
b = (b₁, b₂, b₃, b₄): Powers of value "s," where b = (1, s, s², s³).
Inner product result z = ⟨a,b⟩

After receiving the proof of opening in the first iteration, the verifier sends a random value x to the prover. This x is then used by the prover in the second iteration to reduce the proof size. The size of the proof is reduced by O(log(n)) in each iteration, where n is the size of the vector.

The problem

Sending large commitment data in every interaction with the verifier can be highly inefficient. The Inner Product Argument (IPA) presents an elegant solution by enabling a prover to commit to a vector, progressively reducing its size through proofs, all while ensuring its connection to the original vector remains validated.

Reduced Problem (2nd Iteration)

a' = x⁻¹(a₁a₂) + x(a₃a₄)
b' = x(b₁b₂) + x⁻¹(b₃b₄)
G' = x(G₁G₂) + x⁻¹(G₃G₄)
⟨a',b'⟩ = z' (reduced problem)

now we need 2 things:

1. a proof that proving above statement is the same as proving the previous statement ⟨a.b⟩ = z
2. a way for the verifier to compute z', b' and A'(commitment of a') by themselves.

The Proof

A' = ⟨a',G'⟩
= (x⁻¹a₁ + xa₃)(xG₁ + x⁻¹G₃) + (x⁻¹a₂ + xa₄)(xG₂ + x⁻¹G₄)
= A + x⁻²(a₁G₃ + a₂G₄) + x²(a₃G₁ + a₄G₂)
= A + x⁻²La + x²Ra

So to compute this new commitment, the verifier needs:

1. A (previous commitment) which they already have
2. La and Ra, points on the curve
3. some powers of x

now we also have to calculate z'

z' = ⟨a',b'⟩
= ⟨(x⁻¹a₁ + xa₃, x⁻¹a₂ + xa₄), (xb₁ + x⁻¹b₃, xb₂ + x⁻¹b₄)⟩
=(a₁b₁ + a₂b₂ + a₃b₃ + a₄b₄) + x⁻²(a₁b₃ + a₂b₄)+ x²(a₃b₁ + a₄b₂)
z' = z + x⁻²(Lz) + x²(Rz)

Now the total proof to send to the verifier in the 2nd iteration is

a' (half of a)
La and Ra, points on the curve
Lz and Rz, some scalar values

Summary

• The prover's first commitment is to the full secret vector.
• To reduce the vector size, the prover splits the vector into two halves.
• They create a new commitment to just one half vector.
• But this new commitment is not independent - it is computed in a way that cryptographically links it to the previous full commitment.
• Specifically, the new commitment includes a randomness term derived from the randomness of the original commitment.
• This creates a mathematical dependency between the commitments in the chain.
• After log2(n) rounds, the vector size is reduced down to just 1 element.