比如將原來多項式稍微修改一下變為x^3 - 6x^2 + 10x - 5，兩個多項式的影象如下圖：
我們可以令兩個多項式相等來找到它們的交點，得出 x = 1，即兩個多項式只有一個交點(1, 0)。
對於這兩個多項式，最多有三個不同的x取值可以讓結果相等（實際這裡只有一個），其他任意取值的x導致的計算結果都不相同。因此當一個Prover（證明者）聲稱他知道Verifier（驗證者）也知道的多項式，即他知道該多項式的係數（知道所有n個係數即可確定一個n階多項式），這裡階數越高係數越多，無論係數多少個，他們都可以按下面的協議進行驗證：
Verifier選擇一個隨機值r並在本地計算多項式的結果
Verifier將r傳給Prover，並讓Prover計算相關的多項式結果
Prover代入r到多項式計算並將結果返回給Verifier
Verifier檢查本地計算結果和Prover返回的結果是否相等，如果相等則說明Prover的陳述有較高可信度
比如將r的取值範圍定為[1, 10^77]，多項式階數為d，P和V計算得到不同結果的數量可以有10^77-d個，因此如果他們多項式不相等，則碰巧計算結果相等的概率為d/10^77，我們認為幾乎不可能。
這裡只需要驗證一次就可以達到幾乎100%的可信度，所以zkSNARK的核心就是用多項式作為證明媒介。
3. 證明多項式的知識
如上所述，多項式的知識就是它的係數。如果一個人說他知道一個多項式（例如：c1x^1 + c0=0），就意味著他知道多項式的係數c1、c0。
一個比較簡單的定理是，任意一個多項式只要有解，就可以分解成多個線性多項式（一階多項式的影象是直線所以叫線性多項式)，即可以將任意多項式看成其因式的乘積：
(x - a0)(x - a1)...(x - an) = 0
只要任意一個因式為0則整個多項式等於0，也就是所有x=a0,a1...an都是多項式的解。
瞭解了這些，接下來讓我們看看這樣一個證明問題：V想要找一個包含解x=1和x=2的多項式，P聲稱自己知道這樣一個多項式，他需要向V證明他知道，但是不希望V馬上知道答案。
假設P知道的多項式為x^3 - 3x^2 + 2x = x(x-1)(x-2)，他要證明多項式p(x)包含兩個解x=1和x=2，令t = (x-1)(x-2)，則只需要證明p(x) = h(x) * t(x)
這裡h(x) = p(x) / t(x) ，如果不能計算出這樣的h(x)，也就意味p(x)不包含t(x)，會有餘數（關於多項式除法可以參考[pik14]）。
這裡計算出h(x) = x，沒有餘數。說明Prover可以證明他知道這樣一個多項式包含解x=1和x=2。
接下來實踐一遍驗證過程：
Verifier隨機挑選一個數r = 23，計算t = (23 - 1)(23 - 2) = 462，將r發給Prover
Prover計算得到h(x) = p(x)/t(x) = x，分別計算p(r) = p(23) = 10626，h(r) = h(23) = 23，將p(r)和h(r)發給Verifier
Verifier驗證p = h * t : 10626 = 23 * 462 是正確的，驗證透過
這裡如果Prover不知道具體的p(x)，則不能計算出匹配的h(x)，返回的數值就不會驗證透過。完成驗證後Verifier不知道具體的p(x)和h(x)，但是可以確定Prover知道這樣一個多項式，包含解x=1和x=2。
4. 一般程式到多項式-zkSNARK
上面我們講了如何證明多項式的知識，接下來只需要將證明一般的程式問題轉為證明多項式就可以解決大部分場景的證明問題了。
我們用一個簡單問題來走一遍：證明你知道三次方程x^3 + x + 5 == 35的解(答案是3)，前提是不透露這個解。
第一步：拍平
拍平就是將任意複雜的表示式轉換為只有兩種運算形式（加法和乘法）。
這裡說的任意複雜的問題是指計算機在有限時間內能解決的計算問題，加法和乘法可以表示其他的運演算法則，比如證明a-b=c，因為證明問題我們是知道結果c的，所以只需要寫成b+c=a就可以，其他比如除法、比較大小等都可以表示，這裡不作展開。
上述方程拍平可以得到：
sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5
可以看出來，拍平後的表示式與原始方程是等價的。
第二步：轉為R1CS
一階約束系統R1CS（rank-1 contraint system）是描述向量組之間的約束關係。其實上面的方程或者拍平的表示式就是一種約束系統，這種約束關係確定了只有特定的x滿足約束條件，這裡x=3就是滿足約束的解，將x=3代入拍平後的表示式可以得到一組解向量s：
[~one, x, ~out, sym_1, y, sym_2]
= [1, 3, 35, 9, 27, 30]
拍平後的四行表示式，每一行是一個乘法門（加法是乘常數1），即一個約束。用R1CS描述原方程就是有四個約束，每一個乘法門約束關係我們都用A*B-C=0表示。例如第一個約束sym_1 = x * x，表示為R1CS為一個向量組：
A: [0, 1, 0, 0, 0, 0]
B: [0, 1, 0, 0, 0, 0]
C: [0, 0, 0, 1, 0, 0]
將解向量代入應該是滿足這一個約束的（3 * 3 - 9 = 0），如下圖所示
這裡是將解向量代入驗證，用來表示約束關係只需要a、b、c三個向量，所以將四個約束全部表示出來得到如下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]
可以看出來，我們將乘法門左向量都放到A組，右向量都放到B組，輸出向量都在C組。到這裡我們就成功將一個計算問題轉換成了R1CS，接下來要做的就是證明我們的解滿足這個約束關係。我們不能像上圖那樣把解帶進去驗證四次，這樣的證明不能零知識也不夠簡潔，所以下一步還需要將R1CS轉為多項式。
第三步：R1CS轉為QAP
要將這些向量轉為QAP(quadratic arithmetic program)，需要先了解一下拉格朗日插值定理：
經過n個點(x1, y1)、(x2, y2)...(xn, yn)的n-1階多項式為：
比如點(1,2) (2,2) (3,4)對應的多項式為：
知道怎麼用這個公式之後，我們開始將上一步的R1CS轉為QAP。對於ABC三組向量，每組的六個變數分別對應一個多項式，多項式經過四個點，取橫座標x=1,2,3,4，縱座標為向量的值，進行拉格朗日插值：
例如(1, 0) (2, 0) (3, 0) (4, 5) 插值後的多項式為0.833x^3 - 5x^2+9.166x -5，將多項式的係數按冪升序排列，於是有全部的QAP：
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]
此時如果將x=1代入上面18個多項式，可以得到第一個約束的三個先向量，再將x=2,3,4分別代入可以恢復出所有的R1CS。我們可以驗證，當且僅當x=1、2、3、4時，下面關係都是成立的：
設Z(x)=(x-1)(x-2)(x-3)(x-4),則有A(x) * B(x) - C(x) = H * Z(x)
參考上面多項式證明中講的一致性原理，這裡原始方程x^3 + x + 5 ==35的解3決定了A、B、C多項式的係數，我們要驗證的就是Prover知道詳細的A(x)、B(x)、C(x)的具體數值，Verifier透過發起隨機數挑戰就可以驗證Prover知道原方程的解，但是Verifier自始至終無法得到原方程的解。
5. 總結
至此我們理解了zkSNARK的基本原理，這裡也能看出，一個簡單的方程要做到零知識證明需要相對較多的計算，但是證明的效率卻很高。如果希望更快速高效的進行鏈上驗證，包括解決小數誤差的影響，就要用到有限域和橢圓曲線等。後面的系列我們會介紹如何繼續最佳化zkSNARK，讓它可以實際應用起來。
附錄
[Pik14] - Scott Pike. Dividing by a Polynomial. 2014.
url:http://www.mesacc.edu/~scotz47781/mat120/notes/divide_poly/long_division/long_division.html
[But16] - Vitalik Buterin. Quadratic Arithmetic Programs: from Zero to Hero. 2016.
url:https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
[But17] - Vitalik Buterin. zk-SNARKs: Under the Hood. 2017.
url:https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
