今年初，我們推出了 Lasso 和 Jolt，它們不僅性能更強大，而且更易於構建和審計的 SNARK。

Lasso 是一種具有明顯更快證明者的新型查找參數。Jolt 基於 Lasso，提供了一種根本上新的設計範例，用於設計所謂的 zkVMs - SNARKs，使證明者能夠證明它正確地運行了計算機程序（以某個特定虛擬機的匯編語言指定）。

Lasso 和 Jolt 的核心都是一種稱為 sum-check 協議的技術工具，它們使用該協議來最小化證明者必須承諾的數據量（以及每個數據片的「大小」）。承諾數據的成本是 SNARK 證明者性能的關鍵瓶頸。

今天，Ulvetanna 的 Ben Diamond 和 Jim Posen（以下簡稱 D&P）發布了一篇改變遊戲規則的論文。D&P 的核心貢獻是修改了 Ligero/Brakedown 承諾方案，使證明者可以對每個承諾的值「按位」付費。我將解釋他們是如何實現這一點的，以及為什麼與 Lasso 結合使用，這導致 SNARK 性能大幅提升。D&P 將他們的實現稱為 Binius。

這些發展不僅提高了性能，也表明我們一直在錯誤地構思 SNARK 設計的關鍵方面。例如，Jolt 已經表明，當我們手工設計「SNARK-friendly」VMs 時，實際上我們一直在為今天流行的 SNARKs 的人工限制進行定製。D&P 表明，SNARK-friendly 哈希也是如此。在本文末尾，我還將詳細說明關於 SNARK 設計需要發生哪些變化，無論是我們如何思考它還是我們構建什麼。

通過 Lasso 實現更好的 Circuit-SAT SNARK

Jolt 可以看作是將 Lasso 應用於 VM 執行的一種應用，其定義包括一遍又一遍地執行 VM 的簡單取指-解碼-執行循環。然而，Lasso 本身具有更廣泛的適用性。

D&P 的第一步是使用 Lasso 為電路可滿足性提供更好的 SNARK（更準確地說，支持的「電路」是 Plonkish 約束系統）。這可以看作是將 Lasso 應用於（潛在的）非均勻計算（與 VM 執行不同，後者在本質上是均勻的，因為 VM 反覆執行相同的取指、解碼和執行循環）。這種應用利用了 Lasso 實際上比查找參數更強大：它是一種用於一般稀疏線性關係的參數，用於建立 M⋅t = a 的關係，其中 M 是一個稀疏矩陣（即，其大多數條目為零），而 t 和 a 是（可能已提交的）向量。

與 Jolt 一樣，對 Lasso 的這種應用具有重要的特性，即證明者幾乎需要進行密碼學承諾的所有值都很小，意味著它們在 0 到 2b 之間，其中 b 是一個不是很大的數字（我們將 b 稱為每個承諾值的比特複雜度）。例如，在 Jolt 中，對於大多數承諾的值，b ≤ 25。

在另一篇文章中，Srinath Setty 和我提出了一種 Plonkish 泛化的替代 SNARK，我們認為這種替代方法在概念上更簡單，但可能不太容易與 D&P 隨後的貢獻整合。

這些基於 Lasso 的新的 Plonkish 約束系統 SNARK 將使 Lasso 基礎技術更容易整合到現有的工具（如 Halo2）中，其中許多工具專門支持 Plonkish。

更快速的小值多項式承諾方案

首先，正如我在之前的文章中解釋的那樣，大多數 SNARKs 由兩個組件組成：一個所謂的多項式 IOP 和一個稱為多項式承諾方案的密碼原語。關鍵的證明者瓶頸通常是多項式承諾方案。

如今，有兩類廣泛使用的多項式承諾方案。一類基於橢圓曲線密碼學，其中最流行的例子是 KZG 承諾和 Bulletproofs/IPA。另一類基於哈希，當前最流行的例子是 FRI。

對於基於曲線和基於哈希的承諾方案，承諾小值比大值更快。但是，就證明者的成本而言，它是一個關於值大小的階躍函數：隨著值的大小增長，成本基本保持不變，偶爾會有顯著的跳躍。

在基於曲線的情況下，這是由於 Pippenger 的算法，它大致允許證明者使用單個群操作對 1 到 20 位值進行承諾，使用兩個群操作對 20 到 40 位值進行承諾，使用三個群操作對 40 到 60 位值進行承諾，依此類推。（在這裡，20 是「承諾向量長度的對數」的替代，這個長度通常在 20 到 30 之間，並且前述的承諾成本是攤銷的。）對於基於哈希的承諾方案，許多項目今天在擴展域上工作，這些域具有其中一個更小的基礎域。如果所有承諾的值都駐留在基礎域中，則計算承諾的速度更快，目前常見的基礎域大小在 31 到 64 位之間。

