ZK 技術的歷史發展脈絡梳理

撰文：Lambda Class

編譯：白丁、Faust、Nickqiao

英文原文發佈於 2024 年 2 月 17 日

零知識證明 (ZK Proofs) 是功能強大的密碼學原語，允許一方（證明者）在不透露任何私密信息的情況下，使另一方（驗證者）相信某個給定的聲明是真實有效的。近年來 ZK 在可驗證私密計算、為計算機程序提供有效性證明以及區塊鏈領域獲得了廣泛關注，並且對世界的發展產生了重大的積極作用。

雖然 ZK 是新興技術，但其基本思想和概念可以追溯到上世紀 80 年代。在與比特幣和以太坊等區塊鏈結合後，ZK 技術的發展顯著加速，因為區塊鏈可以通過 SNARK 和 STARK 進行有效性證明，極大程度的增強可擴展性，這使 ZK 在區塊鏈領域中炙手可熱。

正如 Starkware 創始人 Eli Ben-Sasson 所言，近年來我們見證了密碼學證明系統的「寒武紀大爆發」，每種證明系統各有獨特的優勢和劣勢，並且在設計時進行了權衡。硬件的進步、更好的算法、新的論點和周邊工具，都刺激了 ZK 系統的性能提升及新式系統的誕生。許多證明系已經在實際應用中被採用，而人們仍在不斷擴展 ZK 的邊界。

這也促使人們深入思考一個問題：是否有一個適用於所有應用的通用 ZK 證明系統？對此我們認為這種可能性不大，原因有三點：

1. 應用程序的多樣性；

2. 不同的約束類型（包括內存、驗證時間、證明時間）；

3. 對魯棒性的需求（如果一種證明系統被黑客攻破，我們仍然可以切換到其他系統作為保險）。

基於上述理由，ZK 證明系統理應是多樣性的。但即使證明系統的種類很多，也一定有一個顯著的共性：ZK 證明可以被快速的驗證，並且擁有一個驗證層，可以很容易地適應新的證明系統，以解決其依附的基礎層（如以太坊）的相關困難。

在 ZK 領域中，zk-SNARK 被頻繁提及。它是實現零知識證明的一種形式，通過使用複雜的數學工具，如雙線性配對和算術電路，來實現高效的零知識證明。zk-SNARK 的特點是證明過程簡潔化、非交互式，證明者和驗證者之間只需要單次通訊不需要多次交互。此外，zk-SNARK 的證明尺寸非常短小，驗證效率高，適合在資源有限的環境中使用。

而 zk-STARK 是另一種常見的形式，旨在克服 zk-SNARK 的某些侷限性。zk-STARK 不依賴於可信設置，使用更透明的數學構造系統，如多項式承諾和有限域運算、哈希碰撞等，來生成和驗證證明。zk-STARK 比 zk-SNARK 更具可擴展性，適用於更大規模的計算，證明生成速度更快，但是 Proof 本身的尺寸通常較大。

可以說，zk-SNARK 和 zk-STARK 都是零知識證明中常用的形式，但它們在透明度、可擴展性、證明大小等方面有所不同。

總體來看，一個 ZK 證明系統通常包括 PIOP（多項式交互式預言機）和 PCS（多項式承諾方案）兩大部分。常見的 PIOP 方案包括 PLONKish、GKR 等，而常見的 PCS 方案包括 FRI，KZG，IPA 等，比如 Zcash 版本的 Halo2 使用了 Plonkish+IPA 的實現方式，至於 zk-STARK 其實可以當成是一種基於 FRI 的特殊的 zk-SNARK。

如果更詳細的說，不同類型的證明系統會使用不同的多項式承諾方案 (PCS)、算術化方案、交互式預言機證明 (IOP) 或概率可檢查證明 (PCP)。

進一步說，不同的 ZK 證明系統往往在如下指標上有所不同：

• 密碼學假設：抗碰撞哈希函數、橢圓曲線上的離散對數問題、指數知識

• 透明設置 vs 可信設置

• 生成證明的耗時：線性 vs 超線性

• 驗證證明的耗時：常數時間、對數時間、次線性、線性

• 證明尺寸的大小

• 遞歸的簡易性

• 算術化方案

• 單變量 vs 多變量多項式

下文中我們將簡要談及 ZK 技術的起源，探索其基本的構建模塊，概述不同 ZK 證明系統的興起和衰落過程。同時，本文並不對證明系統本身進行詳盡分析，而是著重介紹那些對該領域產生深遠影響的人，畢竟任何行業的發展只有通過先驅者的偉大想法並訴諸實踐，才有可能實現。

