Zk-SNARKs：引擎蓋下

作者：Vitalik Buterin

原标题：《Zk-SNARKs: Under the Hood》

發表時間：2017 年 2 月 1 日

這是解釋 zk-SNARKs 背後的技術如何工作的系列文章的第三部分；以前關於二次算術程序和橢圓曲線配對的文章是必讀的，本文將假設這兩個概念的知識。還假設了 zk-SNARK 是什麼以及它們做什麼的基本知識。另請參閱此處的 Christian Reitwiessner 的文章以獲得另一篇技術介紹。

在之前的文章中，我們介紹了二次算術程序，這是一種用多項式方程表示任何計算問題的方法，它更適合各種形式的數學技巧。我們還介紹了橢圓曲線配對，它允許一種非常有限的單向同態加密形式，可以讓你進行相等性檢查。現在，我們將從上次中斷的地方開始，使用橢圓曲線配對以及其他一些數學技巧，以允許證明者證明他們知道特定 QAP 的解決方案，而無需透露任何關於實際解決方案。

本文將重點介紹 Parno、Gentry、Howell 和 Raykova 從 2013 年開始的Pinocchio 協議（通常稱為 PGHR13）；基本機制有一些變化，因此在實踐中實施的 zk-SNARK 方案可能會略有不同，但基本原理通常保持不變。

首先，讓我們進入我們將要使用的機制的安全性背後的關鍵密碼假設：指數知識假設。

基本上，如果你得到一對點 P 和 Q，其中 P * k = Q，並且你得到一個點 C，那麼除非 C 以某種方式從 P"派生"出來，否則不可能得出 C * k你知道的。這可能看起來很直觀，但是這個假設實際上不能從我們通常在證明基於橢圓曲線的協議的安全性時使用的任何其他假設（例如離散對數硬度）推導出來，因此 zk-SNARK 實際上確實依賴於比橢圓曲線密碼學更普遍的基礎更不穩定------儘管它仍然足夠堅固，大多數密碼學家都可以接受。

現在，讓我們來看看如何使用它。假設有一對點 (P, Q) 從天上掉下來，其中 P * k = Q，但沒有人知道 k 的值是多少。現在，假設我提出了一對點 (R, S)，其中 R * k = S。那麼，KoE 假設意味著我可以得出這對點的唯一方法是取 P 和 Q，並且將兩者乘以我個人知道的某個因子 r 。還要注意，由於橢圓曲線配對的魔力，檢查 R = k * S 實際上並不需要知道 k -相反，你可以簡單地檢查 e(R, Q) = e(P, S)。

讓我們做一些更有趣的事情。假設我們有十對點從天而降：(P1, Q1), (P2, Q2)… (P10, Q10)。在所有情況下，Pi * k = Qi。假設我隨後為你提供一對點 (R, S)，其中 R * k = S。你現在知道什麼？你知道 R 是一些線性組合 P1 * i1 + P2 * i2 + … + P10 * i10，其中我知道係數 i1, i2 … i10。也就是說，要得到這樣的一對點（R，S），唯一的方法就是取 P1，P2…P10 的一些倍數並將它們相加，然後用 Q1，Q2…Q_10 進行相同的計算。

請注意，給定任何你可能想要檢查線性組合的特定 P1…P10 點集，你實際上無法在不知道 k 是什麼的情況下創建隨附的 Q1…Q10 點，如果你確實知道 k 是什麼，那麼你可以創建一對 (R, S)，其中 R * k = S 為你想要的任何 R，而無需創建線性組合。因此，要使其發揮作用，絕對必須確保創建這些點的人是值得信賴的，並且在創建十個點後實際上刪除 k。這就是"可信設置"概念的來源。

請記住，QAP 的解是一組多項式 (A, B, C)，使得 A(x) * B(x) - C(x) = H(x) * Z(x)，其中：

• A 是一組多項式 {A1…Am} 的線性組合
• B 是具有相同係數的 {B1…Bm} 的線性組合
• C 是具有相同係數的 {C1…Cm} 的線性組合

