二次算術程序：關於零知識證明的論述

作者：Vitalik Buterin

原标题：《Quadratic Arithmetic Programs: from Zero to Hero》

發表時間：2016 年 12 月 10 日

最近人們對zk-SNARKs（零知識證明）背後的技術有很多興趣，人們越來越多地試圖去揭開一些被許多人稱為"月球數學"的東西的神秘面紗，因為人們認為它的複雜性非常難以理解。zk-SNARKs的理解確實相當具有挑戰性，尤其是由於整個系統需要組裝起來才能工作的移動部件太多，但如果我們把這項技術一件一件地分解，那麼理解起來就會變得更簡單。

這篇文章的目的不是用於完整的介紹zk-SNARKs，它假定您具有以下背景知識：

1- 你知道zk-SNARKs和它的大致原理；

2- 你有足夠的數學知識，能理解一些基本的多項式知識。(如 if P(x)+ Q(x)=(P + Q)(x)，P和Q代表多項式，如果你對這類多項式表述方式已經非常熟悉，說明你符合繼續閱讀的要求)。

zk-SNARK知識管道圖，Eran Tromer繪製

如上圖，可以將以上零知識證明分為由上至下的兩個階段。首先，zk-SNARK不能直接應用於任何計算問題；相反，您必須將問題轉換為操作的正確"形式"。這種形式被稱為"二次算術程序"(QAP)，將函數的代碼轉換成這些代碼本身就非常重要。與將函數代碼轉換為QAP的過程一起運行的還有另一個過程，這樣，如果對代碼有輸入，就可以創建相應的解決方案（有時稱為QAP的"見證"）。這就是本文需要講述的內容。

在此之後，還有另一個相當複雜的過程來為這個QAP創建實際的"零知識證明"，還有一個單獨的過程來驗證別人傳給你的證據，但是這些細節超出了本文的範圍。

在下面示例中，我們將選擇一個非常簡單的問題：

求一個三次方程的解:x**3 + x + 5 == 35(提示:答案是3)。

這個問題很簡單，但是重要的，你可以由此案例看到所有的功能是如何發揮作用的。

用編程語言描述以上方程如下：

def qeval(x):
y = x**3
return x + y + 5
我們在這裡使用的簡單編程語言支持基本的算術(+、-、、/)、恒等幂指數(x7，但不是x*y)和變量賦值，這足夠強大到理論上可以在其中進行任何計算（只要計算步驟的數量是有界的;不允許循環）。注意模(%)和比較運算符(\<、>、≤≥)不支持，因為沒有有效的方法做模或直接比較有限循環群算法（感謝;如果有任何一種方法可以做到這一點，那麼椭圓曲線密碼破環的速度將超過"二分查找"和"中國剩餘定理"）。

您可以通過位分解來將語言擴展到模和比較，（例如：13 = 2**3 + 2**2 + 1=8+4+1)作為輔助輸入，證明這些分解的正確性，並在二進制電路中進行數學運算；在有限域算法中，執行等式(==)檢查也是可行的，實際上更容易一些，但這兩個細節我們現在都不討論。我們可以擴展語言來支持條件句（例如將語句：if x \< 5: y = 7; else: y = 9; 轉換為算術形式：y = 7 * (x \< 5) + 9 * (x >= 5);）不過請注意，條件的兩個"路徑"都需要執行，如果您有許多嵌套的條件，那麼這會導致大量開銷。

現在讓我們一步一步地經歷這個過程。如果你想自己做任何代碼，我在這裡用Python實現了一段代碼（僅用於教育目的；還沒有準備好為現實世界的zk-SNARK製作QAPs !）

第一步：壓扁

第一步是一個"壓扁"的過程，我們把原來的代碼（這可能包含任意複雜的語句和表達式）分解為最簡單的表達式，這種表達式有兩種形式:

1- x = y （y可以是變量或數字)
2- x = y(op)z (op可以+,-,*,/，y和z可以是變量，數字或子表達式)。

你可以把這些表述看成是電路中的邏輯門。上述表達式x**3 + x + 5的扁平化過程結果如下:

sym1 = x * x y = sym1 * x //相當於實現了幂函數y = x**3
sym2 = y + x ~out = sym2 + 5

你可以認為上述的每一行聲明都是一個電路中的邏輯門，與原始代碼相比，這裡我們引入了兩個中間變量sym1 和 sym2，還有一個表示輸出的冗餘變量 ~out，不難看出"壓扁"後的聲明序列和原始代碼是等價的。

第二步：轉為R1CS

現在，我們把它轉換成一個稱為R1CS（Rand-1 Constraint System）的東西。R1CS是由三個向量(a, b, c)組成的序列，R1CS的解是一個向量s，其中s必須滿足方程

