a16z：SNARK 安全性和效能

作者：Justin Thaler

SNARK（Succinct Non-interactive Argument of Knowledge）是一種加密工具，它在系統設計中開闢了令人興奮的新可能性，特別是在去中心化的環境中。SNARKs允許資料被不被信任的實體處理，然後他們可以證明資料是有效的，並且被正確處理過。證明這一點的一個天真的方法是公佈資料，允許任何希望檢查其有效性並直接處理它的人。

一個SNARK可以達到同樣的效果，但是驗證者的成本更高。例如，在一個第二層（L2）可驗證的rollup中，一個rollup服務處理區塊鏈交易。該服務定期將其使用者的賬戶餘額釋出到第一層區塊鏈上。每次它釋出餘額的更新，它都會附加一個SNARK證明，證明它知道將舊賬戶餘額改變為更新賬戶餘額的有效交易序列。通過這種方式，區塊鏈驗證者不必做檢查交易有效性的艱苦工作（例如，檢查每個交易的數字簽名），也不必明確處理交易以計算更新的餘額。

我的上一篇文章集中討論了SNARK驗證器的效能–SNARK適用性的主要決定因素。雖然執行SNARK證明者可能是計算密集型的，以至於為大規模計算生成證明可能不可行，但SNARK驗證通常比直接檢查和處理資料便宜得多。然而，SNARK的驗證成本確實有很大的不同。這篇文章解讀了這些成本，並比較了不同SNARKs的安全屬性。

特別是，我想解釋說，在具有可信的量子後安全（PQ-SNARKs）的實際SNARKs中，安全和驗證成本之間存在著明顯的緊張關係。此外，在某些情況下，這種緊張關係目前正在得到解決，有利於驗證成本而不是安全性。

為了使SNARKs實現其潛力，部署的系統必須是安全的，使用者必須對其安全性有信心。在文章的最後，我提出了Web3社群可以採取的簡單行動，以幫助確保這些特性長期存在。

量化的安全措施

如果產生一個令人信服的虛假宣告的證明在計算上是不可行的，那麼一個SNARK就是安全的。例如，在二級rollups的背景下，一個希望竊取我的資金的攻擊者會想要證明一個虛假的宣告，其形式為“我知道一個數字簽名的交易，將Justin的所有資產轉移到我自己的賬戶。””

SNARK的安全級別是由找到一個令人信服的虛假宣告的證明所必須做的工作量來衡量的。與數字簽名等其他加密基元類似，這一工作量的對數被稱為“安全位元”。例如，30位元的安全性意味著攻擊SNARK需要230≈10億“工作步驟”。這本質上是對現實世界安全性的近似衡量，因為一個工作步驟的概念可能會有所不同，而且沒有考慮到諸如記憶體要求或並行機會等實際因素。

還有定性的

位元的安全性是對SNARK安全性的定量衡量。SNARKs在其定性的安全屬性方面也有所不同。

例如，一些SNARKs需要一個可信的設定儀式來生成一個結構化的證明金鑰。完全不需要可信設定的SNARKs被稱為透明的。

對於一個非透明的SNARK是安全的，通常情況下，儀式中至少有一個參與者必須表現得誠實，這意味著他們產生然後丟棄一個“陷阱門”，如果與所有其他參與者的陷阱門相結合，將使人們很容易找到任何虛假陳述的令人信服的SNARK“證明”。受信任的設定正在與成百上千的參與者一起執行，以使這種假設儘可能地溫和。

SNARKs在其對量子攻擊的敏感性方面也有不同。具體來說，許多SNARKs（例如，Groth16、PlonK、Marlin、Bulletproofs、Nova）依賴於離散對數難以計算的假設（在某些情況下，還有其他假設）。計算離散對數是量子計算機能夠有效完成的事情。因此，這些SNARKs不是後量子安全（非PQ）。

雖然目前正在進行緊急努力，以轉向後量子加密方案，但這主要是由於需要在未來幾十年內保持加密資訊的祕密。一個對手如果今天儲存了截獲的資訊，並等待量子計算機的到來，例如五十年後，就可以使用計算機來解密五十年前的資訊。SNARKs的情況則完全不同。今天使用非PQ SNARKs不應該損害未來五十年後區塊鏈的安全性，即使量子計算機屆時真的到來。

