notes - April 12, 2023

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

the committer can prove that it knows a polynomial that evaluates to
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
are publicly known.

But what is this strange


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


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

And then there is a pairing function:

A pairing is a map
such that:
  • are cyclic groups of prime order
  • is bilinear, i.e. for all
  • is an admissible bilinear map, i.e.
    • is efficiently computable
    • if
      are generators of
      is generated by
  • The discrete logarithm problem is hard to compute in

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

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:


has at most
zeros and
(for example
) is tiny compared to
(as in
, for example around
). The number of polynomials which evaluate to
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

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


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:


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


But could the prover not find some values for

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.

Boogie Math Newsletter

Some characters on this website might be partially or entirely fictional. You have been warned, my friend!

© 2023 Boogie Math, all rights reserved Follow us: Twitter