来源：登链社区

零知识证明在近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)