a16z：以三要素衡量SNARK性能_ARK

本文來自 a16z，原文作者：Justin Thaler，由 Odaily 星球日報譯者 Katie 辜編譯。

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

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

但由于 SNARK 驗證通常很便宜，適用性的主要決定因素是 SNARK 證明者 P 的成本。本文中將解釋如何估算這些成本，以確定何時合理使用 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。

Socket完成2000萬美元A輪融資，a16z領投:8月2日消息，開源軟件安全解決方案Socket完成2000萬美元A輪融資，Andreessen Horowitz(a16z)領投，Abstract Ventures、Wndrco、Unusual Ventures，以及包括Box聯合創始人Aaron Levie、Figma聯合創始人Dylan Field、Okta聯合創始人Frederic Kerrest、Vercel CEO Guillermo Rauch和Eventbrite聯合創始人Julia和Kevin Hartz在內的多名天使投資人參投。

加上此前460萬美元種子輪募資，Socket融資總額達2460萬美元，未來這筆資金將被用于擴充Socket團隊，并支持和集成更多編程語言。Socket目前客戶包括Metamask、Brave、Magic Eden、Figma和Vercel等項目。[2023/8/2 16:13:32]

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

關鍵問題是，相對于簡單地對數據重新執行 ψ，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，必須滿足以下三個條件中的一個：

a16z合伙人：加密市場低迷給風投公司更多投資機會，希望創造一個更好的互聯網:8月23日消息，a16z合伙人Chris Dixon在接受《金融時報》采訪時表示，目前的加密市場低迷給風險投資公司更多的投資機會。目前互聯網上的權力由一小部分公司掌握。我們可以做的是創造一個更好的互聯網，創造新的系統，讓網絡效應累積到社區而不是公司。（CoinDesk）[2022/8/23 12:43:10]

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

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

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

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

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

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

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

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

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

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

a16z Crypto和Cultural Leadership Fund公布HBCU Token委托計劃:2 月 11 日，a16z Crypto 和 Cultural Leadership Fund 公布 HBCU Token 委托計劃，此次授權委托是擴大在治理過程中擁有有意義發言權的參與者群體的一種方式。當它有效地完成時，它最終是一種長期發展更高質量管理機構的方式。

a16z 創建了代表計劃以允許更多人參與網絡治理，與多元化的優秀代表網絡合作，包括非營利組織、初創公司、學生俱樂部、社區領袖等。為 HBCU 學生和俱樂部舉辦的信息發布會將于 2 月 23 日舉行。[2022/2/11 9:44:32]

例如，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 程序轉化為電路之前將其編譯成其他匯編語言。這些項目的性能結果尚未確定。

AI流動性策略開發團隊Kosen Labs完成500萬美元種子輪融資，a16z 領投:11月17日消息，由前谷歌 DeepMind 人工智能研究人員Miljan Martic和Peter Toth建立的去中心化AI流動性策略開發團隊項目Kosen Labs宣布完成由 a16z 領投的500萬美元種子輪融資，Framework Ventures 等參投。

Kosen Labs希望將AI帶入到Web3領域中，將專注于為下一代自動做市商（如Uniswap V3 和 Sushiswap Trident）提供主動流動性提供解決方案。另外，Kosen Labs 將組建Kosen基金會，并將發布DAO治理代幣。Kosen Labs 將作為基金會的一部分提供有效的LP策略和AI解決方案。[2021/11/17 6:56:20]

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

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

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

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

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

Mysten Labs在由a16z領投的A輪融資中籌集3600萬美元:金色財經報道，Web 3基礎設施公司Mysten Labs在由Andreessen Horowitz(a16z)領投的A輪融資中籌集了3600萬美元。這家初創公司由Facebook加密部門Novi Research的資深人士創立，并將很快推出一個NFT平臺。據悉，Mysten首席執行官Evan Cheng領導Novi并幫助開發了Diem區塊鏈和Move編程語言。[2021/12/7 12:55:43]

但是無論如何，對于今天所有熱門的 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·124≈400·|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的值相對較小（例如 T≥220），每個列的字段操作數至少是 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 后端，證明程序需要為 C 中的每個門存儲多個字段元素，這種空間開銷可能非常大。在筆記本電腦上運行一秒鐘的程序 ψ 可以在現代處理器上執行10億次原始操作。一般來說，C 需要超過 100 個門來完成這樣的操作。這意味著 1000 億個門，這取決于 SNARK，可能意味著 P 有幾十或幾百 TB 的空間。

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

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

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

在某種程度上，我認為我們會的。首先，今天最快的后端（例如 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 在內的豐富指令集所帶來的通用性和改進的開發人員體驗。

Tags：ARKNARAIRCAILoud MarketDigiDinar TokenBear BillionaireCaixaPay

LTC