PH23+KZG10 协议（优化版）协议描述文档：PH23+KZG10 Protocol (Optimized Version)
对于 KZG10 协议，因为其 Commitment 具有加法同态性。
Precomputation ¶ 预计算 s 0 ( X ) , … , s n − 1 ( X ) s_0(X),\ldots, s_{n-1}(X) s 0 ( X ) , … , s n − 1 ( X ) v H ( X ) v_H(X) v H ( X ) v H ( X ) = X N − 1 v_H(X) = X^N -1 v H ( X ) = X N − 1 s i ( X ) = v H ( X ) v H i ( X ) = X N − 1 X 2 i − 1 s_i(X) = \frac{v_H(X)}{v_{H_i}(X)} = \frac{X^N-1}{X^{2^i}-1} s i ( X ) = v H i ( X ) v H ( X ) = X 2 i − 1 X N − 1 预计算 D = ( 1 , ω , ω 2 , … , ω 2 n − 1 ) D=(1, \omega, \omega^2, \ldots, \omega^{2^{n-1}}) D = ( 1 , ω , ω 2 , … , ω 2 n − 1 ) { w ^ i } \{\hat{w}_i\} { w ^ i } w ^ j = ∏ l ≠ j 1 ω 2 j − ω 2 l \hat{w}_j = \prod_{l\neq j} \frac{1}{\omega^{2^j} - \omega^{2^l}} w ^ j = l = j ∏ ω 2 j − ω 2 l 1 预计算 Lagrange Basis 的 KZG10 SRS A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 A_0 =[L_0(\tau)]_1, A_1= [L_1(\tau)]_1, A_2=[L_2(\tau)]_1, \ldots, A_{N-1} = [L_{2^{n-1}}(\tau)]_1 A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 C a = [ f ^ ( τ ) ] 1 C_a=[\hat{f}(\tau)]_1 C a = [ f ^ ( τ ) ] 1 f ~ ( X 0 , X 1 , … , X n − 1 ) \tilde{f}(X_0, X_1, \ldots, X_{n-1}) f ~ ( X 0 , X 1 , … , X n − 1 ) u ⃗ = ( u 0 , u 1 , … , u n − 1 ) \vec{u}=(u_0, u_1, \ldots, u_{n-1}) u = ( u 0 , u 1 , … , u n − 1 ) v = f ~ ( u 0 , u 1 , … , u n − 1 ) v=\tilde{f}(u_0,u_1,\ldots, u_{n-1}) v = f ~ ( u 0 , u 1 , … , u n − 1 ) f ~ \tilde{f} f ~ X ⃗ = u ⃗ \vec{X}=\vec{u} X = u Commit 计算过程 ¶ Prover 构造一元多项式 a ( X ) a(X) a ( X ) a ⃗ = ( a 0 , a 1 , … , a N − 1 ) \vec{a}=(a_0, a_1, \ldots, a_{N-1}) a = ( a 0 , a 1 , … , a N − 1 ) a i = f ~ ( b i t s ( i ) ) a_i = \tilde{f}(\mathsf{bits}(i)) a i = f ~ ( bits ( i )) f ~ \tilde{f} f ~ { 0 , 1 } n \{0,1\}^n { 0 , 1 } n a ( X ) = a 0 ⋅ L 0 ( X ) + a 1 ⋅ L 1 ( X ) + a 2 ⋅ L 2 ( X ) + ⋯ + a N − 1 ⋅ L N − 1 ( X ) a(X) = a_0\cdot L_0(X) + a_1\cdot L_1(X) + a_2\cdot L_2(X) + \cdots + a_{N-1}\cdot L_{N-1}(X) a ( X ) = a 0 ⋅ L 0 ( X ) + a 1 ⋅ L 1 ( X ) + a 2 ⋅ L 2 ( X ) + ⋯ + a N − 1 ⋅ L N − 1 ( X ) Prover: 这一步 Prover 不需要求出系数式，直接用 evaluation form 进行计算，不涉及计算复杂度。
Prover 计算 f ^ ( X ) \hat{f}(X) f ^ ( X ) C a C_a C a C a C_a C a C a = a 0 ⋅ A 0 + a 1 ⋅ A 1 + a 2 ⋅ A 2 + ⋯ + a N − 1 ⋅ A N − 1 = [ f ^ ( τ ) ] 1 C_{a} = a_0\cdot A_0 + a_1\cdot A_1 + a_2\cdot A_2 + \cdots + a_{N-1}\cdot A_{N-1} = [\hat{f}(\tau)]_1 C a = a 0 ⋅ A 0 + a 1 ⋅ A 1 + a 2 ⋅ A 2 + ⋯ + a N − 1 ⋅ A N − 1 = [ f ^ ( τ ) ] 1 其中 A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 A_0 =[L_0(\tau)]_1, A_1= [L_1(\tau)]_1, A_2=[L_2(\tau)]_1, \ldots, A_{N-1} = [L_{2^{n-1}}(\tau)]_1 A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1
Prover: 算法复杂度为 m s m ( N , G 1 ) \mathsf{msm}(N, \mathbb{G}_1) msm ( N , G 1 ) N N N
Commit 阶段复杂度 ¶ 在 commit 阶段 prover 的复杂度总计为：
> m s m ( N , G 1 ) > > \mathsf{msm}(N, \mathbb{G}_1)
> > msm ( N , G 1 ) > Evaluation 证明协议 ¶ 回忆下证明的多项式运算的约束：
f ~ ( u 0 , u 1 , u 2 , … , u n − 1 ) = v \tilde{f}(u_0, u_1, u_2, \ldots, u_{n-1}) = v f ~ ( u 0 , u 1 , u 2 , … , u n − 1 ) = v 这里 u ⃗ = ( u 0 , u 1 , u 2 , … , u n − 1 ) \vec{u}=(u_0, u_1, u_2, \ldots, u_{n-1}) u = ( u 0 , u 1 , u 2 , … , u n − 1 )
Prover Memory ¶ KZG10 SRS : A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 A_0 =[L_0(\tau)]_1, A_1= [L_1(\tau)]_1, A_2=[L_2(\tau)]_1, \ldots, A_{N-1} = [L_{2^{n-1}}(\tau)]_1 A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 Bary-Centric Weights: { w ^ i } \{\hat{w}_i\} { w ^ i } ( [ z H ( x ) ∣ x ∈ g H ] ) − 1 = ( g N − 1 ) − 1 ([z_H(x)|_{x \in gH}])^{-1} = (g^N - 1)^{-1} ([ z H ( x ) ∣ x ∈ g H ] ) − 1 = ( g N − 1 ) − 1 a ⃗ = { a 0 , … , a N − 1 } = [ a ( x ) ∣ x ∈ H ] \vec{a} = \{a_0, \ldots, a_{N-1}\} = [a(x)|_{x \in H}] a = { a 0 , … , a N − 1 } = [ a ( x ) ∣ x ∈ H ] C a = [ f ^ ( τ ) ] 1 C_a=[\hat{f}(\tau)]_1 C a = [ f ^ ( τ ) ] 1 u ⃗ = ( u 0 , u 1 , … , u n − 1 ) \vec{u}=(u_0, u_1, \ldots, u_{n-1}) u = ( u 0 , u 1 , … , u n − 1 ) v = f ~ ( u 0 , u 1 , … , u n − 1 ) v=\tilde{f}(u_0,u_1,\ldots, u_{n-1}) v = f ~ ( u 0 , u 1 , … , u n − 1 ) c ⃗ = { c 0 , … , c N − 1 } \vec{c} = \{c_0, \ldots, c_{N-1}\} c = { c 0 , … , c N − 1 } Round 1. ¶ Prover:
Round 1-1 ¶ 计算向量 c ⃗ \vec{c} c c i = e q ∼ ( b i t s ( i ) , u ⃗ ) c_i=\overset{\sim}{eq}(\mathsf{bits}(i), \vec{u}) c i = e q ∼ ( bits ( i ) , u ) Prover Cost 1-1 ¶ Prover:
向量 c ⃗ \vec{c} c
@classmethod
def eqs_over_hypercube(cls, rs):
k = len(rs)
n = 1 << k
evals = [Field(1)] * n
half = 1
for i in range(k):
for j in range(half):
evals[j+half] = evals[j] * rs[i]
evals[j] = evals[j] - evals[j+half]
half *= 2
return evals例如 k = 2 k = 2 k = 2
> > 00 ( 1 − u 0 ) ( 1 − u 1 ) > 10 u 0 ( 1 − u 1 ) > 01 ( 1 − u 0 ) u 1 > 11 u 0 u 1 > > > \begin{aligned}
> 00 & \quad (1 - u_0) & (1- u_1) \\
> 10 & \quad u_0 & (1- u_1) \\
> 01 & \quad (1 - u_0) & u_1 \\
> 11 & \quad u_0 & u_1
> \end{aligned}
> > > 00 > 10 > 01 > 11 ( 1 − u 0 ) u 0 ( 1 − u 0 ) u 0 ( 1 − u 1 ) ( 1 − u 1 ) u 1 u 1 > > 这个算法就是先按 u 0 u_0 u 0 u 1 u_1 u 1
for j in range(1) 循环内部计算出 evals[1] 和 evals[0]:evals[1] = u 0 u_0 u 0 u 0 u_0 u 0 1evals[0] = 1 − u 0 1 - u_0 1 − u 0 u 0 u_0 u 0 0for j in range(2) ，更新 u 1 u_1 u 1 j = 0，更新 evals[0] 和 evals[2]j = 1，更新 evals[1] 和 evals[3]每次循环 for j in range(half) 内部有 1 次有限域上的乘法，即 evals[j+half] = evals[j] * rs[i] ，而 half 的变化为 1 , 2 , 2 2 , … , 2 k − 1 1, 2, 2^2, \ldots, 2^{k-1} 1 , 2 , 2 2 , … , 2 k − 1
> 1 + 2 + 2 2 + … + 2 k − 1 = 1 ( 1 − 2 k ) 1 − 2 = 2 k − 1 = N − 1 > > 1 + 2 + 2^2 + \ldots + 2^{k - 1} = \frac{1(1 - 2^k)}{1 - 2} = 2^k - 1 = N - 1
> > 1 + 2 + 2 2 + … + 2 k − 1 = 1 − 2 1 ( 1 − 2 k ) = 2 k − 1 = N − 1 > 因此这里的计算复杂度为 ( N − 1 ) F m u l (N - 1) ~ \mathbb{F}_{\mathsf{mul}} ( N − 1 ) F mul
Prover Memory 1-1 ¶ KZG10 SRS : A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 A_0 =[L_0(\tau)]_1, A_1= [L_1(\tau)]_1, A_2=[L_2(\tau)]_1, \ldots, A_{N-1} = [L_{2^{n-1}}(\tau)]_1 A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 Bary-Centric Weights: { w ^ i } \{\hat{w}_i\} { w ^ i } a ⃗ = { a 0 , … , a N − 1 } = [ a ( x ) ∣ x ∈ H ] \vec{a} = \{a_0, \ldots, a_{N-1}\} = [a(x)|_{x \in H}] a = { a 0 , … , a N − 1 } = [ a ( x ) ∣ x ∈ H ] C a = [ f ^ ( τ ) ] 1 C_a=[\hat{f}(\tau)]_1 C a = [ f ^ ( τ ) ] 1 u ⃗ = ( u 0 , u 1 , … , u n − 1 ) \vec{u}=(u_0, u_1, \ldots, u_{n-1}) u = ( u 0 , u 1 , … , u n − 1 ) v = f ~ ( u 0 , u 1 , … , u n − 1 ) v=\tilde{f}(u_0,u_1,\ldots, u_{n-1}) v = f ~ ( u 0 , u 1 , … , u n − 1 ) c ⃗ = { c 0 , … , c N − 1 } \vec{c} = \{c_0, \ldots, c_{N-1}\} c = { c 0 , … , c N − 1 } Round 1-2 ¶ 构造多项式 c ( X ) c(X) c ( X ) H H H c ⃗ \vec{c} c
c ( X ) = ∑ i = 0 N − 1 c i ⋅ L i ( X ) c(X) = \sum_{i=0}^{N-1} c_i \cdot L_i(X) c ( X ) = i = 0 ∑ N − 1 c i ⋅ L i ( X ) Prover Cost 1-2 ¶ Prover: 这一步不需要计算 c ( X ) c(X) c ( X ) c ⃗ \vec{c} c
Round 1-3 ¶ 计算 c ( X ) c(X) c ( X ) C c = [ c ( τ ) ] 1 C_c= [c(\tau)]_1 C c = [ c ( τ ) ] 1 C c C_c C c
C c = K Z G 10. C o m m i t ( c ⃗ ) = [ c ( τ ) ] 1 C_c = \mathsf{KZG10.Commit}(\vec{c}) = [c(\tau)]_1 C c = KZG10.Commit ( c ) = [ c ( τ ) ] 1 Prover Cost 1-3 ¶ C c C_c C c
C c = c 0 ⋅ A 0 + c 1 ⋅ A 1 + … + c N − 1 ⋅ A N − 1 C_c = c_0 \cdot A_0 + c_1 \cdot A_1 + \ldots + c_{N - 1} \cdot A_{N - 1} C c = c 0 ⋅ A 0 + c 1 ⋅ A 1 + … + c N − 1 ⋅ A N − 1 这里算法复杂度为 m s m ( N , G 1 ) \mathsf{msm}(N, \mathbb{G}_1) msm ( N , G 1 )
Prover Cost Round 1 ¶ Prover 复杂度为：
> ( N − 1 ) F m u l + m s m ( N , G 1 ) > > (N - 1) ~ \mathbb{F}_{\mathsf{mul}} + \mathsf{msm}(N, \mathbb{G}_1)
> > ( N − 1 ) F mul + msm ( N , G 1 ) > Prover Memory Round 1 ¶ KZG10 SRS : A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 A_0 =[L_0(\tau)]_1, A_1= [L_1(\tau)]_1, A_2=[L_2(\tau)]_1, \ldots, A_{N-1} = [L_{2^{n-1}}(\tau)]_1 A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 Bary-Centric Weights: { w ^ i } \{\hat{w}_i\} { w ^ i } a ⃗ = { a 0 , … , a N − 1 } = [ a ( x ) ∣ x ∈ H ] \vec{a} = \{a_0, \ldots, a_{N-1}\} = [a(x)|_{x \in H}] a = { a 0 , … , a N − 1 } = [ a ( x ) ∣ x ∈ H ] C a = [ f ^ ( τ ) ] 1 C_a=[\hat{f}(\tau)]_1 C a = [ f ^ ( τ ) ] 1 u ⃗ = ( u 0 , u 1 , … , u n − 1 ) \vec{u}=(u_0, u_1, \ldots, u_{n-1}) u = ( u 0 , u 1 , … , u n − 1 ) v = f ~ ( u 0 , u 1 , … , u n − 1 ) v=\tilde{f}(u_0,u_1,\ldots, u_{n-1}) v = f ~ ( u 0 , u 1 , … , u n − 1 ) c ⃗ = { c 0 , … , c N − 1 } \vec{c} = \{c_0, \ldots, c_{N-1}\} c = { c 0 , … , c N − 1 } Round 2. ¶ Verifier: 发送挑战数 α ← $ F p \alpha\leftarrow_{\$}\mathbb{F}_p α ← $ F p
Prover:
Round 2-1 ¶ 构造关于 c ⃗ \vec{c} c p 0 ( X ) , … , p n ( X ) p_0(X),\ldots, p_{n}(X) p 0 ( X ) , … , p n ( X )
p 0 ( X ) = s 0 ( X ) ⋅ ( c ( X ) − ( 1 − u 0 ) ( 1 − u 1 ) . . . ( 1 − u n − 1 ) ) p k ( X ) = s k − 1 ( X ) ⋅ ( u n − k ⋅ c ( X ) − ( 1 − u n − k ) ⋅ c ( ω 2 n − k ⋅ X ) ) , k = 1 … n \begin{split}
p_0(X) &= s_0(X) \cdot \Big( c(X) - (1-u_0)(1-u_1)...(1-u_{n-1}) \Big) \\
p_k(X) &= s_{k-1}(X) \cdot \Big( u_{n-k}\cdot c(X) - (1-u_{n-k})\cdot c(\omega^{2^{n-k}}\cdot X)\Big) , \quad k=1\ldots n
\end{split} p 0 ( X ) p k ( X ) = s 0 ( X ) ⋅ ( c ( X ) − ( 1 − u 0 ) ( 1 − u 1 ) ... ( 1 − u n − 1 ) ) = s k − 1 ( X ) ⋅ ( u n − k ⋅ c ( X ) − ( 1 − u n − k ) ⋅ c ( ω 2 n − k ⋅ X ) ) , k = 1 … n Prover Cost 2-1 ¶ 📝 笔记 ：先介绍一般如何快速的做有限域上的多项式乘法和除法，不妨设
H ′ = { g 0 , g 1 , … , g 2 N − 1 } = ⟨ g ⟩ H' = \{g^0, g^1, \ldots, g^{2N - 1}\} = \langle g \rangle H ′ = { g 0 , g 1 , … , g 2 N − 1 } = ⟨ g ⟩ 取
> H = ⟨ g 2 ⟩ = ⟨ ω ⟩ = { ω 0 , ω 1 , … , ω N − 1 } > >H = \langle g^2 \rangle = \langle \omega \rangle = \{\omega^0, \omega^1, \ldots, \omega^{N - 1} \}
> > H = ⟨ g 2 ⟩ = ⟨ ω ⟩ = { ω 0 , ω 1 , … , ω N − 1 } > 则
> g H = { g ω 0 , g ω 1 , … , g ω N − 1 } = { g 1 , g 3 , … , g 2 N − 1 } > >gH = \{g\omega^0, g\omega^1, \ldots, g\omega^{N - 1} \} =\{ g^1, g^3, \ldots, g^{2N - 1} \}
> > g H = { g ω 0 , g ω 1 , … , g ω N − 1 } = { g 1 , g 3 , … , g 2 N − 1 } > 若要计算
> a ( X ) = a 1 + a 2 X + … + a N − 1 X N − 1 > >a(X) = a_1 + a_2 X + \ldots + a_{N - 1}X^{N - 1}
> > a ( X ) = a 1 + a 2 X + … + a N − 1 X N − 1 > 与
> b ( X ) = b 1 + b 2 X + … + b N − 1 X N − 1 > >b(X) = b_1 + b_2 X + \ldots + b_{N - 1}X^{N - 1}
> > b ( X ) = b 1 + b 2 X + … + b N − 1 X N − 1 > 的乘积多项式 c ( X ) = a ( X ) ⋅ b ( X ) c(X) = a(X)\cdot b(X) c ( X ) = a ( X ) ⋅ b ( X ) a ( X ) a(X) a ( X ) b ( X ) b(X) b ( X ) H H H
[ a ( x ) ∣ x ∈ H ] , [ b ( x ) ∣ x ∈ H ] [a(x)|_{x \in H}], \quad [b(x)|_{x \in H}] [ a ( x ) ∣ x ∈ H ] , [ b ( x ) ∣ x ∈ H ] 我们想要计算的是商多项式
> q ( X ) = a ( X ) ⋅ b ( X ) z H ( X ) > >q(X) = \frac{a(X) \cdot b(X)}{z_H(X)}
> > q ( X ) = z H ( X ) a ( X ) ⋅ b ( X ) > 由于 deg ( q ) < N \deg(q) < N deg ( q ) < N q ( X ) q(X) q ( X ) z H ( X ) z_H(X) z H ( X ) H H H
> [ ( a ( x ) ⋅ b ( x ) ) ∣ x ∈ g H ] , [ z H ( x ) ∣ x ∈ g H ] > >[(a(x) \cdot b(x))|_{x \in gH}], \quad [z_H(x)|_{x \in gH}]
> > [( a ( x ) ⋅ b ( x )) ∣ x ∈ g H ] , [ z H ( x ) ∣ x ∈ g H ] > 再对位相除计算出 [ q ( x ) ∣ x ∈ g H ] [q(x)|_{x \in gH}] [ q ( x ) ∣ x ∈ g H ]
计算得到 [ a ( x ) ) ∣ x ∈ g H ] [a(x))|_{x \in gH}] [ a ( x )) ∣ x ∈ g H ] [ a ( x ) ∣ x ∈ H ] [a(x)|_{x \in H}] [ a ( x ) ∣ x ∈ H ] a ( X ) a(X) a ( X ) g H gH g H N log N F m u l N \log N ~ \mathbb{F}_{\mathsf{mul}} N log N F mul F F T ( N ) + I F F T ( N ) \mathsf{FFT}(N) + \mathsf{IFFT}(N) FFT ( N ) + IFFT ( N ) 计算得到 [ b ( x ) ) ∣ x ∈ g H ] [b(x))|_{x \in gH}] [ b ( x )) ∣ x ∈ g H ] [ b ( x ) ∣ x ∈ H ] [b(x)|_{x \in H}] [ b ( x ) ∣ x ∈ H ] b ( X ) b(X) b ( X ) g H gH g H F F T ( N ) + I F F T ( N ) \mathsf{FFT}(N) + \mathsf{IFFT}(N) FFT ( N ) + IFFT ( N ) N log N F m u l N \log N ~ \mathbb{F}_{\mathsf{mul}} N log N F mul 先计算 [ ( a ( x ) ⋅ b ( x ) ) ∣ x ∈ g H ] [(a(x) \cdot b(x))|_{x \in gH}] [( a ( x ) ⋅ b ( x )) ∣ x ∈ g H ] N N N N F m u l N ~ \mathbb{F}_{\mathsf{mul}} N F mul 计算 [ z H ( x ) ∣ x ∈ g H ] [z_H(x)|_{x \in gH}] [ z H ( x ) ∣ x ∈ g H ] z H ( X ) = X N − 1 z_H(X) = X^N - 1 z H ( X ) = X N − 1 z H ( x ) = z H ( g ω i ) = ( g ω i ) N − 1 = g N ⋅ ( ω N ) i − 1 = g N − 1 z_H(x) = z_H(g\omega^i) = (g\omega^i)^N - 1 = g^N \cdot (\omega^N)^i - 1 = g^N - 1 z H ( x ) = z H ( g ω i ) = ( g ω i ) N − 1 = g N ⋅ ( ω N ) i − 1 = g N − 1 z H ( X ) z_H(X) z H ( X ) g H gH g H ( g N − 1 ) − 1 (g^N - 1)^{-1} ( g N − 1 ) − 1 计算 [ q ( x ) ∣ x ∈ g H ] [q(x)|_{x \in gH}] [ q ( x ) ∣ x ∈ g H ] [ ( a ( x ) ⋅ b ( x ) ) ∣ x ∈ g H ] [(a(x) \cdot b(x))|_{x \in gH}] [( a ( x ) ⋅ b ( x )) ∣ x ∈ g H ] ( g N − 1 ) − 1 (g^N - 1)^{-1} ( g N − 1 ) − 1 [ q ( x ) ∣ x ∈ g H ] [q(x)|_{x \in gH}] [ q ( x ) ∣ x ∈ g H ] N F m u l N ~ \mathbb{F}_{\mathsf{mul}} N F mul 因此整体计算除法的复杂度为
> 2 F F T ( N ) + 2 I F F T ( N ) + 2 N F m u l > > 2~ \mathsf{FFT}(N) + 2~\mathsf{IFFT}(N) + 2N ~ \mathbb{F}_{\mathsf{mul}}
> > 2 FFT ( N ) + 2 IFFT ( N ) + 2 N F mul > 现在分析算法复杂度。Prover 要计算出 [ p i ( x ) ∣ x ∈ g H ] [p_i(x)|_{x \in gH}] [ p i ( x ) ∣ x ∈ g H ]
prover 计算 [ s 0 ( x ) ∣ x ∈ g H ] , [ s 1 ( x ) ∣ x ∈ g H ] , … , [ s n − 1 ( x ) ∣ x ∈ g H ] [s_0(x)|_{x \in gH}], [s_1(x)|_{x \in gH}], \ldots, [s_{n - 1}(x)|_{x \in gH}] [ s 0 ( x ) ∣ x ∈ g H ] , [ s 1 ( x ) ∣ x ∈ g H ] , … , [ s n − 1 ( x ) ∣ x ∈ g H ] O ( n ) O(n) O ( n ) s 0 ( x ) , … , s n − 1 ( x ) s_0(x), \ldots, s_{n - 1}(x) s 0 ( x ) , … , s n − 1 ( x ) ( n − 1 ) F m u l (n - 1) ~ \mathbb{F}_{\mathsf{mul}} ( n − 1 ) F mul ∣ g H ∣ = N |gH| = N ∣ g H ∣ = N g H gH g H ( n − 1 ) N F m u l (n - 1)N ~ \mathbb{F}_{\mathsf{mul}} ( n − 1 ) N F mul 计算得到 [ c ( x ) ∣ x ∈ g H ] [c(x)|_{x \in gH}] [ c ( x ) ∣ x ∈ g H ] [ c ( x ) ∣ x ∈ H ] [c(x)|_{x \in H}] [ c ( x ) ∣ x ∈ H ] g H gH g H F F T ( N ) + I F F T ( N ) \mathsf{FFT}(N) + \mathsf{IFFT}(N) FFT ( N ) + IFFT ( N ) 计算 [ ( c ( x ) − ( 1 − u 0 ) ( 1 − u 1 ) … ( 1 − u n − 1 ) ) ∣ x ∈ g H ] [(c(x) - (1 - u_0)(1 - u_1) \ldots (1 - u_{n - 1}))|_{x \in gH}] [( c ( x ) − ( 1 − u 0 ) ( 1 − u 1 ) … ( 1 − u n − 1 )) ∣ x ∈ g H ] ( 1 − u 0 ) ( 1 − u 1 ) … ( 1 − u n − 1 ) (1 - u_0)(1 - u_1) \ldots (1 - u_{n - 1}) ( 1 − u 0 ) ( 1 − u 1 ) … ( 1 − u n − 1 ) c 0 c_0 c 0 计算 [ p 0 ( x ) ∣ x ∈ g H ] [p_0(x)|_{x \in gH}] [ p 0 ( x ) ∣ x ∈ g H ] N N N N F m u l N ~ \mathbb{F}_{\mathsf{mul}} N F mul 对于 k = 1 , … , n k = 1, \ldots, n k = 1 , … , n [ ( u n − k ⋅ c ( x ) − ( 1 − u n − k ) ⋅ c ( ω 2 n − k ⋅ x ) ) ∣ x ∈ g H ] [( u_{n-k}\cdot c(x) - (1-u_{n-k})\cdot c(\omega^{2^{n-k}}\cdot x))|_{x \in gH}] [( u n − k ⋅ c ( x ) − ( 1 − u n − k ) ⋅ c ( ω 2 n − k ⋅ x )) ∣ x ∈ g H ] k k k x ∈ g H x \in gH x ∈ g H k k k 2 n N F m u l 2nN ~ \mathbb{F}_{\mathsf{mul}} 2 n N F mul 对于 k = 1 , … , n k = 1, \ldots, n k = 1 , … , n [ p k ( x ) ∣ x ∈ g H ] [p_k(x)|_{x \in gH}] [ p k ( x ) ∣ x ∈ g H ] k k k N N N n N F m u l nN ~ \mathbb{F}_{\mathsf{mul}} n N F mul 总结下这一步的总复杂度为
( n − 1 ) N F m u l + F F T ( N ) + I F F T ( N ) + N F m u l + 3 n N F m u l = F F T ( N ) + I F F T ( N ) + 4 n N F m u l \begin{aligned}
& (n - 1)N ~ \mathbb{F}_{\mathsf{mul}} + \mathsf{FFT}(N) + \mathsf{IFFT}(N) + N ~ \mathbb{F}_{\mathsf{mul}} + 3nN ~ \mathbb{F}_{\mathsf{mul}} \\
= & \mathsf{FFT}(N) + \mathsf{IFFT}(N) + 4nN ~ \mathbb{F}_{\mathsf{mul}}
\end{aligned} = ( n − 1 ) N F mul + FFT ( N ) + IFFT ( N ) + N F mul + 3 n N F mul FFT ( N ) + IFFT ( N ) + 4 n N F mul Prover Memory 2-1 ¶ KZG10 SRS : A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 A_0 =[L_0(\tau)]_1, A_1= [L_1(\tau)]_1, A_2=[L_2(\tau)]_1, \ldots, A_{N-1} = [L_{2^{n-1}}(\tau)]_1 A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 Bary-Centric Weights: { w ^ i } \{\hat{w}_i\} { w ^ i } a ⃗ = { a 0 , … , a N − 1 } = [ a ( x ) ∣ x ∈ H ] \vec{a} = \{a_0, \ldots, a_{N-1}\} = [a(x)|_{x \in H}] a = { a 0 , … , a N − 1 } = [ a ( x ) ∣ x ∈ H ] C a = [ f ^ ( τ ) ] 1 C_a=[\hat{f}(\tau)]_1 C a = [ f ^ ( τ ) ] 1 u ⃗ = ( u 0 , u 1 , … , u n − 1 ) \vec{u}=(u_0, u_1, \ldots, u_{n-1}) u = ( u 0 , u 1 , … , u n − 1 ) v = f ~ ( u 0 , u 1 , … , u n − 1 ) v=\tilde{f}(u_0,u_1,\ldots, u_{n-1}) v = f ~ ( u 0 , u 1 , … , u n − 1 ) c ⃗ = { c 0 , … , c N − 1 } = [ c ( x ) ∣ x ∈ H ] \vec{c} = \{c_0, \ldots, c_{N-1}\} = [c(x)|_{x \in H}] c = { c 0 , … , c N − 1 } = [ c ( x ) ∣ x ∈ H ] c ( X ) c(X) c ( X ) [ c ( x ) ∣ x ∈ g H ] [c(x)|_{x \in gH}] [ c ( x ) ∣ x ∈ g H ] { [ p k ( x ) ∣ x ∈ g H ] } k = 0 n \{[p_k(x)|_{x \in gH}]\}_{k = 0}^n {[ p k ( x ) ∣ x ∈ g H ] } k = 0 n Round 2-2 ¶ 把 { p i ( X ) } \{p_i(X)\} { p i ( X )} p ( X ) p(X) p ( X )
p ( X ) = p 0 ( X ) + α ⋅ p 1 ( X ) + α 2 ⋅ p 2 ( X ) + ⋯ + α n ⋅ p n ( X ) p(X) = p_0(X) + \alpha\cdot p_1(X) + \alpha^2\cdot p_2(X) + \cdots + \alpha^{n}\cdot p_{n}(X) p ( X ) = p 0 ( X ) + α ⋅ p 1 ( X ) + α 2 ⋅ p 2 ( X ) + ⋯ + α n ⋅ p n ( X ) Prover Cost 2-2 ¶ 这一步其实算的并不是多项式的系数，而是中间计算出 [ p ( x ) ∣ x ∈ g H ] [p(x)|_{x \in gH}] [ p ( x ) ∣ x ∈ g H ]
prover 由 α \alpha α α 2 , α 3 , … , α n \alpha^2, \alpha^3, \ldots, \alpha^n α 2 , α 3 , … , α n n − 1 n - 1 n − 1 ( n − 1 ) F m u l (n - 1) ~ \mathbb{F}_{\mathsf{mul}} ( n − 1 ) F mul 对每一个 x ∈ g H x \in gH x ∈ g H p ( x ) = p 0 ( x ) + α ⋅ p 1 ( x ) + α 2 ⋅ p 2 ( x ) + ⋯ + α n ⋅ p n ( x ) p(x) = p_0(x) + \alpha\cdot p_1(x) + \alpha^2\cdot p_2(x) + \cdots + \alpha^{n}\cdot p_{n}(x) p ( x ) = p 0 ( x ) + α ⋅ p 1 ( x ) + α 2 ⋅ p 2 ( x ) + ⋯ + α n ⋅ p n ( x ) 涉及有限域乘法为 n n n ∣ g H ∣ = N |gH| = N ∣ g H ∣ = N x x x n N F m u l nN ~ \mathbb{F}_{\mathsf{mul}} n N F mul
总结下这一步的复杂度为
( n N + n − 1 ) F m u l (nN + n - 1) ~ \mathbb{F}_{\mathsf{mul}} ( n N + n − 1 ) F mul Prover Memory 2-2 ¶ KZG10 SRS : A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 A_0 =[L_0(\tau)]_1, A_1= [L_1(\tau)]_1, A_2=[L_2(\tau)]_1, \ldots, A_{N-1} = [L_{2^{n-1}}(\tau)]_1 A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 Bary-Centric Weights: { w ^ i } \{\hat{w}_i\} { w ^ i } a ⃗ = { a 0 , … , a N − 1 } = [ a ( x ) ∣ x ∈ H ] \vec{a} = \{a_0, \ldots, a_{N-1}\} = [a(x)|_{x \in H}] a = { a 0 , … , a N − 1 } = [ a ( x ) ∣ x ∈ H ] C a = [ f ^ ( τ ) ] 1 C_a=[\hat{f}(\tau)]_1 C a = [ f ^ ( τ ) ] 1 u ⃗ = ( u 0 , u 1 , … , u n − 1 ) \vec{u}=(u_0, u_1, \ldots, u_{n-1}) u = ( u 0 , u 1 , … , u n − 1 ) v = f ~ ( u 0 , u 1 , … , u n − 1 ) v=\tilde{f}(u_0,u_1,\ldots, u_{n-1}) v = f ~ ( u 0 , u 1 , … , u n − 1 ) c ⃗ = { c 0 , … , c N − 1 } = [ c ( x ) ∣ x ∈ H ] \vec{c} = \{c_0, \ldots, c_{N-1}\} = [c(x)|_{x \in H}] c = { c 0 , … , c N − 1 } = [ c ( x ) ∣ x ∈ H ] [ c ( x ) ∣ x ∈ g H ] [c(x)|_{x \in gH}] [ c ( x ) ∣ x ∈ g H ] [ p ( x ) ∣ x ∈ g H ] [p(x)|_{x \in gH}] [ p ( x ) ∣ x ∈ g H ] Round 2-3 ¶ 构造累加多项式 z ( X ) z(X) z ( X )
z ( 1 ) = a 0 ⋅ c 0 z ( ω i ) − z ( ω i − 1 ) = a ( ω i ) ⋅ c ( ω i ) , i = 1 , … , N − 1 z ( ω N − 1 ) = v \begin{split}
z(1) &= a_0\cdot c_0 \\
z(\omega_{i}) - z(\omega_{i-1}) &= a(\omega_{i})\cdot c(\omega_{i}), \quad i=1,\ldots, N-1 \\
z(\omega^{N-1}) &= v \\
\end{split} z ( 1 ) z ( ω i ) − z ( ω i − 1 ) z ( ω N − 1 ) = a 0 ⋅ c 0 = a ( ω i ) ⋅ c ( ω i ) , i = 1 , … , N − 1 = v Prover Cost 2-3 ¶ 前面已经得到了 [ a ( x ) ∣ x ∈ H ] [a(x)|_{x \in H}] [ a ( x ) ∣ x ∈ H ] [ c ( x ) ∣ x ∈ H ] [c(x)|_{x \in H}] [ c ( x ) ∣ x ∈ H ] [ z ( x ) ∣ x ∈ H ] [z(x)|_{x \in H}] [ z ( x ) ∣ x ∈ H ]
z ( 1 ) = a 0 ⋅ c 0 z ( ω 1 ) = z ( 1 ) + a ( ω 1 ) ⋅ c ( ω 1 ) ⋯ z ( ω N − 1 ) = z ( ω N − 2 ) + a ( ω N − 1 ) ⋅ c ( ω N − 1 ) z ( ω N − 1 ) = v \begin{aligned}
& z(1) = a_0 \cdot c_0 \\
& z(\omega_1) = z(1) + a(\omega_1) \cdot c(\omega_1) \\
& \cdots \\
& z(\omega_{N - 1}) = z(\omega_{N - 2}) + a(\omega_{N - 1}) \cdot c(\omega_{N - 1}) \\
& z(\omega^{N - 1}) = v
\end{aligned} z ( 1 ) = a 0 ⋅ c 0 z ( ω 1 ) = z ( 1 ) + a ( ω 1 ) ⋅ c ( ω 1 ) ⋯ z ( ω N − 1 ) = z ( ω N − 2 ) + a ( ω N − 1 ) ⋅ c ( ω N − 1 ) z ( ω N − 1 ) = v 涉及的复杂度为 N F m u l N ~ \mathbb{F}_{\mathsf{mul}} N F mul
Prover Memory 2-3 ¶ KZG10 SRS : A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 A_0 =[L_0(\tau)]_1, A_1= [L_1(\tau)]_1, A_2=[L_2(\tau)]_1, \ldots, A_{N-1} = [L_{2^{n-1}}(\tau)]_1 A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 Bary-Centric Weights: { w ^ i } \{\hat{w}_i\} { w ^ i } ( [ z H ( x ) ∣ x ∈ g H ] ) − 1 = ( g N − 1 ) − 1 ([z_H(x)|_{x \in gH}])^{-1} = (g^N - 1)^{-1} ([ z H ( x ) ∣ x ∈ g H ] ) − 1 = ( g N − 1 ) − 1 [ L 0 ( x ) ∣ x ∈ g H ] [L_0(x)|_{x \in gH}] [ L 0 ( x ) ∣ x ∈ g H ] [ L N − 1 ( x ) ∣ x ∈ g H ] [L_{N - 1}(x)|_{x \in gH}] [ L N − 1 ( x ) ∣ x ∈ g H ] a ⃗ = { a 0 , … , a N − 1 } = [ a ( x ) ∣ x ∈ H ] \vec{a} = \{a_0, \ldots, a_{N-1}\} = [a(x)|_{x \in H}] a = { a 0 , … , a N − 1 } = [ a ( x ) ∣ x ∈ H ] C a = [ f ^ ( τ ) ] 1 C_a=[\hat{f}(\tau)]_1 C a = [ f ^ ( τ ) ] 1 u ⃗ = ( u 0 , u 1 , … , u n − 1 ) \vec{u}=(u_0, u_1, \ldots, u_{n-1}) u = ( u 0 , u 1 , … , u n − 1 ) v = f ~ ( u 0 , u 1 , … , u n − 1 ) v=\tilde{f}(u_0,u_1,\ldots, u_{n-1}) v = f ~ ( u 0 , u 1 , … , u n − 1 ) c ⃗ = { c 0 , … , c N − 1 } = [ c ( x ) ∣ x ∈ H ] \vec{c} = \{c_0, \ldots, c_{N-1}\} = [c(x)|_{x \in H}] c = { c 0 , … , c N − 1 } = [ c ( x ) ∣ x ∈ H ] [ c ( x ) ∣ x ∈ g H ] [c(x)|_{x \in gH}] [ c ( x ) ∣ x ∈ g H ] [ p ( x ) ∣ x ∈ g H ] [p(x)|_{x \in gH}] [ p ( x ) ∣ x ∈ g H ] [ z ( x ) ∣ x ∈ H ] [z(x)|_{x \in H}] [ z ( x ) ∣ x ∈ H ] Round 2-4 ¶ 构造约束多项式 h 0 ( X ) , h 1 ( X ) , h 2 ( X ) h_0(X), h_1(X), h_2(X) h 0 ( X ) , h 1 ( X ) , h 2 ( X )
h 0 ( X ) = L 0 ( X ) ⋅ ( z ( X ) − c 0 ⋅ a ( X ) ) h 1 ( X ) = ( X − 1 ) ⋅ ( z ( X ) − z ( ω − 1 ⋅ X ) − a ( X ) ⋅ c ( X ) ) h 2 ( X ) = L N − 1 ( X ) ⋅ ( z ( X ) − v ) \begin{split}
h_0(X) &= L_0(X)\cdot\big(z(X) - c_0\cdot a(X) \big) \\
h_1(X) &= (X-1)\cdot\big(z(X)-z(\omega^{-1}\cdot X)-a(X)\cdot c(X)) \\
h_2(X) & = L_{N-1}(X)\cdot\big( z(X) - v \big) \\
\end{split} h 0 ( X ) h 1 ( X ) h 2 ( X ) = L 0 ( X ) ⋅ ( z ( X ) − c 0 ⋅ a ( X ) ) = ( X − 1 ) ⋅ ( z ( X ) − z ( ω − 1 ⋅ X ) − a ( X ) ⋅ c ( X )) = L N − 1 ( X ) ⋅ ( z ( X ) − v ) Prover Cost 2-4 ¶ 要计算出 [ h 0 ( x ) ∣ x ∈ g H ] , [ h 1 ( x ) ∣ x ∈ g H ] , [ h 2 ( x ) ∣ x ∈ g H ] [h_0(x)|_{x \in gH}], [h_1(x)|_{x \in gH}], [h_2(x)|_{x \in gH}] [ h 0 ( x ) ∣ x ∈ g H ] , [ h 1 ( x ) ∣ x ∈ g H ] , [ h 2 ( x ) ∣ x ∈ g H ]
先计算出 [ z ( x ) ∣ x ∈ g H ] [z(x)|_{x \in gH}] [ z ( x ) ∣ x ∈ g H ] F F T ( N ) + I F F T ( N ) \mathsf{FFT}(N) + \mathsf{IFFT}(N) FFT ( N ) + IFFT ( N ) 计算出 [ a ( x ) ∣ x ∈ g H ] [a(x)|_{x \in gH}] [ a ( x ) ∣ x ∈ g H ] F F T ( N ) + I F F T ( N ) \mathsf{FFT}(N) + \mathsf{IFFT}(N) FFT ( N ) + IFFT ( N ) 计算出 [ h 0 ( x ) ∣ x ∈ g H ] [h_0(x)|_{x \in gH}] [ h 0 ( x ) ∣ x ∈ g H ] 2 N F m u l 2N ~ \mathbb{F}_{\mathsf{mul}} 2 N F mul 计算出 [ ( a ( x ) ⋅ c ( x ) ) ∣ x ∈ g H ] [(a(x) \cdot c(x))|_{x \in gH}] [( a ( x ) ⋅ c ( x )) ∣ x ∈ g H ] N F m u l N ~ \mathbb{F}_{\mathsf{mul}} N F mul 计算出 [ h 1 ( x ) ∣ x ∈ g H ] [h_1(x)|_{x \in gH}] [ h 1 ( x ) ∣ x ∈ g H ] N F m u l N ~ \mathbb{F}_{\mathsf{mul}} N F mul 计算出 [ h 2 ( x ) ∣ x ∈ g H ] [h_2(x)|_{x \in gH}] [ h 2 ( x ) ∣ x ∈ g H ] N F m u l N ~ \mathbb{F}_{\mathsf{mul}} N F mul 2 F F T ( N ) + 2 I F F T ( N ) + 5 N F m u l 2~ \mathsf{FFT}(N) + 2~ \mathsf{IFFT}(N) + 5N ~ \mathbb{F}_{\mathsf{mul}} 2 FFT ( N ) + 2 IFFT ( N ) + 5 N F mul Prover Memory 2-4 ¶ 这一轮增加 [ h 0 ( x ) ∣ x ∈ g H ] , [ h 1 ( x ) ∣ x ∈ g H ] , [ h 2 ( x ) ∣ x ∈ g H ] [h_0(x)|_{x \in gH}], [h_1(x)|_{x \in gH}], [h_2(x)|_{x \in gH}] [ h 0 ( x ) ∣ x ∈ g H ] , [ h 1 ( x ) ∣ x ∈ g H ] , [ h 2 ( x ) ∣ x ∈ g H ]
KZG10 SRS : A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 A_0 =[L_0(\tau)]_1, A_1= [L_1(\tau)]_1, A_2=[L_2(\tau)]_1, \ldots, A_{N-1} = [L_{2^{n-1}}(\tau)]_1 A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 Bary-Centric Weights: { w ^ i } \{\hat{w}_i\} { w ^ i } ( [ z H ( x ) ∣ x ∈ g H ] ) − 1 = ( g N − 1 ) − 1 ([z_H(x)|_{x \in gH}])^{-1} = (g^N - 1)^{-1} ([ z H ( x ) ∣ x ∈ g H ] ) − 1 = ( g N − 1 ) − 1 [ L 0 ( x ) ∣ x ∈ g H ] [L_0(x)|_{x \in gH}] [ L 0 ( x ) ∣ x ∈ g H ] [ L N − 1 ( x ) ∣ x ∈ g H ] [L_{N - 1}(x)|_{x \in gH}] [ L N − 1 ( x ) ∣ x ∈ g H ] a ⃗ = { a 0 , … , a N − 1 } = [ a ( x ) ∣ x ∈ H ] \vec{a} = \{a_0, \ldots, a_{N-1}\} = [a(x)|_{x \in H}] a = { a 0 , … , a N − 1 } = [ a ( x ) ∣ x ∈ H ] C a = [ f ^ ( τ ) ] 1 C_a=[\hat{f}(\tau)]_1 C a = [ f ^ ( τ ) ] 1 u ⃗ = ( u 0 , u 1 , … , u n − 1 ) \vec{u}=(u_0, u_1, \ldots, u_{n-1}) u = ( u 0 , u 1 , … , u n − 1 ) v = f ~ ( u 0 , u 1 , … , u n − 1 ) v=\tilde{f}(u_0,u_1,\ldots, u_{n-1}) v = f ~ ( u 0 , u 1 , … , u n − 1 ) c ⃗ = { c 0 , … , c N − 1 } = [ c ( x ) ∣ x ∈ H ] \vec{c} = \{c_0, \ldots, c_{N-1}\} = [c(x)|_{x \in H}] c = { c 0 , … , c N − 1 } = [ c ( x ) ∣ x ∈ H ] [ c ( x ) ∣ x ∈ g H ] [c(x)|_{x \in gH}] [ c ( x ) ∣ x ∈ g H ] [ p ( x ) ∣ x ∈ g H ] [p(x)|_{x \in gH}] [ p ( x ) ∣ x ∈ g H ] [ z ( x ) ∣ x ∈ H ] [z(x)|_{x \in H}] [ z ( x ) ∣ x ∈ H ] z ( X ) z(X) z ( X ) [ h 0 ( x ) ∣ x ∈ g H ] , [ h 1 ( x ) ∣ x ∈ g H ] , [ h 2 ( x ) ∣ x ∈ g H ] [h_0(x)|_{x \in gH}], [h_1(x)|_{x \in gH}], [h_2(x)|_{x \in gH}] [ h 0 ( x ) ∣ x ∈ g H ] , [ h 1 ( x ) ∣ x ∈ g H ] , [ h 2 ( x ) ∣ x ∈ g H ] Round 2-5 ¶ 把 p ( X ) p(X) p ( X ) h 0 ( X ) , h 1 ( X ) , h 2 ( X ) h_0(X), h_1(X), h_2(X) h 0 ( X ) , h 1 ( X ) , h 2 ( X ) h ( X ) h(X) h ( X )
h ( X ) = p ( X ) + α n + 1 ⋅ h 0 ( X ) + α n + 2 ⋅ h 1 ( X ) + α n + 3 ⋅ h 2 ( X ) \begin{split}
h(X) &= p(X) + \alpha^{n+1} \cdot h_0(X) + \alpha^{n+2} \cdot h_1(X) + \alpha^{n+3} \cdot h_2(X)
\end{split} h ( X ) = p ( X ) + α n + 1 ⋅ h 0 ( X ) + α n + 2 ⋅ h 1 ( X ) + α n + 3 ⋅ h 2 ( X ) Prover Cost 2-5 ¶ 这一轮计算 [ h ( x ) x ∈ g H ] [h(x)_{x \in gH}] [ h ( x ) x ∈ g H ]
在这一轮中的前面第 2 步已经计算出 α 2 , … , α n \alpha^2, \ldots, \alpha^n α 2 , … , α n α n + 1 , α n + 2 , α n + 3 \alpha^{n + 1}, \alpha^{n + 2} , \alpha^{n + 3} α n + 1 , α n + 2 , α n + 3 3 F m u l 3 ~ \mathbb{F}_{\mathsf{mul}} 3 F mul 计算 [ h ( x ) ∣ g H ] [h(x)|_{gH}] [ h ( x ) ∣ g H ] 3 N F m u l 3N ~ \mathbb{F}_{\mathsf{mul}} 3 N F mul ( 3 N + 3 ) F m u l (3N + 3) ~ \mathbb{F}_{\mathsf{mul}} ( 3 N + 3 ) F mul Prover Memory 2-5 ¶ KZG10 SRS : A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 A_0 =[L_0(\tau)]_1, A_1= [L_1(\tau)]_1, A_2=[L_2(\tau)]_1, \ldots, A_{N-1} = [L_{2^{n-1}}(\tau)]_1 A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 Bary-Centric Weights: { w ^ i } \{\hat{w}_i\} { w ^ i } ( [ v H ( x ) ∣ x ∈ g H ] ) − 1 = ( g N − 1 ) − 1 ([v_H(x)|_{x \in gH}])^{-1} = (g^N - 1)^{-1} ([ v H ( x ) ∣ x ∈ g H ] ) − 1 = ( g N − 1 ) − 1 [ L 0 ( x ) ∣ x ∈ g H ] [L_0(x)|_{x \in gH}] [ L 0 ( x ) ∣ x ∈ g H ] [ L N − 1 ( x ) ∣ x ∈ g H ] [L_{N - 1}(x)|_{x \in gH}] [ L N − 1 ( x ) ∣ x ∈ g H ] a ⃗ = { a 0 , … , a N − 1 } = [ a ( x ) ∣ x ∈ H ] \vec{a} = \{a_0, \ldots, a_{N-1}\} = [a(x)|_{x \in H}] a = { a 0 , … , a N − 1 } = [ a ( x ) ∣ x ∈ H ] C a = [ f ^ ( τ ) ] 1 C_a=[\hat{f}(\tau)]_1 C a = [ f ^ ( τ ) ] 1 u ⃗ = ( u 0 , u 1 , … , u n − 1 ) \vec{u}=(u_0, u_1, \ldots, u_{n-1}) u = ( u 0 , u 1 , … , u n − 1 ) v = f ~ ( u 0 , u 1 , … , u n − 1 ) v=\tilde{f}(u_0,u_1,\ldots, u_{n-1}) v = f ~ ( u 0 , u 1 , … , u n − 1 ) c ⃗ = { c 0 , … , c N − 1 } = [ c ( x ) ∣ x ∈ H ] \vec{c} = \{c_0, \ldots, c_{N-1}\} = [c(x)|_{x \in H}] c = { c 0 , … , c N − 1 } = [ c ( x ) ∣ x ∈ H ] [ c ( x ) ∣ x ∈ g H ] [c(x)|_{x \in gH}] [ c ( x ) ∣ x ∈ g H ] [ p ( x ) ∣ x ∈ g H ] [p(x)|_{x \in gH}] [ p ( x ) ∣ x ∈ g H ] [ z ( x ) ∣ x ∈ H ] [z(x)|_{x \in H}] [ z ( x ) ∣ x ∈ H ] [ h 0 ( x ) ∣ x ∈ g H ] , [ h 1 ( x ) ∣ x ∈ g H ] , [ h 2 ( x ) ∣ x ∈ g H ] [h_0(x)|_{x \in gH}], [h_1(x)|_{x \in gH}], [h_2(x)|_{x \in gH}] [ h 0 ( x ) ∣ x ∈ g H ] , [ h 1 ( x ) ∣ x ∈ g H ] , [ h 2 ( x ) ∣ x ∈ g H ] [ h ( x ) ∣ x ∈ g H ] [h(x)|_{x \in gH}] [ h ( x ) ∣ x ∈ g H ] Round 2-6 ¶ 计算 Quotient 多项式 t ( X ) t(X) t ( X )
h ( X ) = t ( X ) ⋅ v H ( X ) h(X) =t(X)\cdot v_H(X) h ( X ) = t ( X ) ⋅ v H ( X ) Prover Cost 2-6 ¶ 计算出 [ t ( x ) ∣ x ∈ g H ] [t(x)|_{x \in gH}] [ t ( x ) ∣ x ∈ g H ] ∀ x ∈ g H \forall x \in gH ∀ x ∈ g H
t ( x ) = h ( x ) ⋅ ( v H ( x ) ) − 1 = h ( x ) ⋅ ( g N − 1 ) − 1 t(x) = h(x) \cdot (v_H(x))^{-1} = h(x) \cdot (g^N - 1)^{-1} t ( x ) = h ( x ) ⋅ ( v H ( x ) ) − 1 = h ( x ) ⋅ ( g N − 1 ) − 1 复杂度为 N F m u l N ~ \mathbb{F}_{\mathsf{mul}} N F mul
Prover Memory 2-6 ¶ KZG10 SRS : A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 A_0 =[L_0(\tau)]_1, A_1= [L_1(\tau)]_1, A_2=[L_2(\tau)]_1, \ldots, A_{N-1} = [L_{2^{n-1}}(\tau)]_1 A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 Bary-Centric Weights: { w ^ i } \{\hat{w}_i\} { w ^ i } ( [ v H ( x ) ∣ x ∈ g H ] ) − 1 = ( g N − 1 ) − 1 ([v_H(x)|_{x \in gH}])^{-1} = (g^N - 1)^{-1} ([ v H ( x ) ∣ x ∈ g H ] ) − 1 = ( g N − 1 ) − 1 [ L 0 ( x ) ∣ x ∈ g H ] [L_0(x)|_{x \in gH}] [ L 0 ( x ) ∣ x ∈ g H ] [ L N − 1 ( x ) ∣ x ∈ g H ] [L_{N - 1}(x)|_{x \in gH}] [ L N − 1 ( x ) ∣ x ∈ g H ] a ⃗ = { a 0 , … , a N − 1 } = [ a ( x ) ∣ x ∈ H ] \vec{a} = \{a_0, \ldots, a_{N-1}\} = [a(x)|_{x \in H}] a = { a 0 , … , a N − 1 } = [ a ( x ) ∣ x ∈ H ] C a = [ f ^ ( τ ) ] 1 C_a=[\hat{f}(\tau)]_1 C a = [ f ^ ( τ ) ] 1 u ⃗ = ( u 0 , u 1 , … , u n − 1 ) \vec{u}=(u_0, u_1, \ldots, u_{n-1}) u = ( u 0 , u 1 , … , u n − 1 ) v = f ~ ( u 0 , u 1 , … , u n − 1 ) v=\tilde{f}(u_0,u_1,\ldots, u_{n-1}) v = f ~ ( u 0 , u 1 , … , u n − 1 ) c ⃗ = { c 0 , … , c N − 1 } = [ c ( x ) ∣ x ∈ H ] \vec{c} = \{c_0, \ldots, c_{N-1}\} = [c(x)|_{x \in H}] c = { c 0 , … , c N − 1 } = [ c ( x ) ∣ x ∈ H ] [ c ( x ) ∣ x ∈ g H ] [c(x)|_{x \in gH}] [ c ( x ) ∣ x ∈ g H ] [ p ( x ) ∣ x ∈ g H ] [p(x)|_{x \in gH}] [ p ( x ) ∣ x ∈ g H ] [ z ( x ) ∣ x ∈ H ] [z(x)|_{x \in H}] [ z ( x ) ∣ x ∈ H ] [ t ( x ) ∣ x ∈ g H ] [t(x)|_{x \in gH}] [ t ( x ) ∣ x ∈ g H ] Round 2-7 ¶ 计算 C t = [ t ( τ ) ] 1 C_t=[t(\tau)]_1 C t = [ t ( τ ) ] 1 C z = [ z ( τ ) ] 1 C_z=[z(\tau)]_1 C z = [ z ( τ ) ] 1 C t C_t C t C z C_z C z
C t = K Z G 10. C o m m i t ( t ( X ) ) = [ t ( τ ) ] 1 C z = K Z G 10. C o m m i t ( z ( X ) ) = [ z ( τ ) ] 1 \begin{split}
C_t &= \mathsf{KZG10.Commit}(t(X)) = [t(\tau)]_1 \\
C_z &= \mathsf{KZG10.Commit}(z(X)) = [z(\tau)]_1
\end{split} C t C z = KZG10.Commit ( t ( X )) = [ t ( τ ) ] 1 = KZG10.Commit ( z ( X )) = [ z ( τ ) ] 1 Prover Cost 2-7 ¶ 计算 C t C_t C t
通过 [ t ( x ) ∣ x ∈ g H ] [t(x)|_{x \in gH}] [ t ( x ) ∣ x ∈ g H ] [ t ( x ) ∣ x ∈ H ] [t(x)|_{x \in H}] [ t ( x ) ∣ x ∈ H ] F F T ( N ) + I F F T ( N ) \mathsf{FFT}(N) + \mathsf{IFFT}(N) FFT ( N ) + IFFT ( N ) 计算 C t = t 0 A 0 + … + t N − 1 A N − 1 C_t = t_0 A_0 + \ldots + t_{N - 1}A_{N - 1} C t = t 0 A 0 + … + t N − 1 A N − 1 复杂度为 m s m ( N , G 1 ) \mathsf{msm}(N, \mathbb{G}_1) msm ( N , G 1 )
计算 C z C_z C z m s m ( N , G 1 ) \mathsf{msm}(N, \mathbb{G}_1) msm ( N , G 1 )
因此这一步的总复杂度为
F F T ( N ) + I F F T ( N ) + 2 m s m ( N , G 1 ) \mathsf{FFT}(N) + \mathsf{IFFT}(N) + 2 ~ \mathsf{msm}(N, \mathbb{G}_1) FFT ( N ) + IFFT ( N ) + 2 msm ( N , G 1 ) 💡 Option
如果在不考虑内存的情况下，内存中可以提前存好另一组 KZG10 的 SRS，B 0 = [ L 0 ′ ( τ ) ] 1 , B 1 = [ L 1 ′ ( τ ) ] 1 , B 2 = [ L 2 ′ ( τ ) ] 1 , … , B N − 1 = [ L 2 n − 1 ′ ( τ ) ] 1 B_0 =[L'_0(\tau)]_1, B_1= [L'_1(\tau)]_1, B_2=[L'_2(\tau)]_1, \ldots, B_{N-1} = [L'_{2^{n} - 1}(\tau)]_1 B 0 = [ L 0 ′ ( τ ) ] 1 , B 1 = [ L 1 ′ ( τ ) ] 1 , B 2 = [ L 2 ′ ( τ ) ] 1 , … , B N − 1 = [ L 2 n − 1 ′ ( τ ) ] 1 L 0 ′ , … , L N − 1 ′ L_0', \ldots, L_{N - 1}' L 0 ′ , … , L N − 1 ′ g H gH g H
计算 C t C_t C t
C t = t 0 B 0 + … + t N − 1 B N − 1 C_t = t_0 B_0 + \ldots + t_{N - 1}B_{N - 1} C t = t 0 B 0 + … + t N − 1 B N − 1 其中 [ t 0 , … , t N − 1 ] [t_0, \ldots, t_{N-1}] [ t 0 , … , t N − 1 ] [ t ( x ) ∣ x ∈ g H ] [t(x)|_{x \in gH}] [ t ( x ) ∣ x ∈ g H ] m s m ( N , G 1 ) \mathsf{msm}(N, \mathbb{G}_1) msm ( N , G 1 )
计算 C z C_z C z m s m ( N , G 1 ) \mathsf{msm}(N, \mathbb{G}_1) msm ( N , G 1 )
总复杂度为
2 m s m ( N , G 1 ) 2 ~ \mathsf{msm}(N, \mathbb{G}_1) 2 msm ( N , G 1 ) 这种方案会少一次 FFT 和一次 IFFT，节省 N log N F m u l N \log N ~ \mathbb{F}_{\mathsf{mul}} N log N F mul
Prover Cost Round 2 ¶ 汇总上面所有步骤的 Prover 计算复杂度
F F T ( N ) + I F F T ( N ) + 4 n N F m u l + ( n N + n − 1 ) F m u l + N F m u l + 2 F F T ( N ) + 2 I F F T ( N ) + 5 N F m u l + ( 3 N + 3 ) F m u l + N F m u l + F F T ( N ) + I F F T ( N ) + 2 m s m ( N , G 1 ) = 4 F F T ( N ) + 4 I F F T ( N ) + ( 5 n N + 10 N + n + 2 ) F m u l + 2 m s m ( N , G 1 ) \begin{aligned}
& \mathsf{FFT}(N) + \mathsf{IFFT}(N) + 4nN ~ \mathbb{F}_{\mathsf{mul}} + (nN + n - 1) ~ \mathbb{F}_{\mathsf{mul}} + N ~ \mathbb{F}_{\mathsf{mul}} + 2~ \mathsf{FFT}(N) + 2~ \mathsf{IFFT}(N) + 5N ~ \mathbb{F}_{\mathsf{mul}} \\
& + (3N + 3) ~ \mathbb{F}_{\mathsf{mul}} + N ~ \mathbb{F}_{\mathsf{mul}} + \mathsf{FFT}(N) + \mathsf{IFFT}(N) + 2 ~ \mathsf{msm}(N, \mathbb{G}_1) \\
= & 4 ~ \mathsf{FFT}(N) + 4 ~ \mathsf{IFFT}(N) + (5nN + 10N + n + 2) ~ \mathbb{F}_{\mathsf{mul}} + 2 ~ \mathsf{msm}(N, \mathbb{G}_1)
\end{aligned} = FFT ( N ) + IFFT ( N ) + 4 n N F mul + ( n N + n − 1 ) F mul + N F mul + 2 FFT ( N ) + 2 IFFT ( N ) + 5 N F mul + ( 3 N + 3 ) F mul + N F mul + FFT ( N ) + IFFT ( N ) + 2 msm ( N , G 1 ) 4 FFT ( N ) + 4 IFFT ( N ) + ( 5 n N + 10 N + n + 2 ) F mul + 2 msm ( N , G 1 ) Round 3. ¶ Verifier: 发送随机求值点 ζ ← $ F p \zeta\leftarrow_{\$}\mathbb{F}_p ζ ← $ F p
Prover:
Round 3-1 ¶ 计算 s i ( X ) s_i(X) s i ( X ) ζ \zeta ζ s 0 ( ζ ) , s 1 ( ζ ) , … , s n − 1 ( ζ ) s_0(\zeta), s_1(\zeta), \ldots, s_{n-1}(\zeta) s 0 ( ζ ) , s 1 ( ζ ) , … , s n − 1 ( ζ ) Prover Cost 3-1 ¶ 这里 Prover 可以高效计算 s i ( ζ ) s_i(\zeta) s i ( ζ ) s i ( X ) s_i(X) s i ( X )
s i ( ζ ) = ζ N − 1 ζ 2 i − 1 = ( ζ N − 1 ) ( ζ 2 i + 1 ) ( ζ 2 i − 1 ) ( ζ 2 i + 1 ) = ζ N − 1 ζ 2 i + 1 − 1 ⋅ ( ζ 2 i + 1 ) = s i + 1 ( ζ ) ⋅ ( ζ 2 i + 1 ) \begin{aligned}
s_i(\zeta) & = \frac{\zeta^N - 1}{\zeta^{2^i} - 1} \\
& = \frac{(\zeta^N - 1)(\zeta^{2^i} +1)}{(\zeta^{2^i} - 1)(\zeta^{2^i} +1)} \\
& = \frac{\zeta^N - 1}{\zeta^{2^{i + 1}} - 1} \cdot (\zeta^{2^i} +1) \\
& = s_{i + 1}(\zeta) \cdot (\zeta^{2^i} +1)
\end{aligned} s i ( ζ ) = ζ 2 i − 1 ζ N − 1 = ( ζ 2 i − 1 ) ( ζ 2 i + 1 ) ( ζ N − 1 ) ( ζ 2 i + 1 ) = ζ 2 i + 1 − 1 ζ N − 1 ⋅ ( ζ 2 i + 1 ) = s i + 1 ( ζ ) ⋅ ( ζ 2 i + 1 ) 因此 s i ( ζ ) s_i(\zeta) s i ( ζ ) s i + 1 ( ζ ) s_{i + 1}(\zeta) s i + 1 ( ζ )
s n − 1 ( ζ ) = ζ N − 1 ζ 2 n − 1 − 1 = ζ 2 n − 1 + 1 s_{n-1}(\zeta) = \frac{\zeta^N - 1}{\zeta^{2^{n-1}} - 1} = \zeta^{2^{n-1}} + 1 s n − 1 ( ζ ) = ζ 2 n − 1 − 1 ζ N − 1 = ζ 2 n − 1 + 1 因此可以得到一个 O ( n ) O(n) O ( n ) s i ( ζ ) s_i(\zeta) s i ( ζ ) s n − 1 ( ζ ) → s n − 2 ( ζ ) → ⋯ → s 0 ( ζ ) s_{n-1}(\zeta) \rightarrow s_{n-2}(\zeta) \rightarrow \cdots \rightarrow s_0(\zeta) s n − 1 ( ζ ) → s n − 2 ( ζ ) → ⋯ → s 0 ( ζ )
可以先由随机数 ζ \zeta ζ ζ 2 , ζ 4 , … , ζ 2 n − 1 \zeta^2, \zeta^4, \ldots, \zeta^{2^{n - 1}} ζ 2 , ζ 4 , … , ζ 2 n − 1 ζ 2 = ζ × ζ \zeta^2 = \zeta \times \zeta ζ 2 = ζ × ζ ζ 4 = ζ 2 × ζ 2 \zeta^4 = \zeta^2 \times \zeta^2 ζ 4 = ζ 2 × ζ 2 n − 1 n - 1 n − 1 ( n − 1 ) F m u l (n - 1) ~ \mathbb{F}_{\mathsf{mul}} ( n − 1 ) F mul 计算得到 s n − 1 ( ζ ) = ζ 2 n − 1 + 1 s_{n-1}(\zeta) = \zeta^{2^{n-1}} + 1 s n − 1 ( ζ ) = ζ 2 n − 1 + 1 计算 s i ( ζ ) ( i = 0 , … , n − 2 ) s_{i}(\zeta) (i = 0, \ldots, n - 2) s i ( ζ ) ( i = 0 , … , n − 2 ) s i ( ζ ) = s i + 1 ( ζ ) ⋅ ( ζ 2 i + 1 ) s_{i}(\zeta) = s_{i + 1}(\zeta) \cdot (\zeta^{2^i} +1) s i ( ζ ) = s i + 1 ( ζ ) ⋅ ( ζ 2 i + 1 ) F m u l \mathbb{F}_{\mathsf{mul}} F mul i = 0 , … , n − 2 i = 0, \ldots, n - 2 i = 0 , … , n − 2 ( n − 1 ) F m u l (n - 1) ~ \mathbb{F}_{\mathsf{mul}} ( n − 1 ) F mul 因此总共的复杂度为
> ( n − 1 ) F m u l + ( n − 1 ) F m u l = 2 ( n − 1 ) F m u l > > (n - 1) ~ \mathbb{F}_{\mathsf{mul}} + (n - 1) ~ \mathbb{F}_{\mathsf{mul}} = 2(n - 1) ~ \mathbb{F}_{\mathsf{mul}}
> > ( n − 1 ) F mul + ( n − 1 ) F mul = 2 ( n − 1 ) F mul > Round 3-2 ¶ 定义求值 Domain D ′ D' D ′ n + 1 n+1 n + 1
D ′ = D ζ = { ζ , ω ζ , ω 2 ζ , ω 4 ζ , … , ω 2 n − 1 ζ } D'=D\zeta = \{\zeta, \omega\zeta, \omega^2\zeta,\omega^4\zeta, \ldots, \omega^{2^{n-1}}\zeta\} D ′ = D ζ = { ζ , ω ζ , ω 2 ζ , ω 4 ζ , … , ω 2 n − 1 ζ } Round 3-3 ¶ 计算并发送 c ( X ) c(X) c ( X ) D ′ D' D ′
c ( ζ ) , c ( ζ ⋅ ω ) , c ( ζ ⋅ ω 2 ) , c ( ζ ⋅ ω 4 ) , … , c ( ζ ⋅ ω 2 n − 1 ) c(\zeta), c(\zeta\cdot\omega), c(\zeta\cdot\omega^2), c(\zeta\cdot\omega^4), \ldots, c(\zeta\cdot\omega^{2^{n-1}}) c ( ζ ) , c ( ζ ⋅ ω ) , c ( ζ ⋅ ω 2 ) , c ( ζ ⋅ ω 4 ) , … , c ( ζ ⋅ ω 2 n − 1 ) Prover Cost 3-3 ¶ 这里 ( 1 , ω , ω 2 , … , ω 2 n − 1 ) (1, \omega, \omega^2, \ldots, \omega^{2^{n - 1}}) ( 1 , ω , ω 2 , … , ω 2 n − 1 ) ( ζ , ζ ⋅ ω , ζ ⋅ ω 2 , … , ζ ⋅ ω 2 n − 1 ) (\zeta, \zeta \cdot \omega, \zeta \cdot \omega^2, \ldots, \zeta \cdot \omega^{2^{n - 1}}) ( ζ , ζ ⋅ ω , ζ ⋅ ω 2 , … , ζ ⋅ ω 2 n − 1 ) n n n n F m u l n ~\mathbb{F}_{\mathsf{mul}} n F mul 计算 [ c ( x ) ∣ x ∈ D ′ ] [c(x)|_{x \in D'}] [ c ( x ) ∣ x ∈ D ′ ] c ( X ) c(X) c ( X ) N N N D ′ ⊂ D ( 2 ) D' \subset D^{(2)} D ′ ⊂ D ( 2 ) [ c ( x ) ∣ x ∈ D ( 2 ) ] [c(x)|_{x \in D^{(2)}}] [ c ( x ) ∣ x ∈ D ( 2 ) ] ∣ D ′ ∣ = n , ∣ D ( 2 ) ∣ = N |D'| = n, |D^{(2)}| = N ∣ D ′ ∣ = n , ∣ D ( 2 ) ∣ = N [ c ( x ) ∣ x ∈ D ′ ] [c(x)|_{x \in D'}] [ c ( x ) ∣ x ∈ D ′ ] F F T ( N ) \mathsf{FFT}(N) FFT ( N ) 💡 这里由于多算了很多值，本来只需要在 D ′ D' D ′ D ( 2 ) D^{(2)} D ( 2 )
这一步的复杂度为
n F m u l + F F T ( N ) n ~\mathbb{F}_{\mathsf{mul}} + \mathsf{FFT}(N) n F mul + FFT ( N ) Round 3-4 ¶ 计算并发送 z ( ω − 1 ⋅ ζ ) z(\omega^{-1}\cdot\zeta) z ( ω − 1 ⋅ ζ )
Prover Cost 3-4 ¶ 在 Round 2-4 已经计算出 z ( X ) z(X) z ( X ) z ( X ) z(X) z ( X )
Prover:
计算 ω − 1 ⋅ ζ \omega^{-1}\cdot\zeta ω − 1 ⋅ ζ F m u l \mathbb{F}_{\mathsf{mul}} F mul z ( ω − 1 ⋅ ζ ) z(\omega^{-1}\cdot\zeta) z ( ω − 1 ⋅ ζ ) N F m u l N ~\mathbb{F}_{\mathsf{mul}} N F mul
> ( N + 1 ) F m u l > > (N + 1) ~ \mathbb{F}_{\mathsf{mul}}
> > ( N + 1 ) F mul > Prover Memory 3-4 ¶ KZG10 SRS : A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 A_0 =[L_0(\tau)]_1, A_1= [L_1(\tau)]_1, A_2=[L_2(\tau)]_1, \ldots, A_{N-1} = [L_{2^{n-1}}(\tau)]_1 A 0 = [ L 0 ( τ ) ] 1 , A 1 = [ L 1 ( τ ) ] 1 , A 2 = [ L 2 ( τ ) ] 1 , … , A N − 1 = [ L 2 n − 1 ( τ ) ] 1 Bary-Centric Weights: { w ^ i } \{\hat{w}_i\} { w ^ i } ( [ v H ( x ) ∣ x ∈ g H ] ) − 1 = ( g N − 1 ) − 1 ([v_H(x)|_{x \in gH}])^{-1} = (g^N - 1)^{-1} ([ v H ( x ) ∣ x ∈ g H ] ) − 1 = ( g N − 1 ) − 1 [ L 0 ( x ) ∣ x ∈ g H ] [L_0(x)|_{x \in gH}] [ L 0 ( x ) ∣ x ∈ g H ] [ L N − 1 ( x ) ∣ x ∈ g H ] [L_{N - 1}(x)|_{x \in gH}] [ L N − 1 ( x ) ∣ x ∈ g H ] L 0 ( X ) L_0(X) L 0 ( X ) L N − 1 ( X ) L_{N - 1}(X) L N − 1 ( X ) ω − 1 \omega^{-1} ω − 1 a ⃗ = { a 0 , … , a N − 1 } = [ a ( x ) ∣ x ∈ H ] \vec{a} = \{a_0, \ldots, a_{N-1}\} = [a(x)|_{x \in H}] a = { a 0 , … , a N − 1 } = [ a ( x ) ∣ x ∈ H ] C a = [ f ^ ( τ ) ] 1 C_a=[\hat{f}(\tau)]_1 C a = [ f ^ ( τ ) ] 1 u ⃗ = ( u 0 , u 1 , … , u n − 1 ) \vec{u}=(u_0, u_1, \ldots, u_{n-1}) u = ( u 0 , u 1 , … , u n − 1 ) v = f ~ ( u 0 , u 1 , … , u n − 1 ) v=\tilde{f}(u_0,u_1,\ldots, u_{n-1}) v = f ~ ( u 0 , u 1 , … , u n − 1 ) c ⃗ = { c 0 , … , c N − 1 } = [ c ( x ) ∣ x ∈ H ] \vec{c} = \{c_0, \ldots, c_{N-1}\} = [c(x)|_{x \in H}] c = { c 0 , … , c N − 1 } = [ c ( x ) ∣ x ∈ H ] [ c ( x ) ∣ x ∈ g H ] [c(x)|_{x \in gH}] [ c ( x ) ∣ x ∈ g H ] [ p ( x ) ∣ x ∈ g H ] [p(x)|_{x \in gH}] [ p ( x ) ∣ x ∈ g H ] [ z ( x ) ∣ x ∈ H ] [z(x)|_{x \in H}] [ z ( x ) ∣ x ∈ H ] [ z ( x ) ∣ x ∈ g H ] [z(x)|_{x \in gH}] [ z ( x ) ∣ x ∈ g H ] [ t ( x ) ∣ x ∈ g H ] [t(x)|_{x \in gH}] [ t ( x ) ∣ x ∈ g H ] c ( X ) c(X) c ( X ) z ( X ) z(X) z ( X ) c ( ζ ) , c ( ζ ⋅ ω ) , c ( ζ ⋅ ω 2 ) , c ( ζ ⋅ ω 4 ) , … , c ( ζ ⋅ ω 2 n − 1 ) c(\zeta), c(\zeta\cdot\omega), c(\zeta\cdot\omega^2), c(\zeta\cdot\omega^4), \ldots, c(\zeta\cdot\omega^{2^{n-1}}) c ( ζ ) , c ( ζ ⋅ ω ) , c ( ζ ⋅ ω 2 ) , c ( ζ ⋅ ω 4 ) , … , c ( ζ ⋅ ω 2 n − 1 ) s 0 ( ζ ) , s 1 ( ζ ) , … , s n − 1 ( ζ ) s_0(\zeta), s_1(\zeta), \ldots, s_{n-1}(\zeta) s 0 ( ζ ) , s 1 ( ζ ) , … , s n − 1 ( ζ ) z ( ω − 1 ⋅ ζ ) z(\omega^{-1}\cdot\zeta) z ( ω − 1 ⋅ ζ ) α , α 2 , … , α n + 3 \alpha, \alpha^2, \ldots, \alpha^{n + 3} α , α 2 , … , α n + 3 Round 3-5 ¶ 计算 Linearized Polynomial l ζ ( X ) l_\zeta(X) l ζ ( X )
l ζ ( X ) = ( s 0 ( ζ ) ⋅ ( c ( ζ ) − c 0 ) + α ⋅ s 0 ( ζ ) ⋅ ( u n − 1 ⋅ c ( ζ ) − ( 1 − u n − 1 ) ⋅ c ( ω 2 n − 1 ⋅ ζ ) ) + α 2 ⋅ s 1 ( ζ ) ⋅ ( u n − 2 ⋅ c ( ζ ) − ( 1 − u n − 2 ) ⋅ c ( ω 2 n − 2 ⋅ ζ ) ) + ⋯ + α n − 1 ⋅ s n − 2 ( ζ ) ⋅ ( u 1 ⋅ c ( ζ ) − ( 1 − u 1 ) ⋅ c ( ω 2 ⋅ ζ ) ) + α n ⋅ s n − 1 ( ζ ) ⋅ ( u 0 ⋅ c ( ζ ) − ( 1 − u 0 ) ⋅ c ( ω ⋅ ζ ) ) + α n + 1 ⋅ ( L 0 ( ζ ) ⋅ ( z ( X ) − c 0 ⋅ a ( X ) ) + α n + 2 ⋅ ( ζ − 1 ) ⋅ ( z ( X ) − z ( ω − 1 ⋅ ζ ) − c ( ζ ) ⋅ a ( X ) ) + α n + 3 ⋅ L N − 1 ( ζ ) ⋅ ( z ( X ) − v ) − v H ( ζ ) ⋅ t ( X ) ) \begin{split}
l_\zeta(X) =& \Big(s_0(\zeta) \cdot (c(\zeta) - c_0) \\
& + \alpha\cdot s_0(\zeta) \cdot (u_{n-1}\cdot c(\zeta) - (1-u_{n-1})\cdot c(\omega^{2^{n-1}}\cdot\zeta))\\
& + \alpha^2\cdot s_1(\zeta) \cdot (u_{n-2}\cdot c(\zeta) - (1-u_{n-2})\cdot c(\omega^{2^{n-2}}\cdot\zeta)) \\
& + \cdots \\
& + \alpha^{n-1}\cdot s_{n-2}(\zeta)\cdot (u_{1}\cdot c(\zeta) - (1-u_{1})\cdot c(\omega^2\cdot\zeta))\\
& + \alpha^n\cdot s_{n-1}(\zeta)\cdot (u_{0}\cdot c(\zeta) - (1-u_{0})\cdot c(\omega\cdot\zeta)) \\
& + \alpha^{n+1}\cdot (L_0(\zeta)\cdot\big(z(X) - c_0\cdot a(X))\\
& + \alpha^{n+2}\cdot (\zeta - 1)\cdot\big(z(X)-z(\omega^{-1}\cdot\zeta)-c(\zeta)\cdot a(X) ) \\
& + \alpha^{n+3}\cdot L_{N-1}(\zeta)\cdot(z(X) - v) \\
& - v_H(\zeta)\cdot t(X)\ \Big)
\end{split} l ζ ( X ) = ( s 0 ( ζ ) ⋅ ( c ( ζ ) − c 0 ) + α ⋅ s 0 ( ζ ) ⋅ ( u n − 1 ⋅ c ( ζ ) − ( 1 − u n − 1 ) ⋅ c ( ω 2 n − 1 ⋅ ζ )) + α 2 ⋅ s 1 ( ζ ) ⋅ ( u n − 2 ⋅ c ( ζ ) − ( 1 − u n − 2 ) ⋅ c ( ω 2 n − 2 ⋅ ζ )) + ⋯ + α n − 1 ⋅ s n − 2 ( ζ ) ⋅ ( u 1 ⋅ c ( ζ ) − ( 1 − u 1 ) ⋅ c ( ω 2 ⋅ ζ )) + α n ⋅ s n − 1 ( ζ ) ⋅ ( u 0 ⋅ c ( ζ ) − ( 1 − u 0 ) ⋅ c ( ω ⋅ ζ )) + α n + 1 ⋅ ( L 0 ( ζ ) ⋅ ( z ( X ) − c 0 ⋅ a ( X )) + α n + 2 ⋅ ( ζ − 1 ) ⋅ ( z ( X ) − z ( ω − 1 ⋅ ζ ) − c ( ζ ) ⋅ a ( X )) + α n + 3 ⋅ L N − 1 ( ζ ) ⋅ ( z ( X ) − v ) − v H ( ζ ) ⋅ t ( X ) ) 显然，l ζ ( ζ ) = 0 l_\zeta(\zeta)= 0 l ζ ( ζ ) = 0 [ l ζ ( τ ) ] 1 [l_\zeta(\tau)]_1 [ l ζ ( τ ) ] 1
Prover Cost 3-5 ¶ 计算得到 [ l ζ ( x ) ∣ x ∈ H ] [l_{\zeta}(x)|_{x \in H}] [ l ζ ( x ) ∣ x ∈ H ]
L 0 ( ζ ) L_0(\zeta) L 0 ( ζ ) L N − 1 ( ζ ) L_{N - 1}(\zeta) L N − 1 ( ζ ) L 0 ( X ) L_0(X) L 0 ( X ) L N − 1 ( X ) L_{N - 1}(X) L N − 1 ( X ) L 0 ( ζ ) L_0(\zeta) L 0 ( ζ ) L N − 1 ( ζ ) L_{N - 1}(\zeta) L N − 1 ( ζ ) 2 N F m u l 2N ~\mathbb{F}_{\mathsf{mul}} 2 N F mul s 0 ( ζ ) ⋅ ( c ( ζ ) − c 0 ) s_0(\zeta) \cdot (c(\zeta) - c_0) s 0 ( ζ ) ⋅ ( c ( ζ ) − c 0 ) F m u l \mathbb{F}_{\mathsf{mul}} F mul α ⋅ s 0 ( ζ ) ⋅ ( u n − 1 ⋅ c ( ζ ) − ( 1 − u n − 1 ) ⋅ c ( ω 2 n − 1 ⋅ ζ ) ) \alpha \cdot s_0(\zeta) \cdot (u_{n-1}\cdot c(\zeta) - (1-u_{n-1})\cdot c(\omega^{2^{n-1}}\cdot\zeta)) α ⋅ s 0 ( ζ ) ⋅ ( u n − 1 ⋅ c ( ζ ) − ( 1 − u n − 1 ) ⋅ c ( ω 2 n − 1 ⋅ ζ )) 4 F m u l 4 ~ \mathbb{F}_{\mathsf{mul}} 4 F mul n + 1 n + 1 n + 1 4 n F m u l 4n ~ \mathbb{F}_{\mathsf{mul}} 4 n F mul 对于 x ∈ H x \in H x ∈ H [ α n + 1 ⋅ L 0 ( ζ ) ⋅ ( z ( x ) − c 0 ⋅ a ( x ) ) ) ] [\alpha^{n+1}\cdot L_0(\zeta)\cdot\big(z(x) - c_0\cdot a(x))\big)] [ α n + 1 ⋅ L 0 ( ζ ) ⋅ ( z ( x ) − c 0 ⋅ a ( x )) ) ] 3 N F m u l 3N ~ \mathbb{F}_{\mathsf{mul}} 3 N F mul 对于 x ∈ H x \in H x ∈ H [ α n + 2 ⋅ ( ζ − 1 ) ⋅ ( z ( x ) − z ( ω − 1 ⋅ ζ ) − c ( ζ ) ⋅ a ( x ) ] [\alpha^{n+2}\cdot (\zeta - 1)\cdot\big(z(x)-z(\omega^{-1}\cdot\zeta)-c(\zeta)\cdot a(x)] [ α n + 2 ⋅ ( ζ − 1 ) ⋅ ( z ( x ) − z ( ω − 1 ⋅ ζ ) − c ( ζ ) ⋅ a ( x )] ω − 1 ⋅ ζ \omega^{-1}\cdot\zeta ω − 1 ⋅ ζ x x x ( 3 N + 1 ) F m u l (3N + 1) ~ \mathbb{F}_{\mathsf{mul}} ( 3 N + 1 ) F mul 对于 x ∈ H x \in H x ∈ H [ α n + 3 ⋅ L N − 1 ( ζ ) ⋅ ( z ( x ) − v ) ] [\alpha^{n+3}\cdot L_{N-1}(\zeta)\cdot(z(x) - v)] [ α n + 3 ⋅ L N − 1 ( ζ ) ⋅ ( z ( x ) − v )] 2 N F m u l 2N ~ \mathbb{F}_{\mathsf{mul}} 2 N F mul 计算 v H ( ζ ) v_H(\zeta) v H ( ζ ) N F m u l N ~ \mathbb{F}_{\mathsf{mul}} N F mul 对于 x ∈ H x \in H x ∈ H [ v H ( ζ ) ⋅ t ( x ) ] [v_H(\zeta)\cdot t(x)] [ v H ( ζ ) ⋅ t ( x )] N F m u l N ~ \mathbb{F}_{\mathsf{mul}} N F mul 这一步的总复杂度为
( 12 N + 4 n + 2 ) F m u l (12 N + 4n + 2) ~ \mathbb{F}_{\mathsf{mul}} ( 12 N + 4 n + 2 ) F mul Round 3-6 ¶ 构造多项式 c ∗ ( X ) c^*(X) c ∗ ( X ) D ζ D\zeta D ζ
c ∗ ⃗ = ( c ( ω ⋅ ζ ) , c ( ω 2 ⋅ ζ ) , c ( ω 4 ⋅ ζ ) , … , c ( ω 2 n − 1 ⋅ ζ ) , c ( ζ ) ) \vec{c^*}= \Big(c(\omega\cdot\zeta), c(\omega^2\cdot\zeta), c(\omega^4\cdot\zeta), \ldots, c(\omega^{2^{n-1}}\cdot\zeta), c(\zeta)\Big) c ∗ = ( c ( ω ⋅ ζ ) , c ( ω 2 ⋅ ζ ) , c ( ω 4 ⋅ ζ ) , … , c ( ω 2 n − 1 ⋅ ζ ) , c ( ζ ) ) Prover 可以利用事先预计算的 D D D { w ^ i } \{\hat{w}_i\} { w ^ i } c ∗ ( X ) c^*(X) c ∗ ( X )
c ∗ ( X ) = c 0 ∗ ⋅ w ^ 0 X − ω ζ + c 1 ∗ ⋅ w ^ 1 X − ω 2 ζ + ⋯ + c n ∗ ⋅ w ^ n X − ω 2 n ζ w ^ 0 X − ω ζ + w ^ 1 X − ω 2 ζ + ⋯ + w ^ n X − ω 2 n ζ c^*(X) = \frac{c^*_0 \cdot \frac{\hat{w}_0}{X-\omega\zeta} + c^*_1 \cdot \frac{\hat{w}_1}{X-\omega^{2}\zeta} + \cdots + c^*_n \cdot \frac{\hat{w}_n}{X-\omega^{2^n}\zeta}}{
\frac{\hat{w}_0}{X-\omega\zeta} + \frac{\hat{w}_1}{X-\omega^2\zeta} + \cdots + \frac{\hat{w}_n}{X-\omega^{2^n}\zeta}
} c ∗ ( X ) = X − ω ζ w ^ 0 + X − ω 2 ζ w ^ 1 + ⋯ + X − ω 2 n ζ w ^ n c 0 ∗ ⋅ X − ω ζ w ^ 0 + c 1 ∗ ⋅ X − ω 2 ζ w ^ 1 + ⋯ + c n ∗ ⋅ X − ω 2 n ζ w ^ n 这里 w ^ j \hat{w}_j w ^ j
w ^ j = ∏ l ≠ j 1 ω 2 j − ω 2 l \hat{w}_j = \prod_{l\neq j} \frac{1}{\omega^{2^j} - \omega^{2^l}} w ^ j = l = j ∏ ω 2 j − ω 2 l 1 Prover Cost 3-6 ¶ 📝 Notes
📝 之前的分析过程：
Prover:
c ∗ ⃗ \vec{c^*} c ∗ ω 2 i ζ \omega^{2^i}\zeta ω 2 i ζ 计算 w ^ i X − ω 2 i ζ \frac{\hat{w}_i}{X-\omega^{2^i}\zeta} X − ω 2 i ζ w ^ i p o l y d i v ( 0 , 1 ) \mathsf{polydiv}(0, 1) polydiv ( 0 , 1 ) 计算 c i ∗ ⋅ w ^ i X − ω 2 i ζ c_i^* \cdot \frac{\hat{w}_i}{X-\omega^{2^i}\zeta} c i ∗ ⋅ X − ω 2 i ζ w ^ i p o l y m u l ( 0 , − 1 ) \mathsf{polymul}(0, -1) polymul ( 0 , − 1 ) 最后计算 c ∗ ( X ) c^*(X) c ∗ ( X ) n n n p o l y d i v ( n , n ) \mathsf{polydiv}(n, n) polydiv ( n , n ) c ∗ ( X ) c^*(X) c ∗ ( X ) n n n 多项式相加的复杂度只涉及有限域的加法，不做计入，因此这一步 c ∗ ( X ) c^*(X) c ∗ ( X )
> n p o l y m u l ( 0 , − 1 ) + n p o l y d i v ( 0 , 1 ) + p o l y d i v ( n , n ) > > n ~ \mathsf{polymul}(0, -1) + n ~\mathsf{polydiv}(0, 1) + \mathsf{polydiv}(n, n)
> > n polymul ( 0 , − 1 ) + n polydiv ( 0 , 1 ) + polydiv ( n , n ) > 复杂度为
( n + 1 ) log 2 ( n + 1 ) F m u l (n + 1) \log^2(n + 1) ~ \mathbb{F}_{\mathsf{mul}} ( n + 1 ) log 2 ( n + 1 ) F mul Round 3-7 ¶ 因为 l ζ ( ζ ) = 0 l_\zeta(\zeta)= 0 l ζ ( ζ ) = 0 q ζ ( X ) q_\zeta(X) q ζ ( X )
q ζ ( X ) = 1 X − ζ ⋅ l ζ ( X ) q_\zeta(X) = \frac{1}{X-\zeta}\cdot l_\zeta(X) q ζ ( X ) = X − ζ 1 ⋅ l ζ ( X ) Prover Cost 3-7 ¶ 这一步的计算采用的是下面的算法，代码为
def division_by_linear_divisor(self, d):
"""
Divide a polynomial by a linear divisor (X - d) using Ruffini's rule.
Args:
coeffs (list): Coefficients of the polynomial, from lowest to highest degree.
d (Scalar): The constant term of the linear divisor.
Returns:
tuple: (quotient coefficients, remainder)
"""
assert len(self.coeffs) > 0, "Polynomial degree must be at least 1"
n = len(self.coeffs)
quotient = [0] * (n - 1)
# Start with the highest degree coefficient
current = self.coeffs[-1]
# Iterate through coefficients from second-highest to lowest degree
for i in range(n - 2, -1, -1):
# Store the current value in the quotient
quotient[i] = current
# Compute the next value
current = current * d + self.coeffs[i]
# The final current value is the remainder
remainder = current
return UniPolynomial(quotient), remainder对于一个 n n n
> f ( X ) = f 0 + f 1 X + f 2 X 2 + ⋯ + f n − 1 X n − 1 + f n X n > > f(X) = f_0 + f_1 X + f_2 X^2 + \cdots + f_{n-1} X^{n-1} + f_n X^n
> > f ( X ) = f 0 + f 1 X + f 2 X 2 + ⋯ + f n − 1 X n − 1 + f n X n > 除上一个一次多项式 X − d X - d X − d f ( X ) = q ( X ) ( X − d ) + r ( X ) f(X) = q(X)(X - d) + r(X) f ( X ) = q ( X ) ( X − d ) + r ( X )
> > f 0 + f 1 X + f 2 X 2 + ⋯ + f n − 1 X n − 1 + f n X n > = ( X − d ) ( f n ⋅ X n − 1 ) + d ⋅ f n ⋅ X n − 1 + f n − 1 X n − 1 + ⋯ + f 1 X + f 0 > = ( X − d ) ( f n ⋅ X n − 1 ) + ( X − d ) ( ( d f n + f n − 1 ) ⋅ X n − 2 ) > + d ⋅ ( d f n + f n − 1 ) + f n − 2 X n − 2 + ⋯ + f 1 X + f 0 > > > \begin{aligned}
> & f_0 + f_1 X + f_2 X^2 + \cdots + f_{n-1} X^{n-1} + f_n X^n \\
> = & (X - d)(f_n \cdot X^{n - 1}) + d \cdot f_n \cdot X^{n - 1} + f_{n - 1} X^{n - 1} + \cdots + f_1 X + f_0 \\
> = & (X - d)(f_n \cdot X^{n - 1}) + (X - d)((df_n + f_{n - 1}) \cdot X^{n - 2}) \\
> & + d \cdot (df_n + f_{n - 1}) + f_{n - 2} X^{n - 2} + \cdots + f_1 X + f_0 \\
> \end{aligned}
> > > >= >= > > f 0 + f 1 X + f 2 X 2 + ⋯ + f n − 1 X n − 1 + f n X n ( X − d ) ( f n ⋅ X n − 1 ) + d ⋅ f n ⋅ X n − 1 + f n − 1 X n − 1 + ⋯ + f 1 X + f 0 ( X − d ) ( f n ⋅ X n − 1 ) + ( X − d ) (( d f n + f n − 1 ) ⋅ X n − 2 ) + d ⋅ ( d f n + f n − 1 ) + f n − 2 X n − 2 + ⋯ + f 1 X + f 0 > 通过上式子发现，
> > q n − 1 = f n > q i = d ⋅ q i + 1 + f i + 1 , i = n − 2 , … , 0 > > > \begin{aligned}
> & q_{n - 1} = f_n \\
> & q_i = d \cdot q_{i + 1} + f_{i + 1} , \quad i = n - 2, \ldots, 0 \\
> \end{aligned}
> > > > > q n − 1 = f n q i = d ⋅ q i + 1 + f i + 1 , i = n − 2 , … , 0 > 因此最后的余项为
> r ( X ) = d ⋅ q 0 + f 0 > > r(X) = d \cdot q_0 + f_0
> > r ( X ) = d ⋅ q 0 + f 0 > 这里 i i i n − 2 , … , 0 n - 2, \ldots, 0 n − 2 , … , 0 r ( X ) r(X) r ( X ) n F m u l n ~ \mathbb{F}_{\mathsf{mul}} n F mul
回到分析计算 q ζ ( X ) q_\zeta(X) q ζ ( X ) l ζ ( X ) l_\zeta(X) l ζ ( X )
> > l ζ ( X ) = ( s 0 ( ζ ) ⋅ ( c ( ζ ) − c 0 ) > + α ⋅ s 0 ( ζ ) ⋅ ( u n − 1 ⋅ c ( ζ ) − ( 1 − u n − 1 ) ⋅ c ( ω 2 n − 1 ⋅ ζ ) ) > + α 2 ⋅ s 1 ( ζ ) ⋅ ( u n − 2 ⋅ c ( ζ ) − ( 1 − u n − 2 ) ⋅ c ( ω 2 n − 2 ⋅ ζ ) ) > + ⋯ > + α n − 1 ⋅ s n − 2 ( ζ ) ⋅ ( u 1 ⋅ c ( ζ ) − ( 1 − u 1 ) ⋅ c ( ω 2 ⋅ ζ ) ) > + α n ⋅ s n − 1 ( ζ ) ⋅ ( u 0 ⋅ c ( ζ ) − ( 1 − u 0 ) ⋅ c ( ω ⋅ ζ ) ) > + α n + 1 ⋅ ( L 0 ( ζ ) ⋅ ( z ( X ) − c 0 ⋅ a ( X ) ) > + α n + 2 ⋅ ( ζ − 1 ) ⋅ ( z ( X ) − z ( ω − 1 ⋅ ζ ) − c ( ζ ) ⋅ a ( X ) ) > + α n + 3 ⋅ L N − 1 ( ζ ) ⋅ ( z ( X ) − v ) > − v H ( ζ ) ⋅ t ( X ) ) > > > \begin{split}
> l_\zeta(X) =& \Big(s_0(\zeta) \cdot (c(\zeta) - c_0) \\
> & + \alpha\cdot s_0(\zeta) \cdot (u_{n-1}\cdot c(\zeta) - (1-u_{n-1})\cdot c(\omega^{2^{n-1}}\cdot\zeta))\\
> & + \alpha^2\cdot s_1(\zeta) \cdot (u_{n-2}\cdot c(\zeta) - (1-u_{n-2})\cdot c(\omega^{2^{n-2}}\cdot\zeta)) \\
> & + \cdots \\
> & + \alpha^{n-1}\cdot s_{n-2}(\zeta)\cdot (u_{1}\cdot c(\zeta) - (1-u_{1})\cdot c(\omega^2\cdot\zeta))\\
> & + \alpha^n\cdot s_{n-1}(\zeta)\cdot (u_{0}\cdot c(\zeta) - (1-u_{0})\cdot c(\omega\cdot\zeta)) \\
> & + \alpha^{n+1}\cdot (L_0(\zeta)\cdot\big(z(X) - c_0\cdot a(X))\\
> & + \alpha^{n+2}\cdot (\zeta - 1)\cdot\big(z(X)-z(\omega^{-1}\cdot\zeta)-c(\zeta)\cdot a(X) \big) \\
> & + \alpha^{n+3}\cdot L_{N-1}(\zeta)\cdot(z(X) - v) \\
> & - v_H(\zeta)\cdot t(X)\ \Big)
> \end{split}
> > > l ζ ( X ) = > > > > > > > > > ( s 0 ( ζ ) ⋅ ( c ( ζ ) − c 0 ) + α ⋅ s 0 ( ζ ) ⋅ ( u n − 1 ⋅ c ( ζ ) − ( 1 − u n − 1 ) ⋅ c ( ω 2 n − 1 ⋅ ζ )) + α 2 ⋅ s 1 ( ζ ) ⋅ ( u n − 2 ⋅ c ( ζ ) − ( 1 − u n − 2 ) ⋅ c ( ω 2 n − 2 ⋅ ζ )) + ⋯ + α n − 1 ⋅ s n − 2 ( ζ ) ⋅ ( u 1 ⋅ c ( ζ ) − ( 1 − u 1 ) ⋅ c ( ω 2 ⋅ ζ )) + α n ⋅ s n − 1 ( ζ ) ⋅ ( u 0 ⋅ c ( ζ ) − ( 1 − u 0 ) ⋅ c ( ω ⋅ ζ )) + α n + 1 ⋅ ( L 0 ( ζ ) ⋅ ( z ( X ) − c 0 ⋅ a ( X )) + α n + 2 ⋅ ( ζ − 1 ) ⋅ ( z ( X ) − z ( ω − 1 ⋅ ζ ) − c ( ζ ) ⋅ a ( X ) ) + α n + 3 ⋅ L N − 1 ( ζ ) ⋅ ( z ( X ) − v ) − v H ( ζ ) ⋅ t ( X ) ) > > 前面几项都为常数，
α n + 1 ⋅ ( L 0 ( ζ ) ⋅ ( z ( X ) − c 0 ⋅ a ( X ) ) \alpha^{n+1}\cdot (L_0(\zeta)\cdot\big(z(X) - c_0\cdot a(X)) α n + 1 ⋅ ( L 0 ( ζ ) ⋅ ( z ( X ) − c 0 ⋅ a ( X )) N − 1 + N − 1 = 2 N − 2 N - 1 + N - 1 = 2N - 2 N − 1 + N − 1 = 2 N − 2 α n + 2 ⋅ ( ζ − 1 ) ⋅ ( z ( X ) − z ( ω − 1 ⋅ ζ ) − c ( ζ ) ⋅ a ( X ) ) \alpha^{n+2}\cdot (\zeta - 1)\cdot\big(z(X)-z(\omega^{-1}\cdot\zeta)-c(\zeta)\cdot a(X) \big) α n + 2 ⋅ ( ζ − 1 ) ⋅ ( z ( X ) − z ( ω − 1 ⋅ ζ ) − c ( ζ ) ⋅ a ( X ) ) N − 1 N - 1 N − 1 α n + 3 ⋅ L N − 1 ( ζ ) ⋅ ( z ( X ) − v ) \alpha^{n+3}\cdot L_{N-1}(\zeta)\cdot(z(X) - v) α n + 3 ⋅ L N − 1 ( ζ ) ⋅ ( z ( X ) − v ) N − 1 + N − 1 = 2 N − 2 N - 1 + N - 1 = 2N - 2 N − 1 + N − 1 = 2 N − 2 v H ( ζ ) ⋅ t ( X ) v_H(\zeta)\cdot t(X) v H ( ζ ) ⋅ t ( X ) 2 N − 1 2N - 1 2 N − 1 因此 l ζ ( X ) l_\zeta(X) l ζ ( X ) 2 N − 1 2N - 1 2 N − 1 q ζ ( X ) q_\zeta(X) q ζ ( X ) ( 2 N − 1 ) F m u l (2N - 1) ~ \mathbb{F}_{\mathsf{mul}} ( 2 N − 1 ) F mul
📝 高效求逆算法
一般地，对于 N N N a 0 , … , a N − 1 a_0, \ldots, a_{N - 1} a 0 , … , a N − 1 a 0 − 1 , … , a N − 1 − 1 a_0^{-1}, \ldots, a_{N-1}^{-1} a 0 − 1 , … , a N − 1 − 1
先计算出 N N N b 0 = a 0 b 1 = b 0 ⋅ a 1 = a 0 ⋅ a 1 b 2 = b 1 ⋅ a 2 = a 0 ⋅ a 1 ⋅ a 2 … b N − 2 = b N − 3 ⋅ a N − 2 = a 0 ⋅ a 1 ⋯ a N − 2 b N − 1 = b N − 2 ⋅ a N − 1 = a 0 ⋅ a 1 ⋯ a N − 2 ⋅ a N − 1 \begin{aligned}
& b_0 = a_0 \\
& b_1 = b_0 \cdot a_1 = a_0 \cdot a_1 \\
& b_2 = b_1 \cdot a_2 = a_0 \cdot a_1 \cdot a_2 \\
& \ldots \\
& b_{N - 2} = b_{N - 3} \cdot a_{N - 2} = a_0 \cdot a_1 \cdots a_{N - 2} \\
& b_{N - 1} = b_{N - 2} \cdot a_{N - 1} = a_0 \cdot a_1 \cdots a_{N - 2} \cdot a_{N - 1}\\
\end{aligned} b 0 = a 0 b 1 = b 0 ⋅ a 1 = a 0 ⋅ a 1 b 2 = b 1 ⋅ a 2 = a 0 ⋅ a 1 ⋅ a 2 … b N − 2 = b N − 3 ⋅ a N − 2 = a 0 ⋅ a 1 ⋯ a N − 2 b N − 1 = b N − 2 ⋅ a N − 1 = a 0 ⋅ a 1 ⋯ a N − 2 ⋅ a N − 1 计算 b 1 , … , b N − 1 b_1, \ldots, b_{N - 1} b 1 , … , b N − 1 ( N − 1 ) F m u l (N - 1) ~ \mathbb{F}_{\mathsf{mul}} ( N − 1 ) F mul
计算出 b N − 1 − 1 b_{N-1}^{-1} b N − 1 − 1 F i n v \mathbb{F}_{\mathsf{inv}} F inv 计算 b N − 2 − 1 = ( a 0 ⋅ a 1 ⋯ a N − 2 ) − 1 = a N − 1 ⋅ b N − 1 − 1 b N − 3 − 1 = ( a 0 ⋅ a 1 ⋯ a N − 3 ) − 1 = a N − 2 ⋅ b N − 2 − 1 … b 1 − 1 = ( a 0 ⋅ a 1 ) − 1 = a 2 ⋅ b 2 − 1 \begin{aligned}
& b_{N-2}^{-1} = (a_0 \cdot a_1 \cdots a_{N - 2} )^{-1} = a_{N - 1} \cdot b_{N-1}^{-1} \\
& b_{N-3}^{-1} = (a_0 \cdot a_1 \cdots a_{N - 3} )^{-1} = a_{N - 2} \cdot b_{N-2}^{-1} \\
& \ldots \\
& b_{1}^{-1} = (a_0 \cdot a_1 )^{-1} = a_{2} \cdot b_{2}^{-1} \\
\end{aligned} b N − 2 − 1 = ( a 0 ⋅ a 1 ⋯ a N − 2 ) − 1 = a N − 1 ⋅ b N − 1 − 1 b N − 3 − 1 = ( a 0 ⋅ a 1 ⋯ a N − 3 ) − 1 = a N − 2 ⋅ b N − 2 − 1 … b 1 − 1 = ( a 0 ⋅ a 1 ) − 1 = a 2 ⋅ b 2 − 1 这一步复杂度为 ( N − 2 ) F m u l (N - 2) ~ \mathbb{F}_{\mathsf{mul}} ( N − 2 ) F mul
现在再从头相乘计算出 a 0 − 1 , … , a N − 1 − 1 a_0^{-1}, \ldots, a_{N-1}^{-1} a 0 − 1 , … , a N − 1 − 1 a 0 − 1 = 1 a 0 ⋅ a 1 ⋅ a 1 = b 1 − 1 ⋅ a 1 a 1 − 1 = 1 a 0 ⋅ a 1 ⋅ a 0 = b 1 − 1 ⋅ b 0 a 2 − 1 = 1 a 0 ⋅ a 1 ⋅ a 2 ⋅ ( a 0 ⋅ a 1 ) = b 2 − 1 ⋅ b 1 … a N − 2 − 1 = 1 a 0 ⋅ a 1 ⋅ a 2 ⋯ a N − 3 ⋅ a N − 2 ⋅ ( a 0 ⋅ a 1 ⋅ a 2 ⋯ a N − 3 ) = b N − 2 − 1 ⋅ b N − 3 a N − 1 − 1 = 1 a 0 ⋅ a 1 ⋅ a 2 ⋯ a N − 2 ⋅ a N − 1 ⋅ ( a 0 ⋅ a 1 ⋅ a 2 ⋯ a N − 2 ) = b N − 1 − 1 ⋅ b N − 2 \begin{aligned}
& a_0^{-1} = \frac{1}{a_0 \cdot a_1} \cdot a_1 = b_1^{-1} \cdot a_1 \\
& a_1^{-1} = \frac{1}{a_0 \cdot a_1} \cdot a_0 = b_1^{-1} \cdot b_0\\
& a_2^{-1} = \frac{1}{a_0 \cdot a_1 \cdot a_2} \cdot (a_0 \cdot a_1) = b_2^{-1} \cdot b_1\\
& \ldots \\
& a_{N - 2}^{-1} = \frac{1}{a_0 \cdot a_1 \cdot a_2 \cdots a_{N - 3} \cdot a_{N - 2}} \cdot (a_0 \cdot a_1 \cdot a_2 \cdots a_{N - 3} ) = b_{N - 2}^{-1} \cdot b_{N - 3} \\
& a_{N - 1}^{-1} = \frac{1}{a_0 \cdot a_1 \cdot a_2 \cdots a_{N - 2} \cdot a_{N - 1}} \cdot (a_0 \cdot a_1 \cdot a_2 \cdots a_{N - 2} ) = b_{N - 1}^{-1} \cdot b_{N - 2}
\end{aligned} a 0 − 1 = a 0 ⋅ a 1 1 ⋅ a 1 = b 1 − 1 ⋅ a 1 a 1 − 1 = a 0 ⋅ a 1 1 ⋅ a 0 = b 1 − 1 ⋅ b 0 a 2 − 1 = a 0 ⋅ a 1 ⋅ a 2 1 ⋅ ( a 0 ⋅ a 1 ) = b 2 − 1 ⋅ b 1 … a N − 2 − 1 = a 0 ⋅ a 1 ⋅ a 2 ⋯ a N − 3 ⋅ a N − 2 1 ⋅ ( a 0 ⋅ a 1 ⋅ a 2 ⋯ a N − 3 ) = b N − 2 − 1 ⋅ b N − 3 a N − 1 − 1 = a 0 ⋅ a 1 ⋅ a 2 ⋯ a N − 2 ⋅ a N − 1 1 ⋅ ( a 0 ⋅ a 1 ⋅ a 2 ⋯ a N − 2 ) = b N − 1 − 1 ⋅ b N − 2 复杂度为 N F m u l N ~ \mathbb{F}_{\mathsf{mul}} N F mul
因此计算出逆 a 0 − 1 , … , a N − 1 − 1 a_0^{-1}, \ldots, a_{N-1}^{-1} a 0 − 1 , … , a N − 1 − 1 F i n v + ( 3 N − 3 ) F m u l \mathbb{F}_{\mathsf{inv}} + (3N - 3) ~ \mathbb{F}_{\mathsf{mul}} F inv + ( 3 N − 3 ) F mul
分析 Prover Cost
在 Round 3-5 已经计算得到 [ l ζ ( x ) ∣ x ∈ H ] [l_{\zeta}(x)|_{x \in H}] [ l ζ ( x ) ∣ x ∈ H ] [ q ζ ( x ) ∣ x ∈ H ] [q_{\zeta}(x)|_{x \in H}] [ q ζ ( x ) ∣ x ∈ H ]
先计算 N N N [ ( x − ζ ) − 1 ∣ x ∈ H ] [(x - \zeta)^{-1}|_{x \in H}] [( x − ζ ) − 1 ∣ x ∈ H ] F i n v + ( 3 N − 3 ) F m u l \mathbb{F}_{\mathsf{inv}} + (3N - 3) ~ \mathbb{F}_{\mathsf{mul}} F inv + ( 3 N − 3 ) F mul 计算 [ q ζ ( x ) ∣ x ∈ H ] [q_{\zeta}(x)|_{x \in H}] [ q ζ ( x ) ∣ x ∈ H ] N F m u l N ~ \mathbb{F}_{\mathsf{mul}} N F mul 因此这一步总复杂度为
F i n v + ( 4 N − 3 ) F m u l \mathbb{F}_{\mathsf{inv}} + (4N - 3) ~ \mathbb{F}_{\mathsf{mul}} F inv + ( 4 N − 3 ) F mul Round 3-8 ¶ 第 8 步. 构造 D ζ D\zeta D ζ z D ζ ( X ) z_{D_{\zeta}}(X) z D ζ ( X )
z D ζ ( X ) = ( X − ζ ω ) ⋯ ( X − ζ ω 2 n − 1 ) ( X − ζ ) z_{D_{\zeta}}(X) = (X-\zeta\omega)\cdots (X-\zeta\omega^{2^{n-1}})(X-\zeta) z D ζ ( X ) = ( X − ζ ω ) ⋯ ( X − ζ ω 2 n − 1 ) ( X − ζ ) Prover Cost 3-8 ¶ 在 Round 3-6 中已经计算出消失多项 z D ζ ( X ) z_{D_{\zeta}}(X) z D ζ ( X )
Round 3-9 ¶ 第 9 步，构造 Quotient 多项式 q c ( X ) q_c(X) q c ( X )
q c ( X ) = ( c ( X ) − c ∗ ( X ) ) ( X − ζ ) ( X − ω ζ ) ( X − ω 2 ζ ) ⋯ ( X − ω 2 n − 1 ζ ) q_c(X) = \frac{(c(X) - c^*(X))}{(X-\zeta)(X-\omega\zeta)(X-\omega^2\zeta)\cdots(X-\omega^{2^{n-1}}\zeta)} q c ( X ) = ( X − ζ ) ( X − ω ζ ) ( X − ω 2 ζ ) ⋯ ( X − ω 2 n − 1 ζ ) ( c ( X ) − c ∗ ( X )) Prover Cost 3-9 ¶ 这里由于分母的多项式的次数比较高，因此用点值式来进行计算会比较高效。
已有：c ∗ ( X ) c^*(X) c ∗ ( X ) z D ζ ( X ) z_{D_{\zeta}}(X) z D ζ ( X )
计算 [ c ∗ ( x ) ∣ x ∈ H ] [c^*(x)|_{x \in H}] [ c ∗ ( x ) ∣ x ∈ H ] c ∗ ( X ) c^*(X) c ∗ ( X ) H H H F F T ( N ) \mathsf{FFT}(N) FFT ( N ) 计算 [ z D ζ ( x ) ∣ x ∈ H ] [z_{D_{\zeta}}(x)|_{x \in H}] [ z D ζ ( x ) ∣ x ∈ H ] z D ζ ( X ) z_{D_{\zeta}}(X) z D ζ ( X ) H H H F F T ( N ) \mathsf{FFT}(N) FFT ( N ) 计算逆 [ ( z D ζ ( x ) ) − 1 ∣ x ∈ H ] [(z_{D_{\zeta}}(x))^{-1}|_{x \in H}] [( z D ζ ( x ) ) − 1 ∣ x ∈ H ] F i n v + ( 3 N − 3 ) F m u l \mathbb{F}_{\mathsf{inv}} + (3N - 3) ~ \mathbb{F}_{\mathsf{mul}} F inv + ( 3 N − 3 ) F mul 计算 [ q c ( x ) ∣ x ∈ H ] [q_c(x)|_{x \in H}] [ q c ( x ) ∣ x ∈ H ] N F m u l N ~ \mathbb{F}_{\mathsf{mul}} N F mul 因此这一步的总复杂度为
2 F F T ( N ) + F i n v + ( 4 N − 3 ) F m u l 2 ~ \mathsf{FFT}(N) + \mathbb{F}_{\mathsf{inv}} + (4N - 3) ~ \mathbb{F}_{\mathsf{mul}} 2 FFT ( N ) + F inv + ( 4 N − 3 ) F mul Round 3-10 ¶ 第 10 步，构造 Quotient 多项式 q ω ζ ( X ) q_{\omega\zeta}(X) q ω ζ ( X )
q ω ζ ( X ) = z ( X ) − z ( ω − 1 ⋅ ζ ) X − ω − 1 ⋅ ζ q_{\omega\zeta}(X) = \frac{z(X) - z(\omega^{-1}\cdot\zeta)}{X - \omega^{-1}\cdot\zeta} q ω ζ ( X ) = X − ω − 1 ⋅ ζ z ( X ) − z ( ω − 1 ⋅ ζ ) Prover Cost 3-10 ¶ 方法一：用系数式进行相除。
在前面 Round 2-4 已经计算得到了 z ( X ) z(X) z ( X ) z ( X ) − z ( ω − 1 ⋅ ζ ) z(X) - z(\omega^{-1}\cdot\zeta) z ( X ) − z ( ω − 1 ⋅ ζ ) ( N − 1 ) F m u l (N - 1) ~ \mathbb{F}_{\mathsf{mul}} ( N − 1 ) F mul
方法二：用点值式进行计算。
计算得到 [ q ω ζ ( x ) ∣ x ∈ H ] [q_{\omega\zeta}(x)|_{x \in H}] [ q ω ζ ( x ) ∣ x ∈ H ]
先计算 [ ( x − ω − 1 ⋅ ζ ) − 1 ∣ x ∈ H ] [(x - \omega^{-1} \cdot \zeta)^{-1}|_{x \in H}] [( x − ω − 1 ⋅ ζ ) − 1 ∣ x ∈ H ] F i n v + ( 3 N − 3 ) F m u l \mathbb{F}_{\mathsf{inv}} + (3N - 3) ~ \mathbb{F}_{\mathsf{mul}} F inv + ( 3 N − 3 ) F mul 计算 [ q ω ζ ( x ) ∣ x ∈ H ] [q_{\omega\zeta}(x)|_{x \in H}] [ q ω ζ ( x ) ∣ x ∈ H ] N F m u l N ~ \mathbb{F}_{\mathsf{mul}} N F mul 这种方法的总复杂度为
F i n v + ( 4 N − 3 ) F m u l \mathbb{F}_{\mathsf{inv}} + (4N - 3) ~ \mathbb{F}_{\mathsf{mul}} F inv + ( 4 N − 3 ) F mul 可以看到，由于分母只是一次多项式，用方法一会更高效一些。
Round 3-11 ¶ 第 11 步，发送 ( Q c = [ q c ( τ ) ] 1 , Q ζ = [ q ζ ( τ ) ] 1 , Q ω ζ = [ q ω ζ ( τ ) ] 1 , ) \big(Q_c = [q_c(\tau)]_1, Q_\zeta=[q_\zeta(\tau)]_1, Q_{\omega\zeta}=[q_{\omega\zeta}(\tau)]_1, \big) ( Q c = [ q c ( τ ) ] 1 , Q ζ = [ q ζ ( τ ) ] 1 , Q ω ζ = [ q ω ζ ( τ ) ] 1 , )
Prover Cost 3-11 ¶ 在 Round 3-9 得到的 [ q c ( x ) ∣ x ∈ H ] [q_c(x)|_{x \in H}] [ q c ( x ) ∣ x ∈ H ] Q c = q c ( ω 0 ) ⋅ A 0 + … q c ( ω N − 1 ) ⋅ A N − 1 Q_c = q_c(\omega^0) \cdot A_0 + \ldots q_c(\omega^{N - 1}) \cdot A_{N - 1} Q c = q c ( ω 0 ) ⋅ A 0 + … q c ( ω N − 1 ) ⋅ A N − 1 复杂度为 m s m ( N , G 1 ) \mathsf{msm}(N, \mathbb{G}_1) msm ( N , G 1 )
在 Round 3-7 得到 [ q ζ ( x ) ∣ x ∈ H ] [q_{\zeta}(x)|_{x \in H}] [ q ζ ( x ) ∣ x ∈ H ] Q ζ = q ζ ( ω 0 ) ⋅ A 0 + … q ζ ( ω N − 1 ) ⋅ A N − 1 Q_\zeta = q_\zeta(\omega^0) \cdot A_0 + \ldots q_\zeta(\omega^{N - 1}) \cdot A_{N - 1} Q ζ = q ζ ( ω 0 ) ⋅ A 0 + … q ζ ( ω N − 1 ) ⋅ A N − 1 复杂度为 m s m ( N , G 1 ) \mathsf{msm}(N, \mathbb{G}_1) msm ( N , G 1 )
在 Round 3-10 若用方法一，则得到的是 q ω ζ ( X ) q_{\omega\zeta}(X) q ω ζ ( X ) q ω ζ ( 0 ) , q ω ζ ( 1 ) , … , q ω ζ ( N − 2 ) q_{\omega\zeta}^{(0)}, q_{\omega\zeta}^{(1)}, \ldots, q_{\omega\zeta}^{(N - 2)} q ω ζ ( 0 ) , q ω ζ ( 1 ) , … , q ω ζ ( N − 2 ) Q ω ζ = q ω ζ ( 0 ) ⋅ G + q ω ζ ( 1 ) ⋅ ( τ ⋅ G ) + ⋯ + q ω ζ ( N − 2 ) ⋅ ( τ N − 2 ⋅ G ) Q_{\omega\zeta} = q_{\omega\zeta}^{(0)} \cdot G + q_{\omega\zeta}^{(1)} \cdot (\tau \cdot G) + \cdots + q_{\omega\zeta}^{(N - 2)} \cdot (\tau^{N - 2} \cdot G) Q ω ζ = q ω ζ ( 0 ) ⋅ G + q ω ζ ( 1 ) ⋅ ( τ ⋅ G ) + ⋯ + q ω ζ ( N − 2 ) ⋅ ( τ N − 2 ⋅ G ) 其中 G G G G 1 \mathbb{G}_1 G 1 ( G , τ G , … , τ N − 2 G ) (G, \tau G, \ldots, \tau^{N - 2}G) ( G , τ G , … , τ N − 2 G ) m s m ( N − 1 , G 1 ) \mathsf{msm}(N - 1, \mathbb{G}_1) msm ( N − 1 , G 1 )
若用方法二，得到的是 [ q ω ζ ( x ) ∣ x ∈ H ] [q_{\omega\zeta}(x)|_{x \in H}] [ q ω ζ ( x ) ∣ x ∈ H ] Q ζ = q ω ζ ( ω 0 ) ⋅ A 0 + … q ω ζ ( ω N − 1 ) ⋅ A N − 1 Q_\zeta = q_{\omega\zeta}(\omega^0) \cdot A_0 + \ldots q_{\omega \zeta}(\omega^{N - 1}) \cdot A_{N - 1} Q ζ = q ω ζ ( ω 0 ) ⋅ A 0 + … q ω ζ ( ω N − 1 ) ⋅ A N − 1 复杂度为 m s m ( N , G 1 ) \mathsf{msm}(N, \mathbb{G}_1) msm ( N , G 1 )
总结上面的复杂度：
在 Round 3-10 用方法一，系数形式，复杂度为 2 m s m ( N , G 1 ) + m s m ( N − 1 , G 1 ) 2 ~ \mathsf{msm}(N, \mathbb{G}_1) + \mathsf{msm}(N - 1, \mathbb{G}_1) 2 msm ( N , G 1 ) + msm ( N − 1 , G 1 ) 在 Round 3-10 用方法二，点值形式，复杂度为 3 m s m ( N , G 1 ) 3 ~ \mathsf{msm}(N, \mathbb{G}_1) 3 msm ( N , G 1 ) Prover Cost Round 3 ¶ 将这一轮的计算复杂度相加为
在 Round 3-10 用方法一，系数形式，复杂度为 这种方法要求内存中要存储 SRS ( G , τ G , … , τ N − 2 G ) (G, \tau G, \ldots, \tau^{N - 2}G) ( G , τ G , … , τ N − 2 G )
在 Round 3-10 用方法二，点值形式，复杂度为 2 ( n − 1 ) F m u l + n F m u l + F F T ( N ) + ( N + 1 ) F m u l + ( 12 N + 4 n + 2 ) F m u l + ( n + 1 ) log 2 ( n + 1 ) F m u l + F i n v + ( 4 N − 3 ) F m u l + 2 F F T ( N ) + F i n v + ( 4 N − 3 ) F m u l + F i n v + ( 4 N − 3 ) F m u l + 3 m s m ( N , G 1 ) = 3 F F T ( N ) + ( 21 N + 7 n − 3 ) F m u l + 2 F i n v + ( n + 1 ) log 2 ( n + 1 ) F m u l + F i n v + ( 4 N − 3 ) F m u l + 3 m s m ( N , G 1 ) = 3 F F T ( N ) + ( 25 N + 7 n − 6 ) F m u l + 3 F i n v + 3 m s m ( N , G 1 ) + ( n + 1 ) log 2 ( n + 1 ) F m u l \begin{aligned}
& 2(n - 1) ~ \mathbb{F}_{\mathsf{mul}} + n ~\mathbb{F}_{\mathsf{mul}} + \mathsf{FFT}(N) + (N + 1) ~ \mathbb{F}_{\mathsf{mul}} + (12 N + 4n + 2) ~ \mathbb{F}_{\mathsf{mul}} \\
& + {\color{orange} (n + 1) \log^2(n + 1) ~ \mathbb{F}_{\mathsf{mul}} } + \mathbb{F}_{\mathsf{inv}} + (4N - 3) ~ \mathbb{F}_{\mathsf{mul}} + 2 ~ \mathsf{FFT}(N) + \mathbb{F}_{\mathsf{inv}} + (4N - 3) ~ \mathbb{F}_{\mathsf{mul}} \\
& + {\color{red} \mathbb{F}_{\mathsf{inv}} + (4N - 3) ~ \mathbb{F}_{\mathsf{mul}}} + {\color{red} 3 ~ \mathsf{msm}(N, \mathbb{G}_1)} \\
= & 3 ~ \mathsf{FFT}(N) + (21N + 7n - 3) ~ \mathbb{F}_{\mathsf{mul}} + 2~ \mathbb{F}_{\mathsf{inv}} + {\color{orange} (n + 1) \log^2(n + 1) ~ \mathbb{F}_{\mathsf{mul}} } \\
& + {\color{red} \mathbb{F}_{\mathsf{inv}} + (4N - 3) ~ \mathbb{F}_{\mathsf{mul}}} + {\color{red} 3 ~ \mathsf{msm}(N, \mathbb{G}_1)} \\
= & 3 ~ \mathsf{FFT}(N) + (25N + 7n - 6) ~ \mathbb{F}_{\mathsf{mul}} + 3~ \mathbb{F}_{\mathsf{inv}} + 3 ~ \mathsf{msm}(N, \mathbb{G}_1) + {\color{orange} (n + 1) \log^2(n + 1) ~ \mathbb{F}_{\mathsf{mul}} } \\
\end{aligned} = = 2 ( n − 1 ) F mul + n F mul + FFT ( N ) + ( N + 1 ) F mul + ( 12 N + 4 n + 2 ) F mul + ( n + 1 ) l o g 2 ( n + 1 ) F mul + F inv + ( 4 N − 3 ) F mul + 2 FFT ( N ) + F inv + ( 4 N − 3 ) F mul + F inv + ( 4 N − 3 ) F mul + 3 msm ( N , G 1 ) 3 FFT ( N ) + ( 21 N + 7 n − 3 ) F mul + 2 F inv + ( n + 1 ) l o g 2 ( n + 1 ) F mul + F inv + ( 4 N − 3 ) F mul + 3 msm ( N , G 1 ) 3 FFT ( N ) + ( 25 N + 7 n − 6 ) F mul + 3 F inv + 3 msm ( N , G 1 ) + ( n + 1 ) l o g 2 ( n + 1 ) F mul Round 4. ¶ Round 4-1 ¶ Verifier 发送第二个随机挑战点 ξ ← $ F p \xi\leftarrow_{\$}\mathbb{F}_p ξ ← $ F p
Round 4-2 ¶ Prover 构造第三个 Quotient 多项式 q ξ ( X ) q_\xi(X) q ξ ( X )
q ξ ( X ) = c ( X ) − c ∗ ( ξ ) − z D ζ ( ξ ) ⋅ q c ( X ) X − ξ q_\xi(X) = \frac{c(X) - c^*(\xi) - z_{D_\zeta}(\xi)\cdot q_c(X)}{X-\xi} q ξ ( X ) = X − ξ c ( X ) − c ∗ ( ξ ) − z D ζ ( ξ ) ⋅ q c ( X ) Prover Cost 4-2 ¶ c ∗ ( X ) c^*(X) c ∗ ( X ) N − 1 N - 1 N − 1 c ∗ ( ξ ) c^*(\xi) c ∗ ( ξ ) N F m u l N ~ \mathbb{F}_{\mathsf{mul}} N F mul z D ζ ( X ) z_{D_\zeta}(X) z D ζ ( X ) n + 1 n + 1 n + 1 z D ζ ( ξ ) z_{D_\zeta}(\xi) z D ζ ( ξ ) ( n + 2 ) F m u l (n + 2) ~ \mathbb{F}_{\mathsf{mul}} ( n + 2 ) F mul 在 Round 3-9 已经得到 [ q c ( x ) ∣ x ∈ H ] [q_c(x)|_{x \in H}] [ q c ( x ) ∣ x ∈ H ] [ ( z D ζ ( ξ ) ⋅ q c ( x ) ) ∣ x ∈ H ] [(z_{D_\zeta}(\xi)\cdot q_c(x))|_{x \in H}] [( z D ζ ( ξ ) ⋅ q c ( x )) ∣ x ∈ H ] N F m u l N ~ \mathbb{F}_{\mathsf{mul}} N F mul 计算得到 z D ζ ( ξ ) ⋅ q c ( X ) z_{D_\zeta}(\xi)\cdot q_c(X) z D ζ ( ξ ) ⋅ q c ( X ) I F F T ( N ) \mathsf{IFFT}(N) IFFT ( N ) 计算 c ( X ) − c ∗ ( ξ ) − z D ζ ( ξ ) ⋅ q c ( X ) X − ξ \frac{c(X) - c^*(\xi) - z_{D_\zeta}(\xi)\cdot q_c(X)}{X-\xi} X − ξ c ( X ) − c ∗ ( ξ ) − z D ζ ( ξ ) ⋅ q c ( X ) N − 1 N - 1 N − 1 ( N − 1 ) F m u l (N - 1) ~ \mathbb{F}_{\mathsf{mul}} ( N − 1 ) F mul 因此这一步的总复杂度为
I F F T ( N ) + ( 3 N + n + 1 ) F m u l \mathsf{IFFT}(N) + (3N + n + 1) ~ \mathbb{F}_{\mathsf{mul}} IFFT ( N ) + ( 3 N + n + 1 ) F mul Round 4-3 ¶ Prover 计算并发送 Q ξ Q_\xi Q ξ
Q ξ = K Z G 10. C o m m i t ( q ξ ( X ) ) = [ q ξ ( τ ) ] 1 Q_\xi = \mathsf{KZG10.Commit}(q_\xi(X)) = [q_\xi(\tau)]_1 Q ξ = KZG10.Commit ( q ξ ( X )) = [ q ξ ( τ ) ] 1 Prover Cost 4-3 ¶ 前面一步计算得到的是 q ξ ( X ) q_\xi(X) q ξ ( X ) deg ( q ξ ) = N − 2 \deg(q_\xi) = N - 2 deg ( q ξ ) = N − 2 m s m ( N − 1 , G 1 ) \mathsf{msm}(N - 1, \mathbb{G}_1) msm ( N − 1 , G 1 )
这种方法要求内存中要存储 SRS ( G , τ G , … , τ N − 2 G ) (G, \tau G, \ldots, \tau^{N - 2}G) ( G , τ G , … , τ N − 2 G )
Prover Cost Round 4 ¶ 汇总这一轮的复杂度
I F F T ( N ) + ( 3 N + n + 1 ) F m u l + m s m ( N − 1 , G 1 ) \mathsf{IFFT}(N) + (3N + n + 1) ~ \mathbb{F}_{\mathsf{mul}} + \mathsf{msm}(N - 1, \mathbb{G}_1) IFFT ( N ) + ( 3 N + n + 1 ) F mul + msm ( N − 1 , G 1 ) Prover Cost ¶ 汇总所有轮的 Prover Cost
在 Round 3-10 用方法一，系数形式，复杂度为 这种方法要求内存中要存储 SRS ( G , τ G , … , τ N − 2 G ) (G, \tau G, \ldots, \tau^{N - 2}G) ( G , τ G , … , τ N − 2 G )
在 Round 3-10 用方法二，点值形式，复杂度为 ( N − 1 ) F m u l + m s m ( N , G 1 ) + 4 F F T ( N ) + 4 I F F T ( N ) + ( 5 n N + 10 N + n + 2 ) F m u l + 2 m s m ( N , G 1 ) + 3 F F T ( N ) + ( 25 N + 7 n − 6 ) F m u l + 3 F i n v + 3 m s m ( N , G 1 ) + ( n + 1 ) log 2 ( n + 1 ) F m u l + I F F T ( N ) + ( 3 N + n + 1 ) F m u l + m s m ( N − 1 , G 1 ) = ( 17 n N + 39 N + 9 n − 4 ) F m u l + ( n + 1 ) log 2 ( n + 1 ) F m u l + 3 F i n v + 6 m s m ( N , G 1 ) + m s m ( N − 1 , G 1 ) \begin{align}
& {\color{blue} (N - 1) ~ \mathbb{F}_{\mathsf{mul}} + \mathsf{msm}(N, \mathbb{G}_1)} \\
& + {\color{red} 4 ~ \mathsf{FFT}(N) + 4 ~ \mathsf{IFFT}(N) + (5nN + 10N + n + 2) ~ \mathbb{F}_{\mathsf{mul}} + 2 ~ \mathsf{msm}(N, \mathbb{G}_1)} \\
& + 3 ~ \mathsf{FFT}(N) + (25N + 7n - 6) ~ \mathbb{F}_{\mathsf{mul}} + 3~ \mathbb{F}_{\mathsf{inv}} + 3 ~ \mathsf{msm}(N, \mathbb{G}_1) + {\color{orange} (n + 1) \log^2(n + 1) ~ \mathbb{F}_{\mathsf{mul}} } \\
& + {\color{purple}\mathsf{IFFT}(N) + (3N + n + 1) ~ \mathbb{F}_{\mathsf{mul}} + \mathsf{msm}(N - 1, \mathbb{G}_1)} \\
= & (17nN + 39N + 9n - 4) ~ \mathbb{F}_{\mathsf{mul}} + {\color{orange} (n + 1) \log^2(n + 1) ~ \mathbb{F}_{\mathsf{mul}} } + 3~ \mathbb{F}_{\mathsf{inv}} + 6 ~ \mathsf{msm}(N, \mathbb{G}_1) + \mathsf{msm}(N - 1, \mathbb{G}_1)
\end{align} = ( N − 1 ) F mul + msm ( N , G 1 ) + 4 FFT ( N ) + 4 IFFT ( N ) + ( 5 n N + 10 N + n + 2 ) F mul + 2 msm ( N , G 1 ) + 3 FFT ( N ) + ( 25 N + 7 n − 6 ) F mul + 3 F inv + 3 msm ( N , G 1 ) + ( n + 1 ) l o g 2 ( n + 1 ) F mul + IFFT ( N ) + ( 3 N + n + 1 ) F mul + msm ( N − 1 , G 1 ) ( 17 n N + 39 N + 9 n − 4 ) F mul + ( n + 1 ) l o g 2 ( n + 1 ) F mul + 3 F inv + 6 msm ( N , G 1 ) + msm ( N − 1 , G 1 ) 证明表示 ¶ 7 ⋅ G 1 7\cdot\mathbb{G}_1 7 ⋅ G 1 ( n + 1 ) ⋅ F p (n+1)\cdot\mathbb{F}_{p} ( n + 1 ) ⋅ F p
π e v a l = ( z ( ω − 1 ⋅ ζ ) , c ( ζ ) ， c ( ω ⋅ ζ ) , c ( ω 2 ⋅ ζ ) , c ( ω 4 ⋅ ζ ) , … , c ( ω 2 n − 1 ⋅ ζ ) , C c , C t , C z , Q c , Q ζ , Q ξ , Q ω ζ ) \begin{aligned}
\pi_{eval} &= \big(z(\omega^{-1}\cdot\zeta), c(\zeta)，c(\omega\cdot\zeta), c(\omega^2\cdot\zeta), c(\omega^4\cdot\zeta), \ldots, c(\omega^{2^{n-1}}\cdot\zeta), \\
& \qquad C_{c}, C_{t}, C_{z}, Q_c, Q_\zeta, Q_\xi, Q_{\omega\zeta}\big)
\end{aligned} π e v a l = ( z ( ω − 1 ⋅ ζ ) , c ( ζ ) ， c ( ω ⋅ ζ ) , c ( ω 2 ⋅ ζ ) , c ( ω 4 ⋅ ζ ) , … , c ( ω 2 n − 1 ⋅ ζ ) , C c , C t , C z , Q c , Q ζ , Q ξ , Q ω ζ ) 验证过程 ¶ Step 1 ¶ Verifier 计算 c ∗ ( ξ ) c^*(\xi) c ∗ ( ξ ) { w ^ i } \{\hat{w}_i\} { w ^ i } c ∗ ( ξ ) = ∑ i c i ∗ w ^ i ξ − x i ∑ i w ^ i ξ − x i c^*(\xi)=\frac{\sum_i c_i^*\frac{\hat{w}_i}{\xi-x_i}}{\sum_i \frac{\hat{w}_i}{\xi-x_i}} c ∗ ( ξ ) = ∑ i ξ − x i w ^ i ∑ i c i ∗ ξ − x i w ^ i 再计算对应的承诺 C ∗ ( ξ ) = [ c ∗ ( ξ ) ] 1 C^*(\xi)=[c^*(\xi)]_1 C ∗ ( ξ ) = [ c ∗ ( ξ ) ] 1
Verifier Cost 1 ¶ Verifier:
先分析每一项计算的复杂度，计算 w ^ i ξ − x i \frac{\hat{w}_i}{\xi-x_i} ξ − x i w ^ i w ^ i \hat{w}_i w ^ i ξ − x i \xi-x_i ξ − x i w ^ i \hat{w}_i w ^ i F m u l + F i n v \mathbb{F}_{\mathsf{mul}} + \mathbb{F}_{\mathsf{inv}} F mul + F inv 计算 c i ∗ w ^ i ξ − x i c_i^*\frac{\hat{w}_i}{\xi-x_i} c i ∗ ξ − x i w ^ i F m u l \mathbb{F}_{\mathsf{mul}} F mul 最后将分子分母得到有限域上的值相除，其实就是分母的值求逆，再和分子相乘，复杂度为 F m u l + F i n v \mathbb{F}_{\mathsf{mul}} + \mathbb{F}_{\mathsf{inv}} F mul + F inv 计算得到 c ∗ ( ξ ) c^*(\xi) c ∗ ( ξ ) C ∗ ( ξ ) C^*(\xi) C ∗ ( ξ ) E c c M u l G 1 \mathsf{EccMul}^{\mathbb{G}_1} EccMul G 1 因此这一步的总复杂度为
> > ( n + 1 ) ( F m u l + F i n v ) + ( n + 1 ) F m u l + F m u l + F i n v + E c c M u l G 1 > = ( 2 n + 3 ) F m u l + ( n + 2 ) F i n v + E c c M u l G 1 > > > \begin{aligned}
> & (n + 1) ~ (\mathbb{F}_{\mathsf{mul}} + \mathbb{F}_{\mathsf{inv}}) + (n + 1) ~ \mathbb{F}_{\mathsf{mul}} + \mathbb{F}_{\mathsf{mul}} + \mathbb{F}_{\mathsf{inv}} + \mathsf{EccMul}^{\mathbb{G}_1} \\
> = & \color{orange}{(2n + 3) ~ \mathbb{F}_{\mathsf{mul}} + (n + 2) ~ \mathbb{F}_{\mathsf{inv}} + \mathsf{EccMul}^{\mathbb{G}_1}}
> \end{aligned}
> > > >= ( n + 1 ) ( F mul + F inv ) + ( n + 1 ) F mul + F mul + F inv + EccMul G 1 ( 2 n + 3 ) F mul + ( n + 2 ) F inv + EccMul G 1 > > Step 2 ¶ Verifier 计算 v H ( ζ ) , L 0 ( ζ ) , L N − 1 ( ζ ) v_H(\zeta), L_0(\zeta), L_{N-1}(\zeta) v H ( ζ ) , L 0 ( ζ ) , L N − 1 ( ζ )
v H ( ζ ) = ζ N − 1 v_H(\zeta) = \zeta^N - 1 v H ( ζ ) = ζ N − 1 L 0 ( ζ ) = 1 N ⋅ v H ( ζ ) ζ − 1 L_0(\zeta) = \frac{1}{N}\cdot \frac{v_{H}(\zeta)}{\zeta-1} L 0 ( ζ ) = N 1 ⋅ ζ − 1 v H ( ζ ) L N − 1 ( ζ ) = ω N − 1 N ⋅ v H ( ζ ) ζ − ω N − 1 L_{N-1}(\zeta) = \frac{\omega^{N-1}}{N}\cdot \frac{v_{H}(\zeta)}{\zeta-\omega^{N-1}} L N − 1 ( ζ ) = N ω N − 1 ⋅ ζ − ω N − 1 v H ( ζ ) Verifier Cost 2 ¶ Verifier:
v H ( ζ ) v_H(\zeta) v H ( ζ ) ζ N \zeta^N ζ N log N \log N log N log N F m u l \log N ~ \mathbb{F}_{\mathsf{mul}} log N F mul L 0 ( ζ ) L_0(\zeta) L 0 ( ζ ) 1 / N 1/N 1/ N ζ − 1 \zeta-1 ζ − 1 F i n v \mathbb{F}_{\mathsf{inv}} F inv ζ − 1 \zeta-1 ζ − 1 v H ( ζ ) v_{H}(\zeta) v H ( ζ ) F m u l \mathbb{F}_{\mathsf{mul}} F mul 1 / N 1/N 1/ N F m u l \mathbb{F}_{\mathsf{mul}} F mul F i n v + 2 F m u l \mathbb{F}_{\mathsf{inv}} + 2 ~ \mathbb{F}_{\mathsf{mul}} F inv + 2 F mul L N − 1 ( ζ ) L_{N-1}(\zeta) L N − 1 ( ζ ) ω N − 1 / N \omega^{N-1}/N ω N − 1 / N ζ − ω N − 1 \zeta-\omega^{N-1} ζ − ω N − 1 F i n v \mathbb{F}_{\mathsf{inv}} F inv ζ − ω N − 1 \zeta-\omega^{N-1} ζ − ω N − 1 v H ( ζ ) v_{H}(\zeta) v H ( ζ ) F m u l \mathbb{F}_{\mathsf{mul}} F mul ω N − 1 / N \omega^{N-1}/N ω N − 1 / N F m u l \mathbb{F}_{\mathsf{mul}} F mul F i n v + 2 F m u l \mathbb{F}_{\mathsf{inv}} + 2 ~ \mathbb{F}_{\mathsf{mul}} F inv + 2 F mul 因此这一步的总复杂度为 2 F i n v + ( log N + 4 ) F m u l 2 ~ \mathbb{F}_{\mathsf{inv}} + (\log N + 4) ~ \mathbb{F}_{\mathsf{mul}} 2 F inv + ( log N + 4 ) F mul
Step 3 ¶ Verifier 计算 s 0 ( ζ ) , … , s n − 1 ( ζ ) s_0(\zeta), \ldots, s_{n-1}(\zeta) s 0 ( ζ ) , … , s n − 1 ( ζ )
Verifier Cost 3 ¶ ζ 2 , ζ 4 , … , ζ 2 n − 1 \zeta^2, \zeta^4, \ldots, \zeta^{2^{n - 1}} ζ 2 , ζ 4 , … , ζ 2 n − 1 ζ N \zeta^N ζ N 剩下求值与在 Round 3-1 的分析一致，这一步的复杂度为 ( n − 1 ) F m u l (n - 1) ~ \mathbb{F}_{\mathsf{mul}} ( n − 1 ) F mul Step 4 ¶ Verifier 计算 z D ζ ( ξ ) z_{D_\zeta}(\xi) z D ζ ( ξ )
z D ζ ( ξ ) = ( ξ − ζ ω ) ⋯ ( ξ − ζ ω 2 n − 1 ) ( ξ − ζ ) z_{D_{\zeta}}(\xi) = (\xi-\zeta\omega)\cdots (\xi-\zeta\omega^{2^{n-1}})(\xi-\zeta) z D ζ ( ξ ) = ( ξ − ζ ω ) ⋯ ( ξ − ζ ω 2 n − 1 ) ( ξ − ζ ) Verifier Cost 4 ¶ Verifier:
ξ − ζ ω i \xi-\zeta\omega^i ξ − ζ ω i n n n ( n − 1 ) F m u l (n - 1) ~ \mathbb{F}_{\mathsf{mul}} ( n − 1 ) F mul
Step 5 ¶ Verifier 计算线性化多项式的承诺 C l C_l C l
C l = ( ( ( c ( ζ ) − c 0 ) s 0 ( ζ ) + α ⋅ ( u n − 1 ⋅ c ( ζ ) − ( 1 − u n − 1 ) ⋅ c ( ω 2 n − 1 ⋅ ζ ) ) ⋅ s 0 ( ζ ) + α 2 ⋅ ( u n − 2 ⋅ c ( ζ ) − ( 1 − u n − 2 ) ⋅ c ( ω 2 n − 2 ⋅ ζ ) ) ⋅ s 1 ( ζ ) + ⋯ + α n − 1 ⋅ ( u 1 ⋅ c ( ζ ) − ( 1 − u 1 ) ⋅ c ( ω 2 ⋅ ζ ) ) ⋅ s n − 2 ( ζ ) + α n ⋅ ( u 0 ⋅ c ( ζ ) − ( 1 − u 0 ) ⋅ c ( ω ⋅ ζ ) ) ⋅ s n − 1 ( ζ ) ) ⋅ [ 1 ] 1 + α n + 1 ⋅ L 0 ( ζ ) ⋅ ( C z − c 0 ⋅ C a ) + α n + 2 ⋅ ( ζ − 1 ) ⋅ ( C z − z ( ω − 1 ⋅ ζ ) ⋅ [ 1 ] 1 − c ( ζ ) ⋅ C a ) + α n + 3 ⋅ L N − 1 ( ζ ) ⋅ ( C z − v ⋅ [ 1 ] 1 ) − v H ( ζ ) ⋅ C t ) \begin{split}
C_l & =
\Big( \Big((c(\zeta) - c_0)s_0(\zeta) \\
& + \alpha \cdot (u_{n-1}\cdot c(\zeta) - (1-u_{n-1})\cdot c(\omega^{2^{n-1}}\cdot\zeta))\cdot s_0(\zeta)\\
& + \alpha^2\cdot (u_{n-2}\cdot c(\zeta) - (1-u_{n-2})\cdot c(\omega^{2^{n-2}}\cdot\zeta))\cdot s_1(\zeta) \\
& + \cdots \\
& + \alpha^{n-1}\cdot (u_{1}\cdot c(\zeta) - (1-u_{1})\cdot c(\omega^2\cdot\zeta))\cdot s_{n-2}(\zeta)\\
& + \alpha^n\cdot (u_{0}\cdot c(\zeta) - (1-u_{0})\cdot c(\omega\cdot\zeta))\cdot s_{n-1}(\zeta) \Big) \cdot [1]_1 \\
& + \alpha^{n+1}\cdot L_0(\zeta)\cdot(C_z - c_0\cdot C_a)\\
& + \alpha^{n+2}\cdot (\zeta-1)\cdot\big(C_z - z(\omega^{-1}\cdot \zeta)\cdot [1]_1-c(\zeta)\cdot C_{a} ) \\
& + \alpha^{n+3}\cdot L_{N-1}(\zeta)\cdot(C_z - v \cdot [1]_1) \\
& - v_H(\zeta)\cdot C_t \Big)
\end{split} C l = ( ( ( c ( ζ ) − c 0 ) s 0 ( ζ ) + α ⋅ ( u n − 1 ⋅ c ( ζ ) − ( 1 − u n − 1 ) ⋅ c ( ω 2 n − 1 ⋅ ζ )) ⋅ s 0 ( ζ ) + α 2 ⋅ ( u n − 2 ⋅ c ( ζ ) − ( 1 − u n − 2 ) ⋅ c ( ω 2 n − 2 ⋅ ζ )) ⋅ s 1 ( ζ ) + ⋯ + α n − 1 ⋅ ( u 1 ⋅ c ( ζ ) − ( 1 − u 1 ) ⋅ c ( ω 2 ⋅ ζ )) ⋅ s n − 2 ( ζ ) + α n ⋅ ( u 0 ⋅ c ( ζ ) − ( 1 − u 0 ) ⋅ c ( ω ⋅ ζ )) ⋅ s n − 1 ( ζ ) ) ⋅ [ 1 ] 1 + α n + 1 ⋅ L 0 ( ζ ) ⋅ ( C z − c 0 ⋅ C a ) + α n + 2 ⋅ ( ζ − 1 ) ⋅ ( C z − z ( ω − 1 ⋅ ζ ) ⋅ [ 1 ] 1 − c ( ζ ) ⋅ C a ) + α n + 3 ⋅ L N − 1 ( ζ ) ⋅ ( C z − v ⋅ [ 1 ] 1 ) − v H ( ζ ) ⋅ C t ) Verifier Cost 5 ¶ Verifier:
先计算 α 2 , … , α n + 3 \alpha^2, \ldots, \alpha^{n+3} α 2 , … , α n + 3 n + 2 n + 2 n + 2 ( n + 2 ) F m u l (n + 2) ~ \mathbb{F}_{\mathsf{mul}} ( n + 2 ) F mul s 0 ( ζ ) ⋅ ( c ( ζ ) − c 0 ) s_0(\zeta) \cdot (c(\zeta) - c_0) s 0 ( ζ ) ⋅ ( c ( ζ ) − c 0 ) F m u l \mathbb{F}_{\mathsf{mul}} F mul α ⋅ s 0 ( ζ ) ⋅ ( u n − 1 ⋅ c ( ζ ) − ( 1 − u n − 1 ) ⋅ c ( ω 2 n − 1 ⋅ ζ ) ) \alpha \cdot s_0(\zeta) \cdot (u_{n-1}\cdot c(\zeta) - (1-u_{n-1})\cdot c(\omega^{2^{n-1}}\cdot\zeta)) α ⋅ s 0 ( ζ ) ⋅ ( u n − 1 ⋅ c ( ζ ) − ( 1 − u n − 1 ) ⋅ c ( ω 2 n − 1 ⋅ ζ )) 4 F m u l 4 ~ \mathbb{F}_{\mathsf{mul}} 4 F mul n + 1 n + 1 n + 1 4 n F m u l 4n ~ \mathbb{F}_{\mathsf{mul}} 4 n F mul 将上面计算的结果相加得到一个有限域的值，再与 [ 1 ] 1 [1]_1 [ 1 ] 1 E c c M u l G 1 \mathsf{EccMul}^{\mathbb{G}_1} EccMul G 1 α n + 1 ⋅ L 0 ( ζ ) ⋅ ( C z − c 0 ⋅ C a ) \alpha^{n+1}\cdot L_0(\zeta)\cdot(C_z - c_0\cdot C_a) α n + 1 ⋅ L 0 ( ζ ) ⋅ ( C z − c 0 ⋅ C a ) c 0 ⋅ C a c_0\cdot C_a c 0 ⋅ C a E c c M u l G 1 \mathsf{EccMul}^{\mathbb{G}_1} EccMul G 1
C z − c 0 ⋅ C a C_z - c_0\cdot C_a C z − c 0 ⋅ C a P 1 − P 2 = P 1 + ( − P 2 ) P_1 - P_2 = P_1 + (-P_2) P 1 − P 2 = P 1 + ( − P 2 ) P 2 = ( x 2 , y 2 ) P_2 = (x_2, y_2) P 2 = ( x 2 , y 2 ) − P 2 = ( x 2 , − y 2 ) -P_2 = (x_2, -y_2) − P 2 = ( x 2 , − y 2 ) x 2 , y 2 x_2, y_2 x 2 , y 2 E c c A d d G 1 \mathsf{EccAdd}^{\mathbb{G}_1} EccAdd G 1
📝 关于椭圆曲线上的加法或减法 python 实现可参考 py_ecc 。
α n + 1 ⋅ L 0 ( ζ ) \alpha^{n+1}\cdot L_0(\zeta) α n + 1 ⋅ L 0 ( ζ ) F m u l \mathbb{F}_{\mathsf{mul}} F mul
α n + 1 ⋅ L 0 ( ζ ) ⋅ ( C z − c 0 ⋅ C a ) \alpha^{n+1}\cdot L_0(\zeta)\cdot(C_z - c_0\cdot C_a) α n + 1 ⋅ L 0 ( ζ ) ⋅ ( C z − c 0 ⋅ C a ) E c c M u l G 1 \mathsf{EccMul}^{\mathbb{G}_1} EccMul G 1
因此计算这一步的总复杂度为 F m u l + 2 E c c M u l G 1 + E c c A d d G 1 \mathbb{F}_{\mathsf{mul}} + 2 ~ \mathsf{EccMul}^{\mathbb{G}_1} + \mathsf{EccAdd}^{\mathbb{G}_1} F mul + 2 EccMul G 1 + EccAdd G 1
α n + 2 ⋅ ( ζ − 1 ) ⋅ ( C z − z ( ω − 1 ⋅ ζ ) ⋅ [ 1 ] 1 − c ( ζ ) ⋅ C a ) \alpha^{n+2}\cdot (\zeta-1)\cdot\big(C_z - z(\omega^{-1}\cdot \zeta)\cdot [1]_1-c(\zeta)\cdot C_{a} \big) α n + 2 ⋅ ( ζ − 1 ) ⋅ ( C z − z ( ω − 1 ⋅ ζ ) ⋅ [ 1 ] 1 − c ( ζ ) ⋅ C a ) c ( ζ ) ⋅ C a c(\zeta)\cdot C_{a} c ( ζ ) ⋅ C a E c c M u l G 1 \mathsf{EccMul}^{\mathbb{G}_1} EccMul G 1 z ( ω − 1 ⋅ ζ ) ⋅ [ 1 ] 1 z(\omega^{-1}\cdot \zeta)\cdot [1]_1 z ( ω − 1 ⋅ ζ ) ⋅ [ 1 ] 1 E c c M u l G 1 \mathsf{EccMul}^{\mathbb{G}_1} EccMul G 1 C z − z ( ω − 1 ⋅ ζ ) ⋅ [ 1 ] 1 − c ( ζ ) ⋅ C a C_z - z(\omega^{-1}\cdot \zeta)\cdot [1]_1-c(\zeta)\cdot C_{a} C z − z ( ω − 1 ⋅ ζ ) ⋅ [ 1 ] 1 − c ( ζ ) ⋅ C a 2 E c c A d d G 1 2 ~\mathsf{EccAdd}^{\mathbb{G}_1} 2 EccAdd G 1 α n + 2 ⋅ ( ζ − 1 ) \alpha^{n+2}\cdot (\zeta-1) α n + 2 ⋅ ( ζ − 1 ) F m u l \mathbb{F}_{\mathsf{mul}} F mul α n + 2 ⋅ ( ζ − 1 ) ⋅ ( C z − z ( ω − 1 ⋅ ζ ) ⋅ [ 1 ] 1 − c ( ζ ) ⋅ C a ) \alpha^{n+2}\cdot (\zeta-1)\cdot\big(C_z - z(\omega^{-1}\cdot \zeta)\cdot [1]_1-c(\zeta)\cdot C_{a} \big) α n + 2 ⋅ ( ζ − 1 ) ⋅ ( C z − z ( ω − 1 ⋅ ζ ) ⋅ [ 1 ] 1 − c ( ζ ) ⋅ C a ) E c c M u l G 1 \mathsf{EccMul}^{\mathbb{G}_1} EccMul G 1 总计： F m u l + 3 E c c M u l G 1 + 2 E c c A d d G 1 \mathbb{F}_{\mathsf{mul}} + 3~\mathsf{EccMul}^{\mathbb{G}_1} + 2 ~\mathsf{EccAdd}^{\mathbb{G}_1} F mul + 3 EccMul G 1 + 2 EccAdd G 1 α n + 3 ⋅ L N − 1 ( ζ ) ⋅ ( C z − v ⋅ [ 1 ] 1 ) \alpha^{n+3}\cdot L_{N-1}(\zeta)\cdot(C_z - v \cdot [1]_1) α n + 3 ⋅ L N − 1 ( ζ ) ⋅ ( C z − v ⋅ [ 1 ] 1 ) v ⋅ [ 1 ] 1 v \cdot [1]_1 v ⋅ [ 1 ] 1 E c c M u l G 1 \mathsf{EccMul}^{\mathbb{G}_1} EccMul G 1 C z − v ⋅ [ 1 ] 1 C_z - v \cdot [1]_1 C z − v ⋅ [ 1 ] 1 E c c A d d G 1 \mathsf{EccAdd}^{\mathbb{G}_1} EccAdd G 1 α n + 3 ⋅ L N − 1 ( ζ ) ⋅ ( C z − v ⋅ [ 1 ] 1 ) \alpha^{n+3}\cdot L_{N-1}(\zeta)\cdot(C_z - v \cdot [1]_1) α n + 3 ⋅ L N − 1 ( ζ ) ⋅ ( C z − v ⋅ [ 1 ] 1 ) F m u l + E c c M u l G 1 \mathbb{F}_{\mathsf{mul}} + \mathsf{EccMul}^{\mathbb{G}_1} F mul + EccMul G 1 总计： F m u l + 2 E c c M u l G 1 + E c c A d d G 1 \mathbb{F}_{\mathsf{mul}} + 2~\mathsf{EccMul}^{\mathbb{G}_1} + \mathsf{EccAdd}^{\mathbb{G}_1} F mul + 2 EccMul G 1 + EccAdd G 1 v H ( ζ ) ⋅ C t v_H(\zeta)\cdot C_t v H ( ζ ) ⋅ C t E c c M u l G 1 \mathsf{EccMul}^{\mathbb{G}_1} EccMul G 1 将上面所有结果相加，涉及椭圆曲线上 4 次加法，复杂度为 4 E c c A d d G 1 4 ~ \mathsf{EccAdd}^{\mathbb{G}_1} 4 EccAdd G 1 因此，在这一步计算 l ζ ( X ) l_{\zeta}(X) l ζ ( X )
> > ( n + 2 + 1 + 4 n ) F m u l + E c c M u l G 1 > + F m u l + 2 E c c M u l G 1 + E c c A d d G 1 > + F m u l + 3 E c c M u l G 1 + 2 E c c A d d G 1 > + F m u l + 2 E c c M u l G 1 + E c c A d d G 1 > + E c c M u l G 1 + 4 E c c A d d G 1 > = ( 5 n + 6 ) F m u l + 9 E c c M u l G 1 + 8 E c c A d d G 1 > > > \begin{aligned}
> & (n + 2 + 1 + 4n) ~ \mathbb{F}_{\mathsf{mul}} + \mathsf{EccMul}^{\mathbb{G}_1} \\
> & + \mathbb{F}_{\mathsf{mul}} + 2~\mathsf{EccMul}^{\mathbb{G}_1} + \mathsf{EccAdd}^{\mathbb{G}_1} \\
> & + \mathbb{F}_{\mathsf{mul}} + 3~\mathsf{EccMul}^{\mathbb{G}_1} + 2 ~\mathsf{EccAdd}^{\mathbb{G}_1} \\
> & + \mathbb{F}_{\mathsf{mul}} + 2~\mathsf{EccMul}^{\mathbb{G}_1} + \mathsf{EccAdd}^{\mathbb{G}_1} \\
> & + \mathsf{EccMul}^{\mathbb{G}_1} + 4 ~ \mathsf{EccAdd}^{\mathbb{G}_1} \\
> = & (5n + 6) ~ \mathbb{F}_{\mathsf{mul}} + 9 ~ \mathsf{EccMul}^{\mathbb{G}_1} + 8 ~ \mathsf{EccAdd}^{\mathbb{G}_1}
> \end{aligned}
> > > > > > > >= ( n + 2 + 1 + 4 n ) F mul + EccMul G 1 + F mul + 2 EccMul G 1 + EccAdd G 1 + F mul + 3 EccMul G 1 + 2 EccAdd G 1 + F mul + 2 EccMul G 1 + EccAdd G 1 + EccMul G 1 + 4 EccAdd G 1 ( 5 n + 6 ) F mul + 9 EccMul G 1 + 8 EccAdd G 1 > > Step 6 ¶ Verifier 产生随机数 η \eta η
e ( C l + ζ ⋅ Q ζ , [ 1 ] 2 ) = ? e ( Q ζ , [ τ ] 2 ) e ( C c − C ∗ ( ξ ) − z D ζ ( ξ ) ⋅ Q c + ξ ⋅ Q ξ , [ 1 ] 2 ) = ? e ( Q ξ , [ τ ] 2 ) e ( C z + ζ ⋅ Q ω ζ − z ( ω − 1 ⋅ ζ ) ⋅ [ 1 ] 1 , [ 1 ] 2 ) = ? e ( Q ω ζ , [ τ ] 2 ) \begin{split}
e(C_l + \zeta\cdot Q_\zeta, [1]_2)\overset{?}{=}e(Q_\zeta, [\tau]_2)\\
e(C_c - C^*(\xi) - z_{D_\zeta}(\xi)\cdot Q_c + \xi\cdot Q_\xi, [1]_2) \overset{?}{=} e(Q_\xi, [\tau]_2)\\
e(C_z + \zeta\cdot Q_{\omega\zeta} - z(\omega^{-1}\cdot\zeta)\cdot[1]_1, [1]_2) \overset{?}{=} e(Q_{\omega\zeta}, [\tau]_2)\\
\end{split} e ( C l + ζ ⋅ Q ζ , [ 1 ] 2 ) = ? e ( Q ζ , [ τ ] 2 ) e ( C c − C ∗ ( ξ ) − z D ζ ( ξ ) ⋅ Q c + ξ ⋅ Q ξ , [ 1 ] 2 ) = ? e ( Q ξ , [ τ ] 2 ) e ( C z + ζ ⋅ Q ω ζ − z ( ω − 1 ⋅ ζ ) ⋅ [ 1 ] 1 , [ 1 ] 2 ) = ? e ( Q ω ζ , [ τ ] 2 ) 合并后的验证只需要两个 Pairing 运算。
$$
\begin{split}
P &= \Big(C_l + \zeta\cdot Q_\zeta\Big) \
& + \eta\cdot \Big(C_c - C^*(\xi) - z_{D_\zeta}(\xi)\cdot Q_c + \xi\cdot Q_\xi\Big) \
& + \eta^2\cdot\Big(C_z + \zeta\cdot Q_{\omega\zeta} - z(\omega^{-1}\cdot\zeta)\cdot[1]_1\Big)
\end{split}
$$
e ( P , [ 1 ] 2 ) = ? e ( Q ζ + η ⋅ Q ξ + η 2 ⋅ Q ω ζ , [ τ ] 2 ) e\Big(P, [1]_2\Big) \overset{?}{=} e\Big(Q_\zeta + \eta\cdot Q_\xi + \eta^2\cdot Q_{\omega\zeta}, [\tau]_2\Big) e ( P , [ 1 ] 2 ) = ? e ( Q ζ + η ⋅ Q ξ + η 2 ⋅ Q ω ζ , [ τ ] 2 ) Verifier Cost 6 ¶ Verifier:
可以先计算出 η 2 \eta^2 η 2 F m u l \mathbb{F}_{\mathsf{mul}} F mul
( C l + ζ ⋅ Q ζ ) \Big(C_l + \zeta\cdot Q_\zeta\Big) ( C l + ζ ⋅ Q ζ ) E c c M u l G 1 + E c c A d d G 1 \mathsf{EccMul}^{\mathbb{G}_1} + \mathsf{EccAdd}^{\mathbb{G}_1} EccMul G 1 + EccAdd G 1
η ⋅ ( C c − C ∗ ( ξ ) − z D ζ ( ξ ) ⋅ Q c + ξ ⋅ Q ξ ) \eta\cdot \Big(C_c - C^*(\xi) - z_{D_\zeta}(\xi)\cdot Q_c + \xi\cdot Q_\xi\Big) η ⋅ ( C c − C ∗ ( ξ ) − z D ζ ( ξ ) ⋅ Q c + ξ ⋅ Q ξ )
> 2 E c c M u l G 1 + 3 E c c A d d G 1 + E c c M u l G 1 = 3 E c c M u l G 1 + 3 E c c A d d G 1 > > 2 ~ \mathsf{EccMul}^{\mathbb{G}_1} + 3 ~ \mathsf{EccAdd}^{\mathbb{G}_1} + \mathsf{EccMul}^{\mathbb{G}_1} = 3 ~ \mathsf{EccMul}^{\mathbb{G}_1} + 3 ~ \mathsf{EccAdd}^{\mathbb{G}_1}
> > 2 EccMul G 1 + 3 EccAdd G 1 + EccMul G 1 = 3 EccMul G 1 + 3 EccAdd G 1 > η 2 ⋅ ( C z + ζ ⋅ Q ω ζ − z ( ω − 1 ⋅ ζ ) ⋅ [ 1 ] 1 ) \eta^2\cdot\Big(C_z + \zeta\cdot Q_{\omega\zeta} - z(\omega^{-1}\cdot\zeta)\cdot[1]_1\Big) η 2 ⋅ ( C z + ζ ⋅ Q ω ζ − z ( ω − 1 ⋅ ζ ) ⋅ [ 1 ] 1 ) 3 E c c M u l G 1 + 2 E c c A d d G 1 3 ~\mathsf{EccMul}^{\mathbb{G}_1} + 2~\mathsf{EccAdd}^{\mathbb{G}_1} 3 EccMul G 1 + 2 EccAdd G 1
计算 P P P 2 E c c A d d G 1 2 ~ \mathsf{EccAdd}^{\mathbb{G}_1} 2 EccAdd G 1
e ( P , [ 1 ] 2 ) e\Big(P, [1]_2\Big) e ( P , [ 1 ] 2 ) P P P
Q ζ + η ⋅ Q ξ + η 2 ⋅ Q ω ζ Q_\zeta + \eta\cdot Q_\xi + \eta^2\cdot Q_{\omega\zeta} Q ζ + η ⋅ Q ξ + η 2 ⋅ Q ω ζ 2 E c c M u l G 1 + 2 E c c A d d G 1 2 ~\mathsf{EccMul}^{\mathbb{G}_1} + 2 ~ \mathsf{EccAdd}^{\mathbb{G}_1} 2 EccMul G 1 + 2 EccAdd G 1
e ( Q ζ + η ⋅ Q ξ + η 2 ⋅ Q ω ζ , [ τ ] 2 ) e\Big(Q_\zeta + \eta\cdot Q_\xi + \eta^2\cdot Q_{\omega\zeta}, [\tau]_2\Big) e ( Q ζ + η ⋅ Q ξ + η 2 ⋅ Q ω ζ , [ τ ] 2 ) P P P
将上面的所有结果相加，得到这一步的总复杂度为
> > F m u l + E c c M u l G 1 + E c c A d d G 1 > + 3 E c c M u l G 1 + 3 E c c A d d G 1 > + 3 E c c M u l G 1 + 2 E c c A d d G 1 > + 2 E c c A d d G 1 + P + 2 E c c M u l G 1 + P > = F m u l + 9 E c c M u l G 1 + 8 E c c A d d G 1 + 2 P > > > \begin{aligned}
> & \mathbb{F}_{\mathsf{mul}} + \mathsf{EccMul}^{\mathbb{G}_1} + \mathsf{EccAdd}^{\mathbb{G}_1} \\
> & + 3 ~ \mathsf{EccMul}^{\mathbb{G}_1} + 3 ~ \mathsf{EccAdd}^{\mathbb{G}_1} \\
> & + 3 ~\mathsf{EccMul}^{\mathbb{G}_1} + 2~\mathsf{EccAdd}^{\mathbb{G}_1} \\
> & + 2 ~ \mathsf{EccAdd}^{\mathbb{G}_1} + P + 2 ~\mathsf{EccMul}^{\mathbb{G}_1} + P \\
> = & \mathbb{F}_{\mathsf{mul}} + 9 ~ \mathsf{EccMul}^{\mathbb{G}_1} + 8 ~ \mathsf{EccAdd}^{\mathbb{G}_1} + 2 ~ P
> \end{aligned}
> > > > > > >= F mul + EccMul G 1 + EccAdd G 1 + 3 EccMul G 1 + 3 EccAdd G 1 + 3 EccMul G 1 + 2 EccAdd G 1 + 2 EccAdd G 1 + P + 2 EccMul G 1 + P F mul + 9 EccMul G 1 + 8 EccAdd G 1 + 2 P > > Verifier Cost ¶ ( 2 n + 3 ) F m u l + ( n + 2 ) F i n v + E c c M u l G 1 + 2 F i n v + ( log N + 4 ) F m u l + 2 ( n − 1 ) F m u l + ( n − 1 ) F m u l + ( 5 n + 6 ) F m u l + 9 E c c M u l G 1 + 8 E c c A d d G 1 + F m u l + 9 E c c M u l G 1 + 8 E c c A d d G 1 + 2 P = ( 9 n + 8 ) F m u l + 2 F i n v + 18 E c c M u l G 1 + 16 E c c A d d G 1 + 2 P + ( 2 n + 3 ) F m u l + ( n + 2 ) F i n v + E c c M u l G 1 = ( 11 n + 11 ) F m u l + ( n + 4 ) F i n v + 19 E c c M u l G 1 + 16 E c c A d d G 1 + 2 P \begin{aligned}
& {\color{orange} (2n + 3) ~ \mathbb{F}_{\mathsf{mul}} + (n + 2) ~ \mathbb{F}_{\mathsf{inv}} + \mathsf{EccMul}^{\mathbb{G}_1}} \\
& + 2 ~ \mathbb{F}_{\mathsf{inv}} + (\log N + 4) ~ \mathbb{F}_{\mathsf{mul}} \\
& + 2(n - 1) ~ \mathbb{F}_{\mathsf{mul}} \\
& + (n - 1) ~ \mathbb{F}_{\mathsf{mul}} \\
& + (5n + 6) ~ \mathbb{F}_{\mathsf{mul}} + 9 ~ \mathsf{EccMul}^{\mathbb{G}_1} + 8 ~ \mathsf{EccAdd}^{\mathbb{G}_1} \\
& + \mathbb{F}_{\mathsf{mul}} + 9 ~ \mathsf{EccMul}^{\mathbb{G}_1} + 8 ~ \mathsf{EccAdd}^{\mathbb{G}_1} + 2 ~ P \\
= & (9n + 8) ~ \mathbb{F}_{\mathsf{mul}} + 2 ~ \mathbb{F}_{\mathsf{inv}} + 18 ~ \mathsf{EccMul}^{\mathbb{G}_1} + 16 ~ \mathsf{EccAdd}^{\mathbb{G}_1} + 2 ~ P \\
& + {\color{orange} (2n + 3) ~ \mathbb{F}_{\mathsf{mul}} + (n + 2) ~ \mathbb{F}_{\mathsf{inv}} + \mathsf{EccMul}^{\mathbb{G}_1}} \\
= & (11n + 11) ~ \mathbb{F}_{\mathsf{mul}} + (n + 4) ~ \mathbb{F}_{\mathsf{inv}} + 19 ~ \mathsf{EccMul}^{\mathbb{G}_1} + 16 ~ \mathsf{EccAdd}^{\mathbb{G}_1} + 2 ~ P
\end{aligned} = = ( 2 n + 3 ) F mul + ( n + 2 ) F inv + EccMul G 1 + 2 F inv + ( log N + 4 ) F mul + 2 ( n − 1 ) F mul + ( n − 1 ) F mul + ( 5 n + 6 ) F mul + 9 EccMul G 1 + 8 EccAdd G 1 + F mul + 9 EccMul G 1 + 8 EccAdd G 1 + 2 P ( 9 n + 8 ) F mul + 2 F inv + 18 EccMul G 1 + 16 EccAdd G 1 + 2 P + ( 2 n + 3 ) F mul + ( n + 2 ) F inv + EccMul G 1 ( 11 n + 11 ) F mul + ( n + 4 ) F inv + 19 EccMul G 1 + 16 EccAdd G 1 + 2 P 协议复杂度汇总 ¶ Commit Phase ¶ Prover’s cost:
N log N F m u l + m s m ( N , G 1 ) N\log N ~\mathbb{F}_{\mathsf{mul}} + \mathsf{msm}(N, \mathbb{G}_1) N log N F mul + msm ( N , G 1 ) Evaluation Protocol ¶ Prover’s cost:
在 Round 3-10 用方法一，系数形式，复杂度为 ( 17 n N + 36 N + 9 n − 2 ) F m u l + ( n + 1 ) log 2 ( n + 1 ) F m u l + 2 F i n v + 5 m s m ( N , G 1 ) + 2 m s m ( N − 1 , G 1 ) \begin{align}
(17nN + 36N + 9n - 2) ~ \mathbb{F}_{\mathsf{mul}} + {\color{orange} (n + 1) \log^2(n + 1) ~ \mathbb{F}_{\mathsf{mul}} } + 2~ \mathbb{F}_{\mathsf{inv}} + 5 ~ \mathsf{msm}(N, \mathbb{G}_1) + 2 ~ \mathsf{msm}(N - 1, \mathbb{G}_1)
\end{align} ( 17 n N + 36 N + 9 n − 2 ) F mul + ( n + 1 ) l o g 2 ( n + 1 ) F mul + 2 F inv + 5 msm ( N , G 1 ) + 2 msm ( N − 1 , G 1 ) 这种方法要求内存中要存储 SRS ( G , τ G , … , τ N − 2 G ) (G, \tau G, \ldots, \tau^{N - 2}G) ( G , τ G , … , τ N − 2 G )
在 Round 3-10 用方法二，点值形式，复杂度为 ( 17 n N + 39 N + 9 n − 4 ) F m u l + ( n + 1 ) log 2 ( n + 1 ) F m u l + 3 F i n v + 6 m s m ( N , G 1 ) + m s m ( N − 1 , G 1 ) \begin{align}
(17nN + 39N + 9n - 4) ~ \mathbb{F}_{\mathsf{mul}} + {\color{orange} (n + 1) \log^2(n + 1) ~ \mathbb{F}_{\mathsf{mul}} } + 3~ \mathbb{F}_{\mathsf{inv}} + 6 ~ \mathsf{msm}(N, \mathbb{G}_1) + \mathsf{msm}(N - 1, \mathbb{G}_1)
\end{align} ( 17 n N + 39 N + 9 n − 4 ) F mul + ( n + 1 ) l o g 2 ( n + 1 ) F mul + 3 F inv + 6 msm ( N , G 1 ) + msm ( N − 1 , G 1 ) Verifier’s cost:
( 11 n + 11 ) F m u l + ( n + 4 ) F i n v + 19 E c c M u l G 1 + 16 E c c A d d G 1 + 2 P (11n + 11) ~ \mathbb{F}_{\mathsf{mul}} + (n + 4) ~ \mathbb{F}_{\mathsf{inv}} + 19 ~ \mathsf{EccMul}^{\mathbb{G}_1} + 16 ~ \mathsf{EccAdd}^{\mathbb{G}_1} + 2 ~ P ( 11 n + 11 ) F mul + ( n + 4 ) F inv + 19 EccMul G 1 + 16 EccAdd G 1 + 2 P Proof size:
( n + 1 ) ⋅ F p + 7 G 1 (n + 1) \cdot \mathbb{F}_p + 7 ~ \mathbb{G}_1 ( n + 1 ) ⋅ F p + 7 G 1