原文出自：https://blog.z.cash/snark-explain5/
作者：Ariel Gabizon
译者：Matter实验室
In the three previous parts, we developed a certain machinery for dealing with polynomials. In this part, we show how to translate statements we would like to prove and verify to the language of polynomials. The idea of using polynomials in this way goes back to the groundbreaking work of Lund, Fortnow, Karloff and Nisan.
在之前的三篇文章中，我们开发了处理多项式的一个中心构件。 在本篇文章中，我们将展示如何将我们想要证明和验证的状态转换成多项式语言。这种采用多项式的想法可以追溯到Lund,Fortnow,Karloff以及Nisan的开创性工作——交互式证明系统的代数方法。
In 2013, another breakthrough work of Gennaro, Gentry, Parno and Raykova defined an extremely useful translation of computations into polynomials called a Quadratic Arithmetic Program (QAP). QAPs have become the basis for modern zk-SNARK constructions, in particular those used by Zcash.
在2018年，另外一项突破性工作(Gennaro, Gentry, Parno 和 Raykova)定义了一个极为有用的将计算转换为多项式的方法，被称为二次算术程序(QAP)。QAPs 已经成为了当前zk-SNARK结构的基础，尤其是其被Zcash使用了。
In this post we explain the translation into QAPs by example. Even when focusing on a small example rather than the general definition, it is unavoidable that it is a lot to digest at first, so be prepared for a certain mental effort :).
在本篇博文中，我们使用一个例子解释了 QAPs 的转换过程。即便关注与一个小例子而不是一般定义，也不可避免的需要先理解一些东西，所以在阅读前请先做好脑力准备:)。
Suppose Alice wants to prove to Bob she knows c1,c2,c3∈Fp such that (c1⋅c2)⋅(c1+c3)=7. The first step is to present the expression computed from c1,c2,c3 as an arithmetic circuit.
假设 Alice 想要向 Bob 证明她知道 c1,c2,c3∈Fp 满足(c1⋅c2)⋅(c1+c3)=7。第一步需要将从 c1,c2,c3 开始计算的表达式表示成一个数字电路。
ARITHMETIC CIRCUITS
数字电路
An arithmetic circuit consists of gates computing arithmetic operations like addition and multiplication, with wires connecting the gates. In our case, the circuit looks like this:
一个数字电路由多个通过使用线路链接的数字运算门组成，这些运算可以是加法和乘法。 在我们的例子中，电路的样子如图所示：
数字电路
The bottom wires are the input wires, and the top wire is the output wire giving the result of the circuit computation on the inputs.
在底部的线路是输入线路，在顶部的线路是输出线路，它给出输入在电路上计算的结果。
As can be seen in the picture, we label the wires and gates of the circuit in a very particular way, that is needed for the next step of translating the circuit into a QAP:
When the same outgoing wire goes into more than one gate, we still think of it as one wire – like w1 in the example.
We assume multiplication gates have exactly two input wires, which we call the left wire and right wire.
We don’t label the wires going from an addition to multiplication gate, nor the addition gate; we think of the inputs of the addition gate as going directly into the multiplication gate. So in the example we think of w1 and w3 as both being right inputs of g2.
在图中可以看出，我们使用一种特殊的方式为线路和环路的门添加了标签，这些标签在接下来转换电路到QAP时有用:
-
当相同的输出节点输出到不止一个门的时候，我们认为他是同一条，就像例子中的w1。
-
我们假设乘法门有两个输入线，我们将其称为左输入线和右输入线。
-
我们不会标记从加法门到乘法门的线，也不会标记加法门；我们认为加法门的输入直接进入到乘法门中。因此，在例子中，我们认为w1和w3都是g2的右输入。
A legal assignment for the circuit, is an assignment of values to the labeled wires where the output value of each multiplication gate is indeed the product of the corresponding inputs.
针对电路的一个合法的赋值，是给被标记线的赋值，在这儿每个乘法门的输出值确实是相应输入的产物。
So for our circuit, a legal assignment is of the form: (c1,…,c5) where c4=c1⋅c2 and c5=c4⋅(c1+c3).
因此，对于我们的电路，一个合乎规范的赋值形式是：(c1,…,c5) 其中 c4=c1⋅c2 并且 c5=c4⋅(c1+c3) 。
In this terminology, what Alice wants to prove is that she knows a legal assignment (c1,…,c5) such that c5=7. The next step is to translate this statement into one about polynomials using QAPs.
在这样的语句中，Alice想要证明的是她知道一个对(c1,…,c5)的合法的赋值，可以满足c5=7。下一步是使用QAPs将这样的语句翻译成一个多项式。
REDUCTION TO A QAP
还原一个QAP
We associate each multiplication gate with a field element: g1 will be associated with 1∈Fp and g2 with 2∈Fp. We call the points {1,2} our target points. Now we need to define a set of “left wire polynomials” L1,…,L5, “right wire polynomials” R1,…,R5 and “output wire polynomials” O1,…,O5.
我们将每个乘法门与域元素联系起来，g1将与1∈Fp联系起来，g2 与 2∈Fp 联系起来。我们称点{1,2}为我们的目标点。现在，我们需要定义 “左线多项式” L1,…,L5 集合, “右线多项式” R1,…,R5集合 以及 “输出多项式” O1,…,O5集合。
The idea for the definition is that the polynomials will usually be zero on the target points, except the ones involved in the target point’s corresponding multiplication gate.
对于这些定义的想法是多项式在目标点的取值一般为零，除了目标点的涉及的乘法门所包含的那些多项式外。
Concretely, as w1,w2,w4 are, respectively, the left, right and output wire of g1; we define L1=R2=O4=2−X, as the polynomial 2−X is one on the point 1 corresponding to g1 and zero on the point 2 corresponding to g2.
具体来说，像w1,w2,w4各自是g1的左、右、和输出线；我们定义L1=R2=O4=2−X，作为多项式2-X，根据g1，多项式在1点值是一，根据g2，多项式在2点值是零。
Note that w1 and w3 are both right inputs of g2. Therefore, we define similarly L4=R1=R3=O5=X−1 – as X−1 is one on the target point 2 corresponding to g2 and zero on the other target point.
注意到w1 和 w3都是g2的右输入。因此我们同样定义L4=R1=R3=O5=X−1——因为，根据g2，X-1在目标点2是一，而在另外一个点是零。
We set the rest of the polynomials to be the zero polynomial.
我们将其余的多项式都设置成零多项式。
Given fixed values (c1,…,c5) we use them as coefficients to define a left, right, and output “sum” polynomials. That is, we define
L:=∑(5,i=1) ci⋅Li
R:=∑(5,i=1) ci⋅Ri
O:=∑(5,i=1) ci⋅Oiand then we define the polynomial P:=L⋅R−O.
给定 (c1,…,c5) 固定值，我们用他们作为一个系数来定义一个左、右和输出的“和”多项式。也就是说，我们定义：
L:=∑(5,i=1) ci⋅Li
R:=∑(5,i=1) ci⋅Ri
O:=∑(5,i=1) ci⋅Oi
之后，我们再定义多项式 P:=L⋅R−O
Now, after all these definitions, the central point is this: (c1,…,c5) is a legal assignment to the circuit if and only if P vanishes on all the target points.
现在，在完成所有这些定义之后，关键点在于： (c1,…,c5) 是一个对于电路的合法赋值，当且仅当P在所有的目标点上取零。
Let’s examine this using our example. Suppose we defined L,R,O,P as above given some c1,…,c5. Let’s valuate all these polynomials at the target point 1:
让我们使用例子来验证一下。假设我们定义 L,R,O,P ，采用上述给出的c1,…,c5。让我们在目标点1上计算所有的这些多项式：
Out of all the Li’s only L1 is non-zero on 1. So we have L(1)=c1⋅L1(1)=c1. Similarly, we get R(1)=c2 and O(1)=c4.
Therefore, P(1)=c1⋅c2−c4. A similar calculation shows P(2)=c4⋅(c1+c3)–c5.
在所有的Li中，只有L1在1点上是非零的。因此我们有L(1)=c1⋅L1(1)=c1。同样，我们可以得到R(1)=c2 和 O(1)=c4。
因此，P(1)=c1⋅c2−c4。 一个类似的计算是： P(2)=c4⋅(c1+c3)–c5。
In other words, P vanishes on the target points if and only if (c1,…,c5) is a legal assignment.
也就是说，当且仅当 (c1,…,c5) 被合法赋值后，P 在目标点位的值为零。
Now, we use the following algebraic fact: For a polynomial P and a point a∈Fp, we have P(a)=0 if and only if the polynomial X−a divides P, i.e. P=(X−a)⋅H for some polynomial H.
现在，我们使用下面的代数事实：对于一个多项式 P 和一个点 a∈Fp，当且仅当多项式 X−a 可以整除 P 时，我们有 P(a)=0 ，比如 P=(X−a)⋅H ，H是一些多项式。
Defining the target polynomial T(X):=(X−1)⋅(X−2), we thus have that T divides P if and only if (c1,…,c5) is a legal assignment.
定义目标多项式 T(X):=(X−1)⋅(X−2)，当且仅当 (c1,…,c5) 是一个合法的赋值时，我们确信 T 能整除 P。
Following the above discussion, we define a QAP as follows:
A Quadratic Arithmetic Program Q of degree d and size m consists of polynomials L1,…,Lm, R1,…,Rm, O1,…,Om and a target polynomial T of degree d.
An assignment (c1,…,cm) satisfies Q if, defining
L:=∑(m,i=1) ci⋅Li
R:=∑(m,i=1) ci⋅Ri
O:=∑(m,i=1) ci⋅Oi
and
P:=L⋅R−O
we have that T divides P.In this terminology, Alice wants to prove she knows an assignment (c1,…,c5) satisfying the QAP described above with c5=7.
根据上面的讨论，我们对于 QAP 做出如下定义：
一个d阶m大小的二次算术程序(QAP) Q，由多项式L1,…,Lm, R1,…,Rm, O1,…,Om 和 一个d阶目标多项式 T 构成。
如果 (c1,…,cm) 的值满足 Q，定义
L:=∑(m,i=1) ci⋅Li
R:=∑(m,i=1) ci⋅Ri
O:=∑(m,i=1) ci⋅Oi
和
P:=L⋅R−O
我们可以确定T可以整除P。
在这些语句中，Alice想要证明他知道一个限定c5=7的(c1,...,c5)的值满足上述描述的QAP。
To summarize, we have seen how a statement such as “I know c1,c2,c3 such that (c1⋅c2)⋅(c1+c3)=7” can be translated into an equivalent statement about polynomials using QAPs. In the next part, we will see an efficient protocol for proving knowledge of a satisfying assignment to a QAP.
总之，我们已经看到，使用QAPs，像“我知道c1,c2,c3能满足(c1⋅c2)⋅(c1+c3)=7”这样的语句能被转换成等价的多项式语句。在下一篇中，我们将看到一个高效率的QAP协议，这个协议可以证明满足条件的知识。
[1]In this post we tried to give the most concise example of a reduction to QAP; we also recommend Vitalik Buterin’s excellent post for more details on the transformation from a program to a QAP.
[1]在本篇博文中，我们尝试使用最简便的例子来还原 QAP；我们同样推荐 Vitalik Buterin 关于如何将程序转换到 QAP 的更多细节的精彩博文
译者总结
数学关系
网友评论