詳解a16z crypto新推出的兩款SNARK工具

本文來自 a 16 z ，原文作者：Justin Thaler，由 Odaily 星球日報譯者 Jessica 編譯。

8 月 10 日，a 16 z crypto 推出基於 SNARK 的新工具 Lasso 和 Jolt，它們共同代表了一種全新的 SNARK 設計方法，可將廣泛部署的工具鏈的性能提高一個數量級或更多；提供更好、更方便的开發者體驗；並使審計變得更加容易。

SNARK （簡潔的非交互式知識參數）是一種加密協議，任何人都可以向不信任的驗證者證明它知道滿足某些屬性的“證人” 。

• 在 Web 3 中的一個突出用例是 L 2 向 L 1 證明它們知道授權一系列交易的數字籤名，因此籤名本身不必由 L 1 網絡存儲和驗證，從而提升可擴展性。

• 在區塊鏈之外的應用包括：快速證明不受信任的硬件設備產生的所有輸出的有效性，確保用戶可以信任它們。個人可以以零知識的方式證明 ，受信任的當局已向他們頒發了憑證，證明他們的年齡足以訪問有年齡限制的內容，而無需透露其出生日期。任何通過網絡發送加密數據的人都可以向管理員證明該數據符合網絡策略，而無需透露更多細節。

雖然許多 SNARK 對驗證者來說保持有吸引力的成本，但 SNARK 通常仍會在證明者計算中引入約六個數量級的开銷。證明者所承受的額外工作是高度並行化的，但數百萬倍的开銷嚴重限制了 SNARK 的應用範圍。

更具性能優勢的 SNARK 將加速 L 2 ，還可以允許構建者解鎖尚未設想的應用。 這就是為什么我們要引入兩項新的相關技術：Lasso ，一種新的查找參數，可以顯着提高證明者成本；Jolt ，它使用 Lasso 提供了一個新的框架，用於為所謂的 zkVM 和更廣泛的前端設計設計 SNARK。它們共同提高了 SNARK 設計的性能、开發人員體驗和可審核性，進而提高了 web 3 中的構建。

我們對 Lasso 的初步實現已經證明，與流行的 SNARK 工具鏈 halo 2 中的查找參數相比，速度提高了 10 倍以上。當 Lasso 代碼庫完全優化後，我們預計速度會提高約 40 倍。Jolt 包含 Lasso 之上的其他創新，我們預計它能夠實現與現有 zkVM 類似或更好的加速。

查找參數、Lasso 和 Jolt

SNARK 前端是將計算機程序轉換為 SNARK 後端可以攝取的電路的編譯器。 （注：電路是一種極其有限的計算模型，其中可用的“原始運算”只是加法和乘法。）

現代 SNARK 設計中的一個關鍵工具是一種稱為查找參數的協議，它允許不受信任的證明者以加密方式提交一個大向量，然後證明該向量的每個條目都包含在某個預定的表中。查找參數可以通過有效地處理並非由少量加法和乘法自然計算的運算來幫助保持電路較小。

然而，正如以太坊基金會的 Barry Whitehat 去年所言，“如果我們能夠僅使用查找參數來有效地定義電路，那么它將導致更簡單的工具和電路”。我們設計的電路只執行查找。隨着時間的推移，查找參數“對於幾乎所有事情都將變得比多項式約束更有效”。

這一愿景與當今的工作方式形成鮮明對比，當今开發人員通過使用特殊的領域特定語言（將程序編譯為多項式約束）或直接手動編碼約束來編寫程序來部署 SNARK。該工具鏈需要大量工作，並且為安全關鍵型錯誤的蔓延提供了很大的表面積。即使使用復雜的工具和電路，SNARK 的性能仍然很慢，這限制了它們的適用性。

Lasso 和 Jolt 解決了所有三個關鍵問題：性能、开發人員體驗和可審核性， 共同實現了查找奇點的愿景。Lasso 和 Jolt 還迫使人們重新思考 SNARK 設計中許多公認的智慧。

在介紹完必要的背景知識後，下文重新審視了有關 SNARK 性能的一些常見觀點，並解釋了如何根據 Lasso 和 Jolt 等創新來優化它們。

SNARK 設計背景：為什么這么慢？

大多數 SNARK 後端都讓證明者使用多 項式承諾方案以加密 方式承諾電路中每個門的值。然後證明者證明所提交的值確實對應於見證檢查程序的正確執行。

我將 來自多項式承諾方案的證明者工作稱為承諾成本。 SNARK 具有來自多項式承諾方案之外的額外證明成本。但 承諾成本往往是瓶頸。 Lasso 和 Jolt 也是如此。如果設計一個 SNARK，其中承諾成本不是主要的證明者成本，這並不意味着多項式承諾方案很便宜。相反，這意味着其他成本高於應有的成本。

