Polynomial Commitments based on error-correcting codes Instructors: Dan Boneh, Shafi Goldwasser, Dawn Song, Justin Thaler, Yupeng Zhang
A polynomial commitment scheme SNARK for general circuits A polynomial interactive oracle proof (IOP) ZKP MOOC
Univariate polynomials of degree <= d Prover gp = (g, g T, g T², …, g Tà T
Verifier com, el comf / g' , , = e(gt-u,π) - f(u) - u)q(x) ZKP MOOC m
4
Motivations: ✓ Plausibly post-quantum secure ✓ No group exponentiations (prover only uses hashes, additions and multiplications) ✓ Small global parameters Drawbacks: ✖ Large proof size × Not homomorphic and hard to aggregate
5

. Background on error-correcting codes •   Polynomial commitment based on error-correcting codes ▪ Linear-time encodable code based on expanders
ZKP MOOC
6

7
[n, k, Δ] code: ◾ Enc(m): Encode a message of size k to a codeword of size n ◾ Minimum distance (Hamming) between any two codewords is Δ k n
ZKP MOOC
80
Binary with k = 2 and n = 6 ▪  Enc(00) = 00000, Enc(01) = 000111 ◾ Enc(10) = 111000, Enc(11) = 11111 ▪  Minimum distance Δ = 3 Can correct 1 error during the transmission e.g. 010111→ 01    Dec(c): decode algorithm (not used in poly-commit)
ZKP MOOC
9

Rate:一Relative distance: A E.g. repetition code with rate ξ , Δ = α, relative distance:ニTrade-off between the rate and the distance of a code
ZKP MOOC
10

Any linear combination of codewords is also a codeword ⇒ Encoding can always be represented as vector-matrix multiplication between m and the generator matrix ⇒ minimum distance is the same as the codeword with the least number of non-zeros (weight).
ZKP MOOC
11

Encode: Fk → Fn ◾ View the message as a unique degree k-1 univariate polynomial ◾ The codeword is the evaluations at n points E.g., (ω , ω², …, ωʱ) for n-th root-of-unity ωʱ = 1 mod p ▪ Distance Δ = n − k + 1 a degree k-1 polynomial has at most k-1 roots E.g, n  =  2k, rate is 1/2, and relative distance is 1/2 ◾ Encoding time: 0 ( n log n ) using the fast Fourier transform (FFT)
ZKP MOOC
12
Polynomial commitment based on linear codes
keygen(λ, F) → gp Prover
eval(gp,f ,u) → v, π Verifier ZKP MOOC 5

15

f (u) = f (u) =
1+(j-1)√d di=1
ZKP MOOC
16

Argument for Vec-Mat product → Polynomial commitment with √d proof size
ZKP MOOC
17

Encode each row with a linear code
18

ZKP MOOC

ZKP MOOC
Commit to each column of the encoded matrix using Merkle tree ZKP MOOC
21

Test if the committed matrix indeed consists of √d codewords
1. The vector is a codeword 2. Columns are as committed in Merkle tree 3. Inner product between r and each column is consistent Verifier Send several random columns Prover
22

Send several random columns . Probability of passing check 3 is small Prover Suppose the prover cheats ▪ If the vector is correctly computed → it is not a codeword →  check 1 . If the vector is false → many different locations from the correct answer . By check 2, columns are as committed
ZKPIMOOC
23

◾ Ligero [AHIV'2017] : Interleaved test. Reed-Solomon code ◾ [BCGGHJ'2017] : Ideal linear commitment model. Linear-time encodable code → first SNARK with linear prover time
ZKP MOOC
24

If the committed matrix C is e-far from any codeword for e < 2 →Pr[w = r T C is e-close to any codeword] ≤ −−− If w = r T C is e-far from any codeword → Pr[check 3 is true for t random columns] ≤ (1 − −
25

26
Prover 3. Inner product between ữ and each column is consistent ll message m Verifier Send several random columns
27

▪ By the proximity test, the committed matrix C is close to a codeword ◾ There exists an extractor that extracts F by Merkle tree commitment and decoding C, s.t. ẩ × F = m with probability 1 – ε
ZKP MOOC
28

▪ Keygen: sample a hash function ◾ Commit: encode the coefficient matrix of f row-wise with a linear code, compute the Merkle tree commitment ◾ Eval and Verify: ◾ Proximity test: random linear combination of all rows, check its consistency with t random columns ▪ Consistency test: ૌ × F = m, encode m and check its consistency with t random columns ▪ f(u) = ⟨m, u'⟩
29

Keygen: O(1), transparent setup! . Commit: . . Encoding: O(d logd) field multiplications using RS code, O(d) using linear-time encodable code . Merkle tree: O(d) hashes, O(1) commitment size Eval: O(d) field multiplications . (non-interactive via Fiat Shamir) Proof size: O(√d) . Verifier time: O(√d) .
ZKP MOOK
30

degree d = 2²5, linear-time encodable code . Commit: 36s . Eval: 3.2s . Proof size: 49MB •    Verifier time: 0.7s
ZKP MOOC
31

◾ [Bootle-Chiesa-Groth'20]: Tensor query IOP 〈f,   ( u & u ')) ▪ Generalizes to multiple dimensions with proof size O ( n ε ) for constant ε < 1 ◾ Brakedown [GLSTW'21]: polynomial commitment based on tensor query ◾ Knowledge soundness without efficient decoding algorithm
ZKP MOOC
32

▪ [Bootle-Chiesa-Liu'21] ◾ Proof size polylog( n ) with a proof composition of tensor IOP and PCP of proximity [Mie’09] ◾ Orion [Xie-Zhang-Song’22] ◾ Proof size O (log² n) with a proof composition of the code- switching technique [Ron-Zewi-Rothblum'20] (5.7MB for d = 225)
33

Ideal linear model   Tensor IOP 0(d͡) 0(√d) proof size Tensor IOP+PCPP polylog(d) Polynomial Code-switching commitment proof composition 0(d͡) 0(log²d)
ZKP MOOC
35

codeword
36

◾  # left nodes = |L|, # right nodes = α|L| for a constant α ◾ Degree of a left node = g ◾ For every subset S of nodes on the left, # of neighbors |Г(Ｓ)| = g|Ｓ|, for | S | ≤ α | | g
ZKP MOOC
37

◾  # left nodes = |L|, # right nodes = α|L| for a constant α ◾ Degree of a left node = g ◾ For every subset S of nodes on the left, # of neighbors δ | L | |Γ(Տ)| ≥ (1 − β)g|S|, for |S| ≤ = = = (β → 0, δ → α)
ZKP MOOC
38

ZKP MOOC
39

◾ Message m of size k , codeword size 4k , rate is 1/4 ◾ Suppose there is an encoding algorithm from k/2 to 2k with good relative distance  Δ ◾ Suppose there are lossless expander graphs of size k and 2k, and α = 1/2 1. Pass m through lossless expander to get m 1 of size k / 2 Encode m₁ to get c₁ of size 2k 2. Pass c 1 through lossless expander to get c 2 of size k 3. Codeword c = m||c1||c2 4.
ZKP MOOC
40

◾ Repeat for k/2, k/4 ... until a constant size ◾ Use any code with good distance for a constant-size message. E.g., Reed-Solomon code
ZKP MOOC
41

constant relative distance Δ′ = min{Δ, ξ ZKP MOOC
42

◾  # left nodes = k , # right nodes = αk for a constant α ◾ Degree of a left node = g ◾ For every subset S of nodes on the left, # of neighbors δ | L | |Γ(Տ)| ≥ (1 − β)g|S|, for |S| ≤ = = − (β → 0, δ → α)
ZKP MOOC
43

constant relative distance Δ′ = min{Δ, ϕ}, codeword c = m||c1||c2 1. If weight of m is larger than 4kΔ′ →  done 2.   If (weight of m) ≤ 4kΔ′, the condition of lossless expander holds ◾  Let S be the set of nonzero nodes, |Г(S)| ≥ (1 − β)g|S| ◾ At least 1 node in |Γ( S )| have a unique neighbor in S ◾    m₁ is nonzero → (weight of c₁) ≥ 2kΔ 3. If it is larger than 4kΔ′ → done 4. Else, weight of c 2 ≥ 2kΔ′ because of lossless expander
ZKP MOOC
44

◾ [Capalbo-Reingold-Vadhan-Wigderson'2002]: Explicit construction of lossless expander (large hidden constant) ◾ Random sampling: 1/poly(n) failure probability
ZKP MOOC
45

◾ Brakedown [Golovnev-Lee-Setty-Thaler-Wahby’21]: random summations with better concrete distance analysis ▪ Orion [Xie-Zhang-Song'22]: expander testing with a negligible failure probability via maximum density of the graph
ZKP MOOC
46

Polynomial commitment (and SNARK) based on linear code ✓ Transparent setup: 0 (1) ✓ Commit and Prover time: 0 ( d ) field additions and multiplications ✓ Plausibly post-quantum secure ✓ Field agnostic ✖ Proof size: O (√d), MBs
ZKP MOOC
47

Next: FRI and Stark