s . a * s . b - s . c = 0

其中 . 代表內積運算。

例如，以下是一個令人滿意的R1CS：

a = (5,0,0,0,0,1)，
b = (1,0,0,0,0,0)，
c = (0,0,1,0,0,0)，
s = (1,3,35,9,27,30)，

（譯者注：第一個35=1*5 + 30*1，第二個35=35 * 1）

上述例子只是一个约束，接下来我们要将每个逻辑门（即"压扁"后的每一个声明语句）转化成一个约束（即一个(a, b, c)三向量组），转化的方法取决于声明是什么运算 (+,-,*,/) 和声明的参数是变量还是数字。在我们这个例子中，除了"压扁"后的五个变量 ('x', '~out', 'sym1', 'y', 'sym2') 外，还需要在第一个分量位置处引入一个冗余变量~one来表示数字1，就我们这个系统而言，一个向量所对应的 6 个分量是(可以是其他顺序，只要对应起来即可)：

'~one', 'x', '~out', 'sym1', 'y', 'sym2'

第一个门

sym1 = x * x，即 x*x - sym1 = 0

我们可以得到如下向量组：

a = [0, 1, 0, 0, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 1, 0, 0]

如果解向量 s 的第二个标量是 3，第四个标量是 9，无论其他标量是多少，都成立，因为：a = 3 * 1, b = 3 * 1, c = 9 * 1，即a * b = c。同样，如果 s 的第二个标量是 7，第四个标量是 49，也会通过检查，第一次检查仅仅是为了验证第一个门的输入和输出的一致性。

第二个门

y = sym1 * x，即 sym1 * x - y = 0
可以得到以下向量组：

a = [0, 0, 0, 1, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 0, 1, 0]

第三个门

sym2 = y + x，加法门需要转换为：(x + y) * 1 - sym2 = 0
得到以下向量组：

a = [0, 1, 0, 0, 1, 0]
b = [1, 0, 0, 0, 0, 0] 对应常量1，用~one位
c = [0, 0, 0, 0, 0, 1]

第四个门

~out = sym2 + 5，即 (sym2 + 5) * 1 - ~out = 0
得到以下向量组：

a = [5, 0, 0, 0, 0, 1]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 1, 0, 0, 0]

现在，我们假设x = 3，根据第一个门，得到sym1 = 9，根据第二个门得到y = 27，根据第三个门，得到sym2 = 30，根据第四个门得到~out = 35，因此，根据：'~one', 'x', '~out', 'sym1', 'y', 'sym2'，可以得到：

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

如果假设不同的x，都可以得到不同的s，但所有s都可以用来验证(a, b, c)

现在我们得到了四个约束的R1CS，完整的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形式，它实现了完全相同的逻辑，只是使用多项式而不是内积。我们是这样做的：从4组长度为6的3个向量到6组长度为3度的多项式，在每个x坐标处求多项式代表一个约束条件。也就是说，如果我们求出x=1处的多项式，我们就得到了第一组向量，如果我们求出x=2处的多项式，我们就得到第二组向量，以此类推。

