KZG - Batch Proofs

Overview

• generate multiple proofs in the commitment but:

  • proof size remains at 1 element

• recall for a single point, the proof evaluation is:

CreateWitness$(PK,\varphi (x),i)$ - Prover

CreateWitness - Prover

Input:
Output: proof

• compute
• compute witness (proof) :

• we can transform the above to multiple points by replacing:
  1. $\varphi (x)$ with $I(X)$,
  2. $x-i$ with $Z(X)$
  • which gives:
    • $\psi (x)=\frac{\varphi (x)-I(X)}{Z(X)}$
  • where:
    • $I(X)=\sum _{i=0}^{k-1}{y}_i\prod _{\genfrac{}{}{0ex}{}{j=0}{j\ne i}}^{k-1}\frac{X-z_j}{z_i-z_j}$
      • Interpolation Polynomial computed with Lagrange interpolation, which goes through all $k$ points
    • $Z(X)=(X-z_0)\cdot (X-z_1)\cdots (X-z_{k-1})$
      • Zero Polynomial where each factor (e.g. $(X-z_0)$) represents a point that $\varphi (x)-I(x)=0$
        • i.e. $z_0$ is a root, and $\varphi (x)-I(x)=0$ is divisible by the factor

References

• Kate-Zaverucha-Goldberg (KZG) Constant-Sized Polynomial Commitments - Alin Tomescu
• Batch proof in KZG Commitments - arnaucube - blog
• KZG polynomial commitments | Dankrad Feist