Zaki's Blog

Learning About ZK SNARKs

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.

Surveys

  1. ZK-SNARKs in a Nut Shell

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.

  1. 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.

Qudratic Arithmetic Programs

  1. Quadratic Arithmetic Programs: from Zero to Hero

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.

  1. Succinct Non-Interactive Arguments from Quadratic Arithmetic Programs

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

Pairing Cryptography

  1. http://www.craigcostello.com.au/pairings/PairingsForBeginners.pdf

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

Core SNARK papers

  1. SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge

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

  1. Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture

  2. The Hunting Of the SNARK

  1. Succinct Non-Interactive Arguments via Linear Interactive Proofs

Recent research

  1. On The Size of Pairing-based Non-Interactive Arguments

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.

  1. Snarky Signatures: \ Minimal Signatures of Knowledge from Simulation-Extractable SNARKs

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

  1. A multi-party protocol for constructing the public parameters of the Pinocchio zk-SNARK

The Techniques ZCash used in their CRS generation ceremony.

  1. JubJub The ZCash Electric Coin Company’s breakthrough improvements in SNARK performance