Polynomial承諾

所有的SNARKs都使用一種被稱為Polynomial承諾方案的加密基元，這個元件通常是一個性能瓶頸。 (詳情見我之前的文章。) 此外，SNARK的透明度和可信的量子後安全性完全由它使用的Polynomial承諾方案決定。

一個突出的例子是所謂的KZG Polynomial承諾，它被PlonK、Marlin和其他許多人使用。KZG承諾既不透明，也沒有後量子安全。其他承諾方案是透明的，但不是後量子的，包括Bulletproofs, Hyrax, 和Dory。

還有一些方案既是透明的，又是可信的後量子的。這些包括FRI、Ligero、Ligero++、Brakedown和Orion。所有這些方案都是基於糾錯碼的。雜湊是它們使用的唯一加密原素。它們還有一個共同的特性：驗證成本（由雜湊值和欄位操作的數量衡量）隨著安全位元數的增加而線性增長。

粗略地說，這些後量子Polynomial承諾的一次“迭代”只實現了少量（比如2-4）位元的安全性。因此，該協議必須重複多次才能“放大”安全級別，每次重複的驗證成本都會增加。 因此，為了控制PQ-SNARKs的驗證成本（以及區塊鏈應用中的gas成本），協議設計者被激勵保持低安全級別。

除了極少數例外，在非PQ-SNARKs（透明和非透明的都一樣）中不會出現具體安全和驗證成本之間的這種緊張關係。非PQ-SNARKs使用 elliptic curve組，其中離散對數被認為是難以計算的，其安全級別由使用的組決定。適當的 elliptic curve組的大小，以及每個組操作的成本，隨著所需的安全級別而增長。然而，證明中的組元素的數量與組的選擇無關。

在PQ-SNARKs中，不僅雜湊值的大小隨所需的安全級別線性增長，而且包括在證明中並由驗證人執行的評價的數量也是如此。

部署的SNARKs中具體的驗證人成本和安全性

部署的SNARKs的具體驗證人成本和安全級別有很大的不同。下面是一些說明性的例子：

驗證者成本

我在上一篇文章中提到了兩個具體驗證成本的例子。PlonK證明在以太坊上的驗證成本低於30萬個gas，而StarkWare的證明則需要花費大約500萬個gas。StarkWare的證明是透明的，而且是可信的後量子，而PlonK的證明則不是。然而，正如接下來所詳述的，StarkWare的證明在以太坊上執行的安全級別要比PlonK的證明低很多。

具體的安全性

唯一有Ethereum預編譯的elliptic curve叫做altbn128，所以這是所有部署在Ethereum上的非PQ SNARK使用的curve，包括Aztec和zkSync的。這個curve–因此也是使用它的部署的SNARKs–最初被認為提供了大約128位的安全性。但由於攻擊的改進（其精確的執行時間很難確定），該curve現在被廣泛認為提供100到110位元的安全。

有一些EIP正在考慮引入不同curve的預編譯，這些curve仍然被認為提供了接近128位元的安全性。這樣的curve已經在非以太坊專案的SNARKs中使用，包括ZCash、Algorand、Dfinity、Filecoin和Aleo。

相反，根據鏈上資料，StarkWare的PQ-SNARKs（在其所謂的SHARP系統中，SHARed Prover的縮寫）被配置為80位元的安全目標。這個安全級別在關於FRI的統計健全性的某些猜想下是成立的（我將在這篇文章的後面討論）。

術語“80位元安全”在這裡是模糊的，所以讓我把它拆開。粗略地說，它意味著攻擊者可以通過對一個雜湊函式（即KECCAK-256，以太坊使用的雜湊函式）進行280次評估，產生一個令人信服的虛假宣告證明。更準確地說，一個願意進行2k次雜湊評估的攻擊者可以產生一個令人信服的證明，其概率大約為2k-80。例如，通過270次雜湊值評估，人們可以找到一個SNARK“證明”一個錯誤宣告的概率約為2-10=1/1024。

