零知識證明(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系統中，要將程式碼轉換為可以被證明的形式，需要將程式碼編譯為一組數學形式的多項式限制。
起初，上述過程必須手動完成，既耗時又容易出錯。後來針對該方向的技術更迭，主要試圖解決下述核心問題：
-
提供更有效率的證明
-
減少預處理的次數
-
實現通用的而非電路特定的設置
-
避免可信任設定
-
發展使用高階語言描述電路的方法，而不是手動編寫多項式約束
Pinocchio協定（2013）
Pinocchio協定是第一個實際可用的zk-SNARK系統，基於二次算術程序（QAP），最初的證明大小為288位元組。 Pinocchio的工具鏈提供了一個將C語言編譯為算術電路的編譯器，它可以進一步轉換為QAP。 Pinocchio協定要求驗證者產生金鑰，這些金鑰並不通用，而是由電路特定的。此證明系統產生和金鑰設定的漸進時間複雜度與計算規模呈線性關係，驗證時間與公共輸入和輸出的大小呈線性關係。
Groth16(2016)
Groth引進了一種新的ZK明演算法，在處理R1CS上具有更高的效能。 R1CS即Rank-1 Constraint System，一階約束系統，是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證明系統將持續湧現，且效能將持續提升。對於使用這些證明系統的應用來說，如果無法跟隨最新技術的迭代發展，不斷重構並應用最新的演算法，現在的領先地位也只是暫時的。
原文連結：https://blog.lambdaclass.com/our-highly-subjective-view-on-the-history-of-zero-knowledge-proofs/