然而，當前的承諾方案在受益於小值方面的程度是有限的。在基於曲線的情況下，承諾一個 2 位值（即 {1, 2, 3, 4} 中的值）的速度不比承諾一個 20 位值（即介於 0 和 2^20≈100 萬之間的數字）快：兩者都需要通過 Pippenger 的算法進行大致一次群操作。今天流行的基於哈希的方案也是如此，它們對待所有基礎域元素都差不多。

D&P 通過兩種技術的組合，使 Ligero/Brakedown 基於哈希的多項式承諾方案的這種階躍函數變得更加平滑，允許證明者大致按比特「支付」每個承諾的值。他們通過兩種技術的組合實現了這一點。首先，他們在 GF[2^128] 域上工作，這個域的特徵是二（這與今天流行的 SNARKs 有很大的不同，後者的特徵至少為 2^31）。他們將這個域構造為一個塔，意味著 GF[2^128] 被構造為 GF[2^64] 的擴展，GF[2^64] 被構造為 GF[2^32] 的擴展，以此類推。其次，他們使用與代碼串聯相關的技術，以確保承諾一個 1 位值的成本真的比承諾一個 2 位值便宜約 2 倍，承諾一個 2 位值的成本大約比承諾一個 4 位值便宜 2 倍，依此類推。（有關這些技術的概述，請參閱我更詳細的技術伴隨 FAQ。）

這一效果可能是巨大的。在 D&P 目前針對 Keccak 的 SNARK 中，所有的承諾值都是單獨的位，他們的改進使得承諾這些一位值的時間縮短了一個數量級以上。舉個例子，在 Jolt 中，三分之一到三分之二的承諾值只是一個單一的位。

戲劇性改進的哈希 SNARKs

前兩個貢獻在應用於特徵為二的場域上的電路滿足性方面，產生了一個更快的 SNARK，可能比以前的工作快一個甚至兩個數量級。

然後，D&P 將這個 SNARK 應用於實現哈希函數 Keccak（以及另一個稱為 Grøstl 的函數），為這些哈希函數產生比以前任何東西都要快得多的 SNARKs。一旦完全優化，我預計他們的 SNARKs 在單線程情況下每秒可以證明超過 5,000 個 Keccak-f 排列（在基準測試中使用的機器是 AWS c7i.16xlarge 實例，配備 Intel Sapphire Rapids 8488C 處理器），並且有充足的並行性可用。這意味著 20-25 MiB 的數據可以在約 30 秒的單線程處理中進行哈希。

影響

更好的用於哈希的 SNARKs 本身就是強大的，因為 SNARKs 應用於許多密碼學語句（如 Merkle 身份驗證路徑的知識）最終都歸結為哈希。事實上，這是 Type-1 zkEVMs 以及遞歸哈希基礎的 SNARKs 的關鍵瓶頸。

因此，儘管 Lasso 使哈希的 SNARKs 更好，它和 Jolt 也從中受益：對哈希更好的 SNARKs 使 Lasso 和 Jolt 能夠與（遞歸版本的）基於 Ligero/Brakedown 哈希的多項式承諾方案結合使用。這些方案的證明者非常快速，但需要驗證者執行相當多的哈希操作（在承諾的多項式大小的平方根）。這使得使用 Ligero/Brakedown 遞歸應用 SNARKs 變得困難，因為證明者很難證明它正確執行了驗證者的哈希操作。在使用更快的哈希 SNARKs 後，這個困難應該會消失。

具體而言，對於擁有數十億門的電路，Ligero/Brakedown 證明的大小在 MB 級別，驗證者 V 主要執行字段操作（對於遞歸而言很便宜）和哈希操作。考慮到 SNARKs 可以在 30 秒的單線程處理時間內對 20 MB 的數據進行哈希（並且具有充分的可並行性），證明者應該需要不到 10 秒的單線程處理時間來對該證明系統應用遞歸。

除此之外，當使用遞歸時，優化 Ligero/Brakedown 的證明大小並不合理，而應該優化遞歸證明器的運行時間。由於相比於字段操作，哈希操作更昂貴，因此應配置 Ligero/Brakedown 讓驗證者 V 執行更少的哈希操作，即使這意味著更大的證明和更多的字段操作。這將加速遞歸證明，超出了前述 10 秒的估計。

