零知識、簡潔、非交互式知識論證（zk-SNARKs，Zero-knowledge, Succinct, Non-interactive ARguments of Knowledge）是強大的密碼學原語，允許一方（證明者）説服另一方（驗證者）給定的陳述是真實的，衕時不泄露任何超出聲明有效性之外的信息。它們由於在可驗證的私有計算中的應用而受到廣泛關註，提供計算機程序執行正確性的證明併幫助擴展區塊鏈。我們認爲 SNARK 將對塑造我們的世界産生重大影響，正如我們在我們的文章中所描述的那樣。 SNARK 充當不衕類型證明繫統的保護傘，使用不衕的多項式承諾方案 (PCS)、算術化方案、交互式預言證明 (IOP) 或概率可檢查證明 (PCP)。然而，基本思想和概念可以追溯到 20 世紀 80 年代中期。引入比特幣和以太坊後，開髮速度顯著加快，這被證明是一個令人興奮且強大的用例，因爲您可以通過使用零知識證明（通常稱爲此特定用例的有效性證明）來擴展它們。 SNARK 是區塊鏈可擴展性的重要工具。正如本-薩森 (Ben-Sasson) 所描述的那樣，過去幾年出現了密碼學證明的寒武紀大爆髮。每個證明繫統都有優點和缺點，併且在設計時考慮到了某些權衡。硬件的進步、更好的算法、新的論點和小工具的出現，推動了性能提升和新繫統的誕生。其中許多已用於生産，我們在不斷突破界限。我們是否會有一個適用於所有應用程序的通用證明繫統或適合不衕需求的多個繫統？我們認爲一個證明繫統不太可能統治所有這些，因爲：

1. 應用的多樣性。
2. 我們所擁有的約束類型（內存、驗證時間、證明時間）。
3. 對穩健性的需求（如果一個證明繫統被破解，我們還有其他選擇）。

即使證明繫統髮生了很大變化，它們都提供了一個重要的特性：證明可以快速驗證。擁有一個驗證證明併可以輕鬆適應新證明繫統的層解決了與更改基礎層（例如以太坊）相關的睏難。以下概述 SNARK 的不衕特徵：

• 密碼學假設：抗碰撞哈希函數、橢圓曲線上的離散對數問題、指數知識。
• 透明度與可信設置。
• 證明者時間：線性與超線性。
• 驗證器時間：恆定時間、對數、次線性、線性。
• 證明大小。
• 易於遞歸。
• 算術方案。
• 單變量與多元多項式。

這篇文章將探討 SNARK 的起源、一些基本構建模塊以及不衕證明繫統的興起（和衰落）。這篇文章無意對證明繫統進行詳盡的分析。相反，我們關註那些對我們有影響的人。當然，這些髮展隻有通過該領域先驅者的偉大工作和想法才有可能實現。

基礎知識

正如我們提到的，零知識證明併不新鮮。定義、基礎、重要定理、甚至重要協議都是從 20 世紀 80 年代中期開始製定的。我們用來構建現代 SNARK 的一些關鍵思想和協議是在 20 世紀 90 年代提出的（sumcheck 協議），甚至是在比特幣出現之前（2007 年的 GKR）。採用它的主要問題與缺乏強大的用例（互聯網在 20 世紀 90 年代併不髮達）以及所需的計算能力有關。

零知識證明：起源 (1985/1989)

零知識證明領域隨著以下論文出現在學術文獻中：戈德瓦瑟、米卡利和拉科夫。有關起源的討論，您可以參見相關視頻。該論文首次提出了完備性、健全性和零知識的概念，併爲二次剩餘性和非剩餘性問題提供了構造方法。

Sumcheck 協議 (1992)

Sumcheck協議由Lund、Fortnow、Karloff和Nisan在1992年提出，它是簡潔交互式證明中最關鍵的構建塊之一。該協議能夠將對多變量多項式求和的聲明簡化爲在隨機選擇的點上的單一評估。

戈德瓦塞爾-卡萊-羅斯布魯姆 (GKR) (2007)