集合 {A1…Am}、{B1…Bm} 和 {C1…Cm} 以及多項式 Z 是問題陳述的一部分。

但是，在大多數實際情況下，A、B 和 C 都非常大；對於像散列函數這樣具有數千個電路門的東西，多項式（以及線性組合的因子）可能有數千個項。因此，我們不是讓證明者直接提供線性組合，而是使用我們上面介紹的技巧讓證明者證明他們提供的東西是線性組合，但不透露其他任何東西。

你可能已經注意到，上面的技巧適用於橢圓曲線點，而不是多項式。因此，實際發生的是我們將以下值添加到可信設置中：

G * A1(t), G * A1(t) * ka G * A2(t), G * A2(t) * ka
…
G * B1(t), G * B1(t) * kb G * B2(t), G * B2(t) * kb
…
G * C1(t), G * C1(t) * kc G * C2(t), G * C2(t) * kc
…
你可以將 t 視為計算多項式的"秘密點"。G 是一個"生成器"（一些隨機橢圓曲線點，被指定為協議的一部分），t、ka、kb 和 kc 是"有毒廢物"，絕對必須不惜一切代價刪除的數字，否則擁有它們的人將能夠製作假證明。現在，如果有人給你一對點 P, Q 使得 P * ka = Q （提醒：我們不需要 ka 來檢查這個，因為我們可以做配對檢查），那麼你知道他們給了什麼你是在 t 處求值的 Ai 多項式的線性組合。

因此，到目前為止，證明者必須給出：

πa = G * A(t), π'a = G * A(t) * ka πb = G * B (t), π'_ b = G * B(t) * kb πc = G * C(t), π'c = G * C(t) * kc

請注意，證明者實際上不需要知道（也不應該知道！）t、ka、kb 或 k_c 來計算這些值；相反，證明者應該能夠僅根據我們添加到可信設置的點來計算這些值。

下一步是確保所有三個線性組合具有相同的係數。我們可以通過向可信設置添加另一組值來做到這一點：G * (Ai(t) + Bi(t) + C_i(t)) * b，其中 b 是另一個應該被視為"有毒廢物"的數字，並且受信任的設置完成後立即丟棄。然後，我們可以讓證明者使用具有相同係數的這些值創建一個線性組合，並使用與上述相同的配對技巧來驗證該值是否與提供的 A + B + C 匹配。

最後，我們需要證明 A * B - C = H * Z。我們通過配對檢查再次執行此操作：

e( π_ a, π_ b) / e( π_ c, G) ?= e( π_ h, G * Z(t))

其中 π_h = G * H (t)。如果這個方程和 A * B - C = H * Z 之間的聯繫對你來說沒有意義，請返回閱讀有關配對的文章。

我們在上面看到了如何將 A、B 和 C 轉換為橢圓曲線點；G 只是生成器（即橢圓曲線點等價於數字一）。我們可以將 G * Z(t) 添加到可信設置中。H 更硬；H 只是個多項式，我們很少提前預測每個單獨 QAP 解決方案的係數。因此，我們需要向可信設置添加更多數據；具體順序：

G, G * t, G * t², G * t³, G * t⁴ …。

在 Zcash 可信設置中，這裡的序列高達 200 萬左右；這是你需要多少次幂才能確保始終能夠計算 H(t)，至少對於他們關心的特定 QAP 實例而言。這樣，證明者就可以為驗證者提供所有信息以進行最終檢查。

還有一個細節需要我們討論。大多數時候，我們不只是想抽象地證明某些特定問題的解決方案存在；相反，我們想證明某個特定解決方案的正確性（例如，證明如果你使用"cow"一詞並對其進行 SHA3 哈希一百萬次，最終結果以 0x73064fe5 開頭），或者如果你限制解決方案存在一些參數。例如，在交易金額和賬戶餘額被加密的加密貨幣實例中，你想證明你知道一些解密密鑰 k，這樣：