zk-SNARK 的歷史發展脈絡

起源：20 世紀 80~90 年代

正如我們所提到的，零知識證明並不是新概念，其定義、基礎、重要定理，甚至相關的重要協議，早在上世紀 80 年代中期就已經出現，首次出現是在是在 Goldwasser、Micali(Algorand 創始人 ) 和 Rackoff 的論文《The Knowledge Complexity of Interactive Proof Systems》中。

而如今我們用來構建 ZK-SNARK 技術的關鍵思想和協議，在 20 世紀 90 年代就被出，比如 Sumcheck 協議，將對多元多項式求值總和的聲明，簡化為在橢圓曲線上隨機選擇的點進行單一求值，該協議為 ZK 技術奠定了重要基礎。

所以，ZK 思想的萌芽實際上遠遠早於比特幣的出現，但在當時普遍缺乏 ZK 的合適用例，人們也無法提供滿足 ZK 證明系統所需的強大算力，畢竟互聯網和硬件設備在上世紀 90 年代並不發達。

GKR 協議（2007)

GKR（Goldwasser-Kalai-Rothblum）是一種交互式協議，證明者的運行時間與電路中邏輯門的數量呈線性相關，而驗證者的耗時則與電路大小呈次線性關係。在 GKR 協議中，證明者和驗證者需要對一個有限域上的雙輸入算術電路運行結果達成一致，該電路的深度為 d，第 d 層為輸入層，第 0 層為輸出層。協議從關於電路輸出的聲明開始，通過遞歸將其簡化為對上一層的聲明。最後，我們可以將對輸出的聲明轉換為對電路輸入參數的聲明，這很容易被驗證。可以說，GKR 協議是在前面提及的 Sumcheck 協議基礎上進行了高度簡化的。

KZG 多項式承諾方案 (2010)

2010 年，三名 ZK 領域的專家——來自德國研究機構 MPI-SWS 的 Kate，來自加拿大密碼學公司 Certicom Research 的 Zaverucha，以及來自滑鐵盧大學的 Goldberg 聯合發表了一篇論文《Constant-Size Commitments to Polynomialsand Their Applications》。該論文提出了一種使用雙線性對群的多項式承諾方案，名為 KZG。

該承諾由一個單獨的群元素組成，提交者可以高效地揭示多項式的任何正確求值，藉助批處理技術，可以對多個多項式的求值進行揭示。KZG 承諾成為了一些知名 ZK 證明系統的基本構建模塊之一（比如以太坊 PES 小組用的 halo2），更是在以太坊的 EIP-4844 中起到了核心作用。若要更直觀地瞭解批處理技術的概念，可以參考關於 Mina-Ethereum 橋的文章 Mina-Ethereum bridge。

參考資料：https://blog.lambdaclass.com/mina-to-ethereum-bridge/

基於橢圓曲線的實用 ZK-SNARK 系統（2013）

ZK-SNARK 的第一個實用結構出現在 2013 年，需要一個預處理步驟來生成證明密鑰和驗證密鑰，並且是隨程序或電路特定的，沒有泛用化。這些密鑰的尺寸可能非常大，並取決於秘密參數本身；若這種保密性被破壞，攻擊者就可以偽造出證明。在這種實用的 ZK-SNARK 系統中，要將代碼轉換為可以被證明的形式，需要將代碼編譯為一組數學形式的多項式約束。

起初，上述過程必須手動完成，既耗時又容易出錯。後來針對該方向的技術更迭，主要試圖解決下述核心問題：

1. 提供更高效的證明

2. 減少預處理的次數

3. 實現通用的而非電路特定的設置

4. 避免可信設置

5. 開發使用高級語言描述電路的方法，而不是手動編寫多項式約束

Pinocchio 協議（2013）

Pinocchio 協議是第一個實際可用的 zk-SNARK 系統，基於二次算術程序（QAP），最初的證明大小為 288 字節。Pinocchio 的工具鏈提供了一個將 C 語言編譯為算術電路的編譯器，它可以進一步轉換為 QAP。Pinocchio 協議要求驗證者生成密鑰，這些密鑰並不通用，而是由電路特定的。該證明系統生成和密鑰設置的漸進時間複雜度與計算規模呈線性關係，驗證時間與公共輸入和輸出的大小呈線性關係。

Groth16(2016)

Groth 引入了一種新的 ZK 明算法，在處理 R1CS 上具有更高的性能。R1CS 即 Rank-1 Con­straint Sys­tem，一階約束系統，是 zk-SNARK 中的一種多項式約束形式。Gorth 的證明是數據規模最小的（僅包含三個群元素），且驗證速度很快，只需進行三個配對運算，以及一個使參考字符串結構化的預處理步驟。但 Gorth 主要的缺點是每個需要證明的程序都需要進行不同的可信設置，這在實際應用中相當不便。

