零多项式

零知识证明详解五：计算转为多项式

简介：本⽂翻译⾃zcash官⽅博客，讲解zcash中所使⽤的zk-SNARKs的原理第五部分，此处是原⽂链接。友情提⽰：本⽂偏技术化，适合对技术和数学⾮常感兴趣的同学阅读。

zkSNARK是zero-knowledgesuccintnon-interactiveargumentsofknowledge的简称，意思是：简洁的⾮交互的零知识证明(本⽂授权BH好⽂好报群摘编、转载以及相关转授权推⽂⾏为)

在前三章，我们得出了⼀个处理多项式的⽅法。本章，我们研究下如何把我们想证明和验证的语句转化为多项式。

2013年，Gennaro,Gentry,Parno以及Raykova等⼈定义⼀种⾮常有⽤的、把计算转化为多项式的⽅法，叫做：⼆次运算程序(QAP)，QAPs已经成为了zk-SNARK构造⽅法的基础。

本章，我们将通过⼀些例⼦解释QAPs的转化⽅法。不过，你需要做好⼼⾥准备，即便我们只是使⽤⼀些⼩例⼦，也不可避免的要先理解⼀下其他的知识点。

假设，Alice想要向Bob证明她知道c_1,c_2,c_3inmathbb{F}_p，并使得(c_1*c_2)*(c_1+c_3)=7。第⼀步，我们先把上⾯的计算转化⼀个运算电路。

运算电路

运算电路由各种运算门（⽐如加法和乘法），以及连接门的线路构成。在我们上⾯的例⼦中，电路的样⼦如图所⽰：

底部的线路是输⼊线，顶部的线路是输出线，它给出输⼊在电路上计算的结果。

在图中可以看出，wds桥接 我们使⽤了⼀种特殊的⽅式为线路和门添加了标签，这些标签在接下来转换电路到QAP时有⽤：

1.当海归 相同的输出节点输出到不⽌⼀个门的时候，我们认为它是同⼀条，就像例⼦中的w1。

2.我们假设乘法门有且刚好有2条输⼊线，我们分别称之为左线和右线

3.我们没有标记出从加法门到乘法门的线，也没有标记加法门。我们认罗技保修 为加法的输⼊直接进⼊乘法门，所以，在上例中我们认为

w1

和

w3

都

是

g2的右输⼊。

针对电路的⼀个合法的赋值，是给被标记线的赋值，使得每个乘法门的输出值确实是相应输⼊的乘积。因此，对于我们的电路，⼀个合乎规范的赋值形式是：(c1,…,c5)其中c4=c1*c2并且c5=c4*(c1+c3)。

按照这种⽅式，Alice想豁达开朗 要证明的是，她知道⼀组合法的赋值(c_1,...,c_5)，可以满⾜c_5=7。下⼀步，是使⽤QAP将这个语句翻译成⼀个多项式。

简化为⼆次运算⽅程

我们将每个乘法门与域元素联系起来：g_1将与1inmathbb{F}_p联系起来，g_2与2inmathbb{F}_p联系起来。我们称点{1,2}为我们的

⽬标点。现在，我们需要定义“左线多项式smt技术员 ”集合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}^5c_i*L_i,R:=sum_{i=1}^5c_i*R_i,O:=sum_{i=1}^5c_i*O_i然后我们定义多项式P:=L*R-O

现在，在完成所有这些定义之后，核⼼点在于：当且仅当P在所有的⽬标点上等于0时，(c1,…,c5)才是⼀个对于电路的合法赋值。

(

译者注：作者这⾥少了⼀步，否则下⾯的验证会有些突兀：

L(X)=sum_{i=1}^5c_i*L_i=c_1(2-X)+c_4(X-1)

R(X)=sum_{i=1}^5c_i*R_i=c_1(X-1)+c_2(2-X)

O(X)=sum_{i=1}^5c_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和⼀个点ainmathbb{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}^mc_i⋅L_i

R:=sum_{i=1}^mc_i⋅R_i俞大维

O:=sum_{i=1}^mc_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（天平）。