Sep 7, 2017 |
3 minutes read

ZK SNARKs are one of the most amazing products of modern cutting edge cryptography. They let a prover secretly run a program of arbitrary complexity and generate a compact proof that any can verify that correctly ran the program. The program can have secret inputs and the prover reveals nothing to the user.

Zk SNARKs have been deployed in the ZCash cryptocurrency and many other protocols are examining using them. SNARKs represent the culmination of decades of research into the field anonymous credentials. Blockchain transactions are a type of credential and the potential applications of SNARK transactions in a blockchain context seem limitless.

SNARKs are a synthesis of multiple areas of cryptography and theoretical computer science that were unified into a cohesive whole. This requires conducting a survey over a large field of research.

The resources below are a great starting point.

Ethereum have been very interested getting the ability to evaluate various SNARK protocols into the Ethereum system to enhance the privacy properties of smart contracts. This survey of SNARKs is very comprehensive and good jumping off point for someone familiar with cryptography.

- Eran Tromer’s introduction to SNARKs is a also a decent jumping off point if you like a lecture format. He tries to provide a comprehensive introduction to the subject targeted at graduate level students.

SNARKs are a synthesis of multiple lines of research the combined researchers observed that progress in compiling arbitrary programs into arithmetic functions could be combined with progress in certain fields of partially homomorphic cryptography. Vitalik does a deep dive into how simple programs get turned into arithmetic functions. This is one of the most magical parts of the SNARK system.

Alisa Pankova did an incredible literature review of the entire field of Quadratic arithemetic programs.

Highly recommend Parings for Beginners for learning about the pairing cryptosystems that allow QAPs to generate such compact proofs

Check out Appendix A. It’s p cool on how simple verification is.

2016 work from Jens Goth that shrinks the size of proofs to their theoretical limits, increases speed of verification and potentially increases the number of parties involved in generating the CRS dramatically. Will be used in the next ZCash protocol upgrade.

2017 work from Goth that trade larger proofs for built in non-malleability.

The Techniques ZCash used in their CRS generation ceremony.