a16z：以三要素衡量SNARK性能

SNARK（簡潔的非交互式知識參數）是一種重要的密碼原語，用於發現區塊鏈可擴展性（例如 L2 Rollup）和隱私的應用。SNARK 允許某人向不可信驗證器 V（例如以太坊區塊鏈）證明他們知道一些數據（例如一批有效交易）。證明這一點的簡單方法是將數據發送給 V，然後 V 可以直接檢查其有效性。SNARK 實現了同樣的效果，但對 V 來說成本更高。特別是 SNARK 證明應該比包含數據本身的原始證明更短。

SNARK 的驗證成本可能會有所不同，但成果通常都很好。例如，PlonK 的證明在以太坊上的驗證成本約為 29 萬 gas，而 StarkWare  的證明成本約為 500 萬 gas。SNARK 可能適用於區塊鏈之外的各種不同的設置，例如，允許使用快速但不可信的服務器和硬體。

但由於 SNARK 驗證通常很便宜，適用性的主要決定因素是 SNARK 證明者 P 的成本。本文中將解釋如何估算這些成本，以確定何時合理使用 SNARK，以及未來如何改進 SNARK。值得注意的是，這是一個快速發展的領域，本文中討論的幾個項目正在積極提高其性能。

SNARK 是如何部署的？

在 SNARK 部署中，開發人員通常編寫一個計算機程序，將證明人聲稱知道的數據 w 作為輸入（w 代表驗證者），並檢查 w 是否有效。例如，在 Rollup 中，程序將檢查 w 中的所有交易是否都經過數字簽名，是否導致任何帳戶餘額低於零等。然後通過 SNARK 前端輸入程序，該前端將程序編譯成更適合 SNARK 技術應用的格式。這種 SNARK 友好格式稱為中間代碼（IR）。

通常，IR 是某種等效於 的電路可滿足性實例。這意味著電路 C 以數據 w 作為輸入，以及一些通常被稱為「非確定性建議」的額外輸入，並在 w 上運行。這些建議輸入用於幫助 C 運行，同時保持 C 較小。例如，每當 除以兩個數 x 和 y 時，商數 q 和餘數 r 就可以作為建議提供給 C, C 可以簡單地檢查 x = qy + r。這種檢查比讓 C 運行除法算法從頭計算 q 和 r 更便宜。

最後，將可滿足性電路 SNARK 應用於 C。這稱為 SNARK 後端。對於一些高度結構化的問題，如矩陣乘法、卷積和一些圖問題，已知的 SNARK 可以避免這種前端/後端範式，從而實現更快的證明。但本文的重點是通用的 SNARK。

正如我們將看到的，SNARK 後端驗證成本隨著 C 的規模而增長。保持 C 儘可能小是一項挑戰，因為電路是一種極為有限的計算格式。它們由門組成，由電線連接。給每個門 g 輸入一些值，並對這些值應用一個非常簡單的函數。然後，通過 g 發出的導線將結果送入「下游」門。

SNARK 的可擴展性需要多長時間？

關鍵問題是，相對於簡單地對數據重新執行，SNARK 證明器需要多長時間？答案是 SNARK 的驗證程序，是相對於直接的驗證者核查。後一個表達式指的是在 P 將 w 發送給 V 的原始證明中，V 通過對 w 執行 來檢查 w 的有效性。

將證明器開銷分為「前端開銷」和「後端開銷」是有利的。如果逐門計算電路 C 的成本是運行 的 F 倍，那麼我們稱前端開銷為 F。如果將後端驗證程序應用於 C 的成本是逐門評估 C 的 B 倍，那麼我們稱後端開銷為 B。總驗證程序開銷是 F 乘以 B。即使 F 和 B 各自都不大，這個乘法開銷也可能很大。

實際上，F 和 B 都可以是 1000 或更大。這意味著相對於直接驗證者核查，證明程序的總開銷可能是 100 萬到 1000 萬或更多。在筆記本電腦上運行一秒鐘的程序很容易導致 SNARK 驗證程序需要數十天或數百天的計算時間（單線程）。幸運的是，這項工作通常在不同程度上是並行的（取決於 SNARK）。

