Understanding Zero-Knowledge Proofs: Part 4— Polynomial Commitments
In part 2 of this series, we went over some basic mathematical background needed for cryptography, namely finite fields, cyclic groups, and elliptic curves, and in part 3, we discussed elliptic curve cryptography (ECC) and the concept of bilinear pairings. In this part, we will finally start to get into the nitty-gritty of how Zero-knowledge proofs, specifically, Zero-knowledge succinct non-interactive argument of knowledge (zk-SNARKs), work by learning about polynomial commitment.
To write this article, I am borrowing from many sources including the article “Why and how zk-SNARK works” by Maksym Petkus, Polynomial commitments by Ben Bencik, and this article on the KZG commitment scheme. Another useful reference on the subject is Dankrad Feist’s article on KZG polynomial commitments.
Verifying Knowledge of Polynomials
Why Polynomials: First, consider polynomial functions of real-valued numbers. One property of polynomials is that two polynomials of degree d can intersect in at most d points. (This is because if you equate them, you get a polynomial equation of at most degree d, which can yield at most d distinct real roots.) This implies that if you evaluate a polynomial at an arbitrary point, it is highly unlikely that another polynomial could have the same value at that point. Thus it is possible to evaluate someone’s claim that they know a certain polynomial with high probability by testing it at an arbitrary point.
The above result generalizes also to finite fields, via the Schwartz-Zippel Lemma. The lemma states the following: Let P() be a non-zero polynomial in n variables of degree d over a field F. Let S be a finite subset of F. If you choose the n arguments (r_1, r_2, … r_n) for the polynomial uniformly and independently at random from a finite subset S of F, then the probability that P(r_1, r_2, … r_n) = 0 is at most d/|S|. This can be used to show that the probability of two different polynomials agreeing on a randomly chosen point can be made arbitrary low (by choosing a sufficiently large set S). This reduces proving knowledge of a polynomial to proving knowledge of the polynomial at one point, enabling succinctness — one of the key properties of a zk-SNARK.
Proving knowledge of a Polynomial: Say we have a polynomial f(x) of degree d that has the property that f(a) = b. We want the prover to generate a proof that it knows f(x) and has calculated that f(a) = b. It is equivalent to ask the prover to show that there exists some quotient polynomial w(x) that can be expressed as the ratio: w(x) = (f(x)-b)/(x-a).
(Why? Because it implies f(x)-b = w(x)(x-a). This is saying precisely that when x=a, f(x)-b = 0 => f(a)=b.)
Based on what we said above, with high probability it would suffice for the prover to show for a given point s that w(s) = (f(s)-b)/(s-a).
Now there is one subtlety to account for. In providing and determining w(s), the prover should not be allowed to know what s is, and the commitment to f(s) should be made in advance. Else, they could simply cook up some arbitrary f’(s) != f(s) and return any arbitrary w’(s) that satisfies the (incorrect) equation w’(s) = (f’(s) — b)/(s-a).
Instead, we want to give the prover access to an encrypted version of s and an encrypted version of f(s), and have it generate a proof based on that, that in turn can be checked by the verifier. This is what is done in the scheme described below, known as the KZG polynomial commitment scheme due to its first appearance in a paper by Aniket Kate, Gregory Zaverucha, and Ian Goldberg in 2010.
KZG Polynomial Commitment Scheme
Trusted Setup: pick a random element s. Consider elliptic curves with generators g and h. Calculate and publish a standard reference string (SRS) consisting of [g, s⋅g, s²⋅g, … s^d⋅g, h, s⋅h]. The point s is then discarded as “toxic waste” (recall that the prover should not be allowed to see it).
Commitment: The prover must commit to the encrypted version of the polynomial f(x) = sum_i (p_i * x^i) at the point s. This is done as E(f(s)) = sum_i (p_i ⋅(s^i⋅g)). Note that the prover has access to s^i⋅g (for all i) from the SRS and can therefore calculate this polynomial commitment.
Function Evaluation and Proof Generation: When asked to produce the output for an input a, first the output f(a) = b is computed. Then, given its knowledge of f(x), a, b, the prover is able to compute the quotient polynomial function w(x) = (f(x)-b)/(x-a)). Say that this function is of the form w(x) = sum_i (w_i * x^i). The prover can calculate the encrypted evaluation of this function at the point s as follows: E(w(s)) = sum_i (w_i⋅(s^i⋅g)), we will consider this quantity the proof. The prover then sends the evaluation f(a) = b, the polynomial commitment E(f(s)), and the proof E(w(s)) to the verifier.
Verification: The verifier has access to the following elements: the evaluation of f(a)=b, E(f(s)), and E(w(s)). From these elements alone, it aims to verify the calculation w(s) = (f(s)-b)/(s-a), or equivalently, w(s)*(s-a) = f(s)-b. Note that this equation holding would imply that the prover knows f(x) and has done the correct evaluation f(a) = b.
The difficulty is that the verifier also does not know s or f(s) or w(s), only the encrypted versions of the latter two polynomial evaluations. Hence this verification is done by using a suitable bilinear pairing. Specifically, it can be converted to checking the equality of the following two bilinear pairings( recall from part 3 that with a bilinear pairing involving groups with generators P and Q respectively, we get that e(a⋅P,b⋅Q) = e(P,Q)^(ab) ):
e((f(s)-b)⋅g, h) = e(g,h)^(f(s)-b) ... (1)
e(w(s)⋅g, (s-a)⋅h) = e(g,h)^(w(s)(s-a)) … (2)
First, note that the verifier is able to calculate both (1) and (2) as follows. For (1), the first term (f(s)-b)⋅g can be rewritten as f(s)⋅g — b⋅g, and the verifier has already obtained E(f(s)) = f(s)⋅g which was the encrypted polynomial commitment, as well as the value b from the prover. And it knows h from the SRS. For (2), it knows E(w(s))=w(s)⋅g as this was the proof provided by the prover, and it can calculate (s-a)⋅h = s⋅h -a⋅h as it has s⋅h from the SRS and a from the prover.
So if the two calculations are equal, we will have that e(g,h)^(f(s)-b) = e(g,h)^(w(s)(s-a)), which implies that indeed f(s)-b = w(s)(s-a), which is what the verifier needs to check. If they are not equal then the prover either does not know the polynomial f() or has not performed the correct computation f(a)=b. If they are, then the verifier may rest assured that the prover has indeed done the correct computation with the function.
Succinctness with KZG: Note that both the polynomial commitment E(f(s)) and the proof E(w(s)) are just one element of the group (elliptic curve) with generator g. Thus the commitment and proof size remain constant regardless of the degree of the polynomial.
Application of KZG to zk-SNARKs: In this article we focused on the problem of how a prover can prove correct execution of a single evaluation of a single polynomial function. Proving correct execution of a general program requires quite a bit more than this. We should mention that the scheme can be easily extended to handle multiple polynomials in a batch. Variants of the KZG polynomial commitment scheme described in this article form part of several general zk-SNARK schemes including Sonic, Marlin, and PLONK.
Next Articles: Next, we will see how a general computation can be represented in the form of an arithmetic circuit, then converted to representations such as rank-one constrained systems (R1CS) and further to quadratic arithmetic programs (QAPs) so that they can ultimately be represented in terms of polynomials whose evaluations need to be verified at particular points.