10 篇塑造現(xiàn)代零知識證明的必讀論文
來源：登鏈社區(qū)
零知識證明在近40年中取得了顯著的發(fā)展，達(dá)到了前所未有的復(fù)雜性和效率水平。如今，每天都有新的論文和項目涌現(xiàn)，建立在豐富的思想和創(chuàng)新基礎(chǔ)之上。
想知道這一切是如何開始的嗎？在這篇文章中，我們將深入探討零知識證明的歷史，探索10篇幫助塑造這一領(lǐng)域的里程碑論文。1-起源
Goldwasser,Micali,Rackoff-交互式證明系統(tǒng)的知識復(fù)雜性(1985)[^1]
我們的第一個里程碑帶我們回到1985年那篇開創(chuàng)性的論文！這項工作引入了許多術(shù)語和基礎(chǔ)概念，這些概念至今仍然是零知識證明的核心。
首先，論文定義了一個證明系統(tǒng)，其模型為一個涉及兩個概率圖靈機(jī)的雙方協(xié)議：一個證明者和一個驗證者。證明系統(tǒng)的目標(biāo)是使證明者能夠說服驗證者某個給定輸入x屬于正式語言L。在大多數(shù)早期工作中，證明者是計算上不受限制的，而驗證者則限制在多項式時間計算。在交互結(jié)束時，驗證者輸出“接受”或“拒絕”。
6-第一個實用的SNARK
Gennaro,Gentry,Parno,Raykova-QuadraticSpanProgramsandSuccinctNIZKswithoutPCPs(2013)[^12]
我們現(xiàn)在跳到一篇介紹第一個實用SNARK構(gòu)造的論文！這項工作標(biāo)志著旨在創(chuàng)建不依賴于低效PCP定理的SNARK研究的巔峰。雖然PCP定理提供了一個理論上的SNARK構(gòu)造，但對于實際應(yīng)用來說速度太慢，因此研究人員試圖尋找更高效的替代方案。例如，Groth在2010年提出了一種基于雙線性群和配對的非交互式論證系統(tǒng)[^13]，盡管它需要證明者的二次時間。然而，這篇論文實現(xiàn)了線性證明者時間，代表了實際應(yīng)用的重大改進(jìn)。
這項工作為其他重要協(xié)議鋪平了道路，例如Pinocchio協(xié)議[^14]，以及最終著名的Groth16[^15] 證明系統(tǒng)。該論文還介紹了二次跨度程序和二次算術(shù)程序，這些構(gòu)造在這些系統(tǒng)中仍然至關(guān)重要。
這些構(gòu)造的一個顯著缺點(diǎn)是需要可信設(shè)置，這意味著公共參考字符串生成階段產(chǎn)生的秘密信息（通常稱為有毒廢物）如果不正確銷毀，可能會被用來創(chuàng)建虛假證明。此外，這種設(shè)置不是通用的，這意味著每個電路都需要新的設(shè)置。盡管存在這些限制，生成的證明大小在不同構(gòu)造中仍然是最小的，使其成為各種應(yīng)用的熱門選擇。
還值得一提的是，Zerocash[^16]的第一次迭代是一個早期且有影響力的Blockchain應(yīng)用，利用了zk-SNARKs，建立在這些系統(tǒng)之上。7-PlonKSNARK
Gabizon,Williamson,Ciobotaru-PlonK:PermutationsoverLagrange-basesforOecumenicalNoninteractiveargumentsofKnowledge(2019)[^17]
這篇2019年的影響力論文介紹了PlonKSNARK，這是一個基于多項式交互式oracle證明（IOPs）的系統(tǒng)，這意味著驗證者可以對一些多項式進(jìn)行oracle訪問，并可以在選擇的點(diǎn)上對其進(jìn)行評估。該系統(tǒng)使用各種多項式小工具來證明關(guān)于多項式的陳述，其中最顯著的是大乘積論證，允許證明者表明在一個域上的評估的乘積為1。利用這一點(diǎn)，我們可以構(gòu)造一個置換論證來證明兩個序列是彼此的置換。使用這些小工具，證明者可以為任何算術(shù)電路構(gòu)造證明，驗證者可以以非交互的方式驗證它。
在實踐中，oracle訪問是通過多項式承諾方案（PCS）實現(xiàn)的，這允許證明者：承諾一個多項式，并提供在特定點(diǎn)評估該多項式的開放值。
這使得驗證者可以在任何點(diǎn)查詢多項式并驗證IOP的關(guān)系。論文中建議的PCS是KZG承諾方案[^18]，它既高效又實用。KZG使證明者對多項式的承諾作為單個群元素，驗證者可以通過計算幾個橢圓曲線配對來確認(rèn)開放值。雖然KZG需要可信設(shè)置，但它是通用的，可以在設(shè)置后用于任何電路。然而，PlonK可以與其他PCS方案結(jié)合，使其適應(yīng)透明論證系統(tǒng)。
此外，PlonK中的置換論證啟發(fā)了查找論證。查找論證使證明者能夠表明一個序列的所有元素都包含在另一個序列中，這對于zkVM架構(gòu)非常有用。查找論證允許將見證分解為更小的軌跡，并證明它們之間的查找關(guān)系，從而使復(fù)雜證明更高效。8-STARKs
Ben-Sasson,Bentov,Horesh,Riabzev-Scalable,transparent,andpost-quantumsecurecomputationalintegrity(2018)[^19]
這篇論文介紹了STARK證明系統(tǒng)，另一種流行的證明系統(tǒng)，基于FRI[^20]，這是一個用于Reed-Solomon碼的接近性測試的IOP協(xié)議。在STARKs中，證明者通過在一個域上構(gòu)建默克爾樹來承諾多項式的評估。由于承諾的值最初是未知的，驗證者使用FRI確認(rèn)這些評估形成一個足夠低度的有效多項式。該協(xié)議還可以作為多項式承諾方案，允許驗證者檢查承諾多項式在任何點(diǎn)的評估。
STARKs最引人注目的特點(diǎn)之一是它們僅依賴于密碼學(xué)抗碰撞哈希函數(shù)，而不是其他密碼學(xué)假設(shè)，如離散對數(shù)問題。這使得STARKs在潛在的后量子安全性方面具有優(yōu)勢，因為抗碰撞哈希函數(shù)被廣泛認(rèn)為即使在量子攻擊下也安全。此外，STARKs是透明的，即它們不需要任何可信設(shè)置。它們也是通用的，這意味著它們不局限于特定電路，在各種應(yīng)用中提供靈活性。9-遞歸
Valiant-Incrementallyverifiablecomputationorproofsofknowledgeimplytime/spaceefficiency.(2008)[^21]
多年來出現(xiàn)的一個重要概念是遞歸，簡單來說，這意味著一個證明可以用來證明另一個證明的正確性。本文中提出的場景涉及一個證明者希望證明一個可能很長的計算結(jié)果的正確性。給定一個圖靈機(jī)，我們可以證明狀態(tài)轉(zhuǎn)移函數(shù)的單個步驟的正確性，但這還不夠；我們想證明整個計算的正確性，這由一系列狀態(tài)轉(zhuǎn)移組成。
增量可驗證計算（IVC）背后的想法如下：假設(shè)我們可以證明從S1到S2的單個狀態(tài)轉(zhuǎn)移是正確的。然后，我們可以將兩個證明合并為一個：證明者表明他們知道兩個有效證明：
合并的證明將說服驗證者從S1到S3的轉(zhuǎn)移是正確的。這個過程可以對任意數(shù)量的步驟重復(fù)，使我們能夠?qū)⑷我忾L的計算壓縮為一個證明（更具體地說，是多項式長的計算）。
重要的是要注意，這個構(gòu)造依賴于兩個關(guān)鍵假設(shè)：證明系統(tǒng)的知識健全性：證明者不僅必須證明單個狀態(tài)轉(zhuǎn)換的證明存在，還必須證明他們知道這些證明。直觀上講，通過歸納的知識可提取性，我們可以提取所有單個狀態(tài)轉(zhuǎn)換的證明。實際中的哈希函數(shù)是隨機(jī)預(yù)言機(jī)：這是一個更強(qiáng)的假設(shè)，但對于驗證聚合證明中子證明的正確性是必要的。
盡管這個構(gòu)造在理論上是強(qiáng)大的，但在實踐中應(yīng)用成本高。為了解決這個問題，提出了新的方法來提高效率。其中之一是使用折疊方案[^22]，它放寬了假設(shè)并避免了遞歸SNARK驗證的需要。折疊的想法是，給定兩個證明，π和π′，我們可以將它們“折疊”成一個單一的證明，π″。驗證者相信，如果折疊實例是可滿足的，則原始實例也是可滿足的。10-通過zkVM進(jìn)行可驗證計算
Ben-Sasson,Chiesa,Tromer,Virza-適用于馮·諾依曼架構(gòu)的簡潔非交互式零知識(2014)[^23]
這篇最終的論文討論了第一個實用的零知識虛擬機(jī)(zkVM)構(gòu)造，這是一種能夠執(zhí)行任意程序并生成這些計算正確性證明的虛擬機(jī)。所描述的機(jī)器遵循馮·諾依曼架構(gòu)，這意味著程序和數(shù)據(jù)存儲在同一內(nèi)存中。大多數(shù)現(xiàn)代CPU基于這一范式，因此，從理論上講，任何可以在經(jīng)典計算機(jī)上運(yùn)行的程序也可以在該架構(gòu)上運(yùn)行。
論文介紹了一種稱為vnTinyRAM的RISC架構(gòu)，并展示了一個移植到該指令集的C編譯器。證明系統(tǒng)旨在驗證程序執(zhí)行的正確性，直到固定的步驟數(shù)為止。其基本思想是電路被構(gòu)造為一個重復(fù)的狀態(tài)轉(zhuǎn)換函數(shù)，展開直到達(dá)到指令計數(shù)限制。
如今，zkVM越來越受歡迎。它們的一個關(guān)鍵優(yōu)勢是用戶可以使用高級編程語言編寫程序并用它們生成證明。這相較于手動編寫電路提供了顯著的優(yōu)勢，因為許多標(biāo)準(zhǔn)算法和數(shù)據(jù)結(jié)構(gòu)已經(jīng)在這些高級語言中定義。此外，開發(fā)者可以重用熟悉的計算模型，這大大降低了使用零知識證明的學(xué)習(xí)曲線。
還值得注意的是，許多zk-rollup基于這一模型。例如，支持Ethereum虛擬機(jī)(EVM)執(zhí)行的zk-rollup使用zkVM來證明EVM執(zhí)行的正確性。
最后，論文介紹了其自身的架構(gòu)，優(yōu)化用于零知識證明系統(tǒng)。另一個流行的zk友好架構(gòu)示例是CairoCPU架構(gòu)[^24]，這是一個經(jīng)過優(yōu)化以使用STARKs進(jìn)行證明的圖靈完備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)