加密的 oldbalance、txvalue 和 new_balance 應該公開指定，因為這些是我們希望在特定時間驗證的特定值；只有解密密鑰應該被隱藏。需要對協議進行一些細微的修改，以創建與輸入的某些特定限制相對應的"自定義驗證密鑰"。

現在，讓我們退後一步。首先，這裡是完整的驗證算法，由 ben Sasson、Tromer、Virza 和 Chiesa 提供：

第一行處理參數化；本質上，你可以將其功能視為為指定了某些參數的問題的特定實例創建"自定義驗證密鑰" 。第二行是 A、B、C 的線性組合檢查；第三行是檢查線性組合是否具有相同的係數，第四行是乘積檢查 A * B - C = H * Z。

總之，驗證過程是幾個橢圓曲線乘法（每個"公共"輸入變量一個）和五次配對檢查，其中一次包括額外的配對乘法。證明包含八個橢圓曲線點：A(t)、B(t) 和 C(t) 各有一對點，b * (A(t) + B(t) + C(t ) 有一個點 πk ))，以及 H(t) 的點 πh 。其中七個點在 Fp 曲線上（每個 32 個字節，因為你可以將 y 坐標壓縮到一位），在 Zcash 實現中，一個點 ( πb ) 在 F_p² 的扭曲曲線上（64 個字節），所以證明的總大小約為 288 字節。

創建證明的兩個計算上最難的部分是：

將 (A * B - C) / Z 除以得到 H（基於快速傅立葉變換的算法可以在次二次時間內完成此操作，但它的計算量仍然很大）
進行橢圓曲線乘法和加法運算以創建 A(t)、B(t)、C(t) 和 H(t) 值及其對應的對
創建證明如此困難的基本原因是，如果我們要從中製作零知識證明，原始計算中的單個二進制邏輯門變成了必須通過橢圓曲線操作進行加密處理的操作。這一事實，加上快速傅立葉變換的超線性，意味著 Zcash 交易的證明創建需要大約 20-40 秒。

另一個非常重要的問題是：我們是否可以嘗試使受信任的設置稍微……不那麼需要信任？不幸的是，我們不能讓它完全不信任；KoE 假設本身排除了在不知道 k 是什麼的情況下製作獨立對 (Pi, Pi * k)。但是，我們可以通過使用 N-of-N 多方計算來大大提高安全性------也就是說，在 N 方之間構建可信設置，只要至少有一個參與者刪除他們的有毒廢物，那麼你就可以了。

為了稍微了解如何執行此操作，這裡有一個簡單的算法，用於獲取現有集合（G、G * t、G * t²、G * t³…），並"添加"你自己的秘密，以便你需要你的秘密和以前的秘密（或以前的一組秘密）來作弊。

輸出集很簡單：

G, (G * t) * s, (G * t²) * s², (G * t³) * s³…

請注意，你可以只知道原始集合和 s 來生成此集合，並且新集合的功能與舊集合相同，只是現在使用 t*s 作為"有毒廢物"而不是 t。只要你和創建前一組的人（或多人）都沒有刪除你的有毒廢物並隨後串通，那麼該組是"安全的"。

為完整的受信任設置執行此操作要困難得多，因為涉及多個值，並且必須在各方之間分幾輪完成算法。這是一個積極研究的領域，看看是否可以進一步簡化多方計算算法並使其需要更少的輪次或更可並行化，因為你可以做的越多，參與可信設置過程的參與方就越多。有理由看到為什麼六個相互認識並一起工作的參與者之間的信任設置可能會讓一些人感到不舒服，但是一個擁有數千名參與者的信任設置與完全不信任幾乎沒有區別------而且如果你真的很偏執，你可以自己進入並參與設置過程，並確保你親自刪除了你的值。

另一個活躍的研究領域是使用不使用配對的其他方法和相同的可信設置範例來實現相同的目標。請參閱Eli ben Sasson 最近的演示文稿以了解另一種選擇（儘管請注意，它至少在數學上與 SNARK 一樣複雜！）

特別感謝 Ariel Gabizon 和 Christian Reitwiessner 的審閱。