Awesome zero knowledge proofs (zkp)

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

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 (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

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

	SNARKs	STARKs	Bulletproofs
Algorithmic complexity: prover	O(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 TX	Tx: 200 bytes, Key: 50 MB	45 kB	1.5 kb
- size estimate for 10.000 TX	Tx: 200 bytes, Key: 500 GB	135 kb	2.5 kb
Ethereum/EVM verification gas cost	~600k (Groth16)	~2.5M (estimate, no impl.)	N/A
Trusted setup required?	YES 😒	NO 😄	NO 😄
Post-quantum secure	NO 😒	YES 😄	NO 😒
Crypto assumptions	Strong 😒	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 = Succinct Non-interactive ARguments of Knowledge

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 = Succinct Non-interactive Oecumenical (Universal) aRguments of Knowledge

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

STARKS

STARK = Succinct (Scalable) Transparent ARguments of Knowledge

STARKs are SNARKs without Trusted Setup.

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