總的來說，將 Lasso 和 Jolt 與 D&P 的承諾方案（遞歸應用）相結合將進一步提高 Lasso 和 Jolt 的性能。這既因為 Keccak 和 Grøstl 比今天流行的 SNARK 友好的哈希函數更快，而且無論使用哪種哈希函數，Ligero/Brakedown 的證明速度都比 FRI 快。

重新審視 SNARK 友好哈希的觀點

Jolt 表明，大多數 zkVM 項目對於什麼是「SNARK-friendly」虛擬機存在誤解。使一條指令「SNARK-friendly」的關鍵屬性是一種被稱為可分解性的東西。實際的指令集，而不是為了所謂的 SNARK 友好而手工設計的指令集，自然滿足這種屬性。我們一直在手工設計虛擬機，使其適應當今流行的 SNARK 的限制，但這些限制是人為的。D&P 表明 SNARK 友好哈希也是如此。近期，未來的工作是完全優化 D&P 的 SNARKs 以適應標準哈希函數，並在應用於表面上是 SNARK-friendly 哈希時將其性能與當今流行的哈希函數進行比較。

更快的小域求和檢查證明程序

D&P 目前的承諾成本已經降低到這樣一個程度，在他們目前的 Keccak SNARK 實現中，證明者的瓶頸不再是多項式承諾方案，而是求和檢查協議（Lasso 和 Jolt 基礎多項式 IOP 的技術核心）。

然而，包括 D&P 在內的現有求和檢查證明程序實現並沒有被優化，以充分利用被求和的值都是「小」的這一事實。也就是說，現有的求和檢查證明程序執行很少的有限域操作，但是大多數這些操作發生在「整個域」GF[2^128] 中，即使大多數被求和的值存在於一個更小的子域中，比如 GF[2]，GF[2^8] 或 GF[2^16]。

在我的另一篇文章中，我已經優化了求和檢查證明程序以利用小的值。取決於值的大小，這可以將求和檢查證明程序的工作改進大約 2 倍，甚至是多個數量級。

將這些優化納入 D&P 的實現是短期未來的工作。

在 SNARK 設計中交互的作用

當今被廣泛認為具有領先證明性能的 SNARKs 使用最小交互（即常數輪）的多項式 IOP，結合高度交互的多項式承諾方案，即 FRI。（Bulletproofs/IPA 也是高度交互的，儘管不太常與快速證明器聯繫在一起。）這與設計快速證明器 SNARKs 的方式相反。多項式 IOP 中的交互可以被利用以減少證明器成本，而多項式承諾方案中的交互則被利用以減少驗證器成本，通常是以證明器成本為代價。

由於證明器成本是 SNARK 的關鍵可擴展性瓶頸，多項式 IOP 中的交互是實現更可擴展 SNARK 的關鍵，而在多項式承諾方案中大量的交互實際上可能會損害可擴展性。

更詳細地說，FRI（和 Bulletproofs/IPA）利用交互來最小化證明大小，但這是以證明時間為代價的。相反，我們應該追求可能最快的證明器，即使這意味著僅獲得略微次線性大小的證明。然後，我們可以應用遞歸來減小證明的大小。這正是 Ligero/Brakedown 多項式承諾中所做的，它僅涉及一輪交互，並且具有非常快速的證明器，但具有平方根大小的證明。在 D&P 的工作之前，使用這些承諾方案遞歸 SNARKs 是困難的，因為 Ligero/Brakedown 驗證器必須執行大量哈希評估。實際上，一些作品，如 Orion，簡單地「在遞歸中留出驗證器的哈希」，限制了證明大小和驗證器工作的減少。但是，由於用於證明哈希評估的 SNARKs 速度更快，這個問題就消失了。

多輪的多項式 IOP 內的交互確實在很大程度上幫助了證明者。具體而言，求和檢查協議利用多輪的交互來最小化證明者的承諾成本。在更低的層次上，求和檢查協議使用多變量多項式和多輪的交互，而當今最流行的多項式 IOPs 使用單變量多項式和少量輪次的交互。單變量方法實現了與多變量方法相同的功能，但在關鍵時刻以要求證明者承諾大量額外數據為代價。

這裡發生的情況是，求和檢查協議讓證明者執行額外的字段操作（這是快速的），以減少證明者在承諾方案中使用的加密操作的數量（這是慢的）。這對於證明者的時間是一種勝利。相比之下，高度交互的承諾方案讓證明者執行額外的加密操作（相對於最小交互方案），並不是為了減少證明者的工作，而是為了降低驗證者的成本，比如證明大小和驗證者工作。最好使用遞歸而不是交互，將這些驗證者成本轉嫁給證明者，而證明者的時間只會略微增加（現在我們有了足夠快速的用於散列的 SNARKs）。

