另类专区另类专区亚洲,日韩国产欧美精品综合二区,日本黄色免费在线视频,天天爽夜夜爽免费看

有關 SNARK 為何如此重要、其當前設計狀態(tài)、需要理解的關鍵概念以及開發(fā)人員和工程師的實現(xiàn)細節(jié)的更多信息，請閱讀《Building on Lasso and Jolt》（其中還包括一個開源實現(xiàn)）。研究論文可以在這里找到（Lasso，Jolt）。您還可以在此YouTube 播放列表中觀看解釋 Lasso 和 Jolt、查找奇點以及思考 SNARK 設計的新方法的完整或簡短視頻。 

SNARK （簡潔的非交互式AR知識）是一種加密協(xié)議，任何人都可以向不信任的驗證者證明它知道滿足某些屬性的“證人” 。web3 中的一個突出應用是第 2 層 (L2) 匯總，向第 1 層 (L1) 區(qū)塊鏈證明它們知道授權一系列交易的數(shù)字簽名，因此簽名本身不必由網絡存儲和驗證。 L1，從而有助于可擴展性。 

區(qū)塊鏈之外的應用程序包括快速但不受信任的 硬件 設備，證明它們產生的所有輸出的有效性，確保用戶可以信任它們。個人可以以零知識的方式證明 ，受信任的當局已向他們頒發(fā)了憑證，證明他們的年齡足以訪問有年齡限制的內容，而無需透露其出生日期。任何通過網絡發(fā)送加密數(shù)據的人 都可以向管理員證明該數(shù)據符合 網絡策略，而無需透露更多細節(jié)。

雖然許多 SNARK 對驗證者來說具有有吸引力的成本，但 SNARK 通常仍會在證明者計算中引入約六個數(shù)量級的開銷。證明者所承受的額外工作是高度并行化的，但數(shù)百萬倍的 因子開銷嚴重限制了 SNARK 的應用范圍。（有關更多詳細信息，請參閱我之前關于 SNARK證明器性能、安全性和開發(fā)歷史的帖子，以及對這種強大但復雜的技術的常見誤解。） 

更具性能的 SNARK 將加速 L2，還可以允許構建者解鎖尚未設想的應用程序。這就是為什么我們要引入兩項新的相關技術：Lasso ，一種新的查找參數(shù)，可以顯著提高證明者成本；Jolt ，它使用 Lasso 提供了一個新的框架，用于為所謂的 zkVM 和更廣泛的前端設計設計 SNARK。它們共同提高了 SNARK 設計的性能、開發(fā)人員體驗和可審核性，進而提高了 web3 中的構建。

我們對 Lasso 的初步實現(xiàn)已經證明，與流行的 SNARK 工具鏈 halo2 中的查找參數(shù)相比，速度提高了 10 倍以上。當 Lasso 代碼庫完全優(yōu)化后，我們預計速度會提高約 40 倍。Jolt 包含 Lasso 之上的其他創(chuàng)新，我們預計它能夠實現(xiàn)與現(xiàn)有 zkVM 類似或更好的加速。

查找參數(shù)、Lasso 和 Jolt 

SNARK前端是將計算機程序轉換為 SNARK 后端可以攝取的電路的編譯器。電路是一種極其有限的計算模型，其中可用的“原始運算”只是加法和乘法。

現(xiàn)代 SNARK 設計中的一個關鍵工具是一種稱為查找參數(shù)的協(xié)議，它允許不受信任的證明者以加密方式提交一個大向量，然后證明該向量的每個條目都包含在某個預定的表中。查找參數(shù)可以通過有效地處理并非由少量加法和乘法自然計算的運算來幫助保持電路較?。ㄕ垍㈤單覀兊呐涮孜恼?/a>中討論的按位運算示例）。

然而，正如以太坊基金會的 Barry Whitehat 去年在他稱之為“查找奇點”的愿景中所概述的那樣，“如果我們能夠僅使用查找參數(shù)來有效地定義電路，那么它將導致更簡單的工具和電路”。我們設計的電路只執(zhí)行查找。正如巴里所寫，隨著時間的推移，查找參數(shù)“對于幾乎所有事情都將變得比多項式約束更有效”。 

這一愿景與當今的工作方式形成鮮明對比，當今開發(fā)人員通過使用特殊的領域特定語言（將程序編譯為多項式約束）或直接手動編碼約束來編寫程序來部署 SNARK。該工具鏈需要大量工作，并且為安全關鍵型錯誤的蔓延提供了很大的表面積。即使使用復雜的工具和電路，SNARK 的性能仍然很慢，這限制了它們的適用性。  