總之，如果你想在今天的應用程序中使用 SNARK，必須滿足以下三個條件中的一個：

1. 在筆記本電腦上直接核查驗證者只需要不到一秒鐘的時間。

2. 直接驗證者核查特別適合在電路中進行，因此前端的開銷很小。

3. 你願意等待數天等待 SNARK 驗證程序完成，並/或支付巨大的並行計算資源。

本文的其餘部分解釋了前端和後端開銷從何而來，以及我如何對不同的 SNARK 進行估算。以及未來改善的前景。

區分前端和後端

因為不同的後端支持不同類型的電路，所以完全區分前端和後端是一個挑戰。因此，前端可以根據它們期望與之交互的後端而有所不同。

SNARK 後端通常支持所謂的算術電路，這意味著電路的輸入是某個有限域的元素，電路的門執行兩個域元素的加法和乘法。這些電路大致相當於直線計算機程序（沒有分支、條件語句等），這些程序在本質上是代數的，也就是說，它們的原始數據類型是字段元素。

大多數後端實際上支持大部分算術電路，通常稱為 Rank-1 約束滿足（R1CS）實例。除了 Groth16 和它的前身，這些 SNARK 也可以用來支持其他的 IR。例如，StarkWare 使用了一種叫做代數中間表示（AIR）的方法，這與 PlonK 和其他後端支持的 PlonKish 算術運算類似。一些後端支持更通用的 IR 的能力可以減少產生這些 IR 的前端的開銷。

後端也因其本機支持的有限字段而有所不同。我將在下一節進一步討論這個問題。

前端的多種方法

一些（非常特殊的）計算機程序自然對應於算術電路。一個例子是在某個域上執行矩陣簡單乘法的計算機程序。但大多數計算機程序既不是直線也不是代數。它們通常涉及條件語句、整數除法或浮點運算等與有限域運算不自然對應的運算等。在這些情況下，前端開銷將相當大。

一種熱門的前端方法是生成基本的電路，逐步執行一些簡單的 CPU，也稱為虛擬機（VM）。前端設計人員指定一組基本操作，類似於實際計算機處理器的匯編指令。想要使用前端的開發人員要麼直接用匯編語言編寫「驗證者檢查程序」，要麼用諸如 Solidity 這樣的高級語言編寫「驗證者檢查程序」，然後讓他們的程序自動編譯成匯編代碼。

例如，StarkWare 的 Cairo 是一種非常有限的匯編語言，其中的匯編指令大致允許在有限域上進行加法和乘法運算、函數調用以及對不可變（即只寫一次）內存的讀寫。Cairo VM 是一種馮·諾伊曼架構，這意味著前端產生的電路本質上將 Cairo 程序作為公共輸入，並在見證器面前運行該程序。Cairo 語言是圖靈完備的——儘管它的指令集有限，但它可以模擬更多的標準架構，儘管這樣做可能會很昂貴。Cairo 前端將執行 T 個原語指令的 Cairo 程序轉換為所謂的「2 級 AIR, T 行，大約 50 列」。這到底意味著什麼並不重要，但就 SNARK 證明而言，這相當於 Cairo CPU 的每個 T 步驟都有 50 到 100 個門的電路。

RISC Zero 採用了與 Cairo 類似的方法，但它的虛擬機是所謂的 RISC-V 架構，這是一種開源架構，具有豐富的軟體生態系統，越來越受歡迎。作為一個非常簡單的指令集，設計一個高效的支持它的 SNARK 前端可能是相對容易處理的（至少相對於複雜的體繫結構，如 x86 或 ARM）。截至 5 月，RISC Zero 正在將執行原始 RISC-V 指令的程序轉換為具有 3 排和 160 列的 5 級 AIR。這對應於每步 RISC-V CPU 至少有 500 個門的電路。預計在不久的將來會有進一步的改進。

