KZG Polynomial Commitments

This article is based on Dankrad Feist’s summary on KZG Polynomial Commitments (https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html)

Ozgun Ozerk

Published in

Subspace Network

15 min readOct 24, 2022

What is it good for?

Compared to Merkle tree proofs, the proof size is constant. At the end of this article, we will be able to replace Merkle proofs with KZG polynomial commitments, and our proof will always be constant (48 bytes), regardless of the array size or the polynomial order.

Polynomial commitments via Merkle trees

Recap on polynomials (skip this if you are already familiar with them)

A polynomial is nothing but adding some powers of x, combined with some coefficients. It is demonstrated via: p(X). The tradition is, capital letters are for abstract polynomials, for example, p(X), in this one, X can be anything, it could be the secret key, it could be a random data point, it can be anything. Whereas small letters are for certain values, for example, p(s), in this one, s will be a certain value (the secret key).

Some examples:

The polynomial p(X) can be anything. For example: p(x) = 5x³ + (1)x² + 7x¹ + 6(x⁰), which can be also expressed as:

or p(X) can be: 6x⁵ + 0x⁴ + 0x³ + 0x² + 0x¹ -55x⁰, which is equivalent to:

notice that, even in 6x⁵ — 55, there are actually 6 coefficients (0’s are omitted for brevity) → 6, 0, 0, 0, 0, -55

Recap on polynomials (end)

The relationship between data and polynomials:

It is enough to have only coefficients to construct a polynomial. We can treat our data points as coefficients, allowing us to construct a polynomial for our data.

If our data is 6, 0, 0, 0, 0, -55 → then the polynomial will be 6x⁵ + 0x⁴ + 0x³ + 0x² + 0x¹ -55x⁰, or for the shorter version: 6x⁵ — 55. There is exactly one and only one polynomial for a specific coefficient set. In other words, there is one-to-one mapping between polynomials and coefficients.

Have some math culture! Mmmhh, delicious:

the formal definition is:

where cᵢ’s are the coefficients. For the ones who don’t like math, this mambo-jambo basically means:

multiply the coefficients cᵢ with powers of x
then add them all together

in the end, we will have a polynomial with a degree of n (which means, the highest power of x will be n)

What are polynomial commitments?

This means, we will commit to some polynomial p(X), and then we will claim that at the point z, this very polynomial will give the result y. In math language, p(z) = y.

The verifier will request a proof that we did not change the polynomial in order to make p(z) = y. In other words, the verifier wants to be sure about the equation p(z) = y will hold only for the very polynomial that is selected in the beginning.

To provide a proof to the verifier, we can commit to the polynomial selected in the beginning. How? By calculating the Merkle root of the coefficients.

Introduction to Merkle trees

An Example Run of Constructing a Polynomial Commitment using Merkle Trees:

Say our p(X) = 5x³ + (1)x² + 0x¹ + 6(x⁰) = 5x³ + x² + 6
The coefficients are: 5, 1, 0, 6Now, we will build a Merkle tree out of these coefficients.

I used this link to generate this image: https://blockchain-academy.hs-mittweida.de/merkle-tree/

As the first thing, we will send our commitment (the Merkle root) to the verifier. Then the verifier will give us a value (say, it will be $2$), and ask for the evaluation of this value for our polynomial. Note that, the verifier does not know the polynomial yet.

Now, say we are the prover, and our claim is p(2) = 50, which is correct (we choose not to cheat). But there can be multiple polynomials that can hold the above equation, for example: p’(X) = 25x

We should prove that the equation p(2) = 50 holds for the original polynomial, which is p(X) = 5x³ + x² + 6

To prove this, we can send all the coefficients to the verifier 5, 1, 0, 6 and the Merkle root: c297747c8df365fd5618743f2a9fbd78fec142e66e572a054e14e1b731e27a58

The verifier will check for 2 things:

given the polynomial coefficients, she will construct the polynomial, and compute the result herself, and check if our claimed result is matching with what she computed → p(2) =? 50. If they are matching, good! If the computed results are not matching, that means someone in this protocol is not… very smart :)
if the first check holds, then she will construct the Merkle tree for these coefficients herself, and compare our Merkle root provided in the proof, with her Merkle root (which she computed herself). If they are matching, that means we did not change the polynomial!