後來 Groth16 被用於 ZCash，後者是一個比較有名的隱私區塊鏈項目（Starkware 創始人 Eli 參與做的）。

Bulletproofs 與 IPA（2016）

前面提到的 KZG 多項式承諾方案，其一大弱點是需要可信設置。Bootle 等人提出了一種有效的零知識證明系統，該系統對滿足內在乘積關係的 Pedersen 承諾的開啟進行了分析。內積證明具有線性複雜度的證明耗時，證明者和驗證者之間的交互次數是對數級的，但驗證時間是線性的。此外 Bootle 等人還開發了一種不需要可信設置的多項式承諾方案。這些思想後來被 Halo2 和 Kimchi 等採用。

Sonic、Marlin 和 Plonk（2019）

Sonic、Plonk 和 Marlin 解決了 Groth16 算法中每個程序都需要可信設置的問題，引入了通用且可更新的結構化參考字符串（用來實現僅需一次的可信設置）。其中，Marlin 提供了一個基於 R1CS 的證明系統，並且成為了 Aleo 的核心技術。

而 Plonk 引入了一種新的算術方案（後來被稱為 Plonkish）以及使用 grand-product 來檢查複製約束。Plonkish 還允許引入用於特定操作的專用電路邏輯門，即所謂的「自定義門」。許多知名的區塊鏈項目方都用到了 Plonk 的定製化版本，包括 Aztec、zkSync、Polygon zkEVM、Mina、以太坊 PSE 小組和 Scroll 等。

Spartan（2019）

Spartan 為使用 R1CS 描述的電路提供了一個 IOP，利用了多變量多項式和求和檢驗協議的特性。通過使用合適的多項式承諾方案，它實現了一套具有透明性的 zk-SNARK 系統，並且生成證明的時間複雜度是線性的。

Lookups(2020)

Gabizon 和 Williamson 於 2020 年在論文中提出了 plookup，利用 grand-product 證明某個值包含在預先計算出的真值表中，展示瞭如何將 plookup 參數引入 Plonk 算法。

然而，這些 lookup arguments 有一個共同的問題，證明者需要耗費巨大成本建立完整的真值表，因此之前圍繞著 Lookups 的工作都致力於將證明成本減少。

後來 Haböck 在論文中引入了 LogUp，它使用對數導數將 grand-product 檢查轉化為倒數之和。LogUp 對於 Polygon zkEVM 的性能提升至關重要，因為他們需要將整個真值表拆分為多個 STARK 模塊。這些模塊必須正確鏈接，而跨表查找可以強制實現這一點。此後 LogUp-GKR 的引入又通過 GKR 協議提高了 LogUp 的性能。

Caulk 是第一個使證明時間與真值表大小呈亞線性關係的方案，它的預處理時間複雜度為 O(NlogN)，存儲佔用的空間複雜度為 O(N)，其中 N 是真值表大小。隨後又出現了其他方案，如 Baloo、flookup、cq 和 caulk+。此外，Lasso 提出了若干改進方案，避免在真值表具有特定結構時對其進行承諾。

HyperPlonk（2022）

HyperPlonk 在論文《HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates》中被提出。HyperPlonk 基於 Plonk 的理念，採用多變量多項式。它不使用除法來檢查約束的執行，而是依賴於求和檢驗協議。同時，它還支持高階約束，而不會影響證明生成的時間。

由於使用了多變量多項式，無需執行快速傅里葉變換（FFT），證明生成的時間與電路規模成線性關係。HyperPlonk 還引入了一種適用於小字段的新置換 IOP，並且採用基於求和檢驗的協議，減少了證明者的工作量、證明大小，以及驗證時間。

使用防碰撞哈希函數的 ZK 證明系統

在 2013 年 Pinocchio 被提出的同時，有一些關於生成電路 / 算術化方案的方案，這些方案可以證明虛擬機對指令的執行結果正確。儘管為虛擬機開發算術化方案比為某些程序編寫專用電路更復雜或效率更低，但它卻有一個重要優勢：無論程序多複雜，只需證明其在虛擬機中是正確執行的即可。

TinyRAM 中的一些想法後來在 Cairo 虛擬機的設計中得到了改進，隨後又有了 zk-evm 和通用 zkvm 等。在證明系統中使用抗碰撞的哈希函數消除了對可信設置或橢圓曲線操作的需求，但代價是證明時間更長。