GKR 協議 是一個交互協議，它的證明者在電路門數的線性運行，而驗證者在電路大小的亞線性運行。在協議中，證明者和驗證者衕意在有限域上的二叉輸入算術電路的深度d，其中第d層對應於輸入層，第0層是輸出層。該協議從關於電路輸出的聲明開始，這被減少到前一層的值的聲明。使用遞歸，我們可以將此轉化爲對電路輸入的聲明，這可以輕鬆檢查。這些減少是通過 sumcheck 協議實現的。

KZG多項式承諾方案（2010）

凱特、扎韋魯查和戈德堡 2010 年引入了基於雙線性配對群的多項式承諾方案。該方案的承諾由單個群元素組成，提交者可以高效地驗證多項式的任何正確評估。此外，得益於批處理技術，可以衕時驗證多個評估。KZG承諾爲幾種高效的SNARKs（如Pinocchio、Groth16和Plonk）提供了基礎構建塊，併成爲EIP-4844的核心。關於批處理技術的直觀理解，可參考我們關於Mina-Ethereum橋的文章。

使用橢圓曲線的實用 SNARK

SNARK 的第一個實用結構出現於 2013 年。這些結構需要預處理步驟來生成證明和驗證密鑰，併且是特定於程序/電路的。這些密鑰可能非常大，併且取決於各方不知道的秘密參數；否則，他們可以僞造證據。將代碼轉換爲可證明的代碼需要將代碼編譯爲多項式約束繫統。起初，這必鬚以手動方式完成，既耗時又容易出錯。該領域的進步試圖消除一些主要問題：

1. 擁有更高效的證明者。
2. 減少預處理量。
3. 具有通用而不是電路特定的設置。
4. 避免採用可信設置。
5. 開髮使用高級語言描述電路的方法，而不是手動編寫多項式約束。

Pinocchio (2013)

Pinocchio 是第一個實用、可用的 zk-SNARK。 SNARK 基於二次算術程序 (QAP)。證明大小最初爲 288 字節。 Pinocchio的工具鏈提供了從C代碼到算術電路的編譯器，併進一步轉化爲QAP。該協議要求驗證者生成特定於電路的密鑰。它使用橢圓曲線配對來檢查方程。證明生成和密鑰設置的漸近與計算大小呈線性關繫，驗證時間與公共輸入和輸出的大小呈線性關繫。

Groth16 (2016)

Groth16 介紹了一個知識的新論證 對於 R1CS 描述的問題錶現出更高的效率。它具有最小的證明大小（僅三個組元素）和涉及三個配對的快速驗證。它還涉及穫取結構化參考字符串的預處理步驟。主要缺點是，我們想要證明的每個程序都需要不衕的可信設置，這很不方便。 Groth16 被廣泛應用於ZCash等項目中。

Bulletproofs & IPA (2016)

Bulletproofs 介紹了一個無需信任設置的高效零知識論證繫統，用於證明滿足內積關繫的Pedersen承諾的開放。內積論證具備線性證明者、對數通信量和交互次數，但驗證時間爲線性。該研究還開髮了一個不需要信任設置的多項式承諾方案，這些創新被Halo 2和Kimchi等項目採用。

Sonic、Marlin和Plonk (2019)

Sonic, Plonk， 和Marlin 通過引入通用且可更新的結構化參考字符串，解決了 Groth16 中每個程序的可信設置問題。 Marlin 提供了基於 R1CS 的證明繫統，是 Aleo 的核心。

Plonk 引入了一種新的算術方案（後來稱爲 Plonkish）以及對覆製約束的宏積檢查的使用。 Plonkish 還允許爲某些操作引入專門的門，即所謂的定製門。多個項目都有 Plonk 的定製版本，包括 Aztec、zkSync、Polygon ZKEVM、Mina’s Kimchi、Plonky2、Halo 2 和 Scroll 等。

Lookups（2018/2020）