Why the Merkle root is enough to prove that we did not change the polynomial?

Because: hash functions are not reversible. If we found another polynomial, for which the equation is true → p’(X) = 25x, then we have to send the coefficients of this polynomial to the verifier, and generate a Merkle tree from the coefficients for this polynomial. Recall that we already sent a Merkle root to the verifier as the first step of the protocol, and generating a fake polynomial for which the Merkle root will be equal to the one we sent to the verifier, is practically impossible.

Summary of the protocol:

the prover has a polynomial, he commits to it, and sends the commitment to the verifier
the verifier has a value, sends this to the prover, and asks for an evaluation for this value
prover evaluates the value, sends the result, and sends the coefficients of the polynomial
verifier constructs the polynomial herself, computes the result for the value, checks if the prover’s evaluation is the same
the verifier also constructs the Merkle tree for the coefficients, checks if the prover’s Merkle root is the same

Let’s overview the properties of this scheme:

the commitment was a single element, which is the Merkle root (typically 32 bytes)
the prover had to send all the coefficients
the whole polynomial is shared with the verifier, nothing is secret in this scheme
the data that need to be sent to the verifier is linear: if our polynomial had 1.000.000 coefficients, then we will send 1.000.000 coefficients… In other words, the proof grows as the polynomial grows, this is not very scalable
the verifier had to reconstruct the polynomial, re-calculate the whole computation
verifier had to reconstruct the whole Merkle tree

Committing to a polynomial via Merkle trees did not make much sense? Great! Because it doesn’t… It is silly and inefficient. But it will help us understand what polynomial commitments are, and then we will significantly improve it using Kate Proofs.

What we will achieve with Kate scheme:

commitment size will be 48 bytes (yeah, 12 bytes larger than before)
The proof size, independent of the size of the polynomial, is always only one group element. Verification, independent of the size of the polynomial, requires two group multiplications and two pairings, no matter what the degree of the polynomial is. This means, the proof size is constant! UNBELIEVABLE!
The scheme hides the polynomial (practically: yes; theoretically: not 100%, if the polynomial is very simple, it can be guessed. But it shouldn’t be simple in the first place hehe)

The promises are amazing! Let’s try to learn how it works.

Combining Elliptic Curves and Secure Multi-Party Computation

