KZG Commitments - theory, applications

Kate, Zaverucha and Goldberg (KZG) commitments serve as both a vector and functional commitment scheme. Using it, you can commit to a vector of values using a polynomial's coefficients or evaluations. Additionally, by enabling the revelation of arbitrary polynomial evaluations later, it can also work as a functional commitment scheme.

KZG proofs have the advantage of being constant size: it is independent of the polynomial's degree or of the number of evaluations we prove - using "multiproofs". Thus, KZG makes commmunication costs between a prover and a verifier quite low. The tradeoff is the requirement to carry out a (re-usable) trusted setup.

Some of the steps laid out here can be followed with accompanying toy arkworks code here. If you want to jump to the cool stuff directly, we review KZG in an applied context at the end of this post.

Algorithm

Recall that a pairing is a bilinear function $e$ such that $\forall a,b \in \mathbb{F}_r$ and $P, Q$ two elements of groups $G_1$ (of order $r$) and $G_2$, we have:

where $\mathbb{F}_r$ is the scalar field of $G_1$.

KZG can be instantiated with any type of pairing group (type 1, type 2 or type 3). Most of recent pairing-based protocols use type 3 curves though. This is today's recommended way of designing things.

In the literature, a polynomial commitment scheme is often defined as a collection of six distinct algorithms: $\mathcal{Setup}$, $\mathcal{Commit}$, $\mathcal{Open}$, $\mathcal{VerifyPoly}$, $\mathcal{CreateWitness}$ and $\mathcal{VerifyEval}$. Let's go through each of them.

1. $\mathcal{Setup}$

Select a pairing friendly curve consisting of groups $G_1$, $G_2$. Choose public generators $g_1 \in G_1$ and $g_2 \in G_2$. Sample at random a secret value $\tau \in \mathbb{F}_r$. We will commit to a univariate polynomial $\phi(x)$ of degree $m$, taken from $\mathbb{F}_r[x]$; i.e. a polynomial with coefficients in the integers modulo $r$.

Compute the trusted setup parameters:

where $n \gt m$. We note $[ \tau^i ]_{1} = \tau^i * g_1$. Hence, $[\tau^0]_1$ will be equal to $g_1$).

Set the verification key:

Where $[ \tau ]_{2}$ is $\tau * g_2$. Finally, get rid of $\tau$.

2. $\mathcal{Commit}$

Compute the commitment $\mathcal{C}$ to $\phi$ with:

This is possible to compute without knowing $\tau$ since:

Elements $[\tau^i]_1$ are from the trusted setup. The commitment $\mathcal{C}$ is a single group element in $g_1$.

3. $\mathcal{Open}$

The prover outputs a polynomial $\tilde{\phi}(x)$. The verifier can run $\mathcal{VerifyPoly}$ to ensure that this opened polynomial corresponds to the commitment $\mathcal{C}$.

4. $\mathcal{VerifyPoly}$

This algorithm is run by the verifier. It takes as input the commitment $\mathcal{C}$ and a polynomial $\tilde{\phi}(x)$ sent by the prover. It checks:

where each $\tilde{a}_i$ is a coefficient of $\tilde{\phi}(x)$. Outputs $1$ if the equality holds, $0$ otherwise.

5. $\mathcal{CreateWitness}$

Creates the evalution proof, proving evaluations of $\phi(x)$ at a point $r$. The prover computes a new univariate polynomial $\psi_r(x)$ :

where $\phi(r)$ is the evaluation of $\phi(x)$ at $r$. The proof $\pi$ is $[\psi_r(\tau)]_1$. The prover does not need to know $\tau$ to compute $\pi$ since:

where each $b_i$ is a coefficient of $\psi_r(x)$. It outputs the tuple $(r, \phi(r), \pi)$.

6. $\mathcal{VerifyEval}$

The verifier wants to check whether the claimed $\phi(r)$ is true. The verifier does not have access to $\phi(x)$, but only to the commitment $\mathcal{C}$, the value $r$, the claimed $\phi(r)$ and the proof $\pi$.

The verifier checks whether this equality holds:

To see why, the verifier's check actually boils down to:

Applications

Here is a quick list of interesting KZG applications.

1. Credentials

This is detailed in section 4.3 of the seminal paper, along with other cool applications. The idea is to have a trusted authority sign a commitment to a polynomial. Evaluations ${(0, \phi(0)), \dots, (n, \phi(n))}$ of this polynomial would correspond to the vector of information which build up a credential's content. Using this signed commitment, a user can then selectively prove a value or a subset of values of his/her credentials information. The verifier will only have to check that the signature of the commmitted polynomial it receives is valid and that the evaluation proof is correct.

2. Proto-danksharding

Ethereum uses the BLS12-381 type-3 pairing friendly curve for EIP-4844 which leverages KZG commitments under the hood. Blob data consists in a vector of 4096 field elements from the scalar field $\mathbb{F}_r$. This vector of field elements is interpreted as coefficients of a polynomial and committed to using KZG. To this end, a point evaluation precompile is being introduced in the EVM. Its use is mainly intended for L2 rollups. Given the large application surface of KZG, I would not be surprised if this precompile were to deviate from its initial purpose in the near future, though.

3. Halo2

Scroll L2 switched Halo2's initial polynomial commitment scheme (a variant of IPA) for KZG. Roughly, KZG is used to commit to witness values and to a quotient polynomial attesting to the fact that the constraint systems is satisfied with this witness. There is a nice post here going over the nitty-gritty.

4. Proof of solvency protocols

V. Buterin described a proof of solvency protocol where a CEX's users and balances would be committed to using KZG. Users would then be able to verify that they have been included into the commitment using evaluation proofs. An additional auxiliary polynomial is used to also prove properties of the exchange's balance sheet - namely that it is solvent. Summa is a project working on this. We also did a simpler example implementation here.

5. Extractable Witness Encryption

As I'm currently updating this blog, let me add this more recent application. In this paper, the authors show how to encrypt a message so that only someone with the knowledge of a valid KZG opening can decrypt it. There is a nice presentation done by Nils Fleischhacker himself here.