零知识证明详解五：计算转为多项式
简介：本文翻译自zcash官方博客，讲解zcash中所使用的zk-SNARKs的原理第五部分，此处是原文链接。友情提示：本文偏技术化，适合对技术和数学非常感兴趣的同学阅读。
zkSNARK是zero-knowledge succint non-interactive arguments of knowledge的简称，意思是：简洁的非交互的零知识证明
(本文授权BH好文好报群摘编、转载以及相关转授权推文行为)
在前三章，我们得出了一个处理多项式的方法。本章，我们研究下如何把我们想证明和验证的语句转化为多项式。
2013年，Gennaro, Gentry, Parno以及Raykova等人定义一种非常有用的、把计算转化为多项式的方法，叫做：二次运算程序(QAP)，QAPs已经成为了zk-SNARK构造方法的基础。
本章，我们将通过一些例子解释QAPs的转化方法。不过，你需要做好心里准备，即便我们只是使用一些小例子，也不可避免的要先理解一下其他的知识点。
假设，Alice想要向Bob证明她知道c_1, c_2, c_3 \in \mathbb{F}_p，并使得(c_1*c_2) * (c_1 + c_3) = 7。第一步，我们先把上面的计算转化一个运算电路。
运算电路
运算电路由各种运算门（比如加法和乘法），以及连接门的线路构成。在我们上面的例子中，电路的样子如图所示：
CircuitDrawing.png
底部的线路是输入线，顶部的线路是输出线，它给出输入在电路上计算的结果。
在图中可以看出，我们使用了一种特殊的方式为线路和门添加了标签，这些标签在接下来转换电路到QAP时有用：
- 当相同的输出节点输出到不止一个门的时候，我们认为它是同一条，就像例子中的w1。
- 我们假设乘法门有且刚好有2条输入线，我们分别称之为左线和右线
- 我们没有标记出从加法门到乘法门的线，也没有标记加法门。我们认为加法的输入直接进入乘法门，所以，在上例中我们认为
w1和w3都是g2的右输入。
针对电路的一个合法的赋值，是给被标记线的赋值，使得每个乘法门的输出值确实是相应输入的乘积。
因此，对于我们的电路，一个合乎规范的赋值形式是：(c1,…,c5) 其中 c4=c1*c2 并且 c5=c4*(c1+c3) 。
按照这种方式，Alice想要证明的是，她知道一组合法的赋值(c_1, ..., c_5)，可以满足c_5=7。下一步，是使用QAP将这个语句翻译成一个多项式。
简化为二次运算方程
我们将每个乘法门与域元素联系起来：g_1将与1 \in \mathbb{F}_p联系起来，g_2 与 2 \in \mathbb{F}_p 联系起来。我们称点{1,2}为我们的目标点。现在，我们需要定义 “左线多项式”集合 L1,…,L5 , “右线多项式” 集合R1,…,R5 以及 “输出多项式” 集合：O1,…,O5。
这些定义的想法是，非乘法门所涉及的多项式在目标点的取值一般为零。
具体来说，像w_1,w_2,w_4各自是g_1的左、右、和输出线；我们定义L_1=R_2=O_4=2-X，因为多项式2-X，根据g_1，在1点值是1，根据g_2，多项式在2点值是0。译者注：可将X=1代入验证 2-X = 2 - 1 = 1，将X=2代入验证：2-X = 2- 2=0
注意到w_1 和 w_3都是g_2的右输入。因此我们同样定义L_4=R_1=R_3=O_5=X-1——因为，根据g2，X-1在目标点2是1，而在另外一个点是0。
我们将其余的多项式都设置成零多项式。(译者注：也即L2=L_3=L_5=R_2=R_4=R_5=O_1=O_2=O_3 = 0)
给定 (c1,…,c5) 固定值，我们用他们作为系数来定义一个左、右和输出的“和”多项式。也就是说，我们定义：
L := \sum_{i=1}^5 c_i * L_i, R := \sum_{i=1}^5 c_i * R_i, O := \sum_{i=1}^5 c_i * O_i
然后我们定义多项式P := L * R - O
现在，在完成所有这些定义之后，核心点在于：当且仅当P在所有的目标点上等于0时， (c1,…,c5)才是一个对于电路的合法赋值。
(
译者注：作者这里少了一步，否则下面的验证会有些突兀：
L(X) = \sum_{i=1}^5 c_i * L_i = c_1(2-X)+c_4(X-1)
R(X) = \sum_{i=1}^5 c_i * R_i = c_1(X-1)+c_2(2-X)
O(X) = \sum_{i=1}^5 c_i * R_i = c_4(2-X)+c_5(X-1)
)
让我们使用例子来验证一下。假设我们定义 L,R,O,P ，采用上述给出的c_1,…,c_5。让我们在目标点1上计算所有的这些多项式：
在所有的L_i中，只有L_1在1点上是非零的。因此我们有L(1)=c_1⋅L_1(1)=c_1。同样，我们可以得到R(1)=c_2 和 O(1)=c_4。
(*译者注：
R(1) = c_1(1-1)+c_2(2-1) = c_2
O(1) = c_4(2-1)+c_5(1-1) = c_4
*)
因此，P(1)=c_1*c_2-c_4。 类似的可以计算出： P(2)=c_4*(c_1+c_3)-c_5。
换句话说，当且仅当(c_1, ..., c_5)是一组正确的赋值的时候，P在所有的目标点为0
现在，我们使用下面的代数事实：对于一个多项式 P 和一个点 a \in \mathbb{F}_p，当且仅当多项式 X-a 可以整除 P 时，我们有 P(a) = 0 ，比如 P=(X - a) * H ，H是某个多项式。
定义目标多项式 T(X) := (X-1)*(X-2)，当且仅当(c1,…,c5) 是一个合法的赋值时，我们有T 能整除 P。
根据上面的讨论，我们对于 QAP 做出如下定义：
一个d阶m大小的二次算术程序(QAP) Q，由多项式L_1,…,L_m, R_1,…,R_m, O_1,…,O_m 和 一个d阶目标多项式 T 构成。
如果给(c1,…,cm) 的赋值满足 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_1,...,c_5)满足上述的QAP,并且c_5 = 7。
总之，我们已经看到，像“我知道c_1,c_2,c_3能满足(c1⋅c2)⋅(c1+c3)=7”这样的语句，是怎么样通过QAP被转换成等价的多项式语句的。在下一篇中，我们将看到一个高效率的QAP协议。
早赞声明：为方便早赞、避免乱赞，“BH好文好报群”为点赞者、写作者牵线搭桥，实行“先审后赞、定时发表”的规则，也让作品脱颖而出、速登热门！加群微信：we01230123（天平）。