各種 zkEVM 項目（例如，zkSync  2.0、Scroll、Polygo 的 zkEVM）將虛擬機作為以太坊虛擬機。將每條 EVM 指令轉換為等效的「小工具」（即實現指令的優化電路）的過程要比簡單的 Cairo 和 RISC-V 架構複雜得多。由於各種原因，一些 zkEVM 項目並沒有直接實現 EVM 指令集，而是在將高級 Solidity 程序轉化為電路之前將其編譯成其他匯編語言。這些項目的性能結果尚未確定。

如 RISC-V 和 Cairo 的「CPU 模擬器」項目，產生的單個電路可以處理相關匯編語言中的所有程序。另一種方法是類似 ASIC 晶片的，為不同的程序產生不同的電路。這種類似 ASIC 的方法可以為一些程序產生更小的電路，特別是當程序在每個時間步執行的匯編指令不依賴於程序的輸入時。例如，它可以潛在地完全避免直線程序（如初始矩陣乘法）的前端開銷。但 ASIC 的方法似乎也非常有限/據我所知，還不知道如何使用它來支持沒有預先確定迭代邊界的循環。

前端開銷的最後一個組成部分來自於所有 SNARK 都使用在有限域上運行的電路。你的筆記本電腦上的 CPU 可以用一條機器指令將兩個整數相乘或相加。如果前端輸出電路的場特性足夠大，它本質上可以通過相應的場操作來模擬乘法或加法。但是，在真正的 CPU 上實現字段操作通常需要許多機器指令（儘管一些現代處理器確實對某些字段有本機支持）。

一些 SNARK 後端支持比其他更靈活的字段選擇。例如，如果後端使用加密組 G，則電路的字段必須與 G 中的元素數量匹配，這可能是有限的。此外，並非所有領域都支持實用的 FFT 算法。

只有一個實現的 SNARK——Brakedown，在本地支持任意（足夠大）字段的計算。除了它的下一代，它在其他 SNARK 支持的字段上具有最快的已知具體驗證性能，但目前它的證明對於許多區塊鏈應用來說太大了。最近的工作試圖改進證明的大小，但證明器的速度較慢，並且在實用性方面似乎存在障礙。

有些項目選擇在運算速度特別快的領域工作。例如，Plonky2 和其他算法使用 264 - 232 + 1 的特徵域，因為該域的算法實現速度比非結構化域快好幾倍。然而，使用如此小的特徵可能會導致通過字段操作有效地表示整數算術的挑戰。（例如，將一個 32 位無符號整數乘以任何大於 232 的數字可能會產生大於字段特徵的結果。因此，字段選擇自然只支持 32 位數字的算術。）

但是無論如何，對於今天所有熱門的 SNARK 來說，要實現 128 位的安全性（不需要明顯增加驗證成本），它們必須在大於 2128 的域上工作。據我所知，這意味著每個字段操作將需要至少 10 次 64 位機器乘法，以及相當多的加法和位運算。因此，由於需要在有限域上運行的電路，應該考慮至少一個數量級的前端開銷。

總而言之，使用虛擬機抽象的現有前端在虛擬機的每個步驟中產生 100 到 1000 個門的電路，對於更複雜的虛擬機可能會產生更多。最重要的是，有限字段算法比現代處理器上的類似指令至少慢 10 倍（如果處理器內置了對某些字段的支持，也可能有例外）。一種「ASIC 晶片前端方法」可能會減少其中一些開銷，但目前僅限於它能支持的程序類型。

後端瓶頸是什麼？

可滿足性電路的 SNARK 通常是通過結合一個稱為「多項式 IOP」的資訊理論上安全協議和一個稱為「多項式承諾方案」的密碼協議來設計的。在大多數情況下，證明器的具體瓶頸是多項式承諾方案。特別是這些 SNARK 使證明器以加密方式提交一個或多個多項式，其次數為（至少）|C|，即電路 C 中的門數。

相應地，多項式承諾方案中的具體瓶頸將取決於所使用的方案和電路大小。但總是以下三種操作中的一種：計算 FFT、加密組中的冪運算或 Merkle 哈希。Merkle 哈希通常只有在電路很小的情況下才是瓶頸，因此我們將不再進一步討論它。

基於離散對數的多項式承諾

