Awesome zero knowledge proofs (zkp)

A curated list of awesome things related to learning zero knowledge proofs

- Contents
- General introduction
- Courses
- Use cases
- Applications
- Ethereum
- Other blockchains
- Comparison of the most popular zkp systems
- Bulletproofs
- Try
- Proof system implementations:
- Halo
- SNARKs
- Learn
- Try
- Scaling the prover
- Multi-Party Ceremony (MPC) for Trusted Setup
- SNORKs
- Sonic
- PLONK
- Marlin
- STARKS
- Learn
- FRI-STARKs
- SuperSonic
- Fractal
- Social media

## Contents

- General introduction
- Courses
- Applications
- Comparison of the most popular zkp systems
- Bulletproofs
- Halo

- SNARKs
- SNORKs
- Sonic
- Marlin
- PLONK

- STARKs
- FRI-STARKs
- SuperSonic
- Fractal

- Social media

## General introduction

Zero-Knowledge Proofs Starter Pack: alternative introductory list for beginners (more videos).

- Zero Knowledge Proofs: An illustrated primer by Matthew Green
- Demystifying zero-knowledge proofs (video) (math-heavy, awesome introduction into underlying cryptography)
- Introduction to SNARKs/STARKs by Eli Ben-Sasson (YouTube)
- On Interactive Proofs and Zero-Knowledge: A Primer

A Hands-On Tutorial for Zero-Knowledge Proofs by Shir Peled (StarkWare):

- Part I
- Part II
- Part III
- Appendix

Zero-Knowledge Proofs for Engineers (Dark Forest)

- Part I
- Part II

More complete curated list of implementations and scientific resources: https://zkp.science

## Courses

- The 9th BIU Winter School on Cryptography: Zero Knowledge
- UIUC: ECE498AC/CS498AM: Applied Cryptography, Fall 2019

## Use cases

- Awesome Privacy on Blockchains

## Applications

### Ethereum

- ZK Sync by Matter Labs
- ZK SDK
- ZK Sync code
- ZK Sync live demo

- SNARK-based permissioned database: rollup by BarryWhitehat
- Gnosis dFusion: DEX on SNARKs
- Loopring DEX Protocol (v3)
- zkPoD: A Practical Decentralized System for Data Exchange
- Dark Forest: zkSNARK space warfare strategy game

### Other blockchains

- Zcash: Privacy-Protecting Digital Currency (SNARKs)
- chatroom

- Monero: Private Digital Currency (Bulletproofs)
- Coda: A Constant-Size Blockchain (recursive SNARKs)
- YouTube introduction

- Grin: Simple, privacy-focused, scalable MimbleWimble chain implementation (Bulletproofs)
- Beam: Private and Scalable Coin based on MimbleWimble

## Comparison of the most popular zkp systems

SNARKsSTARKsBulletproofsAlgorithmic complexity: proverO(N * log(N))O(N * poly-log(N))O(N * log(N))Algorithmic complexity: verifier~O(1)O(poly-log(N))O(N)Communication complexity (proof size)~O(1)O(poly-log(N))O(log(N))- size estimate for 1 TXTx: 200 bytes, Key: 50 MB45 kB1.5 kb- size estimate for 10.000 TXTx: 200 bytes, Key: 500 GB135 kb2.5 kbEthereum/EVM verification gas cost~600k (Groth16)~2.5M (estimate, no impl.)N/ATrusted setup required?YES 😒NO 😄NO 😄Post-quantum secureNO 😒YES 😄NO 😒Crypto assumptionsDLP + secure bilinear pairing 😒Collision resistant hashes 😄Discrete log 😏

## Bulletproofs

- Introduction and collection of resources
- From Zero (Knowledge) to Bulletproofs – a long and very nice gradual explanation
- Bulletproofs – succinct and complete description of the protocol

### Try

- Implementation in Haskell
- Implementation in Rust

### Proof system implementations:

- Programmable Constraint Systems for Bulletproofs

### Halo

- Halo: Recursive bullet proof composition

## SNARKs

SNARK = **S**uccinct **N**on-interactive **AR**guments of **K**nowledge

### Learn

Get started:

- Introduction to zk-SNARKs with examples
- What are zk-SNARKs (Zcash blog)
- BabySNARK- The simplest possible SNARK for NP. You know, for kids!

Why and How zk-SNARK Works:

- Why and How zk-SNARK Works 1: Introduction & the Medium of a Proof
- Why and How zk-SNARK Works 2: Proving Knowledge of a Polynomial
- Why and How zk-SNARK Works 3: Non-interactivity & Distributed Setup
- Why and How zk-SNARK Works 4: General-Purpose Computation
- Why and How zk-SNARK Works 5: Variable Polynomials
- Why and How zk-SNARK Works 6: Verifiable Computation Protocol
- Why and How zk-SNARK Works 7: Constraints and Public Inputs
- Why and How zk-SNARK Works 8: Zero-Knowledge Computation

