Changes between Version 2 and Version 3 of SNARKs


Ignore:
Timestamp:
2014-03-11T18:46:28Z (10 years ago)
Author:
warner
Comment:

more papers

Legend:

Unmodified
Added
Removed
Modified

  • SNARKs

    v2 v3  
    55
    66== SNARKs ==
     7
     8=== SNARKs for C ===
    79
    810[http://tau.ac.il/~tromer/papers/csnark-20131007.pdf SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge]:
    … …  
    52540.11 seconds.
    5355
     56=== Pinocchio ===
     57
     58[https://eprint.iacr.org/2013/279.pdf Pinocchio: Nearly Practical Verifiable Computation]: (Parno, Gentry)
     59
     60This precursor is the application paper for the main generic snark
     61implementation.
     62
     63=== Recursive Composition of SNARKs ===
     64
     65[http://www.cs.tau.ac.il/~tromer/papers/bootsnark-20120403.pdf Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data]: (Nitansky, Canetti, Chiesa, Tromer)
     66
     67Andrew Miller tells me that the introductory text in this paper is
     68really good, but the rest is "more advanced technical stuff".
     69
     70=== GGPR ===
     71
     72[https://usukitacs.com/sites/default/files/QSP.pdf Quadratic Span Programs and Succinct NIZKs without PCPs]: (Gennaro, Gentry, Parno, Raykova)
     73
     74This is "the" big result in this field, known as "GGPR". Andrew
     75says this is analogous to the big Craig Gentry paper on
     76fully-homomorphic encryption, but for SNARKs. He says it's good to
     77use to gauge your understanding by flipping back to this one.
     78
     79=== History ===
     80
     81http://courses.cs.washington.edu/courses/cse533/05au/pcp-history.pdf
     82
     83Over the last 30 years, folks have been trying to identify what
     84kinds of problems can be proved in this zero-knowledge style (where
     85the "prover" knows a solution but doesn't want to reveal it, and a
     86"verifier" wants to be convinced that they really do know a valid
     87solution). Originally the categories of problems (defined as a
     88class of languages in which the solution is an valid statement in
     89the language) were quite narrow. Variations on what it means to
     90prove something were thrown about (interactive vs non-interactive,
     91publically-verifiable versus not, public coin-tosses vs private).
     92Eventually it was shown that a very large class of problems can be
     93efficiently proved this way.