學術向 | 深入淺出zkSNARKs
zkSNARKs的成功性令人印象深刻，因為你可以在不執行，甚至不知道執行的具體內容是什麼的情況下確定某個計算的結果是否正確 -- 而你唯一知道的資訊就是它正確的完成了。不幸的是，zkSNARKs的大多數解釋在某些時候都只是表面的，而且他們往往會留下一些“神奇的”東西，這表明只有最聰明的人才能理解他們的工作方式和原因。現實情況是，zkSNARKs可以簡化為四種簡單的技術，這篇博文旨在解釋它們。任何能夠理解RSA密碼系統如何工作的人，也應該對當前使用的zkSNARKs有很好的理解。讓我們拭目以待！
作為一個非常簡短的總結，當前使用的zkSNARKs有4個主要成分（不用擔心，我們將在後面的章節中解釋所有術語）：
A）編碼為多項式問題
將需要檢查的程式被編譯成多項式的二次方程：t（x）h（x）= w（x）v（x），其中當且僅當程式被正確計算時，等式成立。證明者想要說服驗證者這個等式成立。
B）簡單隨機抽樣
驗證者會選擇一個私密評估點 s 來將多項式乘法和驗證多項式函式相等的問題簡化成簡單乘法和驗證等式 t(s)h(s)= w(s)v(s) 的問題。 這極大地減少了證明大小和驗證時間。
C）同態編碼/加密
使用具有一些同態屬性的編碼/加密函式E（但不是完全同態的，這是不可行的）。這允許證明者在不知道s的情況下計算E（t（s）），E（h（s）），E（w（s）），E（v（s）），她只知道E（s）和一些其他有用的加密值。
D）零知識
證明者通過乘以一個數字來置換值E（t（s）），E（h（s）），E（w（s）），E（v（s）），以便驗證者再不知道實際的編碼值仍然可以檢查它們的正確性結構。
有一個粗糙的想法是這樣的，因為校驗 t(s)h(s) = w(s)v(s) 和校驗 t(s)h(s) k =w(s)v(s) k（對於一個不等於 0 的私密的隨機數 k 來說）幾乎是完全一樣的，而不同的地方在於如果你只接收到了 (t(s)h(s) k) 和 (w(s)v(s) k) 那麼從中獲取到 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 qd：1 < d < n – 1 的隨機數e：d e ≡ 1 (mod (p-1)(q-1)) 公鑰是 (e,n)，私鑰是 d。素數 p 和 q 可以丟棄，但是不能暴露。
訊息m通過下面公式加密
E（m）：= m e％n 並且c = E（m）通過解密
D（c）：= c d％n。 因為cd≡（me％N）d≡med（mod n），m的指數就是對（P-1）（Q-1）這組數取模，我們得到med ≡m（mod n）。此外，RSA的安全性依賴於這樣的假設：n不能輕易被因式分解，因此d不能從e計算（如果我們知道p和q，這將是容易的）。
RSA 的一個牛逼的特性是同態乘法。通常來講，如果你可以交換兩個操作的順序而不影響計算結果，那麼我們就說這兩個操作是同態的。在同態加密中，這就是你可以對加密資料進行計算的一個屬性。完全同態加密是存在的，但是現在還沒有應用到實際中，它能夠對任何基於加密資料的程式完成計算。在這裡對於 RSA 來說，我們只討論組乘法。更正式地：E（x）E（y）≡xe y e ≡（xy）e≡E（xy）（mod n），文字描述就是：兩個加密訊息的的乘積等於兩個資訊乘機的加密。
這種同態性已經允許某種零知識的乘法證明：證明者知道一些祕密數字x和y並計算它們的乘積，但只發送加密版本a= E（x），b = E（y）和c = E（xy）到驗證者。驗證者現在檢查（ab）％n≡c％n 是否成立，此時驗證者只知道加密版的乘積以及乘積是否被正確的計算，但是她不知道兩個乘數和真正的乘積。如果你用加法來替代乘法，那就是一個主要操作為新增餘額的區塊鏈方向了。
互動驗證
我們已經對零知識這個概念有了一定的瞭解了，讓我們現在關注zkSNARKs的另一個主要特徵，即簡潔性。正如您稍後將看到的，簡潔性是zkSNARKs中更為顯著的部分，因為由於某種編碼允許有限形式的同態編碼，零知識部分將“免費”給出。
SNARKs 是 succinct non-interactive arguments of knowledge 的縮寫。一般都通用設定之所以叫做互動式協議，是因為這裡有一個證明者和一個驗證者，證明者想要通過交換資訊的方式讓驗證者相信一個表示式（比如 f(x) = y）。一般來說，沒有證明者可以讓驗證者相信一個錯誤的表示式（可靠性），而且對於證明者來說一定存在一個確定的策略讓驗證者相信任何真實的表示式（完整性）。SNARKs 各個部分的的意義如下：
簡潔：與實際計算的長度相比，訊息的大小很小 非互動式：沒有或者只有很少很少的互動。對於 zkSNARKs 來說就是在證明者向驗證者傳送一條資訊之後的過程。此外，SNARKs 還常常擁有叫做『公共驗證者』的屬性，它的意思是在沒有再次互動的情況下任何人都可以驗證，這對於區塊鏈來說是至關重要的。 引數：驗證者僅受到計算限制的證明者的保護。具有足夠計算能力的證明器可以建立關於錯誤語句的證明/引數（注意，如果具有足夠的計算能力，則可以破壞任何公鑰加密）。這也稱為“計算可靠性”，而不是“完美可靠性”。 知識：對於證明者來說在不知道一個叫做證據（witness）（比如一個雜湊函式的原象或者一個確定 Merkle-tree 節點的路徑）的情況下，構造出一組引數和證明是不可能的。
如果你添加了零知識的字首，那麼在互動中你就需要一個性質，即驗證者除了知道表示式的正確與否之外其他一無所知。尤其是驗證者不能知道 見證字串 稍後我們會詳細解釋這是什麼。
舉個例子，讓我們考慮下面的交易驗證計算：當且僅當 σ 1 和σ2 是賬戶默克樹s（pre 和 post 狀態）的根雜湊，s 和 r 是傳送者和接收者賬戶， PS和PR 是默克樹 的證明（當 v 從 s 的餘額中轉移到 r 的餘額的過程中，能夠證明在 中 s 的餘額至少是 v 並且他們的雜湊結果是 而不是 ），這些條件都成立時，f（σ1，σ2，s ,r,v,ps,pr,v) 成立。
如果所有輸入都已知，則驗證f的計算相對容易。正因為如此，我們可以將F轉換成一個zkSNARK，其中只有σ 1和σ 2是公開的和（s ,r,v,ps,pr,v）是witmess-string。零知識屬性現在會使得驗證者能夠檢查證明方是否知道一些見證，它可以將根雜湊從σ 1轉換至σ 2，而這樣的轉換又不影響正常的交易，但是驗證者卻不知道到底是誰傳送了多少錢給誰。
關於零知識的部分相對正式的定義（仍然缺乏一些細節）就是：存在一個模擬器，它可以生成一些設定欄位，但是卻不知道私密的證人，它還可以和驗證者互動 -- 但是外部的觀察者卻不能分辨出哪個與驗證者進行的互動，哪個是與證明者進行的互動。
為了瞭解zkSNARKs可以用於哪些問題和計算，我們必須從複雜性理論中定義一些概念。如果你不關心“見證”是什麼，那麼即使在“閱讀”零知識證明之後你也不會知道他是什麼，並且你也不會了解到為什麼 zkSNARKs 只適用於特定的多項式問題，如果真是這樣的話，那麼你就可以跳過本節了。
p和NP
首先，我們限制函式只能輸出 0 和 1，並稱這樣的函式為問題。因為您可以單獨查詢較長結果的每個位，所以這不是一個真正的限制，但它可以使理論更容易。現在我們要測量解決給定問題（計算函式）的“複雜程度”。對於數學函式f的特定機器實現M，我們總是可以計算在特定輸入x上計算f所需的步數 - 這稱為x在M上的執行時間。究竟什麼是“步驟”，在這種情況下並不太重要。由於程式對於更大的輸入旺旺需要更多的步數，而執行時間以輸入的大小或長度（位數）來衡量的。這就是例如”n2 演算法”的來源 -- 這就是一個當輸入值大小為 n 時，至多需要n2 個步數的演算法。這裡的”程式”和”演算法”廣義上是相同的。
對於某些k，其執行時間最多為n k的程式也稱為“多項式時間程式”。
複雜性理論中的兩個主要問題型別是P和NP：
P是具有多項式時間程式的一類問題類 雖然 k 的指數對於一些問題來說確實非常大，但是實際上對於那些非人造的，k 不大於 4 的 P 問題仍然被認為是可以“解決的”的問題。要確認一筆比特幣的交易就是一個 P 問題，因為經過評估它需要一個多項式時間（並且只能輸出 0 和 1）。簡單的說就是，如果你只是計算一些值而不去“搜尋”，那麼這個問題就是 P 問題。但是如果你不得不搜尋一些東西，那麼你就會進入到另一個叫做 NP 問題的類別中。
NP類問題
對於NP類中的所有問題都是zkSNARK，實際上，現在存在的實際使用的zkSNARKs通常意義上都是NP問題。目前尚不清楚有沒有不屬於 NP 問題的 zkSNARKs 存在。
NP中的所有問題總是具有一定的結構，這源於NP的定義： NP 問題是 L（含有多項式時間的程式 V）的一類問題， 這個程式 V 可以在給定一個多項式尺度的叫做因子的 witness 的情況下驗證這個因子。更正式的說就是： 當且僅當一些多項式尺度的字串 w（被稱作 witness）滿足 V(x, w) = 1 時，L(x) = 1 成立。 作為NP中問題的一個例子，讓我們考慮布林公式可滿足性（SAT）的問題。為此，我們使用歸納定義定義布林函式：
任何變數x 1，x 2，x 3，...都是布林函式（我們還使用任何其他字元來表示變數 如果f是布林函式，則¬f是布林函式（否命題） 如果f和g是布林函式，那麼（f∧g）和（f∨g）也是布林函式（∧是且，∨是或）。 字串“（（X 1 ∧X 2）∧¬x 2）”也是一個布林函式。
如果有一種方法可以將真值賦給變數，那麼布林函式是可以滿足的，這樣公式的計算結果為真（其中σ為真，¬false為真，true∧false為假，依此類推）。可滿足性問題SAT是所有可滿足的布林函式的集合。
當且僅當 f 是一個可滿足函式且不是 0 時，SAT(f) := 1 成立 上面的例子中，“（（X 1 ∧X 2）∧¬x 2）”，是不符合要求的，因此它不屬於SAT。證明一個給定公式滿足定義並且同時確保它賦值的變數也是可滿足的就是一個可以在多項式時間內被解決的問題。
P=NP?
如果你將 NP 問題定義為長度為 0 的 見證字串，那麼你會發現這就是 P 問題。因此 每個 P 問題其實都是 NP 問題。在複雜性理論研究中有一個主要的任務就是發掘出這兩類問題的不同 -- 即一個不屬於 P 的 NP 問題。在這裡似乎是很顯然的，但是如果你可以再一般情況下證明它，那麼你可以獲得 1 百萬美元。額外說一句，如果你可以反向證明，即 P 和 NP 是等價的，也可以獲得那筆獎金。而數字貨幣領域有朝一日能夠證明的概率很大。我這麼說的原因是，比起一個雜湊函式的碰撞或者根據地址找到私鑰來說，找到一個工作難題解決辦法的證明顯然更容易一點。這些都是 NP 問題，因為你剛已經證明了 P = NP，那麼對於這些 NP 問題來說就一定存在一個多項式時間的程式。但是本文就不討論了，雖然大部分研究者都認為 P 問題和 NP 問題並不是等價的。
NP完全性
讓我們回到SAT。這個看似簡單的問題的有趣特性是它不僅存在於NP中，而且還是NP完全問題。這裡的“完整”一詞與“圖靈完整”中的完整相同。這意味著它是NP中最難的問題之一，但更重要的是這就是NP完全的定義 - NP中任何問題的輸入都可以轉換為SAT的等效輸入，具體如下： 所有 NP 問題 L 都有一個在多項式時間可計算的”還原函式”f： L（x）= SAT（f（x）） 這樣的一個還原函式不能被看成一個編譯器：編譯器是可以將一些程式語言寫的原始碼等價的轉換成另一種程式語言的機器，也就是擁有語義行為的機器語言。因為 SAT 是 NP 完全的，所以這樣一個還原對於任何可能的 NP 問題都是存在的，比如給定一個合適的塊雜湊，驗證一筆比特幣交易是否合法。這裡還可以將一筆交易轉換成一個布林函式的還原函式，因此當且僅當這個交易是合法的時候這個布林函式就是可滿足的。
還原示例
為了弄明白這樣一個還原的方法，讓我們先考慮評估多項式的問題。首先，讓我們定義一個由整數常量，變數，加法，減法，乘法和（正確匹配的）括號構成的多項式（類似於布林函式）。現在讓我們考慮下面的問題： 如果 f 是一個變數都來自於集合 {0, 1} 的多項式，並且其中包含一個零項，那麼 PolyZero(f) := 1 現在我們就可以構建出一個從 SAT 到 PolyZero 的還原方法了，同時這也說明了 PolyZero 也是一個 NP 完全問題（驗證它是否屬於 NP 就作為留給你們的練習）。
在一個布林函式的結構要素上是可以定義一個還原函式 r 的。對於任何布林函式 f，r(f)的值擁有相同的變數個數，並且當且僅當 r（f）（a 1，..，a k）為0時f（a 1，..，a k）為真，其中true對應於1，false對應於0，並且 r(f) 只假設了來自集合 {0, 1} 的變數值 0 或者 1：
r（x i）：=（1 - x i） r（¬f）：=（1 - r（f）） r（（f∧g））：=（1 - （1 - r（f））（1 - r（g））） r（（f∨g））：= r（f）r（g） 有些人可能會假設將 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 的資訊。
（未完待續）
（來源：格密鏈）