直觀上，承諾的目的是通過密碼學方法安全地增加證明系統的簡潔性。當證明者提交一個大的值向量時，大致就像證明者將整個向量發送給驗證者，就像普通證明系統將整個見證人發送給驗證者一樣。承諾方案可以在不強迫驗證者實際接收整個見證的情況下實現這一目標——這意味着 SNARK 設計中承諾方案的目的是控制驗證者成本。

但這些加密方法對於證明者來說非常昂貴，特別是與 SNARK 在多項式承諾方案之外使用的信息論方法相比。信息論方法僅依賴於有限域運算。並且一個字段操作比提交任意字段元素所需的時間快幾個數量級。

根據使用的多項式承諾方案，計算承諾涉及多重冪運算（也稱為多標量乘法，或 MSM）或 FFT 和 Merkle 哈希。Lasso 和 Jolt 可以使用任何多項式承諾方案，但在使用基於 MSM 的方案實例化時具有特別有吸引力的成本，例如 IPA / Bulletproofs、KZG / PST、Hyrax、Dory 或 Zeromorph。

為什么 Lasso 和 Jolt 很重要

Lasso 是一種新的查找參數，其中證明者承諾比以前的工作更少且更小的值。 這可能會有 20 倍或更多的加速 ，其中 2 到 4 倍的加速來自於較少的提交值，另一個 10 倍的加速來自於 Lasso 中所有提交的值都很小的事實。與許多先前的查找參數不同，Lasso（和 Jolt）還避免了 FFT ，FFT 佔用大量空間，並且可能成為大型實例的瓶頸。

此外，Lasso 甚至適用於巨大的表，只要這些表是“結構化的”（在精確的技術意義上）。這些表太大，任何人都無法顯式實現，但 Lasso 只為其實際訪問的表元素付費。特別是——與之前的查找參數相比——如果表是結構化的，那么任何一方都不需要以加密方式提交表中的所有值。

Lasso 利用兩種不同的結構概念：可分解性和 LDE 結構。 （LDE 是稱為低次擴展多項式的技術概念的縮寫。） 可分解性大致意味着可以通過對更小的表執行少量查找來回答對表的單次查找。這是比 LDE 結構更嚴格的要求，但 Lasso 在應用於可分解表時特別有效。

Jolt

Jolt（Just One Lookup Table ）是一種新的前端，由 Lasso 使用巨大的查找表的能力解鎖。 Jolt 的目標是虛擬機/CPU 抽象，也稱為 指令集 架構 （ISA） 。 支持這種抽象的 SNARK 稱為 zkVM 。例如，考慮 RISC-Z ero 項目也針對的 RISC-V 指令集 （包括 乘法 擴展 ）。這是由計算機體系結構社區开發的一種流行的开源 ISA，沒有考慮到 SNARK。

對於每個 RISC-V 指令 fi ，Jolt 的主要思想是創建一個包含 fi 的整個評估表的查找表。 對於基本上每個 RISC-V 指令，生成的查找表都是可分解的，並且套索適用。

重新審視 SNARK 設計中公認的智慧

Lasso 和 Jolt 還顛覆了 SNARK 設計中的一些公認的智慧。

#1. 大面積的 SNARK 是一種浪費。每個人都應該使用 FRI、 Ligero 、Brakedown 或變體，因為它們避免了通常適用於大範圍的橢圓曲线技術。

這裏的字段大小大致對應於 SNARK 證明中出現的數字的大小。由於非常大的數字的加法和乘法成本很高，因此大字段上的 SNARK 是浪費的想法意味着我們應該努力設計永遠不會出現大數字的協議。基於 MSM 的承諾使用橢圓曲线，橢圓曲线通常是在大字段（大小約為 2 256）上定義的，因此這些承諾因性能較差而聞名。

使用小字段是否有意義（即使它們是一個選項）在很大程度上取決於應用程序。Lasso 和 Jolt 走得更遠。他們表明，即使使用基於 MSM 的承諾方案，證明者的工作也幾乎可以獨立於字段大小。這是因為，對於基於 MSM 的承諾，承諾值的大小比這些值所在字段的大小更重要。

現有的 SNARK 使證明者承諾許多隨機字段元素。例如，名為 Plonk 的流行 SNARK 後端中的證明者承諾每個電路門大約 7 個隨機場元素（以及其他非隨機場元素）。即使被證明的計算中出現的所有值都很小，這些隨機場元素也會很大。

相比之下，Lasso 和 Jolt 僅要求證明者提交較小的值（Lasso 的證明者提交的值也比先前的查找參數少）。這極大地提高了基於 MSM 的方案的性能。至少，Lasso 和 Jolt 應該廢除這樣的觀念：在證明者性能很重要的情況下，社區應該放棄基於 MSM 的承諾。

#2 更簡單的指令集帶來更快的 zkVM。

只要每條指令的評估表是可分解的，Jolt 的（每條指令）復雜度僅取決於指令的輸入大小。Jolt 證實，令人驚訝的復雜指令是可分解的，特別是所有 RISC-V。

