本文翻譯自V神的Medium文章：二次計(jì)算方程：從0到1，詳細(xì)講解了QAP，并給出了一個(gè)程序?qū)崿F(xiàn)，本文是上半部分，介紹了把計(jì)算轉(zhuǎn)化為R1CS的過(guò)程。zcash官方博客對(duì)QAP這部分講解的比較粗糙，V神的這篇文章是個(gè)很好的補(bǔ)充。友情提示：本文偏技術(shù)化，適合對(duì)技術(shù)非常感興趣的同學(xué)閱讀。
(本文授權(quán)BH好文好報(bào)群摘編、轉(zhuǎn)載以及相關(guān)轉(zhuǎn)授權(quán)推文行為)
二次計(jì)算方程：從0到1
最近zk-SNARKs吸引了很多人的注意力，因?yàn)樗请y以捉摸的復(fù)雜性，所以有人把它稱之為“月亮數(shù)學(xué)”；人人都想揭開(kāi)它的神秘面紗。zk-SNARKs確實(shí)比較難以掌握，它里面包含了好幾個(gè)比較難以理解的知識(shí)點(diǎn)；如果我們把這些知識(shí)點(diǎn)分開(kāi)來(lái)去掌握，就沒(méi)那么難了。
這篇文章，不會(huì)把zk-SNARKs的內(nèi)部都介紹一邊，而是假設(shè)你已經(jīng)有了如下基礎(chǔ)知識(shí)：
- 你知道zk-SNARKs是什么以及它有什么用
- 你有多項(xiàng)式相關(guān)的數(shù)學(xué)知識(shí)(如果這樣的多項(xiàng)式對(duì)你來(lái)說(shuō)很熟悉： P(x) + Q(x) = (P+X)(x),其中P和Q都是多項(xiàng)式。
那么你就沒(méi)問(wèn)題)。不僅如此，本文還會(huì)對(duì)技術(shù)背后的機(jī)制做深入的研究，并試圖解釋下圖中前半部分的知識(shí)點(diǎn)。
這些步驟可以分成兩部分。第一，zk-SNARKs不是所有的計(jì)算問(wèn)題都可以直接用的；你需要把問(wèn)題轉(zhuǎn)換為正確的“形式”之后，才能進(jìn)行后續(xù)操作。這種形式被稱作“二次計(jì)算方程”(QAP)，把一個(gè)函數(shù)的代碼轉(zhuǎn)化為這種形式本身就不是一件簡(jiǎn)單的事情。在這個(gè)轉(zhuǎn)換過(guò)程之外，還有另外一個(gè)過(guò)程，就是如果你有這段代碼的輸入，就能夠創(chuàng)建相應(yīng)的“解”(有時(shí)候被叫做QAP的"見(jiàn)證者")。然后，為這個(gè)“解”創(chuàng)建真正的"零知識(shí)證明"，以及驗(yàn)證證明的過(guò)程，不過(guò)這些都是本篇內(nèi)容之外的內(nèi)容，這里不做細(xì)述了。
我們選用的是一個(gè)簡(jiǎn)單的例子: 證明你知道下面這個(gè)三次方程的解：
x^3 + x + 5 = 35(提示：答案是3).
這問(wèn)題非常簡(jiǎn)單，這樣生成的QAP不會(huì)太大，所以比較好模擬；但是已經(jīng)足夠我們研究相關(guān)的技術(shù)機(jī)制了。
我們把這個(gè)函數(shù)這樣寫下來(lái)：
def qeval(x)
y = x**3
return x + y + 5
這里用到的這個(gè)特別的編程語(yǔ)言支持基本的算術(shù)運(yùn)算(+,-, *, /)，常數(shù)指數(shù)運(yùn)算(類似于x**7，而不是x**y)，以及變量賦值。這些已經(jīng)足夠強(qiáng)大了，理論上，你可以用他們做任何計(jì)算。注意，求余運(yùn)算(%)和比較運(yùn)算(<, >, <=, >=)是不支持的。這是因?yàn)樵谟邢扪h(huán)群里面，沒(méi)有求余運(yùn)算和比較運(yùn)算的高效方法(幸虧是這樣；不然橢圓曲線加密算法就可以很快被破解了)。
要是想支持求余和比較運(yùn)算，你可以給這個(gè)語(yǔ)言增加位分解功能（比如： 13 = 2 ^3 + 2^2 + 1），它可以作為一種輔助輸入，在二進(jìn)制電路里面進(jìn)行一些數(shù)學(xué)計(jì)算并驗(yàn)證分解的正確性；在有限域運(yùn)算中，檢測(cè)相等(==)也是可行，實(shí)際上還更容易一點(diǎn)，不過(guò)這些都是一些細(xì)節(jié)了，我們這里不再深入了。我們可以給這個(gè)語(yǔ)言增加條件判斷(比如：if x < 5: y= 7; else: y = 9)，可以通過(guò)把它們轉(zhuǎn)化為算術(shù)形式來(lái)實(shí)現(xiàn)：y = 7*(x < 5) + 9 * (x >= 5) , 不過(guò)這種這種形式還是會(huì)有兩個(gè)條件運(yùn)算需要執(zhí)行。如果你有很多的嵌套的條件判斷，那么這個(gè)計(jì)算量的開(kāi)銷也是很大的。
現(xiàn)在讓我們一步步的走一遍這個(gè)過(guò)程。如果你想自己實(shí)現(xiàn)一些代碼，可以參考我實(shí)現(xiàn)的這個(gè)翻譯器(僅供學(xué)習(xí)使用；不能作為真實(shí)場(chǎng)景中的zk-SNARKs使用)
抹平
第一步就是"抹平"操作，我們把原始的包含各種復(fù)雜的語(yǔ)句和表達(dá)式的代碼，轉(zhuǎn)化為一組這樣的語(yǔ)句序列：x = y(y可以是一個(gè)變量或者數(shù)字)和x = y (op) z(op可以是+, -, * /, y和z可以是變量，數(shù)字，或者子表達(dá)式)。你可以把每條語(yǔ)句想象成某種電路的邏輯門， 上面的代碼被抹平后的結(jié)果如下：
sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5
如果你對(duì)比下原來(lái)的代碼，你會(huì)很容易發(fā)現(xiàn)，它們是等價(jià)的。
轉(zhuǎn)化為R1CS
現(xiàn)在，我們把這個(gè)東西轉(zhuǎn)化為一級(jí)約束系統(tǒng)(R1CS)。一個(gè)R1CS是一組三向量(a, b, c)構(gòu)成的一個(gè)序列。假設(shè)R1CS的解是一個(gè)向量s，那么s必須滿足這個(gè)等式s·a * s·b - s·c = 0。這里的·代表向量的點(diǎn)乘，簡(jiǎn)單說(shuō)，s·a就是把s , a一對(duì)一并在一起，把他們相同位置上的元素相乘然后結(jié)果相加，就得到了點(diǎn)乘的結(jié)果，然后我們對(duì)于s·b和s·c也這么操作，那么如果第三個(gè)結(jié)果就等于前兩個(gè)結(jié)果的和，上面的式子就滿足了，就像下面這樣：
上面圖示的只是一個(gè)約束，我們將會(huì)有多個(gè)約束：每個(gè)邏輯門一個(gè)約束。把邏輯門轉(zhuǎn)換為(a, b, c)三個(gè)向量組有一個(gè)標(biāo)準(zhǔn)的方法，這個(gè)方法于運(yùn)算符(+,-,*,/)及其操作數(shù)有關(guān)。每個(gè)向量的長(zhǎng)度等于這個(gè)系統(tǒng)中所有變量的個(gè)數(shù)，同時(shí)也包括代表1的變量~one，我們把它放在向量第一個(gè)索引位置；還包括代表輸出的~out，以及中間變量(上面的sym1, sym2)。這些向量通常比較稀疏，只在邏輯門相關(guān)的變量位置才有值，其他地方都為0。
首先，我們先提供我們將要使用的變量位置映射如下：
one, x, ~out, sym_1, y, sym_2
解向量 的值代表著依次給上面變量的賦值。
譯者注：假設(shè)解向量的結(jié)果是[1, 2, 3, 4, 5, 6]，那么代表著x == 2, ~out == 3, sym_1 == 4, y = 5, sym_2 = 6
現(xiàn)在我們給出第一組邏輯門的向量(a, b, c):
a = [0, 1, 0, 0, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 1, 0, 0]
譯者注：參見(jiàn)這個(gè)邏輯門 sym_1 = x * x， a向量在對(duì)應(yīng)位置存儲(chǔ)運(yùn)算符(*)左邊操作數(shù)x的系數(shù)1，參見(jiàn)上面的映射中變量x的位置，它在第2個(gè)位置，所以就把系數(shù)1也寫在a向量的第2個(gè)位置。
你可以看到，如果解向量在第二個(gè)位置包含3，在第4個(gè)位置包含9，那么不管解向量中其他位置是什么，這個(gè)點(diǎn)乘(s·a * s·b = s·c)就變成了3*3 = 9，如此就能通過(guò)測(cè)試——做這個(gè)檢測(cè)是僅僅為了驗(yàn)證第一個(gè)邏輯門的輸入和輸出是否一致。
現(xiàn)在我們繼續(xù)第二個(gè)邏輯門：
a = [0, 0, 0, 1, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 0, 1, 0]
同樣的檢測(cè)的方式，我們可以驗(yàn)證它是與sym_1 * x = y相符的。
再來(lái)第三個(gè)門：
a = [0, 1, 0, 0, 1, 0]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 0, 0, 0, 1]
這里，有一點(diǎn)不同：它是把解向量中第1個(gè)元素與第二個(gè)元素相乘，再加上第五個(gè)元素，然后檢查是否與第6個(gè)元素相等。因?yàn)榻庀蛄恐械谝粋€(gè)元素總是1，所以這只是一個(gè)加法的檢查，看兩個(gè)輸入的和是否等于輸出。
最后，第四個(gè)門：
a = [5, 0, 0, 0, 0, 1]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 1, 0, 0, 0]
這里，我們做最后一個(gè)檢查~out = sym_2 + 5。把解向量中的第六個(gè)元素與5被的第一個(gè)元素相加(記住，第一個(gè)元素是1，所以最終變成 加5)，然后與第三個(gè)元素相比較。
這就是我們帶四個(gè)約束條件的R1CS。它的見(jiàn)證者(witness)很簡(jiǎn)單，就是對(duì)所有這些變量(包括輸入輸出和中間變量)的一組賦值。
[1, 3, 35, 9, 27, 30]
你可以自己執(zhí)行以下試試，利用下上面的被抹平的代碼，從給變量的賦值x=3開(kāi)始，然后計(jì)算出中間值，并與上面解向量對(duì)比一下。
我們把完整的R1CS放在一起如下(譯者注：A代表a向量組，B代表b向量組，C代表c向量組)：
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]
譯者注：V神的文章喜歡用長(zhǎng)語(yǔ)句，我翻譯的比較慢，怕翻譯錯(cuò)了。今天先到這里吧，今天是上半部分，明天繼續(xù)下半部分
早贊聲明：為方便早贊、避免亂贊，“BH好文好報(bào)群”為點(diǎn)贊者、寫作者牽線搭橋，實(shí)行“先審后贊、定時(shí)發(fā)表”的規(guī)則，也讓作品脫穎而出、速登熱門！加群微信：we01230123（天平）。