在基於密碼組 G（KZG、BulletProof、Dory 和 Hyrax commit）中離散對數問題的硬度的多項式承諾中，證明者必須計算多項式係數的 Pedersen 向量承諾。這涉及到多重冪運算，其大小等於多項式的次數。在 SNARK 中，這種程度通常是電路 C 的大小|C|。

簡單地說，對大小|C|進行多次冪運算需要大約 1.5·124400·|C|群運算，其中 124G|-表示群 G 中的元素數。然而，有一種稱為 Pippenger 算法的方法，可以將其減少大約 log|C|。對於大型電路（例如|C|225），該對數|C|因子可以具體為 25 或更大，也就是說，對於大型電路，我們預計 Pedersen 向量組合可以通過略多於 10·124C124 的群運算來計算。反過來，每組操作往往比有限場操作慢 10 倍左右（作為一個非常粗略的球場）。使用這些多項式承諾的 SNARK 對於 P 來說與大約 100·|C|現場操作一樣昂貴。

但是現有的 SNARK 除了 100 倍的倍數之外還有額外的開銷。例如：

Spartan 的證明使用 Hyrax 多項式承諾，必須做|C|½多次冪，每個大小為|C|½，削弱了 Pippenger 的算法的加速約為 2 倍。

在 Groth16 中，P 必須在對結對友好的組上工作，其操作通常比不對結對友好的組慢至少兩倍。P 也必須執行 3 次多次冪而不是 1 次。綜合起來，這導致了相對於上面估計的 100·|C|的至少額外 6 倍的減速。

Marlin  和 PlonK 也要求配對，他們的證明者承諾的多項式遠多於 3 個。

對於任何使用了子彈證明的 SNARK（例如 Halo2，它大致是 PlonK，但使用了子彈證明而不是 KZG 多項式承諾），證明者必須在承諾方案的「開始」階段計算對數級的多次冪，這在很大程度上消除了任何 Pippenger 加速。

總之，已知的 SNARK 使用 Pedersen 矢量承諾的後端開銷至少為 200 倍，最高可達 1000 倍或更多。

其他多項式的承諾

對於使用其他多項式承諾（如 FRI 和 liigero -commit）的 SNARK，瓶頸處在於證明程序需要執行大型 FFT。例如，在 Cairo 生產的 2 級 AIR（有 51 列和 T 行，Cairo CPU 每步有 1 行）中，StarkWare 部署的驗證程序每列至少執行 2 個 FFT，長度在 16·T 到 32·T 之間。常量 16 和 32 依賴於 StarkWare 設置的 FRI 內部參數，可以減少，但以增加驗證成本為代價。

樂觀地說，一個長度為 32 的 FFT 大約需要 64·T·log（32T）場乘法。這意味著即使 T 的值相對較小（例如 T220），每個列的字段操作數至少是 64·25·T=1600·T。因此，後端開銷似乎至少有數千。此外，大型 FFT 的瓶頸可能是內存帶寬，而不是字段操作。

在某些上下文中，執行大型 FFT 的 SNARK 的後端開銷可以通過一種稱為證明聚合的技術來減輕。對於 Rollup，這意味著 P （Rollup 服務）將一大批交易分解為 10 個較小的批。對於每一個小批量 i, P 產生一個 SNARK 證明 i 的批次有效性。但是 P 沒有將這些證明發布到以太坊，因為這將導致 gas 成本增加近 10 倍。相反，再次應用了 SNARK，這一次產生了 的證明，證明 P 知道 1，10。也就是說，P 聲稱知道的證人是 1，…，10 這十個證明，直接證人核查將 SNARK 驗證程序應用到每一個證明上。這個簡單的 證明被發布到以太坊。

在多項式承諾（如 FRI 和 liigero -commit）中，P 時間和 V 花費之間存在很強的張力，內部參數充當一個旋鈕，可以在兩者之間進行權衡。由於 1，…，10 沒有發布到以太坊，旋鈕可以調整，所以這些證明是大的，生產它們的速度更快。只有在 SNARK 的最終應用中，才能將 1、10 聚合成單個證明，才需要配置承諾方案來保證小證明。

