index.md

What is a zero-knowledge proof?

• A New Approach To Protecting Secrets Is Discovered - The New York Times, February 17th, 1987
• Zero Knowledge Proofs: An illustrated primer
• What are zk-SNARKs?
• "The Functionality of zk-SNARK" challenge set in "The Hunting of the SNARK".
• "Probabilistic Proof Systems" course notes
• Vitalik Buterin's introduction to SNARKs, part 1, 2, and 3; and STARKs, part 1, 2, and 3.

History of Zero-knowledge proofs

• Invention of zero-knowledge
  • Zero-Knowledge Proofs [GMR85]
  • Non-Interactive ZK [BFM88]
• Important landmarks for zk-SNARKs
  • Succinct ZK[K92]
  • Succinct Non-Interactive ZK [M94]
  • "SNARK" terminology and characterization of existence [BCCT11]
  • Succinct NIZK without the PCP Theorem [Groth10]
  • Succinct NIZK without PCP Theorem & Quasi-linear prover time (GGPR13)

Recent Zero-Knowledge proving systems

• GGPR13
  • Pinocchio (PGHR13)
  • BCGTV13
  • Geppetto (CFHKKNPZ14)
  • BCTV14a
• BCTV14b
  • Coda (MS18)
• CTV15
• ZKBoo (GMO16)
• Groth16
  • GM17
  • BG18
  • DIZK (WZCPS18)
    • Distributed implementation of Groth16
    • Enables zkSNARK computations of up to billions of logical gates (100x larger than prior art) at a cost of 10μs per gate (100x faster than prior art)
    • Implements distributed polynomial evaluation/interpolation, distributed Lagrange polynomial computations, and distributed multi-scalar multiplication
• BCCGP16
  • Bulletproofs (BBBPWM17)
• Hybrid Interactive ZK (CCM16)
• ZKB++ / Picnic (CDGORRSZ17)
• Ligero (AHIV17)
• Hyrax (WTSTW17)
• zk-STARKs (BBHR18)
• Updatable Universal CRSs (GKMMM18)
  • Sonic (MBKM19)
• Hybrid NIZK (ACM18)
• Aurora (BCRSVW18)
• Libra (XZZPS19)

Implementations of proving systems

Name	Language	Curves	Proving systems
libsnark	C++	BN254	Groth16, BCTV14a, BCTV14b, CTV15
bellman	Rust	BLS12-381	Groth16
dalek bulletproofs	Rust	ristretto255	BBBPWM17
adjoint-io bulletproofs	Haskell	secp256k1	BBBPWM17
DIZK	Java	BN254	Groth16
snarkjs	JavaScript	BN254	Groth16, BCTV14a
websnark	WebAssembly	BN254	Groth16

Other implementations:

• ZKBoo
• ZKB++
• BBBPWM17
  • BulletProofLib - Java implementation
  • secp256k1-zkp (experimental) - C implementation on secp256k1
• Picnic
  • Reference implementation
  • Optimized implementation
• emmy
  • ZKP primitives for Camenisch-Lysyanskaya anonymous credentials
  • Camenisch-Lysyanskaya anonymous credentials (work in progress)
  • client-server (prover-verifier) communication based on Protobuffers and gRPC
• VC implementation accompanying the Pinocchio (PGHR13) and Geppetto (CFHKKNPZ14) papers
• ZEXE - a Rust library for decentralized private computation
  • GM17
• libSTARK - Academic C++ library for zk-STARKs
  • BBHR18
• libiop - Academic C++ library for IOP-based zk-SNARKs.
  • AHIV17
  • BCRSVW18

Generating structured reference strings

Some proving systems require a structured reference string (SRS). The following works discuss secure SRS generation.

• [BCGTV15] - MPC for generating the SRS for PGHR13/BCGTV13
• [BGG17] - improved MPC for generating the SRS for PGHR13/BCGTV13
• [BGM18] - "Powers of Tau" protocol for scalable generation of structured reference string for Groth16

Libraries for writing circuits

Name	DSL	Host Language	Backed by	Description
libsnark's gadgetlib1/2		C++	libsnark	Libraries for building circuits for preprocessing zk-SNARKs
bellman		Rust	bellman	Library for building circuits; various gadgets in sapling-crypto
jsnark		Java	libsnark	Library for building circuits for preprocessing zk-SNARKs
ZoKrates	Python subset	Rust	libsnark, bellman	Toolbox for zk-SNARKs on Ethereum
Snarky	Embedded OCaml	OCaml	libsnark	Front-end for writing R1CS SNARKs
Circom	Typed JS	JavaScript	snarkjs	Language for writing R1CS SNARKs
Circomlib	Typed JS	JavaScript		Library of basic circuits for Circom
ZEXE's snark-gadgets		Rust	ZEXE	Module for building circuits, comes with pre-built algebra circuits
ZkVM		Rust	bulletproofs	Language for writing confidential smart contracts that create Bulletproofs R1CS proofs

General-purpose compilers from high-level languages

• ZKPDL [MEKHL10]
  • Cashlib - C++ implementation
• Pinocchio (PGHR13)
  • Pinocchio toolchain - Python implementation
• Pantry [BFRSBW13]
• Geppetto (CFHKKNPZ14)
• TinyRAM (BCGTV13), vnTinyRAM (BCTV14a) and scalable TinyRAM (BCTV14b)
• Buffet [WSRBW15]
• C0C0 [KZMQCPPSS15]
• Pequin - Toolchain to verifiably execute programs expressed in (a large subset of) C, backed by libsnark.
  • Relevant publications
• Snårkl [SML17] - Haskell embedded DSL for verifiable computing
  • Implementation backed by libsnark
• xJsnark [KPS18]

Example circuits

• Zcash Sprout
  • Based on Zerocash [BCGGMTV14]
  • C++ implementation over BN128 using libsnark
  • Rust implementation over BLS12-381 using bellman
• ANONIZE [HMP15]
  • Mobile applications (closed-source)
• [KM18]
• Zcash Sapling
  • Rust implementation over BLS12-381 using bellman
• Zexe [BCGMMW2018]
• Spacesuit
  • Rust implementation of the Cloak confidential assets protocol using Bulletproofs.

Circuit optimization

• Daira Hopwood's notes from Zcon0

Standardization efforts

• Zero Knowledge Proof Standardization and 1st Workshop
• Letter to NIST on standardizing new cryptographic standards

So are they fast yet?

Stay tuned! 😁

Improve this page

Additions, corrections and other suggestions are welcome! You can propose an edit to this page here. (Note that after making your edits, there are 3 confirmations to click through in order to create the "pull request" in the Git repository underlying this page.)

For more broad changes, you can make a pull request here!