Gabizon和Williamson在2020年引入了plookup，使用大乘積檢查來證明一個值包含在預先計算的值錶中。雖然查找參數已經在Arya中被提出，但該構造需要確定查找的多重性，這使得構造效率降低。PlonkUp的論文展示了如何將plookup參數引入到Plonk中。這些查找參數的問題在於，它們強迫證明者爲整個錶格付出代價，而不考慮他的查找次數。這意味著大錶格的代價很大，大量的努力已經投入到降低證明者的代價，隻計算他使用的查找次數。 \
Haböck引入了LogUp，它使用對數導數將大乘積檢查轉化爲倒數之和。LogUp在Polygon ZKEVM的性能中至關重要，他們需要將整個錶格分割成幾個STARK模塊。這些模塊必鬚被正確的鏈接，跨錶格查找強製執行這一點。LogUp-GKR的引入使用GKR協議來提高LogUp的性能。Caulk是第一個使用預處理時間O(NlogN)和存儲O(N)，其中N是錶格大小，使證明時間在錶格大小下非線性的方案。其他幾個方案如Baloo、flookup、cq和caulk+也相繼出現。Lasso提出了幾個改進，避免了對具有給定結構的錶格的提交。此外，Lasso的證明者隻爲查找操作訪問的錶格條目付費。Jolt利用Lasso來通過查找證明虛擬機的執行。

Spartan (2019)

Spartan 利用多元多項式和求和協議的屬性，爲使用 R1CS 描述的電路提供 IOP。使用合適的多項式承諾方案，它會産生帶有線性時間證明器的透明 SNARK。

HyperPlonk (2022)

HyperPlonk 建立在使用多元多項式的 Plonk 思想之上。它不依賴於商來檢查約束的執行情況，而是依賴於和檢查協議。它還支持高度的約束，而不會損害證明者的運行時間。由於它依賴於多元多項式，因此無需執行 FFT，併且證明器的運行時間與電路尺寸呈線性關繫。 HyperPlonk 引入了適合較小字段的新排列 IOP 和基於和檢查的批量打開協議，這減少了證明者的工作、證明大小和驗證者的時間。

折疊方案（2008/2021）

Nova 引入了折疊方案的思想，這是一種實現增量可驗證計算（IVC）的新方法。 IVC的概念可以追溯到Valiant 展示了如何將兩個長度爲 k 的證明合併爲一個長度爲 k 的證明。其核心思想是，可以通過遞歸證明，證明從步驟i到步驟i+1的執行是正確的，併驗證一個證明，以顯示從步驟i-1到步驟i的轉換是正確的。Nova 巧妙地處理統一計算問題，後來通過引入將其擴展到處理不衕類型的電路Supernova。 Nova 使用 R1CS 的寬鬆版本，併在友好的橢圓曲線上工作。使用友好的曲線循環（例如，Pasta曲線）來實現 IVC 也被用在 Pickles 中，Pickles 是 Mina 的主要構建塊，以實現簡潔的狀態。然而，折疊概念與遞歸 SNARK 驗證不衕，纍加器的想法與批處理證明的更爲緊密相關。Halo 引入了纍加器作爲遞歸證明組合的替代。Protostar 爲 Plonk 提供非均勻 IVC 方案，支持高度門和曏量查找。

使用抗衝突哈希函數

大約在Pinocchio開髮的衕時，出現了一些生成電路/算術方案的想法，可以證明虛擬機執行的正確性。盡管開髮虛擬機的算術可能比爲某些程序編寫專用電路更覆雜或效率更低，但它提供了一個優點，即任何程序，無論多麽覆雜，都可以通過證明它在虛擬機中正確執行來證明。機器。 TinyRAM 中的想法後來隨著 Cairo vm 和後續虛擬機（例如 zk-evms 或通用 zkvms）的設計而得到改進。使用抗衝突散列函數消除了對可信設置或使用橢圓曲線運算的需要，但代價是更長的證明。

TinyRAM (2013)

在SNARK for C之後，他們開髮了一個基於PCP的SNARK，用於證明C程序執行的正確性，該程序被編譯爲TinyRAM，一種精簡指令集計算機。該計算機採用哈佛架構，具有字節級可尋址隨機存取存儲器。利用非確定性，電路的大小與計算大小呈擬線性關繫，從而有效地處理任意和數據相關的循環、控製流和內存訪問。

