來源：登鏈社區

零知識證明在近40年中取得了顯著的發展，達到了前所未有的復雜性和效率水平。如今，每天都有新的論文和項目涌現，建立在豐富的思想和創新基礎之上。

想知道這一切是如何開始的嗎？在這篇文章中，我們將深入探討零知識證明的歷史，探索10篇幫助塑造這一領域的里程碑論文。1-起源

Goldwasser,Micali,Rackoff-交互式證明系統的知識復雜性(1985)[^1]

我們的第一個里程碑帶我們回到1985年那篇開創性的論文！這項工作引入了許多術語和基礎概念，這些概念至今仍然是零知識證明的核心。

首先，論文定義了一個證明系統，其模型為一個涉及兩個概率圖靈機的雙方協議：一個證明者和一個驗證者。證明系統的目標是使證明者能夠說服驗證者某個給定輸入x屬于正式語言L。在大多數早期工作中，證明者是計算上不受限制的，而驗證者則限制在多項式時間計算。在交互結束時，驗證者輸出“接受”或“拒絕”。

6-第一個實用的SNARK

Gennaro,Gentry,Parno,Raykova-QuadraticSpanProgramsandSuccinctNIZKswithoutPCPs(2013)[^12]

我們現在跳到一篇介紹第一個實用SNARK構造的論文！這項工作標志著旨在創建不依賴于低效PCP定理的SNARK研究的巔峰。雖然PCP定理提供了一個理論上的SNARK構造，但對于實際應用來說速度太慢，因此研究人員試圖尋找更高效的替代方案。例如，Groth在2010年提出了一種基于雙線性群和配對的非交互式論證系統[^13]，盡管它需要證明者的二次時間。然而，這篇論文實現了線性證明者時間，代表了實際應用的重大改進。

這項工作為其他重要協議鋪平了道路，例如Pinocchio協議[^14]，以及最終著名的Groth16[^15] 證明系統。該論文還介紹了二次跨度程序和二次算術程序，這些構造在這些系統中仍然至關重要。

這些構造的一個顯著缺點是需要可信設置，這意味著公共參考字符串生成階段產生的秘密信息（通常稱為有毒廢物）如果不正確銷毀，可能會被用來創建虛假證明。此外，這種設置不是通用的，這意味著每個電路都需要新的設置。盡管存在這些限制，生成的證明大小在不同構造中仍然是最小的，使其成為各種應用的熱門選擇。

還值得一提的是，Zerocash[^16]的第一次迭代是一個早期且有影響力的Blockchain應用，利用了zk-SNARKs，建立在這些系統之上。7-PlonKSNARK

Gabizon,Williamson,Ciobotaru-PlonK:PermutationsoverLagrange-basesforOecumenicalNoninteractiveargumentsofKnowledge(2019)[^17]

這篇2019年的影響力論文介紹了PlonKSNARK，這是一個基于多項式交互式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,andpost-quantumsecurecomputationalintegrity(2018)[^19]

這篇論文介紹了STARK證明系統，另一種流行的證明系統，基于FRI[^20]，這是一個用于Reed-Solomon碼的接近性測試的IOP協議。在STARKs中，證明者通過在一個域上構建默克爾樹來承諾多項式的評估。由于承諾的值最初是未知的，驗證者使用FRI確認這些評估形成一個足夠低度的有效多項式。該協議還可以作為多項式承諾方案，允許驗證者檢查承諾多項式在任何點的評估。

STARKs最引人注目的特點之一是它們僅依賴于密碼學抗碰撞哈希函數，而不是其他密碼學假設，如離散對數問題。這使得STARKs在潛在的后量子安全性方面具有優勢，因為抗碰撞哈希函數被廣泛認為即使在量子攻擊下也安全。此外，STARKs是透明的，即它們不需要任何可信設置。它們也是通用的，這意味著它們不局限于特定電路，在各種應用中提供靈活性。9-遞歸

