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

原文標題：Approaching the 'lookup singularity': Introducing Lasso and Jolt
編譯：倩雯，ChainCatcher

SNARK 是一種加密協議，它允許任何人向不信任的驗證者證明自己認識滿足某些屬性的"見證"（witness）。SNARK 在 Web3 中的一個突出應用是 L2 rollup 向 L1 的區塊鏈證明他們認識授權一系列交易的數字簽名，這樣簽名本身就不必由 L1 存儲和驗證，從而提升可擴展性。

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

雖然很多 SNARK 對證明者（prover）來說成本很低，但 SNARK 一般仍會在驗證計算中帶來約六個數量級的開銷。驗證者被迫承擔的額外工作是高度可並行化的，但一百萬倍的系數開銷嚴重限制了 SNARK 的應用。

性能更強的 SNARK 可以加快 L2 的速度，還能讓建構者解鎖尚未實現的應用。因此，我們推出了兩項相關的新技術：Lasso 是一種新的查找參數，可顯著降低證明者成本；Jolt 使用 Lasso 技術，為 zkVM 和其他前端設計提供了設計 SNARK 的新框架。它們共同提高了 SNARK 設計的性能、開發者體驗和可審計性，促進 web3 的建設。

與流行的 SNARK 工具鏈 halo2 中的查找參數相比，Lasso 初步實現已經證明速度提高 10 倍以上。我們預計，當 Lasso 代碼庫完全優化後，速度將提高約 40 倍。Jolt 包含基於 Lasso 的更多創新，我們希望它能實現與現有 zkVM 類似或更高的速度。

查找參數、Lasso和Jolt

SNARK 前端（SNARK frontend）是一種編譯器，可將計算機程序轉化為電路，並由 SNARK 後端攝取。電路是一種極其有限的計算模型，其中的原始運算僅僅是加法和乘法。

現代 SNARK 設計中的一個關鍵工具是查找參數（lookup argument），它是一種協議，允許不受信證明者以加密方式提交一個大型向量，然後證明該向量的每個條目都包含在某個預定表中。查找參數可以有效地處理那些無法通過少量加法和乘法自然計算的運算，從而有助於保持電路維持小型規模。

以太坊基金會的 Barry 就提出了一種設想，他認為如果我們可以實現"只使用查找參數就能高效地定義電路，就可以帶來更簡化的工具和電路"，也就是實現"查找奇點"，此時我們已經可以"設計出只執行查找的電路時"，這種方式在幾乎所有方面這優於比多項式約束。

這一願景與當今的工作方式形成了鮮明對比，在當今的工作方式中，開發人員部署 SNARK 的方法是使用特異性領域特定語言（將程序編譯為多項式約束）編寫程序，或者直接手動編碼約束。這種工具鏈耗費大量人力物力，導致安全關鍵漏洞的概率很高。即使用複雜的工具和電路，SNARK 仍然很慢，這限制了它的應用。

Lasso 和 Jolt 解決了所有三個關鍵問題：性能、開發人員體驗和可審計性。我相信，它們將共同實現查找奇點的願景。Lasso 和 Jolt 還讓我們對 SNARK 設計中的許多公认真題進行反思。在介紹了一些必要的背景知識後，本篇文章將重新審視有關 SNARK 性能的一些常見觀點，並解釋如何根據 Lasso 和 Jolt 等創新技術更新這些觀點。

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

大多數 SNARK 後端都讓驗證者對電路中每個門的值進行加密承諾，使用的方法稱為多項式承諾方案。然後，證明者證明所承諾的值符合見證檢查程序的正確執行。

我將來自多項式承諾方案的證明者工作稱為承諾成本（commitment cost）。SNARK 還有額外的證明者成本，這些成本來自多項式承諾方案之外。但承諾成本往往是瓶頸所在。Lasso 和 Jolt 的情況也是如此。在設計 SNARK 時，如果承諾成本不構成主要的證明者成本，這不意味著多項式承諾方案的成本低，反而意味著其他費用高於它們應有的水平。

直觀地說，承諾的目的是通過加密方法安全地增加證明系統的簡潔性。當證明者對一個大的值向量做出承諾時，這就類似於證明者把整個向量發送給驗證者，就像微小證明系統（trivial proof system）把整個見證發送給驗證者一樣。承諾方案無需強制驗證者實際接收整個見證就能實現這一點，這意味著在 SNARK 設計中，承諾方案的目的是控制驗證者成本。

但這些加密方法對證明者來說非常昂貴，尤其是與 SNARK 在多項式承諾方案之外使用的信息論方法相比。信息論方法只依賴於有限域運算。而一次字段運算的速度要比對任意字段元素進行承諾所需的時間快上幾個數量級。

