How to Build a Quadratic Arithmetic Program

In a previous post I explained how one can express a provable function for a ZK-SNARK in a Rank-1 Constraint System. These constrains have to be transformed into a Quadratic Arithmetic Program before being usable to produce the Zero-Knowledge Proof. This post is the second post in a mini-series about Quadratic Arithmetic Programs, and explains how to create them. 

This transition has been explained by Vitalik Buterin in his “from hero to zero” post on quadratic arithmetic programs, but I find he covers too much ground in a single post and leaves some things unsaid. This series aims at removing the unnecessary complexity and clarifying the relation between the constraints and polynomials, and the degrees and sizes of the QAP and R1CS.

Rank 1 Constraint Systems

A Rank 1 Constraint System (R1CS) is a set of constraints that can be specified by 3 linear combinations, commonly called A,B,C. Given an assignment describing the full state of a computation, which lists the value of every variable used in the execution, the R1CS can be used to check that all the steps were correctly computed, until one last step(s) confirm(s) the output is as expected.

The naive way to do this is to take the assignment s and in turn each constraint (A,B,C), and check that <A.s> * <B.s> - <C.s> = 0

This will be very inefficient for real systems, which can have thousands of constraints. Instead, we use a notion called Quadratic Arithmetic Programs, which I describe in this post.

Definition of Quadratic Arithmetic Programs

A Quadratic Arithmetic Program (QAP) is derived from an R1CS. A QAP has two main parameters (I follow the definitions in BCTV14):

• m: the size of the QAP
• d: the degree of the QAP

The QAP itself is made up of 3 polynomial vectors, PA, PB, PC, corresponding to the linear combinations of the same name in the R1CS; plus one polynomial Z. (A note on notation: I use bold and italic to denote vectors, but normal font for a single vector element.) The degree of Z is exactly d, and the degree of the polynomials in each vector is at most d-1. Each vector contains exactly m+1 polynomials.

These are directly related to the original circuit and its R1CS.

• Each linear combination in the R1CS has exactly m+1 entries (I often use coefficients to mean the same thing).
• The state assignment has exactly m + 1 entries, for m variables plus the constant 1.
• The R1CS has:
  • one constraint per gate;
  • one constraint per circuit output.
• The QAP adds
  • n+1 constraints to enforce a non-degeneracy condition on the constant 1 and each of the public inputs, which require the resulting polynomials to be linearly independent: 1 * 0 = 0 and ik * 0 = 0.

My current understanding regarding the non-degeneracy constraints is that they remove reduce inputs. If an input can be computed from a linear combination of others, then the corresponding polynomials would be linearly dependent. There may be other reasons, though, that I don’t understand yet.

How to Construct the Quadratic Arithmetic Program

Once we have the full set of constraints, we can create the QAP. Our goal is to devise a set of polynomials that simultaneously encode all of the constraints, so that we can verify the satisfiability thereof with a single check on the polynomials instead of a check over each constraint. The clever trick is to build the polynomials in a way that they can generate all of the constraints.

We make one polynomial for each entry of a linear combination. That is, polynomial PA0 will generate the first entry of all A linear combinations. Polynomial PA1 will generate the second such entry and so on. Since each linear combination has m+1 entries, in total we will have m+1 polynomials each for A, B and C, and these are grouped in vectors PA,PB,PC.

Now, in order to generate these coefficients, we first assign an arbitrary number (which does not have to be random) to each constraint, say r1 to rd (which should all be different). Now, we fix the polynomials such that their evaluation at a point is the value of the corresponding coefficient of the constraint for that point.

For example, take polynomial PB3. This generates the fourth coefficient of all B linear combinations. Then, evaluating PB3 at the point for the first constraint, r1, gives that coefficient for the B linear combination of the first constraint, and so on:

• PB3(r1) = B1[3]
• PB3(r2) = B2[3].

Polynomial Interpolation