TinyRAM（2013）

在「SNARKs for C」中，他們基於 PCP 開發了一種證明系統，用於證明 C 語言編寫的程序的執行結果正確。該程序被編譯為 TinyRAM，一種簡化的 VM。該 VM 具有字節級可尋址的隨機存儲器，電路大小在計算規模上呈准線性增長，可以高效地處理循環、控制流和內存訪問等操作。

其中，PCP 指 Probabilistically Checkable Proof，即概率可檢查證明，驗證者只需閱讀證明中隨機選擇的一小部分內容，就能以很高的置信度檢查證明的有效性。與驗證者需要檢查整個證明的傳統證明系統不同，PCP 只需有限的隨機性即可實現高效驗證。

Ligero（2017）

Ligero 引入了一套證明系統，該系統可實現大小為 O(√￣n) 的證明，其中 n 是電路的大小。它以矩陣形式排列多項式係數。Brakedown 基於 Ligero 構建，並引入了領域無關的多項式承諾方案的概念。

STARKs（2018）

STARKs（Scalable Transparent ARguments of Knowledge）由 Eli Ben-Sasson 等人於 2018 年提出。它們實現了𝑂(log²⁡𝑛) 的證明覆雜度，具有快速的驗證速度，不需要可信設置，並且被推測為後量子安全。它們被 Starkware/Starknet 與 Cairo 虛擬機一起投入採用。其關鍵創新包括代數中間表示（AIR）和快速 Reed-Solomon 交互式 Oracle 接近證明（FRI）協議。另外，STARKs 也被許多知名的區塊鏈項目所使用（如 Polygon Miden、RiscZero、Winterfell、Neptune 以及 ZeroSync、zkSync 等）。

新的發展方向

不同的證明系統在實際應用中的使用展示了不同方法的優點，並推動了 ZK 的發展。例如，Plonkish 的算術化方案提供了一種簡單的方法，來包含自定義邏輯門和 lookup arguments；FRI 已經顯示出作為 PCS 的出色性能，促成了 Plonky 的誕生。同時，在 AIR 中使用 grand-products 檢查（帶來了預處理的隨機化 AIR）提高了其性能並簡化了內存訪問參數。zk-STARK 由於在生成效率上更好，且有越來越多的 ZK 友好型哈希函數被引入，而越來越受歡迎。

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

隨著基於多變量多項式的高效 SNARK（如 Spartan 或 HyperPlonk）的出現，人們對適用於此類多項式的新承諾方案的興趣日益增加。Binius、Zeromorph 和 Basefold 都提出了新的方式來承諾多線性多項式。Binius 的優勢在於表示數據類型時沒有額外開銷（而許多其他證明系統至少使用 32 位字段元素來表示單個位），並且在二進制域上工作。該承諾方案採用了為領域無關而設計的 brakedown。Basefold 將 FRI 推廣到除 Reed-Solomon 之外，從而實現了領域無關的多項式承諾方案（PCS）。

領域無關是多項式承諾方案的一個性質，指多項式承諾方案中，承諾過程不依賴於任何特定領域的特定屬性。這意味著可以對任何代數結構的多項式做出承諾，如有限域、橢圓曲線，甚至整數環。

可定製約束系統（2023）

CCS 泛化了 R1CS，同時捕捉了 R1CS、Plonkish 和 AIR 的算術化，而沒有額外開銷。使用 CCS 與 Spartan IOP 結合可以產生 SuperSpartan，它支持高維度約束，而證明者無需承擔與約束階數成比例的加密成本。特別地，SuperSpartan 為 AIR 提供了一個具有線性時間證明的 SNARK。

總結

這篇文章綜述了自上世紀 80 年代中期以來 ZK 技術的進展。計算機科學、數學和硬件的進步，加上區塊鏈的引入，催生了新的、更高效的 ZK 證明系統出現，為許多可能改變社會的應用開闢了道路。

研究人員和工程師們根據需求提出了 ZK 系統的改進方案，重點圍繞在證明尺寸大小、內存使用程度、透明度、抗量子安全性、證明時間和驗證時間等方面。雖然一直以來，ZK 的主流實現方案有兩大類（SNARK 與 STARKs），但這兩者之間的界限已經逐漸模糊，不同證明系統的優勢正被結合起來，例如結合不同的算術化方案與新的多項式承諾方案。

我們可以預期，新的 ZK 證明系統將繼續湧現，且性能會不斷提升。對於使用這些證明系統的應用來說，如果不能跟隨最新技術的迭代發展，不斷重構並應用最新的算法，現在的領先地位也只是暫時的。