我們應該利用多項式 IOP 內的交互來最小化證明者需要承諾的數據量。用於承諾數據的多項式承諾方案應該對證明者來說儘可能快，前提是具有次線性的驗證成本。只需要一輪交互就足夠了。然後，可以通過遞歸減少驗證成本，而不引入新的證明者瓶頸。

新發展概要

D&P 使用 Lasso 提供了更好的電路可滿足性（circuit-SAT）SNARK。

這個 SNARK 可以使用任何多線性多項式的承諾方案。另外，他們提供了一個更快的多項式承諾方案（在特徵為二的域上實例化的 Ligero/Brakedown）。簡而言之，通過使用二進制塔場和代碼級聯，他們確保對非常小的值進行承諾非常快（至少比以前的工作快一個數量級）。這個方案對於證明者來說非常快，但驗證成本相對較高（驗證者需要進行大量哈希運算）。

這兩個進展共同為標準哈希函數（如 Keccak）提供了極快的 SNARKs。再次強調，這一驗證成本相對較高。

更快的哈希 SNARKs 使這些 SNARKs 可以進行遞歸，儘管它們的驗證成本相對較高。

遞歸反過來解決了大量驗證成本的問題。

加密學術文章對 SNARK 生態系統的影響

這些新的研究成果意味著，為了獲得性能卓越的 SNARK 證明者，我們應該基本上改變今天部署的每個組件，包括：

多項式 IOPs（交互式證明）：它們應該基於總檢查以最小化證明者需要提交的數據量。

多項式承諾方案：我們應該將更快的證明者、更大的證明方案，如 Ligero/Brakedown，與遞歸相結合。Ligero/Brakedown 具有與 FRI 完全相同的安全屬性。它們是透明的，有可能在量子計算後期是安全的，僅基於哈希等。

哈希函數：我主張使用諸如 Keccak 和 Grøstl 之類的哈希函數，它們可以至少與今天所謂的「SNARK 友好」哈希函數一樣快速地進行證明。如果我們確實想要設計出更加友好於 SNARK 的哈希函數，我們將不得不從頭開始，考慮到我們對高性能 SNARK 實際能力和侷限性的改進理解。

zkVM 的指令集：我們應該使用 RISC-V 的標準指令集，而不是設計在先前證明系統的限制周圍的指令集。我們也不應該手動設計實現每個指令的電路。相反，zkVM 的設計者應該簡單地指定每個指令的評估表，並使用像 Lasso 這樣基於總檢查的查找參數。

它們所涉及的領域：由於各種技術原因，今天流行的 SNARK 通常需要具有相對大特徵的領域（部署通常使用至少 231 的特徵）。基於總檢查協議的 SNARK 沒有這個限制，而 D＆P 展示了如何利用具有非常小特徵的領域，比如 GF[2128]，以獲得性能的顯著提升。

幸運的是，導致這些變化的同一發展也使 SNARK 變得更簡單、更易於構建，儘管仍有進一步改進的空間。特別是，Jolt 消除了為 zkVM 手動設計指令集或手動優化實現這些指令集的電路的需要，因為它用每個原始指令的評估表的簡單規範替代了這些電路。這種模塊化和通用的架構使得更容易替換領域和多項式承諾方案，實現遞歸，並且通常減少了錯誤的表面積和需要維護和審核的代碼量。

這種簡單性不僅對可用性和開發速度至關重要。它有助於解決一個重要的安全問題。基於 SNARK 的系統由成千上萬行代碼組成，需要理解多個定製的約束系統或 DSL，將永遠無法足夠可審計，以確保數十億美元的價值的安全。

我希望這篇文章能夠說服更多的項目投資於開發符合這一設計範例的 SNARKs。

在不久的將來，我所提出的一些觀點仍然需要通過實施進行全面驗證（例如，比較 D&P 的 Keccak SNARK 與那些表面上友好的 SNARK 哈希函數的比較，以及充分實施遞歸以減小證明大小）。與此同時，我們的初步 Jolt 實現（採用基於曲線的承諾方案）已經接近完成。一旦完成，重新實現 Jolt 以使用 D&P 的基於哈希的承諾方案將是值得的。這有些複雜，主要是因為從大素數域切換到二特徵域需要重新定義所有 Lasso 應用的查找表。我還希望基於新的 Lasso 的 Plonkish 電路的 SNARK 能夠簡化將 Lasso 集成到現有工具中的過程，因為它可以將人們已經編寫的電路饋送到其中。

這些是明顯的下一步。我很期待看到社區完全吸收求和檢查協議以最小化承諾成本的能力後會發生什麼。

原文連結