KZG Polynomial Commitments

In the first part of the article (refer here), we introduced zero-knowledge proofs and their different types. We started constructing a zk-SNARK for a simple problem by creating an arithmetic circuit, representing it as an R1CS, and ultimately converting it into polynomials using QAP. Now that the statement is in polynomial form and ready for cryptography, we'll examine the properties that make polynomials suitable for cryptographic use and investigate some other cryptographic tools available.

Remember the matrix-form polynomials we obtained from the QAP transformation in our previous article? When we multiply them by the solution vector s [1, 5, 37, 25, 30], we get the following polynomials for each matrix:

Ap [-38.0, 52.0, -9.0],

Bp [13.0, -10.0, 2.0], and

Cp [22.0, 2.0, 1.0].

After multiplying these polynomials together, we obtain the final polynomial:

\(-516x^4 + 1054x^3 - 714x^2 + 194x -18\)

This polynomial encapsulates the computations we performed and the ultimate solution to our initial problem. If someone knows this polynomial, they can claim to have knowledge of the solution to the problem:

\(x^2 + x + 7 = 37\)

Selected properties of polynomials

Polynomials are useful in cryptography because they can represent complex mathematical constructs and be used for encrypting and decrypting messages. They also can store large amounts of data, as we saw in the previous article. Furthermore, finding intersections between two slightly different polynomials by randomly picking points is extremely difficult, as we will see shortly.

The degree of a polynomial is determined by the highest exponent of an x coordinate within the polynomial. The example of a polynomial of degree 3 is:

\(x^3 - 2x^2 + 1\)

Let's compare this polynomial to another similar polynomial, and see how they fit on the coordinate plane.

\(x^3 - x^2 + 1\)

Despite their near-identical nature, their positions on the plane differ significantly. The key takeaway is that it's almost impossible to find two distinct polynomials with common points.

To find out if two polynomials share a common point (or cross paths), we need to set them equal to each other. Take this example:

\(x^3 - 2x^2 + 1 = x^3 - x^2 + 1\)

Solving for x gives us x = 1, a polynomial of degree 1. This means they only intersect at one point, which is x = 1. So, a polynomial of degree d can have up to d intersection points. This tells us that evaluating a polynomial at certain points gives us an accurate representation of the whole polynomial.

In this situation, a prover can show to a verifier, who knows a specific polynomial, that they know the polynomial too by evaluating it at certain points. For a polynomial of degree d and a coordinate x in the range

