Explaining SNARKs Part V: From Computations to Polynomials

<< Part IV

In the three previous parts, we developed a certain machinery for dealing with polynomials. In this part, we show how to translate statements we would like to prove and verify to the language of polynomials. The idea of using polynomials in this way goes back to the groundbreaking work of Lund, Fortnow, Karloff and Nisan.

In 2013, another breakthrough work of Gennaro, Gentry, Parno and Raykova defined an extremely useful translation of computations into polynomials called a Quadratic Arithmetic Program (QAP). QAPs have become the basis for modern zk-SNARK constructions, in particular those used by Zcash.

In this post we explain the translation into QAPs by example. Even when focusing on a small example rather than the general definition, it is unavoidable that it is a lot to digest at first, so be prepared for a certain mental effort :).

Suppose Alice wants to prove to Bob she knows c1,c2,c3?pc1,c2,c3∈Fp such that (c1c2)(c1+c3)=7(c1⋅c2)⋅(c1+c3)=7. The first step is to present the expression computed from c1,c2,c3c1,c2,c3 as an arithmetic circuit.

ARITHMETIC CIRCUITS

An arithmetic circuit consists of gates computing arithmetic operations like addition and multiplication, with wires connecting the gates. In our case, the circuit looks like this:

The bottom wires are the input wires, and the top wire is the output wire giving the result of the circuit computation on the inputs.

As can be seen in the picture, we label the wires and gates of the circuit in a very particular way, that is needed for the next step of translating the circuit into a QAP:

  • When the same outgoing wire goes into more than one gate, we still think of it as one wire – like ??w1 in the example.
  • We assume multiplication gates have exactly two input wires, which we call the left wire and right wire.
  • We don’t label the wires going from an addition to multiplication gate, nor the addition gate; we think of the inputs of the addition gate as going directly into the multiplication gate. So in the example we think of ??w1and ??w3 as both being right inputs of ??g2.

A legal assignment for the circuit, is an assignment of values to the labeled wires where the output value of each multiplication gate is indeed the product of the corresponding inputs.

So for our circuit, a legal assignment is of the form: (c1,,c5)(c1,…,c5) where c4=c1c2c4=c1⋅c2 and c5=c4(c1+c3)c5=c4⋅(c1+c3).

In this terminology, what Alice wants to prove is that she knows a legal assignment (c1,,c5)(c1,…,c5) such that c5=7c5=7. The next step is to translate this statement into one about polynomials using QAPs.

REDUCTION TO A QAP

We associate each multiplication gate with a field element: ??g1 will be associated with 1?p1∈Fp and ??g2 with 2?p2∈Fp. We call the points {1,2}{1,2} our target points. Now we need to define a set of “left wire polynomials” L1,,L5L1,…,L5, “right wire polynomials” R1,,R5R1,…,R5 and “output wire polynomials” O1,,O5O1,…,O5.

The idea for the definition is that the polynomials will usually be zero on the target points, except the ones involved in the target point’s corresponding multiplication gate.

Concretely, as ??,??,??w1,w2,w4 are, respectively, the left, right and output wire of ??g1; we define L1=R2=O4=2XL1=R2=O4=2−X, as the polynomial 2X2−X is one on the point 11 corresponding to ??g1 and zero on the point 22 corresponding to ??g2.

Note that ??w1 and ??w3 are both right inputs of ??g2. Therefore, we define similarly L4=R1=R3=O5=X1L4=R1=R3=O5=X−1– as X1X−1 is one on the target point 22 corresponding to ??g2 and zero on the other target point.

We set the rest of the polynomials to be the zero polynomial.

Given fixed values (c1,,c5)(c1,…,c5) we use them as coefficients to define a left, right, and output “sum” polynomials. That is, we define

L:=5i=1ciLi,R:=5i=1ciRi,O:=5i=1ciOiL:=∑i=15ci⋅Li,R:=∑i=15ci⋅Ri,O:=∑i=15ci⋅Oi,

and then we define the polynomial P:=LROP:=L⋅R−O.

Now, after all these definitions, the central point is this: (c1,,c5)(c1,…,c5) is a legal assignment to the circuit if and only if PP vanishes on all the target points.

Let’s examine this using our example. Suppose we defined L,R,O,PL,R,O,P as above given some c1,,c5c1,…,c5. Let’s evaluate all these polynomials at the target point 11:

Out of all the LiLi‘s only L1L1 is non-zero on 11. So we have L(1)=c1L1(1)=c1L(1)=c1⋅L1(1)=c1. Similarly, we get R(1)=c2R(1)=c2and O(1)=c4O(1)=c4.

Therefore, P(1)=c1c2c4P(1)=c1⋅c2−c4. A similar calculation shows P(2)=c4(c1+c3)c5P(2)=c4⋅(c1+c3)−c5.

In other words, PP vanishes on the target points if and only if (c1,,c5)(c1,…,c5) is a legal assignment.

Now, we use the following algebraic fact: For a polynomial PP and a point a?pa∈Fp, we have P(a)=0P(a)=0 if and only if the polynomial XaX−a divides PP, i.e. P=(Xa)HP=(X−a)⋅H for some polynomial HH.

Defining the target polynomial T(X):=(X1)(X2)T(X):=(X−1)⋅(X−2), we thus have that TT divides PP if and only if (c1,,c5)(c1,…,c5) is a legal assignment.

Following the above discussion, we define a QAP as follows:

A Quadratic Arithmetic Program QQ of degree dd and size mm consists of polynomials L1,,LmL1,…,Lm, R1,,RmR1,…,Rm, O1,,OmO1,…,Om and a target polynomial TT of degree dd.

An assignment (c1,,cm)(c1,…,cm) satisfies QQ if, defining L:=mi=1ciLi,R:=mi=1ciRi,O:=mi=1ciOiL:=∑i=1mci⋅Li,R:=∑i=1mci⋅Ri,O:=∑i=1mci⋅Oiand P:=LROP:=L⋅R−O, we have that TT divides PP.

In this terminology, Alice wants to prove she knows an assignment (c1,,c5)(c1,…,c5) satisfying the QAP described above with c5=7c5=7.

To summarize, we have seen how a statement such as “I know c1,c2,c3c1,c2,c3 such that (c1c2)(c1+c3)=7(c1⋅c2)⋅(c1+c3)=7” can be translated into an equivalent statement about polynomials using QAPs. In the next part, we will see an efficient protocol for proving knowledge of a satisfying assignment to a QAP.

[1] In this post we tried to give the most concise example of a reduction to QAP; we also recommend Vitalik Buterin’s excellent post for more details on the transformation from a program to a QAP.

Comments 1

发表评论

电子邮件地址不会被公开。 必填项已用*标注