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。

a16z推出新的加密貨幣指數，顯示采用率和創新參數:金色財經報道，Andreessen Horowitz 的 web3 投資部門 a16z Crypto 公布了其新的“加密貨幣狀態”指數，該指數描繪了比大多數價格圖表更樂觀的新興市場圖景。 該指數考慮了幾個所謂的采用和創新參數，包括活躍開發人員的數量、學術研究中對加密貨幣的提及，以及去中心化交易場所的交易量。[2023/4/11 13:57:22]

正如我們將看到的，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，必須滿足以下三個條件中的一個：

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

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

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

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

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

商業支付服務商Sequence獲1900萬美元種子輪融資，a16z領投:金色財經報道，商業支付服務商Sequence宣布獲得1900萬美元種子輪融資，a16z領投。Sequence總部位于倫敦，由首席執行官Riya Grover和董事長Eamon Jubbawy創立，前者曾是食品配送平臺Feedr的聯合創始人，后者是數字身份證公司Onfido的前創始人。

Sequence旨在解決商業結算和支付領域的遲鈍和笨拙，通過開發“動態”B2B計費和收款解決方案，Sequence正在提供自動化和更加簡化的定價和發票流程，并計劃利用API、數據和分析來實現這一目標。[2022/9/22 7:12:51]

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 個門的電路。

Web3初創公司Halliday完成600萬美元種子輪融資，a16z領投:8月5日消息，Web3初創公司Halliday完成600萬美元種子輪融資，Andreesen Horowitz (a16z) 領投，Hashed、A.Capital、SV Angel等參投。

Halliday聯合創始人Griffin Dunaif表示，Halliday為游戲玩家提供了“現在玩，以后付款（play now, pay later）”的選擇。Halliday 的目標是讓游戲內購買和NFT所有權證明對那些可能因游戲中NFT的高價而惱火的游戲玩家來說更加實惠和方便。Halliday讓玩家可以訪問游戲內的NFT市場。在不離開游戲的情況下，玩家可以選擇他們想要的數字收藏品并直接購買，或者與Halliday達成付款計劃。（Decrypt）[2022/8/5 12:03:29]

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 的方法似乎也非常有限/據我所知，還不知道如何使用它來支持沒有預先確定迭代邊界的循環。

NFT游戲初創公司Mythical Games完成1.5億美元C輪融資，a16z領投:11月4日消息，在不到四個月前完成7500萬美元B輪融資之后，NFT游戲初創公司Mythical Games今日宣布獲得由a16z領投的1.5億美元C輪融資，公司估值達到12.5億美元。D1 Capital、RedBird Capital、The Raine Group和交易所Binance、FTX參投，現有投資者Galaxy Interactive、WestCap、01 Advisors、Javelin Partners、Struck Capital、Alumni Ventures和Signum Growth Investments追投。（businesswire）[2021/11/4 6:32:11]

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

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

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

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

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

推特發言人Nick Pacilio將加入a16z，負責媒體關系:9月17日消息，推特發言人Nick Pacilio在推特任職7年后將離開推特，加入a16z并負責媒體關系。[2021/9/17 23:32:33]

總而言之，使用虛擬機抽象的現有前端在虛擬機的每個步驟中產生 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：ARKNARAIRCAIARKEExtra Ordinary CoinFAIR價格MCAI

比特幣交易