本文翻譯自V神的Medium文章：二次計算方程：從0到1磺送，詳細講解了QAP躯泰，并給出了一個程序?qū)崿F(xiàn)栈戳，本文是上半部分厨剪，介紹了把計算轉(zhuǎn)化為R1CS的過程哄酝。zcash官方博客對QAP這部分講解的比較粗糙，V神的這篇文章是個很好的補充祷膳。友情提示：本文偏技術(shù)化陶衅，適合對技術(shù)非常感興趣的同學閱讀。
(本文授權(quán)BH好文好報群摘編直晨、轉(zhuǎn)載以及相關(guān)轉(zhuǎn)授權(quán)推文行為)
二次計算方程：從0到1
最近zk-SNARKs吸引了很多人的注意力搀军，因為她那難以捉摸的復雜性，所以有人把它稱之為“月亮數(shù)學”勇皇；人人都想揭開它的神秘面紗罩句。zk-SNARKs確實比較難以掌握，它里面包含了好幾個比較難以理解的知識點敛摘；如果我們把這些知識點分開來去掌握门烂，就沒那么難了。
這篇文章，不會把zk-SNARKs的內(nèi)部都介紹一邊屯远，而是假設你已經(jīng)有了如下基礎知識：
- 你知道zk-SNARKs是什么以及它有什么用
- 你有多項式相關(guān)的數(shù)學知識(如果這樣的多項式對你來說很熟悉： P(x) + Q(x) = (P+X)(x),其中P和Q都是多項式蔓姚。
那么你就沒問題)。不僅如此慨丐，本文還會對技術(shù)背后的機制做深入的研究坡脐，并試圖解釋下圖中前半部分的知識點。
這些步驟可以分成兩部分房揭。第一备闲，zk-SNARKs不是所有的計算問題都可以直接用的；你需要把問題轉(zhuǎn)換為正確的“形式”之后捅暴，才能進行后續(xù)操作浅役。這種形式被稱作“二次計算方程”(QAP)，把一個函數(shù)的代碼轉(zhuǎn)化為這種形式本身就不是一件簡單的事情伶唯。在這個轉(zhuǎn)換過程之外觉既，還有另外一個過程，就是如果你有這段代碼的輸入乳幸，就能夠創(chuàng)建相應的“解”(有時候被叫做QAP的"見證者")瞪讼。然后，為這個“解”創(chuàng)建真正的"零知識證明"粹断，以及驗證證明的過程符欠，不過這些都是本篇內(nèi)容之外的內(nèi)容，這里不做細述了瓶埋。
我們選用的是一個簡單的例子: 證明你知道下面這個三次方程的解：
x^3 + x + 5 = 35(提示：答案是3).
這問題非常簡單希柿，這樣生成的QAP不會太大，所以比較好模擬养筒；但是已經(jīng)足夠我們研究相關(guān)的技術(shù)機制了曾撤。
我們把這個函數(shù)這樣寫下來：
def qeval(x)
y = x**3
return x + y + 5
這里用到的這個特別的編程語言支持基本的算術(shù)運算(+,-, *, /)，常數(shù)指數(shù)運算(類似于x**7晕粪，而不是x**y)挤悉，以及變量賦值。這些已經(jīng)足夠強大了巫湘，理論上装悲，你可以用他們做任何計算。注意尚氛，求余運算(%)和比較運算(<, >, <=, >=)是不支持的诀诊。這是因為在有限循環(huán)群里面，沒有求余運算和比較運算的高效方法(幸虧是這樣阅嘶；不然橢圓曲線加密算法就可以很快被破解了)属瓣。
要是想支持求余和比較運算，你可以給這個語言增加位分解功能（比如： 13 = 2 ^3 + 2^2 + 1），它可以作為一種輔助輸入奠涌，在二進制電路里面進行一些數(shù)學計算并驗證分解的正確性宪巨；在有限域運算中，檢測相等(==)也是可行溜畅，實際上還更容易一點捏卓，不過這些都是一些細節(jié)了，我們這里不再深入了慈格。我們可以給這個語言增加條件判斷(比如：if x < 5: y= 7; else: y = 9)怠晴，可以通過把它們轉(zhuǎn)化為算術(shù)形式來實現(xiàn)：y = 7*(x < 5) + 9 * (x >= 5) , 不過這種這種形式還是會有兩個條件運算需要執(zhí)行。如果你有很多的嵌套的條件判斷浴捆，那么這個計算量的開銷也是很大的蒜田。
現(xiàn)在讓我們一步步的走一遍這個過程。如果你想自己實現(xiàn)一些代碼选泻，可以參考我實現(xiàn)的這個翻譯器(僅供學習使用冲粤；不能作為真實場景中的zk-SNARKs使用)
抹平
第一步就是"抹平"操作，我們把原始的包含各種復雜的語句和表達式的代碼页眯，轉(zhuǎn)化為一組這樣的語句序列：x = y(y可以是一個變量或者數(shù)字)和x = y (op) z(op可以是+, -, * /, y和z可以是變量梯捕，數(shù)字，或者子表達式)窝撵。你可以把每條語句想象成某種電路的邏輯門傀顾， 上面的代碼被抹平后的結(jié)果如下：
sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5
如果你對比下原來的代碼，你會很容易發(fā)現(xiàn)碌奉，它們是等價的短曾。
轉(zhuǎn)化為R1CS
現(xiàn)在，我們把這個東西轉(zhuǎn)化為一級約束系統(tǒng)(R1CS)赐劣。一個R1CS是一組三向量(a, b, c)構(gòu)成的一個序列嫉拐。假設R1CS的解是一個向量s，那么s必須滿足這個等式s·a * s·b - s·c = 0隆豹。這里的·代表向量的點乘椭岩，簡單說茅逮，s·a就是把s , a一對一并在一起璃赡，把他們相同位置上的元素相乘然后結(jié)果相加，就得到了點乘的結(jié)果献雅，然后我們對于s·b和s·c也這么操作碉考，那么如果第三個結(jié)果就等于前兩個結(jié)果的和，上面的式子就滿足了挺身，就像下面這樣：
上面圖示的只是一個約束侯谁，我們將會有多個約束：每個邏輯門一個約束。把邏輯門轉(zhuǎn)換為(a, b, c)三個向量組有一個標準的方法，這個方法于運算符(+,-,*,/)及其操作數(shù)有關(guān)墙贱。每個向量的長度等于這個系統(tǒng)中所有變量的個數(shù)热芹，同時也包括代表1的變量~one，我們把它放在向量第一個索引位置惨撇；還包括代表輸出的~out伊脓，以及中間變量(上面的sym1, sym2)。這些向量通常比較稀疏魁衙，只在邏輯門相關(guān)的變量位置才有值报腔，其他地方都為0。
首先剖淀，我們先提供我們將要使用的變量位置映射如下：
one, x, ~out, sym_1, y, sym_2
解向量 的值代表著依次給上面變量的賦值纯蛾。
譯者注：假設解向量的結(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]
譯者注：參見這個邏輯門 sym_1 = x * x纵隔， a向量在對應位置存儲運算符(*)左邊操作數(shù)x的系數(shù)1翻诉，參見上面的映射中變量x的位置，它在第2個位置捌刮，所以就把系數(shù)1也寫在a向量的第2個位置米丘。
你可以看到，如果解向量在第二個位置包含3糊啡，在第4個位置包含9拄查，那么不管解向量中其他位置是什么，這個點乘(s·a * s·b = s·c)就變成了3*3 = 9棚蓄，如此就能通過測試——做這個檢測是僅僅為了驗證第一個邏輯門的輸入和輸出是否一致堕扶。
現(xiàn)在我們繼續(xù)第二個邏輯門：
a = [0, 0, 0, 1, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 0, 1, 0]
同樣的檢測的方式，我們可以驗證它是與sym_1 * x = y相符的梭依。
再來第三個門：
a = [0, 1, 0, 0, 1, 0]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 0, 0, 0, 1]
這里稍算，有一點不同：它是把解向量中第1個元素與第二個元素相乘，再加上第五個元素役拴，然后檢查是否與第6個元素相等糊探。因為解向量中第一個元素總是1，所以這只是一個加法的檢查河闰，看兩個輸入的和是否等于輸出科平。
最后，第四個門：
a = [5, 0, 0, 0, 0, 1]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 1, 0, 0, 0]
這里姜性，我們做最后一個檢查~out = sym_2 + 5瞪慧。把解向量中的第六個元素與5被的第一個元素相加(記住，第一個元素是1部念，所以最終變成 加5)弃酌，然后與第三個元素相比較氨菇。
這就是我們帶四個約束條件的R1CS。它的見證者(witness)很簡單妓湘，就是對所有這些變量(包括輸入輸出和中間變量)的一組賦值查蓉。
[1, 3, 35, 9, 27, 30]
你可以自己執(zhí)行以下試試，利用下上面的被抹平的代碼榜贴，從給變量的賦值x=3開始奶是，然后計算出中間值，并與上面解向量對比一下竣灌。
我們把完整的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神的文章喜歡用長語句初嘹，我翻譯的比較慢及汉，怕翻譯錯了。今天先到這里吧屯烦，今天是上半部分坷随，明天繼續(xù)下半部分
早贊聲明：為方便早贊、避免亂贊驻龟，“BH好文好報群”為點贊者温眉、寫作者牽線搭橋，實行“先審后贊翁狐、定時發(fā)表”的規(guī)則类溢，也讓作品脫穎而出、速登熱門露懒！加群微信：we01230123（天平）闯冷。
