a16z：Lasso+Jolt如何實現更高效的SNARK系統？

2023-11-21 11:11:13

原文標題：《A technical FAQ on Lasso, Jolt, and recent advancements in SNARK design》

原文作者： Justin Thaler

原文編譯：Luccy，BlockBeats

編者按： 11 月 20 日， Ulvetanna 的 Ben Diamond 和 Jim Posen（D&P）發布了一篇論文，改進了基於求和檢查的多項式 IOPs 和結合更快的證明者、更大證明的承諾方案 Ligero /Brakedown，並將其與基於 sum-check 的 SNARKs（如 Lasso）集成在一起。a16z 的研究合夥人 Justin Thaler 對該技術進行了深入解析後，各研究員對文章內容提出疑問。

相關閱讀：《a16z：Lasso+Jolt，快速承諾的嶄新前景》

這篇 FAQ 整合了 13 個問題，回答包括 Jolt Prover 性能、D&P 選擇 Keccak 和 Grøstl 哈希函數的原因，以及對基於哈希的承諾方案安全性等多方面問題。此外，該篇回答中還涵蓋了 Lasso 和 Jolt 的基礎關系、使用 Reed-Solomon 碼的性能優勢、Ligero/Brakedown 相對於 FRI 的優勢，以及 D&P 承諾 GF[ 2 ] 元素經濟性的解釋。

討論焦點包括整個計算的布爾電路實現、特徵二字段的優勢，以及通過遞歸組合 SNARK 證明和結合 D&P 承諾方案與基於 elliptic-curve 的 SNARK 的技術和成本問題。最後，文章還提出了使用 D&P 的承諾方案的 SNARK 是否可以與折疊方案（如 Nova）結合使用的問題。這些問題的深入研究有望促進該領域的技術創新和進一步改進。

Q1：相對於 RISC-V 程序的本機執行，一旦 Jolt 被重新實現以使用 D&P 的承諾，您認為 Jolt prover 的速度會有多快？

A：這裏提供一個粗糙且推測性的估計。Jolt prover 預計每個 RISC-V CPU 的步驟將承諾約 800 位的數據，使用 32 位數據類型和乘法擴展。需要注意兩點：首先，某些 RISC-V 指令通過多個僞指令處理。例如，除法指令通過讓 prover 提供商和余數，並通過乘法、加法和不等式檢查對兩者進行驗證。其次，在我們解析 GF[ 2128 ] 的查找表分解後，這個數字估計可能會略有調整。

使用 D&P 的承諾方案，並假設遞歸不會成為瓶頸，在 T 步計算中，主要的承諾成本如下。

首先，對總共約 200 T 字節的數據應用加法 FFT。更確切地說，Ligero/Brakedown 證明者執行 O(√T) 個大小為 O(√T) 的獨立 FFT（這涉及的總工作量較少，且能更好地並行化，而不是執行長度為 O(T) 的單個 FFT）。其次，使用標准哈希函數如 Keccak 或 SHA 2 對大約 200 T 字節進行哈希。

經驗上，D&P 發現 FFT 和哈希在證明者時間中大致相等。

使用 Keccak 哈希，每字節約需要 70 個 RISC-V 周期的估算表明，這些操作將比僅運行未經證明的 RISC-V 程序慢約 30, 000 倍。換句話說，為了證明 Jolt 證明者正確運行了一個 RISC-V 程序Ψ，證明者本身（在 RISC-V 中實現）將需要至少比Ψ本身多 20, 000 倍的周期。

這些承諾成本足夠「快」，表明證明者的瓶頸可能在於其在總檢查協議中執行的有限域操作，即使考慮到小特徵域的優化。因此，粗略估計，我猜測 Jolt 證明者（在 RISC-V 中實現）將比僅運行 RISC-V 程序慢約 50, 000 倍。

整個計算有點兒荒謬：當 Jolt 部署時，證明者本身不太可能由 RISC-V 實現。但這確實給出了如何估算 zkVM 證明者开銷的大致思路。

