來源：登鏈社區
零知識證明在近40 年中取得了顯著的發展，達到了前所未有的複雜性和效率水平。如今，每天都有新的論文和專案湧現，建立在豐富的思想和創新基礎上。
想知道這一切是如何開始的嗎？ 在這篇文章中，我們將深入探討零知識證明的歷史，探索10 篇幫助塑造這一領域的里程碑論文。
1 – 起源
Goldwasser, Micali, Rackoff – 互動式證明系統的知識複雜性(1985) [^1]
我們的第一個里程碑帶我們回到1985 年那篇開創性的論文！這項工作引入了許多術語和基礎概念，這些概念仍然是零知識證明的核心。
首先，論文定義了一個證明系統，其模型為一個涉及兩個機率圖靈機的雙方協議：一個證明者和一個驗證者。證明系統的目標是使證明者能夠說服驗證者某個給定輸入x 屬於正式語言L。在大多數早期工作中，證明者是計算上不受限制的，而驗證者則限制在多項式時間計算。在互動結束時，驗證者輸出「接受」或「拒絕」。
2 – 第一個應用
Fiat, Shamir – 如何證明自己：識別和簽署問題的實用解決方案(1986) [^2]
這篇由Fiat 和Shamir 撰寫的論文，發表於零知識證明基礎工作的一年後，介紹了這些概念的第一個實際應用。他們提出了兩個協議：一個識別方案，這是互動的，另一個是簽名方案，這是非互動式的。兩者之間的關鍵區別在於，在識別方案中，第三方可以透過製作有效的記錄來說服自己一個虛假的陳述。而在簽名協議中，即使是一個不誠實的證明者也無法說服自己一個虛假的陳述，從而使簽名不可偽造。
識別方案將二次剩餘性證明系統應用為互動式協議，其中驗證者發送隨機挑戰，證明者相應地回應。簽名方案透過用對雜湊函數的呼叫替換驗證者的挑戰來修改這一點。
作者的名字聽起來很熟悉嗎？這是一個強大通用技術的首次實例，現在被廣泛稱為Fiat-Shamir 啟發式。它使得透過用對隨機預言機的查詢（在實踐中是加密哈希函數）來取代驗證者的挑戰，將任何公共幣互動式證明系統轉換為非互動式的。
3 – 我們究竟能證明什麼？
Goldreich, Micali, Wigderson – 如何在零知識中證明所有NP 語句及密碼協議設計的方法論(1987) [^3]
這篇1986 年的論文給了一個顯著的結果：每個NP 中的語言都承認一個零知識證明系統。這很重要，因為這意味著我們可以在不透露額外資訊的情況下證明任何可以在多項式時間內驗證的陳述的真實性。作者透過提供一個圖的3-著色性的證明系統來展示這一點，該問題是確定圖的節點是否可以用三種顏色著色，使得沒有兩個相鄰的節點共享相同的顏色。此外，證明僅假設存在機率加密。
證明的直覺如下：在每一輪中，
- 證明者選擇三種顏色的隨機排列，
- 證明者承諾每個節點的排列顏色，
- 驗證者查詢兩個相鄰節點並詢問它們的顏色，
- 證明者透過揭示查詢節點的顏色來打開承諾。
- 如果顏色匹配，驗證者立即拒絕。
透過以多項式次數運行此協議，驗證者以高概率確信證明者知道有效的3-著色，而不學習任何信息，因為打開的顏色在每一步都是隨機的！
在這項工作中還有兩篇其他論文同樣值得注意：所有可證明的內容都可以在零知識中證明[^4]，該論文表明每個IP 中的語言都有一個零知識證明系統，以及IP = PSPACE [^5]，顯示IP 與PSPACE 一樣強大。
4 – PCPs 和簡潔非互動式證明的起源
Micali – 計算上可靠的證明(2000) [^6]
這篇2000 年的論文由Micali 撰寫，是零知識證明歷史上的重要貢獻。它甚至可以被視為第一個SNARK 構造，儘管當時尚未創造出SNARK 這個術語！
Micali 的構造將任何機率可檢查證明（PCP）轉化為簡潔且非互動的證明。 PCP 是可以透過只閱讀少量位元來驗證的證明，而一個關鍵結果，即PCP 定理 [^7]，表明每個NP 中的語言都有一個可以透過僅閱讀證明中的常數位元來驗證的PCP！
Micali 的構造使用梅克爾樹如下：
- 證明者為證明建造一個默克爾樹並將根發送給驗證者，
- 驗證者查詢他們希望檢查的特定位，
- 證明者提供這些位元的認證路徑，驗證者驗證這些路徑。
透過簡單應用Fiat-Shamir 啟發式，可以使該構造變為非互動式（這種轉換的一個互動版本是由Kilian 提出的 [^8]）。論文也關注計算效率：實際上，驗證者不需要接收整個證明，而只需接收常數數量的位元和認證路徑，這使得證明簡潔。這個系統的主要缺點是PCP 構造不切實際，這促使了互動式預言機證明（IOPs）的發展，IOPs 是PCP 的一種推廣，可以產生實用的論證。
5 – 雙重高效率的IPs
Goldwasser, Kalai, Rothblum – 委託計算：針對麻瓜的互動式證明(2015) [^9]
這篇論文強烈關注效率，並引入了廣為人知的GKR 協議，這是一個針對可用算術電路的公共幣互動協議。值得注意的是，驗證者和證明者都在多項式時間內運行，使其成為雙重高效的互動式證明。
該協議開始於證明者和驗證者就一個輸入扇入為2 的算術電路達成協議。然後，證明者發送給定輸入值的電路聲稱輸出。協定透過逐層檢查電路進行，從輸出層開始，向輸入層移動。每一步將當前層的聲明減少為對前一層的聲明，直到驗證者到達輸入層，在那裡他們可以檢查它是否與原始輸入相符。
在每一步中，主要使用的原語是求和檢查協議 [^10]，這是一種互動式證明，使證明者能夠說服驗證者關於一個具有oracle 存取權限的v-變數多項式g 的值之和，定義在布林超立方體上：
由於其高效性和簡單性，求和檢查協議和GKR 協議在實踐中被廣泛使用。有關進一步的解釋，可以在Thaler 的註釋中找到這些協議的替代概述 [^11]。
6 – 第一個實用的SNARK
Gennaro, Gentry, Parno, Raykova – Quadratic Span Programs and Succinct NIZKs without PCPs (2013) [^12]
我們現在跳到一篇介紹第一個實用SNARK 構造的論文！這項工作標誌著旨在創建不依賴低效PCP 定理的SNARK 研究的巔峰。雖然PCP 定理提供了一個理論上的SNARK 構造，但對於實際應用來說速度太慢，因此研究人員試圖尋找更有效率的替代方案。例如，Groth 在2010 年提出了一個基於雙線性群和配對的非互動式論證系統 [^13] ，儘管它需要證明者的二次時間。然而，這篇論文實現了線性證明者時間，代表了實際應用的重大改進。
這項工作為其他重要協議鋪平了道路，例如Pinocchio 協議[^14] ，以及最終著名的Groth16[^15] 證明系統。該論文還介紹了二次跨度程序和二次算術程序，這些構造在這些系統中仍然至關重要。
這些構造的一個顯著缺點是需要可信設置，這意味著公共參考字串生成階段產生的秘密資訊（通常稱為有毒廢物）如果不正確銷毀，可能會被用來創建虛假證明。此外，這種設定不是通用的，這意味著每個電路都需要新的設定。儘管有這些限制，生成的證明大小在不同構造中仍然是最小的，使其成為各種應用的熱門選擇。
另外值得一提的是，Zerocash [^16] 的第一次迭代是一個早期且有影響力的區塊鏈應用，利用了zk-SNARKs，建立在這些系統之上。
7 – PlonK SNARK
Gabizon, Williamson, Ciobotaru – PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge (2019) [^17]
這篇2019 年的影響力論文介紹了PlonK SNARK，這是一個基於多項式互動式oracle 證明（IOPs）的系統，這意味著驗證者可以對一些多項式進行oracle 訪問，並可以在選擇的點上對其進行評估。該系統使用各種多項式小工具來證明關於多項式的陳述，其中最顯著的是大乘積論證，允許證明者表明在一個域上的評估的乘積為1。利用這一點，我們可以建構一個置換論證來證明兩個序列是彼此的置換。使用這些小工具，證明者可以為任何算術電路構造證明，驗證者可以以非交互的方式驗證它。
在實踐中，oracle 存取是透過多項式承諾方案（PCS）實現的，這允許證明者：
- 承諾一個多項式，並
- 提供在特定點評估該多項式的開放值。
這使得驗證者可以在任何點查詢多項式並驗證IOP 的關係。論文中建議的PCS 是KZG 承諾方案 [^18] ，它既高效又實用。 KZG 使證明者對多項式的承諾作為單一群體元素，驗證者可以透過計算幾個橢圓曲線配對來確認開放值。雖然KZG 需要可信設置，但它是通用的，可以在設置後用於任何電路。然而，PlonK 可以與其他PCS 方案結合，使其適應透明論證系統。
此外，PlonK 中的置換論證啟發了尋找論證。尋找論證使證明者能夠表明一個序列的所有元素都包含在另一個序列中，這對於zkVM 架構非常有用。查找論證允許將見證分解為更小的軌跡，並證明它們之間的查找關係，從而使複雜證明更有效率。
8 – STARKs
Ben-Sasson, Bentov, Horesh, Riabzev – Scalable, transparent, and post-quantum secure computational integrity (2018) [^19]
這篇論文介紹了STARK 證明系統，另一個流行的證明系統，基於FRI [^20] ，這是一個用於Reed-Solomon 碼的接近性測試的IOP 協定。在STARKs 中，證明者透過在一個領域上建立默克爾樹來承諾多項式的評估。由於承諾的值最初是未知的，驗證者使用FRI 確認這些評估形成一個足夠低度的有效多項式。該協議還可以作為多項式承諾方案，允許驗證者檢查承諾多項式在任何點的評估。
STARKs 最引人注目的特點之一是它們僅依賴密碼學抗碰撞雜湊函數，而不是其他密碼學假設，例如離散對數問題。這使得STARKs 在潛在的後量子安全性方面具有優勢，因為抗碰撞雜湊函數被廣泛認為即使在量子攻擊下也安全。此外，STARKs 是透明的，即它們不需要任何可信設定。它們也是通用的，這意味著它們不局限於特定電路，在各種應用中提供靈活性。
9 – 遞迴
Valiant – Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. (2008) [^21]
多年來出現的一個重要概念是遞歸，簡單來說，這意味著一個證明可以用來證明另一個證明的正確性。本文所提出的場景涉及一個證明者希望證明一個可能很長的計算結果的正確性。給定一個圖靈機，我們可以證明狀態轉移函數的單一步驟的正確性，但這還不夠；我們想證明整個計算的正確性，這由一系列狀態轉移組成。
增量可驗證計算（IVC）背後的想法如下：假設我們可以證明從S1 到S2 的單一狀態轉移是正確的。然後，我們可以將兩個證明合併為一個：證明者表明他們知道兩個有效證明：
合併的證明將說服驗證者從S1 到S3 的轉移是正確的。這個過程可以對任意數量的步驟重複，使我們能夠將任意長的計算壓縮為一個證明（更具體地說，是多項式長的計算）。
重要的是要注意，這個構造依賴於兩個關鍵假設：
- 證明系統的知識健全性：證明者不僅必須證明單一狀態轉換的證明存在，還必須證明他們知道這些證明。直觀上講，透過歸納的知識可提取性，我們可以提取所有單一狀態轉換的證明。
- 實際中的雜湊函數是隨機預言機：這是一個更強的假設，但對於驗證聚合證明中子證明的正確性是必要的。
儘管這個構造在理論上是強大的，但在實務上應用成本高。為了解決這個問題，提出了新的方法來提高效率。其中之一是使用折疊方案 [^22] ，它放寬了假設並避免了遞歸SNARK 驗證的需要。折疊的想法是，給定兩個證明，π 和π′，我們可以將它們「折疊」成單一的證明，π″。驗證者相信，如果折疊實例是可滿足的，則原始實例也是可滿足的。
10 – 透過zkVM 進行可驗證計算
Ben-Sasson, Chiesa, Tromer, Virza – 適用於馮諾依曼架構的簡潔非互動零知識(2014) [^23]
這篇最終的論文討論了第一個實用的零知識虛擬機(zkVM) 構造，這是一種能夠執行任意程式並產生這些計算正確性證明的虛擬機。所描述的機器遵循馮諾依曼架構，這意味著程式和資料儲存在同一記憶體中。大多數現代CPU 是基於此範式，因此，從理論上講，任何可以在經典電腦上運行的程式也可以在該架構上運行。
論文介紹了一種稱為vnTinyRAM 的RISC 架構，並展示了一個移植到該指令集的C 編譯器。證明系統旨在驗證程式執行的正確性，直到固定的步驟數為止。其基本思想是電路被建構為一個重複的狀態轉換函數，展開直到達到指令計數限制。
如今，zkVM 越來越受歡迎。它們的一個關鍵優勢是使用者可以使用高級程式語言編寫程式並用它們產生證明。這相較於手動編寫電路提供了顯著的優勢，因為許多標準演算法和資料結構已經在這些高階語言中定義。此外，開發者可以重複使用熟悉的計算模型，這大大降低了使用零知識證明的學習曲線。
還值得注意的是，許多zk-rollup 是基於這個模型。例如，支援以太坊虛擬機器(EVM) 執行的zk-rollup 使用zkVM 來證明EVM 執行的正確性。
最後，論文介紹了其自身的架構，優化用於零知識證明系統。另一個流行的zk 友善架構範例是Cairo CPU 架構 [^24] ，這是一個經過最佳化以使用STARKs 進行證明的圖靈完備CPU。
參考論文
[^1]: Goldwasser, S., Micali, S., & Rackoff, C. (1985). The knowledge complexity of interactive proof-systems. (link) ↩︎
[^2]: Fiat, A., & Shamir, A. (1986). How to prove yourself: Practical solutions to identification and signature problems. (link) ↩︎
[^3]: Goldreich, O., Micali, S., & Wigderson, A. (1987). How to prove all NP statements in zero-knowledge and a methodology of cryptographic protocol design. (link) ↩︎
[^4]: Ben-Or, M., Goldreich, O., Goldwasser, S., Håstad, J., Kilian, J., Micali, S., & Rogaway, P. (1990). Everything provable is provable in zero-knowledge . (link) ↩︎
[^5]: Shamir, A. (1992). IP=PSPACE. (link) ↩︎
[^6]: Micali, S. (2000). Computationally sound proofs. (https://www.jinse.cn/blockchain/3702530.html(https://people.csail.mit.edu/silvio/Selected Scientific Papers/Proof Systems/Computationally_Sound_Proofs.pdf)) ↩︎
[^7]: Cook, SA (1971). Proof Verification and Hardness of Approximation Problems. (link) ↩︎
[^8]: Kilian, J. (1992, July). A note on efficient zero-knowledge proofs and arguments. (link) ↩︎
[^9]: Goldwasser, S., Kalai, YT, & Rothblum, GN (2015). Delegating computation: interactive proofs for muggles. (link, see also this note by Justin Thaler) ↩︎
[^10]: Lund, C., Fortnow, L., Karloff, H., & Nisan, N. (1992). Algebraic methods for interactive proof systems. (link) ↩︎
[^11]: Thaler, J. (2015). A note on the GKR protocol. (link) ↩︎
[^12]: Gennaro, R., Gentry, C., Parno, B., & Raykova, M. (2013). Quadratic span programs and succinct NIZKs without PCPs. (link) ↩︎
[^13]: Groth, J. (2010). Short pairing-based non-interactive zero-knowledge arguments. (link) ↩︎
[^14]: Parno, B., Howell, J., Gentry, C., & Raykova, M. (2016). Pinocchio: Nearly practical verifiable computation. (link) ↩︎
[^15]: Groth, J. (2016). On the size of pairing-based non-interactive arguments. (link) ↩︎
[^16]: Sasson, EB, Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., & Virza, M. (2014). Zerocash: Decentralized anonymous payments from bitcoin. (link) ↩︎
[^17]: Gabizon, A., Williamson, ZJ, & Ciobotaru, O. (2019). Plonk: Permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. (link) ↩︎
[^18]: Kate, A., Zaverucha, GM, & Goldberg, I. (2010). Constant-size commitments to polynomials and their applications. (link) ↩︎
[^19]: Ben-Sasson, E., Bentov, I., Horesh, Y., & Riabzev, M. (2018). Scalable, transparent, and post-quantum secure computational integrity. (link) ↩︎
[^20]: Ben-Sasson, E., Bentov, I., Horesh, Y., & Riabzev, M. (2018). Fast reed-solomon interactive oracle proofs of proximity. (link) ↩︎
[^21]: Valiant, P. (2008). Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. (link) ↩︎
[^22]: Kothapalli, A., Setty, S., & Tzialla, I. (2022, August). Nova: Recursive zero-knowledge arguments from folding schemes. (link) ↩︎
[^23]: Ben-Sasson, E., Chiesa, A., Tromer, E., & Virza, M. (2014). Succinct Non-Interactive zero knowledge for a von neumann architecture. (link) ↩︎
[^24]: Goldberg, L., Papini, S., & Riabzev, M. (2021). Cairo–a Turing-complete STARK-friendly CPU architecture. (link) ↩︎
