zero-knowledge
Part 4
In the three previous parts, we developed a certain machinery for dealing with polynomials. In this part, we show how to translate statements we would like to prove and verify to the language of polynomials. The idea of using polynomials in this way goes back to the groundbreaking work of Lund, Fortnow, Karloff, and Nisan.
In 2013, another breakthrough work of Gennaro, Gentry, Parno, and Raykova defined an extremely useful translation of computations into polynomials called a Quadratic Arithmetic Program (QAP). QAPs have become the basis for modern zk-SNARK constructions, in particular those used by Zcash.
In this post we explain the translation into QAPs by example. Even when focusing on a small example rather than the general definition, it is unavoidable that it is a lot to digest at first, so be prepared for a certain mental effort.
Arithmetic Circuits
The bottom wires are the input wires, and the top wire is the output wire giving the result of the circuit computation on the inputs.
As can be seen in the picture, we label the wires and gates of the circuit in a very particular way, needed for the next step of translating the circuit into a QAP:
- We assume multiplication gates have exactly two input wires, which we call the left wire and right wire.
A legal assignment for the circuit is an assignment of values to the labeled wires where the output value of each multiplication gate is indeed the product of the corresponding inputs.
Reduction to a QAP
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.
[1]In this post we tried to give the most concise example of a reduction to QAP; we also recommend Vitalik Buterin's excellent post for more details on the transformation from a program to a QAP.
Part 6