盡管 50, 000 倍的減速看起來很大，但比我大約 18 個月前樂觀估計的 100 萬倍开銷要快 20 倍。這種改善的主要原因是由 Lasso 和 Jolt 解鎖的承諾數據較小（以及每個承諾值的較小大小）。其余的原因歸功於更好的承諾方案（例如，改進了使用快速哈希函數和在基於哈希的 SNARKs 中利用承諾值的小規模的能力）。

Q2：D&P 提供了 Keccak 和 Grøstl 的快速 SNARKs。為什么選擇這些哈希函數？還有哪些哈希函數適合這些技術？BlockBeats 注：Grøstl 是一個加密哈希函數

A： Keccak/SHA 3 是一個明顯的選擇，因為它是 NIST 標准、以太坊預編譯和 Type-1 zkEVM 的關鍵瓶頸。SHA 3 是官方的 NIST 標准，Keccak 是以太坊預編譯，它們在與 SNARK 成本無關。

D&P 考慮了 Grøstl，因為它應該導致更快的證明者，同時保持 Keccak 的許多優點。特別是，Grøstl 經受了強大的密碼分析審查，盡管最終未被選中，但因為它進入了 NIST 的 SHA-3 競賽的最後一輪，並且使用了 AES S-box。由於 AES 加速指令 AES-NI，Grøstl 在英特爾芯片上甚至比 Keccak 運行得更快。

D&P 的證明者對於 Grøstl 應該比對於 Keccak 更快，因為 Grøstl 基本上是在 GF[ 28 ] 上本地定義的，這意味着 D&P 的證明者可以對比 Keccak 更少的域元素進行承諾。（有關這如何使證明者受益的詳細信息，詳情請參考 Q 9 。）總的來說，Grøstl 應該比 Keccak 更適合（遞歸）SNARKs，因為它在證明者和芯片上都更快。

D&P 的 SNARKs 與 Keccak 和 Grøstl 無關。這些技術應該適用於許多其他哈希函數。例如，D&P 認為 SHA 2 也應該和 Keccak 一樣好，但尚未詳細研究過。

Q3：我以為 Lasso/Jolt 是針對 elliptic-curve 基礎的承諾方案？

A：不，Lasso 和 Jolt 並不專門針對基於 curve 的承諾方案。但在幾個月前的情況下，與之前的工作相比，它們的優勢在與基於 curve 的承諾結合使用時最為明顯。這是因為當證明者不得不對隨機域元素進行承諾時，基於 curve 的承諾支付了特別高的代價，因此 Lasso/Jolt 的新穎能力避免這一情況在這些承諾被使用時具有最引人注目的性能影響。

簡而言之，雖然以前沒有人設計過使用基於 curve 承諾的 SNARKs 以利用被承諾的小值，但在一定程度上，已經有了在小字段上工作的基於哈希的承諾利用了這一點。

但是，即使使用基於哈希的承諾，Lasso 和 Jolt 在兩個方面都比之前的工作有所改進。首先，D&P 表明，與先前已知的方式相比，基於哈希的承諾可以更強大地受益於只有小域元素被承諾。例如，而今天的承諾方案對於承諾 1 位值和 32 位值產生相同的證明者成本，使用 D&P 的方案，對於承諾 1 位值幾乎便宜了 32 倍。其次，Lasso 和 Jolt 不僅確保證明者只承諾小域元素，而且還確保證明者承諾的域元素比非基於求和檢查的 SNARKs 更少。事實上，在 Jolt 中，我們仔細計算了所有承諾域元素的總位復雜度，並確認它遠遠小於現有 zkVMs 中所做的工作。

幾個月前 Lasso/Jolt 發布時，另一個技術上的麻煩使我們突出了基於 curve 的承諾：唯一一個具有對數多項式證明大小的基於哈希的承諾方案，FRI，是針對單變量多項式的，而 Lasso/Jolt 使用的是多线性多項式。已知的幾種轉換將 FRI 調整為適用於多线性多項式的承諾方案，但這些轉換在證明者時間、證明大小或兩者方面增加了我們認為非常不可取的开銷。BaseFold 現在允許具有對數多項式證明大小的「直接」多线性承諾，盡管由此產生的證明速度比 Brakedown 的慢，而且證明比 FRI 的大。

