[镜像] 二次算术程序：从零到英雄

这是对帖子https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649的镜像

最近对zk-SNARKs背后的技术产生了很多兴趣，人们越来越多地试图解密一些被许多人称之为“月球数学”的内容，因为它被认为有着无法解读的复杂性。zk-SNARKs确实相当具有挑战性，特别是由于许多移动部分需要结合在一起才能使整个技术正常运作，但如果我们将技术逐步拆解，那么理解它就变得简单了。

这篇帖子的目的是不是提供对zk-SNARKs的全面介绍；它假设你已经了解（i）zk-SNARKs是什么以及它们的作用，以及（ii）了解到足够的数学以便可以推理诸如多项式之类的内容（如果P(x)+Q(x)=(P+Q)(x)这个表达对你来说很自然且显而易见，那么你就掌握了正确的水平）。相反，这篇帖子将深入研究该技术背后的机制，并尽可能清楚地解释zk-SNARK研究者Eran Tromer在这里描绘的流程的前半部分：

这里的步骤可以分为两部分。首先，zk-SNARKs不能直接应用于任何计算问题；相反，你需要将问题转换为正确的“形式”才能进行操作。这个形式被称为“二次算术程序”（QAP），将函数的代码转换为其中之一本身就是一个相当不平凡的过程。将函数代码转换为QAP的过程还有另一个过程可以并行进行，因此如果你有输入代码，你可以创建相应的解决方案（有时称为QAP的“见证”）。在此之后，还有一个相当复杂的过程用于创建这个见证的实际“零知识证明”，以及一个单独的过程用于验证其他人传递给你的证明，但这些细节超出了本文的范围。

我们选择的例子是一个简单的例子：证明你知道一个三次方程的解：x3+x+5=35（提示：答案是3）。这个问题简单到结果QAP不会大到令人恐惧，但又足够不平凡，以便你可以看到所有机械部分的运作。

让我们将函数写成如下：

def qeval(x):
    y = x**3
    return x + y + 5

我们在这里使用的简单专用编程语言支持基本算术运算（+，−，⋅，/）、常数幂指数运算（x7而不是xy）以及变量赋值，这足够强大，从理论上讲，你可以在其中执行任何计算（只要计算步骤的数量是有限的；不允许循环）。请注意，模运算（%）和比较运算符（<, >, ≤, ≥）不被支持，因为在有限循环群运算中没有有效的方法直接执行模运算或比较（对这一点表示感激；如果有办法做到其中任何一个，那么椭圆曲线密码学将比你能说“二分查找”和“中国余数定理”还要快速被攻破）。

你可以通过提供比特分解（例如13=23+22+1）作为辅助输入，将语言扩展到模运算和比较，证明这些分解的正确性并在二进制电路中进行数学运算；在有限域运算中，做相等（==）检查也是可行的，实际上还要简单一些，但这些都是我们此时不打算深入探讨的细节。我们可以通过将条件语句转换为算术形式来扩展语言以支持条件（例如，如果x<5:y=7；否则：y=9）：y=7⋅(x<5)+9⋅(x≥5)，但请注意，条件的两个“路径”都需要执行，如果你有许多嵌套条件，那么这可能会导致大量开销。

现在让我们逐步进行这个过程。如果你想为任何代码片段执行此操作，我实现了一个编译器（仅供教育用途；现在还不适合为真实世界的zk-SNARKs生成QAP！）。

展平

第一步是“展平”过程，我们将原始代码转换为复杂的语句和表达式，这些语句形成两种形态：x=y（其中y可以是变量或数字）和x=y (op) z（其中op可以是+，−，⋅或/，并且y和z可以是变量、数字或它们本身的子表达式）。你可以将每个语句视为电路中的逻辑门。上面代码的展平过程的结果如下：

sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5

如果你阅读原始代码和这里的代码，你可以相对容易地看到两者是等价的。

门到R1CS

