jakiro
零知識證明(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/