與 FRI 不同，Ligero/Brakedown 承諾方案直接應用於多线性多項式，並且具有非常快速的證明者。但以前，應用遞歸以降低其證明大小很難，因為驗證者執行大量哈希操作，使得遞歸昂貴。通過為哈希提供更快的 SNARKs，D&P 的工作將大大降低這種遞歸的成本。

Q4：你不是說基於 curve 的承諾方案比哈希基礎的方案更快（當只承諾小值時，如 Lasso/Jolt）嗎？這不是與你對 D&P 的 SNARKs 的認可相矛盾嗎？

A：首先，正如我之前所說，有一些重要的 SNARK 應用場景，哈希基礎的 SNARKs 明顯不是性能最佳的選擇，因為在 elliptic-curve 群的基礎域上工作是有意義的。在使用這些域時，基於 curve 的承諾更快。證明關於 elliptic-curve 密碼系統的任何陳述（包括關於 ECDSA 數字籤名授權區塊鏈交易的知識）都屬於這一類別。

其次，即使在合理使用小特徵域的應用中，基於哈希的方案與基於 curve 的方案的性能比較也很復雜。例如，它在很大程度上取決於基於哈希的方案中使用的哈希函數有多快。今天，許多（但不是所有）項目使用較慢的哈希函數，如 Poseidon，以實現遞歸。使用這樣的哈希函數，基於哈希的方案在承諾小值時（如 Lasso/Jolt）明顯比基於 curve 的方案慢。即使使用快速的哈希函數，它們是否更快並不明確（正如我之前的評論所述）。

但是，D&P 通過加速基於哈希的承諾，使其在使用特徵為 2 的域時更為高效，並允許證明者更好地利用承諾值的小規模，與現有的基於哈希的方案（如 FRI）相比。因此，我目前的期望是，在特徵為 2 的域上，Ligero/Brakedown 將是前進的方式，除非證明與其他有限域上的本地定義。

總之，直到今天，人們普遍認為基於哈希的承諾方案比基於 curve 的方案更快的主要原因是，像 Plonk 這樣的流行 SNARKs 要求證明者承諾隨機的域元素，而不是小的域元素，而在這種情況下，基於 curve 的承諾方案非常慢。Lasso 和 Jolt 表明，證明者無需承諾隨機的域元素。在這種情況下，比較至少更為細致。直到今天，基於 curve 的方案實際上更快，但有了 D&P 的改進，情況相反了（除了在本地定義在大域上的情況）。

Q 5 ：你不是說基於哈希的承諾方案的安全性較低嗎？

A：像 FRI 或 Ligero/Brakedown 這樣的基於哈希的承諾方案本身並沒有不安全的地方。但是，項目普遍優先考慮性能而不是安全性，通過在已知攻擊接近可行的配置上部署 FRI，並假設對 FRI 的這些已知攻擊恰好是最優的。

Ligero/Brakedown 承諾方案的一個好處是，關於 FRI 的主要猜想，即在約翰遜界之外的鄰近參數下的猜想安全性並不相關，因此 SNARK 設計者沒有借此猜想基於安全性的誘因。

同樣，我長期以來一直對表面上「SNARK 友好」的哈希函數（如 Poseidon）在 SNARK 部署中的使用感到擔憂。與標准哈希函數如 Keccak 相比，這些哈希函數的安全性（即使是那些存在時間最長的）受到的審查遠遠不夠。

在上述兩種情況中，我認為項目一直在為掩蓋當今 SNARK 性能缺陷而危及安全性。消除這些做法的最簡單方法就是簡單地开發性能更好的 SNARKs。

