Zero Knowledge Proofs

SNARKs via Interactive Proofs
Instructors: Dan Boneh, Shafi Goldwasser, Dawn Song, Justin Thaler, Yupeng Zhang

Recall: What is a SNARK ?
▪

ZKP MOOC

Interactive Proofs:
Motivation and ModelZKP MOOC
Credit: Faithie/ShutterstockInteractive Proofs
Cloud Provider

Business/Agency/Scientist

ZKP MOOC

Interactive Proofs
Cloud Provider

Business/Agency/Scientist
Data

ZKP MOOC

Interactive Proofs
Cloud Provider

Business/Agency/Scientist

Data
Summary
Data

ZKP MOOC

Interactive Proofs
Cloud Provider

Business/Agency/Scientist
Question
AnswerData
Summary

Data

ZKP MOOCInteractive Proofs
Cloud Provider

Business/Agency/Scientist
Challenge
Response

Data
Summary

Data

ZKP MOOC

Interactive Proofs
Cloud Provider

Business/Agency/Scientist
Challenge
Response

Data

Data
Summary

Challenge
Response

ZKP MOOC

Interactive Proofs
Cloud Provider

Business/Agency/Scientist
Challenge
Response

Data

Data
Summary

Challenge
Response

ZKP MOOC

Interactive Proofs
Cloud Provider

Business/Agency/Scientist
Challenge
Response

Data

Challenge

AcceptorReject

Response

ZKP MOOC

Interactive Proofs▪ P solves problem, tells V the answer.
▪ Then they have a conversation.
▪ P’s goal: convince V the answer is correct.
▪ Requirements:▪ 1. Completeness: an honest P can convince V to accept.
▪ 2. (Statistical) Soundness: V will catch a lying P with high probability.
This must hold even if P is computationally unbounded and trying totrick V into accepting the incorrect answer.

ZKP MOOC

Interactive Proofs▪ P solves problem, tells V the answer.
▪ Then they have a conversation.
▪ P’s goal: convince V the answer is correct.
▪ Requirements:▪ 1. Completeness: an honest P can convince V to accept.
▪ 2. (Statistical) Soundness: V will catch a lying P with high probability.
This must hold even if P is computationally unbounded and trying totrick V into accepting the incorrect answer.

ZKP MOOC

Interactive Proofs▪ P solves problem, tells V the answer.
▪ Then they have a conversation.
▪ P’s goal: convince V the answer is correct.
▪ Requirements:▪ 1. Completeness: an honest P can convince V to accept.
▪ 2. (Statistical) Soundness: V will catch a lying P with high probability.
If soundness holds only against polynomial-time provers, then theprotocol is called an interactive argument.

ZKP MOOC

Interactive Proofs and Arguments▪ Compare soundness to knowledge soundness (last lecture) for
circuit-satisfiability:

ZKP MOOC

Interactive Proofs and Arguments▪ Compare soundness to knowledge soundness (last lecture) for
circuit-satisfiability:

ZKP MOOC

Interactive Proofs and Arguments▪ Compare soundness to knowledge soundness (last lecture) for
circuit-satisfiability:

ZKP MOOC

Interactive Proofs and Arguments▪ Compare soundness to knowledge soundness (last lecture) for
circuit-satisfiability:

ZKP MOOC

Interactive Proofs and Arguments▪ Compare soundness to knowledge soundness (last lecture) for
circuit-satisfiability:

ZKP MOOC

Public Verifiability▪ Interactive proofs and arguments only convince the party
that is choosing/sending the random challenges.
▪ This is bad if there are many verifiers (as in mostblockchain applications).
▪ P would have to convince each verifier separately.

▪ For public coin protocols, we have a solution: Fiat-Shamir.
▪ Makes the protocol non-interactive + publicly verifiable.

ZKP MOOCSNARKs from interactive
proofs: outline

ZKP MOOC
Credit: Faithie/ShutterstockRecall: The trivial SNARK is not a SNARK▪

ZKP MOOCSNARKS from Interactive Proofs (IPs)▪

ZKP MOOCSNARKS from Interactive Proofs (IPs)▪

ZKP MOOC

Review of functionalcommitments

ZKP MOOC
Credit: Faithie/ShutterstockRecall: three important functional commitments▪

ZKP MOOC

Recall: three important functional commitments▪

ZKP MOOC

Recall: three important functional commitments▪

ZKP MOOC

Merkle Trees: The Commitment
k1=H(h1, h2)
h1=H(m1, m2)

h2=H(m3, m4)

m1=H(M, Y)

m2 = H(V, E)

m3 =H(C, T)

m4 =H(O, R)

M

VCO

Y

ET

R

ZKP MOOC

Merkle Trees: Opening Leaf T
k1=H(h1, h2)
h1=H(m1, m2)

h2=H(m3, m4)

m1=H(M, Y)

m2 = H(V, E)

m3 =H(C, T)

m4 =H(O, R)

M

VCO

Y

E

T

R

ZKP MOOC

Merkle Trees▪ Commitment to vector is root hash.
▪ To open an entry of the committed vector (leaf of the tree):▪ Send sibling hashes of all nodes on root-to-leaf path.
▪ V checks these are consistent with the root hash.
▪ “Opening proof” size is O(log n) hash values.

