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