想象一下我們有一個長度為10 的位陣列，現在要向 verifier（例如，程式）證明這樣一個陳述：所有的位都被設定成了 1。
verifier 一次只能檢查（即，讀）一位。為了驗證這個陳述，我們以某種任意的順序讀取元素並檢查其是否確實等於 1 。如果第一次抽樣檢查的結果是 1，就設定「陳述」的可信度為 ⅒= 10％，否則，如果等於 0，就說明「陳述」是錯誤的。驗證者繼續進行下一輪驗證，直到獲得足夠的可信度為止。假如在一些場景下要信任 prover 需要至少 50% 的可信度，那就意味著必須執行 5 次校驗。但假如在其它一些場景下需要 95% 的可信度，就需要檢查所有的元素。很明顯這個證明協議的缺點是必須要根據元素的數量進行檢查，如果我們處理數百萬個元素的陣列，這麼做是不現實的。
現在我們來看一下由數學方程式表示的多項式，它可以被畫成座標系上的一條曲線：
上面的曲線對應多項式: f(x) = x³ – 6x² +11x– 6。多項式的階數取決於 x 的最大指數，當前多項式的階數是 3。
多項式有一個非常好的特性，就是如果我們有兩個階為 d 的不相等多項式，他們相交的點數不會超過 d。例如，稍微修改一下原來的多項式為 x³ – 6x² + 10x– 5 （注：請注意這裡只修改了多項式的最後一個係數，6改成了5）並在圖上用綠色標出：
這一點微小的修改就產生了變化很大的曲線。事實上，我們不可能找到兩條不同的曲線，他們會在某段區域內重合（他們只會相交於一些點）。
這是從找多項式共同點方法中得出的性質。如果要查詢兩個多項式的交點，就要先令它們相等。例如，要找到多項式與 x 軸的交點（即 f(x) = 0），我們就要令 x³ – 6x² + 11x – 6 = 0，等式的解就是共同點：x= 1 ，x= 2 和 x= 3。在上面圖中也可以很清晰得看出這些解，也就是圖上藍色曲線和 x 軸相交的地方。
同樣，我們也可以令上文中原始的多項式和修改後的多項式相等，找到它們的交點。
x³ – 6x² + 11x – 6 =x³ – 6x² + 10x – 5
x-1=0
多項式化簡後的結果階數為 1，它有一個很明顯的解 x = 1。因而這兩個多項式有一個交點。
任意一個由階數為 d 的多項式組成的等式，最後都會被化簡為另外一個階數至多為 d 的多項式，這是因為等式中沒有能夠用來構造更高階數的乘法。例如：5x³ + 7x² – x + 2 = 3x³ – x² + 2x– 5，簡化為 2x³ + 8x² – 3x + 7 = 0。另外代數的基本原理也告訴我們，對於一個階數為 d 的多項式至多有 d 個解（以下部分將對此進行詳細介紹），因而也就至多有d 個共同點。
所以我們可以得出結論，任何多項式在任意點的計算結果（更多關於多項式求值參考：[Pik13]）都可以看做是其唯一身份的表示。我們來計算一下當 x = 10 時，示例多項式的結果。
x³ – 6x² +11x - 6 = 504
x³ – 6x² +10x - 5 = 495
事實上，在 x 可以選擇的所有值中，至多隻有三個值能夠使這些多項式相等，其它的值都是不相等的。
這也是為什麼如果一個 prover 聲稱他知道一些 verifier 也知道的多項式（無論多項式的階數有多大）時，他們就可以按照一個簡單的協議去驗證：
· verifier 選擇一個隨機值 x 並在本地計算多項式結果
· verifier 將 x 值給到 prover，並讓他計算相關的多項式結果
· prover 代入 x 到多項式計算並將結果給到 verifier
· verifier 檢查本地的計算結果和 prover 的計算結果是否相等，如果相等那就說明 prover 的陳述具有較高的可信度
例如，我們把 x 的取值範圍定在 1 到 10⁷⁷, 那麼計算結果不同的點的數量，就有 10⁷⁷ – d 個。因而 x 偶然“撞到”這 d 個結果相同的點中任意一個的概率就等於（可以認為是幾乎不可能）：d/10^77
@Maksym（作者）
與低效的位檢查協議相比，新的協議只需要一輪驗證就可以讓陳述具有非常高的可信度（假設 d 遠小於 x 取值範圍的上限，就幾乎是 100%了）
這也是為什麼即使可能存在其他的證明媒介，多項式依然是 zk-SNARK 相對核心的部分。
註解
admin@chaindaily安比實驗室：這一節告訴了我們多項式的一個重要性質：我們不可能找到共享連續段的兩條不相等曲線，也就是任何多項式在任意點的計算結果都可以看做是其唯一身份的表示。也就是說只要能證明多項式上的某個隨機點就可以證明這個多項式（只有在知道了多項式，才能算出這個點對於的值），這個性質是我們下面所有證明的核心。
這就是 Schwatz-Zippel 定理，它可以擴充套件到多變數多項式，即在一個多維空間內形成一個曲面。這個定理會在多個零知識證明方案的證明中反覆出現。
證明多項式的知識
我們的討論從證明多項式的知識開始，再將證明協議逐步轉換成一種通用的方法，在這個過程中我們也將發現多項式的很多其它性質。
但是到目前為止，我們的協議還只是一個很弱的證明，因為協議中並沒有採取任何措施去保證參與方必須按照協議的規則生成證明，所以參與方只能互相信任。例如，prover 並不需要知道多項式，也可能透過其它方式得到正確的答案。而且，如果 verifier 要驗證的多項式的解的取值範圍不夠大，比如我們前文說的 10，那個就可以去猜一個數字，猜對答案的概率是不可忽略不計的。因而我們必須要解決協議中的這個缺陷，在解決問題之前首先來想一下，知道多項式意味著什麼呢？
多項式可以用下面的形式來表示（其中 n 指的是多項式的階）：
cnxn + …… + c1x1 + c0x0
如果一個人說他或她知道一個一階多項式（即：c1x1 + c0=0），那麼這就意味著他或她確實知道 係數 c0, c1 的值。這個係數可以是包括 0 在內的任意值。
假設證明者聲稱他知道一個包含 x=1 和 x=2 兩個解的三階多項式。滿足此條件的一個有效的多項式就是 x3 – 3x2+ 2x= 0。因為x= 1: 1 – 3 + 2 = 0，x= 2: 8 – 12 + 4 = 0。
我們先來仔細得研究一下這個答案的結構。
註解
admin@chaindaily安比實驗室：這一節告訴了我們多項式的一個本質——多項式的「知識」就是多項式的係數。所謂「知道」多項式就是指「知道」多項式的係數。
因式分解
代數的基本定理表明了任意的一個多項式只要它有解，就可以將它分解成線性多項式（即，一個階數為 1 的多項式代表一條線），因此，我們可以把任意有效的多項式看成是其因式的乘積：
(x-a0)(x-a1)…(x-an) = 0
也就是說如果任意一個因式為 0，那麼整個等式都為 0，也就是說式子中所有的 as 就是多項式的所有解。
x3 - 3x2 + 2x =(x-0)(x-1)(x-2)
所以這個多項式的解（x 的值）就是：0，1，2，在任何形式下多項式的解都可以很輕鬆的被驗證，只不過因式的形式可以讓我們一眼就看出這些解（也稱為根）。
我們再回到前面的問題， prover 宣稱他知道一個階數為 3，其中兩個根分別為 1 和 2 的多項式，也就是說這個多項式的形式為：
(x-1)(x-2) · …
換句話說 (x–1) 和 (x –2) 是問題中多項式的兩個因式。因而如果 prover 想要在不揭示多項式的前提下證明他的多項式確實有這兩個根，那麼他就需要去證明他的多項式 p(x) 是 t(x) = (x- 1)(x- 2) （也稱為目標多項式）和一些任意多項式 h(x) （也就是我們的例子裡面的 x - 0）的乘積，即：
p(x) = t(x) · h(x)
換句話說，存在一些多項式 h(x) 能夠使得 t(x) 與之相乘後等於 p(x)，由此得出， p(x) 中包含 t(x)，所以 p(x) 的根中也包含 t(x) 的所有根，這也就是我們要證明的東西。
自然算出 h(x) 的方式就是直接相除：
如果一個 prover 不能找到這樣一個 h(x) 也就意味著 p(x) 中不包含因式 t(x)，那麼多項式相除就會有餘數。例如我們用 p(x) = x³ – 3x² + 2x 除以 t(x) = (x – 1)(x – 2) = x² – 3x+ 2
注意：左邊的式子是分母，右上角的是計算結果。底部是餘數（多項式相除的解釋及示例可以看這裡 [Pik14] ）。
我們算出結果 h(x) = x，沒有餘數。
注意：為了簡化起見，後面我們會用多項式的字母變數來代替計算結果值，例如：p = p(r)。
註解
admin@chaindaily安比實驗室：多項式可以被因式分解成它的根的因式的乘積。這個性質就意味著，如果一個多項式有某些解，那麼它被因式分解後的式子中一定包含這些解的因式。
有了這個性質，我們就可以愉快地去做一些證明啦。
· 利用多項式一致性檢查協議我們就可以比較多項式 p(x) 和 t(x) ⋅ h(x)：
· verifier 挑選一個隨機值 r, 計算 t = t(r) (即，求值) ，然後將 r 傳送給 prover。
· prover 計算 h(x) =p(x) / t(x) ，並對 p(r) 和 h(r) 進行求值，將計算結果 p, h 提供給 verifier。
· verifier 驗證 p= t⋅h，如果多項式相等，就意味著 t(x) 是 p(x) 的因式。
實踐一下，用下面的例子來執行這個協議：
· verifier 選一個隨機數 23，並計算 t = t(23) = (23 – 1)(23 – 2) = 462，然後將 23 發給 prover
· prover 計算 h(x) =p(x) / t(x) = x, 並對 p(r) 和 h(r) 進行求值，p= p(23) = 10626，h= h(23) = 23，將 p 和 h 提供給 verifier
· verifier 再驗證 p= t⋅h：10626 = 462 ⋅ 23 是正確的，這樣陳述就被證明了。
·相反，如果 prover 使用一個不同的 p′(x) ，它並不包含必要的因式，例如 p′(x) = 2x³ – 3x² + 2x, 那麼：
@Maksym（作者）
雖然為了簡化而使用了一組數學符號，但是如果忽視這個無處不在的基本符號：’(上撇)的話將不利於理解。這個符號本質目的是為了強調一個經過初始變數變換或者推導得到的新變數。即，如果我們想要將 v 乘以 2 並給將它賦值給一個新的變數，我們可以使用：v'= 2 ⋅ v。
我們算出結果2x + 3 和餘數7x – 6，即：p(x) = t(x) × (2x+ 3) + 7x – 6。這就意味著 verifier 為了計算出結果他不得不用 餘數除以t(x)，
不過由於 x 是 verifier 隨機選擇的，就有極低的概率餘數 7x – 6 最終可以被 t(x) 整除。如果後面 verifier 要另外再檢查 p 和 h 必須是整數的話，這個證明才會被拒絕。不過要這麼校驗就同時要求多項式係數也是整數，這對協議產生了極大的限制。
這就是為什麼接下來我們要介紹能夠使餘數不被整除的密碼學原理的原因，儘管這個原始值是有可能被整除的。
Remark 3.1 現在我們就可以在不知道多項式的前提下根據特定的性質來驗證多項式了，這就已經給了我們一些零知識和簡明性的特性。但是，這個結構中還存在好多問題：
· prover 可能並不知道他所聲稱的 p(x)，他可以先算一下 t = t(r)，然後選擇一個隨機值 h，由此計算出 p = t⋅h。因為等式是成立的，所以也能透過 verifier 的校驗。
· 因為 prover 知道隨機點 x = r ，他可以構造出一個任意的多項式，這個任意多項式與 t(r) ⋅ h(r) 在 r 處有共同點。
· 在前面的「陳述」中，prover 聲稱他知道一個特定階數的多項式，但現在的協議對階數並沒有明確的要求。因而 prover 完全可以拿一個滿足因式校驗的更高階數的多項式來欺騙 verifier。
下面我們就要來逐一得解決這些問題。
註解
admin@chaindaily安比實驗室：利用因式的性質構造出了一個證明協議，但這個協議存在一些缺陷，主要是由於
prover 知道了 t(r)，他就可以反過來任意構造一個可以整除 t(r) 的 p(r)
prover 知道了點(r,t(r) · h(r)) 的值，就可以構造經過這一點的任意多項式，同樣滿足校驗
協議並沒有對 prover 的多項式階數進行約束
模糊計算
Remark 3.1 中的前兩個問題是由於 暴露了原始值 而導致的，也就是 prover 知道了 r 和 t(r)。但如果 verifier 給出的這個值像放在黑盒裡一樣不可見的話就完美了，也就是一個人即使不破壞協議，也依然能在這些模糊的值上面完成計算。有點類似雜湊函式，從計算結果就很難再回到原始值上。
同態加密
這也就是要設計同態加密的原因。它允許加密一個值並在密文上進行算術運算。獲取加密的同態性質的方法有多種，我們來介紹一個簡單的方法。
總體思路就是我們選擇一個基礎的（基數需要具有某些特定的屬性）的自然數 g（如 5），然後我們以要加密的值為指數對 g 進行求冪。例如，如果我們要對 3 進行加密：
53=125
這裡 125 就是 3 對應的密文。如果我們想要對被加密的值乘 2，我們可以以 2 為指數來對這個密文進行計算。
125² = 15625 = (5³)² = 52×3 = 56
我們不僅可以用 2 來乘以一個未知的值並保持密文的有效性，還可以透過密文相乘來使兩個值相加，例如 3+2：
53 · 52 = 53+2 = 5 5 =3125
同樣的，我們還可以透過相除提取加密的數字，例如：5-3
55/53 = 55 ·5-3 =5 5-3 = 52 =25
不過由於基數 5 是公開的，很容易就可以找到被加密的數字。只要將密文一直除以 5，直到結果為 1，那麼做除法的次數也就是被加密值的數。
模運算
這裡就到了模運算髮揮作用的地方了。模運算的思路如下：除了我們所選擇的組成有限集合的前 n 個自然數（即，0，1，…，n-1）以外，任何超出此範圍的給定整數，我們就將它“纏繞”起來。例如，我們選擇前六個數。為了說明這一點，可以把它看做一個有六個單位大小相等刻度的圓；這就是我們所說的範圍（通常指的是有限域）。
這就是模運算操作的結果。無論這根繩子多長，它最終都會在圓圈一個刻度處終止。因而模運算結果將保持在一定範圍內（例子中是 0 到 5）。長度為 15 的繩子將會在刻度 3 的地方終止，即 6 + 6 + 3 （纏 2 個完整的圈並剩下 3 個單位長的部分）。負數運算類似，唯一不同的地方就是它是沿相反方向纏繞的，如 -8 的取模結果是 4。
我們執行算術運算，結果都將落在這 n 的範圍內。現在開始我們將用符號 “mod n” 來表示這個範圍內的數。
3 × 5 = 3 mod 6
5 + 2 = 1 mod 6
另外，模運算最重要的性質就是運算順序無所謂。例如，我們可以先做完所有的操作，然後再取模，或者每操作完一步都去取模。例如 (2 × 4 – 1) × 3 = 3 (mod 6) 就等於：
2 × 4 = 1 mod 6
2 - 1 = 1 mod 6
1 × 3 = 3 mod 6
那麼模運算到底有什麼用呢？就是如果我們使用模運算，從運算結果再回到原始值並不容易，因為很多不同的組合會產生一個同樣的運算結果：
5 × 4 = 2 mod 6
4 × 2 = 2 mod 6
2 × 1 = 1 mod 6
……
沒有模運算的話，計算結果的大小會給找出原始值提供一些線索。除非這裡既能把資訊隱藏起來，又可以保留常見的算術屬性。
強同態加密
我們再回到同態加密上，使用模運算，例如取模 7，我們可以得到：
51 = 5(mod 7)
52 = 4(mod 7)
53 = 6(mod 7)
……
不同指數下運算得到了同樣的結果：
55 = 3(mod 7)
511 = 3(mod 7)
517 = 3(mod 7)
……
這樣就很難知道指數是多少了。事實上，如果模取得相當大，從運算結果倒推指數運算就不可行了；現代密碼學很大程度上就是基於這個問題的“困難”。
方案中所有的同態性質都在模運算中保留了下來：
encryption: 53 = 6 (mod 7)
multiplication: 62 = (53)2 = 56 = 1 (mod 7)
addition: 53 · 52 = 55 = 3(mod 7)
注意：模相除有點難已經超出範圍了。
我們來明確地說明一下加密函式：
E(v) = gv(mod n)
這裡 v 就是我們要加密的值。
Remark 3.2 這個同態加密模式有一個限制，我們可以把一個加密的值和一個未加密的值相乘，但我們不能將兩個加密的值相乘（或者相除），也就是說我們不能對加密值取冪。雖然這些性質第一感覺看起來很不友好，但是這卻構成了 zk-SNARK 的基礎。這個限制後面將在“加密值乘法”一節中講到。
註解
admin@chaindaily安比實驗室：透過模運算形成的集合被稱為「有限域」，而透過計算指數再進行模運算形成的集合構成「迴圈群」。常見的同態加密方式除了整數冪取模之外，還有橢圓曲線上的倍乘。
加密多項式
配合這些工具，我們現在就可以在加密的隨機數 x 上做運算並相應地修改零知識 協議了。
我們來看一下如何計算多項式 p(x) = x³ – 3x² + 2x。我們前面明確了，知道一個多項式就是知道它的係數，也就是這個例子中知道：1，-3，2。因為同態加密並不允許再對加密值求冪，所以我們必須要給出 x 的 1 到 3 次冪取加密值：E(x)，E(x²)，E(x³)，那麼我們要計算的加密多項式就是：
E(x3)1 · E(x2)-3 · E(x)2 = (gx³)1 · (gx²)-3 ·(gx)2 = g1x³ · (g-3x²)·(gx)2 = g x³-3x²+2x
所以透過這些運算，我們就獲得了多項式在一些未知數 x 處的加密計算結果。這確實是一個很強大的機制，因為同態的性質，同一個多項式的加密運算在加密空間中始終是相同的。
我們現在就可以更新前面版本的協議了，比如對於階數為 d 的多項式：
注意：因為證明者並不知道跟 s 相關的任何資訊，這就使得他很難提出不合法但是能夠匹配驗證的計算結果。
儘管這個協議中 prover 的靈活性有限，他依然可以在實際不使用 verifier 所提供的加密值進行計算，而是透過其它的方式來偽造證明。例如，如果 prover 聲稱有一個滿足條件的多項式它只使用了 2 個求冪值 s3 和 s1，這個在當前協議中是不能驗證的。
註解
admin@chaindaily安比實驗室：利用強同態加密這個工具，構造了一個相對較強的零知識證明協議。但是如上文所述，這裡還是存在一些問題—— 無法驗證 prover 是否是真的使用了 verifier 提供的值來構造證明的。
大家可以思考一下，如何解決這個問題？以及這個協議還存在哪些缺陷呢？
在下一節中，我們將會繼續展開討論，並展示如何構造一個完備的多項式的零知識證明協議。
原文連結
https://arxiv.org/pdf/1906.07221.pdf
https://medium.com/@imolfar/why-and-how-zk-snark-works-1-introduction-the-medium-of-a-proof-d946e931160
https://medium.com/@imolfar/why-and-how-zk-snark-works-2-proving-knowledge-of-a-polynomial-f817760e2805
參考文獻
[Bit+11] — Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge, and Back Again. Cryptology ePrint Archive, Report 2011/443. https://eprint.iacr.org/2011/443. 2011
[Par+13] — Bryan Parno, Craig Gentry, Jon Howell, and Mariana Raykova. Pinocchio: Nearly Practical Verifiable Computation. Cryptology ePrint Archive, Report 2013/279. https://eprint.iacr.org/2013/279. 2013
[Rei16] — Christian Reitwiessner. zkSNARKs in a Nutshell. 2016. url: https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/
[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
[Gab17] — Ariel Gabizon. Explaining SNARKs. 2017. url: https://z.cash/blog/snark-explain/
[Ben+14] — Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. Zerocash: Decentralized Anonymous Payments from Bitcoin. Cryptology ePrint Archive, Report 2014/349. https://eprint.iacr.org/2014/349. 2014
[GMR85] — S Goldwasser, S Micali, and C Rackoff. “The Knowledge Complexity of Interactive Proof-systems”. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing. STOC ’85. Providence, Rhode Island, USA: ACM, 1985, pp. 291–304. isbn: 0–89791–151–2. doi: 10.1145/22145.22178. url: http://doi.acm.org/10.1145/22145.22178
[BFM88] — Manuel Blum, Paul Feldman, and Silvio Micali. “Non-interactive Zero-knowledge and Its Applications”. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. STOC ’88. Chicago, Illinois, USA: ACM, 1988, pp. 103–112. isbn: 0–89791–264–0. doi: 10.1145/62212.62222. url: http://doi.acm.org/10.1145/62212.62222
[Gro10] — Jens Groth. “Short pairing-based non-interactive zero-knowledge arguments”. In: International Conference on the Theory and Application of Cryptology and Information Security. Springer. 2010, pp. 321–340
[Gen+12] — Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic Span Programs and Succinct NIZKs without PCPs. Cryptology ePrint Archive, Report 2012/215. https://eprint.iacr.org/2012/215. 2012
[Pik13] — Scott Pike. Evaluating Polynomial Functions. 2013. url: http://www.mesacc.edu/~scotz47781/mat120/notes/polynomials/evaluating/evaluating.html
[Pik14] — Scott Pike. Dividing by a Polynomial. 2014. url: http://www.mesacc.edu/~scotz47781/mat120/notes/divide_poly/long_division/long_division.html
