<< 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 such that . The first step is to present the expression computed from as an arithmetic circuit.
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 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 and as both being right inputs of .
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: where and .
In this terminology, what Alice wants to prove is that she knows a legal assignment such that . 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: will be associated with and with . We call the points our target points. Now we need to define a set of “left wire polynomials” , “right wire polynomials” and “output wire polynomials” .
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 are, respectively, the left, right and output wire of ; we define , as the polynomial is one on the point corresponding to and zero on the point corresponding to .
Note that and are both right inputs of . Therefore, we define similarly – as is one on the target point corresponding to and zero on the other target point.
We set the rest of the polynomials to be the zero polynomial.
Given fixed values we use them as coefficients to define a left, right, and output “sum” polynomials. That is, we define
and then we define the polynomial .
Now, after all these definitions, the central point is this: is a legal assignment to the circuit if and only if vanishes on all the target points.
Let’s examine this using our example. Suppose we defined as above given some . Let’s evaluate all these polynomials at the target point :
Out of all the ‘s only is non-zero on . So we have . Similarly, we get and .
Therefore, . A similar calculation shows .
In other words, vanishes on the target points if and only if is a legal assignment.
Now, we use the following algebraic fact: For a polynomial and a point , we have if and only if the polynomial divides , i.e. for some polynomial .
Defining the target polynomial , we thus have that divides if and only if is a legal assignment.
Following the above discussion, we define a QAP as follows:
A Quadratic Arithmetic Program of degree and size consists of polynomials , , and a target polynomial of degree .
An assignment satisfies if, defining and , we have that divides .
In this terminology, Alice wants to prove she knows an assignment satisfying the QAP described above with .
To summarize, we have seen how a statement such as “I know such that ” 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.
|||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.|