现在，我们将其转换为称为秩-1约束系统（R1CS）的东西。R1CS是三个向量（a，b，c）组的序列，R1CS的解是向量s，s必须满足方程s.a⋅s.b−s.c=0，其中.表示点积——简单来说，如果我们“将a和s捆绑在一起”，将两个值相同位置的值相乘，然后对这些乘积求和，再对b和s的乘积做同样的操作，然后对c和s，第三个结果等于前两个结果的乘积。例如，这是一个满足条件的R1CS：

但除了拥有一个约束之外，我们将拥有许多约束：对每个逻辑门都有一个。有一种标准的方法根据操作是（+，−，⋅或/）以及参数是变量还是数字来将逻辑门转换为（a，b，c）三元组。每个向量的长度等于系统中变量的总数，包括在第一个索引处表示数字1的虚拟变量~one，输入变量，表示输出的虚拟变量~out，以及所有中间变量（如上面所示的sym1和sym2）；这些向量通常将非常稀疏，仅填入与特定逻辑门受影响的变量对应的槽。

首先，我们将提供我们要使用的变量映射：

'~one', 'x', '~out', 'sym_1', 'y', 'sym_2'

解向量将由所有这些变量的赋值组成，按此顺序排列。

现在，我们将给出第一个门的（a，b，c）三元组：

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]

与第一个点积检查类似，此处我们检查sym1⋅x=y。

现在，第三个门：

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=sym2+5。通过取解向量中的第六个元素，增加第一个元素的五倍（提醒：第一个元素是1，所以这实际上意味着加5），并将其与第三个元素进行比较，存储输出变量。

我们得到的R1CS具有四个约束。见证仅仅是对所有变量的赋值，包括输入、输出和内部变量：

[1, 3, 35, 9, 27, 30]

你可以通过简单地“执行”上面的展平代码，从输入变量赋值x=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坐标_上评估多项式将表示一个约束。也就是说，如果我们在x=1处评估多项式，我们就得到了第一组向量，如果我们在x=2处评估多项式，就得到了第二组向量，依此类推。

我们可以使用称为拉格朗日插值的东西进行此转换。拉格朗日插值所解决的问题是：如果你有一组点（即（x，y）坐标对），则对这些点进行拉格朗日插值会给你一个穿过所有这些点的多项式。我们通过分解问题来实现这个：对于每个x坐标，我们创建一个在该x坐标上具有所需y坐标而在我们关心的所有其他x坐标上具有y坐标为0的多项式，然后为了得到最终结果，我们将所有多项式加在一起。

让我们举个例子。假设我们想要通过(1,3)，(2,2)和(3,4)的多项式。我们首先制作一个通过(1,3)，(2,0)和(3,0)的多项式。事实证明，制作一个“突出来”的多项式在x=1处而在其他感兴趣点处为零是很简单的；我们只需执行操作：

(x - 2) * (x - 3)

结果如下：

现在，我们只需要“缩放”它，使得在x=1处的高度正确：

(x - 2) * (x - 3) * 3 / ((1 - 2) * (1 - 3))

这给我们：

1.5 * x**2 - 7.5 * x + 9

然后我们对其他两个点做同样的事情，得到另外两个看起来类似的多项式，只是它们在x=2和x=3处“突出来”，而不是x=1。我们把三个多项式加在一起，得到：

1.5 * x**2 - 5.5 * x + 7

而且得到了恰好是我们所需的坐标。上述算法的时间复杂度为O(n^3)，因为有n个点，每个点的多项式相乘需要O(n^2)的时间；经过一番思考，这可以降低到O(n^2)的时间，而经过更多思考，则使用快速傅里叶变换算法等，可以进一步降低——这是一个关键的优化，因为在实践中，被用于zk-SNARKs的函数通常会有成千上万个逻辑门。

现在，让我们使用拉格朗日插值来变换我们的R1CS。我们将做的是从每个a向量取出第一个值，使用拉格朗日插值对其生成多项式（在i处评估多项式得到了第i个a向量的第一个值），对每个b和c向量的第一个值重复该过程，然后对第二个值、第三个值，依此类推，重复该过程。为了方便，我现在会提供答案：

