原文链接
<<< 第五部分
在第五部分我们看到一个Alice想要证明给Bob看的陈述是如何被转化成等价的被称为2次算术程序(QAP)的“多项式语言”形式。
在本文中，我们将展示Alice如何发送一个很短的证明给Bob，来表明她有一个到QAP的满意分配。我们将使用Parno, Howell, Gentry and Raykova发明的皮诺曹协议。但是首先让我们回忆一下QAP的定义：
一个大小为 m m m 的 d d d 阶二次算术程序Q由多项式 L 1 , . . . , L m , R 1 , . . . , R m , O 1 , . . . , O m L_1,...,L_m, R_1,...,R_m, O_1,...,O_m L1,...,Lm,R1,...,Rm,O1,...,Om 和一个 d d d 阶的目标多项式 T T T 组成。
我们 定义 L : Σ i = 1 m c i ⋅ L i , R : = Σ i = 1 m c i ⋅ R i , O : = Σ i = 1 m c i ⋅ O i L: \Sigma_{i=1}^m c_i \cdot L_i, R:=\Sigma_{i=1}^m c_i \cdot R_i, O:=\Sigma_{i=1}^m c_i \cdot O_i L:Σi=1mci⋅Li,R:=Σi=1mci⋅Ri,O:=Σi=1mci⋅Oi 和 P : = L ⋅ R − O P:=L \cdot R−O P:=L⋅R−O，如果分配 ( c 1 , . . . , c m ) (c_1,...,c_m) (c1,...,cm) 满足 Q，我们有 T T T 能除 P P P。
正如我们在第五部分看到的，Alice典型地想去证明她有一个满意分配，并附有一个额外限制，例如 c m = 7 c_m=7 cm=7； 但是我们在这里为了简单先忽略这个限制，展示一下如何仅仅证明某个满意分配的知识。
如果Alice有一个满意分配，这意味着，像上面那样定义 L , R , O , P L,R,O,P L,R,O,P，就会存在一个多项式 H H H 使得 P = H ⋅ T P=H \cdot T P=H⋅T。特别地，对任意 s ∈ F p s \in \textbf F_p s∈Fp 我们有 P ( s ) = H ( s ) ⋅ T ( s ) P(s)=H(s) \cdot T(s) P(s)=H(s)⋅T(s)。
假定现在Alice没有一个满意分配，但是她仍然像上面那样在一些非满意分配 ( c 1 , . . . , c m ) (c_1,...,c_m) (c1,...,cm) 的基础上构造 L , R , O , P L,R,O,P L,R,O,P。于是我们可以确定 T T T 不能除 P P P。这意味着对于任何最多 d − 2 d-2 d−2 阶多项式 H H H， P P P 和 L , R , O , H L,R,O,H L,R,O,H 将会是不同的多项式。注意这里 P P P 最多是 2 ( d − 1 ) 2(d-1) 2(d−1) 阶， L , R , O L,R,O L,R,O 最多 d − 1 d-1 d−1 阶， H H H 最多 d − 2 d-2 d−2 阶。
现在我们可以使用著名的 Schwartz-Zippel 辅助定理。它告诉我们2个阶数最多 2 d 2d 2d 的不同多项式可以在最多 2 d 2d 2d 个点 s ∈ F p s \in \textbf F_p s∈Fp 上相等。如果 p p p 比 2 d 2d 2d 大很多，那么 P ( s ) = H ( s ) ⋅ T ( s ) P(s)=H(s) \cdot T(s) P(s)=H(s)⋅T(s) 在一个随机选择的 s ∈ F p s \in \textbf F_p s∈Fp 上成立的概率是非常小的。
于是我们可以用下面的协议草案来测试是否Alice有一个满意分配。
Alice选择阶数最多为 d d d 的多项式 L , R , O , H L,R,O,H L,R,O,H。Bob选择一个随机点 s ∈ F p s \in \textbf F_p s∈Fp，并且计算 E ( T ( s ) ) E(T(s)) E(T(s))。Alice把所有这些多项式在点s的值的隐藏发送给Bob，也就是这些值 E ( L ( s ) ) , E ( R ( s ) ) , E ( O ( s ) ) , E ( H ( s ) ) E(L(s)),E(R(s)),E(O(s)),E(H(s)) E(L(s)),E(R(s)),E(O(s)),E(H(s))。Bob检查是否这些期望的方程在s点成立。也就是，他检查是否 E ( L ( s ) ⋅ R ( s ) − O ( s ) ) = E ( T ( s ) ⋅ H ( s ) ) E(L(s) \cdot R(s)−O(s))=E(T(s) \cdot H(s)) E(L(s)⋅R(s)−O(s))=E(T(s)⋅H(s))。再次说明，这里的要点是如果Alice没有一个满意分配，她最终会用到那些令方程无法全等的多项式，于是在多数的选择 s s s上都不成立。因此，在这样的情况下，Bob将以很高的概率拒绝他选择的 s s s。
问题是我们是否有实现这个草案的工具。最关键的点是Alice必须在不知道 s s s的情况下选择她将使用的多项式。但是这刚好是可验证盲求值协议中解决的问题。该解决办法是在本系列文章的第二到第四部分中开发出来的
已知我们有了这些，为了把草案变成一个 zk-SNARK，还有4个要点需要解决。在这里我们处理其中2个，剩下2个给本系列文章的下一部分。
这里是一个重要的点：如果Alice没有一个满意分配，并不意味着她无法找到任何阶数最多为d的多项式 L , R , O , H L,R,O,H L,R,O,H，使得 L ⋅ R − O = T ⋅ H L \cdot R-O=T \cdot H L⋅R−O=T⋅H，那只是意味着她无法找到这样的多项式使得 L , R L,R L,R 和 O O O 是“从分配中产生的”。换句话说，就是对同样的 ( c 1 , . . . , c m ) (c_1,...,c_m) (c1,...,cm)，有 L : = Σ i = 1 m c i ⋅ L i , R : = Σ i = 1 m c i ⋅ R i , O : = Σ i = 1 m c i ⋅ O i L:=\Sigma_{i=1}^m c_i⋅L_i,R:=\Sigma_{i=1}^m c_i⋅R_i, O:=\Sigma_{i=1}^m c_i⋅O_i L:=Σi=1mci⋅Li,R:=Σi=1mci⋅Ri,O:=Σi=1mci⋅Oi。
第四部分里的协议只是确保她在用一些有正确阶数的多项式 L , R , O L,R,O L,R,O，而不能确保它们是从分配中产生的。这是一个正式证明有一点微妙的地方；这里我们以一种不用很精确的方式来草拟解决方案。
让我们把多项式 L , R , O L,R,O L,R,O 合并成一个多项式 F F F，如下：
F = L + X d + 1 ⋅ R + X 2 ( d + 1 ) ⋅ O F=L+X^{d+1} \cdot R+X^{2(d+1)} \cdot O F=L+Xd+1⋅R+X2(d+1)⋅O
R乘以 X d + 1 X^{d+1} Xd+1 和 O O O 乘以 X 2 ( d + 1 ) X^{2(d+1)} X2(d+1) 的要点是 L , R , O L,R,O L,R,O 的系数在 F F F 中“不会混在一起”： F F F 中的系数 1 , X , . . . , X d 1,X,...,X^d 1,X,...,Xd 刚好是 L L L 的系数，接下来的 d + 1 d+1 d+1 个系数 X d + 1 , . . . , X 2 d + 1 X^{d+1},...,X^{2d+1} Xd+1,...,X2d+1 刚好是 R R R 的系数，最后 d + 1 d+1 d+1 个是 O O O 的。
让我们用类似的方法来把QAP定义中的多项式合并起来。为每个 i ∈ { 1 , . . . , m } i \in \{1,...,m\} i∈{1,...,m} 定义 一个多项式 F i F_i Fi，它的前面 d + 1 d+1 d+1 个 系数是 L i L_i Li 的系数，接下来是 R i R_i Ri, 然后是 O i O_i Oi。也就是，对于每个 i ∈ { 1 , . . . , m } i \in \{1,...,m\} i∈{1,...,m}，我们定义多项式
F i = L i + X d + 1 ⋅ R i + X 2 ( d + 1 ) ⋅ O i F_i=L_i+X^{d+1} \cdot R_i + X^{2(d+1)} \cdot O_i Fi=Li+Xd+1⋅Ri+X2(d+1)⋅Oi
注意当我们对 F i F_i Fi 中的两项求和时， L i L_i Li， R i R_i Ri，和 O i O_i Oi 会各自区隔地在内部做两项的求和。例如， F 1 + F 2 = ( L 1 + L 2 ) + X d + 1 ⋅ ( R 1 + R 2 ) + X 2 ( d + 1 ) ⋅ ( O 1 + O 2 ) F1+F2=(L1+L2)+X^{d+1} \cdot (R1+R2)+X^{2(d+1)} \cdot (O1+O2) F1+F2=(L1+L2)+Xd+1⋅(R1+R2)+X2(d+1)⋅(O1+O2)
更一般地，假定对于一些 ( c 1 , . . . , c m ) (c_1,...,c_m) (c1,...,cm)，我们有 F = Σ i = 1 m c i ⋅ F i F=\Sigma_{i=1}^m c_i \cdot F_i F=Σi=1mci⋅Fi。然后对于同样的系数 ( c 1 , . . . , c m ) (c_1,...,c_m) (c1,...,cm)， 我们将同样有 L = Σ i = 1 m c i ⋅ L i , R = Σ i = 1 m c i ⋅ R i , O = Σ i = 1 m c i ⋅ O i L=\Sigma_{i=1}^m c_i \cdot L_i, R=\Sigma_{i=1}^m c_i \cdot R_i, O=\Sigma_{i=1}^m c_i \cdot O_i L=Σi=1mci⋅Li,R=Σi=1mci⋅Ri,O=Σi=1mci⋅Oi。换句话说，如果 F F F 是一个 F i F_i Fi的线性组合，这意味着 L , R , O L,R,O L,R,O 实际上是从分配中产生的。
因此 Bob将要求Alice证明 F F F是 F i F_i Fi的线性组合。这可以用跟可验证求值协议类似的方法完成。
Bob选择一个随机 β ∈ F p ∗ \beta \in \textbf F_p^* β∈Fp∗，然后把隐藏 E ( β ⋅ F 1 ( s ) ) , … , E ( β ⋅ F m ( s ) ) E(β⋅F_1(s)),…,E(β⋅F_m(s)) E(β⋅F1(s)),…,E(β⋅Fm(s)) 发送给Alice。然后他叫Alice把元素 E ( β ⋅ F ( s ) ) E(β⋅F(s)) E(β⋅F(s)) 发送给他。如果她成功了，一个系数知识假设的扩展版本意味着她知道如何把 F F F 写成 F i F_i Fi 的线性组合。
在一个zk-SNARK里，Alice想要隐藏关于她分配的所有信息。然而隐藏 E ( L ( s ) ) , E ( R ( s ) ) , E ( O ( s ) ) , E ( H ( s ) ) E(L(s)),E(R(s)),E(O(s)),E(H(s)) E(L(s)),E(R(s)),E(O(s)),E(H(s)) 确实提供了一些关于分配的信息 。
例如，给定一些另外 的满意分配 ( c 1 ′ , … , c m ′ ) (c'_1,…,c'_m) (c1′,…,cm′)，Bob可以计算出相应的 L ′ , R ′ , O ′ , H ′ L',R',O',H' L′,R′,O′,H′ 和 隐藏 E ( L ′ ( s ) ) , E ( R ′ ( s ) ) , E ( O ′ ( s ) ) , E ( H ′ ( s ) ) E(L'(s)),E(R'(s)),E(O'(s)),E(H'(s)) E(L′(s)),E(R′(s)),E(O′(s)),E(H′(s))。如果这些跟Alice的隐藏不一样，他可以推断出 c 1 ′ , … , c m ′ ) c'_1,…,c'_m) c1′,…,cm′) 不是Alice的分配。
为了避免关于她分配的信息泄漏，Alice将为每个多项式增加一个“随机T偏移”，来达到隐藏她的分配的目的。那就是，她选择随机的 δ 1 , δ 2 , δ 3 ∈ F p ∗ \delta_1,\delta_2,\delta_3 \in \textbf F_p^* δ1,δ2,δ3∈Fp∗，并且定义 L z : = L + δ 1 ⋅ T , R z : = R + δ 2 ⋅ T , O z : = O + δ 3 ⋅ T L_z:=L+δ_1⋅T, R_z:=R+δ_2⋅T, O_z:=O+δ_3⋅T Lz:=L+δ1⋅T,Rz:=R+δ2⋅T,Oz:=O+δ3⋅T。
Assume L,R,O were produced from a satisfying assignment; hence, L⋅R−O=T⋅H for some polynomial H. As we’ve just added a multiple of T everywhere, T also divides Lz⋅Rz−Oz. Let’s do the calculation to see this:
假设 L , R , O L,R,O L,R,O 是从一个满意分配中生成的；于是，对于某个多项式 H H H，我们有 L ⋅ R − O = T ⋅ H L⋅R−O=T⋅H L⋅R−O=T⋅H。由于我们刚在每个地方都加了T，T也能除 L z ⋅ R z − O z L_z \cdot R_z - O_z Lz⋅Rz−Oz。让我们做一个计算来说明这一点：
L z ⋅ R z − O z = ( L + δ 1 ⋅ T ) ( R + δ 2 ⋅ T ) – O − δ 3 ⋅ T = ( L ⋅ R − O ) + L ⋅ δ 2 ⋅ T + δ 1 ⋅ T ⋅ R + δ 1 δ 2 ⋅ T 2 – δ 3 ⋅ T = T ⋅ ( H + L ⋅ δ 2 + δ 1 ⋅ R + δ 1 δ 2 ⋅ T – δ 3 ) L_z⋅R_z−O_z=(L+δ_1⋅T)(R+δ_2⋅T)–O−δ_3⋅T =(L⋅R−O)+L⋅δ_2⋅T+δ_1⋅T⋅R+δ_1δ_2⋅T^2–δ3⋅T =T⋅(H+L⋅δ_2+δ_1⋅R+δ_1δ_2⋅T–δ_3) Lz⋅Rz−Oz=(L+δ1⋅T)(R+δ2⋅T)–O−δ3⋅T=(L⋅R−O)+L⋅δ2⋅T+δ1⋅T⋅R+δ1δ2⋅T2–δ3⋅T=T⋅(H+L⋅δ2+δ1⋅R+δ1δ2⋅T–δ3)
于是，定义 H z = H + L ⋅ δ 2 + δ 1 ⋅ R + δ 1 δ 2 ⋅ T − δ 3 H_z=H+L⋅δ_2+δ_1⋅R+δ_1δ_2⋅T−δ_3 Hz=H+L⋅δ2+δ1⋅R+δ1δ2⋅T−δ3，我们有 L z ⋅ R z = T ⋅ H z L_z \cdot R_z=T \cdot H_z Lz⋅Rz=T⋅Hz。因此，如果Alice采用多项式 L z , R z , O z , H z L_z,R_z,O_z,H_z Lz,Rz,Oz,Hz 而不是 L , R , O , H L,R,O,H L,R,O,H，Bob将总是接受。
另一方面，这些多项式在 T ( s ) ≠ 0 T(s) \, \neq 0 T(s)̸=0 ( 除了在那d个s上）的情况下在点 s ∈ F p s \in \textbf F_p s∈Fp 上求值，并不泄露关于分配的信息 。例如，由于 T ( s ) T(s) T(s) 非零并且 δ 1 \delta_1 δ1 是随机的 ， δ 1 ⋅ T ( s ) \delta_1 \cdot T(s) δ1⋅T(s) 是一个随机值，因此 L z ( s ) = L ( s ) + δ 1 ⋅ T ( s ) L_z(s)=L(s)+δ_1⋅T(s) Lz(s)=L(s)+δ1⋅T(s) 不会泄露关于 L ( s ) L(s) L(s) 的 信息，因为它被随机值掩盖了。
目前我们呈现了一个皮诺曹协议的草案。其中Alice可以在不需要泄露分配信息的情况下，说服Bob她拥有一个QAP的满意分配。为了达到zk-SNARK，还需要解决2个问题。
在这个草案中，Bob需要一个“支持乘法”的HH。例如，他需要利用 E ( H ( s ) ) 和 E ( T ( s ) ) E(H(s)) 和 E(T(s)) E(H(s))和E(T(s)) 来计算 E ( H ( s ) ⋅ T ( s ) ) E(H(s)⋅T(s)) E(H(s)⋅T(s))。然而目前我们还没有看到过一个HH能做到这一点的例子。我们只见过一个支持加法和线性组合的HH。
通过这个系列，我们已经讨论了Alice和Bob之间的交互协议 。然而我们最后的目标是能让Alice发送单消息非交互证明，而且是能够公开验证的。这意味着看到这单条消息证明的任何人将会被说服这条消息的有效性，而不光是Bob（他跟Alice之前有通信）。
这两个问题都可以用椭圆曲线配对来解决。我们将在下一个（也是最后一个）部分来讨论他们。
>>> 第七部分
