原文標題：《Boosting Lasso+Jolt through faster commitments – with far-reaching consequences》

原文作者：Justin Thaler

原文編譯：Luccy，BlockBeats

編按：

a16z Crypto 推出了兩種與SNARK 相關的技術：Lasso 和Jolt。它們解決了三個關鍵問題：效能、開發人員體驗和可審核性。

其中Lasso 是一種新的查找參數，可以顯著提高證明者成本；Jolt（Just One Lookup Table）是一個專為與以太坊虛擬機相容的Rollups 設計的框架，一種利用Lasso 建構SNARK VM 的新穎方法。 Lasso 和 Jolt 可以顯著加快 Web3 中的擴展和構建應用程序，它們共同代表了一種全新的 SNARK 設計方法，可將廣泛部署的工具鏈的性能提高一個數量級甚至更多級。

相關閱讀：《a16z 推出零知識證明新工具Lasso 與Jolt：提升SNARK 效能與開發體驗》

a16z 的研究合夥人、喬治城大學電腦科學系的副教授Justin Thaler 深入探討了最新的SNARK 技術發展，強調了透過改變現有部署的各個組件，包括多項關鍵技術，以獲取具有高性能證明者的SNARKs 的必要性。 Justin 建議使用基於求和檢查的多項式 IOPs 和結合更快的證明者、更大證明的方案，例如 Ligero/Brakedown，再加上遞歸，以實現更有效率的 SNARK 系統。此外，他強調了對於更簡單、易於開發的 SNARK 系統的迫切需求，以提高可審計性和安全性。

今年初，我們推出了 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 整合到現有工具中的過程，因為它可以將人們已經編寫的電路饋送到其中。

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

「原文連結」

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

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

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

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