Valiant-Incrementallyverifiablecomputationorproofsofknowledgeimplytime/spaceefficiency.(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基于這一模型。例如，支持Ethereum虛擬機(EVM)執行的zk-rollup使用zkVM來證明EVM執行的正確性。

最后，論文介紹了其自身的架構，優化用于零知識證明系統。另一個流行的zk友好架構示例是CairoCPU架構[^24]，這是一個經過優化以使用STARKs進行證明的圖靈完備CPU。參考論文

[^1]:Goldwasser,S.,Micali,S.,&Rackoff,C.(1985).Theknowledgecomplexityofinteractiveproof-systems.(link)

[^2]:Fiat,A.,&Shamir,A.(1986).Howtoproveyourself:Practicalsolutionstoidentificationandsignatureproblems.(link)

[^3]:Goldreich,O.,Micali,S.,&Wigderson,A.(1987).HowtoproveallNPstatementsinzero-knowledgeandamethodologyofcryptographicprotocoldesign.(link)

[^4]: Ben-Or,M.,Goldreich,O.,Goldwasser,S.,Hstad,J.,Kilian,J.,Micali,S.,&Rogaway,P.(1990).Everythingprovableisprovableinzero-knowledge.(link)

[^5]: Shamir,A.(1992).IP=PSPACE.(link)

[^6]:Micali,S.(2000).Computationallysoundproofs.([link](https://people.csail.mit.edu/silvio/SelectedScientificPapers/ProofSystems/Computationally_Sound_Proofs.pdf))

[^7]: Cook,S.A.(1971).ProofVerificationandHardnessofApproximationProblems.(link)

[^8]: Kilian,J.(1992,July).Anoteonefficientzero-knowledgeproofsandarguments.(link)

[^9]:Goldwasser,S.,Kalai,Y.T.,&Rothblum,G.N.(2015).Delegatingcomputation:interactiveproofsformuggles.(link,seealsothisnotebyJustinThaler)

[^10]:Lund,C.,Fortnow,L.,Karloff,H.,&Nisan,N.(1992).Algebraicmethodsforinteractiveproofsystems.(link)

[^11]: Thaler,J.(2015).AnoteontheGKRprotocol.(link)

[^12]:Gennaro,R.,Gentry,C.,Parno,B.,&Raykova,M.(2013).QuadraticspanprogramsandsuccinctNIZKswithoutPCPs.(link)

[^13]:Groth,J.(2010).Shortpairing-basednon-interactivezero-knowledgearguments.(link)

[^14]:Parno,B.,Howell,J.,Gentry,C.,&Raykova,M.(2016).Pinocchio:Nearlypracticalverifiablecomputation.(link)

[^15]: Groth,J.(2016).Onthesizeofpairing-basednon-interactivearguments.(link)

[^16]: Sasson,E.B.,Chiesa,A.,Garman,C.,Green,M.,Miers,I.,Tromer,E.,&Virza,M.(2014).Zerocash:Decentralizedanonymouspaymentsfrombitcoin.(link)

[^17]: Gabizon,A.,Williamson,Z.J.,&Ciobotaru,O.(2019).Plonk:Permutationsoverlagrange-basesforoecumenicalnoninteractiveargumentsofknowledge.(link)

[^18]:Kate,A.,Zaverucha,G.M.,&Goldberg,I.(2010).Constant-sizecommitmentstopolynomialsandtheirapplications.(link)

[^19]: Ben-Sasson,E.,Bentov,I.,Horesh,Y.,&Riabzev,M.(2018).Scalable,transparent,andpost-quantumsecurecomputationalintegrity.(link)

[^20]: Ben-Sasson,E.,Bentov,I.,Horesh,Y.,&Riabzev,M.(2018).Fastreed-solomoninteractiveoracleproofsofproximity.(link)

[^21]:Valiant,P.(2008).Incrementallyverifiablecomputationorproofsofknowledgeimplytime/spaceefficiency.(link)

[^22]:Kothapalli,A.,Setty,S.,&Tzialla,I.(2022,August).Nova:Recursivezero-knowledgeargumentsfromfoldingschemes.(link)

[^23]:Ben-Sasson,E.,Chiesa,A.,Tromer,E.,&Virza,M.(2014).SuccinctNon-Interactivezeroknowledgeforavonneumannarchitecture.(link)

[^24]:Goldberg,L.,Papini,S.,&Riabzev,M.(2021).Cairo–aTuring-completeSTARK-friendlyCPUarchitecture.(link)