這與人們普遍認為的觀點相反，即更簡單的虛擬機 (zkVM) 必然會導致更小的電路和相關的更快的證明器（VM 的每一步）。這是特別簡單的 zkVM（例如 Cairo VM）背後的指導動機，它們是專門為 SNARK 友好而設計的。

事實上，對於更簡單的虛擬機，Jolt 為證明者實現了比之前的 SNARK 更低的承諾成本。例如，對於 Cairo VM 執行，SNARK 證明者在 VM 的每個步驟中提交 51 個字段元素。Cairo 部署的 SNARK 當前在 251 位字段上工作（63 位是 SNARK 可以使用的字段大小的硬下限）。Jolt 的證明器致力於 RISC-V CPU 的每步約 60 個字段元素（定義超過 64 位數據類型）。考慮到提交的字段元素很小的事實後，Jolt 證明者的成本大致相當於提交 6 個隨機 256 位字段元素的成本。

＃ 3 將大型計算分解為小塊不會造成性能損失。

基於這種觀點，當今的項目將任何大電路分解成小塊，分別證明每個塊，並通過 SNARK 遞歸聚合結果。這些部署使用這種方法來緩解流行 SNARK 中的性能瓶頸。例如，基於 FRI 的 SNARK 需要接近 100 GB 的證明空間，即使對於小型電路也是如此。它們還需要 FFT，這是一種超线性運算，如果 SNARK“同時”應用於大型電路，則可能成為瓶頸。

現實情況是，一些 SNARK（例如 Lasso 和 Jolt）表現出規模經濟（而不是當前部署的 SNARK 中的規模不經濟）。這 意味着被證明的語句越大，相對於直接證人檢查（即在不保證正確性的情況下評估證人電路所需的工作），證明者开銷越小。在技術層面，規模經濟來自兩個地方。

n 大小的 MSM 的 Pippenger 加速：相對於樸素算法的 log( n ) 因子改進。n 越大，改善越大。

在 Lasso 等查找參數中，證明者支付“一次性”成本，該成本取決於查找表的大小，但與查找的值的數量無關。一次性證明者成本在對表的所有查找中進行攤銷。更大的塊意味着更多的查找，這意味着更好的攤銷。

當今處理大型電路的流行方法是將事物分解成盡可能小的部分。每個部分的大小的主要限制是它們不能太小，以至於遞歸聚合證明成為證明者的瓶頸。

Lasso 和 Jolt 提出了一種本質上相反的方法。人們應該使用具有規模經濟性的 SNARK。然後將大型計算分解為盡可能大的部分，並對結果進行遞歸。每個片段大小的主要限制是證明空間，它隨着片段變大而增長。

#4 高度約束對於高效的 SNARK 是必要的。

Jolt 使用 R 1 CS 作為其中間表示。在 Jolt 中使用“高度”或“自定義”約束沒有任何好處。Jolt 中的證明者成本大部分在於查找參數 Lasso，而不是證明將查找視為理所當然的結果約束系統的可滿足性。

Jolt 是通用的，因此它不會失去通用性。因此，它反駁了开發人員對設計高度約束（通常是手動指定）的強烈關注，以努力從當今流行的 SNARK 中擠出改進的性能。

當然，某些上下文仍然可能受益於高度或自定義約束。一個重要的例子是 Minroot VDF，其 5 度約束可以將承諾成本降低約 3 倍。

＃ 5 稀疏多項式承諾方案成本高昂，應盡可能避免。

這是針對最近引入的名為 CCS 的約束系統和支持它的 SNARK 的主要批評—— Spartan 和 Marlin ，CCS 是當今實踐中流行的所有約束系統的清晰概括。

這種批評是沒有根據的。事實上，Lasso 和 Jolt 的技術核心是 Spartan 中的稀疏多項式承諾方案——Spark。Spark 本身是將任何（非稀疏）多項式承諾方案通用轉換為支持稀疏多項式的方案。

Lasso 優化並擴展了 Spark，以確保證明者只承諾“小”值，但即使沒有這些優化，批評也是不合理的。事實上，Spartan 的證明者比 SNARK （例如避免稀疏多項式承諾的 Plonk）承諾更少的（隨機）字段元素。

Spartan 的方法具有額外的性能優勢，特別是對於具有重復結構的電路。對於這些電路，加法門不會增加 Spartan 證明者的加密工作。這項工作僅隨着給定約束系統中變量的數量而增長，而不是隨着約束的數量而增長。與 Plonk 不同的是，Spartan 證明者無需提交同一變量的多個不同“副本”。

我們樂觀地認為 Lasso 和 Jolt 將極大地改變 SNARK 的設計方式，從而提高性能和可審計性。這是一種具有神奇能力的關鍵工具，可以最大限度地減少證明者的承諾成本。

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播信息之目的，不構成任何投資建議，如有侵權行為，請第一時間聯絡我們修改或刪除，多謝。