Vitalik：zk-SNARKs 內部原理

*注：文章撰寫於2017年2月

該文章解釋了zk-SNARKs背後的技術是如何運作的，以前關於二次運算程序和橢圓曲線配對的文章是必讀的，本文將假設你已經瞭解這兩個概念，並瞭解zk-SNARKs的基本知識和它們的作用。另請參閱另外一篇對zk-SNARKs的介紹，Christian Reitwiessner的文章。

在之前的文章中，我們介紹了二次運算程序，這是一種用多項式方程表示任何計算問題的方法。我們還引入了橢圓曲線配對，它允許非常有限的單向同態加密形式，從而允許您進行相等檢查。現在，我們將從我們離開的地方開始，並使用橢圓曲線配對以及其他一些數學技巧，使得證明者能夠證明他們知道特定QAP的解決方案，同時不會洩露任何有關實際解決方案的信息。

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

首先，讓我們進入一個關鍵的假設：指數知識假設(KEA)。這個假設我們將會在說明底層安全機制的時候會用到。

KEA1: 對於任何一個對手A，它接收輸入q,g, g^a，然後返回(C, Y)並且Y = C^a，那麼必然存在一個“提取者”A'，當它接收和A一樣的輸入時，能返回c使得g^c = C。

這個假設基本上意味著，如果你得到一對點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）。

讓我們做一些更有趣的事情。假設我們有十對點從天空落下：（P_1，Q_1），（P_2，Q_2）......（P_10，Q_10）。在所有情況下，都滿足P_i * k = Q_i。假設我然後給你一對點（R，S），其中R * k = S.你現在知道什麼？你知道R是一些線性組合P_1 * i_1 + P_2 * i_2 + ... + P_10 * i_10，其中我知道係數i_1，i_2 ... i_10。也就是說，到達這樣一對點（R，S）的唯一方法是取一些P_1，P_2 ...... P_10的倍數並將它們加在一起，並對Q_1，Q_2 ...... Q_10進行相同的計算。

請注意，給定您可能想要檢查線性組合的任何特定P_1 ... P_10點，您實際上無法創建伴隨的Q_1 ... Q_10點而不知道k是什麼，如果您確實知道k是什麼，那麼您可以創建一對（R，S），其中R * k = S表示您想要的任何R，而無需創建線性組合。因此，為了實現這一點，創建這些點的人必須都是值得信賴的，並且一旦創建了10個點，就要刪除k。這就是“可信設置”概念的來源(譯者注：可信設置，指的是zkSNARK系統啟動的時候所進行一次設置，這個設置只需要進行一次)。

回憶一下，QAP的解是一組多項式（A，B，C），使得A（x）* B（x） - C（x）= H（x）* Z（x），其中：

A是一組多項式{A_1 ... A_m}的線性組合
B是具有相同係數的{B_1 ... B_m}的線性組合
C是具有相同係數的{C_1 ... C_m}的線性組合
集合{A_1 ... A_m}，{B_1 ... B_m}和{C_1 ... C_m}以及多項式Z是問題陳述的一部分。

然而，在大多數現實世界中，A，B和C都非常大;對於像散列函數那樣具有數千個電路門的東西，多項式（以及線性組合的因子）可能有數千項。因此，我們不是讓證明者直接提供線性組合，而是使用我們上面介紹的技巧來證明他們提供的東西是線性組合，並且無需透露任何其他東西。

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

G * A_1（t），G * A_1（t）* k_a
G * A_2（t），G * A_2（t）* k_a
...
G * B_1（t），G * B_1（t）* k_b
G * B_2（t），G * B_2（t）* k_b
...
G * C_1（t），G * C_1（t）* k_c
G * C_2（t），G * C_2（t）* k_c
...
您可以將t視為計算多項式的​​“秘密點”。 G是一個“生成器”（橢圓曲線上面某個隨機的點，一旦確定之後，就把它作為協議的一部分），t，k_a，k_b和k_c是“有毒廢物”，這些數字必須不惜一切代價刪除掉，否則任何擁有它們的人將能夠製作假證明。現在，如果有人給你一對點P，Q，使得P * k_a = Q（提醒：我們不需要k_a來檢查這個，因為我們可以進行配對檢查），那麼你知道他們給你的是在t處計算出的A_i多項式的線性組合。

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

π_a= G * A（t），π'_a= G * A（t）* k_a
π_b= G * B（t），π'_b= G * B（t）* k_b
π_c= G * C（t），π'_c= G * C（t）* k_c

