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
Prover commits to a polynomial f (X)  in  F (X) ▪  eval:  for public u, v ∈ F p ,  prover can convince the verifier that committed poly satisfies f (u) = v   and   deg(f) ≤ d. verifier has  (d, comf, u, v) ◾ Eval proof size and verifier time should be  O λ (log d )
ZKP MOOC

Group   G := { 0,   G,    2 · G,    3 · G ,   ... ,  (p − 1) · G }    of order p. setup(1^) → gp: ◾ Sample random τ E Fn ◾ gp  = ( H 0 = G,  H 1 = τ ⋅ G,  H 2 = τ 2 ⋅ G,  . . . ,  H d = τ α ⋅ G) ∈ Gd+1 ◾ delete  τ !!     (trusted setup) commit(gp, f) →  com f    where    com f  :=  f(τ) · G   ∈ G ◾ ƒ(Х) = ƒo + ƒ1Х + … + ƒaХ đ    ⇒    com f  =  ƒo · Ho + … + ƒa · Ha = f 0 · G + f 1 τ · G + f 2 τ 2 · G + · · · = f ( τ ) · G
ZKP MOOC

Group   G := { 0,   G,    2 · G,    3 · G ,   ... ,  (p − 1) · G }    of order p. setup(1^) → gp: but not hiding ◾ Sample random τ E Fn ◾ gp = (H 0 = G, H 1 = τ ⋅ G, H 2 = τ 2 ⋅ G, … 7 H α ≠ τ ⋅ G) ∈ G 0+1 ◾ delete  τ !!     (trusted setup) commit(gp, f) →  com f    where    com f  :=  f(τ) · G   ∈ G ◾ ƒ(Х) = ƒo + ƒ1Х + … + ƒaХ đ    ⇒    com f  =  ƒo · Ho + … + ƒa · Ha = f 0 · G + f 1 τ · G + f 2 τ 2 · G + · · · = f ( τ ) · G
ZKP MOOC

commit(gp, f) →  com f    where    com f = f(τ) · G    E G eval: Prover(gp, f, u, v) Goal: prove f (u) = v Verifier(gp, comf, u, v) f (u) = v    ⇒   u is a root of  f  := f-v     ⇒    (X-u) divides f ⇒   exists q ∈ F p [X] s.t.  q(X)·(X-u) = f(X)−v compute q(X) and com q =q(τ)·G π := com ∈ G accept if (proof size indep. of deg. d) (τ −u)·com g = comf− v·G
ZKP MOOC

commit(gp, f) →  com f    where    com f = f(τ) · G    E G eval: Prover(gp, f, u, v) Goal:  prove   f (u) = v Verifier(gp, comf, u, v) (τ − u) q(τ) · G ≥ ( f(τ)−ν) · G divides f ⇒ exists g → ** s.t. q(X)·(X-u) = f(X)-v compute q(X) and com q =q(τ)・G π := com ∈ G accept (τ −u) com g = comf− v ·G (proof size indep. of deg. d)
ZKP MOOC

con How to prove that this is a secure PCS?    Not today ... eval: Prover(gp, f, u, v) Goal: prove f (u) = v Verifier(gp, com, u, v) An expensive computation for large d of Verifier does not know τ ⇒ uses a “pairing” (and only needs H o , H 1 from gp) compute q(X) π := com ∈ G accer and com g =q(τ)・G (proof size indep. of deg. d) (τ −u) com g = com f − v ·G
ZKP MOOC

