Understanding Zero-Knowledge Proofs: Part 6-Quadratic Arithmetic Programs

In the previous article (part 5) in this series on zk-SNARKs, we looked at how computations that need verification can be first encoded in the form of arithmetic circuits, then in the R1CS (rank-1 constraint system) form. Next, we can represent an R1CS as a quadratic arithmetic program, which encodes the same constraints in the form of polynomial equations. This, in turn, will allow them to be connected to the cryptographic polynomial commitment schemes we discussed earlier in the series, to generate proofs of computation that a third party can verify.

Lagrange Polynomial Interpolation: Given a set of k+1 points { (x0, y0), (x1,y1)… (xk, yk)}, we know that it is possible to fit a polynomial of degree k through them. One way is to use the Lagrange interpolation formula to generate what is called the Lagrange Polynomial. It consists of first defining a set of k+1 basis polynomials that depend on the x-values as follows:

Basis polynomials for Lagrange Interpolation (From Wikipedia)

Then we represent the Lagrange polynomial as a linear combination of these basis polynomials weighted by the corresponding y-points:

The Lagrange Polynomial defined in terms of the basis polynomials and the y-values (from Wikipedia)

Note that the Lagrange polynomial is also well-defined for finite-fields, and is widely used in cryptography including for Shamir’s secret sharing.

Converting from R1CS to Lagrange Polynomials: Recall that we had three sets of vectors A, B, C for each constraint in R1CS. We first take all the A vectors and stack them as rows in a matrix A, with the i-th row corresponding to the i-th constraint, and the j-th column corresponding to the j-th element of the witness vector. Similarly, we construct the matrices B and C. These matrices are of size n x m, where n is the number of constraints, and m is the number of elements in the witness vector (i.e. 1 plus the number of intermediate and output variables).

If we take each of the m columns of A as a set of different y-values corresponding to the x-values of (1, 2, 3, …, n), where n is the number of constraints in R1CS, we have a set of n x-y points that we can then generate Lagrange polynomials out of. We will thus end up with m polynomials each for A, B, and C, let’s call them A1(x).. Am(x), B1(x)…Bm(x), C1(x)..Cm(x).

The Quadratic Arithmetic Program (QAP):

Now consider a witness vector s = [s1, s2, … sm].

Consider the single polynomial P(x) = (A(x).s)*(B(x).s)-(C(x).s) = sum_j(sj*Aj(x)) * sum_j(sj*Bj(x)) - sum_j sj*Cj(x), for j = 1, 2, … m.

Recall what we had required for the original R1CS system: that (A.s)*(B.s) -C.s = 0 for each constraint, given a correct witness s. Now, with the polynomial we have constructed, this is equivalent to verifying that for a correct computation (represented by a correct witness) P(x) should be zero at each of the x-values corresponding to each constraint, i.e. at x = (1, 2, 3, … c). Verifying this statement about the single polynomial P(x) is thus equivalent to verifying the given R1CS. This is known as a Quadratic Arithmetic Program.

The Quadratic Arithmetic Program can be expressed by the equivalent statement that P(x) has (x-i) as factors, for each i in (1,2,3…c). In other words, it can be expressed in the form

P(x) = H(x)Z(x), where Z(x) = (x-1)(x-2)…(x-c)

In particular, given a P(x) constructed from the R1CS given a witness s for the computation following the procedure described above, if we compute P(x)/Z(x), we should get a polynomial H(x), and no remainder.

Committing to this polynomial in a cryptographically secure manner, building on the ideas described in our earlier article on polynomial commitment schemes, along with various optimizations to minimize the proof size, results in a zero-knowledge proof of correct computation, that can be verified by a third-party. This forms the essence of how zk-SNARKs work.

Additional Notes on QAP:

Quadratic Arithmetic Programs were introduced in a paper by Gennaro et al. (2013) where they state that “Quadratic Arithmetic Programs (QAPs)… ‘naturally’ compute arithmetic circuits over large fields” and present “succinct NIZK constructions that use QAPs.” The following is the definition from the paper using their notation:

They prove that QAPs are efficient for such arbitrary computations via the following theorem.

from Gennaro et al. 2013.

Further Reading:

• Vitalik Buterin, Quadratic Arithmetic Programs: From Zero to Hero, 2016.
• Rareskills, Quadratic Arithmetic Programs, 2023.
• Gennaro, Rosario, Craig Gentry, Bryan Parno, and Mariana Raykova. “Quadratic span programs and succinct NIZKs without PCPs.” In Advances in Cryptology–EUROCRYPT 2013: 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26–30, 2013. Proceedings 32, pp. 626–645. Springer Berlin Heidelberg, 2013.