In part V we saw how a statement Alice would like to prove to Bob can be converted into an equivalent form in the “language of polynomials” called a Quadratic Arithmetic Program (QAP).

In this part, we show how Alice can send a very short proof to Bob showing she has a satisfying assignment to a QAP. We will use the Pinocchio Protocol of Parno, Howell, Gentry and Raykova. But first let us recall the definition of a QAP we gave last time:

*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=1ci⋅Li,R:=∑mi=1ci⋅Ri,O:=∑mi=1ci⋅OiL:=∑i=1mci⋅Li,R:=∑i=1mci⋅Ri,O:=∑i=1mci⋅Oi*and* P:=L⋅R−OP:=L⋅R−O, *we have that* TT *divides* PP.

As we saw in Part V, Alice will typically want to prove she has a satisfying assignment possessing some additional constraints, e.g. cm=7cm=7; but we ignore this here for simplicity, and show how to just prove knowledge of *some* satisfying assignment.

If Alice has a satisfying assignment it means that, defining L,R,O,PL,R,O,P as above, there exists a polynomial HHsuch that P=H⋅TP=H⋅T. In particular, for any s∈?ps∈Fp we have P(s)=H(s)⋅T(s)P(s)=H(s)⋅T(s).

Suppose now that Alice *doesn’t* have a satisfying assignment, but she still constructs L,R,O,PL,R,O,P as above from some unsatisfying assignment (c1,…,cm)(c1,…,cm). Then we are guaranteed that TT does not divide PP. This means that for any polynomial HH of degree at most dd, PP and H⋅TH⋅T will be different polynomials. Note that PP and H⋅TH⋅There are both of degree at most 2d2d.

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

This suggests the following protocol sketch to test whether Alice has a satisfying assignment.

- Alice chooses polynomials L,R,O,HL,R,O,H of degree at most dd.
- Bob chooses a random point s∈?ps∈Fp, and computes E(T(s))E(T(s)).
- Alice sends Bob the hidings of all these polynomials evaluated at ss, i.e. E(L(s)),E(R(s)),E(O(s)),E(H(s))E(L(s)),E(R(s)),E(O(s)),E(H(s)).
- Bob checks if the desired equation holds at ss. That is, he checks whether E(L(s)⋅R(s)−O(s))=E(T(s)⋅H(s))E(L(s)⋅R(s)−O(s))=E(T(s)⋅H(s)).

Again, the point is that if Alice 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 ss. Therefore, Bob will reject with high probability over his choice of ss in such a case.

The question is whether we have the tools to implement this sketch. The most crucial point is that Alice must choose the polynomials she will use, *without* knowing ss. But this is exactly the problem we solved in the verifiable blind evaluation protocol, that was developed in Parts II-IV.

Given that we have that, there are four main points that need to be addressed to turn this sketch into a zk-SNARK. We deal with two of them here, and the other two in the next part.

## MAKING SURE ALICE CHOOSES HER POLYNOMIALS ACCORDING TO AN ASSIGNMENT

Here is an important point: If Alice doesn’t have a satisfying assignment, it doesn’t mean she can’t find *any*polynomials L,R,O,HL,R,O,H of degree at most dd with L⋅R−O=T⋅HL⋅R−O=T⋅H, it just means she can’t find such polynomials where L,RL,R and OO were “produced from an assignment”; namely, that L:=∑mi=1ci⋅Li,R:=∑mi=1ci⋅Ri,O:=∑mi=1ci⋅OiL:=∑i=1mci⋅Li,R:=∑i=1mci⋅Ri,O:=∑i=1mci⋅Oi for *the same* (c1,…,cm)(c1,…,cm).

The protocol of Part IV just guarantees she is using some polynomials L,R,OL,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,OL,R,O into one polynomial FF as follows:

F=L+Xd+1⋅R+X2(d+1)⋅OF=L+Xd+1⋅R+X2(d+1)⋅O

The point of multiplying RR by Xd+1Xd+1 and OO by X2(d+1)X2(d+1) is that the coefficients of L,R,OL,R,O “do not mix” in FF: The coefficients of 1,X,…,Xd1,X,…,Xd in FF are precisely the coefficients of LL, the next d+1d+1 coefficients of Xd+1,…,X2d+1Xd+1,…,X2d+1 are precisely the coefficients of RR, and the last d+1d+1 coefficients are those of OO.

Let’s combine the polynomials in the QAP definition in a similar way, defining for each i∈{1,…,m}i∈{1,…,m} a polynomial FiFi whose first d+1d+1 coefficients are the coefficients of LiLi, followed be the coefficients of RiRi and then OiOi. That is, for each i∈{1,…,m}i∈{1,…,m} we define the polynomial

Fi=Li+Xd+1⋅Ri+X2(d+1)⋅OiFi=Li+Xd+1⋅Ri+X2(d+1)⋅Oi

Note that when we sum two of the FiFi‘s the LiLi, RiRi, and OiOi “sum separately”. For example, F1+F2=(L1+L2)+Xd+1⋅(R1+R2)+X2(d+1)⋅(O1+O2)F1+F2=(L1+L2)+Xd+1⋅(R1+R2)+X2(d+1)⋅(O1+O2).