In cryptography, we have access to a powerful tool, called secure multi party computation (MPC). It basically allows us to collectively generate a secret (let’s denote this with s, and derive some other things from this secret, and in the end (here is the good part), no one will know the secret!

In order to reveal s, all the participants would have to collude (they cannot reveal the secret even if all of them are compromised, except one).

Now, the best part is coming: without knowing the value of this secret number s (that is why, it is secret), we can actually compute p(s) in an elliptic curve setting.

How? Well, if you are unfamiliar with basic elliptic curve cryptography, you might need to read the first parts of this series.

Our special thanks to Medium: I cannot put the below symbol in here (except as an image)

So, I will use G (bold G) for referring to it.

Let G be the points on our elliptic curve, and G be the generator of G.

A generator is a point on the elliptic curve, a base point, which, when added to itself generates all other points on the curve. A simple analogy would be 1 for integers: 1+1 = 2, 1+1+1 = 3, and so on, you can get any integer by adding 1 to itself enough times.

Then, [x] is defined as:

In other words, [x] converts x to a point in the elliptic curve (it will correspond to one of the points in G.

A good property of elliptic curves is you cannot derive the value of x from [x]. After multiplying x with G, the value of x is now hidden. You cannot simply divide [x] with G, if you are wondering why, well, the link for ECC is still up there :)

So, the first thing we will do in our scheme, is to generate a secret number s, and then compute:

(where n is the order(degree) of our polynomial), in an MPC setting. These computed values will be public knowledge, everyone will have access to them. But remember, it is impossible to deduce s from these computed values, and also, it is impossible to compute another power of s from these. In other words, we cannot compute:

What we can do with these computed values instead, is:

we can multiply those with a coefficient. Multiplying s with G will allow us to hide s (thanks to elliptic curves)

That means, we can actually compute [p(s)], by basically multiplying every coefficient cᵢ with [sⁱ],
going back to one of our examples, our coefficients were:6,0,0,0,0,-55
so we should compute 6[s⁵] + 0[s⁴] + 0[s³] + 0[s²] + 0[s¹] — 55[s⁰]
the whole thing can be shown with:

This means, we just computed the elliptic curve point equivalent of p(s), (which is [p(s)] ), without knowing the secret value s.

Kate Commitment

Pronounced kah-tey

In KZG polynomial commitment scheme, the prover first needs to commit to the polynomial p(X) (this polynomial will be generated from our data points, for example, our data points can be the coefficients of this polynomial), and then submit a proof π, along with his claim p(z) = y. I’ll explain what that all means soon, but we have to go step-by-step.

The point z will be selected by the verifier, and sent to the prover after the prover sends his commitment C = [p(s)], which is a commitment to the polynomial p(X).

The things that the prover needs to know/compute:

C = [p(s)] → The prover knows the polynomial p(X), and we showed above how [p(s)] can be computed via an MPC setting.
p(z) = y → z is provided to the prover from the verifier. The prover knows the polynomial itself, this is trivial
π, the proof → we haven’t talked about it yet. Let’s begin!

Now, the proof is another polynomial, which will help us to construct a relationship with the original polynomial p(x). This will become handy when we want to prove we did not change the original polynomial as the prover. Because remember, we are not using Merkle proofs, and we need to have a way to prove that we did not change the original polynomial.

And it is time for some polynomial math!

If a polynomial p(X) has a zero at point m, that means the polynomial p(X) is divisible by the term X — m. Being divisible by the term X — m means we can write the following: p(X) = (X-m).q(X) for some other polynomial q(X). And this equation clearly evaluates to zero at the point X = m

An example:

p(X) = 3x² — 5x — 2 (let this be our polynomial)
p(2) = 3(2²) — 5(2) — 2 = 0 (and we find a number that makes our polynomial evaluate to 0)
p(X) = 3x² — 5x — 2 = (X — 2).q(X)
(ughhh… I have to use an image again)

5. q(X) = 3x + 1

If you are confused about steps 4 and 5, we can divide polynomials using 2 different methods, one of them is by simple division (1), and the other one is by factorization (2).

Coming to the crucial part:

we want to prove p(z) = y
we know p(X) — y will be zero at the point X = z
in other words, we know X — z divides p(X) — y
what we have is:

5. we can compute the polynomial q(X) now (as shown above).

6. X can be anything, so let it be s

7. we now have the following relationship:

8. or another way to display this relationship: p(s) — y = q(s).(s-z)

We cannot work directly with this relationship, because neither the prover nor the verifier does know the value s. What they know is: [sⁱ].

This relationship itself can be the thing that will convince the verifier. The explanation of why this relationship should convince the verifier will be a bit long for this article, but if you want to, you can read it here.

Finalizing our proof with Kate Commitment

Let’s recall our relationship:

And remember, we cannot work directly with this relationship, because neither the prover nor the verifier knows s. What they know is, [sⁱ]. And seems like that is enough!

The proof evaluation will work as the following:

[q(s)] is our proof π.

What we’ve done is, we used [sⁱ] values to turn our equation into points in the elliptic curve.

So if we multiply [q(s)] with [s — z], and check if that is equal to C — [y], we should be good to go for this scheme! And remember, all these are points on the elliptic curve.

However… there is one issue… we cannot multiply elliptic curve points :’)
To simulate this multiplication, we will use something called pairing.

Elliptic Curve Pairing

Pairing is an abstract definition, which will help us to multiply (kind of) two different elliptic curve points. A very basic (and probably wrong) summary could be useful to make it more tangible for our brains:

where Q and P are some points on the elliptic curve, and O is an integer (or a complex number) in the multiplicative group. Basically, we “multiplied” Q and P, and get a result of O.

