CAI:a16z：以三要素衡量SNARK性能_DigiDinar Token

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

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

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

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

SNARK是如何部署的？

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

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

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

a16z Crypto已開源鏈上隱私投票系統Cicada:5月25日消息，a16z Crypto 已開源 Solidity 庫 Cicada，它利用時間同步問題（time-lock puzzle）和零知識證明實現鏈上隱私投票，保證了最小化信任假設，并且可以在以太坊主網上使用，隨后 Cicada 正式證明也即將推出。[2023/5/25 10:38:58]

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

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

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

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

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

Pinecone完成1億美元B輪融資，a16z領投:金色財經報道，Pinecone官方宣布以7.5億美元的估值籌集了1億美元的B輪融資，由a16z領投，ICONIQ Growth、Menlo Ventures和Wing VC跟投。據悉，Pincone是生成式人工智能市場的重要參與者。Pincone向量數據庫使工程師們能夠處理大型語言模型（LLM）和其他AI模型的數據，這對于可擴展、可靠且準確的AI產品至關重要。[2023/4/28 14:32:05]

區分前端和后端

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

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

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

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

前端的多種方法

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

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

Character.AI以10億美元估值完成1.5億美元融資，a16z領投:3月24日消息，生成式AI初創公司Character.AI宣布以10億美元估值完成1.5億美元融資，a16z領投，GitHub前CEO Nat Friedman、Elad Gil、A Capital和SV Angel參投。

Character.AI表示新資金將使其能夠擴展“計算能力，從而產生具有高級推理和更高準確性的更復雜模型”。

此外，有消息稱Character.AI可能會探索加密（或更廣泛的Web3）和社交音頻市場，因為a16z一直是這兩個領域的重要參與者，但該公司截至目前尚未提供額外評論。（CNBC）[2023/3/24 13:23:23]

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

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

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

a16z在2013年首次投資Coinbase，截止2020年共8次投資Coinbase:Coinbase董事、a16z合伙人Katie Haun表示，a16z合伙人Chris在2013年領導了公司對Coinbase的首次投資，到2020年，a16z共8次投資Coinbase。[2021/4/15 20:22:36]

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

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

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

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

有些項目選擇在運算速度特別快的領域工作。例如，Plonky2和其他算法使用264-2321的特征域，因為該域的算法實現速度比非結構化域快好幾倍。然而，使用如此小的特征可能會導致通過字段操作有效地表示整數算術的挑戰。

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

動態 | a16z加密以1500萬美元收購6％的MKR:據btcmanager消息，9月24日，Andreessen Horowitz的專業加密貨幣和區塊鏈基金a16z加密已經購買了MakerDAO的MKR令牌供應量的6％，總價值1500萬美元。[2018/9/25]

總而言之，使用虛擬機抽象的現有前端在虛擬機的每個步驟中產生100到1000個門的電路，對于更復雜的虛擬機可能會產生更多。最重要的是，有限字段算法比現代處理器上的類似指令至少慢10倍。一種“ASIC芯片前端方法”可能會減少其中一些開銷，但目前僅限于它能支持的程序類型。

后端瓶頸是什么？

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

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

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

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

簡單地說，對大小|C|進行多次冪運算需要大約1.5·124≈400·|C|群運算，其中124G|-表示群G中的元素數。然而，有一種稱為Pippenger算法的方法，可以將其減少大約log|C|。對于大型電路，該對數|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，證明者必須在承諾方案的“開始”階段計算對數級的多次冪，這在很大程度上消除了任何Pippenger加速。

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

其他多項式的承諾

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

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

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

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

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

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

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

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

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

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

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

在某種程度上，我認為我們會的。首先，今天最快的后端有很大的證明量——通常是電路大小的平方根，所以人們并沒有真正使用它們。我預計在不久的將來，通過深度一合成和小的驗證障礙，驗證規模和驗證時間將顯著減少。與證明聚合類似，這意味著證明者將首先使用快速證明者，大證明者SNARK生成SNARK證明π，但不會將π發送給V。相反，P將使用一個小的證明SNARK產生一個證明π′，證明它知道π，并將π′發送給V。這可以在很大程度上減少目前流行的?SNARK?后端開銷。

其次，硬件加速會有所幫助。一個非常簡單的規則是GPU可以買到比CPU快10倍的速度，而ASIC可以買到比GPU快10倍的速度。然而，我有三個擔憂。首先，大型FFT的瓶頸可能是內存帶寬，而不是字段操作，所以執行此類FFT的SNARK在專用硬件上的加速可能有限。第二，雖然本文關注的是多項式承諾瓶頸，但許多SNARK要求證明者做其他的操作，這些操作的成本只比多項式承諾瓶頸低一點點。因此，打破多項式承諾瓶頸可能會留下一個新的瓶頸操作，它并不比舊的好多少。最后，導致最有效的SNARK的場和橢圓曲線可能會持續發展一段時間，這可能會給基于ASIC的驗證加速帶來挑戰。

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

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

Tags：ARKNARAIRCAIXMARKDigiDinar TokenAIR幣Cairo Finance

區塊鏈