相關地，我認為目前手工設計「SNARK 友好」虛擬機（VMs）和實現這些 VMs 的約束系統的做法是一個重大的安全問題（以及對开發者資源的巨大消耗），因為設計約束系統和從高級語言开發新編譯器到自定義 VMs 的匯編代碼具有易出錯的特性。我希望 Jolt 通過展示標准指令集確實同樣友好於 SNARK，從而使這種做法過時，並消除手工設計實現這些指令集的約束系統的任何需要或激勵。

消除具有負面安全影響的做法的方法是提出更高性能的 SNARKs，使該做法變得無關緊要。

Q 6 ：D&P 在他們實現的多項式承諾方案中使用了 Reed-Solomon 碼，但 Brakedown 可以使用任何碼。探索其他碼以尋求可能的性能優勢是否值得？

A：是的。

Q 7 ：Ligero/Brakedown 在哪些方面對證明者更有利，而不同於 FRI？

A： D&P 顯著提高的在承諾非常小的值時的證明者時間是 Ligero/Brakedown 獨有的，至少目前是如此。此外： D&P 不僅在承諾小值時改進了證明者時間，還改進了證明者空間。這是一個主要瓶頸，特別是對於基於哈希的 SNARKs。例如， Polygon 的 zkEVM 證明者今天需要 250 多 GB，以證明一個處理大約 1000 萬 gas 的交易批處理的電路。

在使用糾錯碼方面，Ligero/Brakedown 具有更大的靈活性。實際上，通過在 Ligero/Brakedown 內部使用串聯碼，可以簡單地獲得 D&P 在承諾小值方面的許多改進。

當使用 Reed-Solomon 碼時，Ligero/Brakedown 的證明者執行許多小 FFT 而不是一個大 FFT。這在 FFT 運行時間上節省了一倍，更適合並行化。

在技術層面上，FRI 還需要同時進行 FFT 和 IFFT（從技術層面上看，這是因為 FRI 實際上需要在許多點上評估承諾的多項式）。Ligero/Brakedown 的證明者可以跳過 IFFT（在技術層面上，跳過 IFFT 源於 Ligero/Brakedown 在選擇糾錯碼方面的卓越靈活性）。如果使用「Reed-Solomon 膨脹因子」為 2 （這是優化證明者時間的膨脹因子），這可以在證明者時間上再節省 33 ％。

Ligero/Brakedown 的評估證明不需要證明者執行額外的 Merkle 哈希。但 FRI 需要，盡管 FRI 的大多數調用會分期償還在許多承諾的多項式上的評估證明的成本。

Q 8 ：你能概述一下 D&P 如何確保承諾 GF[ 2 ] 元素比承諾 GF[ 2 ^ 2 ] 元素更便宜，而後者比承諾 GF[ 2 ^ 4 ] 元素更便宜，依此類推嗎？

A：證明者用 D&P 的承諾方案承諾一堆值所需的時間大致僅取決於指定這些值所需的總位數，其中 b 位用於指定在 0 和 2b 之間的值。D&P 的 SNARKs 中的其他證明者成本確實會隨着用於編碼這些位的場元素數量的增加而增加（有關詳細信息，請參見下面的＃ 9）。以下是 D&P 如何實現這一點。

Brakedown 的多項式承諾方案使用任何所需的糾錯碼對要承諾的值的子向量進行編碼。假設要承諾的一堆值在 GF[ 2 ] 中，但我們希望編碼本身在更大的域 GF[ 2 ^ 16 ] 上運行。有很多技術原因我們希望這樣做，事實上，如果我們想將某些編碼應用於長度最多為 216 的向量，這是必要的。

為了實現這一點，我們可以簡單地使用碼串聯，這涉及將所有 GF[ 2 ] 值分成大小為 16 的塊，並將每個 16 個 GF[ 2 ] 值的塊「打包」到單個 GF[ 2 ^ 16 ] 場元素中。這將減少要承諾的場元素數量的 16 倍。然後，我們可以應用在域 GF[ 2 ^ 16 ] 上運行的任何糾錯碼，這稱為「外碼」。然後，得到的碼字的每個符號可以「解包」為十六個 GF[ 2 ] 元素，並使用在 GF[ 2 ] 上定義的「內碼」對結果進行編碼。

