a16z Crypto 推出了兩項與 SNARK 相關的技術：Lasso 和 Jolt。它們解決了三個關鍵問題：效能、開發人員體驗和可稽核性。本文源自 a16z Researcher Justin Thaler 所著文章《Boosting Lasso+Jolt through faster commitments – with far-reaching consequences》
（前情提要：a16z：如何用一場魔術理解「零知識證明(ZKP)」是什麼？ ）
（背景補充：V神談Layer2擴容全文：Rollup與Validiums（有效性驗證）兩者間權衡 ）
其中 Lasso 是一種新的查詢引數，可以顯著提高證明者成本；Jolt（Just One Lookup Table）是一個專為與以太坊虛擬機器相容的 Rollups 設計的框架，一種利用 Lasso 構建 SNARK VM 的新穎方法。Lasso 和 Jolt 可以顯著加快 Web3 中的擴容和構建應用程式，它們共同代表了一種全新的 SNARK 設計方法，可將廣泛部署的工具鏈的效能提高一個數量級甚至更多級。
延伸閱讀：科普｜zk-SNARKs是什麼？V神定調零知識證明未來十年「非常重要」
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 hash也是如此。在本文末尾，我還將詳細說明關於 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。另一類基於 hash，當前最流行的例子是 FRI。
對於基於曲線和基於 hash 的承諾方案，承諾小值比大值更快。但是，就證明者的成本而言，它是一個關於值大小的階躍函式：隨著值的大小增長，成本基本保持不變，偶爾會有顯著的跳躍。
在基於曲線的情況下，這是由於 Pippenger 的演算法，它大致允許證明者使用單個群操作對 1 到 20 位值進行承諾，使用兩個群操作對 20 到 40 位值進行承諾，使用三個群操作對 40 到 60 位值進行承諾，依此類推。（在這裡，20 是「承諾向量長度的對數」的替代，這個長度通常在 20 到 30 之間，並且前述的承諾成本是攤銷的。）對於基於 hash 的承諾方案，許多專案今天在擴展域上工作，這些域具有其中一個更小的基礎域。如果所有承諾的值都駐留在基礎域中，則計算承諾的速度更快，目前常見的基礎域大小在 31 到 64 位之間。
然而，當前的承諾方案在受益於小值方面的程度是有限的。在基於曲線的情況下，承諾一個 2 位值（即 {1, 2, 3, 4} 中的值）的速度不比承諾一個 20 位值（即介於 0 和 2^20≈100 萬之間的數位）快：兩者都需要通過 Pippenger 的演算法進行大致一次群操作。今天流行的基於 hash 的方案也是如此，它們對待所有基礎域元素都差不多。
D&P 通過兩種技術的組合，使 Ligero/Brakedown 基於 hash 的多項式承諾方案的這種階躍函式變得更加平滑，允許證明者大致按位元「支付」每個承諾的值。他們通過兩種技術的組合實現了這一點。首先，他們在 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 中，三分之一到三分之二的承諾值只是一個單一的位。
戲劇性改進的hash SNARKs
前兩個貢獻在應用於特徵為二的場域上的電路滿足性方面，產生了一個更快的 SNARK，可能比以前的工作快一個甚至兩個數量級。
然後，D&P 將這個 SNARK 應用於實現 hash 函式 Keccak（以及另一個稱為 Grøstl 的函式），為這些 hash 函式產生比以前任何東西都要快得多的 SNARKs。一旦完全優化，我預計他們的 SNARKs 在單執行緒情況下每秒可以證明超過 5,000 個 Keccak-f 排列（在基準測試中使用的機器是 AWS c7i.16xlarge 例項，配備 Intel Sapphire Rapids 8488C 處理器），並且有充足的並行性可用。這意味著 20-25 MiB 的資料可以在約 30 秒的單執行緒處理中進行hash。
影響
更好的用於 hash 的 SNARKs 本身就是強大的，因為 SNARKs 應用於許多密碼學語句（如 Merkle 身份驗證路徑的知識）最終都歸結為 hash。事實上，這是 Type-1 zkEVMs 以及遞迴 hash 基礎的 SNARKs 的關鍵瓶頸。
因此，儘管 Lasso 使 hash 的 SNARKs 更好，它和 Jolt 也從中受益：對 hash 更好的 SNARKs 使 Lasso 和 Jolt 能夠與（遞迴版本的）基於 Ligero/Brakedown hash 的多項式承諾方案結合使用。這些方案的證明者非常快速，但需要驗證者執行相當多的hash操作（在承諾的多項式大小的平方根）。這使得使用 Ligero/Brakedown 遞迴應用 SNARKs 變得困難，因為證明者很難證明它正確執行了驗證者的 hash 操作。在使用更快的 hash SNARKs 後，這個困難應該會消失。
具體而言，對於擁有數十億門的電路，Ligero/Brakedown 證明的大小在 MB 級別，驗證者 V 主要執行欄位操作（對於遞迴而言很便宜）和hash操作。考慮到 SNARKs 可以在 30 秒的單執行緒處理時間內對 20 MB 的資料進行hash（並且具有充分的可並行性），證明者應該需要不到 10 秒的單執行緒處理時間來對該證明系統應用遞迴。
除此之外，當使用遞迴時，優化 Ligero/Brakedown 的證明大小並不合理，而應該優化遞迴證明器的執行時間。由於相比於欄位操作，hash 操作更昂貴，因此應配置 Ligero/Brakedown 讓驗證者 V 執行更少的 hash 操作，即使這意味著更大的證明和更多的欄位操作。這將加速遞迴證明，超出了前述 10 秒的估計。
總的來說，將 Lasso 和 Jolt 與 D&P 的承諾方案（遞迴應用）相結合將進一步提高 Lasso 和 Jolt 的效能。這既因為 Keccak 和 Grøstl 比今天流行的 SNARK 友好的 hash 函式更快，而且無論使用哪種 hash 函式，Ligero/Brakedown 的證明速度都比 FRI 快。
重新審視 SNARK 友好 hash 的觀點
Jolt 表明，大多數 zkVM 專案對於什麼是「SNARK-friendly」虛擬機器存在誤解。使一條指令「SNARK-friendly」的關鍵屬性是一種被稱為可分解性的東西。實際的指令集，而不是為了所謂的 SNARK 友好而手工設計的指令集，自然滿足這種屬性。我們一直在手工設計虛擬機器，使其適應當今流行的 SNARK 的限制，但這些限制是人為的。D&P 表明 SNARK 友好 hash 也是如此。近期，未來的工作是完全優化 D&P 的 SNARKs 以適應標準hash函式，並在應用於表面上是 SNARK-friendly hash 時將其效能與當今流行的 hash 函式進行比較。
更快的小域求和檢查證明程式
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 驗證器必須執行大量 hash 評估。實際上，一些作品，如 Orion，簡單地「在遞迴中留出驗證器的hash」，限制了證明大小和驗證器工作的減少。但是，由於用於證明 hash 評估的 SNARKs 速度更快，這個問題就消失了。
多輪的多項式 IOP 內的互動確實在很大程度上幫助了證明者。具體而言，求和檢查協議利用多輪的互動來最小化證明者的承諾成本。在更低的層次上，求和檢查協議使用多變數多項式和多輪的互動，而當今最流行的多項式 IOPs 使用單變數多項式和少量輪次的互動。單變數方法實現了與多變數方法相同的功能，但在關鍵時刻以要求證明者承諾大量額外資料為代價。
這裡發生的情況是，求和檢查協議讓證明者執行額外的欄位操作（這是快速的），以減少證明者在承諾方案中使用的加密操作的數量（這是慢的）。這對於證明者的時間是一種勝利。相比之下，高度互動的承諾方案讓證明者執行額外的加密操作（相對於最小互動方案），並不是為了減少證明者的工作，而是為了降低驗證者的成本，比如證明大小和驗證者工作。最好使用遞迴而不是互動，將這些驗證者成本轉嫁給證明者，而證明者的時間只會略微增加（現在我們有了足夠快速的用於雜湊的 SNARKs）。
我們應該利用多項式 IOP 內的互動來最小化證明者需要承諾的資料量。用於承諾資料的多項式承諾方案應該對證明者來說盡可能快，前提是具有次線性的驗證成本。只需要一輪互動就足夠了。然後，可以通過遞迴減少驗證成本，而不引入新的證明者瓶頸。
新發展概要
D&P 使用 Lasso 提供了更好的電路可滿足性（circuit-SAT）SNARK。
這個 SNARK 可以使用任何多線性多項式的承諾方案。另外，他們提供了一個更快的多項式承諾方案（在特徵為二的域上例項化的 Ligero/Brakedown）。簡而言之，通過使用二進位制塔場和程式碼級聯，他們確保對非常小的值進行承諾非常快（至少比以前的工作快一個數量級）。這個方案對於證明者來說非常快，但驗證成本相對較高（驗證者需要進行大量hash運算）。
這兩個進展共同為標準hash函式（如 Keccak）提供了極快的 SNARKs。再次強調，這一驗證成本相對較高。
更快的hash SNARKs 使這些 SNARKs 可以進行遞迴，儘管它們的驗證成本相對較高。
遞迴反過來解決了大量驗證成本的問題。
加密學術文章對 SNARK 生態系統的影響
這些新的研究成果意味著，為了獲得性能卓越的 SNARK 證明者，我們應該基本上改變今天部署的每個元件，包括：
- 多項式 IOPs（互動式證明）：它們應該基於總檢查以最小化證明者需要提交的資料量。
- 多項式承諾方案：我們應該將更快的證明者、更大的證明方案，如 Ligero/Brakedown，與遞迴相結合。Ligero/Brakedown 具有與 FRI 完全相同的安全屬性。它們是透明的，有可能在量子計算後期是安全的，僅基於hash等。
- hash函式：我主張使用諸如 Keccak 和 Grøstl 之類的hash函式，它們可以至少與今天所謂的「SNARK 友好」hash函式一樣快速地進行證明。如果我們確實想要設計出更加友好於 SNARK 的hash函式，我們將不得不從頭開始，考慮到我們對高效能 SNARK 實際能力和侷限性的改進理解。
- zkVM 的指令集：我們應該使用 RISC-V 的標準指令集，而不是設計在先前證明系統的限制周圍的指令集。我們也不應該手動設計實現每個指令的電路。相反，zkVM 的設計者應該簡單地指定每個指令的評估表，並使用像 Lasso 這樣基於總檢查的查詢引數。
- 它們所涉及的領域：由於各種技術原因，今天流行的 SNARK 通常需要具有相對大特徵的領域（部署通常使用至少 231 的特徵）。基於總檢查協議的 SNARK 沒有這個限制，而 D＆P 展示瞭如何利用具有非常小特徵的領域，比如 GF [2128]，以獲得性能的顯著提升。
幸運的是，導致這些變化的同一發展也使 SNARK 變得更簡單、更易於構建，儘管仍有進一步改進的空間。特別是，Jolt 消除了為 zkVM 手動設計指令集或手動優化實現這些指令集的電路的需要，因為它用每個原始指令的評估表的簡單規範替代了這些電路。這種模組化和通用的架構使得更容易替換領域和多項式承諾方案，實現遞迴，並且通常減少了錯誤的表面積和需要維護和稽核的程式碼量。
延伸閱讀：Layer2蓄勢待發，裡面有什麼類型的zkEVM？
這種簡單性不僅對可用性和開發速度至關重要。它有助於解決一個重要的安全問題。基於 SNARK 的系統由成千上萬行程式碼組成，需要理解多個訂製的約束系統或 DSL，將永遠無法足夠可審計，以確保數十億美元的價值的安全。
我希望這篇文章能夠說服更多的專案投資於開發符合這一設計範例的 SNARKs。
在不久的將來，我所提出的一些觀點仍然需要通過實施進行全面驗證（例如，比較 D&P 的 Keccak SNARK 與那些表面上友好的 SNARK hash函式的比較，以及充分實施遞迴以減小證明大小）。與此同時，我們的初步 Jolt 實現（採用基於曲線的承諾方案）已經接近完成。一旦完成，重新實現 Jolt 以使用 D&P 的基於hash的承諾方案將是值得的。這有些複雜，主要是因為從大素數域切換到二特徵域需要重新定義所有 Lasso 應用的查詢表。我還希望基於新的 Lasso 的 Plonkish 電路的 SNARK 能夠簡化將 Lasso 整合到現有工具中的過程，因為它可以將人們已經編寫的電路饋送到其中。
這些是明顯的下一步。我很期待看到社群完全吸收求和檢查協議以最小化承諾成本的能力後會發生什麼。
