## 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
- 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)
- Hybrid NIZK (ACM18)
- Aurora (BCRSVW18)

## 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
- 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
- libSTARK - Academic C++ library for zk-STARKs
- libiop - Academic C++ library for IOP-based zk-SNARKs.

## 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.
- Snårkl [SML17] - Haskell embedded DSL for verifiable computing
- xJsnark [KPS18]

## Example circuits

- Zcash Sprout
- ANONIZE [HMP15]
- [KM18]
- Zcash Sapling
- Zexe [BCGMMW2018]
- Spacesuit
- Rust implementation of the Cloak confidential assets protocol using Bulletproofs.

## Circuit optimization

## 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!