Lasso 和 Jolt 解決了所有三個關鍵問題：性能、開發(fā)人員體驗和可審核性。我相信他們共同實現(xiàn)了查找奇點的愿景。Lasso 和 Jolt 還迫使人們重新思考 SNARK 設計中許多公認的智慧。在介紹了一些必要的背景知識后，本文重新審視了有關 SNARK 性能的一些常見觀點，并解釋了如何根據 Lasso 和 Jolt 等創(chuàng)新來更新它們。

SNARK 設計背景：為什么這么慢？

大多數(shù) SNARK 后端都讓證明者使用多項式承諾方案以加密方式承諾電路中每個門的值。然后證明者證明所提交的值確實對應于見證檢查程序的正確執(zhí)行。 

我將來自多項式承諾方案的證明者工作稱為承諾成本。SNARK 具有來自多項式承諾方案之外的額外證明成本。但承諾成本往往是瓶頸。Lasso 和 Jolt 也是如此。如果設計一個 SNARK，其中承諾成本不是主要的證明者成本，這并不意味著多項式承諾方案很便宜。相反，這意味著其他成本高于應有的成本。 

直觀上，承諾的目的是通過密碼學方法安全地增加證明系統(tǒng)的簡潔性。當證明者提交一個大的值向量時，大致就像證明者將整個向量發(fā)送給驗證者，就像普通證明系統(tǒng)將整個見證人發(fā)送給驗證者一樣。承諾方案可以在不強迫驗證者實際接收整個見證的情況下實現(xiàn)這一目標——這意味著 SNARK 設計中承諾方案的目的是控制驗證者成本。

但這些加密方法對于證明者來說非常昂貴，特別是與SNARK 在多項式承諾方案之外使用的信息論 方法相比。信息論方法僅依賴于有限域運算。并且一個字段操作比提交任意字段元素所需的時間快幾個數(shù)量級。 

根據使用的多項式承諾方案，計算承諾涉及多重冪運算（也稱為多標量乘法，或 MSM）或FFT和 Merkle 哈希。Lasso 和 Jolt 可以使用任何多項式承諾方案，但在使用基于 MSM 的方案實例化時具有特別有吸引力的成本，例如IPA / Bulletproofs、KZG / PST、Hyrax、Dory或Zeromorph。 

為什么 Lasso 和 Jolt 很重要

Lasso 是一種新的查找參數(shù)，其中證明者承諾比以前的工作更少且更小的值。根據上下文，這可能會導致 20 倍或更多的加速，其中 2 到 4 倍的加速來自于較少的提交值，另一個 10 倍的加速來自于 Lasso 中所有提交的值都很小的事實。與許多先前的查找參數(shù)不同，Lasso（和 Jolt）還避免了FFT ，F(xiàn)FT 占用大量空間，并且可能成為大型實例的瓶頸。 

此外，Lasso 甚至適用于巨大的表（比如大小為 2 128），只要這些表是“結構化的”（在精確的技術意義上）。這些表太大，任何人都無法顯式實現(xiàn)，但 Lasso 只為其實際訪問的表元素付費。特別是——與之前的查找參數(shù)相比——如果表是結構化的，那么任何一方都不需要以加密方式提交表中的所有值。

Lasso 利用兩種不同的結構概念：可分解性和LDE 結構。 （LDE 是稱為低次擴展多項式的技術概念的縮寫。） 可分解性大致意味著可以通過對更小的表執(zhí)行少量查找來回答對表的單次查找。這是比 LDE 結構更嚴格的要求，但 Lasso 在應用于可分解表時特別有效。  

Jolt

Jolt（Just One Lookup Table ）是一種新的前端，由 Lasso 使用巨大的查找表的能力解鎖。Jolt 的目標是虛擬機/CPU 抽象，也稱為 指令集架構(ISA) 。支持這種抽象的 SNARK 稱為 zkVM。例如，考慮RISC-Zero 項目也針對的RISC-V 指令集（包括乘法擴展）。這是由計算機體系結構社區(qū)開發(fā)的一種流行的開源 ISA，沒有考慮到 SNARK。 

對于每個 RISC-V 指令fi ，Jolt 的主要思想是創(chuàng)建一個包含fi的整個評估表的查找表。因此，如果fi采用兩個 32 位輸入，則該表將有 2 64 個條目，其中 ( x , y )的第一個條目是fi ( x , y )。如果我們考慮 64 位而不是 32 位數(shù)據類型的指令，則每條指令的表的大小將是 2 128而不是 2 64。 

對于基本上每個 RISC-V 指令，生成的查找表都是可分解的，并且套索適用。（少數(shù)指令是通過應用一小段其他指令來處理的。例如， 除法 是通過讓證明者提交商和余數(shù)來處理的，并通過一次乘法和一次加法檢查這些是否正確提供。）