根據所使用的多項式承諾方案，計算承諾涉及多幂乘（也稱為多標量乘法或 MSM），或 FFT 和梅克爾散列。Lasso 和 Jolt 可以使用任何多項式承諾方案，但在使用基於 MSM 的方案，比如 IPA/Bulletproofs、KZG/PST、Hyrax、Dory 或 Zeromorph 時會產生額外的成本。

Lasso和Jolt為何重要？

Lasso 是一種新的查找參數方法，與之前的方法相比，證明者承諾的值更少、更小。根據具體情況，這可以將速度提高20倍或更多，其中2倍到4倍來自於更少的承諾值，另外10倍是因為在 Lasso 中，所有承諾值都很小。與之前的許多查找參數不同，Lasso（和Jolt）還避免了 FFT，因為 FFT 需要大量空間，在大型實例中可能會導致瓶頸。

此外，只要表格是"結構化"的（從精確的技術意義上說），Lasso 甚至可以應用於巨大的表格（比如規模達到2128）。表格規模太大時，任何人都無法明確地將其具體化，但 Lasso 只對它實際訪問的表格元素付出成本。值得關注的另一點是，如果表是結構化的，那麼任何一方都不需要對表中的所有值進行加密承諾。

Lasso 利用了兩種不同的結構概念：可分解性和 LDE 結構。可分解性大致是指，通過對非常小規模的表少量查找，就能完成對表的一次查找。這是比 LDE 結構更嚴格的要求，但Lasso在應用於可分解的表時十分高效。

Jolt

Jolt（Just One Lookup Table"只需一個查找表"）是一個新的前端，基於 Lasso 使用巨型查找表的功能。Jolt 針對虛擬機/CPU 抽象，也稱為指令集架構（ISA）。支持這種抽象 SNARK 被稱為 zkVM。例如受 RISC-Zero 項目支持的RISC-V指令集（包括乘法擴展的指令集）。這是一種流行的開源 ISA，由計算機體系結構社區開發，在開發時沒有考慮 SNARK。

對於每一條 RISC-V 指令 fi，Jolt 的主要想法是創建一個查找表，其中包含 fi 的整個評估表。因此，如果 fi 接收兩個 32 位輸入，該表將有 264 個條目，其中(x,y)'th的條目為 fi(x,y)。如果我們考慮的是 64 位而不是 32 位數據類型的指令，那麼每條指令的表的大小將是 2128 而不是 264。

基本上每一條 RISC-V 指令的查找表都是可分解的，並適用 Lasso。少數指令是通過應用其他指令的簡短序列來處理的。例如，除法指令的處理方法是讓證明者提交商和餘數，並檢查是否通過一次乘法和一次加法正確提供了商和餘數。

運行 T 步RISC-VCPU 的電路可按如下方式生成。對於 T 步中的每一步，電路都包含一些簡單的邏輯，以確定該步要執行的原始 RISC-V 指令fi，以及該指令的輸入 (x，y)。然後，電路只需執行一次查找，揭示相關表中的第 (x,y) 項，即可執行 fi。更準確地說，Jolt 只考慮了一個表，它由每條指令的表連接而成，因此被稱為"只需一個查找表"。

重新審視SNARK設計中的公认真理

Lasso 和 Jolt 還顛覆了 SNARK 設計中幾項公认真理。

1.SNARK 過度域（over large field）是一種浪費。每個人都應該使用 FRI、Ligero、Brakedown或其變體，因為這些技術避免了椭圆曲线技術，而椭圆曲线技術通常適用於較大的字段。

這裡的字段大小大致可以理解為 SNARK 證明中出現數字的大小。由於大數的加法和乘法開銷很大，因此大字段上的 SNARK 會造成浪費，這意味著我們應盡可能設計永遠不會出現大數的協議。基於 MSM 的承諾使用椭圆曲线，而椭圆曲线通常定義在大字段上（大小約為 2256），因此椭圆曲线的性能較差。

我之前有討論過使用小字段是否合理在很大程度上取決於應用。Lasso 和 Jolt 表明，即使使用基於 MSM 的承諾方案，證明者的工作也幾乎不受字段大小的影響。這是因為，對於基於 MSM 的承諾，承諾值的大小比這些值所在字段的大小更重要。

現有的 SNARK 會讓證明者提交許多隨機字段元素。例如，一個名為 Plonk 的證明者會對每個電路門提交約7個隨機字段元素（以及額外的非隨機字段元素）。即使被證明的計算中出現的所有值都很小，這些隨機字段元素也會很大。

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

2.指令集更簡單，zkVM速度更快。

只要每條指令的評估表都是可分解的，Jolt（每條指令）的複雜度就只取決於指令的輸入大小。Jolt 證明了巨大的複雜指令都是可分解的，尤其是所有 RISC-V 指令。