Generalizations: ◾ Can also use KZG to commit to k-variate polynomials   [PST'13] ▪ Batch proofs: ◾ suppose verifier has commitments      com f1 , ... comfn ◾  prover wants to prove   fi(Ui,j) =  vi,j    for  i ∈ [n],  j ∈ [m] ⇒ batch proof π is only one group element！
Two ways to represent a polynomial f (X)  in  F(≤d)[X] : ▪ Coefficient representation:  f (X) =  f 0 + f 1 X + … + f a X d ⇒ computing com f = f 0 · H 0 + … + f a · H a  takes linear time in d ▪ Point-value representation:   (a o , f (a o )), ..., (a a , f (a a )) computing com t naively: construct coefficients  (f 0 , f 1 , …, f a ) ⇒ time  O (d log d)  using Num. Th. Transform (NTT)
Point-value representation:   a better way to compute com , Lagrange interpolation: f (τ) = ∑ i = o λ i (τ) · f (α i ) where ▪ Idea: transform gp into Lagrange form (a linear map) TP = ( Â0 = λ0(τ) · G,   Â1 = λ1(τ) · G,   ...,   Âd = λd(τ) · G) ∈ Gd+1 ▪ Now, com f = f (τ) · G = f (α 0 ) · A 0 + … + f (α α ) · A a ⇒  linear time in d.      (better than 0(d log d) )
Prover has some f (X)  in  F (≤d)[X] .      Let  Ω ⊆ F p  and  |Ω| = d Suppose prover needs evaluation proofs  πα ∈ G  for all  α ∈ Ω ◾ Naively,  takes time  O(d²):   d proofs each takes time O(d) ◾  Feist-Khovratovich (FK) algorithm (2020): ◾ if Ω is a multiplicative subgroup:   time Ο(d log d) ◾ otherwise:  time 0(d log²d)
ZKP MOOC

Difficulties with KZG:   trusted setup for gp, and gp size is linear in d. Dory: ▪  transparent setup:   no secret randomness in setup ◾ coṃis a single group element   (independent of degree d) ◾ eval proof size for f ∈ F(≤d)[X]  is  O(log d)  group elements ◾ eval verify time is | O(log d) | Prover time: | 0 (d)
ZKP MOOC

Example: vector commitment (a drop-in replacement for Merkle trees)

ZKP MOOC
Proving properties of committed polynomials Credit: Esithia Shutterstock
Prover P(f, g) Verifier Goal: convince verifier that f , g ∈ F (≤α ) [X] satisfy some properties Proof systems presented as an IOP: q r query  f (X), g (X), q (X)  at some points in Fn [ V sends x to P who responds with f (x) and eval proof π ] accept or reject
ZKP MOOC

Suppose p ≈ 2²56  and d ≤ 240  so that  d/p is negligible Let  f, g ∈ F(≤d) [X]. For r ÷ F p ,    if   f (r) = g (r)    then    f = g    w.h.p f(r) − g(r) = 0    ⇒    f − g = 0   w.h.p ⇒ a simple equality test for two committed polynomials
ZKP MOOC

Prover f , g ∈ F (≤ d) [ X ] Verifier accept if: f (r) = g(r) ZKP MOOC
ZKP MOOC
For KZG: f = g   ⇒  com f = com a ⇒  verifier can tell if f  = g on its own But prover is needed to test equality of computed polynomials ◾ Example:  verifier has  f  to test if  f  = 919293:  V queries all four poly. at  r ↔ Fp and tests equality ◾ Complete and sound assuming 3d/p is negligible     ( deg(919293) ≤ 3d )
Let Ω be some subset of F p of size k. Let f E [F(≤d)[X] (d ≥ k) Verifier has | f Let us construct efficient Poly-IOPs for the following tasks: Task 1   (ZeroTest): prove that f  is identically zero on Ω Task 2   (SumCheck): prove that   ΣαεΩ f (α) = 0 Task 3   (ProdCheck): prove that   ΠαεΩ f (α) = 1
Let Ω be some subset of F p of size k. Def:  the vanishing polynomial of Ω is   ΖΩ(X) := ΠαεΩ(X − α) deg(Ζゐ) = k Let ω ∈ F p be a primitive k -th root of unity (so that  ω k = 1). ◾ if  Ω = { 1, ω, ω², …, ωk-1 } ⊆ F p   then   Z Ω(X) = Xk − 1 ⇒  for  r ∈ Fp,  evaluating   Zn(r)   takes  ≤2 log 2 k   field operations
ZKP MOOC

Prover P(f) q(X) ← f(X)/Zo(X) X query q(X) and f(X) at  r Verifier V([ £ ]) rそFp verifier evaluates Z Ω ( r ) by itself learn q(r), f(r) accept if  f (r) ≒ q(r) ⋅ Z Ω(r) Lemma:  f  is zero on Ω if and only if f (X) is divisible by Zo(X) (implies that f (X) = q (X) · Z Ω (X) w.h.p) Thm: this protocol is complete and sound, assuming d/p is negligible.
ZKP MOOC

Prover P(f) q(X) ← f(X)/Zo(X) Verifier V(l f rそFp verifier evaluates Z Ω (r) by itself query q(X) and f(X) at  r learn q(r), f(r) accept if  f (r) ≥ q(r) · Z q(r) Verifier time:  O(log k)  and  two poly queries (but can be done in one) Prover time:  dominated by the time to compute q(X) and then commit to q(X)
ZKP MOOC

Set  t ∈ F(≤k) [X]   to be the degree-k polynomial: t(1) = f (1),      t(ωs) = Π i =0 f (ωi)    for  s = 1,...,k − 1 Then t(ω) = f (1) · f (ω),           t(ω²) = f (1) · f (ω) · f (ω²),    ... t(ωk−1) = ΠαεΩf (α) = 1 and t(ω · x) = t(x) · f (ω · x)   for all  x ∈ Ω     (including at x = ω k − 1 )
ZKP MOOC

Set  t ∈ F(≤k) [X]   to be the degree-k polynomial: t(1) = f (1),      t(ωs) = Πξ=0 f (ωi)    for  s = 1,...,k − 1 Lemma:  if    (i)    t(ωk-¹) = 1    and t(ω・x) − t(x)・f(ω・x) = 0    for all  x ∈ Ω (ii) then   ΠαεΩ f (α) = 1
ZKP MOOC

Verifier V(| f | Prover P(f) construct t(X) ∈ F(≤k) and  t 1(X) = t(ω · X) − t(X) · f(ω · X) set  q(X) = t 1 (X)/(Xk − 1)  ∈  F (≤d) t 1 (X) should be zero on Ω t q query t(X) at  ωk-1, r, ωr ,query q(X) at r , and f(X) at ω, a proves that t 1 (Ω) = 0: r & Fp ☞ learn t(ωk-¹), t(r), t(ωr), q(r), f(ωr), accept if   t(ωk-1) ≥ 1   and t(ωr) − t(r)f(ωr) ≥ q(r) · (rk − 1)
ZKP MOOC

Verifier V( Prover P(f) construct t(X) ∈ F(≤k) and  t 1(X) = t(ω · X) − t(X) · f(ω · X) set q(X) = t 1 (X)/(Xk − 1) ∈ F (≤d) t q query t(X) at  ωk-1, r, ωr learn t(ωk-¹), t(r), t(ωr), q(r), f(ωr) ,query q(X) at r , and f(X) at ω , Proof size: two commits, five evals.   Verifier time: 0 (log k).   Prover time: 0 (k log k).
ZKP MOOC

Prover P(f, g) Verifier V(l f Set  t ∈ F n [X]   to be the degree-k polynomial: t(1) = f (1)/g(1),      t(ωs) = Πξ=0 f (ωi)/g(ωi)    for  s = 1,...,k − 1
(ii)
then   ΠαεΩ f (α)/ g (α) = 1
ZKP MOOC

Let  f,g  be polynomials in  F(≤d)[X].      Verifier has  f  ,   g  . Goal:   prover wants to prove that   (f(1),f(ω),f(ω²),...,f(ωk-¹) )  ∈ Fξ is a permutation of ( g(1), g(ω), g(ω²), ..., g(ωk-¹) ) ∈ F k ⇒ Proves that g(Ω) is the same as f (Ω), just permuted
Prover P(f, a) Verifier
r
implies f (X) = g (X) w.h.p accept or reject [two commits, six evals] [Lipton's trick, 1989]
W : Ω → Ω is a permutation of Ω if     Vi ∈ [ k ]:   W (ω i ) = ω i  is a bijection example (k = 3):    W(ω 0) = ω²,   W(ω¹) = ω⁰,    W(ω²) = ω¹ Let f,g be polynomials in  F(≤d)[X].  Verifier has f), g ,W .
W . Goal:   prover wants to prove that   f (y) = g (W (y))    for all   y ∈ Ω ⇒ Proves that g (Ω) is the same as f (Ω), permuted by the prescribed W
ZKP MOOC

How?    Use a zero-test to prove | f (y) − g (W (y)) = 0    on Ω The problem:    the polynomial   f (y) – g (W (y))  has degree  k² ⇒ prover would need to manipulate polynomials of degree k² ⇒ quadratic time prover !!  (goal:  linear time prover) Let's reduce this to a prod-check on a polynomial of degree 2k    (not k 2 )
ZKP MOOC

Observation: if  (W(α), f(α)) a∈Ω   is a permutation of   (α, g(α)) a∈Ω then  f(y) = g(W(y)) for all y ∈ Ω Proof by example:   W(ω 0 ) =  ω² ,   W(ω¹) = ω⁰ ,    W(ω²) = ω¹ Right tuple:       (ω⁰,g(ω⁰)),  (ω¹,g(ω¹)),  (ω²,g(ω²)) Left tuple: (ω² ,f(ω⁰)), (ω⁰ ,f(ω¹)), (ω¹,f(ω²))
Prover P(f, g, W) Verifier
(bivariate polynomials of total degree k) Lemma:  f(X,Y) = g(X,Y)    ⇒    (W(a),f(a)) a∈Ω  is a perm. of To prove, use the fact that Γ , [X, Y] is a unique factorization domain
ZKP MOOC

Prover P(f, g, W) Verifier Vl r, S
prove that f (r,s) = g (r,s): ProdCheck:
by Schwartz- Zippel implies f (X,Y) = g(X,Y) w.h.p Complete and sound,  assuming  2d/p  is negligible. accept or reject
ZKP MOOC

polynomial equality testing zero test on Ω product check,    sum check permutation check prescribed permutation check
ZKP MOOC
The PLONK IOP
eprint/2019/953
polynomial commitment scheme SNARK system ►KZG’10 Aztec, JellyFish Halo2 (slow verifier) (no trusted setup) Plonky2 (no trusted setup) ZKP MOOC
Step 1:   compile circuit to a computation trace   (gate fan-in = 2) The computation trace (arithmetization):
example input left inputs right outputs inputs
ZKP MOOC

|C| := total # of gates in C ,      | | :=  | I x | +  | I w | = # inputs to C let  d := 3 |C| + |I|   (in example, d = 12)   and   Ω := { 1, ω, ω², …, ωα The plan: prover interpolates a polynomial  T ∈  F(≤α)[X] that encodes the entire trace.
Let's see how …
ZKPIMOOC

The plan:   Prover interpolates  T ∈  F (≤d)[X]   such that T encodes all inputs:    T(ω-ʲ) = input #j     for j = 1, …, | I | (1) (2) T encodes all wires:      ∀ l = 0, ..., | C | − 1: ▪ T(ω³¹):     left input to gate #l ◾ T(ω³l+¹):  right input to gate #l ◾ T(ω³l+²):  output of gate #l

ZKP MOOC

In our example, Prover interpolates  T(X)  such that:
degree(T) = 11 Prover can use FFT to compute the coefficients of T in time  O(d log d)

ZKP MOOC

Prover P(S,,, x, w) Verifier V(S,, x) T T(X) E F(≤α) build Prover needs to prove that T is a correct computation trace: (1) T encodes the correct inputs, (2) every gate is evaluated correctly, (3) the wiring is implemented correctly, (4) the output of last gate is 0 Proving (4) is easy:   prove  T(ω³lc|−¹) = 0 (wiring constraints) inputs: 1 Gate 0: Gate 1: Gate 2: 77
ZKPTMOOC

Both prover and verifier interpolate a polynomial v(X) ∈  F(≤|ﾌｪﾛﾝ[X] that encodes the x-inputs to the circuit: for j = 1,…, | Ix |:      v(ω- j ) = input #j In our example: ν(ω− 1 ) = 5, ν(ω− 2 ) = 6.     (ν  is linear) constructing  ν(X)  takes time proportional to the size of input  χ ⇒ verifier has time do this
ZKP MOOC

Both prover and verifier interpolate a polynomial v(X) ∈  F(≤|¹x|)[X] that encodes the x-inputs to the circuit: for j = 1,…, | Ix |:      v(ω- j ) = input #j (points encoding the input) Prover proves (1) by using a ZeroTest on Ω inp to prove that T(y) − ν(y) = 0       ∀ y ∈ Ωjnp
ZKP MOOC

Idea:   encode gate types using a selector polynomial  S(X) define  S(X) ∈  F(≤α)[X]   such that  ∀ l = 0, …, |C| − 1: S(ω³l) = 1   if   gate #l  is an addition gate S(ω 31 ) = 0   if   gate #l  is a multiplication gate
(+) (+) (×)
ZKP MOOC

Idea:   encode gate types using a selector polynomial  S(X) define  S(X) ∈  F p S(ω³¹) = 1   if   gate #l  is an addition gate S(ω³¹) = 0   if   gate #l  is a multiplication gate Then  ∀ y ∈ Ω gates := { 1, ω 3 , ω 6 , ω 9 , ..., ω 3 (| c|−1) } : S(y) [T(y) + T(ῳy)]  +  (1 − S(y)) ·T(γ)·T(ωy)  =  T(ω²y) left input right input left input right input Output
ZKP MOOC

Setup(C) → pp:=S and vp:= ( | S | ) Prover P(pp, x, w) build   T(X) ∈ F(≤q)[X] + T Verifier V( vp, x) Prover uses ZeroTest to prove that for all ∀ y ∈ Ω gates： S(y)·[T(y) + T(ωy)]  +  (1 − S(y))·T(y)·T(ωy)  −  T(ω²y)  =  0
ZKP MOOC

Step 4:   encode the wires of  C: T(ω-²) = T(ω¹) = T(ω³) T(ω-¹) = T(ω⁰) T(ω²) = T(ω 6)
example:  x₁=5, x₂=6, w₁=1 Define a polynomial   W: Ω → Ω   that implements a rotation: W(ω-², ω-1, ω-1) = (ω-1, ω-2) ,    W(ω-1, ω-1) = (ω-1) ,  ... Lemma:  ∀ y∈Ω :   T(y) = T(W(y))  ⇒   wire constraints are satisfied
ZKP MOOC

Step 4:   encode the wires of  C: T(ω-²) = T(ω¹) = T(ω³) example:  x1=5, x2=6, w1=1 ω-¹, ω-², ω-³: 5, 6, 1 T(ω -1 ) = T(ω 0 ) (11 Proved using a prescribed permutation check 1, 7 2:  ω, ω, ω° :(11) 7, 77 Define a polynom à W(ω-², ω¹ , δ $ Ω that implements a rotation: (ω 1 , ω 3 , ω -²) ,   W(ω -1 , ω 0 ) = (ω 0 , ω -1 ) ,  ... Lemma:  ∀ y∈Ω :   T(y) = T(W(y))  ⇒   wire constraints are satisfied
Setup(C) →  pp := (S,W)  and   vp := ( | S | and  |W)   (untrusted)

ZKP MOOC

Setup(C) →    pp := (S,W)   and    vp := ( | S | and Prover P(pp, x, w) Verifier V( vp, x) build   T(X) E F (≤d)[X] build v(X) ∈ F(≤|ιx|) [X] Thm:  The Plonk Poly-IOP is complete and knowledge sound, assuming 7|C|/p is negligible (eprint/2019/953)
ZKP MOOC

◾ Plonk proof:   a short proof  (O(1) commitments),    fast verifier ◾ The SNARK can easily be made into a zk-SNARK Main challenge:   reduce prover time ▪ Hyperplonk:  replace Ω  with  {0,1} t      ( where  t = log 2 | Ω | ) ▪ The polynomial T  is now a multilinear polynomial in t variables ◾ ZeroTest is replaced by a multilinear SumCheck  (linear time)
ZKP MOOC

Plonk for circuits with gates other than +  and  ×  on rows: Plonkish computation trace: (also used in AIR) An example custom gate: ∀ y ∈ Ωgates:   v(yω) + w(y) · t(y) − t(yω) = 0 All such gate checks are included in the gate check Plookup:  ensure some values are in a pre-defined list
output
ZKP MOOC

Next lecture: More polynomial commitments