然后可以生成運行 RISC-V CPU T個步驟的“電路”，如下所示。對于T個步驟中的每一個，電路都包含一些簡單的邏輯，用于確定該步驟要執(zhí)行的原始 RISC-V 指令f i是什么，以及該指令的輸入 ( x , y )是什么。然后，電路 簡單地通過執(zhí)行查找來執(zhí)行f i ，該查找顯示關聯(lián)表的第( x , y ) 個條目。更準確地說，Jolt 考慮由每條指令的表串聯(lián)組成的單個表 - 因此稱為“僅一個查找表”。 

重新審視 SNARK 設計中公認的智慧

Lasso 和 Jolt 還顛覆了 SNARK 設計中的一些公認的智慧。每條公認的智慧都以粗體字顯示，后面是 Lasso 和 Jolt 如何改變事物。

#1. 大面積的 SNARK是一種浪費。每個人都應該使用FRI、Ligero、Brakedown或變體，因為它們避免了通常適用于大范圍的橢圓曲線技術。

這里的字段大小大致對應于 SNARK 證明中出現(xiàn)的數(shù)字的大小。由于非常大的數(shù)字的加法和乘法成本很高，因此大字段上的 SNARK 是浪費的想法意味著我們應該努力設計永遠不會出現(xiàn)大數(shù)字的協(xié)議?；?MSM 的承諾（定義如下）使用橢圓曲線，橢圓曲線通常是在大字段（大小約為 2 256）上定義的，因此這些承諾因性能較差而聞名。 

我之前的文章解釋說，使用小字段是否有意義（即使它們是一個選項）在很大程度上取決于應用程序。Lasso 和 Jolt 走得更遠。他們表明，即使使用基于 MSM 的承諾方案，證明者的工作也幾乎可以獨立于字段大小。這是因為，對于基于 MSM 的承諾，承諾值的大小比這些值所在字段的大小更重要。

有關 MSM 的詳細信息。大小為n的多次冪運算 （也稱為 MSM）計算以下形式的表達式

，其中每個gi是乘法群的元素。樸素多重求冪算法執(zhí)行n組求冪和n組乘法。每次求冪可能比乘法慢約 400 倍。

Pippenger 的多重求冪算法比樸素算法節(jié)省了大約 log( n )的因子。實際上，這可能遠遠超過 10 倍。此外，如果所有指數(shù)都很“小”（例如，在 0 和 2^20之間），則可以在多次取冪時間中節(jié)省 10 倍的因子。這類似于計算

比計算

速度快 10 倍。前者涉及16次平方，后者涉及160次。 

如果所有提交的值都很小，Pippenger 的算法只需要（大約）一組乘法 來提交一個值（請參閱本文第 4 節(jié)以獲得很好的說明）。

Lasso 和 Jolt 的新屬性。現(xiàn)有的 SNARK 使證明者承諾許多隨機 字段元素。例如，名為Plonk的流行 SNARK 后端中的證明者承諾每個電路門大約 7 個隨機場元素（以及其他非隨機場元素）。即使被證明的計算中出現(xiàn)的所有值都很小，這些隨機場元素也會很大。 

相比之下，Lasso 和 Jolt 僅要求證明者提交較小的值（Lasso 的證明者提交的值也比先前的查找參數(shù)少）。這極大地提高了基于 MSM 的方案的性能。至少，Lasso 和 Jolt 應該廢除這樣的觀念：在證明者性能很重要的情況下，社區(qū)應該放棄基于 MSM 的承諾。

#2：更簡單的指令集帶來更快的 zkVM。 

只要每條指令的評估表是可分解的，Jolt 的（每條指令）復雜度僅取決于指令的輸入大小。Jolt 證實，令人驚訝的復雜指令是可分解的，特別是所有 RISC-V。

這與人們普遍認為的觀點相反，即更簡單的虛擬機 (zkVM) 必然會導致更小的電路和相關的更快的證明器（VM 的每一步）。這是特別簡單的 zkVM（例如Cairo VM）背后的指導動機，它們是專門為 SNARK 友好而設計的。 

事實上，對于更簡單的虛擬機，Jolt 為證明者實現(xiàn)了比之前的 SNARK 更低的承諾成本。例如，對于 Cairo VM 執(zhí)行，SNARK 證明者在 VM 的每個步驟中提交 51 個字段元素。Cairo 部署的 SNARK 當前在251 位字段上工作（63 位是 SNARK 可以使用的字段大小的硬下限）。Jolt 的證明器致力于 RISC-V CPU 的每步約 60 個字段元素（定義超過 64 位數(shù)據類型）。考慮到提交的字段元素很小的事實后，Jolt 證明者的成本大致相當于提交 6 個隨機 256 位字段元素的成本。

＃3：將大型計算分解為小塊不會造成性能損失。 

基于這種觀點，當今的項目將任何大電路分解成小塊，分別證明每個塊，并通過 SNARK 遞歸聚合結果。這些部署使用這種方法來緩解流行 SNARK 中的性能瓶頸。例如，基于 FRI 的 SNARK 需要接近 100 GB 的證明空間，即使對于小型電路也是如此。它們還需要 FFT，這是一種超線性運算，如果 SNARK“同時”應用于大型電路，則可能成為瓶頸。

