Zero Knowledge Proofs
ZKP Applications
Instructors: Dan Boneh, Shafi Goldwasser, Dawn Song, Justin Thaler, Yupeng Zhang

ZKP for Machine Learning
ML inference

fair or not?
Credit Risk Criminal Justice Healthcare
PredictionZKP MOOC

Proving ML Inferences using ZKP
Zero-knowledge proof without revealing the ML models✓ Fairness of ML models✓ Integrity of ML inferences
ML inference

ZKP MOOC

Challenges
Efficiency and Scalability of general-purpose SNARKs:
scale to <230 = 1 billion gates (64 GB RAM), prover time minutes to hours

VGG 16 on CIFAR-10
15 million parameters in the model
1.1 billion gates for an inference

4ZKP MOOC

Solution: Special-Purpose ZKPs
Fully connected or convolutional

Activation
Pooling…
5
Fully connected or convolutional

Softmax

ZKP MOOCZKP for Matrix Multiplication [Thaler’13]
𝑎11𝑎21
𝐴=
⋮
𝑎𝑛1

𝑎12
𝑎22

𝑎𝑛2

⋯
…
⋱⋯

𝑎1𝑛𝑎2𝑛⋮𝑎𝑛𝑛

𝐵=Matrix multiplication C = A×B:
𝐶 𝒙, 𝒚 = ෍ 𝐴 𝒙, 𝒛 𝐵(𝒛, 𝒚)𝑏11𝑏21⋮𝑏𝑛1

𝑏12𝑏22

⋯
…
⋱𝑏𝑛2

⋯

𝑏1𝑛𝑏2𝑛⋮𝑏𝑛𝑛

𝑐11
𝑐𝐶 = 21⋮𝑐𝑛1

𝑐12𝑐22𝑐𝑛2⋯…
⋱⋯

𝑐1𝑛𝑐2𝑛⋮𝑐𝑛𝑛

𝑐𝑖𝑗 = σ𝑘 𝑎𝑖𝑘 𝑏𝑘𝑗
𝐶 𝒊, 𝒋 = 𝑐𝑖𝑗 𝐴 𝒊, 𝒌 = 𝑎𝑖𝑘 𝐵 𝒌, 𝒋 = 𝑏𝑘𝑗𝒛•••

Efficient ZKP with prover time O(n2), proof size O(log n)
Faster than computing the result in O(n3)Verifying is easier than computing

6

ZKP MOOCZKP for 2-D Convolutions [LXZ’21]
2-D convolution C = A ∗ B

O(NK) time to compute

7

ZKP MOOC

Computing Convolution using FFT▪

Equivalent to 1-D convolution𝑐 = 𝑎 ∗ 𝑏 = σ𝑖 𝑎𝑖 𝑏𝑁−𝑖▪

Same as polynomial multiplication𝑐 𝑥 = 𝑎 𝑥 ⋅ 𝑏(𝑥)▪

Can be computed by Fast Fourier Transform (FFT)8ZKP MOOCZKP for Fast Fourier Transform𝑎ത = 𝐹 × 𝑎𝑎(𝒙)ത= ෍ 𝐹 𝒙, 𝒚 ⋅ 𝑎(𝒚)1 11 𝜔1 𝜔2
1 𝜔3

𝐹=𝒚1
𝜔2
𝜔4
𝜔61
𝜔3
𝜔6
𝜔9× Size of 𝐹 𝑥, 𝑦 is N2••=1 11 𝜔1 𝜔2
1 𝜔3

1
𝜔2
𝜔1
𝜔2

1
𝜔3
𝜔2
𝜔1

✓ 𝐹 consists of only N
distinct values

An efficient sumcheck protocol with prover time O(N), proof sizeO(log N), verifier time O(log2 N)
Sublinear in the computation time O(NlogN)

9ZKP MOOC

Performance of zkCNN
1 inference

Accuracy on 100 images

Prover time

88 seconds

680 seconds

Proof size

341 KB673 KB

Verifier time

59 ms

121 msVGG16 on CIFAR10 dataset, 15 million parameters (120MB)

10ZKP MOOC

Other Related Works on ZKMLZKDT[ZFZD20], vCNN [LKKO20], ZEN [FQZ+21],
Mystique [WYX+21], pvCNN [WWT+22], [KHSS22], …

11

ZKP MOOCZKP for Program Analysis

12

ZKP MOOC
Credit: Faithie/ShutterstockZero-knowledge Program Analysis
public function: static analysis algorithm

secret program P

safety properties of P

13

ZKP MOOCZero-knowledge Vulnerability Disclosure
public program

secretvulnerability

Running the program
leads to crash

14

ZKP MOOC

Challenges▪ ZKP schemes support circuits.

×▪ Program analysis is usually RAM computation

15××++ZKP MOOC

Solution: Auxiliary Inputs
Ask the prover to provide additional data as the input of ZKP▪ Not trusted▪ Not sent to the verifier▪ Significantly improves the efficiency of ZKP

16

ZKP MOOCExample: worklist algorithm
Program:

CFG:

Worklist:(1, 2)

State:

Line No.

123(x1, x2, x3)(0, 0, 0)(0, 0, 0)

174

5

6

(0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0)

ZKP MOOC

Worklist algorithms: update
Program:

CFG:

Worklist:(1, 2)

State:(2, 3)(2, 4)

Line No.

12(x1, x2, x3)(0, 0, 0)(1, 0, 0)

3

18

4

5

6

(0, 0, 0) (0, 0, 0) (0, 0, 0) (0, 0, 0)

ZKP MOOC

Worklist algorithms: update
Program:

CFG:

Worklist:(1, 2)

State:(2, 3)(2, 4)(3, 6)(4, 5)

Line No.

123(x1, x2, x3)(0, 0, 0)(1, 0, 0)

19

4

5

6

(1, 0, 0) (1, 0, 0) (0, 0, 0) (1, 0, 1)

ZKP MOOC

Auxiliary inputs▪ Prover provides final state of the list▪ Prover provides head and tail of each step
▪ The circuit checks the correctness (offline memory checking[BEGKN’91,Setty’20, …])st20

ZKP MOOC

Performance
Program with T steps and 𝑣 variables
Worklist algorithm: 𝑂(𝑇·𝑣)→ circuit of size 𝑂(𝑇·𝑣+𝑇log𝑇)

21

ZKP MOOC

Related works▪ Static analysis: [FDNZ’21, LAHPTW’22, …]▪ Vulnerabilities: [GHHKPV’22, CHPPT’23, …]

22

ZKP MOOCZKP for Middlebox

23

ZKP MOOC
Credit: Faithie/ShutterstockMiddleboxesMiddleboxes inspect traffic to ensure security policy

24

ZKP MOOC

Encrypted Traffic

25

ZKP MOOC

Zero-Knowledge Middleboxes [GAZBW’22]
ZKP verification✓26

ZKP MOOC

Challenges▪ Work with TLS 1.3▪ Legacy cryptographic functions such as AES, SHA

27

ZKP MOOC

End of Lecture

ZKP MOOC

28
Credit: Faithie/Shutterstock