有效地說，串聯方法通過 16 倍降低了承諾向量的長度（以場元素數量為度量），但需要證明者執行打包和解包操作，以及對外部碼字的每個（解包的）符號應用內碼。

這種簡單的方法，即使用串聯碼應用 Brakedown，已經實現了 D&P 工作的許多好處。但是 D&P 採用了一種不同的方法，導致證明者的速度更快（代價是證明略大）。例如，D&P 的實際方法避免了對外部碼字的每個解包符號應用內碼的成本。

Q 9 ：由於 D&P 的承諾方案使得承諾 { 0, 1 } 中的值非常便宜，為什么不讓證明者只承諾在計算中出現的所有值的位分解呢？也就是說，為什么不使用布爾電路實現整個計算，並讓 SNARK 為電路中的每個輸入位和門分配一個「完整」的場元素呢？

A：在他們針對 Keccak 的 SNARK 中，D&P 確實讓證明者只承諾 { 0, 1 } 中的值，但這在一般情況下不一定是個好主意。

的確，D&P 的承諾時間大致與所有承諾值的位復雜度之和成正比，而與這些值分布在多少場元素上無關（這就是為什么在 Keccak 的 SNARK 中只對一位值進行承諾是個合理的主意）。

然而，這並不意味着所有的成本都與承諾的場元素數量無關。特別是，承諾方案的評估證明的大小與承諾場元素的數量（的平方根）成正比。

另一個與承諾的場元素數量成正比的成本是在 D&P 的 SNARK 中的求和檢查協議的一些應用中需要求和的項的數量。粗略地說，承諾 x 倍的場元素意味着求和檢查證明需要求和 x 倍多的項。有一些優化可用於減輕這種开銷，但這種減輕並不完美。也就是說，與將這些值打包成單個 x 位場元素後再進行承諾相比，求和檢查證明很可能仍然較慢，即使是 x 個一位值。

D&P 通過提供基於求和檢查的協議，將許多一位值在這些值被承諾後打包成單個場元素，以減輕承諾許多一位值的後一成本。這使得他們在術語上避免了為許多承諾的值支付太多的求和檢查證明時間的代價，同時仍然能夠享受它們的好處（特別是一旦進行了位分解的承諾，通過求和檢查證明時，某些操作如按位與在被證明時不會產生任何額外的承諾成本）。

Q1 0 ：D&P 利用特徵為二的字段的具體優勢是什么？

A：有很多，這裏舉例一部分。

D&P 大量利用了塔場構造。在特徵為二的場的背景下，這指的是構建 GF[ 22 ] 作為 GF[ 2 ] 的二次擴展，然後構建 GF[ 24 ] 作為 GF[ 4 ] 的二次擴展，然後構建 GF[ 28 ] 作為 GF[ 24 ] 的二次擴展，依此類推。特別是對於特徵為二的場，已知存在非常高效的塔構造。

求和檢查協議計算多變量多項式 g 的∑x∈ 0, 1 ^n g(x)。布爾超立方體 { 0, 1 }n（及其子立方體）的大小是 2 的冪次方，因此子場與子立方體很好地對齊。D&P 利用這一點，使得將許多小場元素打包到一個更大的擴展場的單個元素中變得容易。

D&P 目前在 Ligero/Brakedown 多項式承諾方案中使用 Reed-Solomon 編碼。高效的 Reed-Solomon 編碼需要加法 FFT，在特徵為二的場中非常有效，但在其他場中則效果不佳。然而，使用其他編碼可以完全避免對 FFT 的需求。

特徵為二的場在實際硬件中得到很好的處理。現實世界的計算機基於 2 的冪次方大小的數據類型。您可以在寄存器、緩存行等中完美地容納最大的信息，無需填充。Intel 甚至在芯片中內置了用於在 GF[ 28 ] 中執行特別快速的算術的原始指令（Galois Field New Instructions [GFNI]）。當使用塔構造時，這可以用來實現非常快速的 GF[ 2 k] 算術，即使對於 k > 8 也是如此。