現(xiàn)實情況是，一些 SNARK（例如 Lasso 和 Jolt）表現(xiàn)出規(guī)模經濟（而不是當前部署的 SNARK 中的規(guī)模不經濟）。這 意味著被證明的語句越大，相對于直接證人檢查（即在不保證正確性的情況下評估證人電路所需的工作），證明者開銷越小。在技??術層面，規(guī)模經濟來自兩個地方。 

1. n大小的 MSM的 Pippenger 加速：相對于樸素算法的log( n ) 因子改進。n越大，改善越大。
2. 在 Lasso 等查找參數(shù)中，證明者支付“一次性”成本，該成本取決于查找表的大小，但與查找的值的數(shù)量無關。一次性證明者成本在對表的所有查找中進行攤銷。更大的塊意味著更多的查找，這意味著更好的攤銷。

當今處理大型電路的流行方法是將事物分解成盡可能小的部分。每個部分的大小的主要限制是它們不能太小，以至于遞歸聚合證明成為證明者的瓶頸。 

Lasso 和 Jolt 提出了一種本質上相反的方法。人們應該使用具有規(guī)模經濟性的 SNARK。然后將大型計算分解為盡可能大的部分，并對結果進行遞歸。每個片段大小的主要限制是證明空間，它隨著片段變大而增長。

#4：高度約束對于高效的 SNARK 是必要的。 

Jolt 使用 R1CS 作為其中間表示。在 Jolt 中使用“高度”或“自定義”約束沒有任何好處。Jolt 中的證明者成本大部分在于查找參數(shù) Lasso，而不是證明將查找視為理所當然的結果約束系統(tǒng)的可滿足性。 

Jolt 是通用的，因此它不會失去通用性。因此，它反駁了開發(fā)人員對設計高度約束（通常是手動指定）的強烈關注，以努力從當今流行的 SNARK 中擠出改進的性能。 

當然，某些上下文仍然可能受益于高度或自定義約束。一個重要的例子是Minroot VDF，其 5 度約束可以將承諾成本降低約 3 倍。

＃5：稀疏多項式承諾方案成本高昂，應盡可能避免。

這是針對最近引入的名為CCS 的約束系統(tǒng)和支持它的 SNARK 的主要批評——（超級）斯巴達和（超級）馬林魚。正如我在上一篇文章中所討論的，CCS 是當今實踐中流行的所有約束系統(tǒng)的清晰概括。 

這種批評是沒有根據的。事實上，Lasso 和 Jolt 的技術核心是Spartan中的稀疏多項式承諾方案（參見第 7 節(jié)），稱為 Spark。Spark 本身是將任何（非稀疏）多項式承諾方案通用轉換為支持稀疏多項式的方案。 

Lasso 優(yōu)化并擴展了 Spark，以確保證明者只承諾“小”值，但即使沒有這些優(yōu)化，批評也是不合理的。事實上，Spartan 的證明者比SNARK （例如避免稀疏多項式承諾的 Plonk）承諾更少的（隨機）字段元素。

正如我在上一篇文章中所討論的，Spartan 的方法具有額外的性能優(yōu)勢，特別是對于具有重復結構的電路。對于這些電路，加法門不會增加 Spartan 證明者的加密工作。這項工作僅隨著給定約束系統(tǒng)中變量的數(shù)量而增長，而不是隨著約束的數(shù)量而增長。與 Plonk 不同的是，Spartan 證明者無需提交同一變量的多個不同“副本”。

***

我們樂觀地認為 Lasso 和 Jolt 將極大地改變 SNARK 的設計方式，從而提高性能和可審計性。本系列的后續(xù)文章將更深入地探討 Lasso 和 Jolt 的工作原理。特別是，我將解釋他們對和檢查協(xié)議的使用，這是一種具有神奇能力的關鍵工具，可以最大限度地減少證明者的承諾成本。隨著我們繼續(xù)優(yōu)化 Lasso 和構建 Jolt，我們歡迎來自社區(qū)的反饋。您可以在這里聯(lián)系我，我也會在那里宣布未來的工作。 

***

致謝：Justin Thaler 與同事Srinath Setty（微軟研究院）、Riad Wahby（卡內基梅隆大學）和Arasu Arun（紐約大學）一起開發(fā)了 Lasso 和 Jolt；Lasso 的實現(xiàn)是由 a16z 加密工程師Sam Ragsdale和Michael Zhu完成的。 

***

Justin Thaler是 a16z 的研究合伙人，也是喬治城大學計算機科學系的副教授。他的研究興趣包括可驗證計算、復雜性理論和海量數(shù)據集算法。