Zero Knowledge Proofs

Introduction to Modern SNARKs
Instructors: Dan Boneh, Shafi Goldwasser, Dawn Song, Justin Thaler, Yupeng Zhang

What is a zk-SNARK ?

(intuition)▪

ZKP MOOC

Commercial interest in SNARKs

Many more building applications that use SNARKs

ZKP MOOC

Why so much commercial interest?
Babai-Fortnow-Levin-Szegedy 1991:
In this setup, a single reliable PC can monitor
the operation of a herd of supercomputers
working with unreliable software.
“Checking Computations in Polylogarithmic Time”

ZKP MOOC

Why so much commercial interest?
Babai-Fortnow-Levin-Szegedy 1991:
a slow and expensive computer

In this setup, a single reliable PC can monitor
the operation of a herd of supercomputersGPUs
working with unreliable software.
“Checking Computations in Polylogarithmic Time”

ZKP MOOC

Why so much commercial interest?
Babai-Fortnow-Levin-Szegedy 1991:
L1 blockchain

In this setup, a single reliable PC can monitor
the operation of a herd of supercomputersGPUs
working with unreliable software.
“Checking Computations in Polylogarithmic Time”

ZKP MOOC

Blockchain Applications I
Outsourcing computation: (no need for zero knowledge)
L1 chain quickly verifies the work of an off-chain service
Examples:▪ Scalability: proof-based Rollups (zkRollup)
off-chain service processes a batch of Tx;
L1 chain verifies a succinct proof that Tx were processed correctly▪ Bridging blockchains: proof of consensus (zkBridge)
enables transfer of assets from one chain to another
ZKP MOOC

Blockchain Applications II
Some applications require zero knowledge (privacy):▪ Private Tx on a public blockchain:▪ zk proof that a private Tx is valid (Tornado cash, Zcash, IronFish, Aleo)▪ Compliance:▪ Proof that a private Tx is compliant with banking laws (Espresso)▪ Proof that an exchange is solvent in zero-knowledge (Raposa)

ZKP MOOC

Many non-blockchain applications
More on these blockchain applications later in course
Blockchains drive the development of SNARKs… but many non-blockchain applications

ZKP MOOC

Using ZK to fight disinformation

ZKP MOOC

C2PA: a standard for content provenancelocationtimestamp
embedded certified
signing key sk

signature

C2PA

verify metadata
by checking sig

ZKP MOOC

A problem: post-processing
Newspapers often process the photos before publishing:▪ Resize (1500×1000), Crop, Grayscale (AP lists allowed ops)
The problem: laptop cannot verify signature on processed photoprocessedphoto???

ZKP MOOC

A solution using a zk-SNARK(with T. Datta, 2022)▪
photolocation
timestamp
proof πZKP MOOC

Performance▪
(in browser)

See also: PhotoProof by Naveh & Tromer (2016)
ZKP MOOC

Why are all these applications possible now?
The breakthrough: new fast SNARK provers▪ Proof generation time is linear (or quasilinear) in computation size
▪ Many beautiful ideas … will cover in lecturesa large bibliography:

a16zcrypto.com/zero-knowledge-canon

ZKP MOOCNext segment:

What is a SNARK?

ZKP MOOC
Credit: Faithie/ShutterstockWhat is a SNARK?

ZKP MOOC
Credit: Faithie/ShutterstockReview: arithmetic circuits▪

ZKP MOOC

Interesting arithmetic circuits
Examples:▪ CSHA(h, m): outputs 0 if SHA256(m) = h , and ≠0 otherwise
ChSHA(h, m) = (h – SHA256(m)) , |CSHA| ≈ 20K gates▪ Csig(pk, m, σ): outputs 0 if σ is a valid ECDSA signature
on m with respect to pk

ZKP MOOC

Structured vs. unstructured circuits
An unstructured circuit: a circuit with arbitrary wires⋯

outputinput

A structured circuit:Some SNARK techniques only apply to structured circuits
ZKP MOOC

(preprocessing)

Prover

NARK: Non-interactive ARgument of Knowledge

Verifier

accept orreject

ZKP MOOC

(preprocessing)

NARK: Non-interactive ARgument of Knowledge▪

all algs. and adversary haveaccess to a random oracle

ZKP MOOCNARK: requirements (informal)
accept or reject

ZKP MOOCSNARK: a Succinct ARgument of Knowledge▪

ZKP MOOCSNARK: a Succinct ARgument of Knowledge▪

short “summary” of circuit