這個概念比“80位元安全”一詞在其他情況下的含義要弱一些。例如，一個配置為80位元安全的抗碰撞雜湊函式（CRHFs）將產生160位元的輸出。如果雜湊函式設計得很好，最快的碰撞查詢程式將是生日攻擊，這是一個粗暴的程式，可以用大約2160/2=280個雜湊評估找到一個碰撞。然而，在2k個雜湊值的情況下，“生日”攻擊將找到一個碰撞的概率只有22k-160。

例如，270個雜湊值將產生一個概率為2-20≈1/1,000,000的碰撞。這遠遠小於攻擊者偽造配置為80位元安全的PQ-SNARK證明的1/1,000的概率。

這種差異可以極大地改變實施攻擊的吸引力。為了說明問題，設想攻擊者有10萬美元的預算，可以購買270個雜湊評估。並假設如果攻擊者成功，報酬是2億美元。針對配置為80位元安全的PQ-SNARK的攻擊的預期價值是（1/1000）*2億美元，或20萬美元（成本的兩倍）。如果成功概率只有1/1,000,000，就像CRHF那樣，攻擊的預期值就只有200美元。

這兩個“80位元安全”的概念在對獨立攻擊的robustness方面也有很大的不同。例如，假設1,000個獨立方通過進行270次雜湊評估來攻擊PQ-SNARK。由於每個人成功的概率約為1/1000，所以其中至少有一個人很可能成功。如果每個人成功的概率只有1/1,000,000，情況就不會是這樣了。

精心設計的elliptic curve組預計會有類似CRHF的行為，其中類似生日的攻擊，如Pollard的rho演算法是最著名的。這意味著在一個提供128位元安全的組中，2k個組操作應該產生一個離散對數問題例項的解決方案，其概率只有22k-256。例如，270次分組操作將找到一個離散對數，其概率小得像個天文數字，為2-116。此外，每組操作都比CRHF評估慢。

今天有多少雜湊運算是可行的？

在2020年1月，使用GPU計算略低於264個SHA-1評估的成本是45,000美元。這使得在GPU上進行270次SHA-1評估的成本為幾百萬美元（在以太坊合併後可能會更低，因為從GPU主導的工作量證明挖掘的過渡可能會減少對GPU計算的需求，降低其成本）。

由於有效性rollups已經儲存了數億美元的使用者資金，找到一個令人信服的虛假證明可以獲得數百萬美元的利潤。在咄咄逼人的猜想下，將PQ-SNARK配置為80位元的安全性，在有利可圖的攻擊和PQ-SNARK的猜想安全性之間留下了不到10位元的迴旋空間。

作為另一個數據點，比特幣的網路雜湊率目前約為每秒264次雜湊評估，這意味著比特幣礦工作為一個整體每18小時進行280次SHA-256評估。當然，這個令人瞠目結舌的數字是由於對比特幣挖礦的ASIC的巨大投資。

假設每小時建立6個比特幣區塊，並考慮到目前每個區塊6.25比特幣的獎勵，這280個SHA-256評估的成本可能低於22,000美元*18*6*6.25≈1500萬美元。否則，在目前的價格下，比特幣挖礦將無利可圖。

為一個健康的生態系統建議的行動

在rollups中使用SNARKs的全部意義在於實現區塊鏈的可擴充套件性，而使用者不需要盲目地信任rollups服務。由於rollups服務編寫了作為SNARK驗證器的智慧合約，公眾必須能夠檢查該合約，並確認它確實在驗證適當語句的SNARK證明。公眾對智慧合約的檢查可能也是必要的，以確保rollups服務不能審查自己的使用者。提議的抵制審查的方法要求rollups的智慧合約允許使用者在rollups服務未能處理他們的交易時強制提取他們的資金。

鑑於這些協議的複雜性，這種公眾監督的正規化給專家們帶來了一些負擔，讓他們公開和坦誠地討論所部署合約的安全性。

但是對於PQ-SNARKs，即使是專家也很難確定所部署協議的安全級別，原因與這些SNARKs的安全和驗證器效能緊張的原因相同：安全級別（和驗證器成本）取決於SNARK的內部引數。而至少對於StarkWare的智慧合約來說，這些被稱為logBlowupFactor、proofOfWorkBits和n_Queries的引數並不直接在智慧合約的程式碼中指定，而是作為公共資料傳遞給智慧合約。據我所知，從鏈上資訊識別這些引數的最簡單方法是通過四個步驟：