Feel free to treat this as a black box if you are not a math nerd. Otherwise, here is a better explanation of pairing, enjoy!

Coming back to Kate proofs

Recall: Let G be the points on our elliptic curve, and G be the generator of G. Then, [x] is defined as → [x] = xG. In other words, [x] converts x to a point in the elliptic curve (corresponding to one of the points in G).

Now we change it as the following:

Let G₁ and G₂ be two different subgroups of the same elliptic curve
G be the generator of G₁, and H be the generator of G₂,
Then, [x]₁ is defined as → [x]₁ = xG
And, [x]₂ is defined as → [x]₂ = xH
Lastly, let's define our pairing e: G₁ x G₂ → Gₜ, where Gₜ is the multiplicative target group

Of course, from the secret value s, now two different sets will be distributed, one for [sⁱ]₁, and one for [sⁱ]₂

The verifier should now check the equality of:

which is equivalent to:

to which, we are very accustomed to by now :)

The verifier is able to do the computations:

[q(s)] is provided to the verifier from the prover
z is selected by the verifier
the verifier can compute [s — z]₂, since she has access to [s]₂, and computing [s — z]₂ is equal to computing [s]₂ — [z]₂
C is provided to her by the prover
she also knows the value y (sent by the prover)
H is public
pairing function is public

The full workflow:

using an MPC setup, the secret s is generated, and using this secret value, two sets will be distributed publicly, one for [sⁱ]₁, and one for [sⁱ]₂. The secret s is then discarded forever.
the prover selects a polynomial, and commits to it: C = [p(s)]₁, using [sⁱ]₁, and sends this to the verifier.
verifier asks for the evaluation of the committed polynomial at point z.
prover sends the following to the verifier:
— π
— y
the verifier checks the equation: e(π, [s — z]₂) = e(C — [y]₁, H)
— if the equation holds, the verifier accepts the proof
— if the equation does not hold, the verifier rejects the proof

We just showed how to prove an evaluation of a polynomial at a single point, using only one element as the proof! Using Merkle proofs, we would have to send all the coefficients to the verifier to prove that p(z) = y

Batch-proofs (multi proofs)

We can go even further! Let’s show how to evaluate a polynomial at ANY number of points and prove it, using still ONLY ONE element.

Say we want to prove the evaluation of k points:

Using an interpolation polynomial, we can find a polynomial of degree less than k, that goes through all these points. Using Lagrange interpolation, we can compute this interpolation polynomial. I know this may sound advanced, and it is. Google and YouTube will be your friends for understanding how Lagrange interpolation works.

The formula for computing the interpolation polynomial is as follows:

Since our original polynomial p(X) is passing through all these points, the polynomial p(X) — I(X) will be zero at each:

Thus, this polynomial will be divisible by:

So, we define our zero polynomial as:

Using the zero polynomial, we can again establish a similar relationship that we did before:

We now define the Kate multiproof for the evaluations of the points:

Notice that our proof is still a single element!

Some differences in this scheme:

the verifier needs to compute Z(X) and I(X), for computing these, she is going to need the k points.
she also will compute [I(s)]₁ and [Z(s)]₂, for computing these, she needs the sets [sⁱ]₁ and [sⁱ]₂

The equation the verifier needs to check is as the following:

which evaluates into:

And via this, we just proved the evaluation of ANY number of points on our polynomial, again providing a single element as a proof!

Kate as a vector commitment

It is actually quite easy to convert Kate polynomial commitment into a vector commitment. And via doing this, we will achieve the following:

instead of sending log(n) hashes to prove a single element, we will send only one element!
our proof will consist of only one element, regardless of the vector size!

Here is how:

Previously, we were creating a polynomial using our data points as the coefficients. Now, we will do something different: say we have the elements:

And say p(X) is the polynomial that will evaluate to these elements as the following: p(i) = aᵢ.

So, for example, to reach a₂, we will plug in the value 2 to our p(X). We know there always is a polynomial that is passing through the points we like. Again, Lagrange interpolation will help us: