雷鋒網按：原文標題為《zkSNARKs in a nutshell》，作者是以太坊智能合約語言Solidity的發明人Christian Reitwiessner。譯者楊文濤，授權轉載自作者知乎專欄。
摘要：
zkSNARKs（zero-knowledge succint non-interactive arguments of knowledge）的成功實現讓我們印象深刻，因為你可以在不執行，甚至在不知道執行具體內容的情況下確定某個計算的結果是否正確——而你唯一知道的信息就是它正確地完成了。但是不幸的是，大多數關於 zkSNARKs 的解釋都浮於表面，並暗示只有最聰明的人才能懂得它的工作原理。實際上，zkSNARKs 可以總結為 4 個簡單的技術，本篇博客將會逐一解釋這些技術。任何懂得 RSA 加密系統工作原理的人都會對當前使用的 zkSNARKs 有一個更好的理解和認識。
我們當前使用的 zkSNARKs 包含 4 個主要部分：
A) 編碼成一個多項式問題（Polynomial problem）
把需要驗證的程序編寫成一個二次的多項式方程：t(x) h(x) = w(x) v(x)，若且唯若程序的計算結果正確時這個等式才成立。證明者需要說服驗證者這個等式成立。
B) 簡單隨機抽樣
驗證者會選擇一個私密評估點 s 來將多項式乘法和驗證多項式函數相等的問題簡化成簡單乘法和驗證等式 t(s)h(s) = w(s)v(s) 的問題。這樣做不但可以減小證明的大小，還可以大量地減少驗證所需的時間。
C) 同態編碼 / 加密（Homomorphic encoding / encryption）
譯者註：在1978年，Ron Rivest，Leonard Adleman，以及 Michael L. Dertouzos 就以銀行為應用背景提出了同態加密的概念，當時使用的單詞是 homomorphism，也就是和抽象代數的同態是一個單詞。現在一般都使用 homomorphic encryption，國內密碼學圈子基本也都稱作同態加密。Ron Rivest 和 Leonard Adleman 分別就是著名的RSA算法中的 R 和 A（還有一位是 Adi Shamir）。
補充（來自白老師）：同胚和同態在數學上不是一個意思。同胚指連續變形下的不變性，同態指映射下代數運算關係的保持性。
我們使用一個擁有一些同態屬性的（並不是完全同態的，至少在實際使用中有一些不是同態的）編碼 / 加密函數 E。這個函數允許證明者在不知道 s 的情況下計算 E(t(s)), E(h(s)), E(w(s)), E(v(s))，她只知道 E(s) 和一些其他有用的加密信息。
D) 零知識（Zero Knowledge）
證明者通過乘以一個數來替換 E(t(s)), E(h(s)), E(w(s)), E(v(s)) 的值，這樣驗證者就可以在不知道真實的編碼值的情況下驗證他們正確的結構了。
困難的問題在於對一個隨機的私密數 k（k 不等於 0）來說，校驗 t(s)h(s) = w(s)v(s) 和校驗 t(s)h(s) k = w(s)v(s) 幾乎是完全一樣的，而不同點則是如果你只接收到了 (t(s)h(s) k) 和 w(s)v(s) 那麼從中獲取到 t(s)h(s) 或者 w(s)v(s) 的值就幾乎不可能了。
當然，這些都只是基礎的部分，是為了讓讀者更地的理解 zkSNARKs 的本質，接下來將開始詳細講解這些知識點。
RSA 和 零知識證明
現在讓我們快速回想一下 RSA 是如何工作的，先不管那些瑣碎的細節。想想看，我們經常用一個數字對一些數字取模，而並不是所有的整數。這裡的等式 「a + b ≡ c (mod n)」 等價於 「(a + b) % n = c % n」。注意，「(mod n)」 這個部分並不是應用在 「c」 上面的，而是應用在 「≡」 以及相同等式所以其他的 「≡」 上面。雖然這樣非常難以閱讀，但是我保證儘量少用他們。接著讓我們回到 RSA：
證明者提供了下面的數字：
p，q：兩個隨機的私密素數
n := p q
d：1 < d < n – 1 的隨機數
e：d e ≡ 1 (mod (p-1)(q-1))
公鑰是 (e, n)，私鑰是 d。素數 p 和 q 可以丟棄，但是不能暴露。
消息 m 通過下面的公式加密：
c = E(m) 通過下面的公式解密：
因為 ，並且 m 的指數就是對 (p-1)(q-1) 這一組數取模，這樣我們就得到了（譯者註：可以由費馬小定理和中國剩餘定理推出）。而且 RSA 的安全性是基於假設：n 不能被輕易有效的因式分解，d 不能通過 e 計算得到（如果我們知道 p 和 q 的話，就可以輕易得到我們想要的值）。
RSA 的一個牛逼的特性是同態乘法。通常來講，如果你可以交換兩個操作的順序而不影響計算結果，那麼我們就說這兩個操作是同態的。在同態加密中，這就是你可以對加密數據進行計算的一個屬性。完全同態加密是存在的，但是現在還沒有應用到實際中，它能夠對任何基於加密數據的程序完成計算。在這裡對於 RSA 來說，我們只談論 group multiplication。更準確的說就是：，用文字描述就是：兩個加密信息的乘積等於兩個信息乘積的加密。
這個同態的特性已經有一些乘法的零知識證明了：證明者知道一些私密的數字 x 和 y，並計算出了它們的乘積，但是只給驗證者發送加密的版本：a = E(x), b = E(y) 以及 c = E(x y)。驗證者檢驗等式 (a b) % n ≡ c % n 是否成立，此時驗證者只知道加密版的乘積以及乘積是否被正確的計算，但是她不知道兩個乘數和真正的乘積。如果你用加法來替代乘法，那就是一個主要操作為添加餘額的區塊鏈方向了。
交互式驗證
我們已經對零知識這個概念有了一定的了解了，現在讓我們著重看一下 zkSNARKs 的另一個主要的特性：簡明性（succinctness）。之後你會看到這個簡明性是 zkSNARKs 更牛逼的部分，因為零知識部分的實現就是因為這一特定編碼，而這個特定的編碼是一個有限形式的同態編碼。
SNARKs 是 succinct non-interactive arguments of knowledge 的縮寫。一般都通用設置之所以叫做交互式協議，是因為這裡有一個證明者和一個驗證者，證明者想要通過交換信息的方式讓驗證者相信一個表達式（比如 f(x) = y）。一般來說，沒有證明者可以讓驗證者相信一個錯誤的表達式（可靠性），而且對於證明者來說一定存在一個確定的策略讓驗證者相信任何真實的表達式（完整性）。SNARKs 各個部分的的意義如下：
Succinct：比起真正需要計算的長度來說，我們發送的信息大小是很小的。
Non-interactive：沒有或者只有很少很少的交互。對於 zkSNARKs 來說就是在證明者向驗證者發送一條信息之後的過程。此外，SNARKs 還常常擁有叫做『公共驗證者』的屬性，它的意思是在沒有再次交互的情況下任何人都可以驗證，這對於區塊鏈來說是至關重要的。
Arguments：驗證者只對計算能力有限的證明者有效。擁有足夠計算能力的證明者可以創造出關於錯誤表達式的（注意，只要擁有足夠的計算能力，任何公鑰加密系統都可以被破解）證明和參數。這也叫做『計算可靠性』，相對的還有『完美可靠性』。
of Knowledge：對於證明者來說在不知道一個叫做證據（witness）（比如一個哈希函數的原象或者一個確定 Merkle-tree 節點的路徑）的情況下，構造出一組參數和證明是不可能的。
如果你添加了零知識的前綴，那麼在交互中你就需要一個性質，即驗證者除了知道表達式的正確與否之外其他一無所知。尤其是驗證者不能知道 witness string ——稍後我們會詳細解釋這是什麼。
關於零知識的部分相對正式的定義（仍然缺乏一些細節）就是：存在一個模擬器，它可以生成一些設置欄位，但是卻不知道私密的 witness，它還可以和驗證者交互 -- 但是外部的觀察者卻不能分辨出哪個與驗證者進行的交互，哪個是與證明者進行的交互。
NP 和 簡化的複雜性理論
為了了解 zkSNARKs 能用於哪些問題和計算，我們不得不基於複雜的理論定義一些說法。如果你不知道什麼是 「witness」 的話，那麼即使『讀』完零知識證明你也不會知道它是什麼，並且你也不會了解到為什麼 zkSNARKs 只適用於特定的多項式問題，如果真是這樣的話，那麼你就可以跳過本節了。
P 和 NP
首先，我們限制函數只能輸出 0 和 1，並稱這樣的函數為問題（problems）。因為你可以單獨的查詢一個長長的結果的每一位（bit），所以這不是一個真正的限制，但是這樣可以讓定理變的簡單一點。現在我們想衡量解決一個給定的問題（計算函數）到底有多『難』。對於一個數學函數 f 的特定機器的實現 M，給定一個輸入 x，我們可以計算出這個函數 f 需要的步數 -- 這就叫做 x 在 M 上的執行時間，這裡的『步數』其實不太重要。因為程序對於更大的輸入往往會需要更多的步數，而這個執行時間則是用輸入值的大小或者說長度（bit 的數量）來衡量。這就是例如『 算法』的來源 -- 這就是一個當輸入值大小為 n 時，至多需要 個步數的算法。這裡的『程序』和『算法』廣義上是相同的。
執行時間至多為 的程序也叫做 「polynomial-time programs」（多項式時間問題）。
在複雜性理論中有兩個主要的類別，他們就是 P 問題和 NP 問題：
P 問題是具有多項式時間的一類問題
雖然 k 的指數對於一些問題來說確實非常大，但是實際上對於那些非人造的，k 不大於 4 的 P 問題仍然被認為是可以『解決的』的問題。要確認一筆比特幣的交易就是一個 P 問題，因為經過評估它需要一個多項式時間（並且只能輸出 0 和 1）。簡單的說就是，如果你只是計算一些值而不去『搜索』，那麼這個問題就是 P 問題。但是如果你不得不搜索一些東西，那麼你就會進入到另一個叫做 NP 問題的類別中。
NP 類問題
幾乎所有的 NP 類問題都是 zkSNARKs，今天在實際中使用的 zkSNARKs 在通常意義上講都屬於 NP 問題。而我們目前還不知道的是，有沒有不屬於 NP 問題的 zkSNARKs 存在。
所有的 NP 問題都有一個特定的結構，這個特定的結構來自於 NP 問題的定義：
NP 問題是 L（含有多項式時間的程序 V）的一類問題， 這個程序 V 可以在給定一個多項式尺度的叫做因子的 witness 的情況下驗證這個因子。更正式的說就是：若且唯若一些多項式尺度的字符串 w（被稱作 witness）滿足 V(x, w) = 1 時，L(x) = 1 成立。
P = NP ?
如果你將 NP 問題定義為長度為 0 的 witness strings，那麼你會發現這就是 P 問題。因此 每個 P 問題其實都是 NP 問題。在複雜性理論研究中有一個主要的任務就是發掘出這兩類問題的不同 -- 即一個不屬於 P 的 NP 問題。在這裡似乎是很顯然的，但是如果你可以再一般情況下證明它，那麼你可以獲得 1 百萬美元。額外說一句，如果你可以反向證明，即 P 和 NP 是等價的，也可以獲得那筆獎金。而數字貨幣領域有朝一日能夠證明的概率很大。我這麼說的原因是，比起一個哈希函數的碰撞或者根據地址找到私鑰來說，找到一個工作難題解決辦法的證明顯然更容易一點。這些都是 NP 問題，因為你剛已經證明了 P = NP，那麼對於這些 NP 問題來說就一定存在一個多項式時間的程序。但是本文就不討論了，雖然大部分研究者都認為 P 問題和 NP 問題並不是等價的。
NP 完全問題
讓我們再回到 SAT。這個看起來簡單的問題有個有趣的特性就是它並不僅是 NP 問題，還是 NP 完全問題。『完全』這個詞在這裡和『圖靈完備』是一個意思。這意味著它是 NP 中最難的問題，但是更重要的是 NP 完全的定義——任何 NP 問題的輸入都可以用下面的方法轉換成一個同樣的 SAT 的輸入：
所有 NP 問題 L 都有一個在多項式時間可計算的『還原函數（reduction function）』f：
L(x) = SAT(f(x))
這樣的一個還原函數不能被看成一個編譯器：編譯器是可以將一些程式語言寫的原始碼等價的轉換成另一種程式語言的機器，也就是擁有語義行為的機器語言。因為 SAT 是 NP 完全的，所以這樣一個還原對於任何可能的 NP 問題都是存在的，比如給定一個合適的 block hash，驗證一筆比特幣交易是否合法。這裡還可以將一筆交易轉換成一個布爾函數的還原函數，因此若且唯若這個交易是合法的時候這個布爾函數就是可滿足的。
還原示例
為了弄明白這樣一個還原的方法，讓我們先考慮評估多項式的問題。首先，讓我們定義一個由整數常量，變量，加法，減法，乘法和（正確匹配的）括號構成的多項式（類似於布爾函數）。現在讓我們考慮下面的問題：
如果 f 是一個變量都來自於集合 {0, 1} 的多項式，並且其中包含一個零項，那麼 PolyZero(f) := 1
現在我們就可以構建出一個從 SAT 到 PolyZero 的還原方法了，同時這也說明了 PolyZero 也是一個 NP 完全問題（驗證它是否屬於 NP 就當是留給你們的小練習啦）。
有些人可能會假設將 r((f ∧ g)) 定義為 r(f) + r(g)，但是那樣的話多項式的結果就會超出集合 {0, 1} 了。
使用函數 r，((x ∧ y) ∨x) 被轉換成了 (1 – (1 – (1 – x))(1 – (1 – y))(1 – (1 – x))。
注意，對於 r 來說，每一個替換規則都滿足了之前聲明的目的，因此 r 也正確的實現了還原：
若且唯若 r(f) 含有集合 {0, 1} 中的一個 0 時，SAT(f) = PolyZero(r(f)) 或者說 f 是可滿足的
Witness preserving
從這個例子中你可以看出還原函數隻定義了如何轉換輸入，但是當你仔細看的時候（或者閱讀完如何完成一個可用的還原證據之後）你就會知道如何將一個可用 witness 和 輸入一起轉換。在我們的例子中，我們只定義了如何將函數轉換為多項式，但是不知道如何將我們解釋的證據轉換成滿足賦值的 witness。這個 witness 在同一時間轉換對於交易來說不是必要的，但是通常都會包含。而這對於 zkSNARKs 來說是至關重要的，因為對於證明者來說他唯一的任務就是讓驗證者相信有這樣一個 witness 存在，並且還不會暴露任何有關 witness 的信息。
Quadratic Span Programs
在上一部分中，我們看到了 NP 問題的計算是如何被相互化簡的，尤其是那些 NP 完全問題，那些 NP 完全問題基本上又都再次形成了其他的 NP 問題——包括交易驗證問題。那麼對我們來說找到一個對所有 NP 問題都通用的 zkSNARKs 就變的很容易了：我們只需要選擇適合的 NP 完全問題。所以如果我們想展示如何使用 zkSNARKs 來驗證交易的話，那麼展示如何處理這個確定的 NP 完全問題就是一個有效的方法，並且比從理論上解釋更容易讓人接受。
接下來就是基於論文GGPR12（這裡面連結的技術報告比原文的乾貨更多）來談了，這篇論文的作者發現了一個叫做 Quadratic Span Programs（QSP）的問題，這個問題完全就是為 zkSNARKs 準備的。一個 Quadratic Span Program 是由一組多項式和尋找給定多項式倍數的線性組合任務構成。此外，輸入字符串的每個單獨的 bit 都限制了你能夠使用的多項式。詳細來說（通常來講 GSPs 限制不是那麼嚴格，但是我們就是需要這種強限制的版本，因為後面我們會用到）就是：
對於輸入長度為 n 的在域 F 上的 QSP 問題由下面這些部分構成：
這裡的任務很粗糙，就是給多項式乘以一個因子並把它們加起來（也叫做『線性組合』）使得它們的總和是 t 的倍數。對於每一個二進位輸入字符串 u 來說，函數 f 限制了可以被使用的多項式，或者更嚴格的講就是它們必須是線性組合的因子。正式的表示就是：
注意，在這裡當 2n 小於 m 時，選擇元組 a 和 b 仍然是有很大的自由度的。這就意味著 QSP 只對特定大小的輸入是有價值的——這個問題可以通過使用非均勻複雜度來解決，非均勻複雜度這個話題今天我們不會深入的講解，我們只需要知道當輸入值很小時，我們的密碼學也能良好運轉。
這裡我們不會討論如何將通用計算和線路問題簡化成 QSP 問題，因為這對於我們了解基本概念沒有任何幫助，我們只需要知道 QSP 是 NP 完全（或者說比一些非均勻分布的像 NP/poly 問題更完全）的就好了。實際上，這個簡化是一個『工程』部分——必須要使用一種很聰明的方法才能讓 QSP 問題儘可能的小並且有一些其他的優良特性。
zkSNARK 詳解
現在讓我們來詳細的描述一下 QSP 上的 zkSNARK。它在開始設置階段會執行每一個單獨的 QSP。在 zCash 中，交易驗證者的線路是固定的，因此 QSP 的多項式也是固定的，這個 QSP 在設置階段只允許被執行一次，然後在所有的只有輸入 u 不同的交易上復用。這個開始的設置會生成一個公共參考串（common reference string，CRS），驗證者選擇一個隨機且私密的域元素，並在這個點加密多項式的值。驗證者使用一些特定的加密方法 E 並在 CRS 中
如何使用零知識來簡單估計一個多項式
首先讓我們先來看一種簡單的情況，即一個多項式在私密點上的加密估值，而不是完整的 QSP 問題。
這裡的這個示例告訴我們驗證者並不需要求出完整的多項式來證明這一點，僅僅使用配對函數就可以了。下一步我們就要添加零知識的部分了，這樣驗證者就不能構建任何關於 f(s) 值了，甚至連 E(f(s)) 這種加密信息也不行。
好的，現在我們總算知道了一點關於在驗證者不知道那個值的情況下，證明者是如何在一個加密的私密點上面計算出多項式加密值的。接下來讓我們把這些應用到 QSP 問題中吧。
QSP 問題的 SNARK
最後一個等式用來檢驗是否使用了正確的多項式（這一部分還沒有講到，不過其他的例子會說到它）。要注意的是，我們所有的加密值，證明者只需要知道 CRS 就可以全部推算出來。
而驗證者現在要做的還有這些：
假設證明者提供了一個正確的證明，讓我們檢驗一下等式是否滿足。左邊和右邊的部分分別是：
添加零知識
在輸入和 Witness 大小之間取一個折中的值
就像你在上面這些小節中看到的一樣，我們的證明由一個群（就是一個橢圓曲線）的 7 個元素組成。而且驗證者的工作就是檢驗一些配對函數的等式是否成立以及計算 這樣一個跟隨輸入大小的線性任務。最主要的是，在這個驗證過程中，既不需要 witness 字符串的大小，又不需要計算工作量來驗證 QSP（沒有 SNARKs）。這就意味著 SNARKs 的校驗是個很複雜的問題，而簡單的問題往往都是一樣的。造成這個結果的主要原因則是，因為我們只在一個單獨的點上面檢驗了多項式的一致性，而不是全部的點。多項式可以變的非常非常複雜，但是一個點始終是一個點。而唯一能影響到驗證結果的參數就是安全性的等級（比如群的大小）和輸入值的最大尺寸。
減小第二個參數是可行的，將輸入值的一部分移動到 witness 中：我們不驗證函數 f(u, w)，u 是輸入，w 是 witness，而是做一次 hash，然後驗證：
這樣就意味著我們可以用一個 hash 來代表輸入 h(u) 了（這樣就會變的更短），除了驗證 f(x, w)，我們還需要驗證某個值 x 的 hash 等於 H(u)（這樣的話，那 x 極有可能就等於 u 了）。這樣就將原始輸入 u 移動到 witness 字符串中了，這樣雖然會增大 witness 的大小，但是輸入值的大小就減小為一個常數了。
這簡直太厲害了，因為這意味著我們可以在常數時間內完成對任何複雜表達式的檢驗。
zkSNARKs 和 Ethereum 關係緊密
因為驗證計算是 Ethereum 區塊鏈的核心，所以 zkSNARKs 和 Ethereum 關係緊密相連。有了 zkSNARKs，我們不但可以完成任何人都可證實的私密的計算，而且還可以高效的完成。
雖然 Ethereum 使用了一個圖靈完備的虛擬機，但是當前在 Ethereum 上實現一個 zkSNARK 還是不可能的。從概念上講，驗證者的任務似乎很簡單，但是配對函數是真的很難計算，而且在單個區塊中還會消耗更多的 gas。橢圓曲線的乘法相對來講已經非常複雜了，而配對函數將這個複雜度又增加了一個級別。
像 zCash 這種現存的 zkSNARK 系統對每一個任務都使用的是同樣的問題，circuit 計算。在 zCash 中，就是交易驗證。在 Ethereum 上，zkSNARKs 將不會只單單做一個計算問題，而是讓所有的人都能夠在不發布一個新的區塊鏈的情況下構建他們自己的 zkSNARK 系統。每一個添加到 Ethereum 上的 zkSNARK 系統都需要進行一個新的私密的可信任的準備階段（一些可以復用，一些不能），比如生成一個新的 CRS。像為一個『通用虛擬機』添加 zkSNARK 系統將會變的可能。這樣的話當你使用一個新的實例時，你就不需要重新設置了，因為你將不再需要為 Ethereum 上新的智能合約發布一個新的區塊鏈。
如何在Ethereum 上啟用 zkSNARKs
在 Ethereum 上啟用 zkSNARKs 有很多種方式。所有的方式都可以為配對函數和橢圓曲線操作（其他必要的操作都很簡單）減小真實的損耗，因此我們也要減小這些操作消耗的 gas。
提升（確保）EVM 的性能
只在確定的配對函數和橢圓曲線乘法上提升 EVM 的性能
第一項在長期顯然會得到很好的回報，但是實現起來難度比較大。我們現在已經在對 EVM 添加一些新的功能和限制了，例如更好的支持及時編譯以及在現存實現下最小改動的解釋器的實現。當然也不排除直接用 eWASM 來替換 EVM。
第二項則可以通過強制所有的 Ethereum 客戶端執行一個確定的配對函數和確定的橢圓曲線乘法的叫做預編譯合約的東西來實現。這樣做的好處就是實現起來既簡單又快速。而缺點呢則是這樣做我們就會固定在一個確定的的配對函數和一個確定的橢圓曲線上。所有 Ethereum 上新的客戶端都不得不再實現一遍這個預編譯合約。所有，如果有什麼新的進展，或者有人可以找到更好的 zkSNARKs 的方法，更好的配對函數，更好的橢圓曲線，又或者發現了橢圓曲線，配對函數和 zkSNARK 的一些缺點，那麼我們就會添加到新的預編譯合約中。