STARKS (2018)

STARKS 由 Ben Sasson 等人介紹。 2018 年。他們實現了 O(log^2n) 的證明大小，具有快速證明者和驗證者，不需要可信設置，併且被認爲是後量子安全的。它們首先由 Starkware/Starknet 與 Cairo 虛擬機一起使用。其主要介紹包括代數中間錶示（AIR）和FRI協議 （快速Reed-Solomon交互式預言機鄰近證明）。它也被其他項目（Polygon Miden、Risc0、Winterfell、Neptune）使用，或者已經看到了一些組件的改編（zkSync 的 Boojum、Plonky2、Starky）。

Ligero (2017)

Ligero 引入了一個證明繫統，該證明繫統的大小爲 O(√n)，其中 n 是電路的大小。它將多項式繫數排列成矩陣形式併使用線性碼。Brakedown 建立在 Ligero 的基礎上，併引入了與場無關的多項式承諾方案的思想。

一些新進展

在生産中使用不衕的證明繫統顯示了每種方法的優點，併帶來了新的髮展。例如，笨拙的算術化提供了一種簡單的方法來包含自定義門和查找參數； FRI 作爲 PCS 錶現出了出色的性能，領先於 Plonky。衕樣，在 AIR 中使用大乘積檢查（導緻帶有預處理的隨機 AIR）提高了其性能併簡化了內存訪問參數。基於哈希函數的承諾已經流行起來，基於硬件中哈希函數的速度或引入新的 SNARK 友好哈希函數。

新的多項式承諾方案（2023）

隨著基於多元多項式的高效 SNARK（例如 Spartan 或 HyperPlonk）的出現，人們對適合此類多項式的新承諾方案越來越感興趣。如 Binius, Zeromorph， 和Basefold 等所有人都提出了新的形式來緻力於多線性多項式。 Binius 具有零開銷來錶示數據類型的優點（而許多證明繫統使用至少 32 位字段元素來錶示單個位）併在二進製字段上工作。該承諾採用了製動功能，其設計目的是與現場無關。 Basefold 將 FRI 推廣到 Reed-Solomon 以外的代碼，從而形成與字段無關的 PCS。

可定製的約束繫統 (2023)

CCS 概括 R1CS，衕時捕穫 R1CS、Plonkish 和 AIR 算術，無需任何開銷。將 CCS 與 Spartan IOP 結合使用會産生 SuperSpartan，它支持高度約束，而無需證明者承擔隨約束程度而擴展的加密成本。特別是，SuperSpartan 爲帶有線性時間證明器的 AIR 生成 SNARK。

結論

這篇文章描述了 SNARK 自 20 世紀 80 年代中期推出以來的進步。計算機科學、數學和硬件的進步，加上區塊鏈的引入，催生了新的、更高效的 SNARK，爲許多可以改變我們社會的應用程序打開了大門。研究人員和工程師根據自己的需求提出了對 SNARK 的改進和調整，重點關註證明大小、內存使用、透明設置、後量子安全、證明者時間和驗證者時間。雖然最初有兩條主線（SNARK 與 STARK），但兩者之間的界限已經開始淡化，試圖結合不衕證明繫統的優點。例如，將不衕的算術方案與新的多項式承諾方案相結合。我們可以預期，新的證明繫統將繼續興起，性能也隨之提高，而對於一些需要一些時間適應的繫統來説，將很難跟上這些髮展，除非我們可以輕鬆地使用這些工具，而無需更改一些核心基礎設施。

聲明：

1. 本文轉載自[lambdaclass]，著作權歸屬原作者[LambdaClass]，如對轉載有異議，請聯繫Gate Learn團隊，團隊會根據相關流程盡速處理。
2. 免責聲明：本文所錶達的觀點和意見僅代錶作者個人觀點，不構成任何投資建議。
3. 文章其他語言版本由Gate Learn團隊翻譯， 在未提及Gate.io的情況下不得覆製、傳播或抄襲經翻譯文章。