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

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

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])