ZKP MOOCSNARK: a Succinct ARgument of Knowledge
SNARK:a NARC (complete and knowledge sound) that is succinct

zk-SNARK: a SNARK that is also zero knowledge

ZKP MOOC

The trivial SNARK is not a SNARK▪

ZKP MOOC

Types of preprocessing Setup▪

betterrandom bits

deterministic algorithm

ZKP MOOC

Significant progress in recent years (partial list)
setup

post-quantum?

Groth’16

trusted percircuitnoPlonk / Marlin

universal
trusted setupnoBulletproofs

DLOG

no

collision
resistanceyes

verifier timeSTARK

ZKP MOOC

Significant progress in recent years (partial list)
setup

post-quantum?

(for a circuit with ≈220 gates)

trusted percircuit

noPlonk / Marlin

universal
trusted setup

noBulletproofs

transparent

noSTARKtransparent

yes

verifier time
Groth’16⋮⋮ZKP MOOC

Significant progress in recent years (partial list)
setup

post-quantum?

Groth’16

trusted per
circuitnoPlonk / Marlin

universal
trusted setup

noBulletproofs

transparent

noSTARKtransparent

yes

verifier time⋮

⋮ZKP MOOCHow to define“knowledge soundness”?

ZKP MOOC
Credit: Faithie/ShutterstockDefinitions: knowledge soundness▪

P

ZKP MOOC

Definitions: knowledge soundness▪

ZKP MOOC

Zero knowledge

Where isWaldo?

ZKP MOOC

Defining Zero knowledge

See previous lecture

ZKP MOOC

Building an efficient SNARKZKP MOOC
Credit: Faithie/ShutterstockRecall: SNARK (Non-interactive ARgument of Knowledge)▪

ZKP MOOC

General paradigm: two steps(1)

A functional
commitment
scheme(cryptographic object)(2)

A compatible
interactiveoracle proof (IOP)(info. theoretic object)

SNARK forgeneral circuits

Let’s explain each concept …

ZKP MOOC

Review: commitments▪

ZKP MOOC

A standard construction▪

ZKP MOOC

Committing to a function
Prover$Verifiercomfaccept orreject

ZKP MOOC

Committing to a function: syntax▪

a (zk)SNARK for the relation:

ZKP MOOC

Four important functional commitments▪

ZKP MOOC

Let’s look at polynomial commitments▪

ZKP MOOC

Let’s look at polynomial commitments▪

ZKP MOOC

The trivial commitment scheme is not apolynomial commitment▪

ZKP MOOC

A useful observation▪
$(∗)$ZKP MOOC

A useful observation▪

$⇒ a simple equality test for two committedpolynomials
ZKP MOOC

Let’s look at the equality test protocol
ProverA public coinprotocol

Verifier$ZKP MOOC

Making it a SNARK (non-interactive)
The Fiat-Shamir transform:▪ public-coin interactive protocol ⇒ non-interactive protocol[public coin: all verifier randomness is public]

accept or reject

ZKP MOOC

A SNARK for polynomial equality testing▪

accept or reject

ZKP MOOC

A SNARK for polynomial equality testing▪

in practice, use SHA256

accept or reject

ZKP MOOC

Back to the paradigm(1)

A functionalcommitment
schemeSNARK forgeneral circuits(2)

A compatible
interactiveoracle proof (IOP)ZKP MOOC

Goal: boost functional commitment ⇒ SNARK for general circuits

Poly-IOPZKP MOOC▪

ZKP MOOC

oracle$oracle⋮$oracle

ZKP MOOC

Properties▪

ZKP MOOCAn example Poly-IOP (a bit contrived)$

ZKP MOOC

The IOP Zoo(⇒ SNARKs for general circuits)

Poly-IOP
Sonic,
Marlin,Plonk, …

Multilinear-IOP
Spartan,
Clover,Hyperplonk, …

Poly-Commit

Multilinear-Commit

Vector-IOP
STARK,Breakdown,
Orion, …

non-interactive
via Fiat-Shamir

MerkleSNARKZKP MOOCSNARKs in practice
DSL
programCircom,ZoKrates,
Leo,
Zinc,
Cairo,
Noir,
…

SNARK
friendlyformatcompilerdomain specificlanguage

SNARK
backendproverheavy
computation

circuit,
R1CS,
…
EVM
byte code

ZKP MOOC

END OF LECTURE

Coming up:(i) SNARK DSLs
(ii) an efficient multilinear IOP

ZKP MOOC
Credit: Faithie/Shutterstock