ZkStudyClub:

- ZkStudyClub Part 1: Polynomial Commitments with Justin Drake
- ZkStudyClub Part 2: Polynomial Commitments with Justin Drake
- ZkStudyClub Part 3: Polynomial Commitments with Justin Drake

Electric Coin blog series:

- Explaining SNARKs Part I: Homomorphic Hidings
- Explaining SNARKs Part II: Blind Evaluation of Polynomials
- Explaining SNARKs Part III: The Knowledge of Coefficient Test and Assumption
- Explaining SNARKs Part IV: How to make Blind Evaluation of Polynomials Verifiable
- Explaining SNARKs Part V: From Computations to Polynomials
- Explaining SNARKs Part VI: The Pinocchio Protocol
- Explaining SNARKs Part VII: Pairings of Elliptic Curves

Vitalik Buterin’s blog series on SNARKs:

- Part 1: Quadratic Arithmetic Programs: from Zero to Hero
- Part 2: Exploring Elliptic Curve Pairings
- Part 3: Zk-SNARKs: Under the Hood

Protocol descriptions:

- zkSNARKs in a Nutshell
- Groth16 protocol (original paper)
- Zcash Sapling protocol spec (very useful as detailed cheat-sheet of all cryptography used)

### Try

- libsnark (C++)
- great tutorial

- bellman (rust)
- demo circuit

- jsnark (Java, bindings to libsnark)
- snarky (Ocaml, from authors of Coda)
- zokrates (toolbox for zkSNARKs on Ethereum)
- ZoKrates Remix plugin tutorial
- Zero Knowledge Proof Application Demo, with libsnarks, truffle and docker

- ethsnarks by HarryR (alternative toolkit for viable zk-SNARKS on Ethereum, Web, Mobile and Desktop)
- gnark – library for zero-knowledge proof protocols written in Go
- circom and snarkjs tutorial
- Roll-up tutorial using Circom and SnarkJS by Ying Tong

### Scaling the prover

- DIZK: Java library for distributed zero knowledge proof systems with Apache Spark (see the research paper)
- SnarkyGPU: distributed GPU based zkSNARKs prover (work in progress)

### Multi-Party Ceremony (MPC) for Trusted Setup

- “Powers of Tau” protocol for scalable generation of structured reference string
- Implementation of ZCash MPC Ceremony, Part I: “Powers of Tau”
- Archived independent implementation in Go

- Implementation of ZCash MPC Ceremony, Part I: “Sapling Circuit”

## SNORKs

SNORK = **S**uccinct **N**on-interactive **O**ecumenical (Universal) a**R**guments of **K**nowledge

SNORKs are SNARKs with universal and updateable trusted setup.

### Sonic

- Introducing Sonic: A Practical zk-SNARK with a Nearly Trustless Setup
- Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updateable Structured Reference Strings
- Sonic MPC implementation by Matter Labs

### PLONK

(This is a recent development. Contributions are welcome!)

- Awesome PLONK: A curated list of awesome things related to plonk proof system.
- Understanding PLONK by Vitalik Buterin
- Ignition: Trusted Setup MPC Ceremony for PLONK

### Marlin

(This is a recent development. Contributions are welcome!)

- A Marlin is One of the Fastest SNARKs in the Ocean
- Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS

## STARKS

STARK = **S**uccinct (**S**calable) **T**ransparent **AR**guments of **K**nowledge

STARKs are SNARKs without Trusted Setup.

### Learn

Get started:

- STARK @ Home {video playlist}

### FRI-STARKs

Introduction:

- Transparent Succinct Arguments by Alessandro Chiesa (Oct 2018)
- State of the STARK by Eli Ben-Sasson (Devcon IV, Oct 2018) (video)
- Introduction to ZK-STARKs by [email protected]

Vitalik Buterin’s blog series on STARKs:

- Part I: Proofs with Polynomials
- Part II: Thank Goodness It’s FRI-day
- Part III: Into the Weeds

Academic resources:

- The STARK paper
- libstark implemenation

More resources available at starkware.co

### SuperSonic

(This is a recent development. Contributions are welcome!)

- Transparent SNARKs from DARK Compilers (Dec 2019)
- Introducing Sonic: A Practical zk-SNARK with a Nearly Trustless Setup

### Fractal

(This is a recent development. Contributions are welcome!)

- Fractal: Post-Quantum and Transparent Recursive Proofs from Holography

## Social media

Stay tuned!

- Awesome zero knowledge twitter list
- Zero-knowledge podcast
- ZKProof, an academic and industry initiative for standardizing Zero Knowledge Proofs