在第一部分中， 我们介绍了 Gemini [BCH+22] 中实现多元多项式求值证明的 Tensor product 检查协议，并简要说明了如何将它应用到实际证明系统中来实现多元多项式到一元多项式的转换。 这一部分，我们主要关注 Tensor product 检查协议安全性，并在 Gemini 的基础上提出了一些优化。
方便阅读，我们先回顾一下 tensor product 检查协议的流程：
【Tensor-product 检查协议】
目标关系：⟨ f ⃗ , ⊗ j = 0 n − 1 ( 1 , ρ j ) ⟩ = u \langle\vec{f}, \otimes_{j=0}^{n-1}(1,\rho_j) \rangle = u ⟨ f , ⊗ j = 0 n − 1 ( 1 , ρ j )⟩ = u
证明者输入：公共参数，实例 x = ( ρ 0 , . . . , ρ n − 1 , u ) x = (\rho_0,...,\rho_{n-1}, u) x = ( ρ 0 , ... , ρ n − 1 , u ) w = f ⃗ w = \vec{f} w = f
验证者输入：公共参数，实例 x = ( ρ 0 , . . . , ρ n − 1 , u ) x = (\rho_0,...,\rho_{n-1}, u) x = ( ρ 0 , ... , ρ n − 1 , u )
证明者构造一元多项式 f ( 0 ) ( X ) = f ( X ) f^{(0)}(X) = f(X) f ( 0 ) ( X ) = f ( X ) 对 j ∈ 1 , . . . , n j \in 1,...,n j ∈ 1 , ... , n f ( j ) ( X ) = f e ( j − 1 ) ( X ) + ρ j − 1 ⋅ f o ( j − 1 ) ( X ) f^{(j)}(X) = f_e^{(j-1)}(X) + \rho_{j-1} \cdot f_o^{(j-1)}(X) f ( j ) ( X ) = f e ( j − 1 ) ( X ) + ρ j − 1 ⋅ f o ( j − 1 ) ( X ) 其中 f e ( j − 1 ) , f o ( j − 1 ) f_e^{(j-1)}, f_o^{(j-1)} f e ( j − 1 ) , f o ( j − 1 ) f ( j − 1 ) f^{(j-1)} f ( j − 1 ) f ( j − 1 ) ( X ) = f e ( j − 1 ) ( X 2 ) + X ⋅ f o ( j − 1 ) ( X 2 ) f^{(j-1)}(X) = f_e^{(j-1)}(X^2) + X \cdot f_o^{(j-1)}(X^2) f ( j − 1 ) ( X ) = f e ( j − 1 ) ( X 2 ) + X ⋅ f o ( j − 1 ) ( X 2 )
证明者向验证者发送 f ( 0 ) , f ( 1 ) , . . . , f ( n − 1 ) f^{(0)},f^{(1)},...,f^{(n-1)} f ( 0 ) , f ( 1 ) , ... , f ( n − 1 ) 验证者随机选取挑战值 β ← F \beta \leftarrow \mathbb{F} β ← F e ( j − 1 ) : = f ( j − 1 ) ( β ) , e ˉ ( j − 1 ) : = f ( j − 1 ) ( − β ) , e ^ ( j − 1 ) : = f ( j ) ( β 2 ) e^{(j-1)}:= f^{(j-1)}(\beta), \bar{e}^{(j-1)} := f^{(j-1)}(-\beta), \hat{e}^{(j-1)} := f^{(j)}(\beta^2) e ( j − 1 ) := f ( j − 1 ) ( β ) , e ˉ ( j − 1 ) := f ( j − 1 ) ( − β ) , e ^ ( j − 1 ) := f ( j ) ( β 2 ) 其中 j = 1 , . . . , n j=1,...,n j = 1 , ... , n j = n j=n j = n f ( n ) ( β 2 ) f^{(n)}(\beta^2) f ( n ) ( β 2 ) e ^ ( n − 1 ) : = u \hat{e}^{(n-1)} := u e ^ ( n − 1 ) := u
对 j = 0 , . . . , n − 1 j = 0,...,n-1 j = 0 , ... , n − 1 e ^ ( j ) = e ( j ) + e ˉ ( j ) 2 + ρ j ⋅ e ( j ) − e ˉ ( j ) 2 β \hat{e}^{(j)} = \frac{e^{(j)} + \bar{e}^{(j)}}{2} + \rho_j \cdot \frac{e^{(j)}-\bar{e}^{(j)}}{2\beta} e ^ ( j ) = 2 e ( j ) + e ˉ ( j ) + ρ j ⋅ 2 β e ( j ) − e ˉ ( j ) 安全性分析 ¶ 【Completeness】
给定一个多项式系数向量满足 ⟨ f ⃗ , ⊗ j = 0 2 ( 1 , ρ j ) ⟩ = u \langle\vec{f}, \otimes_{j=0}^{2}(1,\rho_j) \rangle = u ⟨ f , ⊗ j = 0 2 ( 1 , ρ j )⟩ = u f e ( j − 1 ) ( X ) , f o ( j − 1 ) ( X ) f_e^{(j-1)}(X), f_o^{(j-1)}(X) f e ( j − 1 ) ( X ) , f o ( j − 1 ) ( X ) f ( j ) ( X ) f^{(j)}(X) f ( j ) ( X ) f ( j ) ( X ) f^{(j)}(X) f ( j ) ( X )
f ( j ) ( X ) = ∑ i 0 , . . . , i n − 1 ∈ { 0 , 1 } f i 0 ⋯ i n − 1 ⋅ ρ 0 i 0 ⋯ ρ j − 1 i j − 1 ⋅ X ⟨ i ⃗ [ j : n − 1 ] , 2 ⃗ n − 1 − j ⟩ f^{(j)}(X) = \sum_{i_0,...,i_{n-1} \in \{ 0,1 \}} f_{i_0\cdots i_{n-1}} \cdot \rho_0^{i_0} \cdots \rho_{j-1}^{i_{j-1}} \cdot X^{\langle \vec{i}_{[j:n-1]}, \vec{2}^{n-1-j}\rangle} f ( j ) ( X ) = i 0 , ... , i n − 1 ∈ { 0 , 1 } ∑ f i 0 ⋯ i n − 1 ⋅ ρ 0 i 0 ⋯ ρ j − 1 i j − 1 ⋅ X ⟨ i [ j : n − 1 ] , 2 n − 1 − j ⟩ 其中 2 ⃗ n − 1 − j = ( 2 0 , . . . , 2 n − 1 − j ) \vec{2}^{n-1-j} = (2^0,...,2^{n-1-j}) 2 n − 1 − j = ( 2 0 , ... , 2 n − 1 − j ) j = n j=n j = n f ( n ) ( X ) = f ~ ( ρ ⃗ ) = u f^{(n)}(X) = \tilde{f}(\vec{\rho})= u f ( n ) ( X ) = f ~ ( ρ ) = u
【Soundness】
这里我们采用和 Gemini 原文不同，但更加容易理解的证明方法。假设 ⟨ f ⃗ , ⊗ j = 0 2 ( 1 , ρ j ) ⟩ ≠ u \langle\vec{f}, \otimes_{j=0}^{2}(1,\rho_j) \rangle \neq u ⟨ f , ⊗ j = 0 2 ( 1 , ρ j )⟩ = u f ( j ) , j = 0 , . . . , n − 1 f^{(j)}, j=0,...,n-1 f ( j ) , j = 0 , ... , n − 1 j j j
p j ( X ) = f ( j ) ( X 2 ) − f ( j − 1 ) ( X ) + f ( j − 1 ) ( − X ) 2 − ρ j − 1 f ( j − 1 ) ( X ) − f ( j − 1 ) ( − X ) 2 X p_j(X) = f^{(j)}(X^2) - \frac{f^{(j-1)}(X)+f^{(j-1)}(-X)}{2} - \rho_{j-1}\frac{f^{(j-1)}(X)-f^{(j-1)}(-X)}{2X} p j ( X ) = f ( j ) ( X 2 ) − 2 f ( j − 1 ) ( X ) + f ( j − 1 ) ( − X ) − ρ j − 1 2 X f ( j − 1 ) ( X ) − f ( j − 1 ) ( − X ) 是非零多项式。注意到 p j ( X ) p_j(X) p j ( X ) 2 n − ( j − 1 ) − 1 2^{n-(j-1)}-1 2 n − ( j − 1 ) − 1 E j E_j E j p j ( X ) p_j(X) p j ( X ) p j ( β ) = 0 p_j(\beta) = 0 p j ( β ) = 0 P r ( E j ) ≤ d e g ( p j ) / ∣ F ∣ Pr(E_j) \leq deg(p_j)/|F| P r ( E j ) ≤ d e g ( p j ) /∣ F ∣ p 1 ( X ) , . . . , p n ( X ) p_1(X),...,p_{n}(X) p 1 ( X ) , ... , p n ( X )
P r ( E 1 ∨ ⋯ ∨ E n ) ≤ P r ( E 1 ) + ⋯ + P r ( E n ) = ∑ j = 1 n d e g ( p j ) ∣ F ∣ = 2 N ∣ F ∣ Pr(E_1 \vee \cdots \vee E_n) \leq Pr(E_1) + \cdots + Pr(E_n) = \sum_{j=1}^n \frac{deg(p_j)}{|F|} = \frac{2N}{|F|} P r ( E 1 ∨ ⋯ ∨ E n ) ≤ P r ( E 1 ) + ⋯ + P r ( E n ) = j = 1 ∑ n ∣ F ∣ d e g ( p j ) = ∣ F ∣ 2 N 【关于 degree bound】
注意在 Gemini 原论文中，验证者需要检查每个 f ( j ) f^{(j)} f ( j ) 2 n − j − 1 2^{n-j}-1 2 n − j − 1 p j ( X ) p_j(X) p j ( X ) 2 n − ( j − 1 ) − 1 2^{n-(j-1)}-1 2 n − ( j − 1 ) − 1
但经过研究我们会发现 degree check 并不是必需的：即使恶意的证明者被允许在每一轮构造一个非法的 f ( j ′ ) f^{(j')} f ( j ′ ) f ( j ) f^{(j)} f ( j ) N N N E j E_j E j P r ( E j ) ≤ N / ∣ F ∣ Pr(E_j) \leq N/|F| P r ( E j ) ≤ N /∣ F ∣ P r ( E 1 ∨ ⋯ ∨ E n ) ≤ N log N / ∣ F ∣ Pr(E_1 \vee \cdots \vee E_n) \leq N \log N/|F| P r ( E 1 ∨ ⋯ ∨ E n ) ≤ N log N /∣ F ∣ N < D N < D N < D D log N / ∣ F ∣ D \log N / |F| D log N /∣ F ∣
因此，第一部分中基于 KZG10 实现的 Tensor-product 检查协议中的 degree bound 检查可以忽略，以减少证明中的 log N \log N log N G 1 \mathbb{G}_1 G 1
实现 Zero-Knowledge ¶ Gemini 当中并没有讨论如何实现 tensor product check 的 ZK 性质，这里我们给出两种可行的方案。
【方案一】
采用与论文 [CFS17] 中实现 zk sumcheck 类似的思想，我们可以直接在原多项式 f ( X ) f(X) f ( X ) g ( X ) g(X) g ( X ) f ( X ) f(X) f ( X ) g ( X ) g(X) g ( X ) ⟨ g ⃗ , ⊗ j = 0 n − 1 ( 1 , ρ j ) ⟩ = v \langle\vec{g}, \otimes_{j=0}^{n-1}(1,\rho_j) \rangle = v ⟨ g , ⊗ j = 0 n − 1 ( 1 , ρ j )⟩ = v
接下来，证明者只需要额外对 g ( X ) g(X) g ( X ) c m ( g ( X ) ) cm(g(X)) c m ( g ( X )) v v v c c c f , g f,g f , g
u + c ⋅ v = ⟨ f ⃗ + c ⋅ g ⃗ , ⊗ j = 0 n − 1 ( 1 , ρ j ) ⟩ u+c\cdot v = \langle\vec{f}+c\cdot \vec{g}, \otimes_{j=0}^{n-1}(1,\rho_j) \rangle u + c ⋅ v = ⟨ f + c ⋅ g , ⊗ j = 0 n − 1 ( 1 , ρ j )⟩ 接下来，证明者和验证者共同完成对上述关系式的 Tensor product check 协议即可。我们不过多赘述这个方案的具体构造。
【方案二】
上述方法十分简单直接，但缺点是证明者需要额外增加一个和 f ( X ) f(X) f ( X ) N N N
该优化方案的思路是：由于证明者在 tensor product check 中一共只发送了 3 n 3n 3 n 3 n 3n 3 n
具体地，令盲化多项式为：
g ( X ) = a 0 , 1 X + a 0 , 2 X 2 + ∑ i = 1 n − 1 ( a i , 1 X 3 i + a i , 2 X 3 i + 1 + a i , 3 X 3 i + 2 ) + a n g(X) = a_{0,1}X + a_{0,2}X^2 + \sum_{i=1}^{n-1} \left( a_{i,1} X^{3i} + a_{i,2} X^{3i+1} + a_{i,3} X^{3i+2} \right) + a_n g ( X ) = a 0 , 1 X + a 0 , 2 X 2 + i = 1 ∑ n − 1 ( a i , 1 X 3 i + a i , 2 X 3 i + 1 + a i , 3 X 3 i + 2 ) + a n 【Zero-Knowledge Tensor Product 检查协议】
为了证明 ⟨ f ⃗ , ⊗ j = 0 n − 1 ( 1 , ρ j ) ⟩ = u \langle\vec{f}, \otimes_{j=0}^{n-1}(1,\rho_j) \rangle = u ⟨ f , ⊗ j = 0 n − 1 ( 1 , ρ j )⟩ = u
证明者构造盲化多项式 g ( X ) g(X) g ( X ) N N N 证明者计算并发送下面数据给验证者 v = ⟨ g ⃗ , ⊗ j = 0 n − 1 ( 1 , ρ j ) ⟩ C g = c m ( g ( X ) ) v = \langle\vec{g}, \otimes_{j=0}^{n-1}(1,\rho_j) \rangle \\ C_g = cm(g(X)) v = ⟨ g , ⊗ j = 0 n − 1 ( 1 , ρ j )⟩ C g = c m ( g ( X )) 验证者随机选取 c ∈ F ∗ c \in F^* c ∈ F ∗ u + c ⋅ v , C f + c ⋅ C g u + c\cdot v, C_f + c\cdot C_g u + c ⋅ v , C f + c ⋅ C g 证明者和验证者运行 tensor product 检查协议证明如下关系 u + c ⋅ v = ⟨ f ⃗ + c ⋅ g ⃗ , ⊗ j = 0 n − 1 ( 1 , ρ j ) ⟩ u+c\cdot v = \langle\vec{f}+c\cdot \vec{g}, \otimes_{j=0}^{n-1}(1,\rho_j) \rangle u + c ⋅ v = ⟨ f + c ⋅ g , ⊗ j = 0 n − 1 ( 1 , ρ j )⟩ 方便起见，我们令 h ( X ) = f ( X ) + c ⋅ g ( X ) h(X) = f(X) + c\cdot g(X) h ( X ) = f ( X ) + c ⋅ g ( X )
【证明】
首先，模拟器 S S S
S S S c ≠ 0 c \neq 0 c = 0 S S S h ⃗ \vec{h} h h ( X ) h(X) h ( X ) C h = C o m m i t ( h ( X ) ) , w = ⟨ h ⃗ , ⊗ j = 0 n − 1 ( 1 , ρ j ) ⟩ C_h = \mathsf{Commit}(h(X)), w = \langle\vec{h}, \otimes_{j=0}^{n-1}(1,\rho_j) \rangle C h = Commit ( h ( X )) , w = ⟨ h , ⊗ j = 0 n − 1 ( 1 , ρ j )⟩ S S S v = ( w − u ) / c v = (w-u)/c v = ( w − u ) / c C g = ( C h / C f ) 1 / c C_g = (C_h/C_f)^{1/c} C g = ( C h / C f ) 1/ c S S S V ∗ V^* V ∗ w = ⟨ h ⃗ , ⊗ j = 0 n − 1 ( 1 , ρ j ) ⟩ w = \langle\vec{h}, \otimes_{j=0}^{n-1}(1,\rho_j) \rangle w = ⟨ h , ⊗ j = 0 n − 1 ( 1 , ρ j )⟩ 显然，第1，3步中的消息和一个诚实证明者 P P P
接下来，我们只需要说明第4步中运行的 S S S V ∗ V^* V ∗ h ( j ) , j = 0 , . . . , n − 1 h^{(j)}, j=0,...,n-1 h ( j ) , j = 0 , ... , n − 1
h ( j ) ( X 2 ) = h ( j − 1 ) ( X ) + h ( j − 1 ) ( − X ) 2 + ρ ⋅ h ( j − 1 ) ( X ) − h ( j − 1 ) ( − X ) 2 X h^{(j)}(X^2)=\frac{h^{(j-1)}(X)+h^{(j-1)}(-X)}{2} + \rho \cdot \frac{h^{(j-1)}(X)-h^{(j-1)}(-X)}{2X} h ( j ) ( X 2 ) = 2 h ( j − 1 ) ( X ) + h ( j − 1 ) ( − X ) + ρ ⋅ 2 X h ( j − 1 ) ( X ) − h ( j − 1 ) ( − X ) 注意到，对于等式右边的 h ( j − 1 ) ( X ) h^{(j-1)}(X) h ( j − 1 ) ( X ) h ( j − 2 ) ( X ) h^{(j-2)}(X) h ( j − 2 ) ( X ) h ( j ) ( X 2 ) h^{(j)}(X^2) h ( j ) ( X 2 ) h ( 0 ) ( X ) , h ( 0 ) ( − X ) , h ( 0 ) ( X 2 ) h^{(0)}(X), h^{(0)}(-X), h^{(0)}(X^2) h ( 0 ) ( X ) , h ( 0 ) ( − X ) , h ( 0 ) ( X 2 ) V ∗ V^* V ∗ h ( j ) h^{(j)} h ( j ) h ⃗ \vec{h} h
总的来说，在进行 tensor product 检查协议后，V ∗ V^* V ∗ 3 ⋅ ( n − 1 ) 3\cdot (n-1) 3 ⋅ ( n − 1 ) h ( 0 ) ( X ) h^{(0)}(X) h ( 0 ) ( X ) h ( n ) ( X ) h^{(n)}(X) h ( n ) ( X ) u + c ⋅ v u+c\cdot v u + c ⋅ v h h h 3 n 3n 3 n
参考文献 ¶ [BCH+22] Bootle, Jonathan, Alessandro Chiesa, Yuncong Hu, **et al. “Gemini: Elastic SNARKs for Diverse Environments.” Cryptology ePrint Archive (2022). https://
[CFS17] Chiesa, Alessandro, Michael A. Forbes, and Nicholas Spooner. “A zero knowledge sumcheck and its applications.” arXiv preprint arXiv:1704.02086 (2017)
[XZZPS19] Xie, T., Zhang, J., Zhang, Y., Papamanthou, C., & Song, D. “Libra: Succinct zero-knowledge proofs with optimal prover computation.” https://