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 of degree and size consists of polynomials , , and a target polynomial of degree .
An assignment satisfies if, defining and , we have that divides .
As we saw in Part V, Alice will typically want to prove she has a satisfying assignment possessing some additional constraints, e.g. ; 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 as above, there exists a polynomial such that . In particular, for any we have .
Suppose now that Alice doesn’t have a satisfying assignment, but she still constructs as above from some unsatisfying assignment . Then we are guaranteed that does not divide . This means that for any polynomial of degree at most , and will be different polynomials. Note that and here are both of degree at most .
Now we can use the famous Schwartz-Zippel Lemma that tells us that two different polynomials of degree at most can agree on at most points . Thus, if is much larger than the probability that for a randomly chosen is very small.
This suggests the following protocol sketch to test whether Alice has a satisfying assignment.
- Alice chooses polynomials of degree at most .
- Bob chooses a random point , and computes .
- Alice sends Bob the hidings of all these polynomials evaluated at , i.e. .
- Bob checks if the desired equation holds at . That is, he checks whether .
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 . Therefore, Bob will reject with high probability over his choice of 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 . 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 of degree at most with , it just means she can’t find such polynomials where and were “produced from an assignment”; namely, that for the same .
The protocol of Part IV just guarantees she is using some polynomials 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 into one polynomial as follows:
The point of multiplying by and by is that the coefficients of “do not mix” in : The coefficients of in are precisely the coefficients of , the next coefficients of are precisely the coefficients of , and the last coefficients are those of .
Let’s combine the polynomials in the QAP definition in a similar way, defining for each a polynomial whose first coefficients are the coefficients of , followed be the coefficients of and then . That is, for each we define the polynomial
Note that when we sum two of the ‘s the , , and “sum separately”. For example, .
More generally, suppose that we had for some . Then we’ll also have for the same coefficients . In other words, if is a linear combination of the ‘s it means that were indeed produced from an assignment.
Therefore, Bob will ask Alice to prove to him that is a linear combination of the ‘s. This is done in a similar way to the protocol for verifiable evaluation:
Bob chooses a random , and sends to Alice the hidings . He then asks Alice to send him the element . If she succeeds, an extended version of the Knowledge of Coefficient Assumption implies she knows how to write as a linear combination of the ‘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 do provide some information about the assignment.
For example, given some other satisfying assignment Bob could compute the corresponding and hidings . If these come out different from Alice’s hidings, he could deduce that is not Alice’s assignment.
To avoid such information leakage about her assignment, Alice will conceal her assignment by adding a “random -shift” to each polynomial. That is, she chooses random , and defines .
Assume were produced from a satisfying assignment; hence, for some polynomial . As we’ve just added a multiple of everywhere, also divides . Let’s do the calculation to see this:
Thus, defining , we have that . Therefore, if Alice uses the polynomials instead of , Bob will always accept.
On the other hand, these polynomials evaluated at with (which is all but ‘s), reveal no information about the assignment. For example, as is non-zero and is random, is a random value, and therefore reveals no information about 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 from and . 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.