本文翻译自zcash官方博客，讲解zcash中所使用的zk-SNARKs的原理第六部分，此处是原文链接。友情提示：本文偏技术化，适合对技术和数学非常感兴趣的同学阅读。
zkSNARK是zero-knowledge succint non-interactive arguments of knowledge的简称，意思是：简洁的非交互的零知识证明
(本文授权BH好文好报群摘编、转载以及相关转授权推文行为)
在第五章，我们看到了如何把Alice想要向Bob证明的语句翻译成等价的“多项式语言”，也就是二次运算方程(QAP).
在本章中，我们将展示Alice如何发送一个简短的证明给Bob，以显示她有一个能满足QAP的赋值。我们将会使用皮诺曹协议。首先，先让我们回忆一下QAP的定义：
一个d阶m大小的二次运算方程Q，由多项式L_1,…,L_m, R_1,…,R_m, O_1,…,O_m和一个d阶目标多项式T构成。
对于一组赋值(c_1,…,c_m)满足Q，如果定义
L := \sum_{i=1}^m c_i * L_i, R := \sum_{i=1}^m c_i * R_i, O:= \sum_{i=1}^m c_i*O_i,以及 P := L * R - O，那么我们可以断定T整除P。
就像我们在第五章看到的，Alice通常想证明她有一个具有额外条件的正确赋值，比如c_m = 7；不过我们这里为了简洁，先忽略它，仅仅展示如何证明她知道一个正确的赋值。
如果Alice有一个正确的赋值，意思是，像上面那样定义L,R,O,P，则存在一个多项式H，使得P = H * T。特别地，对于任意 s \in \mathbb{F}_p，我们都有P(s) = H(s) * T(s)
现在假如Alice没有一个正确的赋值，但是她用一个不满足条件的赋值(c_1,..., c_m)构造L, R, O, P，那么我们可以保证T不能整除P。这是说，对于任意一个阶次不大于d的多项式H，P, L, R, O, H都将是不同的多项式。注意，这里的P, L, R, O, H的阶次都最多不会超过2d。
现在我们可以用著名的Schwartz-Zippel定理了，它告诉我们，两个不同的阶次不大于2d的多项式，他们最多有2d个共同的点 s \in \mathbb{F}_p。因此，如果P比2d大很多，那么随机选择一个s就能满足P(s) = H(s) * T(s)的概率非常低。
于是可以草拟出下面这个可以验证Alice是否有一组正确赋值的协议：
- Alice选择如下阶次不大于d的多项式：L, R, O, H。
- Bob选择一个随机的点 s \in \mathbb{F}_{p'}，并计算出E(T(s))。
- Alice把那些多项式在点s处的隐藏数(E(L(s)), E(R(s)), E(O(s)), E(H(s)))发送给Bob。
- Bob检查如下方程是否在s处成立：E(L(s) * R(s) - O(s)) = E(T(s) * H(s))
再强调一次，如果Alice没有一组正确的赋值，那么她所使用的方程大概率下在s点不能成立，因此，在这种情况，她将不能通过Bob的验证。
有一个问题是我们是否有工具可以实现上面的协议。关键点在于Alice必须在不知道s的情况下选择出她要使用的多项式，而这正是我们在第二章到第四章讲到的可验证的盲式计算协议。
确保Alice是通过一组赋值生成她的协议的
这点很重要：如果Alice没有一组正确的赋值，也并不意味着她不能找到任何的阶次不大于d的，并且满足如下条件的L,R,O,H：L * R - O = T * H。这仅仅是说她不能通过同一组赋值(c_1, ..., c_m)得到这样的多项式: L:=\sum_{i=1}^m c_i*L_i, R:= \sum_{i=1}^m c_i* R_i, O := \sum_{i=1}^m c_i * O_i。
第四章的协议仅仅可以保证她使用了正确的阶次的多项式 L, R, O，但不能保证他们是从过同一组赋值产生的。这儿的形式化证明有点微妙；所以我们粗略的描述一下解决方案。
我们把多项式L, R, O组合成一个多项式F:
F = L + X^{d+1} * R + X ^ {2(d+1)} * O
将R于X^{d+1}相乘、O与x^{2(d+1)}相乘的原因是，这样L, R, O的系数在F中不会混合：1, X, ..., X^d刚好是L的系数，后面d+1个系数x^{d+1}, ..., X^{2d+1}刚好是R的系数，最后d+1个系数是O的。
让我们用同样的方式把QAP中的多项式组合起来，给每个i \in {1, ..., m}定义一个多项式F_i，它的第一部分d+1个系数是L_i的系数，之后的是R_i的系数，再之后是Q_i的系数。也就是说，对于每个i \in {1, ..., m}，我们定义这个多项式：
F_i = L_i + X^{d+1} * R_i + X^{2(d+1)} * O_i
注意，当我们把两个F_i相加时，L_i, R_i, O_i也分别相加。例如：
F_1 + F_2 = (L_1 + L_2) + X^{d+1} * (R_1 + R_2) + X ^{2(d+1)} * (O_1 + O_2)。
更一般地，假设对于(c_1, ..., c_m)我们有F = \sum_{i=1} ^m c_i * F_i ，那么我们将得到： L = \sum_{i=1}^m c_i * L_i, R = \sum_{i=1}^m c_i * R_i, O = \sum_{i=1}^m c_i * O_i，它们共用相同的(c_1, ..., c_m)。换句话说，如果F是F_i的线性组合，那么L, R, O就确实是从同一组赋值得到的。
因此，Bob将会请Alice证明F是F_i的线性组合，这个过程和盲式计算是类似的：
Bob选择一个随机的\beta \in \mathbb{F}_p^*，并把隐藏数E(\beta * F_i(s)), ..., E(\beta * F_m(s))发送给Alice，并请Alice发回E(\beta*F(s))。如果她成功了，根据扩展版本的KCA假设，就代表Alice知道如何对F_i进行线性组合，从而计算出F。
加入零知识-隐藏那组赋值
在zk-SNARK里，Alice想隐藏她的赋值的所有信息，然后这些隐藏数E(L(s)), E(R(s)), E(O(s)), E(H(s))多少还是提供了一些信息。
比如，给定一些其他的符合条件的赋值(c_1, ..., c_m)，Bob可以分别计算出对应的L', R', O', H'，以及它们的隐藏数E(L'(s)), E(R'(s)), E(O'(s)), E(H'(s))。如果这些结果与Alice的隐藏数不同，那么他可以断定(c'_1, ..., c'_m)不是Alice的赋值。
为了避免这种的信息泄漏，Alice想给每个多项式添加一些随机数作为偏移量T，用以隐藏他的赋值。这样，她选择了随机的\sigma_1, \sigma_2, \sigma_3 \in F_p^*，并定义：
L_z:= L + \sigma_1 * T, R_z := R + \sigma_2 * T, O_z := O + \sigma_3 * T。
假设 L, R, O是通过一组正确的赋值得到了，因此对于某个多项式H, 可以使得L * R - O = T * H。因为我们刚刚在每个地方都加了个T的倍数，因此T也能整除L_z * R_z - Oz。看看我们下面的计算：
L_z * R_z - O_z = (L + \sigma_1 * T)(R + \sigma_2 * T) - O - \sigma_3*T
=(L*R - O) + L*\sigma_2*T + \sigma_1 * T * R + \sigma_1 \sigma_2*T^2 - \sigma_3*T
=T*(H + L* \sigma_2 + \sigma_1 * R + \sigma_1 \sigma_2*T - \sigma_3)
如此，我们定义H_z = H + L* \sigma_2 + \sigma_1 * R + \sigma_1 \sigma_2*T - \sigma_3，我们就得到了： L_z * R_z - O_z = T * H_z。因此，如果Alice没使用L, R, O, H，而使用了L_z, R_z, O_z, H_z，那么Bob仍能接受。
换句话说，这些多项式在点s \in \mathbb{F}_p, T(s) \neq 0的计算，没有揭示出任何原有赋值的信息。例如，因为T(s) \neq 0并且\sigma_1是随机的，所以\sigma_1 * T(s)也是一个随机的值，因此，L_z(s) = L(s) + \sigma_1 * T(s)没有揭示出L(s)的任何信息，因为它被随机数给掩盖了。
下一章讲什么？
我们勾勒了出了一个皮诺曹协议，在这个协议里，Alice可以让Bob相信她拥有一组可以供QAP应用的赋值，并且没有泄漏任何关于这组赋值的信息。为了得到zk-SNARK，这里仍有两个主要的问题未被解决：
- 在这个协议中，Bob需要一个支持乘法的同态加密函数(HH)。比如，他需要根据E(H(s))和E(T(s))计算出E(H(s) * T(s))。然而，目前为止，我们还没有看到过这种HH的例子，我们只见过可以支持加法和线性组合的HH。
- 在这个系列中，我们讨论了Alice和Bob间的交互式协议。不过，我们的最终目标是，能够让Alice发送一个单一的不需要交互的证明信息，并且可以被公开的验证——也就是说，任何人都可以看见这个证明信息，都可以验证她的合法性，而不仅仅是Bob(之前和Alice交流过的那个人)可以验证。
这两个问题将会通过应用双椭圆曲线解决，我们在下一章，也是最后一章，会讲解。
早赞声明：为方便早赞、避免乱赞，“BH好文好报群”为点赞者、写作者牵线搭桥，实行“先审后赞、定时发表”的规则，也让作品脱颖而出、速登热门！加群微信：we01230123（天平）。
