零知識的知識（zk-SNARKs）是一種強大的密碼學原語，能夠實現驗證者對某種陳述的正確性進行證明。它在可驗證私人計算、電腦程式正確性證明和區塊鏈擴展等方面得到了廣泛應用。自1980年代中期以來，出現了許多不同類型的論證系統，如皮諾丘、格羅斯16和STARKs等。然而，目前並沒有通用的證明系統能夠適用於所有應用。在過去的幾年中，SNARKs的發展已經大大加速，但它們仍存在一些適應性的問題。同時，一些新的證明系統，如索尼克、馬林魚和普朗克等，也不斷出現。這些系統的性能和適用性也隨之提高。未來，我們可以預期會看到更多新的證明系統的出現，並且效能也會不斷提高。
作者：LambdaClass
翻譯：mutourend；一平，IOSG Ventures
1.引言
零知識、允許簡潔、非飲酒知識論證（zk-SNARKs），是一種強而有力的密碼學原語，論證者說服驗證者某種陳述的正確性，並據此闡明目前的任何資訊。在可驗證私人計算、電腦程式執行正確性證明和區塊鏈擴展方面的應用，zk-SNARKs 受到了廣泛關注。我們相信，正如我們在文章中所描述的那樣，zk-SNARKs 將使計算世界產生重大影響zk-SNARKs主題採用了不同類型的論證系統，使用了不同的捕撈式濃度方案、算化方案、吸血鬼機術或機率可檢驗論證。但這些基本思想和概念可追溯至1980年代中期。自從比特幣和以太坊推出以來，zk-SNARKs的發展大大加速，因為它們能夠透過使用零知識證明（通常被稱為這種特定場景的有效證明）進行擴展。 zk-SNARKs在區塊鏈上可擴展性正如Ben-Sasson，近年來看到了加密貨幣論證的所述寒武紀爆發。終結論證系統具有優勢和劣勢，設計時都考慮了特定的權衡。硬體、演算法、新證明和工具的進步不斷提高效能，也催生了新系統的誕生。這些系統中許多已經投入使用，而我們不斷突破界限。我們是否會擁有適用於所有應用的通用證明系統，或者將會幾種適用於不同需求的系統？我們認為一個證明系統能夠統治所有其他系統的可能性很小，原因包括：
1）應用的多樣性。
2）不同的限制類型（關於記憶體、驗證時間長、證明時間長）。
3）對魯棒性的需求（如果一個證明系統被破壞，還有其他證明系統）。
即使證明系統發生了很大的變化，它們都提供了一個重要的特性：證明可快速驗證。擁有一個驗證證明並且可以輕鬆適應新的證明系統的層，解決了與更改基礎層（如坊以太）相關的問題這篇文章將概述SNARKs 的不同特徵：
1）密碼學假設：抗碰撞曲線函數、橢圓曲線上的曲線對數問題、指數知識。
2）透明與可信任設定。
3）證明時長：線性vs 超線性。
4）驗證器時間：恆定時間、對數、次線性、線性。
5）打樣尺寸。
6）易於下跌。
7）算術化方案。
8）單指標顯示式與多指標顯示式。
本文將討論SNARKs 的起源、一些基本模組建構以及不同論證系統的興起（和衰退）。本文無意對論證系統進行精彩的分析。相反，只關注那些對我們有影響的人。當然，這些發展只有透過該領域先驅者的偉大工作和想法有可能實現。
2.基礎知識
零知識論證並不新鮮。定義、基礎、重要定理、甚至重要協議都是從1980 年代中期開始製定的。用於建構現代SNARKs 的一些關鍵思想和協議是在20 世紀90 年代提出的（sumcheck）協議），甚至是在比特幣出現之前（2007年的GKR）。使用它的主要問題與缺乏豐富的例子（互聯網在20世紀90年代並不發達）以及所需的計算能力有關。
1）零知識名稱：起源(1985/1989)。
零知識論證領域隨著Goldwasser、Micali和Rackoff《交互證明系統的知識複雜性》論文出現在學術文獻中。起源的討論，可觀看2023年1月影片ZKP MOOC講座1：ZKP簡介和歷史。該論文引入了完整倍性、可靠性和零知識性的概念，提供了二次剩餘性和二次非剩餘性的構造。
2）Sumcheck協議（1992）。
sumcheck 協議由Lund、Fortnow、Karloff 和Nisan 於1992 年提出的互動式證明系統代數方法。它是簡潔的互動式證明最重要的建置模組之一。它幫助我們將多指標證明式評估需求和減少要求隨機選擇點的單一評估。
3）Goldwasser-Kalai-Rothblum (GKR) (2007)。
GKR協議（見論文Delegating Computation: Interactive Proofs for Muggles）是一種協議，其證明者根據電路的閘數線性運行，而驗證者則根據電路的大小線性運行。在協議中，證明者和驗證者就深度為d dd的有限域的fan-in-two侵犯電路完成一致，其中layer d dd對應輸入層，layer 0 00對應輸出層。該協定從有關電路輸出的聲明開始，該聲明被簡化為對前一層值的語句。使用遞歸，可以將其轉換為對電路輸入的語句，從而可以輕鬆檢查。這些減少是透過sumcheck 協議實現的。
4）KZG多項式承諾方案（2010）。
Kate、Zaverucha和Goldberg在2010年Constant-Size Commitments to Polynomials and Their applications引入了使用雙線性配置群的示範式行動方案。行動由單一群體元素組成，行動者可有效地打開對示範式的任何正確評價的承諾。此外，由於批次技術，可以對多個評估進行開啟。 KZG 承諾為幾個高效的SNARKs 提供了基本構建模組之一，如Pinocchio、Groth16 和Plonk。它也是EIP-4844 的核心。要理解地了解batching技術，可參考Mina到以太坊ZK橋。
3.使用橢圓形的實用SNARK
SNARKs 的第一個實用結構出現在2013 年。這些構造需要修復步驟來產生證明和驗證金鑰，並且是特定於程式/電路的。這些金鑰可能非常大，並且依賴大家不知道的秘密參數；否則，可格式化校樣。將程式碼轉換為可證明的程式碼需要將程式碼編譯為示範式約束系統。終止，這必須以手動方式完成，既運行又容易出錯。該領域的進展試圖消除一些主要因素問題：
1）擁有更有效率的證明者。
2）減少租金量。
3）具有通用性而非電路特定的設定。
4）避免使用可信任設定。
5）開發使用高階語言描述電路的方法，不受手動編寫式約束。
目前，使用橢圓形的實用SNARK方案有：
1）匹諾曹(2013)
2）格羅斯16 (2016)
3）防彈與IPA (2016)
4）索尼克、馬林魚和普朗克(2019)
5）查找（2018/2020）
6）斯巴達(2019)
7）超級波隆克（2022）
8）折疊方案（2008/2021）
3.1 匹諾曹(2013)
Pinocchio（見論文Pinocchio：近乎實用的可驗證計算）是第一個實用、可用的zk-SNARK。 SNARK基於二次算術程序（二次算術程序，QAP）。證明大小最初為288位元組。 Pinocchio的工具鏈提供了從C程式碼算術到電路的編譯器，並進一步轉換為QAP。該協議要求驗證者產生特定於電路的鑰匙。它使用橢圓形的造型來檢查方程式。證明產生和鑰匙設定的漸進近與計算大小呈線性關係，驗證時間長與公共輸入和輸出的大小呈線性關係。
3.2 格羅斯16（2016）
Groth 2016年論文On the Size of Pairing-based Non-interactive Arguments引入了一種新的知識轉化，提高了由R1CS問題的性能。它具有最小的證明大小（三個僅群元素）和三個涉及描述配對的快速驗證。它還涉及獲取構造參考字串的修復步驟。主要是，待證明每個程式都需要不同的可信設置，這很不方便。 Groth16 曾用於ZCash。詳情也可參考部落格Groth 16證明系統概述。
3.3 Bulletproofs 和IPA (2016)
KZG PCS 的缺點之一是它需要可信的設定。 Bootle 等人2016 年離散日誌設定中算術電路的高效零知識論證論文中引入了滿足內積（內積）關係的Pedersen 承諾開放的有效零知識運算系統。內積證明系統有一個線性證明者，具有對資料通訊和交互作用的作用，但具有線性時長驗證。其也發展了一種不需要可信設定的示範式證明方案。 Halo 2 和Kimchi 都採用了採用IPA PCS思想。
3.4 索尼克、馬林魚和普朗克(2019)
Sonic、Plonk和Marlin透過引入通用且可更新的格式化參考字串，解決了Groth16中每個程式的可信任設定問題。 Marlin提供了基於R1CS的證明系統，是Aleo的核心。
Plonk引入了一種新的術化方案（後來稱為Plonkish），文獻複製約束使用大型產品檢查。 Plonkish還允許為某些操作引入專門的門，即所謂的定制門。多個專案都有Plonk 的定製版本，包括Aztec、ZK-Sync、Polygon ZKEVM、Mina’s Kimchi、Plonky2、Halo 2 和Scroll 等。可參考部落格所有你想了解的Plonk。
3.5 查找（2018/2020）
Gabizon 和Williamson 在2020 年引入了plookup，使用大乘積檢查來證明某些值包含在預先計算的值表中。先前在Arya 中提出了查找參數，但其構造需要確定儘管查找的多重性，效率較低PlonkUp 論文展示瞭如何將plookup 參數引入Plonk。這些查找參數的問題在於，它們足以證明者為整個表格的支付費用，而與之查找次數無關。這意味著大型表的成本相當大，並且已投入大量的精力將證明者的成本降低到其使用的查找數量。
Haböck 引入了LogUp，它利用對數導數將乘積檢查轉換為倒數總和。 LogUp ForPolygon plonky2 ZKEVM（Beyond Limits: Pushing the Boundaries of ZK-EVM）的效能關鍵，其需要將整個表格拆分為多個STARK 模組。這些模組必須正確鏈接，並跨表查找來強化此操作。 LogUp-GKR 的推出利用GKR 協定來提升LogUp 的效能。 Caulk 是第一個證明者時間與表大小呈亞線性關係的查找論證，其重建時長為O ( N log N )且儲存為O ( N ) ，其中N為表大小。另外出現了其他幾個方案，如Baloo、flookup、cq和caulk+。 Lasso提出了對應的方案改進，避免在表具有給定結構時對其進行提交。另外，Lasso 的說明者僅用於查找操作存取的表格邊界付費。 Jolt 利用Lasso 透過尋找來說明虛擬機器的執行情況。
3.6 斯巴達(2019)
Spartan 為使用R1CS 描述的電路提供了IOP，利用多指標示值式和sumcheck 協定的屬性。使用合適的指標式方案，它會產生具有線性時長證明器的透明SNARK。
3.7 HyperPlonk（2022）
HyperPlonk 是基於使用多指標示範式的Plonk 思想而建構。它不依賴商來檢查約束的執行情況，而是依賴sumcheck 協定。它仍然支援高度約束，而不會損害證明者的運行時間。依賴多指標指示式，因此消耗執行FFT，且證明者的運行時間與電路尺寸呈線性關係。 HyperPlonk 引入了適合較小範圍的新排列IOP 和基於sumcheck 的批量開放協議，這減少了證明者的工作量、證明大小和驗證者的時間。
3.8 折疊方案（2008/2021）
Nova引入了折疊方案的思想，是一種實現增量可驗證計算（IVC）的新方法。 IVC的概念可以是另外Valiant，其展示如何將2個長度為k kk證明，合併為，一個長度為k kk的證明。其想法為，可透過梯度證明，來證明由step i ii到step i + 1 i+1i+1的執行是正確的，且驗證由step i − 1 i-1i−1到步驟i ii 的封裝證明是正確的，從而證明任何長時間運行的計算。
Nova可以很好地處理均勻計算；後來隨著Supernova的引入，被分割處理不同類型的電路。 Nova使用R1CS的流行版本，並在圓形的橢圓形上工作。使用圓形的圓形循環（例如，Pasta）曲線）來實現IVC 也被用在Pickles 中，Pickles 是Mina 的主要基礎模組，以實現簡潔的狀態。然而，折疊的想法與多層SNARK 驗證不同。累加器的想法與批次證明的概念有更深入的Halo 引入了累加的概念作為梯度驅動組合的替代方案。 Protostar 為Plonk 提供了非均勻IVC 方案，支援高階閘和向量查找。
4. 使用抗碰撞雜湊函數的SNARK
大約在Pinocchio 開發的同時，出現了一些產生電路/算術的想法，可以證明虛擬機器執行的正確性。儘管開發虛擬機器的算術可能比某些程式編寫的專用電路更複雜或效率更高，但它提供了一個優點，即任何程序，無論多麼複雜，都可以透過證明它在虛擬機器中正確執行來證明。 TinyRAM中的想法後來隨著Cairo vm和後續虛擬機器（如zk-evms或通用zkvms）的設計而得到改進。使用抗碰撞雜湊函數消除了對可信設定或使用光滑圓弧半徑的需要，但代價是更大的證明。
1）TinyRAM (2013)
在SNARKs for C中，發展了一個基於PCP的SNARK，為證明C程式執行的正確性，該程式被編譯為TinyRAM（專業指令集電腦）。該電腦採用哈佛架構，具有位元組級可用隨機存取記憶體。利用非確定性，電路的大小與計算大小呈擬線性擬線性，從而關係有效地處理任何與資料相關的循環、控制流和記憶體存取。
2）史塔克(2018)
STARKs是由Ben Sasson等人於2018年提出。其實現的證明大小為O(log2n)，且具有快速證明者和驗證者，不需要可信設置，並且被認為是後量子安全的。其首先由Starkware/Starknet 與Cairo 虛擬機器一起使用。其關鍵部件包括：
代數中間表示(AIR)
和FRI協定（Fast Reed-Solomon Interactive Oracle Proof of Proximity）。
STARKs也被其他項目（Polygon Miden、Risc0、Winterfell、Neptune）使用，或其一些改編（ZK-Sync 的Boojum、Plonky2、Starky）。
3）利格羅(2017)
Ligero引進了一個證明系統，其證明大小為O(根號n)，其中n為電路大小。將公式的係數排列成矩陣形式並使用線性碼線性碼。
Brakedown建立在Ligero的基礎上，並引入了與域無關的大象式承諾方案的想法。
5. ZKP的一些新進展
在生產中使用不同的證明系統顯示了多種方法的優點，並帶來了新的發展。例如，plonkish算術化提供了一種簡單的方法來自訂包含門和查找參數；FRI作為PCS表現出了的效能，領先於Plonky。同樣，在AIR 中使用大乘積檢查（導致帶隙的隨機化AIR）提高了其性能並簡化了記憶體存取參數。基於雜湊函數的承諾已經流行起來了— — 基於硬體中樞函數的速度或引入新的SNARK 函數函數。
1）新的創意承諾方案（2023）
隨著基於多指示器式的高效能SNARK（如Spartan或HyperPlonk）的出現，人們對適合此類指示器式的新承諾方案越來越感興趣。 Binius、Zeromorph和Basefold都提出了新的形式致力於多線性Binius 用零頭來表示資料類型的優點（而許多論證系統使用至少32 位元域元素來表示單一位元）並在二進位域上工作。 Binius 承諾基於Brakedown，其設計目的是與域無關。 Basefold 將FRI推廣到Reed-Solomon以外的程式碼，從而形成與域相關的PCS。
2）可自訂約束系統（CCS）（2023）
CCS 成長了R1CS，同時捕捉了R1CS、Plonkish 和AIR 算術，耗費任何開支。將CCS 與Spartan IOP 結合使用會產生SuperSpartan，它支援高度約束，而消耗證明者要承擔受約束程度而擴展的加密貨幣成本。特別的是，SuperSpartan 為帶有線性時間證明器的AIR 產生SNARK。
6.結論
本文描述了SNARK 自20 世紀80 年代中期推出以來的進步。電腦科學、數學和硬體的進步，加上區塊鏈的引入，催生了新的、更有效率的SNARK，為許多可以改變我們社會的應用研究人員和工程師根據自己的需求提出了對SNARKs的改進和調整，重點在於證明大小、記憶體使用、透明設定、後量子安全、證明者時間和驗證者時間。
雖然最初有佔地主線（SNARK 與STARK），但兩者之間的界限已經開始淡化，嘗試結合不同論證系統的優點。例如，將不同的算術方案與新的論證式打擊方案結合。可預期，新的證明系統將繼續出現，性能也必然提高，而對於一些需要一些時間適應的系統來說，將很難跟上這些發展，除非可輕鬆地使用這些工具，而消耗了一些核心基礎設施。
資訊來源：0x資訊編譯自網際網路。版權歸作者IOSG所有，未經許可，不得轉載