Matter labs ethereum series

matter labs ethereum series
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 (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


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 = 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
  • Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS

STARKS

STARK = Succinct (Scalable) Transparent ARguments of Knowledge

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

Leave a Reply

Your email address will not be published.