A 多项式
[-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 多项式
[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 多项式
[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⋅x^3−5⋅x^2+9.166⋅x−5。这组多项式（加上一个后面我会解释的Z多项式）构成了这个特定QAP实例的参数。请注意，到目前为止所做的所有工作对于你要使用zk-SNARKs验证的每个函数来说只需要执行一次；一旦生成了QAP参数，它们可以重用。

让我们试着在x=1处计算所有这些多项式。计算多项式在x=1处的值仅仅意味着加总所有系数（因为1^k=1，对所有k成立），所以并不难。我们得到：

A 结果在x=1
0
1
0
0
0
0

B 结果在x=1
0
1
0
0
0
0

C 结果在x=1
0
0
0
1
0
0

看看，我们在这里得到的正好是我们上面创建的第一个逻辑门的三组向量。

检查QAP

那么，这种疯狂的转换有什么意义呢？答案是，我们现在可以通过对多项式进行点积检查来同时检查所有约束，而不是逐个检查R1CS中的约束。

因为在这种情况下，点积检查是一系列多项式的加法和乘法，结果本身也是多项式。如果结果多项式在我们上面用于表示逻辑门的每个x坐标上的评估结果等于零，那么这意味着所有检查都通过；如果结果多项式在至少一个逻辑门的x坐标上给出非零值，则意味着进入和输出该逻辑门的值不一致（即门是y=x⋅sym1，但是提供的值可能是x=2，sym1=2和y=5）。

请注意，结果多项式本身并不一定要为零，事实上在大多数情况下也不会；它可能在不对应于任何逻辑门的点上表现出任何行为，只要它在所有对应于某个逻辑门的点上满足为零即可。为了检查正确性，我们实际上并不在每个对应于门的点上评估多项式t=A.s⋅B.s−C.s；相反，我们除以另一个多项式Z，并检查Z是否均匀除尽t——即，除法t/Z不会留下余数。

Z定义为(x−1)⋅(x−2)⋅(x−3)...——这个最简单的多项式在所有对应于逻辑门的点上等于零。一个代数基本事实是，任何在所有这些点上等于零的多项式都必须是这个最小多项式的倍数。如果一个多项式是Z的倍数，那么它在任何对应于逻辑门的点上的值将会为零；这种等价使我们的工作变得更加简单。

现在，让我们实际进行上述多项式的点积检查。首先，中间多项式：

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]

现在，A.s⋅B.s—C.s：

t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]

现在，最小多项式Z=(x−1)⋅(x−2)⋅(x−3)⋅(x−4)：

Z = [24, -50, 35, -10, 1]

如果我们将上面的结果除以Z，我们得到：

h = t / Z = [-3.666, 17.055, -3.444]

没有余数。

所以我们得到了QAP的解。如果我们试图假造我们从中推导出这个QAP解的R1CS解决中的任何变量——例如，将最后一个值设置为31而不是30，然后我们得到一个t多项式，失败了其中一个检查（在那种情况下，x=3处的结果将等于−1而不是0），而且t也不会是Z的倍数；相反，除以t/Z会有余数为[−5.0,8.833,−4.5,0.666]。

请注意，上述内容是一个简化；在“现实世界”中，加法、乘法、减法和除法将与常规数字进行，而是与有限域元素进行——这是一种自洽的奇异运算，使我们知道和喜爱的所有代数法则仍然适用，但所有答案都是某个有限集合的元素，通常是范围从0到n−1（对于某个n）的整数。例如，如果n=13，则1/2=7（且7⋅2=1），3⋅5=2，诸如此类。使用有限域运算可以消除需要担心舍入错误，并使该系统能够与椭圆曲线很好地协同工作，而椭圆曲线在zk-SNARK的机制中对于使zk-SNARK协议安全是必不可少的。

特别感谢Eran Tromer帮助我解释了zk-SNARK的内部工作细节。

• 原文链接： vitalik.eth.limo/general...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～