Reduction to a QAP

We associate each multiplication gate with a field element: g 1 will be associated with 1 ∈ F p and g 2 with 2 ∈ F p . We call the points { 1 , 2 } our target points. Now we need to define a set of “left wire polynomials” L 1 , … , L 5 , “right wire polynomials” R 1 , … , R 5 and “output wire polynomials” O 1 , … , O 5 .

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 w 1 , w 2 , w 4 are, respectively, the left, right and output wire of g 1 ; we define L 1 = R 2 = O 4 = 2 − X , as the polynomial 2 − X is one on the point 1 corresponding to g 1 and zero on the point 2 corresponding to g 2 .

Note that w 1 and w 3 are both right inputs of g 2 . Therefore, we define similarly L 4 = R 1 = R 3 = O 5 = X − 1 – as X − 1 is one on the target point 2 corresponding to g 2 and zero on the other target point.

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

Given fixed values ( c 1 , … , c 5 ) we use them as coefficients to define a left, right, and output “sum” polynomials.

That is, we define

L := ∑ 5 i = 1 c i ⋅ L i , R := ∑ 5 i = 1 c i ⋅ R i , O := ∑ 5 i = 1 c i ⋅ O i , and then we define the polynomial P := L ⋅ R − O . Now, after all these definitions, the central point is this: ( c 1 , … , c 5 ) is a legal assignment to the circuit if and only if P vanishes on all the target points. Let’s examine this using our example. Suppose we defined L , R , O , P as above given some c 1 , … , c 5 . Let’s evaluate all these polynomials at the target point 1 : Out of all the L i ’s only L 1 is non-zero on 1 .

So we have L ( 1 ) = c 1 ⋅ L 1 ( 1 ) = c 1 . Similarly, we get R ( 1 ) = c 2 and O ( 1 ) = c 4. Therefore, P ( 1 ) = c 1 ⋅ c 2 − c 4 . A similar calculation shows P ( 2 ) = c 4 ⋅ ( c 1 + c 3 ) – c 5 .

In other words, P vanishes on the target points if and only if ( c 1 , … , c 5 ) is a legal assignment.

Now, we use the following algebraic fact: For a polynomial P and a point a ∈ F p , we have P ( a ) = 0 if and only if the polynomial X − a divides P , i.e. P = ( X − a ) ⋅ H for some polynomial H . Defining the target polynomial T ( X ) := ( X − 1 ) ⋅ ( X − 2 ) , we thus have that T divides P if and only if ( c 1 , … , c 5 ) is a legal assignment.

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

A Quadratic Arithmetic Program Q of degree d and size m consists of polynomials L 1 , … , L m , R 1 , … , R m , O 1 , … , O m and a target polynomial T of degree d .

An assignment ( c 1 , … , c m ) satisfies Q if, defining L := ∑ m i = 1 c i ⋅ L i , R := ∑ m i = 1 c i ⋅ R i , O := ∑ m i = 1 c i ⋅ O i and P := L ⋅ R − O , we have that T divides P . In this terminology, Jennifer wants to prove she knows an assignment ( c 1 , … , c 5 ) satisfying the QAP described above with c 5 = 7 .

We have seen how a statement such as “I know c 1 , c 2 , c 3 such that ( c 1 ⋅ c 2 ) ⋅ ( c 1 + c 3 ) = 7 ” can be translated into an equivalent statement about polynomials using QAPs.

The Pinocchio Protocol

A Quadratic Arithmetic Program Q of degree d and size m consists of polynomials L 1 , … , L m , R 1 , … , R m , O 1 , … , O m and a target polynomial T of degree d .

An assignment ( c 1 , … , c m ) satisfies Q if, defining L := ∑ m i = 1 c i ⋅ L i , R := ∑ m i = 1 c i ⋅ R i , O := ∑ m i = 1 c i ⋅ O i and P := L ⋅ R − O , we have that T divides P .

Jennifer will typically want to prove she has a satisfying assignment possessing some additional constraints, e.g. c m = 7 ; but we ignore this here for simplicity, and show how to just prove knowledge of some satisfying assignment.

If Jennifer has a satisfying assignment it means that, defining L , R , O , P as above, there exists a polynomial H such that P = H ⋅ T . In particular, for any s ∈ F p we have P ( s ) = H ( s ) ⋅ T ( s ) . Suppose now that Jennifer doesn’t have a satisfying assignment, but she still constructs L , R , O , P as above from some unsatisfying assignment ( c 1 , … , c m ) . Then we are guaranteed that T does not divide P . This means that for any polynomial H of degree at most d − 2 , P and L , R , O , H will be different polynomials. Note that P here is of degree at most 2 ( d − 1 ) , L , R , O here are of degree at most d − 1 and H here is degree at most d − 2 .

Now we can use the famous Schwartz-Zippel Lemma that tells us that two different polynomials of degree at most 2 d can agree on at most 2 d points s ∈ F p . Thus, if p is much larger than 2 d the probability that P ( s ) = H ( s ) ⋅ T ( s ) for a randomly chosen s ∈ F p is very small.

This suggests the following protocol sketch to test whether Jennifer has a satisfying assignment. Jennifer chooses polynomials L , R , O , H of degree at most d . Ted chooses a random point s ∈ F p , and computes E ( T ( s ) ) .

Jennifer sends Ted the hidings of all these polynomials evaluated at s , i.e. E ( L ( s ) ) , E ( R ( s ) ) , E ( O ( s ) ) , E ( H ( s ) ) .

Ted checks if the desired equation holds at s. That is, he checks whether E ( L ( s ) ⋅ R ( s ) − O ( s ) ) = E ( T ( s ) ⋅ H ( s ) ) .

