解释 SNARKs 第五部分: 从计算到多项式

<< 第四部分

在之前的讲解中,我们已经开发出一款求解多项式的机器。 在本篇博文中,我们将展示如何将我们需要我们需要验证的声明翻译成多项式语言。 使用多项式来验证声明的想法可以追溯到由 Lund, Fortnow, Karloff 和Nisan 撰写的文章 开创性的工作 一文中。

在 2013 年,另外一项突破性的工作 由 Gennaro, Gentry, Parno 和 Raykova 提出,并定义了一种极为有帮助的多项式计算翻译方法,被称为 二次算数编码 (QAP)。 QAPs 已经称为建立现代 zk-SNARK 的基础,它尤其被用于 Zcash 中。

在本篇博文中,我们使用一个例子解释了 QAPs 的工作过程。即便关注与一个小型的例子而不是一般定义,也不可避免的需要先阅读一些前期的摘要,所以在阅读前请先做好脑力准备:)。

假设 Alice 想要向 Bob 证明她知道 c1,c2,c3?pc1,c2,c3∈Fp 比如 (c1c2)(c1+c3)=7(c1⋅c2)⋅(c1+c3)=7。第一步需要将 c1,c2,c3c1,c2,c3 中计算得到的表达式列出一个 数字环路

数字环路

一个数字环路由多个数字计算门组成,其功能类似于加法和乘法,通过使用线路链接门。 在我们的应用场景中,环路的样子如图所示:

在底部的线路是输入线路,在顶部的线路是输出线路,它将输出线路通过计算输入得到的计算结果。

在图中可以看出,我们使用一种特殊的方式为线路和环路的门添加了标签,这些做法将被用于解释环路并导入 QAP:

  • 当相同的输出先进入不同的门,我们将其视为同一根线 – 就像例子中的 ??w1
  • 我们假设乘法门有两个输入线,我们将其称为左侧输入线和右侧输入线。
  • 我们并不为从加法门进入乘法门的线路标记标签,也不为加法门设置标签;我们认为加法门的输出直接进入乘法门的输入。因此,在例子中,我们认为 ??w1??w3 都是 ??g2 的右侧输入。

针对环路的一个 合规的赋值,是针对被标签的线路的赋值过程,且只有在乘法门的输出确实是输入对应的乘积时才进行。

因此,对于我们的环路,一个合乎规范的赋值形式是:(c1,,c5)(c1,…,c5) 其中 c4=c1c2c4=c1⋅c2 并且 c5=c4(c1+c3)c5=c4⋅(c1+c3)

在这项术语中,Alice 需要证明她知道一个合乎规范的赋值形式 (c1,,c5)(c1,…,c5) 比如 c5=7c5=7。 下一步是将声明翻译,并使用 QAPs 将其导入多项式。

还原一个 QAP

我们将每个乘法门的输出与域元素联系起来,也就是 ??g1 将被联系到 1?p1∈Fp 同时 ??g2 将被联系到 2?p2∈Fp。 我们将 {1,2}{1,2} 称为我们的 目标点。 现在,我们需要定义一套 “左线多项式” L1,,L5L1,…,L5, “右线多项式” R1,,R5R1,…,R5 以及 “输出多项式” O1,,O5O1,…,O5

关于定义的想法时多项式在目标点位的取值一般为零,除非被包括在目标点位的取值与乘法门相对应。

具体来说,由于 ??,??,??w1,w2,w4 分别是 ??g1 的左线、右线和输出线;我们定义 L1=R2=O4=2XL1=R2=O4=2−X,由于多项式 2X2−X 是|g1| 中 11 对应的点,同时也是 ??g222 对应的零。

注意到 ??w1??w3 都是 ??g2 的右输入。因此,我们相似地定义 L4=R1=R3=O5=X1L4=R1=R3=O5=X−1 ,由于多项式 X1X−1是|g2| 中 22 对应的点,同时也是其他目标点中对应的零。

我们将其余的多项式都设置成零多项式。

对于一个固定取值的 (c1,,c5)(c1,…,c5),我们使用它作为系数来定义一个多项式的左、右和输出的 “相加”。 也就是说,我们定义

L:=5i=1ciLi,R:=5i=1ciRi,O:=5i=1ciOiL:=∑i=15ci⋅Li,R:=∑i=15ci⋅Ri,O:=∑i=15ci⋅Oi,

之后,我们再定义多项式 P:=LROP:=L⋅R−O

现在,在完成所有这些定义之后,关键问题在于: (c1,,c5)(c1,…,c5) 是一个对于环路的合规赋值,这个条件成立的前提是 如果 PP 在所有的目标点都取值为零

让我们使用例子来验证一下。假设我们定义 L,R,O,PL,R,O,P 是上述给出的 c1,,c5c1,…,c5。让我们在目标点 11 评价以上这些多项式:

在所有的 LiLi 中,只有 L1L111 点的取值非零。 隐私我们得到 L(1)=c1L1(1)=c1L(1)=c1⋅L1(1)=c1。 相似的,我们得到 R(1)=c2R(1)=c2O(1)=c4O(1)=c4

因此, P(1)=c1c2c4P(1)=c1⋅c2−c4。 一个相似的计算显示为 P(2)=c4(c1+c3)c5P(2)=c4⋅(c1+c3)−c5

也就是说,当且仅当 (c1,,c5)(c1,…,c5) 被合规赋值后,PP 在目标点位的值为零。

现在,我们使用下面的代数事实:对于一个多项式 PP 和一个点 a?pa∈Fp,当且晋档多项式 XaX−a 可以整除 PP 时,我们有 P(a)=0P(a)=0 ,比如 P=(Xa)HP=(X−a)⋅H 对于一些多项式 HH

定义 目标多项式 T(X):=(X1)(X2)T(X):=(X−1)⋅(X−2),当且仅当 (c1,,c5)(c1,…,c5) 是一个合规的赋值时,我们有 TT 整除 PP

根据上面的讨论,我们对于 QAP 做出如下定义:

一个二次算数程序 QQ,有 阶数 |d| *和尺寸 mm它由多项式 L1,,LmL1,…,Lm, R1,,RmR1,…,Rm, O1,,OmO1,…,Om 组成,并且有一个 *目标多项式 TT 阶数dd

一个赋值操作 (c1,,cm)(c1,…,cm) 满足 QQ * 如果,定义* L:=mi=1ciLi,R:=mi=1ciRi,O:=mi=1ciOiL:=∑i=1mci⋅Li,R:=∑i=1mci⋅Ri,O:=∑i=1mci⋅Oi * 并且 * P:=LROP:=L⋅R−O, * 我们得到* TT 可以整除 PP

在这些属于中,Alice 需要证明她知道了赋值 (c1,,c5)(c1,…,c5),且其满足 QAP 中描述的 c5=7c5=7

总结,我们已经看到了如这样的声明,“我知道 c1,c2,c3c1,c2,c3 ,因此 (c1c2)(c1+c3)=7(c1⋅c2)⋅(c1+c3)=7”,可以使用 QAPs 被翻译成多项式的表达方式。 在下一部分中,我们将看到验证知识以满足 QAP 中赋值运算的高效率协议。

[1] 在本篇博文中,我们尝试使用最简便的例子来还原 QAP;我们同样推荐 Vitalik Buterin 关于如何将程序翻译进 QAP 的精彩博文<https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649>`_。

Comments 1

发表评论

电子邮件地址不会被公开。 必填项已用*标注