Kate-Zaverucha-Goldberg (KZG) Constant-Sized Polynomial Commitments

 

Kate, Zaverucha and Goldberg introduced a constant-sized polynomial commitment scheme in 20101. We refer to this scheme as KZG and quickly introduce it below.

Prerequisites:

Trusted setup

To commit to degree $\le \ell$ polynomials, need $\ell$-SDH public parameters:

Here, $\tau$ is called the trapdoor. These parameters should be generated via a distributed protocol that outputs just the $g^{\tau^i}$’s and forgets the trapdoor $\tau$.

The public parameters are updatable: given $g^{\tau^i}$’s, anyone can update them to $g^{\alpha^i}$’s where $\alpha = \tau + \Delta$ by picking a random $\Delta$ and computing:

This is useful when you want to safely re-use a pre-generated set of public parameters, without trusting that nobody knows the trapdoor.

Commitments

Commitment to $\phi(X)=\prod_{i\in[0,d]} \phi_i X^i$ is $c=g^{\phi(\tau)}$ computed as:

Since it is just one group element, the commitment is constant-sized.

Evaluation proofs

To prove an evaluation $\phi(a) = y$, a quotient is computed in $O(d)$ time:

Then, the constant-sized evaluation proof is:

Note that this leverages the polynomial remainder theorem.

Verifying an evaluation proof

A verifier who has the commitment $c=g^{\phi(\tau)}$ and the proof $\pi=g^{q(\tau)}$ can verify it in constant-time using two pairings:

\begin{align} e(c / g^y, g) &= e(\pi, g^\tau / g^a) \Leftrightarrow\\\ e(g^{\phi(\tau)-y}, g) &= e(g^{q(\tau)}, g^{\tau-a}) \Leftrightarrow\\\ e(g,g)^{\phi(\tau)-y} &= e(g,g)^{q(\tau)(\tau-a)}\\\ \phi(\tau)-y &= q(\tau)(\tau-a) \end{align}

This effectively checks that $q(X) = \frac{\phi(X) - y}{X-a}$ by checking this equality holds for $X=\tau$. In other words, it checks that the polynomial remainder theorem holds at $X=\tau$.

Batch proofs

Can prove multiple evaluations $(\phi(a_i) = y_i)_{i\in I}$ using a constant-sized KZG batch proof $\pi_I = g^{q_I(\tau)}$, where:

\begin{align} \label{eq:batch-proof-rel} q_I(X) &=\frac{\phi(X)-R_I(X)}{A_I(X)}\\\ A_I(X) &=\prod_{i\in I} (X - a_i)\\\ R_I(a_i) &= y_i,\forall i\in I\\\ \end{align}

$R_I(X)$ can be interpolated via Lagrange interpolation as:

Verifying a batch proof

The verifier who has the commitment $c$, the evaluations $(a_i, y_i)_{i\in I}$ and a batch proof $\pi_I=g^{q_I(\tau)}$ can verify them as follows.

  1. First, he interpolates the accumulator polynomial via a subproduct tree in $O(\vert I\vert\log^2{\vert I\vert})$ time2. Then, commits to it as $g^{A_I(\tau)}$ in $O(\vert I \vert)$ time.
  2. Second, he interpolates $R_I(X)$ s.t. $R_I(a_i)=y_i,\forall i \in I$ via fast Lagrange interpolation in $O(\vert I\vert\log^2{\vert I\vert})$ time2. Then, commits to it as $g^{R_I(\tau)}$ in $O(\vert I \vert)$ time.
  3. Third, he checks Equation \ref{eq:batch-proof-rel} holds at $X=\tau$ using two pairings: $e(c / r, g) = e(\pi_I, a)$.

Note that:

\begin{align} e(g^{\phi(\tau) / g^R_I(\tau)}, g) &= e(g^{q_I(\tau)}, g^{A_I(\tau)})\Leftrightarrow\\\ e(g^{\phi(\tau) - R_I(\tau)}, g) &= e(g,g)^{q_I(\tau) A_I(\tau)}\Leftrightarrow\\\ \phi(\tau) - R_I(\tau) &= q_I(\tau) A_I(\tau) \end{align}

References

  1. Polynomial commitments, by Kate, Aniket and Zaverucha, Gregory M and Goldberg, Ian, 2010, [URL] 

  2. Fast polynomial evaluation and interpolation, by von zur Gathen, Joachim and Gerhard, Jurgen, in Modern Computer Algebra, 2013  2