In
part 5 , 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:
This suggests the following protocol sketch to test whether Alice has a satisfying assignment:
Given 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
Adding the zero-knowledge part - concealing the assignment
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:
- 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.