您好!刚知道Zcash吗?
The Zcash network is young, but evolving quickly! Sign up and we'll be in touch with monthly highlights on ecosystem growth, network development and how to get started with Zcash!

语言

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

Ariel Gabizon | Apr 25, 2017

<< 第四部分

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

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

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

假设 Alice 想要向 Bob 证明她知道 \(c_1,c_2,c_3 \in \mathbb{F}_p\) 比如 \((c_1\cdot c_2)\cdot (c_1 + c_3) = 7\)。第一步需要将 \(c_1,c_2,c_3\) 中计算得到的表达式列出一个 数字环路

数字环路

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

An example of an arithmetic circuit

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

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

  • 当相同的输出先进入不同的门,我们将其视为同一根线 - 就像例子中的 \(\mathsf{w_1}\)
  • 我们假设乘法门有两个输入线,我们将其称为左侧输入线和右侧输入线。
  • 我们并不为从加法门进入乘法门的线路标记标签,也不为加法门设置标签;我们认为加法门的输出直接进入乘法门的输入。因此,在例子中,我们认为 \(\mathsf{w_1}\)\(\mathsf{w_3}\) 都是 \(\mathsf{g_2}\) 的右侧输入。

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

因此,对于我们的环路,一个合乎规范的赋值形式是:\((c_1,\ldots,c_5)\) 其中 \(c_4=c_1\cdot c_2\) 并且 \(c_5=c_4\cdot (c_1+c_3)\)

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

还原一个 QAP

我们将每个乘法门的输出与域元素联系起来,也就是 \(\mathsf{g_1}\) 将被联系到 \(1\in\mathbb{F}_p\) 同时 \(\mathsf{g_2}\) 将被联系到 \(2\in\mathbb{F}_p\)。 我们将 \(\{1,2\}\) 称为我们的 目标点。 现在,我们需要定义一套 “左线多项式” \(L_1,\ldots,L_5\), “右线多项式” \(R_1,\ldots,R_5\) 以及 “输出多项式” \(O_1,\ldots,O_5\)

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

具体来说,由于 \(\mathsf{w_1},\mathsf{w_2},\mathsf{w_4}\) 分别是 \(\mathsf{g_1}\) 的左线、右线和输出线;我们定义 \(L_1=R_2=O_4=2-X\),由于多项式 \(2-X\) 是|g1| 中 \(1\) 对应的点,同时也是 \(\mathsf{g_2}\)\(2\) 对应的零。

注意到 \(\mathsf{w_1}\)\(\mathsf{w_3}\) 都是 \(\mathsf{g_2}\) 的右输入。因此,我们相似地定义 \(L_4=R_1=R_3=O_5=X-1\) ,由于多项式 \(X-1\) 是|g2| 中 \(2\) 对应的点,同时也是其他目标点中对应的零。

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

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

\(L:=\sum_{i=1}^5 c_i\cdot L_i, R:=\sum_{i=1}^5 c_i\cdot R_i, O:=\sum_{i=1}^5 c_i\cdot O_i\),

之后,我们再定义多项式 \(P:=L\cdot R -O\)

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

让我们使用例子来验证一下。假设我们定义 \(L,R,O,P\) 是上述给出的 \(c_1,\ldots,c_5\)。让我们在目标点 \(1\) 评价以上这些多项式:

在所有的 \(L_i\) 中,只有 \(L_1\)\(1\) 点的取值非零。 隐私我们得到 \(L(1)=c_1\cdot L_1(1)=c_1\)。 相似的,我们得到 \(R(1)=c_2\)\(O(1)=c_4\)

因此, \(P(1)=c_1\cdot c_2-c_4\)。 一个相似的计算显示为 \(P(2)= c_4\cdot (c_1+c_3) - c_5\)

也就是说,当且仅当 \((c_1,\ldots,c_5)\) 被合规赋值后,\(P\) 在目标点位的值为零。

现在,我们使用下面的代数事实:对于一个多项式 \(P\) 和一个点 \(a\in\mathbb{F}_p\),当且晋档多项式 \(X-a\) 可以整除 \(P\) 时,我们有 \(P(a)=0\) ,比如 \(P=(X-a)\cdot H\) 对于一些多项式 \(H\)

定义 目标多项式 \(T(X):=(X-1)\cdot (X-2)\),当且仅当 \((c_1,\ldots,c_5)\) 是一个合规的赋值时,我们有 \(T\) 整除 \(P\)

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

一个二次算数程序 \(Q\),有 阶数 |d| *和尺寸 \(m\)它由多项式 \(L_1,\ldots,L_m\), \(R_1,\ldots,R_m\), \(O_1,\ldots,O_m\) 组成,并且有一个 *目标多项式 \(T\) 阶数\(d\)

一个赋值操作 \((c_1,\ldots,c_m)\) 满足 \(Q\) * 如果,定义* \(L:=\sum_{i=1}^m c_i\cdot L_i, R:=\sum_{i=1}^m c_i\cdot R_i, O:=\sum_{i=1}^m c_i\cdot O_i\) * 并且 * \(P:=L\cdot R -O\), * 我们得到* \(T\) 可以整除 \(P\)

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

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

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

cryptography, zkSNARKs, explainers | 查看所有标签