维塔利克·布特林 (Vitalik Buterin) Vitalik Buterin 博客
这是帖子的镜像 https://medium.com/@VitalikButerin/二次算术程序-从零到英雄-f6d558cea649
最近人们对 zk-SNARK 背后的技术产生了很大的兴趣，并且人们越来越多地关注 zk-SNARKs 背后的技术。 试图揭开神秘面纱 由于其难以理解的复杂性，许多人将其称为“月球数学”。 zk-SNARK 确实很难掌握，特别是因为需要将大量的移动部件组合在一起才能使整个系统发挥作用，但如果我们将技术逐个分解，那么理解它就会变得更简单。
这篇文章的目的不是作为 zk-SNARK 的完整介绍；它假设作为背景知识：(i) 你知道 zk-SNARK 是什么以及它们的作用，并且 (ii) 了解足够的数学知识，能够推理多项式等事物（如果语句 �(�)+�(�) =(�+�)(�) ，其中 � 和 � 是多项式，对您来说似乎很自然且显而易见，那么您就处于正确的水平）。相反，这篇文章更深入地挖掘了技术背后的机制，并试图尽可能地解释管道的前半部分，正如 zk-SNARK 研究员 Eran Tromer 在此处绘制的：
这里的步骤可以分为两半。首先，zk-SNARKs不能直接应用于任何计算问题；相反，你必须将问题转换成正确的“形式”以供问题处理。这种形式被称为“二次算术程序”（QAP），将函数代码转换为其中之一本身就非常重要。除了将函数代码转换为 QAP 的过程之外，还有另一个可以同时运行的过程，因此，如果您有代码输入，则可以创建相应的解决方案（有时称为 QAP 的“见证”）。之后，还有另一个相当复杂的过程，用于为该证人创建实际的“零知识证明”，以及一个单独的过程，用于验证其他人传递给您的证明，但这些细节超出了本文的范围。
我们选择的例子很简单：证明您知道三次方程的解：�3+�+5=35（提示：答案是 3）。这个问题足够简单，以至于产生的 QAP 不会大到令人生畏，但也足够重要，你可以看到所有机制都在发挥作用。
让我们写出我们的函数如下：
def qeval(x):
y = x**3
return x + y + 5我们在这里使用的简单专用编程语言支持基本算术（+、−、⋅、/）、恒幂指数（�7 但不是 ��）和变量赋值，它足够强大，理论上您可以做到其内部的任何计算（只要计算步骤的数量是有限的；不允许循环）。请注意，不支持取模 (%) 和比较运算符 (<、>、≤、≥)，因为没有有效的方法可以直接在有限循环群算术中进行取模或比较（对此表示感谢；如果有一种方法做任何一个，那么椭圆曲线密码学将比你说的“二分搜索”和“中国余数定理”更快地被破解）。
您可以通过提供位分解（例如 13=23+22+1）作为辅助输入，将语言扩展到模和比较，证明这些分解的正确性并在二进制电路中进行数学运算；在有限域算术中，进行相等（==）检查也是可行的，而且实际上更容易一些，但这些都是我们现在不会讨论的细节。我们可以通过将条件转换为算术形式来扩展语言以支持条件（例如 if �<5:�=7; else: �=9）：�=7⋅(�<5)+9⋅(�≥5) ）但请注意，条件的两个“路径”都需要执行，如果您有许多嵌套条件，那么这可能会导致大量开销。
现在让我们一步一步地完成这个过程。如果您想自己对任何代码片段执行此操作，我 在这里实现了一个编译器 （仅用于教育目的；尚未准备好为现实世界的 zk-SNARK 制作 QAP！）。
展平
第一步是“扁平化”过程，我们将可能包含任意复杂语句和表达式的原始代码转换为具有两种形式的语句序列：�=�（其中�可以是变量或数字) 和 �=� (��) �� （其中 �� 可以是 +、−、⋅、/，并且 � 和 �� 可以是变量、数字或其本身的子表达式）。您可以将这些语句中的每一个视为电路中的逻辑门。对上述代码进行扁平化处理的结果如下：
sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5如果您阅读原始代码和此处的代码，您可以很容易地看出两者是等效的。
通往 R1CS 的大门
现在，我们将其转换为称为 1 级约束系统 (R1CS) 的系统。 R1CS 是由三个向量 (�,�,�) 组成的组的序列，R1CS 的解是向量�，其中�必须满足方程�.�⋅�.�−�.�=0，其中。表示点积 - 简单来说，如果我们将 � 和 � “压缩在一起”，将两个值在相同位置相乘，然后取这些乘积的总和，然后对 � 和 � 执行相同操作，然后对 � 和 � 执行相同操作，那么第三个结果等于前两个结果的乘积。例如，这是一个满意的R1CS：
但我们将面临许多约束，而不是只有一个约束：每个逻辑门都有一个约束。有一种标准方法可以将逻辑门转换为 (�,�,�) 三元组，具体取决于操作是什么（+、−、⋅ 或 /）以及参数是变量还是数字。每个向量的长度等于系统中变量的总数，包括第一个索引处代表数字1的虚拟变量~one、输入变量、代表输出的虚拟变量~out，然后是所有的向量。中间变量（上面的���1和����2）；向量通常会非常稀疏，仅填充与受某些特定逻辑门影响的变量相对应的槽。
首先，我们将提供我们将使用的变量映射：
'~one', 'x', '~out', 'sym_1', 'y', 'sym_2'解向量将按顺序包含所有这些变量的分配。
现在，我们将为第一个门给出 (�,�,�) 三元组：
a = [0, 1, 0, 0, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 1, 0, 0]您可以看到，如果解向量在第二个位置包含 3，在第四个位置包含 9，那么无论解向量的其余内容如何，点积检查都将归结为 3⋅3=9，并且所以它会过去的。如果解向量第二个位置为-3，第四个位置为9，则检查也将通过；事实上，如果解向量在第二个位置有 7，在第四个位置有 49，那么该检查仍然会通过——第一次检查的目的只是验证第一个门的输入和输出的一致性。
现在，让我们进入第二个门：
a = [0, 0, 0, 1, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 0, 1, 0]与第一个点积检查类似，我们在这里检查 ��1⋅�=�。
现在，第三个门：
a = [0, 1, 0, 0, 1, 0]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 0, 0, 0, 1]这里的模式有些不同：它将解向量中的第一个元素乘以第二个元素，然后乘以第五个元素，将两个结果相加，并检查总和是否等于第六个元素。由于解向量中的第一个元素始终为 1，因此这只是一个加法检查，检查输出是否等于两个输入的总和。
最后是第四道门：
a = [5, 0, 0, 0, 0, 1]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 1, 0, 0, 0]在这里，我们正在评估最后一次检查，~out =���2+5。点积检查的工作原理是取解向量中的第六个元素，添加第一个元素的五倍（提醒：第一个元素是 1，因此这实际上意味着添加 5），然后对照第三个元素进行检查，这就是我们的位置存储输出变量。
我们的 R1CS 有四个约束。见证人只是对所有变量的赋值，包括输入、输出和内部变量：
[1, 3, 35, 9, 27, 30]您可以通过简单地“执行”上面的扁平化代码来自行计算，从输入变量赋值 �=3 开始，然后在计算时输入所有中间变量的值和输出。
完整的 R1CS 放在一起是：
A
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 1, 0]
[5, 0, 0, 0, 0, 1]
B
[0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
C
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0]R1CS 至 QAP
下一步是将这个 R1CS 转换为 QAP 形式，除了使用多项式而不是点积之外，它实现完全相同的逻辑。我们按如下方式进行操作。我们从四组三个长度为六的向量到六组三个三阶多项式，其中评估每个多项式 x坐标 代表约束之一。也就是说，如果我们在 �=1 处计算多项式，则我们得到第一组向量，如果我们在 �=2 处计算多项式，则得到第二组向量，依此类推。
我们可以使用称为 拉格朗日插值。拉格朗日插值解决的问题是：如果您有一组点（即 (�,�) 坐标对），那么对这些点进行拉格朗日插值会得到一个通过所有这些点的多项式。我们通过分解问题来做到这一点：对于每个 � 坐标，我们创建一个多项式，该多项式在该 � 坐标处具有所需的 � 坐标，并且在我们感兴趣的所有其他 � 坐标处具有 0 的 � 坐标，然后得到最终的结果我们将所有多项式加在一起。
我们来举个例子。假设我们想要一个通过 (1,3)、(2,2) 和 (3,4) 的多项式。我们首先创建一个通过 (1,3)、(2,0) 和 (3,0) 的多项式。事实证明，创建一个在 �=1 处“突出”且在其他感兴趣点处为零的多项式很容易；我们简单地做：
(x - 2) * (x - 3)看起来像这样：
现在，我们只需要“重新缩放”它，使 x=1 处的高度正确：
(x - 2) * (x - 3) * 3 / ((1 - 2) * (1 - 3))这给了我们：
1.5 * x**2 - 7.5 * x + 9
然后，我们对其他两个点执行相同的操作，得到另外两个看起来相似的多项式，只不过它们在 �=2 和 �=3 处“突出”，而不是 �=1。我们将这三者加在一起，得到：
1.5 * x**2 - 5.5 * x + 7
正是我们想要的坐标。上述算法需要 �(�3) 时间，因为有 � 个点，每个点需要 �(�2) 时间将多项式相乘；稍微思考一下，这可以减少到 �(�2) 时间，并且通过更多的思考，使用快速傅立叶变换算法等，可以进一步减少 - 当在 zk 中使用函数时，这是一个至关重要的优化-实践中的 SNARK 通常有数千个门。
现在，让我们使用拉格朗日插值来变换我们的 R1CS。我们要做的是从每个 � 向量中取出第一个值，使用拉格朗日插值法从中得出多项式（其中计算 � 处的多项式可以获得第 � 向量的第一个值），重复该过程对于每个 � 和 �� 向量的第一个值，然后对第二个值、第三个值等重复该过程。为了方便起见，我现在就提供答案：
A polynomials
[-5.0, 9.166, -5.0, 0.833]
[8.0, -11.333, 5.0, -0.666]
[0.0, 0.0, 0.0, 0.0]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]
[-1.0, 1.833, -1.0, 0.166]
B polynomials
[3.0, -5.166, 2.5, -0.333]
[-2.0, 5.166, -2.5, 0.333]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
C polynomials
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[-1.0, 1.833, -1.0, 0.166]
[4.0, -4.333, 1.5, -0.166]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]系数按升序排列，因此上面的第一个多项式实际上是 0.833⋅�3—5⋅�2+9.166⋅�−5。这组多项式（加上我稍后将解释的 Z 多项式）构成了这个特定 QAP 实例的参数。请注意，对于您尝试使用 zk-SNARK 验证的每个函数，到目前为止的所有工作只需完成一次；一旦生成QAP参数，就可以重复使用它们。
让我们尝试在 �=1 处计算所有这些多项式。计算 �=1 处的多项式仅意味着将所有系数相加（对于所有 �，1�=1），因此并不困难。我们得到：
A results at x=1
0
1
0
0
0
0
B results at x=1
0
1
0
0
0
0
C results at x=1
0
0
0
1
0
0你瞧，我们这里所拥有的与我们上面创建的第一个逻辑门的三个向量的集合完全相同。
检查 QAP
现在这个疯狂的转变有什么意义呢？答案是，我们现在可以检查 R1CS 中的约束，而不是单独检查 同时所有的约束 通过进行点积检查 在多项式上.
因为在这种情况下，点积检查是一系列多项式的加法和乘法，因此结果本身就是一个多项式。如果在我们上面用来表示逻辑门的每个 � 坐标处计算得到的多项式等于 1，则意味着所有检查都通过了；如果在代表逻辑门的 � 坐标中的至少一个处计算得到的多项式给出非零值，则意味着进出该逻辑门的值不一致（即，该门是 �=�⋅�� �2，但提供的值可能是 �=1、���2=5 和 �=XNUMX)。
请注意，所得多项式本身不一定为零，事实上在大多数情况下不会为零；它可以在不对应于任何逻辑门的点上有任何行为，只要结果在所有点上为零 do 对应某个门。为了检查正确性，我们实际上并不在与门对应的每个点处计算多项式 �=�.�⋅�.�−�.� ；相反，我们将 � 除以另一个多项式 �，并检查 � 是否整除 � – 也就是说，除 �/� 没有余数。
� 定义为 (�−1)⋅(�−2)⋅(�−3)… – 最简单的多项式，在与逻辑门对应的所有点处都等于 XNUMX。这是代数的一个基本事实 任何 在所有这些点处等于 0 的多项式必须是该最小多项式的倍数，并且如果多项式是 � 的倍数，则其在任何这些点处的评估都将为零；这种等价性使我们的工作变得更加容易。
现在，让我们实际使用上面的多项式进行点积检查。首先，中间多项式：
A . s = [43.0, -73.333, 38.5, -5.166]
B . s = [-3.0, 10.333, -5.0, 0.666]
C . s = [-41.0, 71.666, -24.5, 2.833]现在，………………：
t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]现在，最小多项式 �=(�−1)⋅(�−2)⋅(�−3)⋅(�−4)：
Z = [24, -50, 35, -10, 1]如果我们将上面的结果除以 �，我们得到：
h = t / Z = [-3.666, 17.055, -3.444]无余无余。
这样我们就有了 QAP 的解决方案。如果我们尝试伪造 R1CS 解决方案中的任何变量（例如，将最后一个变量设置为 31 而不是 30），那么我们会得到一个未能通过其中一项检查的多项式（在该特定情况下）在这种情况下，�=3时的结果将等于-1而不是0)，而且�不会是�的倍数；相反，除 �/� 会得到余数 [−5.0,8.833,−4.5,0.666]。
请注意，上面是一个简化； “在现实世界中”，加法、乘法、减法和除法不会发生在常规数字上，而是发生在有限域元素上——一种令人毛骨悚然的自洽算术，所以我们仍然知道和喜爱的所有代数定律成立，但所有答案都是某个有限大小集合的元素，对于某些 � 通常是 0 到 �−1 范围内的整数。例如，如果 �=13，则 1/2=7（且 7⋅2=1）、3⋅5=2，依此类推。使用有限域算术无需担心舍入误差，并允许系统与椭圆曲线完美配合，这对于 zk-SNARK 机制的其余部分是必要的，从而使 zk-SNARK 协议真正安全。
特别感谢 Eran Tromer 帮助我向我解释了有关 zk-SNARK 内部工作原理的许多细节。