Kate, Zaverucha and Goldberg introduced a constant-sized polynomial commitment scheme in 2010^{1}.
We refer to this scheme as **KZG** and quickly introduce it below.

**Prerequisites:**

- Pairings (or bilinear maps)
- Polynomials

## 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.

- First, he interpolates the
**accumulator polynomial**via a subproduct tree in $O(\vert I\vert\log^2{\vert I\vert})$ time^{2}. Then, commits to it as $g^{A_I(\tau)}$ in $O(\vert I \vert)$ time. - 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})$ time
^{2}. Then, commits to it as $g^{R_I(\tau)}$ in $O(\vert I \vert)$ time. - 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}