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

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

Prerequisites:

• Cyclic groups of prime order and finite fields ${\mathbb{Z}}_p$
• Pairings (or bilinear maps)
• Polynomials

Trusted setup

To commit to degree $\le \ell$ polynomials, need $\ell$-SDH public parameters: $(g,g^{\tau },g^{{\tau }^2},\dots ,g^{{\tau }^{\ell }})=(g^{{\tau }^i}{)}_{i\in [0,\ell ]}$

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 \mathrm{\Delta }$ by picking a random $\mathrm{\Delta }$ and computing: $g^{{\alpha }^i}={\left(g^{{\tau }^i}\right)}^{{\mathrm{\Delta }}^i}$

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 $\varphi (X)=\sum _{i\in [0,d]}{\varphi }_i{X}^i$ is $c=g^{\varphi (\tau )}$ computed as:

$$\begin{array}{}\text{(1)}& c=\prod _{i\in [0,\mathrm{deg}\varphi ]}{\left(g^{{\tau }^i}\right)}^{{\varphi }_i}\end{array}$$

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

Evaluation proofs

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

$$\begin{array}{}\text{(2)}& q(X)=\frac{\varphi (X)-y}{X-a}\end{array}$$

Then, the constant-sized evaluation proof is:

$$\begin{array}{}\text{(3)}& \pi =g^{q(\tau )}\end{array}$$

Note that this leverages the polynomial remainder theorem.

Verifying an evaluation proof

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

$$\begin{array}{}\text{(4)}& e(c/g^y,g)& =e(\pi ,g^{\tau }/g^a)\iff \text{(5)}& e(g^{\varphi (\tau )-y},g)& =e(g^{q(\tau )},g^{\tau -a})\iff \text{(6)}& e(g,g{)}^{\varphi (\tau )-y}& =e(g,g{)}^{q(\tau )(\tau -a)}\text{(7)}& \varphi (\tau )-y& =q(\tau )(\tau -a)\end{array}$$

This effectively checks that $q(X)=\frac{\varphi (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

One can prove multiple evaluations $(\varphi (e_i)=y_i{)}_{i\in I}$ for arbitrary points $e_i$ using a constant-sized KZG batch proof ${\pi }_I=g^{q_I(\tau )}$, where:

$$\begin{array}{}\text{(8)}& q_I(X)& =\frac{\varphi (X)-R_I(X)}{A_I(X)}\text{(9)}& A_I(X)& =\prod _{i\in I}(X-e_i)\text{(10)}& R_I(e_i)& =y_i,\mathrm{\forall }i\in I\end{array}$$

$R_I(X)$ can be interpolated via Lagrange interpolation in $O(|I|{\log }^2|I|)$ time⁵ as:

$$\begin{array}{}\text{(11)}& R_I(X)=\sum _{i\in I}{y}_i\prod _{j\in I,j\ne i}\frac{X-e_j}{e_i-e_j}\end{array}$$

$A_I(X)$ can be computed in $O(|I|{\log }^2|I|)$ time via a subproduct tree in $O(|I|{\log }^2|I|)$ time⁵, as depicted below (for $|I|=8$). The computation proceeds downwards, in the direction of the arrows, with the $(X-e_i)$ monomials being computed first.

Each node in the subproduct tree multiplies the polynomials stored in its two children nodes. This way, the root polynomial will be exactly $A_I(X)$. If FFT-based multiplication is used, the time to compute a subproduct tree of size $n$ is:

$$\begin{array}{}\text{(12)}& T(n)& =2T(n/2)+O(n\log n)\text{(13)}& & =O(n{\log }^{2}n)\end{array}$$

Observation 1: I believe computing $A_I(X)$ faster for arbitrary points $e_i$ is not possible, but I would be happy to be contradicted!

Observation 2: In practice, the algorithms for computing $R_I(X)$ and $A_I(X)$ efficiently would require FFT-based techniques for polynomial division and multiplication, and FFTs are fastest when the finite field ${\mathbb{Z}}_p$ is endowed with $d$th roots of unity for sufficiently high $d$, on the order of the degrees of $R_I(X)$ and $A_I(X)$.

Verifying a batch proof

The verifier who has the commitment $c$, the evaluations $(e_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 $A_I(X)=\prod _{i\in I}(X-e_i)$ as discussed above. Then, commits to in $O(|I|)$ time: $$\begin{array}{}\text{(14)}& a& =g^{A_I(\tau )}\end{array}$$
2. Second, he interpolates $R_I(X)$ s.t. $R_I(e_i)=y_i,\mathrm{\forall }i\in I$ as discussed above. Then, commits to in $O(|I|)$ time: $$\begin{array}{}\text{(15)}& r& =g^{R_I(\tau )}\end{array}$$
3. Third, he checks Equation $\text{8}$ holds at $X=\tau$ using two pairings: $e(c/r,g)=e({\pi }_I,a)$.

Note that:

$$\begin{array}{}\text{(16)}& e(g^{\varphi (\tau )}/g^{R_I(\tau )},g)& =e(g^{q_I(\tau )},g^{A_I(\tau )})\iff \text{(17)}& e(g^{\varphi (\tau )-R_I(\tau )},g)& =e(g,g{)}^{q_I(\tau )A_I(\tau )}\iff \text{(18)}& \varphi (\tau )-R_I(\tau )& =q_I(\tau )A_I(\tau )\end{array}$$

Aggregation of proofs

For now, we discuss proof aggregation in a different blog post on building vector commitments (VCs) from KZG.

Applications

There are many cryptographic tools one can build using polynomial commitment schemes such as KZG.

Here’s a few we’ve blogged about in the past:

• Cryptographic accumulators
• Vector Commitments (VC) schemes with $O(\log n)$-sized proofs or with $O(1)$-sized proofs
• Range proofs

Appendix

Recently, Cohen et al.⁶ showed that an MPC ceremony for generating $g_1,g_1^{\tau },\dots ,g_1^{{\tau }^q}$ “powers-of-$\tau$” tolerates bias and so does not need a final random beacon contribution.

Acknowledgements

Many thanks to Shravan Srinivasan and Philipp Jovanovic for really helping improve this post.