KZG commitments

Commitment schemes are used heavily in cryptography. In a nutshell, committing to some value means you cannot change this value later and this value is hidden to others. A Kate-Zaverucha-Goldberg commitment (opens new window) or simply Kate commitment allows commitment to a polynomial. And polynomial commitments are one of the building blocks of zk-rollups (opens new window).

So let us take the polynomial $p(x) = a_0 + a_1 x + ... + a_n x^n$. As usually in cryptography, we live in some finite field $F_q$.

A Kate polynomial commitment is value $[p(s)]_1.$. We will see later what the notation $[]_1$ means. What is important is that nobody can extract $p$ or even $p(s)$ from having just $[p(s)]_1$.

Also, the committer (the party that computed $[p(s)]_1$) cannot find another polynomial $q$ such that $q(s) = p(s)$. This property seems strange, but we will see later why this is so.

For a given $\chi$ and $\bar p$ the committer can prove that it knows a polynomial that evaluates to $\bar p$ at $\chi$. This is more powerful than it might seem. I plan to write about it in a post about PLONK (opens new window).

Commitment

Let us say there is some secret value $s$. And let us say $[s^i]_1$ and $[s^i]_2$ for $i = 0, ..., n-1$ are publicly known.

But what is this strange $[]_1$ and $[]_2$ notation?

$[t]_1$ just means $tG$ where $G$ is a point on the elliptic curve. And $[t]_2$ means $tH$ where $H$ is likewise a point on the elliptic curve.

So $[p(s)]_1$ means $p(s) G$. And we cannot extract $p(s)$ from knowing $p(s) G$, because that would mean breaking the elliptic curve discrete logarithm.

And then there is a pairing function:

A pairing is a map $e: G_1 \times G_2 \rightarrow G_T$ such that:

• $G_1, G_2, G_T$ are cyclic groups of prime order $p$.
• $e: G_1 \times G_2 \rightarrow G_T$ is bilinear, i.e. for all $G \in G_1, H \in G_2,$ and $a, b \in \mathbb{Z}$, $e(aG, bH) = e(G, H)^{ab}$.
• $e$ is an admissible bilinear map, i.e.
  • $e$ is efficiently computable
  • if $G$ and $H$ are generators of $G_1$ and $G_2$, then $G_T$ is generated by $e(G, H)$.
• The discrete logarithm problem is hard to compute in $G_1, G_2$, and $G_T$.

The math behind pairings is a complex topic and I plan to write a lot about it on these pages. But if you use a pairing function just as a black box and don’t mind what’s inside, then the polynomial commitments based on pairings are a surprisingly simple construct.

So, back to our polynomial $p$.

We cannot compute $p(s) = a_0 + a_1 s + ... + a_n s^n$ because $s$ is a secret value that nobody knows, but we can compute $[p(s)]_1$:

$[p(s)]_1 = [(a_0 + a_1 s + ... + a_n s^n) G]_1 = a_0 [s^0]_1 + a_1 [s^1]_1 + ... + a_n [s^n]_1$

And this value is a KZG (or Kate) commitment to the polynomial $p$.

Can the committer switch (cheat) to another polynomial?

Are there not many other polynomials that commit to the same value?

Yes, there are. But how likely is it that the polynomial $r$ of the same degree $n$ as the polynomial $p$ is to be found for which it holds that $p(s) = r(s)$?

Let us denote $h(x) = p(x) - r(x)$. It holds: $h(s) = 0$.

But $h$ has at most $n$ zeros and $n$ (for example $2^{28}$) is tiny compared to $q$ (as in $F_q$, for example around $2^{256}$). The number of polynomials which evaluate to $0$ at $s$ is tiny towards the number of all polynomials.

The probability of finding such a polynomial (remember, we do not know $s$) is negligible.

Trusted setup

Where does $s$ come from?

Nobody is allowed to know $s$, but everybody is allowed to know $[s^i]_1$ and $[s^i]_2$ for $i = 0, ..., n-1$.

So, how is this secret value $s$ generated? Well, it can be computed on some computer and this computer can be then thrown away after it spits out the $[s^i]_1$ and $[s^i]_2$ values. But a more secure way would be to use secure multi-party computation (opens new window), so that multiple subjects compute it, but none of them actually knows the value.

Opening

Having a commitment, how do we prove anything about the polynomial?

The verifier chooses a random $\chi \in F_q$ and the prover needs to provide $\bar p = p(\chi)$ and a proof that $\bar p$ really is the evaluation at $\chi$ of the committed polynomial. This is called opening the polynomial at $\chi$.

By opening at one point the prover proves that it knows the polynomial that it has committed to.

The prover computes $g(x)$ such that:

$p(x) - \bar{p} = g(x) (x - \chi)$

Such $g(x)$ exists because $\bar p = p(\chi)$.

The prover sends the value $[g(s)]_1$ to the verifier.

The verifier checks whether:

$e([p(s) - \bar p]_1, [1]_2) = e([g(s)]_1, [(s - \chi)]_2)$

Note that the left side:

$e([p(s) - \bar p]_1, [1]_2) = e((p(s) - \bar p) G), H) = e(G, H)^{p(s) - \bar p}$

And the right side:

$e([g(s)]_1, [(s - \chi)]_2) = e(g(s) G, (s - \chi) H) = e(G, H)^{g(s)(s-\chi)}$

If the equality holds, the verifier knows that the prover knows a polynomial that evaluates to $\bar p$ at $\chi$.

But could the prover not find some values for $\bar p$ and $g(s)$ such that $p(s) - \bar p = g(s) (s-\chi)$?

Well, the prover doesn’t know $s$, so it would need to guess the values. The probability of a correct guess is, again, negligible.