1. 在區塊探索器（如Etherscan）上檢視相應的智慧合約。
2. 點選一個適當的“驗證”交易。
3. 解碼該交易的輸入資料，並
4. 弄清楚如何解釋解碼後的輸入資料，以瞭解共同決定安全級別的關鍵SNARK引數。

這最後一步需要找到實現該交易的適當的Solidity程式碼，這本身可能是一個令人困惑的任務。(當我今年夏天準備關於rollups的調查講座時，Etherscan能夠按照上述步驟2對SHARP驗證器交易的相關輸入資料進行解碼。但這似乎不再起作用了）。

建議1：審查

所以，我對Web3社群的第一個建議是，讓審查已部署的後量子SNARKs的安全級別變得更加容易。這可能涉及到理解鏈上資料的更好的工具，以及專案本身在公佈這些引數時增加透明度。

提議2：更強的規範

80位元的安全性太低了，尤其是弱版本，其中270個雜湊值足以成功攻擊，概率約為1/1000，考慮到對加密基元的驚人攻擊的漫長曆史，更是如此。上面提到的一個，是對成對的elliptic curves的更好的攻擊，如altbn128。一個更著名的例子是SHA-1，它的標準是80位元的安全性，但最終被證明只能達到約60位元。考慮到這段歷史，PQ-SNARK設計者在配置安全級別時應該給自己留出10位元以上的迴旋餘地，特別是如果安全分析涉及到對FRI等相對較新協議的統計安全性的強烈猜想。

即使對於PQ-SNARKs來說，適當的安全級別總是可以實現的，只需增加驗證成本即可。例如，將SHARP的驗證器的安全性從80位增加到128位（在對FRI的統計健全性的猜想下）將增加大約兩倍的gas成本，從500萬多一點增加到1000萬多一點。如果沒有關於FRI的猜想，gas成本將再增加2倍，超過2000萬。

那麼，我的下一個建議是，Web3社群應該圍繞部署的SNARKs的適當安全級別制定更有力的規範。我個人的建議是至少100位元，如果SNARK的安全是基於非標準的假設，則至少128位元。我不是第一個提出這種建議的人。

在這裡，我願意將隨機預言機模型中的無條件安全歸為“標準假設”，如果部署的SNARK中的隨機預言機被例項化為標準雜湊函式，如KECCAK-256。隨機信使模型是一種理想化的設定，旨在捕捉設計良好的加密雜湊函式的行為。它經常被用來分析PQ-SNARKs的安全性。

非標準假設的一個例子是關於FRI等協議的定量合理性的猜想（如下所述），無論是在互動式設定中還是在隨機預言機模型中作為非互動式協議。

SNARK的設計者正在以許多令人興奮的方式進行創新，其中一些可能會推動安全方面的發展，例如，通過使用SNARK友好的雜湊函式，這些函式沒有像更多的標準雜湊函式那樣受到加密分析的影響。我不是在呼籲結束這種努力，遠非如此。但是，這些基元的例項化安全級別應該遠遠超過已知的、可行的攻擊的10位元。

使用SNARKs的rollups通常被描述為繼承了其L1的安全性。但是，如果它們被配置在比L1使用的任何加密基元低得多的安全級別上，這就是一個困難的案例。隨著SNARKs的採用越來越多，我們應該確保我們部署它們的方式與我們談論它們的方式一致。只要仔細分析SNARKs，適當配置並正確實施，它們就和今天使用的任何加密原語一樣安全。

順便提一下：更深入地研究PQ-SNARK的安全性

StarkWare公司的PQ-SNARKs中的80位安全性的說明如下：這些PQ-SNARK使用了一個叫做FRI的polynomial承諾方案，StarkWare的SHARP驗證器在一個猜想下以48位元的安全性執行FRI。粗略地說，該猜想是指對FRI的健全性的簡單攻擊是最佳的。在這種攻擊中，作弊的驗證者只需付出少量的努力，就可以生成一個 “FRI證明”，以2-48的概率通過驗證者隨機選擇的檢查。

StarkWare將FRI與一種稱為“grinding”的技術相結合。這要求誠實的驗證者在產生FRI證明之前先產生一個32位的工作證明。grinding的好處是，它大大增加了作弊驗證人對上述FRI進行簡單攻擊所需的工作，達到約232次雜湊值。

由於（預期）248次簡單攻擊的嘗試在其中一次成功之前是必要的，作弊驗證人偽造FRI證明所需的總工作量大約是248*232=280次雜湊值。

最後，讓我們來解讀一下FRI的48位安全性是如何產生的。FRI驗證者對承諾的多項式進行“查詢”。FRI的驗證成本隨著查詢次數的增加而線性增長。例如，36次FRI驗證器查詢的成本大約是9次查詢的4倍。但更多的查詢意味著更多的安全性。“每次查詢的安全位元數”取決於FRI的另一個引數，稱為程式碼率。

具體來說，FRI 使用稱為 Reed-Solomon 位元速率 r 的東西，其中 r 始終是嚴格介於 0 和 1 之間的數字。FRI 證明者的成本與 r 成反比，因此 1/16 的比率導致證明者為比 ¼ 的速度慢四倍，佔用空間更大。

SHARP驗證器一直在以1/16的編位元速率和12次驗證器查詢的方式執行FRI。

StarkWare猜想，每次FRI驗證器查詢都會增加log2（1/r）位元的安全性。根據這一猜想，12次驗證器查詢可產生12 * log2(16) = 48位元的安全性。

然而，目前的分析只確定了每個驗證器查詢增加的安全性略低於log2（1/r1/2）位元。因此，12個FRI驗證器查詢只產生少於12 * log2(4) = 24位元的“可證明”安全性。

緩解安全和效能之間矛盾的建議

實用的PQ-SNARKs的驗證器成本隨著所需安全位元數的增加而線性增長。緩解這種緊張關係的一個有希望的技術是SNARK組合，我在上一篇文章中描述了它作為解決驗證者和核查者成本之間緊張關係的一種手段，但它也可以解決安全性問題。

兩個例子

Polygon Hermez正在用PlonK合成PQ-SNARKs。如果PQ-SNARK被配置為有一個快速的驗證者和一個足夠的安全級別，那麼π將是大的。所以驗證者不把π傳送給驗證者。相反，它使用PlonK來證明它知道π。

這意味著將PlonK應用於一個以π為輸入的電路，並檢查PQ-SNARK驗證器是否接受π。由於PQ-SNARK的驗證成本是polylogarithmic的，PlonK被應用於一個小電路，因此PlonK驗證器是快速的。由於PlonK證明很小，而且驗證成本很低，所以驗證成本很低。

不幸的是，使用PlonK破壞了透明度和後量子安全。相反，我們可以考慮使用PQ-SNARK本身來代替PlonK來證明對π的瞭解（事實上Polygon使用的PQ-SNARK就是以這種方式自我組成的）。

在PQ-SNARK的第二種應用中，為了證明對π的瞭解，可以對系統進行配置，以便用合理大小的證明實現足夠的安全性，例如，通過選擇一個非常小的程式碼率用於FRI。關鍵的一點是，雖然這種小的位元速率對證明者的時間不利，但PQ-SNARK的第二次應用只適用於一個小的電路，所以總的證明者時間應該仍然很小。

我們對組成的SNARKs的安全性的理論理解還有待提高。然而，目前還沒有已知的對它們的攻擊比單獨攻擊一個組成的SNARKs更快。例如，如果用PlonK組成一個PQ-SNARK，我們不知道有什麼比攻擊PQ-SNARK（即找到一個錯誤宣告的PQ-SNARK證明π），或攻擊PlonK（即找到一個錯誤宣告的PlonK證明“我知道一個驗證者會接受的PQ-SNARK證明π”）更好的攻擊方式。

以這種方式組成SNARKs是一種越來越流行的提高效能的方法。我希望協議設計者也用它來提高安全性。

***

Justin Thaler是喬治敦大學的副教授。在加入喬治城大學之前，他在紐約的雅虎實驗室擔任了兩年的研究科學家，在此之前，他是加州大學伯克利分校西蒙斯計算理論研究所的研究員。

編輯：Tim Sullivan @tim_org

編輯於 2022-09-16 06:55