This may seem like magic, but it is a well-known algebraic procedure. If you fix two points on a plane, you can define a single straight line that goes through it. If you fix 3 points, you can define a single 2nd-degree curve that goes through them, and so on. If you fix any n points, you define a single n-1 degree polynomial that will go through all of them. This is called interpolation, and can be done with an algorithm called Lagrangian interpolation. That is out of the scope of this post.

The important thing to retain is that since we have d constraints we can compute a polynomial of degree at most d-1 for each entry in the linear combination. And this defines the main part of the QAP: the PA, PB, PC polynomial vectors.

The Z polynomial

The last remaining part of the QAP is the Z polynomial. It is technically called the vanishing polynomial of a domain S, but I prefer to call it the Zeroes polynomial. That is because it matches well with the Z initial, but also because it gives you an intuition to what it is:

Z is defined as the polynomial that is 0 exactly at the points we chose above, r1 to rd.

And the definition is very simple:

Z(z) = (z - r1) (z - r2) ... (z - rd)

Thus, Z(z) has degree exactly d. But, why do we need Z in the first place? That is another clever trick. We moved from a situation where we had d groups of 3 * d vectors of m + 1 coefficients (the R1CS) to one where we have 3 vectors each with m+1 polynomials of d-1 degree. Recall constraint j is validated if its linear combinations satisfy this for a particular assignment s to the circuit’s wires:

<Aj . s> * <Bj . s> - <Cj . s> = 0

but it is very inefficient to verify all constraints.

A Polynomial to Encode Them All 

Using the definition of the polynomials above, the same can be written like this:

<PA(rj) . s> * <PB(rj) . s> - <PC(rj) . s> = 0

In the above, I have replaced the actual R1CS constraint by evaluating the polynomial vectors at the point rj. I could do this for every other point. In fact, I can go further.

If I do not fix any point to evaluate and instead just write the polynomial in general form,  what I have is just a series of multiplications and additions of polynomials, which itself is another polynomial:

P(z) = <PA(z) . s> * <PB(z) . s> - <PC(z) . s>

By construction, we know the QAP is only satisfied if P(z) is zero at each of the points z = r1 to z = rd (although it could be 0 also at other points, these at least are required). We could go out and evaluate the polynomial at every such point and test if, but that would leave us no better off than naively checking all constraints directly.

Now, it is a property of Algebra that a polynomial is equal to the product of linear terms of its roots and a scalar. What this means in current English is that if a polynomial has zeroes at points r1, r2, ..., rd, then it can be written as

P(z) = (z - r1) (z - r2) ... (z - rd) H(z),

where H(z) is some other polynomial that represents the other places at which P is 0. Now, notice the similarity with our chosen Z(z) polynomial:

every polynomial P that is 0 at least for the points associated with all the constraints will be necessarily a multiple of Z(z), and can be written as

P(z) = Z(z) * H(z)

And now, in order to prove P(z) is zero at least at all our required points, we only need to divide it by Z(z), which can be done efficiently, and show that the division leaves no remainder.

Summing up

There’s really quite a bit of interesting algebra manipulation going around here. We converted a set of vectors into polynomials that generate them when evaluated at certain fixed points. We used these fixed points to generate a vanishing polynomial that divides any polynomial that evaluates to 0 at least on all those points. We created a new polynomial that summarizes all constraints and a particular assignment, and the consequence is that we can verify all constraints at once if we can divide that polynomial by the vanishing one without remainder. This division is complicated, but there are methods (the Fast Fourier Transform) that can perform if efficiently.

And that is how we can use Quadratic Arithmetic Programs to verify a full circuit computation!

How all of this is used in ZK SNARKs is a matter for another time, but I hope it has at least clarified a step that I find difficult and very confusing, in all of this process. As always, if you like what I write, let me know and please hit the ‘Like’ button below. Also, share in your network if you think others could be interested in reading it. You can even follow me on twitter for regular announcements of other posts (or just subscribe to mail notifications).

Do let me know if this is of help to you, or if you have suggestions of other topics for me to write about.

I hope to “see” you around next time. Meanwhile, have fun.