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 or simply Kate commitment allows commitment to a polynomial. And polynomial commitments are one of the building blocks of zk-rollups.

So let us take the polynomial

As usually in cryptography, we live in some finite field

A Kate polynomial commitment is value

We will see later what the notation means. What is important is that nobody can extract or even from having just

Also, the committer (the party that computed

) cannot find another polynomial such that This property seems strange, but we will see later why this is so.

For a given

and the committer can prove that it knows a polynomial that evaluates to at This is more powerful than it might seem. I plan to write about it in a post about PLONK.

KZG commitment

Let us say there is some secret value

And let us say and for are publicly known.

But what is this strange

and notation?

just means where is a point on the elliptic curve. And means where is likewise a point on the elliptic curve.

So

means And we cannot extract from knowing because that would mean breaking the elliptic curve discrete logarithm.

And then there is a pairing function:

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

We cannot compute

because is a secret value that nobody knows, but we can compute

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

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

of the same degree as the polynomial is to be found for which it holds that

Let us denote

It holds:

But

has at most zeros and (for example ) is tiny compared to (as in , for example around ). The number of polynomials which evaluate to at is tiny towards the number of all polynomials.

The probability of finding such a polynomial (remember, we do not know

) is negligible.

Trusted setup

Where does

come from?

Nobody is allowed to know

but everybody is allowed to know and for

So, how is this secret value

generated? Well, it can be computed on some computer and this computer can be then thrown away after it spits out the and values. But a more secure way would be to use secure multi-party computation, 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

and the prover needs to provide and a proof that really is the evaluation at of the committed polynomial. This is called opening the polynomial at

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

The prover computes

such that:

Such

exists because

The prover sends the value

to the verifier.

The verifier checks whether:

Note that the left side:

And the right side:

If the equality holds, the verifier knows that the prover knows a polynomial that evaluates to

at

But could the prover not find some values for

and such that

Well, the prover doesn’t know

so it would need to guess the values. The probability of a correct guess is, again, negligible.