KZG
The KZG Commitment Scheme
The notation for bilinear pairings over assymetric groups of order \(\textcolor{blue}{\mathtt{q}}\) used in this post are described here
Trusted Setup
Toxic waste discarded by Trusted Entity \(\alpha \xleftarrow[]{\$}\mathbb{F}_{\textcolor{blue}{\mathtt{q}}}\)
Provers Key: \((w_0, \ldots, w_{d}) = (g^{\alpha^0}, \ldots, g^{\alpha^d})\)
Verifiers Key: \(v_1 = h^{\alpha^1}\)
Commit
To commit to a \(f \in \mathbb{F}_{\textcolor{blue}{\mathtt{q}}}[X]\)
Prover \(\rightarrow\) Verifier : \(C_{f}\)
Let \(f\) be a univariate polynomial with degree at most \(d\) with coefficients in \(\mathbb{F}_{\textcolor{blue}{\mathtt{q}}}\). \[f(X) = f_0 + f_1X + \ldots + f_dX^d\]
To commit to a \(f\) the prover computes
\[C_{f} = \prod_{i=0}^d w_i^{f_i} = g^{f(\alpha)}\]
Prover Cost
\(d+1\) \(\mathbb{G}_1\) exponentiations, \(d\) \(\mathbb{G}_1\) multiplications
Opening
Prover \(\leftarrow\) Verifier : Point to evaluate \(z\)
Prover \(\rightarrow\) Verifier : \(y \in \mathbb{F}_{\textcolor{blue}{\mathtt{q}}}\), and that \(\pi\), that \(f(z)=y\)
Given \(C_{f}\), the verifier asks the prover to evaluate \(f\) at \(z\). The prover responds with an evaluation \(y\) and a proof \(\pi\) which proves that prover knows an opening \(f \in \mathbb{F}_{\textcolor{blue}{\mathtt{q}}}[X]\) to \(C_{f}\), with degree \(d\) such that \(f(z) = y\).
To compute the proof \(\pi\), the prover first computes the quotient polynomial \(q(X)\) (See Why No Remainder for the division below does not have a remainder) \[ \begin{align} q(X) = \frac{f(X) - f(z)}{X-z} = q_0 + q_1X + \ldots + q_{d-1}X^{d-1} \end{align} \] sends \(\pi\) as the proof. \[\pi = C_{q} = \prod_{i=0}^{d-1} w_i^{q_i}\]
Prover Cost
\(d+1\) \(\mathbb{G}_1\) exponentiations, \(d\) \(\mathbb{G}_1\) multiplications : To generate compute commitment to quotient polynomial.
To compute quotient polynomial, use Horners method, and that’s \(2d\) Field multiplications and \(2d\) Field additions.
Verification
The verifier computes
\[ \begin{align} \mathtt{LHS}&= e(C_{q}, v_1g^{-z}) \\[10pt] \mathtt{RHS}&= e(C_{f}, h) \quad e(g^{-y}, h) \end{align} \]
Then checks \(\mathtt{LHS}= \mathtt{RHS}\).
See for a derivation of where the above test comes from
Verifier Cost
3 pairing operations, 2 \(\mathbb{G}_1\) exponentiations 1 random sample \(v \xleftarrow[]{\$}\mathbb{F}_{\textcolor{blue}{\mathtt{q}}}\)
Batching KZG
1 polynomial many points
In the proof above the prover commits to a single polynomial, and the verifier wants to evaluate it at a single evaluation point \(z\).
Often we want to evaluate the committed polynomial \(f\) at \(z_1, \ldots, z_k\) where \(k<d\) (otherwise we can learn the polynomial).
Naively, the prover can send \(k\) proofs \(\pi_1, \ldots, \pi_k\) but there is a way to batch it all into 1 proof.
TOTO THis weekend
Many polynomial 1 point
TOTO THis weekend
Many polynomials Many Points
TOTO THis weekend
Appendix
Why No Remainder
Let \(f(x)\) be a polynomial, and let \(b \in \mathbb{F}_{\textcolor{blue}{\mathtt{q}}}\). Consider the expression:
\[ \frac{f(x) - f(b)}{x - b}. \]
To see why this has no remainder (i.e., is a polynomial), define:
\[ g(x) = f(x) - f(b). \] Then clearly: \[ g(b) = f(b) - f(b) = 0, \] so \(x = b\) is a root of \(g(x)\). Therefore, \(x - b\) is a factor of \(g(x)\), by the Factor Theorem. That is, there exists a polynomial \(q(x)\) such that: \[ f(x) - f(b) = (x - b)q(x), \]
where \(\deg(q) = \deg(f) - 1\). Thus,
\[ \frac{f(x) - f(b)}{x - b} = q(x) \] is a polynomial, and the division has no remainder.
Verification Equation
Here we derive the completeness of the verification procedure i.e. if the prover does their computations correctly, the verifier’s test will always pass. Therefore, as the prover is honest, we will assume that \(f(z) = y\).
\[ \begin{align} (X - z)q(X) &= f(X) - f(z) \\[15pt] (\alpha - z)q(\alpha) &= f(\alpha) - f(z) \\[15pt] g^{(\alpha - z)q(\alpha)} &= g^{f(\alpha) - f(z)}\\[15pt] \left(g^{q(\alpha)}\right)^{(\alpha - z)} &= g^{f(\alpha)}g^{-y}\\[15pt] \left(C_{q}\right)^{(\alpha - z)} &= C_{f}g^{-y}\\[15pt] \left(C_{q}\right)^{(\alpha - z)}g^{y} &= C_{f}\\[15pt] e\left(C_{q}^{(\alpha - z)}, h\right) &= e\left(C_{f}g^{-y}, h\right)\\[15pt]\\ e\left(C_{q}, h^{\alpha}h^{-z}\right) &= e\left(C_{f}, h\right)\quad e\left(g^{-y}, h\right)\\[15pt] e\left(C_{q}, v_1h^{-z}\right) &= e\left(C_{f}, h\right)e\left(g^{-y}, h\right)\\[15pt] \end{align} \]