Groth16 算法使得证明者能够基于在可信设置中派生出的椭圆曲线点来计算二次算术程序，并由验证者快速进行检查。它利用可信设置中的辅助椭圆曲线点来防止伪造证明。
先决条件
本文是 RareSkills Book of Zero Knowledge Proofs 中的一章。假定您已熟悉前面的章节。
符号说明
我们将属于 G 1 \mathbb{G}_1 G 1 椭圆曲线点 记为 [ x ] 1 [x]_1 [ x ] 1 G 2 \mathbb{G}_2 G 2 [ x ] 2 [x]_2 [ x ] 2 [ x ] 1 [x]_1 [ x ] 1 [ x ] 2 [x]_2 [ x ] 2 配对 (pairing) 记作 [ x ] 1 ∙ [ x ] 2 [x]_1\bullet[x]_2 [ x ] 1 ∙ [ x ] 2 G 12 \mathbb{G}_{12} G 12 a \mathbf{a} a L \mathbf{L} L d d d 有限域 中进行，该域的特征等于椭圆曲线群的阶。
给定一个算术电路（ZK电路） ，我们将其转换为秩1约束系统 (R1CS) L a ∘ R a = O a \mathbf{L}\mathbf{a}\circ \mathbf{R}\mathbf{a} = \mathbf{O}\mathbf{a} La ∘ Ra = Oa n n n m m m a \mathbf{a} a x x x [ 1 , 2 , . . . , n ] [1,2,...,n] [ 1 , 2 , ... , n ] y y y 二次算术程序 (QAP) 。由于 L \mathbf{L} L R \mathbf{R} R O \mathbf{O} O m m m m m m
u 1 ( x ) , . . . , u m ( x ) 对 L 的 m 列进行插值得到的 m 个多项式 v 1 ( x ) , . . . , v m ( x ) 对 R 的 m 列进行插值得到的 m 个多项式 w 1 ( x ) , . . . , w m ( x ) 对 O 的 m 列进行插值得到的 m 个多项式 \begin{array}{}
u_1(x),...,u_m(x) & 对 \mathbf{L} 的 m 列进行插值得到的 m 个多项式\\
v_1(x),...,v_m(x)& 对 \mathbf{R} 的 m 列进行插值得到的 m 个多项式\\
w_1(x),...,w_m(x)& 对 \mathbf{O} 的 m 列进行插值得到的 m 个多项式\\
\end{array} u 1 ( x ) , ... , u m ( x ) v 1 ( x ) , ... , v m ( x ) w 1 ( x ) , ... , w m ( x ) 对 L 的 m 列进行插值得到的 m 个多项式 对 R 的 m 列进行插值得到的 m 个多项式 对 O 的 m 列进行插值得到的 m 个多项式
由此，我们可以构造一个二次算术程序 (QAP)：
∑ i = 1 m a i u i ( x ) ∑ i = 1 m a i v i ( x ) = ∑ i = 1 m a i w i ( x ) + h ( x ) t ( x ) \sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x) = \sum_{i=1}^m a_iw_i(x) + h(x)t(x) i = 1 ∑ m a i u i ( x ) i = 1 ∑ m a i v i ( x ) = i = 1 ∑ m a i w i ( x ) + h ( x ) t ( x )
其中
t ( x ) = ( x − 1 ) ( x − 2 ) … ( x − n ) t(x) = (x - 1)(x - 2)\dots(x - n) t ( x ) = ( x − 1 ) ( x − 2 ) … ( x − n ) h ( x ) = ∑ i = 1 m a i u i ( x ) ∑ i = 1 m a i v i ( x ) − ∑ i = 1 m a i w i ( x ) t ( x ) h(x) = \frac{\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x) - \sum_{i=1}^m a_iw_i(x)}{t(x)} h ( x ) = t ( x ) ∑ i = 1 m a i u i ( x ) ∑ i = 1 m a i v i ( x ) − ∑ i = 1 m a i w i ( x ) 如果第三方通过 powers of tau 仪式创建了一个结构化参考字符串 (srs)，那么证明者就可以在一个隐藏点 τ \tau τ ∑ a i f i ( x ) \sum a_if_i(x) ∑ a i f i ( x )
[ Ω n − 1 , Ω n − 2 , … , Ω 2 , Ω 1 , G 1 ] = [ τ n G 1 , τ n − 1 G 1 , … , τ G 1 , G 1 ] G 1 的 srs [ Θ n − 1 , Θ n − 2 , … , Θ 2 , Θ 1 , G 2 ] = [ τ n G 2 , τ n − 1 G 2 , … , τ G 2 , G 2 ] G 2 的 srs [ Υ n − 2 , Υ n − 3 , … , Υ 1 , Υ 0 ] = [ τ n − 2 t ( τ ) G 1 , τ n − 3 t ( τ ) G 1 , … , τ t ( τ ) G 1 , t ( τ ) G 1 ] h ( τ ) t ( τ ) 的 srs \begin{align*}
[\Omega_{n-1}, \Omega_{n-2},\dots,\Omega_2,\Omega_1,G_1] &= [\tau^nG_1,\tau^{n-1}G_1,\dots,\tau G_1,G_1] && G_1 \text{ 的 srs} \\
[\Theta_{n-1}, \Theta_{n-2},\dots,\Theta_2,\Theta_1,G_2] &= [\tau^nG_2,\tau^{n-1}G_2,\dots,\tau G_2,G_2] && G_2 \text{ 的 srs}\\
[\Upsilon_{n-2},\Upsilon_{n-3},\dots,\Upsilon_1,\Upsilon_0]&=[\tau^{n-2}t(\tau)G_1,\tau^{n-3}t(\tau)G_1,\dots,\tau t(\tau)G_1,t(\tau)G_1] && h(\tau)t(\tau) \text{ 的 srs}\\
\end{align*} [ Ω n − 1 , Ω n − 2 , … , Ω 2 , Ω 1 , G 1 ] [ Θ n − 1 , Θ n − 2 , … , Θ 2 , Θ 1 , G 2 ] [ Υ n − 2 , Υ n − 3 , … , Υ 1 , Υ 0 ] = [ τ n G 1 , τ n − 1 G 1 , … , τ G 1 , G 1 ] = [ τ n G 2 , τ n − 1 G 2 , … , τ G 2 , G 2 ] = [ τ n − 2 t ( τ ) G 1 , τ n − 3 t ( τ ) G 1 , … , τ t ( τ ) G 1 , t ( τ ) G 1 ] G 1 的 srs G 2 的 srs h ( τ ) t ( τ ) 的 srs
我们将 f ( τ ) f(\tau) f ( τ ) [ τ d G 1 , . . . , τ 2 G 1 , τ G 1 , G 1 ] [\tau^dG_1,...,\tau^2G_1,\tau G_1,G_1] [ τ d G 1 , ... , τ 2 G 1 , τ G 1 , G 1 ]
f ( τ ) = ∑ i = 1 d f i Ω i = ⟨ [ f d , f d − 1 , . . . , f 1 , f 0 ] , [ Ω d , Ω d − 1 , . . . , G 1 ] ⟩ f(\tau) = \sum_{i=1}^d f_i\Omega_i=\langle[f_d, f_{d-1},...,f_1,f_0],[\Omega_d,\Omega_{d-1},...,G_1]\rangle f ( τ ) = i = 1 ∑ d f i Ω i = ⟨[ f d , f d − 1 , ... , f 1 , f 0 ] , [ Ω d , Ω d − 1 , ... , G 1 ]⟩
或者对于 G 2 \mathbb{G}_2 G 2
f ( τ ) = ∑ i = 1 d f i Θ i = ⟨ [ f d , f d − 1 , . . . , f 1 , f 0 ] , [ Θ d , Θ d − 1 , . . . , G 2 ] ⟩ f(\tau) = \sum_{i=1}^d f_i\Theta_i=\langle[f_d, f_{d-1},...,f_1,f_0],[\Theta_d,\Theta_{d-1},...,G_2]\rangle f ( τ ) = i = 1 ∑ d f i Θ i = ⟨[ f d , f d − 1 , ... , f 1 , f 0 ] , [ Θ d , Θ d − 1 , ... , G 2 ]⟩
f ( τ ) f(\tau) f ( τ ) τ \tau τ
证明者可以通过计算以下内容在可信设置上对他们的 QAP 进行求值：
[ A ] 1 = ∑ i = 1 m a i u i ( τ ) [ B ] 2 = ∑ i = 1 m a i v i ( τ ) [ C ] 1 = ∑ i = 1 m a i w i ( τ ) + h ( τ ) t ( τ ) \begin{align*}
[A]_1 &= \sum_{i=1}^m a_iu_i(\tau)\\
[B]_2 &= \sum_{i=1}^m a_iv_i(\tau)\\
[C]_1 &= \sum_{i=1}^m a_iw_i(\tau) + h(\tau)t(\tau)
\end{align*} [ A ] 1 [ B ] 2 [ C ] 1 = i = 1 ∑ m a i u i ( τ ) = i = 1 ∑ m a i v i ( τ ) = i = 1 ∑ m a i w i ( τ ) + h ( τ ) t ( τ )
此计算的详细信息在我们的教程 Quadratic Arithmetic Programs over Elliptic Curves 中有讨论。
如果该 QAP 是平衡的，则以下等式成立：
[ A ] 1 ∙ [ B ] 2 = ? [ C ] 1 ∙ G 2 [A]_1\bullet[B]_2 \stackrel{?}= [C]_1\bullet G_2 [ A ] 1 ∙ [ B ] 2 = ? [ C ] 1 ∙ G 2
动机
仅仅提供 ( [ A ] 1 , [ B ] 2 , [ C ] 1 ) ([A]_1, [B]_2, [C]_1) ([ A ] 1 , [ B ] 2 , [ C ] 1 ) a \mathbf{a} a
证明者可以简单地编造出满足 a b = c ab = c ab = c a a a b b b c c c
[ A ] 1 = a G 1 [ B ] 2 = b G 2 [ C ] 1 = c G 1 \begin{align*}
[A]_1 &= aG_1\\
[B]_2 &= bG_2\\
[C]_1 &= cG_1
\end{align*} [ A ] 1 [ B ] 2 [ C ] 1 = a G 1 = b G 2 = c G 1
并将这些椭圆曲线点 [ A ] 1 [A]_1 [ A ] 1 [ B ] 2 [B]_2 [ B ] 2 [ C ] 1 [C]_1 [ C ] 1
因此，验证者根本无法确定 ( [ A ] 1 , [ B ] 2 , [ C ] 1 ) ([A]_1, [B]_2, [C]_1) ([ A ] 1 , [ B ] 2 , [ C ] 1 )
我们需要在不引入过多计算开销的情况下迫使证明者诚实行事。实现这一目标的第一个算法是“Pinocchio: Nearly Practical Verifiable Computation ”。它的可用性足以让 ZCash 将其第一版区块链建立在它之上。
然而，Groth16 能够用更少的步骤完成同样的事情，而且该算法至今仍被广泛使用，因为在此之后还没有任何算法能在验证步骤上达到如此高的效率（尽管其他算法已经消除了可信设置或显著减少了证明者的工作量）。
2024 年更新： 密码学界发表了一篇标题相当具有胜利意味的论文“Polymath: Groth16 is not the limit ”，展示了一种所需验证者步骤比 Groth16 更少的算法。不过，在撰写本文时，该算法尚无已知的实现。
防止伪造 第 1 部分：引入 α \alpha α β \beta β
一个“无法求解”的验证公式
假设我们将验证公式更新如下：
[ A ] 1 ∙ [ B ] 2 = ? [ D ] 12 + [ C ] 1 ∙ G 2 [A]_1 \bullet [B]_2 \stackrel{?}= [D]_{12} + [C]_1\bullet G_2 [ A ] 1 ∙ [ B ] 2 = ? [ D ] 12 + [ C ] 1 ∙ G 2
请注意，为了方便起见，我们对 G 12 G_{12} G 12
这里，[ D ] 12 [D]_{12} [ D ] 12 G 12 G_{12} G 12
我们现在将展示，如果没有 [ D ] 12 [D]_{12} [ D ] 12 ( [ A ] 1 , [ B ] 2 , [ C ] 1 ) ([A]_1, [B]_2, [C]_1) ([ A ] 1 , [ B ] 2 , [ C ] 1 )
攻击 1：伪造 A 和 B 并推导 C
假设证明者随机选择 a ′ a' a ′ b ′ b' b ′ [ A ] 1 [A]₁ [ A ] 1 [ B ] 2 [B]₂ [ B ] 2 [ C ′ ] [C'] [ C ′ ]
[ A ] 1 ∙ [ B ] 2 = ? [ D ] 12 + [ C ] 1 ∙ G 2 [A]_1 \bullet [B]_2 \stackrel{?}= [D]_{12} + [C]_1\bullet G_2 [ A ] 1 ∙ [ B ] 2 = ? [ D ] 12 + [ C ] 1 ∙ G 2
知道 [ A ] 1 [A]₁ [ A ] 1 [ B ] 2 [B]₂ [ B ] 2 [ C ′ ] [C'] [ C ′ ]
[ A ] 1 ∙ [ B ] 2 − [ D ] 12 ⏟ χ 12 = [ C ′ ] 1 ∙ G 2 [ χ ] 12 = [ C ′ ] 1 ∙ G 2 \begin{align*}\underbrace{[A]_1\bullet [B]_2 - [D]_{12}}_{\chi_{12}}=[C']_1\bullet G_2\\
[\chi]_{12}=[C']_1\bullet G_2
\end{align*} χ 12 [ A ] 1 ∙ [ B ] 2 − [ D ] 12 = [ C ′ ] 1 ∙ G 2 [ χ ] 12 = [ C ′ ] 1 ∙ G 2
最后一行要求证明者求解 χ 12 \chi_{12} χ 12 [ C ′ ] 1 [C']_1 [ C ′ ] 1
攻击 2：伪造 C 并推导 A 和 B
这里证明者选择一个随机点 c ′ c' c ′ [ C ′ ] 1 [C']_1 [ C ′ ] 1 c ′ c' c ′ a ′ a' a ′ b ′ b' b ′
[ A ] 1 ∙ [ B ] 2 = ? [ D ] 12 + [ C ] 1 ∙ G 2 ⏟ [ ζ ] 12 [ A ] 1 ∙ [ B ] 2 = ? [ ζ ] 12 \begin{align*}[A]_1 \bullet [B]_2 &\stackrel{?}= \underbrace{[D]_{12} + [C]_1\bullet G_2}_{[\zeta]_{12}}\\
[A]_1 \bullet [B]_2 &\stackrel{?}=[\zeta]_{12}
\end{align*} [ A ] 1 ∙ [ B ] 2 [ A ] 1 ∙ [ B ] 2 = ? [ ζ ] 12 [ D ] 12 + [ C ] 1 ∙ G 2 = ? [ ζ ] 12
这要求证明者在给定 [ ζ ] 12 [\zeta]_{12} [ ζ ] 12 [ A ] 1 [A]₁ [ A ] 1 [ B ] 2 [B]₂ [ B ] 2 [ ζ ] 12 [\zeta]_{12} [ ζ ] 12
与离散对数问题类似，我们依赖于未经证实的密码学假设：这种计算（将 G 12 \mathbb{G}_{12} G 12 G 1 \mathbb{G}_1 G 1 G 2 \mathbb{G}_2 G 2 [ ζ ] 12 [\zeta]_{12} [ ζ ] 12 [ A ] 1 [A]₁ [ A ] 1 [ B ] 2 [B]₂ [ B ] 2 双线性 Diffie-Hellman 假设 。感兴趣的读者可以参阅关于判定性 Diffie-Hellman 假设 (Decisional Diffie-Hellman Assumption) 的相关讨论。
（未经证实并不意味着不可靠。如果你能找到证明或反驳这个假设的方法，名誉和财富都在等着你！在实践中，没有已知的方法可以将 [ ζ ] 12 [\zeta]_{12} [ ζ ] 12 [ A ] 1 [A]₁ [ A ] 1 [ B ] 2 [B]₂ [ B ] 2
α \alpha α β \beta β 在实践中，Groth16 并不使用 [ D ] 12 [D]_{12} [ D ] 12 α \alpha α β \beta β ( [ α ] 1 , [ β ] 2 ) ([\alpha]_1,[\beta]_2) ([ α ] 1 , [ β ] 2 )
[ α ] 1 = α G 1 [ β ] 2 = β G 2 \begin{align*}
[α]_1 &= α G_1 \\
[β]_2 &= β G_2
\end{align*} [ α ] 1 [ β ] 2 = α G 1 = β G 2
我们之前称为 [ D ] 12 [D]_{12} [ D ] 12 [ α ] 1 ∙ [ β ] 2 [\alpha]_1 \bullet [\beta]_2 [ α ] 1 ∙ [ β ] 2
重新推导证明和验证公式
为了使验证公式 [ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ C ] 1 ∙ G 2 [A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1\bullet[\beta]_2 + [C]_1\bullet G_2 [ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ C ] 1 ∙ G 2 α \alpha α β \beta β
∑ i = 1 m a i u i ( x ) ∑ i = 1 m a i v i ( x ) = ∑ i = 1 m a i w i ( x ) + h ( x ) t ( x ) \sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x) = \sum_{i=1}^m a_iw_i(x) + h(x)t(x) i = 1 ∑ m a i u i ( x ) i = 1 ∑ m a i v i ( x ) = i = 1 ∑ m a i w i ( x ) + h ( x ) t ( x )
现在考虑如果我们在等式左侧引入项 θ \theta θ η \eta η
( θ + ∑ i = 1 m a i u i ( x ) ) ( η + ∑ i = 1 m a i v i ( x ) ) = \left(\boxed{\theta}+\sum_{i=1}^m a_iu_i(x)\right)\left(\boxed{\eta} +\sum_{i=1}^m a_iv_i(x)\right) = ( θ + i = 1 ∑ m a i u i ( x ) ) ( η + i = 1 ∑ m a i v i ( x ) ) =
= θ η + θ ∑ i = 1 m a i v i ( x ) + η ∑ i = 1 m a i u i ( x ) + ∑ i = 1 m a i u i ( x ) ∑ i = 1 m a i v i ( x ) =\boxed{\theta\eta} + \boxed{\theta}\sum_{i=1}^m a_iv_i(x) + \boxed{\eta}\sum_{i=1}^m a_iu_i(x) + \sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x) = θ η + θ i = 1 ∑ m a i v i ( x ) + η i = 1 ∑ m a i u i ( x ) + i = 1 ∑ m a i u i ( x ) i = 1 ∑ m a i v i ( x )
我们可以使用原始的 QAP 定义来替换最右侧的项：
= θ η + θ ∑ i = 1 m a i v i ( x ) + η ∑ i = 1 m a i u i ( x ) + ∑ i = 1 m a i u i ( x ) ∑ i = 1 m a i v i ( x ) =\theta\eta + \theta\sum_{i=1}^m a_iv_i(x) + \eta\sum_{i=1}^m a_iu_i(x) + \boxed{\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x)} = θ η + θ i = 1 ∑ m a i v i ( x ) + η i = 1 ∑ m a i u i ( x ) + i = 1 ∑ m a i u i ( x ) i = 1 ∑ m a i v i ( x )
= θ η + θ ∑ i = 1 m a i v i ( x ) + η ∑ i = 1 m a i u i ( x ) + ∑ i = 1 m a i w i ( x ) + h ( x ) t ( x ) =\theta\eta + \theta\sum_{i=1}^m a_iv_i(x) + \eta\sum_{i=1}^m a_iu_i(x) + \boxed{\sum_{i=1}^m a_iw_i(x) + h(x)t(x)} = θ η + θ i = 1 ∑ m a i v i ( x ) + η i = 1 ∑ m a i u i ( x ) + i = 1 ∑ m a i w i ( x ) + h ( x ) t ( x )
现在我们可以引入一个具有以下定义的“扩展版” QAP：
( θ + ∑ i = 1 m a i u i ( x ) ) ( η + ∑ i = 1 m a i v i ( x ) ) = θ η + θ ∑ i = 1 m a i v i ( x ) + η ∑ i = 1 m a i u i ( x ) + ∑ i = 1 m a i w i ( x ) + h ( x ) t ( x ) \left(\theta+\sum_{i=1}^m a_iu_i(x)\right)\left(\eta +\sum_{i=1}^m a_iv_i(x)\right) =\theta\eta + \theta\sum_{i=1}^m a_iv_i(x) + \eta\sum_{i=1}^m a_iu_i(x) + \sum_{i=1}^m a_iw_i(x) + h(x)t(x) ( θ + i = 1 ∑ m a i u i ( x ) ) ( η + i = 1 ∑ m a i v i ( x ) ) = θ η + θ i = 1 ∑ m a i v i ( x ) + η i = 1 ∑ m a i u i ( x ) + i = 1 ∑ m a i w i ( x ) + h ( x ) t ( x )
为了让大家提前窥见我们接下来的目标，如果我们将 θ \theta θ [ α ] 1 [\alpha]_1 [ α ] 1 η \eta η [ β ] 2 [\beta]_2 [ β ] 2
[ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ C ] 1 ∙ G 2 [A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [C]_1\bullet G_2 [ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ C ] 1 ∙ G 2
其中
( [ α ] 1 + ∑ i = 1 m a i u i ( τ ) ) ⏟ [ A ] 1 ( [ β ] 2 + ∑ i = 1 m a i v i ( τ ) ) ⏟ [ B ] 2 = [ α ] 1 ∙ [ β ] 2 + ( α ∑ i = 1 m a i v i ( τ ) + β ∑ i = 1 m a i u i ( τ ) + ∑ i = 1 m a i w i ( τ ) + h ( τ ) t ( τ ) ) ⏟ [ C ] 1 ∙ G 2 \underbrace{\left([\alpha]_1+\sum_{i=1}^m a_iu_i(\tau)\right)}_{[A]_1}\underbrace{\left([\beta]_2 +\sum_{i=1}^m a_iv_i(\tau)\right)}_{[B]_2} =[\alpha]_1\bullet[\beta]_2 + \underbrace{\left(\alpha\sum_{i=1}^m a_iv_i(\tau) + \beta\sum_{i=1}^m a_iu_i(\tau) + \sum_{i=1}^m a_iw_i(\tau) + h(\tau)t(\tau)\right)}_{[C]_1} \bullet G_2 [ A ] 1 ( [ α ] 1 + i = 1 ∑ m a i u i ( τ ) ) [ B ] 2 ( [ β ] 2 + i = 1 ∑ m a i v i ( τ ) ) = [ α ] 1 ∙ [ β ] 2 + [ C ] 1 ( α i = 1 ∑ m a i v i ( τ ) + β i = 1 ∑ m a i u i ( τ ) + i = 1 ∑ m a i w i ( τ ) + h ( τ ) t ( τ ) ) ∙ G 2
证明者可以在不知道 τ \tau τ α \alpha α β \beta β [ A ] 1 [A]_1 [ A ] 1 [ B ] 2 [B]_2 [ B ] 2 τ \tau τ ( [ α ] 1 , [ β ] 2 ) ([α]_1,[β]_2) ([ α ] 1 , [ β ] 2 ) [ A ] 1 [A]_1 [ A ] 1 [ B ] 2 [B]_2 [ B ] 2
[ A ] 1 = [ α ] 1 + ∑ i = 1 m a i u i ( τ ) [ B ] 2 = [ β ] 2 + ∑ i = 1 m a i v i ( τ ) \begin{align*}
[A]_1 &= [\alpha]_1 + \sum_{i=1}^m a_iu_i(\tau)\\
[B]_2 &= [\beta]_2 + \sum_{i=1}^m a_iv_i(\tau)\\
\end{align*} [ A ] 1 [ B ] 2 = [ α ] 1 + i = 1 ∑ m a i u i ( τ ) = [ β ] 2 + i = 1 ∑ m a i v i ( τ )
这里，a i u i ( τ ) a_iu_i(\tau) a i u i ( τ ) τ \tau τ [ τ n − 1 G 1 , τ n − 2 G 1 , … , τ G 1 , G 1 ] [\tau^{n-1}G_1,\tau^{n-2}G_1,\dots,\tau G_1,G_1] [ τ n − 1 G 1 , τ n − 2 G 1 , … , τ G 1 , G 1 ] i = 1 , 2 , … , m i=1,2,\dots,m i = 1 , 2 , … , m u i ( τ ) u_i(\tau) u i ( τ ) G 2 G_2 G 2 [ B ] 2 [B]_2 [ B ] 2
但是，目前在不知道 α \alpha α β \beta β [ C ] 1 [C]_1 [ C ] 1 [ α ] 1 [\alpha]_1 [ α ] 1 ∑ a i u i ( τ ) \sum a_iu_i(\tau) ∑ a i u i ( τ ) [ β ] 2 [\beta]_2 [ β ] 2 ∑ a i v i ( τ ) \sum a_iv_i(\tau) ∑ a i v i ( τ ) G 12 \mathbb{G}_{12} G 12 [ C ] 1 [C]_1 [ C ] 1 G 1 \mathbb{G}_1 G 1
相反，可信设置需要为扩展 QAP 中存在问题的 C C C m m m
α ∑ i = 1 m a i v i ( τ ) + β ∑ i = 1 m a i u i ( τ ) + ∑ i = 1 m a i w i ( τ ) \alpha\sum_{i=1}^m a_iv_i(\tau) + \beta\sum_{i=1}^m a_iu_i(\tau) + \sum_{i=1}^m a_iw_i(\tau) α i = 1 ∑ m a i v i ( τ ) + β i = 1 ∑ m a i u i ( τ ) + i = 1 ∑ m a i w i ( τ )
通过一些代数变换，我们将所有的求和项合并为一个求和：
= ∑ i = 1 m ( α a i v i ( τ ) + β a i u i ( τ ) + a i w i ( τ ) ) =\sum_{i=1}^m (\alpha a_iv_i(\tau)+\beta a_iu_i(\tau) + a_iw_i(\tau)) = i = 1 ∑ m ( α a i v i ( τ ) + β a i u i ( τ ) + a i w i ( τ ))
并将 a i a_i a i
= ∑ i = 1 m a i ( α v i ( τ ) + β u i ( τ ) + w i ( τ ) ) =\sum_{i=1}^m a_i\boxed{(\alpha v_i(\tau)+\beta u_i(\tau) + w_i(\tau))} = i = 1 ∑ m a i ( α v i ( τ ) + β u i ( τ ) + w i ( τ ))
可信设置可以利用上面方框中的项创建 m m m τ \tau τ
迄今为止的算法总结
可信设置步骤
具体而言，可信设置计算以下内容：
α , β , τ ← 随机标量 [ τ n − 1 G 1 , τ n − 2 G 1 , … , τ G 1 , G 1 ] ← G 1 的 srs [ τ n − 1 G 2 , τ n − 2 G 2 , … , τ G 2 , G 2 ] ← G 2 的 srs [ τ n − 2 t ( τ ) G 1 , τ n − 3 t ( τ ) G 1 , … , τ t ( τ ) G 1 , t ( τ ) G 1 ] ← h ( τ ) t ( τ ) 的 srs [ Ψ 1 ] 1 = ( α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) ) G 1 [ Ψ 2 ] 1 = ( α v 2 ( τ ) + β u 2 ( τ ) + w 2 ( τ ) ) G 1 ⋮ [ Ψ m ] 1 = ( α v m ( τ ) + β u m ( τ ) + w m ( τ ) ) G 1 \begin{align*}
\alpha,\beta,\tau &\leftarrow \text{随机标量}\\
[\tau^{n-1}G_1,\tau^{n-2}G_1,\dots,\tau G_1,G_1] &\leftarrow \mathbb{G}_1 \text{ 的 srs}\\
[\tau^{n-1}G_2,\tau^{n-2}G_2,\dots,\tau G_2,G_2] &\leftarrow \mathbb{G}_2 \text{ 的 srs}\\
[\tau^{n-2}t(\tau)G_1,\tau^{n-3}t(\tau)G_1,\dots,\tau t(\tau)G_1,t(\tau)G_1] &\leftarrow h(\tau)t(\tau) \text{ 的 srs}\\
[\Psi_1]_1 &= (\alpha v_1(\tau) + \beta u_1(\tau) + w_1(\tau))G_1\\
[\Psi_2]_1 &= (\alpha v_2(\tau) + \beta u_2(\tau) + w_2(\tau))G_1\\
&\vdots\\
[\Psi_m]_1 &= (\alpha v_m(\tau) + \beta u_m(\tau) + w_m(\tau))G_1\\
\end{align*} α , β , τ [ τ n − 1 G 1 , τ n − 2 G 1 , … , τ G 1 , G 1 ] [ τ n − 1 G 2 , τ n − 2 G 2 , … , τ G 2 , G 2 ] [ τ n − 2 t ( τ ) G 1 , τ n − 3 t ( τ ) G 1 , … , τ t ( τ ) G 1 , t ( τ ) G 1 ] [ Ψ 1 ] 1 [ Ψ 2 ] 1 [ Ψ m ] 1 ← 随机标量 ← G 1 的 srs ← G 2 的 srs ← h ( τ ) t ( τ ) 的 srs = ( α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ )) G 1 = ( α v 2 ( τ ) + β u 2 ( τ ) + w 2 ( τ )) G 1 ⋮ = ( α v m ( τ ) + β u m ( τ ) + w m ( τ )) G 1 可信设置公布
( [ α ] 1 , [ β ] 2 , G 1 的 srs , G 2 的 srs , h ( τ ) t ( τ ) 的 srs , [ Ψ 1 ] 1 , [ Ψ 2 ] 1 , … , [ Ψ m ] 1 ) ([\alpha]_1,[\beta]_2,G_1 \text{ 的 srs},G_2 \text{ 的 srs},h(\tau)t(\tau) \text{ 的 srs},[\Psi_1]_1,[\Psi_2]_1,\dots,[\Psi_m]_1) ([ α ] 1 , [ β ] 2 , G 1 的 srs , G 2 的 srs , h ( τ ) t ( τ ) 的 srs , [ Ψ 1 ] 1 , [ Ψ 2 ] 1 , … , [ Ψ m ] 1 )
证明者步骤
证明者计算
[ A ] 1 = [ α ] 1 + ∑ i = 1 m a i u i ( τ ) [ B ] 2 = [ β ] 2 + ∑ i = 1 m a i v i ( τ ) [ C ] 1 = ∑ i = 1 m a i [ Ψ i ] 1 + h ( τ ) t ( τ ) \begin{align*}
[A]_1 &= [\alpha]_1 + \sum_{i=1}^m a_iu_i(\tau)\\
[B]_2 &= [\beta]_2 + \sum_{i=1}^m a_iv_i(\tau)\\
[C]_1 &= \sum_{i=1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)\\
\end{align*} [ A ] 1 [ B ] 2 [ C ] 1 = [ α ] 1 + i = 1 ∑ m a i u i ( τ ) = [ β ] 2 + i = 1 ∑ m a i v i ( τ ) = i = 1 ∑ m a i [ Ψ i ] 1 + h ( τ ) t ( τ )
请注意，我们将“有问题的”多项式
= ∑ i = 1 m a i ( α v i ( τ ) + β u i ( τ ) + w i ( τ ) ) =\sum_{i=1}^m a_i\boxed{(\alpha v_i(\tau)+\beta u_i(\tau) + w_i(\tau))} = i = 1 ∑ m a i ( α v i ( τ ) + β u i ( τ ) + w i ( τ ))
（包含 α \alpha α β \beta β
∑ i = 1 m a i [ Ψ i ] 1 \sum_{i=1}^m a_i[\Psi_i]_1 i = 1 ∑ m a i [ Ψ i ] 1
验证者步骤
验证者计算：
[ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ C ] 1 ∙ G 2 [A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [C]_1\bullet G_2 [ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ C ] 1 ∙ G 2
支持公开输入
到目前为止的验证者公式尚不支持公开输入，即公开见证的一部分。
按照惯例，见证的公开部分是向量 a \mathbf{a} a ℓ \ell ℓ
[ a 1 , a 2 , … , a ℓ ] [a_1, a_2, \dots, a_\ell] [ a 1 , a 2 , … , a ℓ ]
为了使验证者能够测试这些值是否确实被使用，验证者必须执行一些原本由证明者负责的计算。
具体来说，证明者现在这样计算：
[ A ] 1 = [ α ] 1 + ∑ i = 1 m a i u i ( τ ) [ B ] 2 = [ β ] 2 + ∑ i = 1 m a i v i ( τ ) [ C ] 1 = ∑ i = ℓ + 1 m a i [ Ψ i ] 1 + h ( τ ) t ( τ ) \begin{align*}
[A]_1 &= [\alpha]_1 + \sum_{i=1}^m a_iu_i(\tau)\\
[B]_2 &= [\beta]_2 + \sum_{i=1}^m a_iv_i(\tau)\\
[C]_1 &= \sum_{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)\\
\end{align*} [ A ] 1 [ B ] 2 [ C ] 1 = [ α ] 1 + i = 1 ∑ m a i u i ( τ ) = [ β ] 2 + i = 1 ∑ m a i v i ( τ ) = i = ℓ + 1 ∑ m a i [ Ψ i ] 1 + h ( τ ) t ( τ )
请注意，只有 [ C ] 1 [C]_1 [ C ] 1 ℓ + 1 \ell + 1 ℓ + 1 m m m a i a_i a i Ψ i \Psi_i Ψ i
验证者计算求和的前 ℓ \ell ℓ
[ X ] 1 = ∑ i = 1 ℓ a i Ψ i [X]_1=\sum_{i=1}^\ell a_i\Psi_i [ X ] 1 = i = 1 ∑ ℓ a i Ψ i 而验证等式变为：
[ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ G 2 + [ C ] 1 ∙ G 2 [A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet G_2 + [C]_1\bullet G_2 [ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ G 2 + [ C ] 1 ∙ G 2
第 2 部分：通过 γ \gamma γ δ \delta δ
通过滥用 i ≤ ℓ i\leq\ell i ≤ ℓ Ψ i \Psi_i Ψ i
上述等式中的假设是，证明者只使用 Ψ ℓ + 1 \Psi_{\ell+1} Ψ ℓ + 1 Ψ m \Psi_m Ψ m [ C ] 1 [C]_1 [ C ] 1 Ψ 1 \Psi_1 Ψ 1 Ψ ℓ \Psi_{\ell} Ψ ℓ [ C ] 1 [C]_1 [ C ] 1
例如，这是我们当前的验证等式：
[ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + ∑ i = 1 ℓ a i Ψ i + [ C ] 1 ∙ G 2 [A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + \sum_{i=1}^\ell a_i\Psi_i + [C]_1\bullet G_2 [ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + i = 1 ∑ ℓ a i Ψ i + [ C ] 1 ∙ G 2
如果我们在底层展开 C 项，我们会得到以下形式：
[ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + ∑ i = 1 ℓ a i Ψ i + ( ∑ i = ℓ + 1 m a i [ Ψ i ] 1 + h ( τ ) t ( τ ) ) ⏟ C ∙ G 2 [A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + \sum_{i=1}^\ell a_i\Psi_i + \underbrace{\left(\sum_{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)\right)}_C \bullet G_2 [ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + i = 1 ∑ ℓ a i Ψ i + C ( i = ℓ + 1 ∑ m a i [ Ψ i ] 1 + h ( τ ) t ( τ ) ) ∙ G 2
假设（不失一般性）a = [ 1 , 2 , 3 , 4 , 5 ] \mathbf{a} = [1,2,3,4,5] a = [ 1 , 2 , 3 , 4 , 5 ] ℓ = 3 \ell=3 ℓ = 3 [ 1 , 2 , 3 ] [1,2,3] [ 1 , 2 , 3 ] [ 4 , 5 ] [4,5] [ 4 , 5 ]
最终的等式将如下所示：
[ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + ( 1 Ψ 1 + 2 Ψ 2 + 3 Ψ 3 ) ∙ G 2 + ( 4 Ψ 4 + 5 Ψ 5 + h ( τ ) t ( τ ) ) ⏟ C ∙ G 2 [A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + (1\Psi_1+2\Psi_2+3\Psi_3)\bullet G2 + \underbrace{(4\Psi_4 + 5\Psi_5 + h(\tau)t(\tau))}_C \bullet G_2 [ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + ( 1 Ψ 1 + 2 Ψ 2 + 3 Ψ 3 ) ∙ G 2 + C ( 4 Ψ 4 + 5 Ψ 5 + h ( τ ) t ( τ )) ∙ G 2
然而，没有任何机制能阻止证明者创建一个部分合法的公共见证，如 [1,2,0]，并将被置为零的公开部分转移到计算的私有部分，如下所示：
[ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + ( 1 Ψ 1 + 2 Ψ 2 + 0 Ψ 3 ) ∙ G 2 + ( 3 Ψ 3 + 4 Ψ 4 + 5 Ψ 5 + h ( τ ) t ( τ ) ) ⏟ C ∙ G 2 [A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + (1\Psi_1+2\Psi_2+\boxed{0\Psi_3})\bullet G2 + \underbrace{(\boxed{3\Psi_3}+4\Psi_4 + 5\Psi_5 + h(\tau)t(\tau))}_C \bullet G_2 [ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + ( 1 Ψ 1 + 2 Ψ 2 + 0 Ψ 3 ) ∙ G 2 + C ( 3 Ψ 3 + 4 Ψ 4 + 5 Ψ 5 + h ( τ ) t ( τ )) ∙ G 2
上面的等式是有效的，但见证却不一定满足原始约束。
因此，我们需要防止证明者在计算 [ C ] 1 [C]_1 [ C ] 1 Ψ 1 \Psi_1 Ψ 1 Ψ ℓ \Psi_{\ell} Ψ ℓ
引入 γ \gamma γ δ \delta δ
为了避免上述问题，可信设置引入了一个新的标量：γ \gamma γ δ \delta δ Ψ ℓ + 1 \Psi_{\ell+1} Ψ ℓ + 1 Ψ m \Psi_m Ψ m Ψ 1 \Psi_1 Ψ 1 Ψ ℓ \Psi_{\ell} Ψ ℓ [ C ] 1 [C]_1 [ C ] 1 δ \delta δ [ X ] 1 [X]_1 [ X ] 1 γ \gamma γ
由于 h ( τ ) t ( τ ) h(\tau)t(\tau) h ( τ ) t ( τ ) [ C ] 1 [C]_1 [ C ] 1 δ \delta δ δ \delta δ γ \gamma γ 可信设置 中，其中 γ \gamma γ G 2 G_2 G 2 δ \delta δ G 2 G_2 G 2
α , β , τ , γ , δ ← 随机标量 [ τ n − 1 G 1 , τ n − 2 G 1 , … , τ G 1 , G 1 ] ← G 1 的 srs [ τ n − 1 G 2 , τ n − 2 G 2 , … , τ G 2 , G 2 ] ← G 2 的 srs [ τ n − 2 t ( τ ) δ G 1 , τ n − 3 t ( τ ) δ G 1 , … , τ t ( τ ) δ G 1 , t ( τ ) δ G 1 ] ← h ( τ ) t ( τ ) 的 srs 见证的公开部分 [ Ψ 1 ] 1 = α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) γ G 1 [ Ψ 2 ] 1 = α v 2 ( τ ) + β u 2 ( τ ) + w 2 ( τ ) γ G 1 ⋮ [ Ψ ℓ ] 1 = α v ℓ ( τ ) + β u ℓ ( τ ) + w ℓ ( τ ) γ G 1 见证的私有部分 [ Ψ ℓ + 1 ] 1 = α v ℓ + 1 ( τ ) + β u ℓ + 1 ( τ ) + w ℓ + 1 ( τ ) δ G 1 [ Ψ ℓ + 2 ] 1 = α v ℓ + 2 ( τ ) + β u ℓ + 2 ( τ ) + w ℓ + 2 ( τ ) δ G 1 ⋮ [ Ψ m ] 1 = α v m ( τ ) + β u m ( τ ) + w m ( τ ) δ G 1 \begin{align*}
\alpha,\beta,\tau,\gamma,\delta &\leftarrow \text{随机标量}\\
[\tau^{n-1}G_1,\tau^{n-2}G_1,\dots,\tau G_1,G_1] &\leftarrow \mathbb{G}_1 \text{ 的 srs}\\
[\tau^{n-1}G_2,\tau^{n-2}G_2,\dots,\tau G_2,G_2] &\leftarrow \mathbb{G}_2 \text{ 的 srs}\\
\left[\frac{\tau^{n-2}t(\tau)}{\delta}G_1,\frac{\tau^{n-3}t(\tau)}{\delta}G_1,\dots,\frac{\tau t(\tau)}{\delta}G_1,
\frac{t(\tau)}{\delta}G_1\right] &\leftarrow h(\tau)t(\tau) \text{ 的 srs}\\
\\
&\text{见证的公开部分}\\
[\Psi_1]_1 &= \frac{\alpha v_1(\tau) + \beta u_1(\tau) + w_1(\tau)}{\gamma}G_1\\
[\Psi_2]_1 &= \frac{\alpha v_2(\tau) + \beta u_2(\tau) + w_2(\tau)}{\gamma}G_1\\
&\vdots\\
[\Psi_\ell]_1 &= \frac{\alpha v_\ell(\tau) + \beta u_\ell(\tau) + w_\ell(\tau)}{\gamma}G_1\\
\\
&\text{见证的私有部分}\\
[\Psi_{\ell+1}]_1 &= \frac{\alpha v_{\ell+1}(\tau) + \beta u_{\ell+1}(\tau) + w_{\ell+1}(\tau)}{\delta}G_1\\
[\Psi_{\ell+2}]_1 &= \frac{\alpha v_{\ell+2}(\tau) + \beta u_{\ell+2}(\tau) + w_{\ell+2}(\tau)}{\delta}G_1\\
&\vdots\\
[\Psi_{m}]_1 &= \frac{\alpha v_{m}(\tau) + \beta u_{m}(\tau) + w_{m}(\tau)}{\delta}G_1\\
\end{align*} α , β , τ , γ , δ [ τ n − 1 G 1 , τ n − 2 G 1 , … , τ G 1 , G 1 ] [ τ n − 1 G 2 , τ n − 2 G 2 , … , τ G 2 , G 2 ] [ δ τ n − 2 t ( τ ) G 1 , δ τ n − 3 t ( τ ) G 1 , … , δ τ t ( τ ) G 1 , δ t ( τ ) G 1 ] [ Ψ 1 ] 1 [ Ψ 2 ] 1 [ Ψ ℓ ] 1 [ Ψ ℓ + 1 ] 1 [ Ψ ℓ + 2 ] 1 [ Ψ m ] 1 ← 随机标量 ← G 1 的 srs ← G 2 的 srs ← h ( τ ) t ( τ ) 的 srs 见证的公开部分 = γ α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) G 1 = γ α v 2 ( τ ) + β u 2 ( τ ) + w 2 ( τ ) G 1 ⋮ = γ α v ℓ ( τ ) + β u ℓ ( τ ) + w ℓ ( τ ) G 1 见证的私有部分 = δ α v ℓ + 1 ( τ ) + β u ℓ + 1 ( τ ) + w ℓ + 1 ( τ ) G 1 = δ α v ℓ + 2 ( τ ) + β u ℓ + 2 ( τ ) + w ℓ + 2 ( τ ) G 1 ⋮ = δ α v m ( τ ) + β u m ( τ ) + w m ( τ ) G 1
可信设置公布
( [ α ] 1 , [ β ] 2 , [ γ ] 2 , [ δ ] 2 , G 1 的 srs , G 2 的 srs , h ( τ ) t ( τ ) 的 srs , [ Ψ 1 ] 1 , [ Ψ 2 ] 1 , … , [ Ψ m ] 1 ) ([\alpha]_1,[\beta]_2,[\gamma]_2,[\delta]_2,G_1 \text{ 的 srs},G_2 \text{ 的 srs},h(\tau)t(\tau) \text{ 的 srs},[\Psi_1]_1,[\Psi_2]_1,\dots,[\Psi_m]_1) ([ α ] 1 , [ β ] 2 , [ γ ] 2 , [ δ ] 2 , G 1 的 srs , G 2 的 srs , h ( τ ) t ( τ ) 的 srs , [ Ψ 1 ] 1 , [ Ψ 2 ] 1 , … , [ Ψ m ] 1 ) 证明者的步骤和以前一样：
[ A ] 1 = [ α ] 1 + ∑ i = 1 m a i u i ( τ ) [ B ] 2 = [ β ] 2 + ∑ i = 1 m a i v i ( τ ) [ C ] 1 = ∑ i = ℓ + 1 m a i [ Ψ i ] 1 + h ( τ ) t ( τ ) \begin{align*}
[A]_1 &= [\alpha]_1 + \sum_{i=1}^m a_iu_i(\tau)\\
[B]_2 &= [\beta]_2 + \sum_{i=1}^m a_iv_i(\tau)\\
[C]_1 &= \sum_{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)\\
\end{align*} [ A ] 1 [ B ] 2 [ C ] 1 = [ α ] 1 + i = 1 ∑ m a i u i ( τ ) = [ β ] 2 + i = 1 ∑ m a i v i ( τ ) = i = ℓ + 1 ∑ m a i [ Ψ i ] 1 + h ( τ ) t ( τ )
而验证者的步骤现在包括通过与 [ γ ] 2 [\gamma]_2 [ γ ] 2 [ δ ] 2 [\delta]_2 [ δ ] 2
[ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ [ γ ] 2 + [ C ] 1 ∙ [ δ ] 2 [A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet [\gamma]_2 + [C]_1\bullet [\delta]_2 [ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ [ γ ] 2 + [ C ] 1 ∙ [ δ ] 2
第 3 部分：实现真正的零知识：r 和 s
我们的方案尚未实现真正的零知识。如果攻击者能够猜出我们的见证向量（如果有效输入的范围很小，这是可能的，例如来自特权地址的秘密投票），那么他们可以通过比较他们构造的证明和原始证明来验证他们的猜测是否正确。
举一个简单的例子，假设我们声称 x 1 x_1 x 1 x 2 x_2 x 2 0 0 0 1 1 1
x 1 ( x 1 − 1 ) = 0 x 2 ( x 2 − 1 ) = 0 \begin{align*}
x_1 (x_1 - 1) = 0\\
x_2 (x_2 - 1) = 0
\end{align*} x 1 ( x 1 − 1 ) = 0 x 2 ( x 2 − 1 ) = 0
攻击者只需要猜测四种组合就能弄清楚见证是什么。也就是说，他们猜测一个见证，生成一个证明，然后看他们的答案是否与原证明匹配。
为了防止被猜测，证明者需要对其证明“加盐” (salt)，同时需要修改验证公式以适应加盐后的证明。
证明者抽取两个随机域元素 r r r s s s A A A B B B r r r s s s
[ A ] 1 = [ α ] 1 + ∑ i = 1 m a i u i ( τ ) + r [ δ ] 1 [ B ] 2 = [ β ] 2 + ∑ i = 1 m a i v i ( τ ) + s [ δ ] 2 [ B ] 1 = [ β ] 1 + ∑ i = 1 m a i v i ( τ ) + s [ δ ] 1 [ C ] 1 = ∑ i = ℓ + 1 m a i [ Ψ i ] 1 + h ( τ ) t ( τ ) + A s + B r − r s [ δ ] 1 \begin{align*}
[A]_1 &= [\alpha]_1 + \sum_{i=1}^m a_iu_i(\tau) + r[\delta]_1\\
[B]_2 &= [\beta]_2 + \sum_{i=1}^m a_iv_i(\tau) + s[\delta]_2\\
[B]_1 &= [\beta]_1 + \sum_{i=1}^m a_iv_i(\tau) + s[\delta]_1\\
[C]_1 &= \sum_{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau) + As+Br-rs[\delta]_1\\
\end{align*} [ A ] 1 [ B ] 2 [ B ] 1 [ C ] 1 = [ α ] 1 + i = 1 ∑ m a i u i ( τ ) + r [ δ ] 1 = [ β ] 2 + i = 1 ∑ m a i v i ( τ ) + s [ δ ] 2 = [ β ] 1 + i = 1 ∑ m a i v i ( τ ) + s [ δ ] 1 = i = ℓ + 1 ∑ m a i [ Ψ i ] 1 + h ( τ ) t ( τ ) + A s + B r − rs [ δ ] 1
为了推导最终的验证公式，让我们暂时忽略我们不知道希腊字母项的离散对数这一事实，直接计算验证等式的左侧 A B AB A B
( α + ∑ i = 1 m a i u i ( x ) + r δ ) ⏟ A ( β + ∑ i = 1 m a i v i ( x ) + s δ ) ⏟ B \underbrace{\left(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta\right)}_A \underbrace{\left(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta\right)}_B A ( α + i = 1 ∑ m a i u i ( x ) + rδ ) B ( β + i = 1 ∑ m a i v i ( x ) + sδ )
将各项展开后我们得到：
α β + α ∑ i = 1 m a i v i ( x ) + α s δ + β ∑ i = 1 m a i u i ( x ) + ∑ i = 1 m a i u i ( x ) ∑ i = 1 m a i v i ( x ) + ∑ i = 1 m a i u i ( x ) s δ + r δ β + r δ ∑ i = 1 m a i v i ( x ) + r δ s δ \alpha\beta+\alpha\sum_{i=1}^m a_iv_i(x)+\alpha s\delta + \beta\sum_{i=1}^m a_iu_i(x) + \sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x)+\sum_{i=1}^m a_iu_i(x) s\delta + r\delta\beta + r\delta\sum_{i=1}^m a_iv_i(x) + r\delta s\delta α β + α i = 1 ∑ m a i v i ( x ) + α sδ + β i = 1 ∑ m a i u i ( x ) + i = 1 ∑ m a i u i ( x ) i = 1 ∑ m a i v i ( x ) + i = 1 ∑ m a i u i ( x ) sδ + rδ β + rδ i = 1 ∑ m a i v i ( x ) + rδsδ
我们可以挑出原属于 C C C
α β + α ∑ i = 1 m a i v i ( x ) + α s δ + β ∑ i = 1 m a i u i ( x ) + ∑ i = 1 m a i u i ( x ) ∑ i = 1 m a i v i ( x ) + ∑ i = 1 m a i u i ( x ) s δ + r δ β + r δ ∑ i = 1 m a i v i ( x ) + r δ s δ \alpha\beta+\boxed{\alpha\sum_{i=1}^m a_iv_i(x)}+\alpha s\delta + \boxed{\beta\sum_{i=1}^m a_iu_i(x)} + \boxed{\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x)}+\sum_{i=1}^m a_iu_i(x) s\delta + r\delta\beta + r\delta\sum_{i=1}^m a_iv_i(x) + r\delta s\delta α β + α i = 1 ∑ m a i v i ( x ) + α sδ + β i = 1 ∑ m a i u i ( x ) + i = 1 ∑ m a i u i ( x ) i = 1 ∑ m a i v i ( x ) + i = 1 ∑ m a i u i ( x ) sδ + rδ β + rδ i = 1 ∑ m a i v i ( x ) + rδsδ
并将它们合并在左侧，将新引入的项留在右侧：
α β + α ∑ i = 1 m a i v i ( x ) + β ∑ i = 1 m a i u i ( x ) + ∑ i = 1 m a i u i ( x ) ∑ i = 1 m a i v i ( x ) + α s δ + ∑ i = 1 m a i u i ( x ) s δ + r δ β + r δ ∑ i = 1 m a i v i ( x ) + r δ s δ ‾ \alpha\beta + \boxed{\alpha\sum_{i=1}^m a_iv_i(x) + \beta\sum_{i=1}^m a_iu_i(x) + \sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x)}+ \underline{\alpha s\delta + \sum_{i=1}^m a_iu_i(x) s\delta + r\delta\beta + r\delta\sum_{i=1}^m a_iv_i(x) + r\delta s\delta} α β + α i = 1 ∑ m a i v i ( x ) + β i = 1 ∑ m a i u i ( x ) + i = 1 ∑ m a i u i ( x ) i = 1 ∑ m a i v i ( x ) + α sδ + i = 1 ∑ m a i u i ( x ) sδ + rδ β + rδ i = 1 ∑ m a i v i ( x ) + rδsδ
我们进一步重排带下划线的项，将其用 A s δ As\delta A sδ B r δ Br\delta B rδ r δ s δ r\delta s\delta rδsδ r s δ 2 + r s δ 2 − r s δ 2 rs\delta^2 + rs\delta^2 - rs\delta^2 rs δ 2 + rs δ 2 − rs δ 2
= α s δ + ∑ i = 1 m a i u i ( x ) s δ + r s δ 2 + r δ β + r δ ∑ i = 1 m a i v i ( x ) + r s δ 2 − r s δ 2 =\alpha s\delta + \sum_{i=1}^m a_iu_i(x) s\delta + rs\delta^2 + r\delta\beta + r\delta\sum_{i=1}^m a_iv_i(x) + rs\delta^2 - rs\delta^2 = α sδ + i = 1 ∑ m a i u i ( x ) sδ + rs δ 2 + rδ β + rδ i = 1 ∑ m a i v i ( x ) + rs δ 2 − rs δ 2
把与 s s s r r r
= ( α s δ + ∑ i = 1 m a i u i ( x ) s δ + r s δ 2 ) + ( r δ β + r δ ∑ i = 1 m a i v i ( x ) + r s δ 2 ) − r s δ 2 =\left(\alpha s\delta + \sum_{i=1}^m a_iu_i(x) s\delta + rs\delta^2\right) + \left(r\delta\beta + r\delta\sum_{i=1}^m a_iv_i(x) + rs\delta^2\right) - rs\delta^2 = ( α sδ + i = 1 ∑ m a i u i ( x ) sδ + rs δ 2 ) + ( rδ β + rδ i = 1 ∑ m a i v i ( x ) + rs δ 2 ) − rs δ 2 提出 s δ s\delta sδ r δ r\delta rδ
= ( α + ∑ i = 1 m a i u i ( x ) + r δ ) s δ ⏟ A s δ + ( β + ∑ i = 1 m a i v i ( x ) + s δ ) r δ ⏟ B r δ − r s δ 2 =\underbrace{\left(\alpha+ \sum_{i=1}^m a_iu_i(x) + r\delta\right)s\delta}_{As\delta} + \underbrace{\left(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta\right)r\delta}_{Br\delta} - rs\delta^2 = A sδ ( α + i = 1 ∑ m a i u i ( x ) + rδ ) sδ + B rδ ( β + i = 1 ∑ m a i v i ( x ) + sδ ) rδ − rs δ 2 代入 A A A B B B
= A s δ + B r δ − r s δ 2 =As\delta + Br\delta - rs\delta^2 = A sδ + B rδ − rs δ 2 因此我们的最终等式为
( α + ∑ i = 1 m a i u i ( x ) + r δ ) ( β + ∑ i = 1 m a i v i ( x ) + s δ ) = α β + ∑ i = 1 m a i ( α v i ( x ) + β u i ( x ) + w i ( x ) ) + h ( x ) t ( x ) + A s δ + B r δ − r s δ 2 \left(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta\right)\left(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta\right)=\alpha\beta+\sum_{i=1}^m a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x)) + h(x)t(x) + As\delta + Br\delta - rs\delta^2 ( α + i = 1 ∑ m a i u i ( x ) + rδ ) ( β + i = 1 ∑ m a i v i ( x ) + sδ ) = α β + i = 1 ∑ m a i ( α v i ( x ) + β u i ( x ) + w i ( x )) + h ( x ) t ( x ) + A sδ + B rδ − rs δ 2
我们现在将其分成公开和私有部分：
( α + ∑ i = 1 m a i u i ( x ) + r δ ) ( β + ∑ i = 1 m a i v i ( x ) + s δ ) = α β + ∑ i = 1 ℓ a i ( α v i ( x ) + β u i ( x ) + w i ( x ) ) ⏟ 公开部分 + ∑ i = ℓ + 1 m a i ( α v i ( x ) + β u i ( x ) + w i ( x ) ) + h ( x ) t ( x ) + A s δ + B r δ − r s δ 2 ⏟ 私有部分 \left(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta\right)\left(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta\right)=\alpha\beta+\underbrace{\sum_{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x))}_\text{公开部分} + \underbrace{\sum_{i=\ell+1}^m a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x)) + h(x)t(x) + As\delta + Br\delta - rs\delta^2}_\text{私有部分} ( α + i = 1 ∑ m a i u i ( x ) + rδ ) ( β + i = 1 ∑ m a i v i ( x ) + sδ ) = α β + 公开部分 i = 1 ∑ ℓ a i ( α v i ( x ) + β u i ( x ) + w i ( x )) + 私有部分 i = ℓ + 1 ∑ m a i ( α v i ( x ) + β u i ( x ) + w i ( x )) + h ( x ) t ( x ) + A sδ + B rδ − rs δ 2
我们希望公开部分和私有部分分别由 γ \gamma γ δ \delta δ
( α + ∑ i = 1 m a i u i ( x ) + r δ ) ( β + ∑ i = 1 m a i v i ( x ) + s δ ) = α β + γ ∑ i = 1 ℓ a i ( α v i ( x ) + β u i ( x ) + w i ( x ) ) γ + δ ∑ i = ℓ + 1 m a i ( α v i ( x ) + β u i ( x ) + w i ( x ) ) + h ( x ) t ( x ) δ + A s δ + B r δ − r s δ 2 (\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta)(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta)=\alpha\beta+\gamma\frac{\sum_{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x))}{\gamma} + \delta\frac{\sum_{i=\ell+1}^m a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x)) + h(x)t(x)}{\delta} + As\delta + Br\delta - rs\delta^2 ( α + i = 1 ∑ m a i u i ( x ) + rδ ) ( β + i = 1 ∑ m a i v i ( x ) + sδ ) = α β + γ γ ∑ i = 1 ℓ a i ( α v i ( x ) + β u i ( x ) + w i ( x )) + δ δ ∑ i = ℓ + 1 m a i ( α v i ( x ) + β u i ( x ) + w i ( x )) + h ( x ) t ( x ) + A sδ + B rδ − rs δ 2
其中一部分项中的 δ \delta δ
( α + ∑ i = 1 m a i u i ( x ) + r δ ) ( β + ∑ i = 1 m a i v i ( x ) + s δ ) = α β + γ ∑ i = 1 ℓ a i ( α v i ( x ) + β u i ( x ) + w i ( x ) ) γ + δ ( ∑ i = ℓ + 1 m a i ( α v i ( x ) + β u i ( x ) + w i ( x ) ) + h ( x ) t ( x ) δ + A s + B r − r s δ ) (\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta)(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta)=\alpha\beta+\gamma\frac{\sum_{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x))}{\gamma} + \delta\left(\frac{\sum_{i=\ell+1}^m a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x)) + h(x)t(x)}{\delta} + As + Br - rs\delta\right) ( α + i = 1 ∑ m a i u i ( x ) + rδ ) ( β + i = 1 ∑ m a i v i ( x ) + sδ ) = α β + γ γ ∑ i = 1 ℓ a i ( α v i ( x ) + β u i ( x ) + w i ( x )) + δ ( δ ∑ i = ℓ + 1 m a i ( α v i ( x ) + β u i ( x ) + w i ( x )) + h ( x ) t ( x ) + A s + B r − rsδ )
我们现在将此等式拆分为验证者和证明者两部分。带方框的项是验证者计算的部分，带下括号的项是证明者提供的部分：
( α + ∑ i = 1 m a i u i ( x ) + r δ ) ⏟ [ A ] 1 ( β + ∑ i = 1 m a i v i ( x ) + s δ ) ⏟ [ B ] 2 = α β + γ ∑ i = 1 ℓ a i ( α v i ( x ) + β u i ( x ) + w i ( x ) ) γ + δ ( ∑ i = ℓ + 1 m a i ( α v i ( x ) + β u i ( x ) + w i ( x ) ) + h ( x ) t ( x ) δ + A s + B r − r s δ ) ⏟ [ C ] 1 \underbrace{(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta)}_{[A]_1}\underbrace{(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta)}_{[B]_2}=\boxed{\alpha\beta}+\boxed{\gamma}\boxed{\frac{\sum_{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x))}{\gamma}} + \boxed{\delta}\underbrace{\left(\frac{\sum_{i=\ell+1}^m a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x)) + h(x)t(x)}{\delta} + As + Br - rs\delta\right)}_{[C]_1} [ A ] 1 ( α + i = 1 ∑ m a i u i ( x ) + rδ ) [ B ] 2 ( β + i = 1 ∑ m a i v i ( x ) + sδ ) = α β + γ γ ∑ i = 1 ℓ a i ( α v i ( x ) + β u i ( x ) + w i ( x )) + δ [ C ] 1 ( δ ∑ i = ℓ + 1 m a i ( α v i ( x ) + β u i ( x ) + w i ( x )) + h ( x ) t ( x ) + A s + B r − rsδ )
Groth16 证明算法
我们现在准备端到端地展示 Groth16 算法。可信设置和验证步骤与我们之前结合了 γ \gamma γ δ \delta δ r r r s s s
可信设置
α , β , τ , γ , δ ← 随机标量 [ τ n − 1 G 1 , τ n − 2 G 1 , … , τ G 1 , G 1 ] ← G 1 的 srs [ τ n − 1 G 2 , τ n − 2 G 2 , … , τ G 2 , G 2 ] ← G 2 的 srs [ τ n − 2 t ( τ ) δ G 1 , τ n − 3 t ( τ ) δ G 1 , … , τ t ( τ ) δ G 1 , t ( τ ) δ G 1 ] ← h ( τ ) t ( τ ) 的 srs 见证的公开部分 [ Ψ 1 ] 1 = α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) γ G 1 [ Ψ 2 ] 1 = α v 2 ( τ ) + β u 2 ( τ ) + w 2 ( τ ) γ G 1 ⋮ [ Ψ ℓ ] 1 = α v ℓ ( τ ) + β u ℓ ( τ ) + w ℓ ( τ ) γ G 1 见证的私有部分 [ Ψ ℓ + 1 ] 1 = α v ℓ + 1 ( τ ) + β u ℓ + 1 ( τ ) + w ℓ + 1 ( τ ) δ G 1 [ Ψ ℓ + 2 ] 1 = α v ℓ + 2 ( τ ) + β u ℓ + 2 ( τ ) + w ℓ + 2 ( τ ) δ G 1 ⋮ [ Ψ m ] 1 = α v m ( τ ) + β u m ( τ ) + w m ( τ ) δ G 1 \begin{align*}
\alpha,\beta,\tau,\gamma,\delta &\leftarrow \text{随机标量}\\
[\tau^{n-1}G_1,\tau^{n-2}G_1,\dots,\tau G_1,G_1] &\leftarrow \mathbb{G}_1 \text{ 的 srs}\\
[\tau^{n-1}G_2,\tau^{n-2}G_2,\dots,\tau G_2,G_2] &\leftarrow \mathbb{G}_2 \text{ 的 srs}\\
\left[\frac{\tau^{n-2}t(\tau)}{\delta}G_1,\frac{\tau^{n-3}t(\tau)}{\delta}G_1,\dots,\frac{\tau t(\tau)}{\delta}G_1,
\frac{t(\tau)}{\delta}G_1\right] &\leftarrow h(\tau)t(\tau) \text{ 的 srs}\\
\\
&\text{见证的公开部分}\\
[\Psi_1]_1 &= \frac{\alpha v_1(\tau) + \beta u_1(\tau) + w_1(\tau)}{\gamma}G_1\\
[\Psi_2]_1 &= \frac{\alpha v_2(\tau) + \beta u_2(\tau) + w_2(\tau)}{\gamma}G_1\\
&\vdots\\
[\Psi_\ell]_1 &= \frac{\alpha v_\ell(\tau) + \beta u_\ell(\tau) + w_\ell(\tau)}{\gamma}G_1\\
\\
&\text{见证的私有部分}\\
[\Psi_{\ell+1}]_1 &= \frac{\alpha v_{\ell+1}(\tau) + \beta u_{\ell+1}(\tau) + w_{\ell+1}(\tau)}{\delta}G_1\\
[\Psi_{\ell+2}]_1 &= \frac{\alpha v_{\ell+2}(\tau) + \beta u_{\ell+2}(\tau) + w_{\ell+2}(\tau)}{\delta}G_1\\
&\vdots\\
[\Psi_{m}]_1 &= \frac{\alpha v_{m}(\tau) + \beta u_{m}(\tau) + w_{m}(\tau)}{\delta}G_1\\
\end{align*} α , β , τ , γ , δ [ τ n − 1 G 1 , τ n − 2 G 1 , … , τ G 1 , G 1 ] [ τ n − 1 G 2 , τ n − 2 G 2 , … , τ G 2 , G 2 ] [ δ τ n − 2 t ( τ ) G 1 , δ τ n − 3 t ( τ ) G 1 , … , δ τ t ( τ ) G 1 , δ t ( τ ) G 1 ] [ Ψ 1 ] 1 [ Ψ 2 ] 1 [ Ψ ℓ ] 1 [ Ψ ℓ + 1 ] 1 [ Ψ ℓ + 2 ] 1 [ Ψ m ] 1 ← 随机标量 ← G 1 的 srs ← G 2 的 srs ← h ( τ ) t ( τ ) 的 srs 见证的公开部分 = γ α v 1 ( τ ) + β u 1 ( τ ) + w 1 ( τ ) G 1 = γ α v 2 ( τ ) + β u 2 ( τ ) + w 2 ( τ ) G 1 ⋮ = γ α v ℓ ( τ ) + β u ℓ ( τ ) + w ℓ ( τ ) G 1 见证的私有部分 = δ α v ℓ + 1 ( τ ) + β u ℓ + 1 ( τ ) + w ℓ + 1 ( τ ) G 1 = δ α v ℓ + 2 ( τ ) + β u ℓ + 2 ( τ ) + w ℓ + 2 ( τ ) G 1 ⋮ = δ α v m ( τ ) + β u m ( τ ) + w m ( τ ) G 1
可信设置公布
( [ α ] 1 , [ β ] 1 [ β ] 2 , [ γ ] 2 , [ δ ] 1 [ δ ] 2 , G 1 的 srs , G 2 的 srs , h ( τ ) t ( τ ) 的 srs , [ Ψ 1 ] 1 , [ Ψ 2 ] 1 , … , [ Ψ m ] 1 ) ([\alpha]_1,[\beta]_1[\beta]_2,[\gamma]_2,[\delta]_1[\delta]_2,G_1 \text{ 的 srs},G_2 \text{ 的 srs},h(\tau)t(\tau) \text{ 的 srs},[\Psi_1]_1,[\Psi_2]_1,\dots,[\Psi_m]_1) ([ α ] 1 , [ β ] 1 [ β ] 2 , [ γ ] 2 , [ δ ] 1 [ δ ] 2 , G 1 的 srs , G 2 的 srs , h ( τ ) t ( τ ) 的 srs , [ Ψ 1 ] 1 , [ Ψ 2 ] 1 , … , [ Ψ m ] 1 ) 证明者步骤
证明者拥有一个见证 a \mathbf{a} a r r r s s s
[ A ] 1 = [ α ] 1 + ∑ i = 1 m a i u i ( τ ) + r [ δ ] 1 [ B ] 1 = [ β ] 1 + ∑ i = 1 m a i v i ( τ ) + s [ δ ] 1 [ B ] 2 = [ β ] 2 + ∑ i = 1 m a i v i ( τ ) + s [ δ ] 2 [ C ] 1 = ∑ i = ℓ + 1 m a i [ Ψ i ] 1 + h ( τ ) t ( τ ) + [ A ] 1 s + [ B ] 1 r − r s [ δ ] 1 \begin{align*}
[A]_1 &= [\alpha]_1 + \sum_{i=1}^m a_iu_i(\tau)+r[\delta]_1\\
[B]_1 &= [\beta]_1 + \sum_{i=1}^m a_iv_i(\tau)+s[\delta]_1\\
[B]_2 &= [\beta]_2 + \sum_{i=1}^m a_iv_i(\tau)+s[\delta]_2\\
[C]_1 &= \sum_{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)+[A]_1s+[B]_1r-rs[\delta]_1\\
\end{align*} [ A ] 1 [ B ] 1 [ B ] 2 [ C ] 1 = [ α ] 1 + i = 1 ∑ m a i u i ( τ ) + r [ δ ] 1 = [ β ] 1 + i = 1 ∑ m a i v i ( τ ) + s [ δ ] 1 = [ β ] 2 + i = 1 ∑ m a i v i ( τ ) + s [ δ ] 2 = i = ℓ + 1 ∑ m a i [ Ψ i ] 1 + h ( τ ) t ( τ ) + [ A ] 1 s + [ B ] 1 r − rs [ δ ] 1 证明者公布 ( [ A ] 1 , [ B ] 2 , [ C ] 1 , [ a 1 , . . . , a ℓ ] ) ([A]_1, [B]_2, [C]_1, [a_1,...,a_\ell]) ([ A ] 1 , [ B ] 2 , [ C ] 1 , [ a 1 , ... , a ℓ ])
验证者步骤
验证者检查
[ X ] 1 = ∑ i = 1 ℓ a i Ψ i [ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ [ γ ] 2 + [ C ] 1 ∙ [ δ ] 2 \begin{align*}
[X]_1&=\sum_{i=1}^\ell a_i\Psi_i\\
[A]_1\bullet[B]_2 &\stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet [\gamma]_2 + [C]_1\bullet [\delta]_2
\end{align*} [ X ] 1 [ A ] 1 ∙ [ B ] 2 = i = 1 ∑ ℓ a i Ψ i = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ [ γ ] 2 + [ C ] 1 ∙ [ δ ] 2
在 Solidity 中验证 Groth16
到了这里，你已经具备了足够的知识去理解 Solidity 中的证明验证代码。这是 Tornado Cash 的证明验证代码 。鼓励读者仔细阅读其源代码。如果读者熟悉 Solidity 汇编编程，那么理解这段源代码将不会很困难，因为变量名与本文中的变量名是一致的。
此外也有库支持 Solana 上的 Groth16 。
需要注意的安全问题
Groth16 具有延展性 (Malleable)
Groth16 证明是具有延展性的。给定一个有效的证明
( [ A ] 1 , [ B ] 2 , [ C ] 1 ) ([A]_1, [B]_2, [C]_1) ([ A ] 1 , [ B ] 2 , [ C ] 1 ) [ A ] 1 [A]_1 [ A ] 1 [ B ] 2 [B]_2 [ B ] 2 ( [ A ′ ] 1 , [ B ′ ] 2 , [ C ] 1 ) ([A']_1, [B']_2, [C]_1) ([ A ′ ] 1 , [ B ′ ] 2 , [ C ] 1 ) [ A ′ ] 1 = n e g ( [ A ] 1 ) [A']_1 = \mathsf{neg}([A]_1) [ A ′ ] 1 = neg ([ A ] 1 ) [ B ′ ] 2 = n e g ( [ B ] 2 ) [B']_2 = \mathsf{neg}([B]_2) [ B ′ ] 2 = neg ([ B ] 2 )
要理解为什么 [ A ] 1 ∙ [ B ] 2 = [ A ′ ] 1 ∙ [ B ′ ] 2 [A]_1\bullet[B]_2 = [A']_1\bullet[B']_2 [ A ] 1 ∙ [ B ] 2 = [ A ′ ] 1 ∙ [ B ′ ] 2
Copy from py_ecc.bn128 import G1, G2, multiply, neg, eq, pairing # chosen arbitrarily x = 10 y = 100 A = multiply(G1, x) B = multiply(G2, y) A_p = neg(A) B_p = neg(B) assert eq(pairing(B, A), pairing(B_p, A_p)) 直观地说，攻击者正在将 A A A B B B − 1 -1 − 1 ( − 1 ) × ( − 1 ) (-1)\times(-1) ( − 1 ) × ( − 1 )
因此，如果验证公式接受
[ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ [ γ ] 2 + [ C ] 1 ∙ [ δ ] 2 [A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet [\gamma]_2 + [C]_1\bullet [\delta]_2 [ A ] 1 ∙ [ B ] 2 = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ [ γ ] 2 + [ C ] 1 ∙ [ δ ] 2 那么它同样也会接受
n e g ( [ A ] 1 ) ∙ n e g ( [ B ] 2 ) = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ [ γ ] 2 + [ C ] 1 ∙ [ δ ] 2 \mathsf{neg}([A]_1)\bullet\mathsf{neg}([B]_2) \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet [\gamma]_2 + [C]_1\bullet [\delta]_2 neg ([ A ] 1 ) ∙ neg ([ B ] 2 ) = ? [ α ] 1 ∙ [ β ] 2 + [ X ] 1 ∙ [ γ ] 2 + [ C ] 1 ∙ [ δ ] 2
针对这种攻击的防御措施在下一节中描述。
你可以在这篇文章 中看到这种攻击的概念验证。
证明者可以为同一个见证创建无限数量的证明
这本身并不算是一个“安全问题”——这是实现零知识所必需的。然而，应用程序需要一套机制来追踪哪些事实已经被证明过，并且不能依赖于证明的唯一性来实现这一点。
通过 RareSkills 了解更多
我们免费发布此类材料的能力依赖于我们学生的持续支持。请考虑注册我们的 Zero Knowledge Bootcamp 、Web3 Bootcamps 或在 RareTalent 上寻找一份工作。
最初发布于 2023 年 8 月 31 日