Under the hood of zkSNARKs — PLONK protocol: Part 1
PLONK is one of the zero-knowledge proving systems that belong to the SNARK group. Compared to Groth16, which is an older system, PLONK offers advantages such as a universal and updatable trusted setup. In Groth16, a circuit-specific (or task-specific, for those unfamiliar with the term) trusted setup is required, whereas in Plonk, the same setup can be reused for any circuit. The term ‘updatable’ refers to the ability for anyone to add randomness to the setup, reinforcing trust in its integrity.
However, a downside of PLONK is that it results in larger proof sizes, which can impact gas costs on the Ethereum network. This is a potential reason why Groth16 may still be considered competitive.
The PLONK protocol encapsulates a variety of different techniques, some of which must be understood before delving into the protocol itself. Let’s start with the basics.
Polynomials
Polynomials are one of the foundational elements of zero-knowledge proving systems. Many of us learned about them in school, but their application in this context might not be immediately obvious. Why are they used?
A polynomial provides a form that allows us to encapsulate the states of a particular process within a single function. This is a simplified way I understand its role. So, when we want to prove something, such as the correctness of a program’s execution or the verification of a statement, we can represent these processes using polynomials. This remarkable characteristic enables us to construct sophisticated proving systems.
KZG/Kate Polynomial Commitment Schema
In a nutshell, Plonk utilizes the KZG (Kate, Zaverucha, Goldberg) scheme for verification. Let’s consider a toy example to understand how commitment schemes work.
Setup Phase:
- Alice has something she wants to commit to, like her decision on where to go for dinner. Let’s say she has chosen “Italian.”
- She writes her choice on a piece of paper.
Commit Phase:
- Alice places the paper inside a box.
- She locks the box with a padlock and keeps the key.
- She gives the locked box to Bob, ensuring him that her dinner choice is inside.
- At this point, Bob has the box with the commitment inside, but he cannot access it because it is locked.
Reveal Phase:
- When it’s time to reveal her dinner choice, Alice gives Bob the key.
- Bob unlocks the box, takes out the paper, and reads Alice’s dinner choice: “Italian.”
- Bob now knows Alice’s commitment, and he is assured that Alice did not change her mind after giving him the locked box because the box was securely locked the entire time.
In the KZG commitment scheme, the prover commits to a polynomial (e.g., representing the correctness of a program execution).
Assume a prover has a polynomial P(x) of degree n to which he needs to commit. To do this, he would require a trusted setup. For additional information about trusted setups, please refer to the following source:
The trusted setup in this context refers to the generation of powers of a random secret value, τ (tau), up to the n-th degree. These powers are then ‘coated’ or represented as points on an elliptic curve. If you are not familiar with elliptic curve points, you can think of them as the product of the secret value τ and a base point on the curve, which obscures the actual value of τ. This process prevents anyone from deducing the original secret value, which is critical for the security of the system.
Commitment to our polynomial would look like this:
The prover calculates a commitment to the polynomial P(τ) using the Common Reference String obtained from the trusted setup, and sends this commitment, which is a point on an elliptic curve, to the verifier.
This is because a scalar multiple of the curve’s base point [G] (such as cτ) results in another point on the curve. The verifier receives the commitment to P(τ), but to maintain the zero-knowledge property, the actual polynomial P(x) is not revealed.
Instead, the verifier sends a random value r to the prover, who then evaluates P(x) at that point and proceeds with the protocol.
The prover sends the evaluated value P(r) back to the verifier. The verifier now has the commitment P(τ), the evaluated P(r), and knowledge of the Polynomial Remainder Theorem (often confused with Bézout’s Theorem in this context), which states:
If you subtract P(r) from P(x) and then divide by x−r, the division should have no remainder, giving you the quotient polynomial Q(x). Along with P(r), the prover also sends the commitment to Q(τ) to the verifier. Now the verifier has P(τ), Q(τ), r, and P(r). Since division as such is not defined on elliptic curves, the commitments P and Q (which are points on the elliptic curve) undergo a series of transformations to enable the verifier to confirm the validity of the equation.
The verifier does not know τ, but he have the commitments [Q(τ)] and [P(τ)] from the prover. When we multiply both sides of the equation by the generator point [G], the scenario becomes more tractable.
The verifier is aware of [Q(τ)] and [P(τ)] — the commitments corresponding to Q(τ) and P(τ) multiplied by [G]. The verifier can also compute P(r)[G] since P(r) is known. To resolve (τ−r)[G], elliptic curve pairing techniques are employed.
The function e represents a bilinear pairing, which takes a point from each of two separate elliptic curve groups and ‘pairs’ them to produce an element in a third target group. The bilinear property of this pairing function is that e(k⋅G1,G2)=e(G1,k⋅G2), where k is a scalar and G1,G2 are points from the two respective groups. This property means that multiplying a point in one group by k before applying the pairing function is equivalent to applying the pairing function first and then multiplying its result by k in the target group.
In the context of bilinear pairings:
- We establish that all previously evaluated elements are associated with a point on curve G1.
- When we refer to ‘multiplication’ in the pairing process, for the term (τ−r)Q(τ) to interact with the pairing function e, we first map (τ−r) onto curve G1 by multiplying it with G1’s generator point, and similarly, map Q(τ) onto curve G2.
- The commutative property of the pairing function allows us to flip the scalar (τ−r) with the commitment Q(τ), without affecting the result.
- Then, we apply the distributive property to ‘open the brackets,’ which means to distribute the multiplication across the terms within the pairing operation.
So now we can state that the verifier is aware of the commitments [Q(τ)]1, [P(τ)]1, and [P(r)]1, and can also compute r[G2] because r is known. As for τ[G2] — this value (point) should come from the trusted setup, which is a part of the common reference string (CRS).
With these elements, the verifier is in a position to check if the final equation, which embodies the proof of knowledge, holds true.
Bathed Polynomial Commitment Schema
In PLONK, the prover is required to commit to not just one polynomial but to multiple polynomials. Although the prover and verifier could theoretically handle all the commitments one by one using the schema mentioned above, the creators of PLONK have designed an altered schema that allows committing to multiple polynomials within a single step. This is possible using method called Linear Independence.
Suppose we have three polynomials, P1(x), P2(x), and P3(x), and our goal is to demonstrate that each polynomial evaluates to zero at a some value r. To efficiently prove this within a single step, we can construct a new polynomial that encapsulates P1(x), P2(x), and P3(x).
New polynomial F(x) is a combination of P1(x), P2(x), and P3(x). If we choose a value r such that when evaluated, P1(r), P2(r), and P3(r) yield the results 2, 3, and -5, respectively, we encounter an issue. The sum of these evaluations is zero, which might incorrectly suggest that each individual polynomial evaluates to zero at r when, in fact, none of them do. This is a potential problem because our aim is to prove that each polynomial individually equals zero at r, not just their sum.
To guarantee that each polynomial P1(x), P2(x), and P3(x) individually equals zero at a specific point r, we choose a non-zero constant v (for example, v=2) and use it to scale the polynomials by increasing powers. We then define a new polynomial F(x) as F(x)=v⁰P1(x)+v¹P2(x)+v²P3(x). When F(r) is evaluated and the result is zero, it implies that P1(r), P2(r), and P3(r) must all be zero, because v is non-zero and the polynomials are scaled by distinct powers of v, making them linearly independent. This clever approach allows us to confirm the individual zeros of P1, P2, and P3 within a single combined equation.
In next article, we will discuss several other aspects that deserve attention before we commence our detailed work on the protocol.