Binding: once the root hash is sent, the committer is bound to a
fixed vector:
Opening any leaf to two different values requires finding a hashcollision (assumed to be intractable).

ZKP MOOC

Merkle Trees▪ Commitment to vector is root hash.
▪ To open an entry of the committed vector (leaf of the tree):▪ Send sibling hashes of all nodes on root-to-leaf path.
▪ V checks these are consistent with the root hash.
▪ “Opening proof” size is O(log n) hash values.

▪ Binding: once the root hash is sent, the committer is bound toa fixed vector.
▪ Opening any leaf to two different values requires finding a hashcollision (assumed to be intractable).

ZKP MOOC

k1=H(h1, h2)
h1=H(m1, m2)

h2=H(m3, m4)

ZKP MOOC

k1=H(h1, h2)
h1=H(m1, m2)

h2=H(m3, m4)

ZKP MOOC▪

ZKP MOOC▪

ZKP MOOC

Interactive proof design:
Technical preliminaries

ZKP MOOC
Credit: Faithie/ShutterstockRecap: SZDL Lemma▪

ZKP MOOC

Low-Degree and Multilinear Extensions▪

ZKP MOOC

12810ZKP MOOC

12345681012141618151821242730

222630343842293439444956
ZKP MOOC

123456810121416

181518

21

24

2730

2226

30

34

38

42

29

34

39

44

49

56
ZKP MOOC

123

4

56

8

10

12

14

16

18

13

16

19

22

25

28

16

20

24

28

32

36

17

22

27

32

37

42
ZKP MOOC

Evaluating multilinear extensions quickly▪

ZKP MOOC

Evaluating multilinear extensions quickly▪

ZKP MOOC

Evaluating multilinear extensions quickly▪

ZKP MOOC

Evaluating multilinear extensions quickly▪

ZKP MOOC

The sum-checkprotocol

ZKP MOOC
Credit: Faithie/ShutterstockSum-Check Protocol [LFKN90]▪

ZKP MOOC

Sum-Check Protocol [LFKN90]▪

ZKP MOOC

Sum-Check Protocol [LFKN90]▪

ZKP MOOC

Sum-Check Protocol [LFKN90]▪

ZKP MOOC

Sum-Check Protocol [LFKN90]▪

ZKP MOOC

Sum-Check Protocol [LFKN90]▪

ZKP MOOC

Sum-Check Protocol [LFKN90]▪

ZKP MOOC

Sum-Check Protocol [LFKN90]▪

ZKP MOOC

Sum-Check Protocol [LFKN90]▪

ZKP MOOC

Analysis of thesum-check protocol

ZKP MOOC
Credit: Faithie/ShutterstockCompleteness▪ Completeness holds by design: If P sends theprescribed messages, then all of V’s checks will pass.

ZKP MOOC

Soundness▪

ZKP MOOC

Soundness▪

ZKP MOOC

Soundness▪

ZKP MOOC

Soundness▪

ZKP MOOC

Soundness analysis: wrap-up▪

ZKP MOOC

Costs of the sum-check protocol▪

ZKP MOOC

Costs of the sum-check protocol▪

ZKP MOOC

A first application of thesum-check protocol:
An IP for counting triangles
with linear-time verifier
ZKP MOOC
Credit: Faithie/ShutterstockCosts of the sum-check protocol▪

ZKP MOOC

Counting Triangles▪

ZKP MOOC

Counting Triangles▪

ZKP MOOC

13572468357946810

ZKP MOOC

Counting Triangles▪

ZKP MOOC

Counting Triangles▪

ZKP MOOC

A SNARK forcircuit-satisfiability

ZKP MOOC
Credit: Faithie/ShutterstockRecall: SNARKs for circuit-satisfiability▪

ZKP MOOC

Recall: SNARKs for circuit-satisfiability▪
54110401020

ZKP MOOC▪

ZKP MOOC

The polynomial IOP
underlying the SNARKZKP MOOC
Credit: Faithie/ShutterstockThe start of the polynomial IOP▪

ZKP MOOC

The start of the polynomial IOP▪

ZKP MOOC▪

ZKP MOOC▪

ZKP MOOC▪

ZKP MOOC

Reminder: the start of the polynomial IOP▪

ZKP MOOC

Two-step plan of attack▪

ZKP MOOC

Step 1 of the plan▪

ZKP MOOC

Step 1 of the plan▪

ZKP MOOC

Step 1 of the plan▪

ZKP MOOC

Step 2: A Hint▪

ZKP MOOC

Step 2: A Hint▪

ZKP MOOC

The actual protocol▪

ZKP MOOC

Recall sum-check

ZKP MOOC

92
Credit: Faithie/ShutterstockSum-check protocol: a reminder▪

ZKP MOOC

The polynomial IOP for circuit-satisfiability▪

ZKP MOOC

The polynomial IOP for circuit-satisfiability▪

ZKP MOOC

END OF LECTURE

ZKP MOOC

96
Credit: Faithie/Shutterstock