Again, the point is that if Jennifer does not have a satisfying assignment, she will end up using polynomials where the equation does not hold identically, and thus does not hold at most choices of s . Therefore, Ted will reject with high probability over his choice of s in such a case.

The question is whether we have the tools to implement this sketch. The most crucial point is that Jennifer must choose the polynomials she will use, without knowing s .But this is exactly the problem we solved in the verifiable blind evaluation protocol.

Given that we have that, there are four main points that need to be addressed to turn this sketch into a zk-SNARK.

Making sure Jennifer chooses her polynomials according to an assignment

Here is an important point: If Jennifer doesn’t have a satisfying assignment, it doesn’t mean she can’t find any polynomials L , R , O , H of degree at most d with L ⋅ R − O = T ⋅ H , it just means she can’t find such polynomials where L , R and O were “produced from an assignment”; namely, that L := ∑ m i = 1 c i ⋅ L i , R := ∑ m i = 1 c i ⋅ R i , O := ∑ m i = 1 c i ⋅ O i for the same ( c 1 , … , c m ) .

The protocol just guarantees she is using some polynomials L , R , O of the right degree, but not that they were produced from an assignment. This is a point where the formal proof gets a little subtle; here we sketch the solution imprecisely.

Let’s combine the polynomials L , R , O into one polynomial F as follows: F = L + X d + 1 ⋅ R + X 2 ( d + 1 ) ⋅ O The point of multiplying R by X d + 1 and O by X 2 ( d + 1 ) is that the coefficients of L , R , O “do not mix” in F : The coefficients of 1 , X , … , X d in F are precisely the coefficients of L , the next d + 1 coefficients of X d + 1 , … , X 2 d + 1 are precisely the coefficients of R , and the last d + 1 coefficients are those of O .

Let’s combine the polynomials in the QAP definition in a similar way, defining for each i ∈ { 1 , … , m } a polynomial F i whose first d + 1 coefficients are the coefficients of L i , followed be the coefficients of R i and then O i . That is, for each i ∈ { 1 , … , m } we define the polynomial F i = L i + X d + 1 ⋅ R i + X 2 ( d + 1 ) ⋅ O i Note that when we sum two of the F i ’s the L i , R i , and O i “sum separately”.

For example, F 1 + F 2 = ( L 1 + L 2 ) + X d + 1 ⋅ ( R 1 + R 2 ) + X 2 ( d + 1 ) ⋅ ( O 1 + O 2 ) . More generally, suppose that we had F = ∑ m i = 1 c i ⋅ F i for some ( c 1 , … , c m ) . Then we’ll also have L = ∑ m i = 1 c i ⋅ L i , R = ∑ m i = 1 c i ⋅ R i , O = ∑ m i = 1 c i ⋅ O i for the same coefficients ( c 1 , … , c m ) .

In other words, if F is a linear combination of the F i ’s it means that L , R , O were indeed produced from an assignment. Therefore, Ted will ask Jennifer to prove to him that F is a linear combination of the F i ’s. This is done in a similar way to the protocol for verifiable evaluation: Ted chooses a random β ∈ F ∗ p , and sends to Jennifer the hidings E ( β ⋅ F 1 ( s ) ) , … , E ( β ⋅ F m ( s ) ) . He then asks Jennifer to send him the element E ( β ⋅ F ( s ) ) .

If she succeeds, an extended version of the Knowledge of Coefficient Assumption implies she knows how to write F as a linear combination of the F i ’s.

Let’s combine the polynomials L , R , O into one polynomial F as follows: F = L + X d + 1 ⋅ R + X 2 ( d + 1 ) ⋅ O The point of multiplying R by X d + 1 and O by X 2 ( d + 1 ) is that the coefficients of L , R , O “do not mix” in F : The coefficients of 1 , X , … , X d in F are precisely the coefficients of L , the next d + 1 coefficients of X d + 1 , … , X 2 d + 1 are precisely the coefficients of R , and the last d + 1 coefficients are those of O .

Let’s combine the polynomials in the QAP definition in a similar way, defining for each i ∈ { 1 , … , m } a polynomial F i whose first d + 1 coefficients are the coefficients of L i , followed be the coefficients of R i and then O i . That is, for each i ∈ { 1 , … , m } we define the polynomial F i = L i + X d + 1 ⋅ R i + X 2 ( d + 1 ) ⋅ O i Note that when we sum two of the F i ’s the L i , R i , and O i “sum separately”. For example, F 1 + F 2 = ( L 1 + L 2 ) + X d + 1 ⋅ ( R 1 + R 2 ) + X 2 ( d + 1 ) ⋅ ( O 1 + O 2 ) .

More generally, suppose that we had F = ∑ m i = 1 c i ⋅ F i for some ( c 1 , … , c m ) . Then we’ll also have L = ∑ m i = 1 c i ⋅ L i , R = ∑ m i = 1 c i ⋅ R i , O = ∑ m i = 1 c i ⋅ O i for the same coefficients ( c 1 , … , c m ) . In other words, if F is a linear combination of the F i ’s it means that L , R , O were indeed produced from an assignment.

Therefore, Ted will ask Jennifer to prove to him that F is a linear combination of the F i ’s. This is done in a similar way to the protocol for verifiable evaluation: Ted chooses a random β ∈ F ∗ p , and sends to Jennifer the hidings E ( β ⋅ F 1 ( s ) ) , … , E ( β ⋅ F m ( s ) ) . He then asks Jennifer to send him the element E ( β ⋅ F ( s ) ) . If she succeeds, an extended version of the Knowledge of Coefficient Assumption implies she knows how to write F as a linear combination of the F i ’s.