\(\langle 0, 10^{10} \rangle, \text{there's a} \; \frac{d}{10^{10}}\)

chance that this polynomial has some overlapping points with another polynomial.

Another critical property of polynomials from a cryptography perspective is their ability to be factored. All polynomials with a valid solution (resulting in 0 after evaluation for x) can be reduced to separate degree 1 polynomials. For example, the polynomial x³ + 3x² + 2x is equivalent to (x+0)(x+1)(x+2). By looking at the factored polynomial, it's easy to identify its solutions (or roots): 0, -1, and -2.

Let's say a prover claims to know a degree 3 polynomial that has roots at -1 and -2. We can then determine that the polynomial will be (x+1)(x+2). As the prover knows a degree 3 polynomial, there must be another polynomial, z(x), which yields the desired result when multiplied with the target polynomial:

\(t(x) = (x+1)(x+2)\)

Thus, we have the equation:

\(p(x) = t(x) * z(x)\)

With this knowledge, how do we find z(x)? We can divide the polynomial p(x) by the target polynomial t(x), resulting in:

\(z(x) = \frac{p(x)}{t(x)}\)

Now, if the polynomial p(x) indeed has roots at -1 and -2, the division outcome will not have a remainder. Let's examine this using our example and perform the calculation:

In the example above, we transformed the target polynomial t(x) from its factored form (x+1)(x+2) to x^2 + 3x + 2. This calculation gives us a result of z(x) = x, with no remainder. Now, let's see what happens when we make a small change to the polynomial p(x) for comparison.

The polynomial p(x) now begins with 2x³ instead of x², resulting in a division remainder of 7x+6!

With this understanding, we can develop a simple protocol where:

1. A verifier randomly generates a value x, evaluates the target polynomial t(x), and provides the value x to the prover.

2. The prover evaluates the polynomial p(x) at the given value x, calculates h(x), and provides evaluations of p and x to the verifier.

3. If the equation p(x) = t(x) * z(x) holds, then p(x) has factors t(x).

Note that the values the prover provides to the verifier are evaluations of the polynomial at x, so the verifier does not know the polynomial itself. However, this protocol allows the prover to cheat and compute another polynomial by merely selecting a random value of z(x). Additionally, it doesn't enforce the polynomial's degree, as the verifier can create a polynomial of any degree that makes p(x) = t(x) * z(x) hold. Both limitations will be addressed later.

Modular math and cyclic groups

Before we dive into commitment schemes, let's explore modular math and prime fields.

A prime field p is a group with p elements that is generated by a single element g, and every element in the group can be written as g^k for some integer k in the range {0, 1, 2, ..., p-1}. The group's order is equal to the number of elements in the group, which is p. A simple example of a prime order p group is the group of integers modulo a prime number p.

For example, if we choose p = 7, then Z_7 is the cyclic group {0, 1, 2, 3, 4, 5, 6}. Let's choose the generator g = 3, which means that the powers of 3 modulo 7 generate all the elements in the group:

\(\begin{align*} 3^0 &\equiv 1 \pmod{7} \\ 3^1 &\equiv 3 \pmod{7} \\ 3^2 &\equiv 2 \pmod{7} \\ 3^3 &\equiv 6 \pmod{7} \\ 3^4 &\equiv 4 \pmod{7} \\ 3^5 &\equiv 5 \pmod{7} \\ 3^6 &\equiv 1 \pmod{7} \end{align*}\)

In modular math, the result of a calculation is expressed as the "remainder" from the calculation on the left-hand side and division by p. In the above example, the first two results don't leave any remainder, as the numbers are smaller than p. But, for any calculation where the result is greater than or equal to p, the modular calculation outcome will be the remainder (though division is more complex).

Why is this important? In cryptography, modular arithmetic is useful to ensure that a committed value or hashed input remains concealed. If we operated on natural numbers, it could be easier to reverse engineer the hiding of an underlying value, weakening the protocol. But, when using modular arithmetic and limiting the results of any calculation to a few possible outcomes, it's much harder to return to the original value, as many different starting points can lead to the same result.

Now that we've learned about two powerful mathematical tools in cryptography - polynomials and modular math - let's delve deeper.

Cryptographic commitments

A cryptographic commitment scheme is a technique that allows someone to commit to a value without revealing it and later prove that the value hasn't been changed or tampered with.

In a commitment scheme, the committing party uses a mathematical algorithm (like a hash function) to create a commitment, which is a fixed-length string representing the hidden value. The commitment is shared with the other party, who can't deduce anything about the value of the commitment itself.

To illustrate this idea, imagine Alice and Bob, two friends who love playing games together. Alice has to leave town for a while, but they decide to keep playing games over the phone. They choose rock-paper-scissors but, being competitive, they don't trust each other to reveal their picks honestly. So, Alice and Bob create a protocol for playing rock-paper-scissors remotely:

1. They agree on a cryptographic hash function, such as SHA-256.

2. They agree on a secret "salt" value that'll be added to each move before hashing to prevent pre-computed hashes. The salt should remain secret and change after each round.

3. Alice and Bob secretly pick a move each.

4. They both compute a commitment to their move by hashing their move and the salt value with the agreed hash function. For instance, Alice might calculate: H(Alice's move) = SHA-256("rock" || salt) where "rock" is her move and "salt" is the secret salt. Bob does the same for his move.

5. They exchange commitments over the phone, without disclosing their moves or the salt value.

6. After exchanging commitments, they "reveal" their moves and the salt value by telling each other their choices and the salt value.

7. They verify that the other player's commitment matches the revealed move and the correct salt value by hashing the move and salt value together.

Alice and Bob can now repeat steps 4-7 for as many rounds as desired, changing the salt value after each round.

Polynomial commitments

Polynomial commitment schemes (PCS) work like cryptographic commitments, but for carrying information they use polynomials instead of regular statements. In a PCS, a prover wants to show to a verifier that they know a polynomial without revealing its coefficients. To do this, the prover creates a commitment to the polynomial and the verifier can then use this commitment to make sure the polynomial is correctly computed at specific points, without actually seeing the coefficients.

Each PCS needs to have the following properties:

• Binding - different polynomials can't result in the same commitment.

• Hiding - a commitment doesn't give away any information about the polynomial.

These properties are similar to the one-wayness and collision resistance of hash functions. There are different types of PCS used in ZK-SNARKs, and each has its pros and cons. The most popular commitment scheme is KZG (from Kate, Zaverucha, Goldberg). Other commitment schemes with different properties used in SNARKs are FRI and DARK.

KZG boasts several distinct features that make it particularly useful for SNARKs:

• Generates constant-size proofs regardless of polynomial length (a single elliptic curve group element).

• Offers constant verification time (two pairing operations).

• Uses elliptic curve pairings as its cryptographic engine.

However, KZG needs a trusted setup, which means a trusted party (or parties) has to generate secret, random values to hide the polynomial (akin to Alice and Bob's "salt" value in their phone game). These values, used to calculate a common reference string (CRS), should then be destroyed so nobody can learn them and break the protocol.

In practice, to lower the risk of a malicious agent, multiple parties join the trusted setup creation process and generate their own parameters ("salt" values), which are multiplied by values created by other participants (Multi-Party Computation, or MPC). With this approach, as long as one party is honest and doesn't share its generated parameters, the whole procedure stays safe. When you hear about a "ceremony" for a trusted setup, that's what's going on.

Elliptic curve pairings

Elliptic curve pairings are a complex encryption technique that employs advanced mathematical algorithms to protect data. They utilize an elliptic curve along with a special mathematical operation called a pairing to perform cryptographic tasks.

An elliptic curve is a mathematical object that looks like a wavy line on a coordinate plane. It is defined by the equation:

\(y^2 = x^3 + a*x + b\)

representing a smooth curve in a two-dimensional space (over a prime field). In the context of cryptography, elliptic curves are usually defined over finite fields, particularly over prime fields (integers modulo a prime number).

Pairing is a unique kind of function that combines two points on an elliptic curve to generate an element of a target group (a multiplicative group of a finite field). Bilinear pairings are the most frequently used pairings in cryptography. For a pairing e: G1 x G2 → GT, where G1 and G2 are cyclic groups and GT is the target group, the function e is bilinear if it satisfies the equation:

\(e(g^a, f^b) = e(a^g, b^f) = e(ab^{gf}) \quad \forall g \in G_1, f \in G_2\)

and integers a and b. Elliptic curve pairings thus enable the multiplication of exponents in the polynomial encrypted in this form, which is not possible with other encryption forms (e.g., hashes).

With all this information, we are now ready to build our zk-SNARK.

Constructing a zk-SNARK with the KZG polynomial commitment scheme

Step 1 » Calculating the polynomial

• We begin by calculating the polynomial using the QAP procedure discussed in the previous article. The polynomial is represented as t(x) with degree d:

  \(-516x^4 + 1054x³ - 714x² + 194x - 18\)

Step 2 » Establishing the trusted setup

• A trusted party (or multiple parties in MPC) generates a secret, random value s used to encrypt the polynomial. This secret value s is produced in the prime group g as:

  \(g^s, g^{s^2}, g^{s^3}, \ldots, g^{s^n}\)

  Group g constrains the degree of the polynomial used in the commitment.

• The secret value s and group g form a Common Reference String (CRS) when evaluated with the polynomial’s coefficients, with each coefficient evaluation being a point on the elliptic curve. After generating the CRS, the value s must be deleted.

• With the trusted setup in place, we can commit to polynomial t at point s, as shown in the expression below:

  \(t(s) = g^{t(s)} = g^{-516s^4 + 1054s^3 - 714s^2 + 194s - 18}\)

• Step 3 » Proof generation (opening)

• To prove the commitment to the polynomial t(x), the prover must "open" the commitment at the point s (even though its value remains unknown). The prover evaluates the polynomial using the CRS's publicly available values, all hidden within the group g.

• Next, the verifier selects another point z and provides it to the prover. The prover calculates the polynomial:

  \(h(x) = \frac{p(s) - p(z)}{s - z}\)

  Now, let’s revisit our earlier example with the target (vanishing) polynomial. The prover has to find a polynomial that satisfies the condition p(s) - p(z) = 0, which naturally occurs when s = z. Consequently, the value s - z divides the polynomial p(s) - p(z) without remainder. The fact that there is no remainder will serve as proof of the evaluation of the polynomial at the point z.

  Although complex, this calculation lies at the heart of the KZG polynomial commitment scheme, making it essential to understand. Feel free to get back to the section about polynomial properties, if required.

• As x can take any value, the prover evaluates the proof h(x) at s instead of x. This results in equality:

  \(p(s) - p(z) = (s - z) * h(s)\)

  which serves as proof of the evaluation. The prover sends this proof to the verifier.

Step 4 » Evaluation

• The proof received by the verifier requires further transformation because s is unknown. To represent x as a point on an elliptic curve [x], we add x to itself g times, where g is a prime field group. The original polynomial evaluates to:

  \([p(s)] = g \times (-516s^4 + 1054s^3 - 714s^2 + 194s - 18)\)

• The relationship to be verified looks then as follows:

  \([h(s)] * [s - z] = [p(s)] - [p(z)]\)

• Each value has been transformed into a point on an elliptic curve:

  • [h(s)] represents the evaluation of h(x) using CRS values, added to itself g times, equivalent to a commitment to h(s).

  • [p(s)] represents the evaluation of the original polynomial p(x) at CRS values, added to itself g times.

  • [p(z)] represents the evaluation of the polynomial p(x) at the verifier-provided value z, added to itself g times.

  • [s - z] corresponds to the difference between s and z, evaluated at CRS values. However, we can't do much about it now since s is secret.

• Also, note that elliptic curve points can't be directly multiplied, so calculating the below part will require elliptic curve pairings:

  \([h(s)] * [s - z]\)

Step 5 » Verification

• To verify the proof, we work with two prime groups, G1 and G2, and their generators g and f, respectively.

• Let’s denote the addition of the secret point s in group G1 g times as [s]1, and the addition of s in group G2 f times as [s]2.

• The pairing of G1 and G2 is denoted as GT, a multiplicative target group.

• With [s - z] in group G2 and [p(z)] in group G1, the verifier checks the equality

  \(e(h(s), [s - z]^2) = e([p(s) - p(z)]^1, f)\)

• The above equation presented in the pairing group looks as follows:

  \([h(s) \cdot (s - z)]^T = [p(s) - p(z)]^T, \quad \text{where} \; [x]^T = e(g,f)^x\)

• This equation is equivalent to our familiar

  \(h(s) * (s - z) = p(s) - p(z)\)

  and the verifier can finally confirm if it holds! Let's take a breath and review each part once again:

  • [h(s)] is provided by the prover.

  • z is selected by the verifier.

  • [s - z]2 can be computed using [s]2 (calculated in group G2 during the trusted setup) and verifier-selected z. Calculating [s - z]2 is equivalent to [s]2 - [z]2.

  • [p(s)] is the commitment provided by the prover.

  • [p(z)]1 is calculated and provided by the prover at the verifier's request.

And there you have it! The verifier successfully confirmed whether the prover truly knows the polynomial they claimed to know. Quite the adventure, right?! To summarize the entire process:

1. In the trusted setup, a random value s is generated along with two sets of elliptic curve points [s]1 and [s]2. The value s is then discarded.

2. The prover commits to the polynomial p(x) using CRS elements from the trusted setup.

3. The verifier selects a point z and shares it with the prover, requesting the evaluation of z with p(x).

4. The prover evaluates p(z) and shares the proof with the verifier in the form of an elliptic curve point h(x).

5. The prover calculates the pairing equation and confirms if it holds.

Congratulations if you made it through! Don't hesitate to re-read any sections you didn't fully understand. It took me some time for all of this to click, so don't be discouraged if everything isn't clear even after a few reads.

In Part III of this article series, we will look into other types of commitments focusing on transparent proofs, an alternative method that doesn't require a trusted setup. Stay tuned as we explore their inner workings, advantages, and drawbacks.

I couldn’t write this piece without the following sources:

• Vitalik Buterin, Understanding PLONK

• Dankrad Feist, KZG Polynomial Commitments

• Ozgur Ozerk, KZG Polynomial Commitments (based on Dankrad’s article)

• Alexander Comerford, Understanding KZG Polynomial Commitments

• David Wong, How does PLONK work?

• Maksym Petkus, Why and How zk-SNARK Works: Definitive Explanation