這與人們普遍認為更簡單的虛擬機（zkVM）必然導致更小的電路和相關的更快證明器（虛擬機的每一步）的看法相反。這一觀點一直指導著極簡zkVM（如 Cairo VM）的設計。

事實上，對於較簡單的虛擬機，Jolt 比之前的 SNARK 更能降低證明者的承諾成本。例如，對於 Cairo VM 執行的證明者在虛擬機的每一步都要提交 51 個字段元素。Cairo VM 部署的 SNARK 目前處於 251 位的字段（63 位是 SNARK 可以使用字段大小的硬下限）。Jolt 的驗證者在 RISC-VCPU 上每步提交約 60 個字段元素（定義為 64 位數據類型）。考慮到提交的字段元素較少，Jolt 驗證者的成本大約相當於提交 6 個 256 位隨機字段元素的成本。

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

基於這種觀點，如今的項目會將大電路分解成小塊，分別證明每一塊，並通過 SNARK 遞歸將結果匯總。這些部署使用這種方法來緩解多數 SNARK 的性能瓶頸。例如，基於 FRI 的 SNARK 即使對小型電路也需要近 100 GB的證明器空間。它們還需要 FFT，這是一種超線性操作，如果 SNARK 一次性應用於大型電路，這種操作就會成為瓶頸。

現實情況是，一些 SNARK（如 Lasso和Jolt）表現出規模經濟性（而目前部署的SNARK不具有規模經濟性）。這意味著被證明的語句越大，證明者的開銷相對見證檢查（witness checking，即在不保證正確性的情況下評估見證電路所需的工作）就越小。在技術層面上，規模經濟來自兩個方面：

1）大小為n的MSM的皮彭格加速度（Pippenger speedup）比原始算法提高了log(n)倍。n越大，提升越大。

2）在Lasso等查找參數中，證明者需要支付一次性成本，該成本取決於查找表的大小，但與查找值的數量無關。證明者的一次性成本在對表的所有查詢中攤銷。更大的數據塊意味著更多的查找次數，也就意味著更好的攤銷。

如今，處理大型電路的主流方法是將電路分成盡可能小的塊。對每塊電路大小的主要限制是，它們不能太小，否則遞歸聚合證明會成為證明者的瓶頸。

Lasso和Jolt提出了一種基本相反的方法。我們應該使用具有規模經濟性的SNARK。然後將大型計算分成盡可能大的部分，並對結果進行遞歸。每個計算片段大小的主要限制因素是證明者空間，隨著計算片段的增大，證明者空間也會隨之增大。

4.高階約束是高效 SNARK 的必要條件。

Jolt 使用 R1CS 作為中間表示。在 Jolt 中，使用"高階"或"自定義"約束沒有任何好處。在 Jolt 中，證明者的大部分成本都在查找參數 Lasso 上，而不是在證明約束系統的可滿足性上（這一系統將查找選項視為理所應當）。

Jolt 是通用型的，因此不會喪失通用性。因此，開發人員在設計高度約束（通常是手動定制）時，為了從當今流行的 SNARK 中榨取更高的性能，把重點放在了設計高度約束上，Jolt正好與之相反。

當然，在某些情況下，高程度或自定義約束條件仍會有所助益。一個重要的例子是 Minroot VDF ，對它來說，5 級約束可以將承諾成本降低約3倍。

5.稀疏多項式承諾方案（Sparse polynomial commitment ）耗資巨大，應盡可能避免。

真一批評主要針對最近推出的名為 CCS 和支持該系統的 SNARK： (Super-)Spartan 和 (Super-)Marlin。CCS 是對當今實踐中流行的所有約束系統的簡潔概括。

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

Lasso 對 Spark 進行了優化和擴展，以確保證明者只提交"小"值，但即使沒有這些優化，這種批評也是沒有道理的。事實上，Spartan 的證明者比 SNARK（如 Plonk 等避免稀疏多項式承諾的SNARK）相比，Spartan 的證明者承諾的（隨機）字段元素更少。

Spartan 的方法具有額外的性能優勢，特別是對於具有重複結構的電路。對於這些電路，添加門並不會增加 Spartan 驗證者的加密工作量。這種工作量只會隨著給定約束系統中變量數量的增加而增加，而不會隨著約束數量的增加而增加。而且與 Plonk 不同的是，Spartan 驗證者無需對同一變量的多個不同"副本"做出承諾。

結語

我們相信，Lasso 和 Jolt 將大大改變 SNARK 的設計方式，從而提高性能和可審計性。本系列的後續文章將深入探討 Lasso 和 Jolt 的工作原理。