我们可以用拉格朗日插值来做这个变换。拉格朗日插值法解决的问题是：如果你有一组点(即(x, y)坐标对），然后对这些点做拉格朗日插值得到一个经过所有这些点的多项式。我们通过分解问题：对于每个x坐标,我们创建一个多项式,所需的y坐标的x坐标和y坐标0在所有其他的x坐標我們感興趣，然後讓最終結果我們一起添加所有的多項式。

讓我們做一個例子。假設我們想要一個多項式經過(1,3),(2,2)和(3,4)。我們首先做一個多項式，經過(1,3)(2,0)和(3,0)。事實證明,一個多項式,"伸出"x = 1和0的其他的興趣點是很容易的，我們只要做以下多項式即可：

y = (x - 2) * (x - 3)

如下圖：

然後，在y軸方向"拉伸"，使用如下方程：

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

經整理，得到：

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

滿足同時經過(1,3)(2,0)和(3,0)三個點，如下圖：

將(2,2)和(3,4)兩點代入上式，可以得到：

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

就是我們想要的坐標方程。上述算法需要O(n3)時間，因為有n個點，每個點都需要O(n2)時間將多項式相乘。稍微思考一下，這就可以減少到O(n**2)的時間，再多思考一下，使用快速的傅里葉變換算法等等，它可以進一步減少------這是一個關鍵的優化，當在zk- spuks中使用的函數通常有成千上萬的門時。

在這裡我直接給出拉格朗日插值公式：

通過n個點(x1,y1),(x2,y2),(x3,y3),…,(xn,yn) 的n-1階多項式為：

例如上例中，通過點(1,3), (2,2), (3,4)的多項式為：

學會使用這個公式後可以繼續我們的步驟了。現在我們要將四個長度為六的三向量組轉化為六組多項式，每組多項式包括三個三階多項式，我們在每個 x 點處來評估不同的約束，在這裡，我們共有四個約束，因此我們分別用多項式在 x = 1,2,3,4 處來評估這四個向量組。

現在我們使用拉格朗日差值公式來將 R1CS 轉化為 QAP 形式。我們先求出四個約束所對應的每個 a 向量的第一個值的多項式，也就是說使用拉格朗日插值定理求過點 (1,0), (2,0), (3,0), (4,0) 的多項式，類似的我們可以求出其餘的四個約束所對應的每個向量的第i個值的多項式。

這裡，直接給出答案：

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 * x**3 - 5 * x**2 + 9.166 * x - 5. 如果我們將 x=1 帶入上述十八個多項式，可以得到第一個約束的三個向量

(0, 1, 0, 0, 0, 0),
(0, 1, 0, 0, 0, 0),
(0, 0, 0, 1, 0, 0),
…
類似的我們將 x = 2, 3, 4 帶入上述多項式可以恢復出 R1CS 的剩餘部分。

第四步：檢查QAP

通過將 R1CS 轉換成 QAP 我們可以通過多項式的內積運算來同時檢查所有的約束而不是像R1CS 那樣單獨的檢查每一個約束。如下圖所示：

因為在這種情況下，點積檢驗是一系列多項式的加法和乘法，結果本身就是一個多項式。如果得到的多項式，在我們上面用來表示邏輯門的每一個x坐標處的值，等於0，那就意味著所有的檢查都通過了；如果結果多項式至少有一個非零值，那麼這就意味著進出邏輯門的值是不一致的。

值得注意的是，得到的多項式本身不一定是零，事實上在大多數情況下不是;它可以在不符合任何邏輯門的點上有任何行為，只要在所有符合某些門的點上結果是零。為了驗證正確性，我們不計算多項式t = A . s * B . s - C . s在每一點對應一個門；相反，我們把t除以另一個多項式Z，然後檢查Z是否均勻地除t，也就是說，除法t / Z沒有餘數。

Z定義為(x - 1) * (x - 2) * (x - 3)…-最簡單的多項式，在所有對應邏輯門的點上都等於0。這是代數的一個基本事實任何多項式在所有這些點上等於零都必須是這個最小多項式的倍數，如果一個多項式是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]
（譯者注：以上計算過程：
43.0 = -5 * 1 + 8 * 3 + 0 * 35 - 6 * 9 + 4 * 27 - 1 * 30，
-73.333 = 9.166 * 1 - 11.333 * 3 + 0 * 35 + 9.5 * 9 - 7 * 27 + 1.833 * 30,
…
-3 = 3 * 1 - 2 * 3 + 0 * 35 + 0 * 9 + 0 * 27 + 0 * 30
…)

以上多項式經過：A . s * B . s - C . s 計算後得到：

t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]
（譯者注：計算過程：
A . s = [43.0, -73.333, 38.5, -5.166] = -5.166 * x3 + 38.5 * x2 - 73.333 * x + 43,
B . s = [-3.0, 10.333, -5.0, 0.666] = 0.666 * x3 - 5 * x2 + 10.333 * x - 3.0,
C . s = [-41.0, 71.666, -24.5, 2.833] = 2.833 * x3 - 24.5 * x2 + 71.666 * x - 41.0
A . s * B . s - C . s 就是上面多項式的計算，計算後，按幂從低到高排列系數，得到： [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]

點擊這裡查看計算過程-%5Cleft(2.833x%5E%7B3%7D-24.5x%5E%7B2%7D%2B71.666x-41%5Cright))

最小多項式為：

Z = (x - 1) * (x - 2) * (x - 3) * (x - 4)

即：

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

以上計算過程點擊這裡查看%20%5Ccdot%20%5Cleft(x%20-%203%5Cright)%20%5Ccdot%20%5Cleft(x%20-%204%5Cright))

現在計算多項式相除：

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

h必須是沒有任何餘數的整除。

可以點這裡查看到過來驗證%20%5Ccdot%5Cleft(x%20-%203%5Cright)%20%5Ccdot%5Cleft(x%20-%204%5Cright)%5Ccdot%5Cleft(-3.444x%5E%7B2%7D%2B17.055x-3.666%5Cright))。

我們有了QAP的解。如果我們試圖偽造R1CS中的變量，而這個R1CS推導出了QAP解決方案------比如,將s的最後一個數字設為31，而不是30，我們將得到一個t多項式失敗的檢查(在特定情況下,在x = 3 = 1而不是0),而且不會是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协议变得真正安全。