Changes between Initial Version and Version 1 of SNARKs

Timestamp:

2014-03-11T18:29:08Z (12 years ago)

Author:

warner

Comment:

collecting papers on SNARKs and other multi-party-computation -ish topics

SNARKs

@@ +1 @@
+= 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 ==
+
+[http://tau.ac.il/~tromer/papers/csnark-20131007.pdf 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.
+