zero-knowledge proofs/arguments of knowledge: reading list

This page collects useful papers, articles, and links about multi-party computation and zero-knowledge proofs.

SNARKs

​SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge: (Ben-Sasson, Chiesa, Genkin, Tromer, Virza). This defines the zk-SNARK (zero-knowledge Succinct Non-interactive ARgument of Knowledge) scheme used by Zerocash.

This paper collects a number of previous clever ideas, adds some new ones, and finds ways to optimize the combination enough to make everything useful. The resulting system does the following:

• compiles an arbitrary C program into a simple virtual machine named "TinyRAM"
• performs a one-time key-generation phase that takes the program and limits on runtime and input size, and produces two keys: the "proving key" and the "verification key". The proving key is very big, while the verification key is pretty small.
• for each run of the program (given some primary input):
  • the Prover runs the TinyRAM program in a special way that gathers information about its execution (order of execution, changes to memory values). It also gets "auxilliary input", which is not revealed to the verifier, and represents nondeterminism (somehow).
  • the Prover combines this information with the proving key to create the proof. These proofs are very small.
  • later, the Verifier can combine the proof, the primary input, and the verification key, and compute a single "accept/reject" value. Verifying a proof is much much faster than creating one.

One example they use is a proof of a good solution for the "rectilinear Traveling Salesman Problem", whose input is the node locations (x,y), the starting point (x,y), and a distance bound. You can solve this problem by measuring the Manhattan distance for all possible routes (permutations of the non-starting-point nodes) and finding at least one whose total distance is lower than the bound. Their example uses such a solution as the "auxilliary input", and a TinyRAM program which sums the distances and compares it against the bound. The verifier learns that the program really does run and emits "yes", without learning what the route is.

For a 200-node graph, their TinyRAM program had 1105 instructions and needed 11001 steps to complete. It took 247 minutes to create the proving and verification keys. The proving key was about 12GB (using an 80-bit security level), and the verification key was 620 bytes. It then took 155 minutes to create one instance of the proof, and the proof itself was 322 bytes. Verifying the proof took 0.11 seconds.