ZK Scholars Assembly Revision 4 - Batch Opening & Vector Commitment

In the last KGZ discussion, we are only proving f(x) = y, what if we want to prove many different points are from the same polynomial? Here comes batch opening.

f(x) is a N-degree polynomial and interpolates set of point {(xi, yi)} i ∈ [n], define an accumulator polynomial as A(x) = ∏ (x - xi) while i ∈ [n]. And f(x) can be express as:

f(x) = A(x) * Q(x) + R(x)

A(x): accumulator polynomial
Q(x): quotient polynomial
R(x): remainder polynomial

For example:
R(x) = y0 ⋅ℓ0(x) + y1 ⋅ℓ1(x) + y2 ⋅ℓ2(x) + …

And quotient polynomial becomes:
Q(x) = (f(x) - R(x)) / A(x)

Using τ from trusted setup, the prove computes g^Q(τ) and the verifier verifies by checking pairings of:

e(g^Q(τ), g^A(τ)) = e(g^(f(τ) - R(τ)), g)
e([Q(τ)], [A(τ)]) = e([f(τ) - R(τ)], [1])

Vector commitment is simply committing a vector of values (an ordered list of elements). For example we have vector of {v0, v1, v2, …, v[n - 1]}, we can construct a polynomial f(x) such that f(i) = vi for i = 0, 1, 2, …, n-1. Committing polynomial f(x) means committing to the vector v, essentially compacting the vector v.

To make things more efficient, we use n-th roots of unity ω. The equation of n-th roots of unity is always x^n = 1, which means x^n - 1 = 0. Because n-th roots of unity is an abelian group itself, therefore we can encode a vector v of length n with n-th roots of unity ω:

P(ωi) = v[I] where ω is a primitive n-th root of unity (i.e. ω^n = 1 and ω^k not = 1 for 0 < k < n)

Other than that, roots of unity enables Fast Fourier Transform to quickly evaluate and interpolate polynomials, making it more practical in term of efficiency. Given polynomial P(x) of degree n - 1, FFT can evaluate it at all n roots of unity in O(n log n) time. Plus we can do inverse FFT to reconstruct the polynomial P(x) given values of the polynomial at the roots of unity in O(n log n) time too.

With all the nice properties of n-th roots of unity, we can now easily commit a vector v that is encoded as polynomial P(x) by evaluating it at secret random point s (or τ with trusted setup) and prove the evaluation P(ωi) = vi later with a proof. For more advance use cases, roots of unity helps facilitate verification of updating elements in dynamic vectors and ensure commitment remains valid.

I spent lots of time trying to wrap my head around roots of unity that’s why this post is taking some time. 😅

We’ll explore R1CS, QAP & Groth16 in the next post!

If A(x) vanishes on the set {xi} i ∈ [n], then the remainder polynomial should satisfy R(xi) = yi for all 
i ∈ [n] and R(x) can be define as a Lagrange form of Interpolation Polynomial:

R(x) = ∑ yi ⋅ ℓi(x) where i = 0, i < n and each Li(x) is the ith Lagrange basis polynomial:
ℓi(x) = ∏ (x - xj) / (xi - xj) where j = 1, j not = i and i < n