a16z：Lasso+Jolt如何實現更有效率的SNARK系統？
原文標題：《A technical FAQ on Lasso, Jolt, and recent advancements in SNARK design》
原文作者：Justin Thaler
原文編譯：Luccy，BlockBeats
編輯：11 月20 日，Ulvetanna 的Ben Diamond 和Jim Posen（DP）發布了一篇論文，改進了基於求和檢查的多項式IOPs 和結合更快的證明者、更大證明的承諾方案Ligero/Brakedown ，並將其與基於sum-check 的SNARKs（如Lasso）整合在一起。 a16z 的研究合夥人Justin Thaler 在這項技術進行了深入解析後，各研究員對文章內容提出疑問。
相關閱讀：《a16z：Lasso+Jolt，快速承諾的嶄新前景》
這篇FAQ 整合了13 個問題，答案包括Jolt Prover 效能、DP 選擇Keccak 和Grøstl 哈希函數的原因，以及對基於哈希的承諾方案安全性等多面向問題。此外，這篇回答中還涵蓋了Lasso 和Jolt 的基礎關係、使用Reed-Solomon 碼的性能優勢、Ligero/Brakedown 相對於FRI 的優勢，以及DP 承諾GF[ 2 ] 元素經濟性的解釋。
討論焦點包括整個計算的布林電路實現、特徵二字段的優勢，以及通過遞歸組合SNARK 證明和結合DP 承諾方案與基於elliptic-curve 的SNARK 的技術和成本問題。最後，文章也提出了使用DP 的承諾方案的SNARK 是否可以與折疊方案（如Nova）結合使用的問題。這些問題的深入研究有望促進該領域的技術創新和進一步改進。
Q1：相對於RISC-V 程式的本機執行，一旦Jolt 被重新實現以使用DP 的承諾，您認為Jolt prover 的速度會有多快？
A：這裡提供一個粗糙且推測性的估計。 Jolt prover 預計每個RISC-V CPU 的步驟將承諾約800 位的數據，使用32 位元資料類型和乘法擴展。需要注意兩點：首先，某些RISC-V 指令會透過多個偽指令處理。例如，除法指令透過讓prover 提供者和餘數，並透過乘法、加法和不等式檢查對兩者進行驗證。其次，在我們解析GF[ 2128 ] 的查找表分解後，這個數字估計可能會略有調整。
使用DP 的承諾方案，並假設遞迴不會成為瓶頸，在T 步驟計算中，主要的承諾成本如下。
首先，總共約200 T 字節的資料應用加法FFT。更確切地說，Ligero/Brakedown 證明者執行O(√T) 大小為O(√T) 的獨立FFT（這涉及的總工作量較少，且能更好地並行化，而不是執行長度為O(T) 的單一FFT）。其次，使用標準雜湊函數如Keccak 或SHA 2 對大約200 T 位元組進行散列。
經驗上，DP 發現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：DP 提供了Keccak 和Grøstl 的快速SNARKs。為什麼選擇這些哈希函數？還有哪些雜湊函數適合這些技術？ BlockBeats 註：Grøstl 是一個加密雜湊函數
A：Keccak/SHA 3 是一個明顯的選擇，因為它是NIST 標準、以太坊預編譯和Type-1 zkEVM 的關鍵瓶頸。 SHA 3 是官方的NIST 標準，Keccak 是以太坊預編譯，它們在與SNARK 成本無關。
DP 考慮了Grøstl，因為它應該導致更快的證明者，同時保持Keccak 的許多優點。特別是，Grøstl 經歷了強大的密碼分析審查，儘管最終未被選中，但因為它進入了NIST 的SHA-3 競賽的最後一輪，並使用了AES S-box。由於AES 加速指令AES-NI，Grøstl 在英特爾晶片上甚至比Keccak 運行得更快。
DP 的證明者對於Grøstl 應該比對於Keccak 更快，因為Grøstl 基本上是在GF[ 28 ] 上本地定義的，這意味著DP 的證明者可以對比Keccak 更少的領域元素進行承諾。 （有關這如何使證明者受益的詳細信息，詳情請參考Q 9 。）總的來說，Grøstl 應該比Keccak 更適合（遞歸）SNARKs，因為它在證明者和晶片上都更快。
DP 的SNARKs 與Keccak 和Grøstl 無關。這些技術應該適用於許多其他哈希函數。例如，DP 認為SHA 2 也應該和Keccak 一樣好，但尚未詳細研究。
Q3：我以為Lasso/Jolt 是elliptic-curve 基礎的承諾方案？
A：不，Lasso 和Jolt 並沒有專門針對基於curve 的承諾方案。但在幾個月前的情況下，與先前的工作相比，它們的優勢在與基於curve 的承諾結合時最為明顯。這是因為當證明者必須對隨機域元素進行承諾時，基於curve 的承諾支付了特別高的代價，因此Lasso/Jolt 的新穎能力避免這種情況在這些承諾被使用時具有最引人注目的性能影響。
簡而言之，雖然以前沒有人設計過使用基於curve 承諾的SNARKs 以利用被承諾的小值，但在一定程度上，已經有了在小字段上工作的基於哈希的承諾利用了這一點。
但是，即使使用基於哈希的承諾，Lasso 和Jolt 在兩個方面都比之前的工作有所改進。首先，DP 表明，與先前已知的方式相比，基於哈希的承諾可以更強大地受益於只有小域元素被承諾。例如，而今天的承諾方案對於承諾1 位值和32 位值產生相同的證明者成本，使用DP 的方案，對於承諾1 位值幾乎便宜了32 倍。其次，Lasso 和Jolt 不僅確保證明者只承諾小域元素，而且還確保證明者承諾的域元素比非基於求和檢查的SNARKs 更少。事實上，在Jolt 中，我們仔細計算了所有承諾域元素的總位複雜度，並確認它遠遠小於現有zkVMs 中所做的工作。
當Lasso/Jolt 在幾個月前發佈時，另一個技術上的麻煩使我們突出了基於curve 的承諾：唯一一個具有對數多項式證明大小的基於哈希的承諾方案，FRI，是針對單變量多項式的，而Lasso/Jolt 使用的是多線性多項式。已知的幾種轉換將FRI 調整為適用於多線性多項式的承諾方案，但這些轉換在證明者時間、證明大小或兩者方面增加了我們認為非常不可取的開銷。 BaseFold 現在允許具有對數多項式證明大小的「直接」多線性承諾，儘管由此產生的證明速度比Brakedown 的慢，而且證明比FRI 的大。
與FRI 不同，Ligero/Brakedown 承諾方案直接應用於多線性多項式，並且具有非常快速的證明者。但以前，應用遞歸以降低其證明大小很難，因為驗證者執行大量哈希操作，使得遞歸昂貴。通過為哈希提供更快的SNARKs，DP 的工作將大大降低這種遞歸的成本。
Q4：你不是說基於curve 的承諾方案比哈希基礎的方案更快（當只承諾小值時，如Lasso/Jolt）嗎？這不是與你對DP 的SNARKs 的認可相矛盾嗎？
A：首先，正如我之前所說，有一些重要的SNARK 應用場景，哈希基礎的SNARKs 明顯不是性能最佳的選擇，因為在elliptic-curve 群的基礎域上工作是有意義的。在使用這些網域時，基於curve 的承諾更快。證明關於elliptic-curve 密碼系統的任何陳述（包括關於ECDSA 數字簽名授權區塊鏈交易的知識）都屬於這一類別。
其次，即使在合理使用小特徵域的應用中，基於散列的方案與基於curve 的方案的效能比較也很複雜。例如，它在很大程度上取決於基於哈希的方案中使用的哈希函數有多快。今天，許多（但不是全部）項目使用較慢的哈希函數，如Poseidon，以實現遞歸。使用這樣的雜湊函數，基於哈希的方案在承諾小值時（如Lasso/Jolt）明顯比基於curve 的方案慢。即使使用快速的哈希函數，它們是否更快並不明確（正如我之前的評論所述）。
但是，DP 通過加速基於哈希的承諾，使其在使用特徵為2 的域時更為高效，並允許證明者更好地利用承諾值的小規模，與現有的基於哈希的方案（如FRI ）相比。因此，我目前的期望是，在特徵為2 的域上，Ligero/Brakedown 將是前進的方式，除非證明與其他有限域上的本地定義。
總而言之，直到今天，人們普遍認為基於哈希的承諾方案比基於curve 的方案更快的主要原因是，像Plonk 這樣的流行SNARKs 要求證明者承諾隨機的域元素，而不是小的域元素，而在在這種情況下，基於curve 的承諾方案非常緩慢。 Lasso 和Jolt 表明，證明者無需承諾隨機的領域元素。在這種情況下，比較至少更為細緻。直到今天，基於curve 的方案實際上更快，但有了DP 的改進，情況相反了（除了在本地定義在大域上的情況）。
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 ：DP 在他們實現的多項式承諾方案中使用了Reed-Solomon 碼，但Brakedown 可以使用任何碼。探索其他碼以尋求可能的效能優勢是否值得？
A：是的。
Q 7 ：Ligero/Brakedown 在哪些方面對證明者較有利，而不同於FRI？
A：DP 顯著提高的在承諾非常小的值時的證明者時間是Ligero/Brakedown 獨有的，至少目前是如此。此外： DP 不僅在承諾小值時改進了證明者時間，也改進了證明者空間。這是一個主要瓶頸，特別是對於基於哈希的SNARKs。例如，Polygon 的zkEVM 證明者今天需要250 多GB，以證明一個處理約1000 萬gas 的交易批次的電路。
在使用糾錯碼方面，Ligero/Brakedown 有更大的彈性。實際上，透過在Ligero/Brakedown 內部使用串聯碼，可以簡單地獲得DP 在承諾小值方面的許多改進。
當使用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 ：你能概述一下DP 如何確保承諾GF[ 2 ] 元素比承諾GF[ 2 ^ 2 ] 元素更便宜，而後者比承諾GF[ 2 ^ 4 ] 元素更便宜，依此類推嗎？
A：證明者用DP 的承諾方案承諾一堆值所需的時間大致只取決於指定這些值所需的總位數，其中b 位用於指定在0 和2b 之間的值。 DP 的SNARKs 中的其他證明者成本確實會隨著用於編碼這些位元的場元素數量的增加而增加（有關詳細信息，請參見下面的＃ 9）。以下是DP 如何實現這一點。
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，已經實現了DP 工作的許多好處。但DP 採用了不同的方法，導致證明者的速度更快（代價是證明略大）。例如，DP 的實際方法避免了對外部碼字的每個解包符號應用內碼的成本。
Q 9 ：由於DP 的承諾方案使得承諾{ 0, 1 } 中的值非常便宜，為什麼不讓證明者只承諾在計算中出現的所有值的位元分解呢？也就是說，為什麼不使用布林電路實現整個計算，並讓SNARK 為電路中的每個輸入位元和閘分配一個「完整」的場元素呢？
A：在他們針對Keccak 的SNARK 中，DP 確實讓證明者只承諾{ 0, 1 } 中的值，但這在一般情況下不一定是個好主意。
的確，DP 的承諾時間大致與所有承諾值的位元複雜度總和成正比，而與這些值分佈在多少場元素上無關（這就是為什麼在Keccak 的SNARK 中只對一位值進行承諾是個合理的主意）。
然而，這並不意味著所有的成本都與承諾的場元素數量無關。特別是，承諾方案的評估證明的大小與承諾場元素的數量（的平方根）成正比。
另一個與承諾的場元素數量成正比的成本是在DP 的SNARK 中的求和檢查協議的一些應用中需要求和的項的數量。粗略地說，承諾x 倍的場元素意味著求和檢查證明需要求和x 倍多的項。有一些優化可用於減輕這種開銷，但這種減輕並不完美。也就是說，與將這些值打包成單一x 位場元素後再進行承諾相比，求和檢查證明很可能仍然較慢，即使是x 個一位值。
DP 通過提供基於求和檢查的協議，將許多一位值在這些值被承諾後打包成單一場元素，以減輕承諾許多一位值的後一成本。這使得他們在術語上避免了為許多承諾的值支付太多的求和檢查證明時間的代價，同時仍然能夠享受它們的好處（特別是一旦進行了位元分解的承諾，通過求和檢查證明時，某些操作如按位與在被證明時不會產生任何額外的承諾成本）。
Q1 0 ：DP 利用特徵為二的字段的具體優勢是什麼？
A：有很多，這裡舉例一部分。
DP 大量利用了塔場構造。在特徵為二的場的背景下，這指的是建構GF[ 22 ] 作為GF[ 2 ] 的二次擴展，然後建構GF[ 24 ] 作為GF[ 4 ] 的二次擴展，然後建構GF[ 28 ] 作為GF[ 24 ] 的二次擴展，依此類推。特別是對於特徵為二的場，已知存在非常高效的塔構造。
求和檢查協議計算多變量多項式g 的∑x∈ 0, 1 ^ng(x)。布爾超立方體{ 0, 1 }n（及其子立方體）的大小是2 的冪，因此子場與子立方體很好地對齊。 DP 利用這一點，使得將許多小場元素打包到一個更大的擴展場的單個元素中變得容易。
DP 目前在Ligero/Brakedown 多項式承諾方案中使用Reed-Solomon 編碼。高效率的Reed-Solomon 編碼需要加法FFT，在特徵為二的場中非常有效，但在其他場中則效果不佳。然而，使用其他編碼可以完全避免對FFT 的需求。
特徵為二的場在實際硬體中得到很好的處理。現實世界的電腦是基於2 的冪大小的資料型態。您可以在寄存器、緩存行等中完美地容納最大的信息，無需填充。 Intel 甚至在晶片中內置了用於在GF[ 28 ] 中執行特別快速的算術的原始指令（Galois Field New Instructions [GFNI]）。當使用塔構造時，這可以用來實現非常快速的GF[ 2 k] 算術，即使對於k > 8 也是如此。
Q1 1 ：難道透過使用DP 的承諾方案遞歸地將SNARK 證明與自身組合，就沒有SNARK 證明會變得小的限制嗎？
A：是的，使用Ligero/Brakedown 承諾的SNARK 的「遞歸閾值」相對較高。遞歸閾值指的是證明的大小，即透過遞歸地將基於Brakedown/Ligero 的SNARK 應用於驗證器，無法再產生更短的證明。我預計遞歸閾值在幾MB 的數量級上。
如果希望獲得更小的證明，我認為可以透過與其他更小證明的SNARK 進行組合來實現，詳情參考Q1 2 。如果這個假設最終被證明是錯誤的，不應視為Binius 的失敗，而應視為對當今流行的SNARK 的可擴展性的指責。如果它們不能在合理的時間內證明幾MB 的數據已被哈希，我們怎麼能說它們具有可擴展性？
無論如何，除了降低證明大小之外，快速遞歸組合還有其他重要原因。最重要的是，它是控制證明空間需求的關鍵工具。由於（非遞歸）SNARK 對於證明者來說佔用空間很大，人們會將大型計算分解成小塊，分別證明每個區塊，並使用遞歸證明將這些區塊「連結」在一起。 DP 對於標準哈希函數（如Keccak）的快速SNARK 使得這種遞歸證明能夠迅速完成，即使證明的大小有些大。
Q1 2 ：假設您想結合DP 的承諾方案與基於elliptic-curve 的SNARK（例如Plonk 或Groth 16）以降低驗證者在鏈上發布證明前的成本。這難道不需要證明涉及“非本地”字段算術嗎？因為DP 的驗證器操作在GF[ 2 ^ 128 ] 上，而基於curve 的SNARK 使用大型素數階欄位。
A：是的，這是一個潛在的挑戰，但我相信能夠找到解決方案。
有一種可能性是先與使用基於哈希的多項式承諾方案的SNARK 進行組合，該方案具有更短的證明（可能是FRI，轉換為多線性多項式承諾方案，或者BaseFold），然後再與基於curve 的SNARK 進行組合。請注意，FRI 可以在特徵為二的欄位上本地運行，事實上，在原始的FRI 論文中就考慮過這種情況。目前流行的SNARK 對使用這些欄位的限制來自於非基於求和檢查的多項式IOPs 的使用，與FRI 本身不同。
這並不能消除非本地字段算術的問題，但可以在很大程度上緩解，因為對於足夠大的多項式，FRI 驗證器執行的總操作較少，尤其是比Ligero/Brakedown 驗證器執行的字段操作較少。
Q1 3 ：使用DP 的承諾方案的SNARK 是否可以與Nova 等折疊方案結合使用？
A：這將遇到與Q1 2 相同的問題，即折疊方案使用elliptic-curve，通常定義在大型素數階字段上，而DP 的承諾方案使用大小為2 的冪的字段。
我預計在折疊方案方面會取得顯著的進展，並且它們將在未來的SNARK 設計中發揮重要作用。然而，可能情況是它們與基於哈希的SNARK 在非常小特徵的字段上並不很好地結合。
目前而言，應在涉及本地定義在大字段上的語句，或者在prover 空間至關重要的情況下使用基於elliptic-curve 的承諾和折疊方案（像Nova 這樣的折疊方案在prover 空間方面遠遠優於其他SNARK，大致上因為它們可以將大型計算分解成比其他SNARK 小得多的部分）。而在其他情況下，應該使用基於哈希的方案，尤其是在小特徵字段上使用。
同樣，未來折疊方案的進一步發展可能導致它們超越基於哈希的方案。實際上，Nova 在某些基準測試中已經比當前世代基於哈希的SNARK 更快（儘管有許多聲稱當前基於哈希的SNARK 比基於curve 的更快的說法）。
