Zero Knowledge Proofs: An illustrated primer

[tao]

What are they, how do they work, and are they fast yet?

 

Introduction: One of the best things about modern cryptography is the beautiful terminology. You could start any number of punk bands (or Tumblrs) named after cryptography terms like ‘hard-core predicate’, ‘trapdoor function’, ‘ or ‘impossible differential cryptanalysis’. And of course, I haven’t even mentioned the one term that surpasses all of these. That term is ‘zero knowledge‘.

 

In fact, the term ‘zero knowledge’ is so appealing that it leads to problems. People misuse it, assuming that zero knowledge must be synonymous with ‘really, really secure‘. Hence it gets tacked onto all kinds of stuff — like encryption systems and anonymity networks — that really have nothing to do with true zero knowledge protocols.

 

This all serves to underscore a point: zero-knowledge proofs are one of the most powerful tools cryptographers have ever devised. But unfortunately they’re also relatively poorly understood. In this series of posts I’m going try to give a (mostly) non–mathematical description of what ZK proofs are, and what makes them so special. In this post and the next I’ll talk about some of the ZK protocols we actually use.

 

Contents:

What is a zero-knowledge proof?

• 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

Zero-knowledge proving systems

• [GGPR13]
  • Pinocchio [PGHR13]
  • [BCGTV13]
  • Geppetto [CFHKKNPZ14]
  • [BCTV14a]
• [BCTV14b]
  • Coda [MS18]
• [CTV15]
• ZKBoo [GMO16]
• [Groth16]
  • [GM17]
  • [BG18]
• [BCC+16]
  • Bulletproofs [BBBPWM17]
• Hybrid Interactive ZK [CCM16]
• ZKB++ / Picnic [CDGORRSZ17]
• Ligero [AHIV17]
• Hyrax [WTSTW17]
• zk-STARKs [BBHR18]
• Updatable Universal CRSs [GKMMM18]
• Hybrid NIZK [ACM18]

Implementations of proving systems

• libsnark - C++ library for zk-SNARK proofs
  • [GGPR13] (implements [BCTV14a] approach)
  • [BCTV14b]
  • [CTV15]
• bellman - Rust library for zk-SNARK proofs
  • [Groth16]
• ZKBoo
• [BCC+16]
  • BulletProofLib - Java implementation (implements Bulletproofs [BBBPWM17] approach)
  • secp256k1-zkp (experimental) - C implementation on secp256k1 (implements Bulletproofs [BBBPWM17] approach)
  • dalek-cryptography/bulletproofs - Rust implementation using Ristretto on Curve25519 (implements Bulletproofs [BBBPWM17] approach) (notes)
  • adjoint-io/bulletproofs - Haskell implementation on secp256k1 (implements Bulletproofs [BBBPWM17] approach)
• Picnic
  • Reference implementation
  • Optimized implementation
• libSTARK
  • zk-STARKs [BBHR18]
• 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

Low-level libraries/languages for writing circuits

• libsnark’s gadgetlib1 and gadgetlib2 - C++ libraries for for building circuits for preprocessing zk-SNARKs
• jsnark - Java library for building circuits for preprocessing zk-SNARKs, backed by libsnark
• ZoKrates - Toolbox for zk-SNARKs on Ethereum, backed by libsnark
• Snarky - OCaml front-end for writing R1CS SNARKs, currently backed by libsnark

General-purpose compilers from high-level languages

• ZKPDL [MEKHL10]
  • Cashlib - C++ implementation
• Pinocchio [PGHR13]
• 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

Standardization efforts

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

 

If interested, please read the primer < here >.