原文標題：《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 步驟計算中，主要的承諾成本如下。

首先，對總共約 200T 位元組的資料套用加法 FFT。更確切地說，Ligero/Brakedown 證明者執行O(√T) 個大小為O(√T) 的獨立FFT（這涉及的總工作量較少，且能更好地並行化，而不是執行長度為O(T) 的單一FFT）。其次，使用標準雜湊函數如 Keccak 或 SHA2 對大約 200T 位元組進行雜湊。

經驗上，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/SHA3 是一個明顯的選擇，因為它是NIST 標準、以太坊預編譯和Type-1 zkEVM 的關鍵瓶頸。 SHA3 是官方的 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 更少的域元素進行承諾。 （有關這如何使證明者受益的詳細信息，詳情請參考 Q9。）總的來說，Grøstl 應該比 Keccak 更適合（遞歸）SNARKs，因為它在證明者和晶片上都更快。

D&P 的 SNARKs 與 Keccak 和 Grøstl 無關。這些技術應該適用於許多其他雜湊函數。例如，D&P 認為 SHA2 也應該和 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 的改進，情況相反了（除了在本地定義在大域上的情況）。

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

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

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

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

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

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

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

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

A：是的。

Q7：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 的大多數調用會分期償還在許多承諾的多項式上的評估證明的成本。

Q8：你能概述一下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 的實際方法避免了對外部碼字的每個解包符號應用內碼的成本。

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

Q10：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[2k] 算術，即使對於 k > 8 也是如此。

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

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

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

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

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

A：是的，這是一個潛在的挑戰，但我相信能夠找到解決方案。

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

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

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

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

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

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

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

「原文連結」

歡迎加入律動 BlockBeats 官方社群：

Telegram 訂閱群：https://t.me/theblockbeats

Telegram 交流群：https://t.me/BlockBeats_App

Twitter 官方帳號：https://twitter.com/BlockBeatsAsia