注意，證明者實際上並不需要知道（並且不應該知道！）t，k_a，k_b或k_c來計算這些值；而是，證明者應該能夠從我們添加到可信設置的點來計算這些值。

下一步是確保所有三個線性組合具有相同的係數。我們可以通過向可信設置添加另一組值來實現：G *（A_i（t）+ B_i（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相當於數字中的1）。我們可以將G * Z（t）添加到可信設置中。 H更難計算; H只是一個多項式，對於每個QAP的解來說，我們很難提前預測它的係數。因此，我們需要向可信設置添加更多數據;特別是序列：

G，G * t，G *t²，G *t³，G *t⁴......

在Zcash可信設置中，此處的序列大約為200萬;想想看你需要耗費多大的算力才能確保你能計算H（t）。由此，證明者可以為驗證者提供所有信息以進行最終檢查。

還有一個我們需要討論的細節。大多數時候，我們不僅僅想抽象地證明某些特定問題存在某種解決方案;相反，我們想要證明某些特定解決方案的正確性（例如，證明：如果把“cow”這個詞用SHA3算法哈希一百萬次，最終結果從0x73064fe5開始），或者如果限制一些參數就一定存在一個解。例如，在加密貨幣的實現中，交易金額和帳戶餘額已加密，您需要證明您知道某些解密密鑰k，以便：

decrypt（old_balance，k）≥deconspt（tx_value，k）
decrypt（old_balance，k） - decrypt（tx_value，k）= decrypt（new_balance，k）

加密後的old_balance，tx_value和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。其中7個點位於F_p曲線上（每個32個字節，因為您可以將y座標壓縮為1bit），在Zcash實現中，另一個點（π_b）位於F_p²（64字節）的扭曲曲線上，因此證明的總大小約為288字節。

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

• 進行（A * B - C）/ Z得到H（基於快速傅立葉變換的算法可以在次二次時間內完成此操作，但它仍然計算量很大）
• 進行橢圓曲線乘法和加法以創建A（t），B（t），C（t）和H（t）的值及其對應的配對

創建證明很困難，它的原因是，因為我們要進行零知識證明，原始計算中的單個二進制邏輯門就必須變成通過橢圓曲線進行加密處理的操作。這一事實以及快速傅立葉變換的超線性，意味著Zcash交易中創建證明需要花費大約20-40秒。

另一個非常重要的問題是：我們可以嘗試使可信設置稍微......對信任要求不高嗎？不幸的是，我們無法讓它完全無信任; KoE假設本身倒是排除了，在不知道k是什麼的情況下形成獨立對（P_i，P_i * k）的可能性。但是，我們可以通過使用N-of-N多方計算來大大提高安全性 - 也就是說，構建N方之間的可信設置，只要至少有一個參與者刪除了他們的有毒廢物然後你就可以了。

為了讓你對如何做到這一點有一點感覺，這裡有一個簡單的算法，用於獲取現有的集合（G，G * t，G *t²，G *t³......），並“加入”你自己的秘密，因此你需要你的秘密和以前的秘密（或以前的秘密的集合）才能作弊。

輸出集很簡單：

G，（G * t）* s，（G t²）s²，（G t³）s³......

請注意，除了現在使用t * s作為“有毒廢物”而不是t之外，您可以僅知道原始集合和s， 以及與舊集合功能相同的新集合。只要您和創建前一集合的人（或人們），刪除有毒廢物沒有都失敗並且後來還串通了，那麼該組就是“安全的”。

為完整的可信設置執行此操作要困難得多，因為涉及多個值，並且算法必須在多方之間經過若干輪才能完成。這是一個積極研究的領域，看看多方計算算法是否可以進一步簡化，並且需要更少的輪次或更多的可並行化，因為如果能做到這些，就能讓更多的參與方參與到可信的設置程序中。有理由看到為什麼六個參與者之間的可信設置可能會讓一些人感到不舒服，但是有數千名參與者的可信設置，幾乎等同於去信任 —— 如果你真的是偏執狂，您可以自己進入並參與設置程序，並確保您個人刪除了您的有毒廢物。

另一個積極研究的領域是，不使用配對和這樣可信設置，用其他方法來實現相同的目標。請參閱Eli ben Sasson最近的一個演示文稿（還是要提醒一下，它在數學上，至少與SNARKs一樣複雜！）