Explaining SNARKs Part VI: The Pinocchio Protocol

<< Part V

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=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.

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=HTP=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 HTH⋅T will be different polynomials. Note that PP and HTH⋅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.

  1. Alice chooses polynomials L,R,O,HL,R,O,H of degree at most dd.
  2. Bob chooses a random point s?ps∈Fp, and computes E(T(s))E(T(s)).
  3. 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)).
  4. 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 anypolynomials L,R,O,HL,R,O,H of degree at most dd with LRO=THL⋅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=1ciLi,R:=mi=1ciRi,O:=mi=1ciOiL:=∑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+1R+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+1Ri+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=1ciFiF=∑i=1mci⋅Fi for some (c1,,cm)(c1,…,cm). Then we’ll also have L=mi=1ciLi,R=mi=1ciRi,O=mi=1ciOiL=∑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 (c1,,cm)(c1′,…,cm′) Bob could compute the corresponding L,R,O,HL′,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 (c1,,cm)(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+δ1T,Rz:=R+δ2T,Oz:=O+δ3TLz:=L+δ1⋅T,Rz:=R+δ2⋅T,Oz:=O+δ3⋅T.

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

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

Thus, defining H=H+Lδ2+δ1R+δ1δ2TH′=H+L⋅δ2+δ1⋅R+δ1δ2⋅T, we have that LzRzOz=THzLz⋅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, δ1T(s)δ1⋅T(s) is a random value, and therefore Lz(s)=L(s)+δ1T(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.

Comments 1

发表评论

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