StarkWare 計劃立即部署證據聚合。這也是 Plonky2 等項目的重點。

SNARK 可擴展性的其他瓶頸是什麼？

本文關注的是驗證時間，但其他驗證成本也可能是可擴展性的瓶頸。例如，對於許多 SNARK 後端，證明程序需要為 C 中的每個門儲存多個字段元素，這種空間開銷可能非常大。在筆記本電腦上運行一秒鐘的程序 可以在現代處理器上執行 10 億次原始操作。一般來說，C 需要超過 100 個門來完成這樣的操作。這意味著 1000 億個門，這取決於 SNARK，可能意味著 P 有幾十或幾百 TB 的空間。

另一個例子是許多熱門的 SNARK（例如，PlonK、Marlin、Groth16）需要一個複雜的「可信設置儀式」來生成一個結構化的「證明密鑰」，它必須由證明者儲存。據我所知，最大的一次這樣的儀式產生了一個能夠支持電路的證明密鑰，大約有 2282.5 億個門。證明的關鍵是幾十 GB 大小。

在證明聚合可能性較高的環境中，這些瓶頸可以適當突破。

展望未來：可擴展性更強的 SNARK 前景

前端和後端開銷都可能是三個數量級或更多。我們能否期待在不久的將來這些數字會大幅下降？

在某種程度上，我認為我們會的。首先，今天最快的後端（例如 Spartanand Brakedown 以及其他結合了求和校驗協議和多項式承諾的 SNARK）有很大的證明量——通常是電路大小的平方根，所以人們並沒有真正使用它們。我預計在不久的將來，通過深度一合成和小的驗證障礙，驗證規模和驗證時間將顯著減少。與證明聚合類似，這意味著證明者將首先使用快速證明者，大證明者 SNARK 生成 SNARK 證明，但不會將 發送給 V。相反，P 將使用一個小的證明 SNARK 產生一個證明，證明它知道，並將 發送給 V。這可以在很大程度上減少目前流行的 SNARK 後端開銷。

其次，硬體加速會有所幫助。一個非常簡單的規則是 GPU 可以買到比 CPU 快 10 倍的速度，而 ASIC 可以買到比 GPU 快 10 倍的速度。

然而，我有三個擔憂。首先，大型 FFT 的瓶頸可能是內存帶寬，而不是字段操作，所以執行此類 FFT 的 SNARK 在專用硬體上的加速可能有限。第二，雖然本文關注的是多項式承諾瓶頸，但許多 SNARK 要求證明者做其他的操作，這些操作的成本只比多項式承諾瓶頸低一點點。因此，打破多項式承諾瓶頸（例如，在基於離散日誌的 SNARK 中加速多次冪）可能會留下一個新的瓶頸操作，它並不比舊的好多少。（例如，SNARK 包括 Groth16、Marlin 和 PlonK，除了多次冪之外，也有 FFT 的驗證程序。）最後，導致最有效的 SNARK 的場和橢圓曲線可能會持續發展一段時間，這可能會給基於 ASIC 的驗證加速帶來挑戰。

在前端，我們可能會越來越多地發現，Cairo、RISC Zero、zkEVM 等項目的「CPU 模擬器」方法實際上可以很好地擴展（就性能而言）CPU 指令集的複雜性。事實上，這正是各種 zkEVM 項目的希望所在。這可能意味著，雖然前端開銷仍然是三個數量級或更多，但前端可以支持越來越匹配真實 CPU 架構的虛擬機。與之相反的一個擔憂是，隨著手工編碼的小工具實現越來越複雜的指令激增，前端可能會變得複雜，難以審核。正式的核查方法很可能在解決這一問題方面發揮重要作用。

最後，至少在區塊鏈應用程序中，我們可能會發現大多數出現在非主流的智能合約主要使用簡單的、SNARK 友好的指令。這在實踐中可能會降低前端開銷，同時保留支持 Solidity 等高級編程語言和包括 EVM 在內的豐富指令集所帶來的通用性和改進的開發人員體驗。

原文連結