More generally, suppose that we had F=∑mi=1ci⋅FiF=∑i=1mci⋅Fi for some (c1,…,cm)(c1,…,cm). Then we’ll also have L=∑mi=1ci⋅Li,R=∑mi=1ci⋅Ri,O=∑mi=1ci⋅OiL=∑i=1mci⋅Li,R=∑i=1mci⋅Ri,O=∑i=1mci⋅Oi for the same coefficients (c1,…,cm)(c1,…,cm). In other words, if FF is a linear combination of the FiFi‘s it means that L,R,OL,R,O were indeed produced from an assignment.

Therefore, Bob will ask Alice to prove to him that FF is a linear combination of the FiFi‘s. This is done in a similar way to the protocol for verifiable evaluation:

Bob chooses a random β∈?∗pβ∈Fp∗, and sends to Alice the hidings E(β⋅F1(s)),…,E(β⋅Fm(s))E(β⋅F1(s)),…,E(β⋅Fm(s)). He then asks Alice to send him the element E(β⋅F(s))E(β⋅F(s)). If she succeeds, an extended version of the Knowledge of Coefficient Assumption implies she knows how to write FF as a linear combination of the FiFi‘s.

## ADDING THE ZERO-KNOWLEDGE PART – CONCEALING THE ASSIGNMENT

In a zk-SNARK Alice wants to conceal all information about her assignment. However the hidings E(L(s)),E(R(s)),E(O(s)),E(H(s))E(L(s)),E(R(s)),E(O(s)),E(H(s)) do provide *some* information about the assignment.

For example, given some other satisfying assignment (c′1,…,c′m)(c1′,…,cm′) Bob could compute the corresponding L′,R′,O′,H′L′,R′,O′,H′ and hidings E(L′(s)),E(R′(s)),E(O′(s)),E(H′(s))E(L′(s)),E(R′(s)),E(O′(s)),E(H′(s)). If these come out different from Alice’s hidings, he could deduce that (c′1,…,c′m)(c1′,…,cm′) is not Alice’s assignment.

To avoid such information leakage about her assignment, Alice will conceal her assignment by adding a “random TT-shift” to each polynomial. That is, she chooses random δ1,δ2,δ3∈?∗pδ1,δ2,δ3∈Fp∗, and defines Lz:=L+δ1⋅T,Rz:=R+δ2⋅T,Oz:=O+δ3⋅TLz:=L+δ1⋅T,Rz:=R+δ2⋅T,Oz:=O+δ3⋅T.

Assume L,R,OL,R,O were produced from a satisfying assignment; hence, L⋅R−O=T⋅HL⋅R−O=T⋅H for some polynomial HH. As we’ve just added a multiple of TT everywhere, TT also divides Lz⋅Rz−OzLz⋅Rz−Oz. Let’s do the calculation to see this:

Lz⋅Rz−Oz=(L+δ1⋅T)(R+δ2⋅T)−O−δ3⋅TLz⋅Rz−Oz=(L+δ1⋅T)(R+δ2⋅T)−O−δ3⋅T =(L⋅R−O)+L⋅δ2⋅T+δ1⋅T⋅R+δ1δ2⋅T2−δ3⋅T=(L⋅R−O)+L⋅δ2⋅T+δ1⋅T⋅R+δ1δ2⋅T2−δ3⋅T =T⋅(H+L⋅δ2+δ1⋅R+δ1δ2⋅T)=T⋅(H+L⋅δ2+δ1⋅R+δ1δ2⋅T)

Thus, defining H′=H+L⋅δ2+δ1⋅R+δ1δ2⋅TH′=H+L⋅δ2+δ1⋅R+δ1δ2⋅T, we have that Lz⋅Rz−Oz=T⋅HzLz⋅Rz−Oz=T⋅Hz. Therefore, if Alice uses the polynomials Lz,Rz,Oz,HzLz,Rz,Oz,Hz instead of L,R,O,HL,R,O,H, Bob will always accept.

On the other hand, these polynomials evaluated at s∈?ps∈Fp with T(s)≠0T(s)≠0 (which is all but dd ss‘s), reveal no information about the assignment. For example, as T(s)T(s) is non-zero and δ1δ1 is random, δ1⋅T(s)δ1⋅T(s) is a random value, and therefore Lz(s)=L(s)+δ1⋅T(s)Lz(s)=L(s)+δ1⋅T(s) reveals no information about L(s)L(s) as it is masked by this random value.

## WHAT’S LEFT FOR NEXT TIME?

We presented a sketch of the Pinocchio Protocol in which Alice can convince Bob she possesses a satisfying assignment for a QAP, without revealing information about that assignment. There are two main issues that still need to be resolved in order to obtain a zk-SNARK:

- In the sketch, Bob needs an HH that “supports multiplication”. For example, he needs to compute E(H(s)⋅T(s))E(H(s)⋅T(s)) from E(H(s))E(H(s)) and E(T(s))E(T(s)). However, we have not seen so far an example of an HH that enables this. We have only seen an HH that supports addition and linear combinations.
- Throughout this series, we have discussed
*interactive*protocols between Alice and Bob. Our final goal, though, is to enable Alice to send single-message*non-interactive proofs*, that are*publicly verifiable*– meaning that anybody seeing this single message proof will be convinced of its validity, not just Bob (who had prior communication with Alice).

Both these issues can be resolved by the use of pairings of elliptic curves, which we will discuss in the next and final part.

[…] << Part VI […]