免責聲明：本文旨在傳遞更多市場信息，不構成任何投資建議。文章僅代表作者觀點，不代表火星財經官方立場。
小編：記得關注哦
來源：安比實驗室SECBIT
導讀
17 年最早接觸 zk-SNARK 開始，就斷斷續續得學習了一些 zk-SNARK 的知識，但對其原理始終存在諸多困惑，沒有形成一個完整的認識。偶然一次機會，看到了 Maksym Petkus 的這篇文章。文章從最基本的多項式性質講起，從一個簡單易懂的證明協議開始，然後像堆積木一樣在發現問題，修改問題中逐步去完善協議，直到最終構造出完整的 zk-SNARK 協議。另外作者這種從問題出發的講解方式，讓讀者知其然，也知其所以然 。作為一枚畢業多年早把數學知識還給老師的程序媛，讀到這篇文章如獲至寶，這篇文章讀下來的感受像找到了一個腳手架，將腦海裡碎片化的知識逐漸拼湊完整。於是想把它翻譯出來（已獲得作者授權），一方面加深自己的學習，另一方面也將這份寶藏分享給小夥伴們。文章翻譯存在不足之處，歡迎糾正，補充，指導。—— even@安比實驗室
作者：Maksym Petkus翻譯 & 註解：even@安比實驗室（even@secbit.io）校對：valuka@安比實驗室本系列文章已獲作者中文翻譯授權。
Maksym（作者）：
不管是原始的論文[Bit+11]; [Par+13] 還是原理講解 [Rei16]; [But16]; [But17]; [Gab17]，其實市面上已經有大量關於 zk-SNARK 的學習資源了 。zk-SNARK 由大量的可變模塊組成，所以對很多人來說它依然像一個黑盒子一樣很難懂。這些資料對 zk-SNARK 中的一些技術難題部分做出了解釋，但由於缺少了對應的其它環節的解釋，大家還是很難通過這些資料了解到 zk-SNARK 的全貌。
當我第一次了解到 zk-SNARK 技術是如何將這些東西完美地融合在一起的時候，就被數學之美震撼到了，並且隨著我發現的維度越多，好奇心就越強烈。在這篇文章中，我主要就基於一些實例簡潔明了地闡明 zk-SNARK ，並對這裡面的很多問題做出了解釋，並利用這種方式分享了我的經驗，進而讓更多人也能夠欣賞到這項最先進的技術以及它的創新之處，最終欣賞到數學之美。
這篇文章的主要貢獻是比較簡潔明了的解釋了其中相當複雜的技術，這些簡單的解釋對於在不具備任何與之相關的先決知識，比如密碼學和高等數學，的前提下理解 zk-SNARK 是很有必要的。文章中並不僅僅只解釋 zk-SNARK 是如何工作的，還解釋了為什麼這樣就可以工作，以及它是怎麼來的。
序言和介紹
儘管最初計劃寫短一些，但現在已經寫了幾十頁了，不過這篇文章讀起來幾乎不需要什麼預備知識，並且你也可以隨意跳過熟悉的部分。如果你不熟悉文中使用的某些數學符號也不需要擔心，文中將會對這些符號逐個進行介紹。Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARK) 確實是一種非常精妙的方法，它可以在不揭示任何信息的前提下證明某個論斷為真。但首要問題是，它為什麼有用？其實零知識證明在無數的應用中都具備優勢，包括：1）證明關於隱私數據的聲明：
一個人 A 的銀行帳戶金額多於 X去年，一家銀行未與實體 Y 進行交易在不暴露全部 DNA 數據的前提下匹配 DNA一個人的信用評分高於 Z 2）匿名認證：
在不揭露身份的情況下（比如登錄密碼），證明請求者 R 有權訪問網站的受限區域證明一個人來自一組被允許的國家/地區列表中的某個國家/地區，但不暴露具體是哪個證明一個人持有地鐵月票，而不透露卡號3）匿名支付：
付款完全脫離任何一種身份納稅而不透露收入4）外包計算
將昂貴的計算外包，並在不重新執行的情況下驗證結果是否正確；它打開了一種零信任計算的類別改進區塊鏈模型，從所有節點做同樣的計算，到只需一方計算然後其它節點進行驗證和「零知識證明」這個偉大的名詞一樣，其背後的方法可以說是數學和密碼學的奇蹟。自1985 年，零知識證明這個概念在 「交互式證明系統的知識複雜性」[GMR85]一文中被引入，還有隨後的非交互式零知識證明[[BFM88]以來（在區塊鏈環境中尤其重要），至今已經進入到第四個十年的研究。在任意的「零知識證明」系統中，都有一個 prover 在不洩漏任何額外信息的前提下要讓 verifier 確信某些陳述（Statement）是正確的。例如 verifier 僅能知道 prover 的銀行帳戶金額超過 X（也就是不披露實際金額）。協議應當滿足下面三個性質：
完整性 —— 只要「陳述」是正確的，prover 就可以讓 verifier 確信可靠性 —— 如果「陳述」是錯誤的，那麼作弊的 prover 就沒有辦法讓 verifier 相信零知識 —— 協議的交互僅僅揭露「陳述」是否正確而不洩漏任何其它的信息zk-SNARK 這個術語本身是在 [Bit+11] 中引入的，它在[Gro10]的基礎上，又遵循了匹諾曹協議[Gen+12; Par+13] 使其能夠適用於通用的計算。
證明的媒介
這裡我們先不要去管零知識，非交互性，其形式和適用性這些概念，就從嘗試證明一些簡單的東西開始。想像一下我們有一個長度為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 – 5x-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 = 504x – 6x +10x - 5 = 495事實上，在 x 可以選擇的所有值中，至多只有三個值能夠使這些多項式相等，其它的值都是不相等的。這也是為什麼如果一個 prover 聲稱他知道一些 verifier 也知道的多項式（無論多項式的階數有多大）時，他們就可以按照一個簡單的協議去驗證：
verifier 選擇一個隨機值 x 並在本地計算多項式結果verifier 將 x 值給到 prover，並讓他計算相關的多項式結果prover 代入 x 到多項式計算並將結果給到 verifierverifier 檢查本地的計算結果和 prover 的計算結果是否相等，如果相等那就說明 prover 的陳述具有較高的可信度例如，我們把 x 的取值範圍定在 1 到 10, 那麼計算結果不同的點的數量，就有 10 – d 個。因而 x 偶然「撞到」這 d 個結果相同的點中任意一個的概率就等於（可以認為是幾乎不可能）：
@Maksym（作者）
與低效的位檢查協議相比，新的協議只需要一輪驗證就可以讓陳述具有非常高的可信度（假設 d 遠小於 x 取值範圍的上限，就幾乎是 100%了）
這也是為什麼即使可能存在其他的證明媒介，多項式依然是 zk-SNARK 相對核心的部分。
註解
even@安比實驗室：這一節告訴了我們多項式的一個重要性質：我們不可能找到共享連續段的兩條不相等曲線，也就是任何多項式在任意點的計算結果都可以看做是其唯一身份的表示。也就是說只要能證明多項式上的某個隨機點就可以證明這個多項式（只有在知道了多項式，才能算出這個點對於的值），這個性質是我們下面所有證明的核心。這就是 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。我們先來仔細得研究一下這個答案的結構。
註解
even@安比實驗室：這一節告訴了我們多項式的一個本質——多項式的「知識」就是多項式的係數。所謂「知道」多項式就是指「知道」多項式的係數。
因式分解
代數的基本定理表明了任意的一個多項式只要它有解，就可以將它分解成線性多項式（即，一個階數為 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)。
註解
even@安比實驗室：多項式可以被因式分解成它的根的因式的乘積。這個性質就意味著，如果一個多項式有某些解，那麼它被因式分解後的式子中一定包含這些解的因式。有了這個性質，我們就可以愉快地去做一些證明啦。利用多項式一致性檢查協議我們就可以比較多項式 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= th，如果多項式相等，就意味著 t(x) 是 p(x) 的因式。實踐一下，用下面的例子來執行這個協議：
verifier 選一個隨機數 23，並計算 t = t(23) = (23 – 1)(23 – 2) = 462，然後將 23 發給 proverprover 計算 h(x) =p(x) / t(x) = x, 並對 p(r) 和 h(r) 進行求值，p= p(23) = 10626，h= h(23) = 23，將 p 和 h 提供給 verifierverifier 再驗證 p= th：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 = th。因為等式是成立的，所以也能通過 verifier 的校驗。因為 prover 知道隨機點 x = r ，他可以構造出一個任意的多項式，這個任意多項式與 t(r) h(r) 在 r 處有共同點。在前面的「陳述」中，prover 聲稱他知道一個特定階數的多項式，但現在的協議對階數並沒有明確的要求。因而 prover 完全可以拿一個滿足因式校驗的更高階數的多項式來欺騙 verifier。下面我們就要來逐一得解決這些問題。
註解
even@安比實驗室：利用因式的性質構造出了一個證明協議，但這個協議存在一些缺陷，主要是由於
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-355/53 = 55 ·5-3 =5 5-3 = 52 =25不過由於基數 5 是公開的，很容易就可以找到被加密的數字。只要將密文一直除以 5，直到結果為 1，那麼做除法的次數也就是被加密值的數。
模運算
這裡就到了模運算發揮作用的地方了。模運算的思路如下：除了我們所選擇的組成有限集合的前 n 個自然數（即，0，1，…，n-1）以外，任何超出此範圍的給定整數，我們就將它「纏繞」起來。例如，我們選擇前六個數。為了說明這一點，可以把它看做一個有六個單位大小相等刻度的圓；這就是我們所說的範圍（通常指的是有限域）。
現在我們看一下數字八應該在哪裡。打個比方，我們可以把它看成一條長度為 8 的繩子。
如果我們將繩子固定在圓圈的開頭
然後用繩子纏繞圓圈，我們在纏完一圈後還剩下一部分的繩子。
然後我們繼續纏繞，這根繩子將在刻度 2 的地方終止。
這就是模運算操作的結果。無論這根繩子多長，它最終都會在圓圈一個刻度處終止。因而模運算結果將保持在一定範圍內（例子中是 0 到 5）。長度為 15 的繩子將會在刻度 3 的地方終止，即 6 + 6 + 3 （纏 2 個完整的圈並剩下 3 個單位長的部分）。負數運算類似，唯一不同的地方就是它是沿相反方向纏繞的，如 -8 的取模結果是 4。我們執行算術運算，結果都將落在這 n 的範圍內。現在開始我們將用符號 「mod n」 來表示這個範圍內的數。3 × 5 = 3 mod 65 + 2 = 1 mod 6另外，模運算最重要的性質就是運算順序無所謂。例如，我們可以先做完所有的操作，然後再取模，或者每操作完一步都去取模。例如 (2 × 4 – 1) × 3 = 3 (mod 6) 就等於：2 × 4 = 1 mod 62 - 1 = 1 mod 61 × 3 = 3 mod 6那麼模運算到底有什麼用呢？就是如果我們使用模運算，從運算結果再回到原始值並不容易，因為很多不同的組合會產生一個同樣的運算結果：5 × 4 = 2 mod 64 × 2 = 2 mod 62 × 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 的基礎。這個限制後面將在「加密值乘法」一節中講到。
註解
even@安比實驗室：通過模運算形成的集合被稱為「有限域」，而通過計算指數再進行模運算形成的集合構成「循環群」。常見的同態加密方式除了整數冪取模之外，還有橢圓曲線上的倍乘。
加密多項式
配合這些工具，我們現在就可以在加密的隨機數 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 的多項式：
Verifier取一個隨機數 s ，也就是秘密值指數 i 取值為 0，1，…，d 時分別計算出 s 的 i 次冪的加密結果，即：代入 s 計算未加密的目標多項式：t(s)將對 s 的冪的加密值提供給 prover：E(s0)，E(s1)，，E(sd)Prover計算多項式 h(x) = p(x)/t(x)使用加密值 ，，…， 和係數 ，，…， 計算然後同樣計算 E(h(s)) =gh(s)將結果 gp 和 gh 提供給 verifierVerifier最後一步是 verifier 去校驗 p = t(s) ·h: gp = (gh)t(s) => gp = gt(s)·h注意：因為證明者並不知道跟 s 相關的任何信息，這就使得他很難提出不合法但是能夠匹配驗證的計算結果。儘管這個協議中 prover 的靈活性有限，他依然可以在實際不使用 verifier 所提供的加密值進行計算，而是通過其它的方式來偽造證明。例如，如果 prover 聲稱有一個滿足條件的多項式它只使用了 2 個求冪值 s3 和 s1，這個在當前協議中是不能驗證的。
註解
even@安比實驗室：利用強同態加密這個工具，構造了一個相對較強的零知識證明協議。但是如上文所述，這裡還是存在一些問題—— 無法驗證 prover 是否是真的使用了 verifier 提供的值來構造證明的。大家可以思考一下，如何解決這個問題？以及這個協議還存在哪些缺陷呢？在下一節中，我們將會繼續展開討論，並展示如何構造一個完備的多項式的零知識證明協議。
原文連結
https://arxiv.org/pdf/1906.07221.pdfhttps://medium.com/@imolfar/why-and-how-zk-snark-works-1-introduction-the-medium-of-a-proof-d946e931160https://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