Q1 1 ：難道通過使用 D&P 的承諾方案遞歸地將 SNARK 證明與自身組合，就沒有 SNARK 證明會變得小的限制嗎？

A：是的，使用 Ligero/Brakedown 承諾的 SNARK 的「遞歸閾值」相對較高。遞歸閾值指的是證明的大小，即通過遞歸地將基於 Brakedown/Ligero 的 SNARK 應用於驗證器，無法再產生更短的證明。我預計遞歸閾值在幾 MB 的數量級上。

如果希望獲得更小的證明，我認為可以通過與其他更小證明的 SNARK 進行組合來實現，詳情參考 Q1 2 。如果這個假設最終被證明是錯誤的，不應視為 Binius 的失敗，而應視為對當今流行的 SNARK 的可擴展性的指責。如果它們不能在合理的時間內證明幾 MB 的數據已被哈希，我們怎么能說它們具有可擴展性呢？

無論如何，除了降低證明大小之外，快速遞歸組合還有其他重要原因。最重要的是，它是控制證明空間需求的關鍵工具。由於（非遞歸）SNARK 對於證明者來說佔用空間很大，人們會將大型計算分解成小塊，分別證明每個塊，並使用遞歸證明將這些塊「鏈接」在一起。D&P 對於標准哈希函數（如 Keccak）的快速 SNARK 使得這種遞歸證明能夠迅速完成，即使證明的大小有些大。

Q1 2 ：假設您想結合 D&P 的承諾方案與基於 elliptic-curve 的 SNARK（例如 Plonk 或 Groth 16）以降低驗證者在鏈上發布證明前的成本。這難道不需要證明涉及「非本地」字段算術嗎？因為 D&P 的驗證器操作在 GF[ 2 ^ 128 ] 上，而基於 curve 的 SNARK 使用大型素數階字段。

A：是的，這是一個潛在的挑战，但我相信能夠找到解決辦法。

有一種可能性是首先與使用基於哈希的多項式承諾方案的 SNARK 進行組合，該方案具有更短的證明（可能是 FRI，轉換為多线性多項式承諾方案，或者 BaseFold），然後再與基於 curve 的 SNARK 進行組合。請注意，FRI 可以在特徵為二的字段上本地運行，事實上，在原始的 FRI 論文中就考慮過這種情況。目前流行的 SNARK 對使用這些字段的限制來自於非基於求和檢查的多項式 IOPs 的使用，與 FRI 本身不同。

這並不能消除非本地字段算術的問題，但可以在很大程度上緩解，因為對於足夠大的多項式，FRI 驗證器執行的總操作較少，尤其是比 Ligero/Brakedown 驗證器執行的字段操作較少。

Q1 3 ：使用 D&P 的承諾方案的 SNARK 是否可以與 Nova 等折疊方案結合使用？

A：這將遇到與 Q1 2 相同的問題，即折疊方案使用 elliptic-curve，通常定義在大型素數階字段上，而 D&P 的承諾方案使用大小為 2 的冪的字段。

我預計在折疊方案方面會取得顯著的進展，並且它們將在未來的 SNARK 設計中發揮重要作用。然而，可能情況是它們與基於哈希的 SNARK 在非常小特徵的字段上並不很好地結合。

目前而言，應當在涉及本地定義在大字段上的語句，或者在 prover 空間至關重要的情況下使用基於 elliptic-curve 的承諾和折疊方案（像 Nova 這樣的折疊方案在 prover 空間方面遠遠優於其他 SNARK，大致因為它們可以將大型計算分解成比其他 SNARK 小得多的部分）。而在其他情況下，應該使用基於哈希的方案，尤其是在小特徵字段上使用。

同樣，未來折疊方案的進一步發展可能導致它們超越基於哈希的方案。實際上，Nova 在某些基准測試中已經比當前一代基於哈希的 SNARK 更快（盡管有很多聲稱當前基於哈希的 SNARK 比基於 curve 的更快的說法）。

原文鏈接