零知识文献，第一部分和第二部分

编辑者注： a16z crypto 有着一系列长期的“经典文献”，从我们去年的 DAO 经典文献 到之前的 NFT 经典文献（在此之前还有我们原始的 加密经典文献）。因此，以下是我们为那些希望理解、更深入并与所有 零知识 相关事物进行构建的人整理的一系列资源：强大、基础的技术，它们掌握着区块链可扩展性的钥匙，并代表了保留隐私的应用的未来——包括在加密/ web3 中的应用——以及无数其他即将到来的创新。

而这些创新的来临已经时日已久：零知识证明系统由 Shafi Goldwasser、Silvio Micali 和 Charles Rackoff 于 1985 年首次提出，对密码学领域产生了变革性的影响；它们于 2012 年获颁 ACM 图灵奖，奖励 Goldwasser 和 Micali。由于这个工作的进行已经有几十年之久，尤其是在理论向实践转变的过程中——因此我们第一次在我们的经典系列中分享了第二部分：由 Justin Thaler 编写的注释阅读清单，按主题和时间顺序组织——在以下第一部分之后…

请务必订阅我们的 web3 每周通讯，获取更多更新及其他策划资源。如果你有建议可以添加的其他高质量文章，请告知我们 @ a16zcrypto 和/或 @smc90。

[致谢：感谢 Michael Blau、Sam Ragsdale 和 Tim Roughgarden。（以及感谢 Pratyush Mishra、Ittai Abraham 和其他人通过 Twitter 的进一步建议，我们已在下方加入！）]

基础、背景与演变

其中一些论文也更多地涉及密码学的一般内容（并不都是零知识证明），包括概述零知识证明今天所解决的问题或关键进展：如何在开放网络中确保隐私和身份验证。

密码学的新方向（1976）——Whitfield Diffie 和 Martin Hellman

https://ee.stanford.edu/~hellman/publications/24.pdf

获取数字签名和公钥加密系统的方法——Ronald Rivest、Adi Shamir、Leonard Adelman

https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=856E21BC2F75800D37FD611032C30B9C?doi=10.1.1.40.5588&rep=rep1&type=pdf

公钥加密系统的协议（1980）——Ralph Merkle

http://www.merkle.com/papers/Protocols.pdf

不安全信道上的安全通信（1978）——Ralph Merkle

https://www.merkle.com/1974/PuzzlesAsPublished.pdf

在密码学中使用椭圆曲线（1988）——Victor Miller

https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf

交互式证明系统的知识复杂性（1985）——Shafi Goldwasser、Silvio Micali、Charles Rackoff

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf

计算上可靠的证明（2000）——Silvio Micali

https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

从可提取的冲突抵抗到简洁的非交互式知识论证 [SNARKs] 及回归（2011）——Nir Bitansky、Ran Canetti、Alessandro Chiesa、Eran Tromer

https://eprint.iacr.org/2011/443.pdf

用于洗牌正确性的高效零知识论证（2012）——Stephanie Bayer 和 Jens Groth

http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

用于冯·诺依曼架构的简洁非交互式零知识证明（2013）——Eli Ben-Sasson、Alessandro Chiesa、Eran Tromer 和 Madars Virza

https://eprint.iacr.org/2013/879.pdf

无需重新执行的计算验证（2015）——Michael Walfish 和 Andrew Blumberg

https://cacm.acm.org/magazines/2015/2/182636-verifying-computations-without-reexecuting-them/

可扩展的、透明的、后量子安全的计算完整性（2018）——Eli Ben-Sasson、Iddo Bentov、Yinon Horesh 和 Michael Riabzev

https://eprint.iacr.org/2018/046.pdf

具（几乎）最少时间和空间开销的公币零知识论证（2020）——Alexander Block、Justin Holmgren、Alon Rosen、Ron Rothblum 和 Pratik Soni

https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645

概述与介绍

证明、论证和零知识——可验证计算和交互式证明及论证的概述，是加密协议允许证明者向验证者提供保证其正确执行请求计算的，包括零知识（其中证明不透露除其有效性以外的任何信息）。Zk 论证在密码学中有许多应用，并在过去十年中从理论转向实践。

由 Justin Thaler 进行

https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

零知识证明模型的演变——对零知识证明的回顾，Meiklejohn（伦敦大学学院，谷歌）探讨推动其发展的应用、捕捉这些新交互式的不同模型、我们可以实现的构造和尚待完成的工作。

由 Sarah Meiklejohn 进行

https://www.youtube.com/watch?v=HO97kVMI3SE

零知识白板会议——介绍模块

与 Dan Boneh 等

https://zkhack.dev/whiteboard/

利用 zkps 进行加密的安全性和隐私——在实践中开拓零知识证明；zkps 是什么以及它们如何工作……包括现场演示

由 Zooko Wilcox 进行

https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

热门技术主题解释——包括零知识的一般定义和影响

由 Joe Bonneau、Tim Roughgarden、Scott Kominers、Ali Yahya、Chris Dixon 进行

https://web3-with-a16z.simplecast.com/episodes/hot-research-summer-blockchain-crypto-tech-topics-explainers-overviews-seminar-videos

零知识的解释——5 个难度级别的介绍

与 Amit Sahai、Wired

https://youtu.be/fOGdb1CTu5c

即将到来的隐私层将如何修复破损的网络——Howard Wu

https://future.com/a-privacy-layer-for-the-web-can-change-everything/

使用 zk 证明对抗虚假信息——Trish Datta 和 Dan Boneh

https://learnblockchain.cn/article/11461

zkSNARKs 介绍——与 Howard Wu、Anna Rose

https://zeroknowledge.fm/38-2/

zk-SNARK 工作的原因及方式：权威解释——Maksym Petkus

https://arxiv.org/pdf/1906.07221.pdf

零知识证明的介绍——Fredrik Harrysson 和 Anna Rose

https://www.zeroknowledge.fm/21 [ 其他地方的总结写作 在这里 ]

zk-SNARKs：幕后——Vitalik Buterin

https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6

第一部分，第二部分，第三部分

去中心化速度——关于零知识证明的进展，去中心化硬件

由 Elena Burger 进行

https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

前沿 zk 研究——与以太坊基金会的 zk 研究者一起进行

与 Mary Maller、Anna Rose、Kobi Gurkan

https://zeroknowledge.fm/232-2/

探索 zk 研究——与 DFINITY 的研究主任一起进行；也支持类似 Groth16 的进展

与 Jens Groth、Anna Rose、Kobi Gurkan

https://zeroknowledge.fm/237-2/

SNARK 的研究与教育——与 ZCash 和 Starkware 的共同创始人之一进行

与 Alessandro Chiesa、Anna Rose

https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

深入探讨：课程、解析和构建者指南

交互式证明——《计算复杂性：现代方法》第 8 章

由 Sanjeev Arora 和 Boaz Barak

https://theory.cs.princeton.edu/complexity/book.pdf

概率证明的基础——来自交互式证明和更多其他内容的 5 单元课程

由 Alessandro Chiesa

https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC

第 9 届 BIU 冬季密码学学校——来自应用密码学与网络安全研究中心

由 Yehuda Lindell、Benny Pinkas、Eli Ben-Sasson、Jens Groth、Carmit Hazay、Yuval Ishai、Alon Rosen、Ron Rothblum

https://cyber.biu.ac.il/event/the-9th-biu-winter-school-on-cryptography/

交互式证明与零知识——来自斯坦福 CSS 355 密码学专题（2018）

由 Henry Corrigan-Gibbs、Sam Kim、David Wu

https://crypto.stanford.edu/cs355/18sp/lec3.pdf

交互式的零知识证明协议演示，用于 3 彩色图——允许说服验证者事实的真实性（即图是三彩色可对应的）而不揭示实际的三种着色方法

http://web.mit.edu/~ezyang/Public/graph/svg.html [ 更多见 ]

一个简单而简洁的零知识证明——呈现一个简单的证明系统，可以为这个领域提供介绍和直觉

由 Ittai Abraham 和 Alin Tomescu

https://decentralizedthoughts.github.io/2020-12-08-a-simple-and-succinct-zero-knowledge-proof/

SNARK（PLONK）编译器、证明者和验证者的 Python 实现——旨在提供教育价值

由 Vitalik Buterin

https://github.com/ethereum/research/tree/master/py_plonk

SNARK 设计，第一部分——调研、在 rollups 中的用途、更多

由 Justin Thaler

https://www.youtube.com/watch?v=tg6lKPdR_e4

SNARK 设计，第二部分——rollups、性能、安全性

由 Justin Thaler

https://www.youtube.com/watch?v=cMAI7g3UcoI

STARKs——第一部分、第二部分、第三部分

由 Vitalik Buterin

https://vitalik.ca/general/2017/11/09/starks_part_1.html

https://vitalik.ca/general/2017/11/22/starks_part_2.html

https://vitalik.ca/general/2018/07/21/starks_part_3.html

STARK 的结构——对 STARK 证明系统机制的六部分教程

由 Alan Szepieniec

https://aszepieniec.github.io/stark-anatomy/

测量 SNARK 性能——前端、后端、更多

由 Justin Thaler

https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

理解 PLONK https://vitalik.ca/general/2019/09/22/plonk.html

PLONK 零知识证明系统——关于 PLONK 如何工作的 12 部短视频系列

由 David Wong

https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

从 AIRs 到 RAPs——PLONK 风格的算术化是如何工作的

由 Ariel Gabizon

https://hackmd.io/@aztec-network/plonk-arithmetiization-air

PLONK 和 Plookup 中的多重集检查由 Ariel Gabizon

https://hackmd.io/@arielg/ByFgSDA7D

Halo2 设计——来自 ECC

https://zcash.github.io/halo2/design.html

Plonky2 https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf

应用与教程：概念验证、演示、工具等

应用的 zk——学习资源，为没有正式数学背景的工程师提供扎实理解基础理论的材料

由 0xPARC

https://learn.0xparc.org/materials/intro

一个 zkSNARK 的在线开发环境——zkREPL，一套新的浏览器内工具集，用于与 Circom 工具栈进行交互

由 Kevin Kwok

https://zkrepl.dev（+ 解释线程 在这里）

从零到英雄的二次算术程序——由 Vitalik Buterin

https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

关于 zkEVMs——与 Alex Gluchowski 和 Anna Rose

https://zeroknowledge.fm/175-2/

不同类型的 zkEVMs——由 Vitalik Buterin

https://vitalik.ca/general/2022/08/04/zkevm.html

ZK 机器学习——在 SNARK 中放置神经网络的教程和演示

由 Horace Pan、Francis Ho 和 Henri Palacci

https://0xparc.org/blog/zk-mnist

关于 ZK 语言——与 Alex Ozdemir 和 Anna Rose

https://zeroknowledge.fm/172-2/

Arkworks——用于开发和编程 zkSNARKs 的 Rust 生态系统

https://github.com/arkworks-rs

黑暗森林——将 zk 加密技术应用于游戏——一个完全去中心化和持久的 RTS（实时策略）游戏

https://blog.zkga.me/announcing-darkforest

针对工程师的 ZKPs——查看黑暗森林的 ZKPs

https://blog.zkga.me/df-init-circuit

深入研究零知识——与 Elena Nadolinski、Anna Rose、James Prestwich 的访谈

https://zeroknowledge.fm/182-2/

zkDocs：零知识信息共享——由 Sam Ragsdale 和 Dan Boneh

https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

使用 ZK 证明对抗虚假信息——由 Trish Datta 和 Dan Boneh

https://learnblockchain.cn/article/11461

使用零知识证明进行隐私保护的加密空投——由 Sam Ragsdale

https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

ZK Hack——谜题，更多

https://zkhack.dev/events/mini.html#puzzles

链上可信设置仪式——由 Valeria Nikolaenko 和 Sam Ragsdale

https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

加密法规、非法金融、隐私及更多——包括关于监管/合规上下文中零知识的部分；“保护隐私”与模糊技术的区别

与 Michele Korver、Jai Ramaswamy、Sonal Chokshi

https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained

其他资源

zkMesh 通讯——月度通讯，分享去中心化隐私保护技术、隐私协议开发和零知识系统的最新动态

https://zkmesh.substack.com/

零知识播客——关于最新的 zk 研究与 zk 应用，以及建筑密码技术的隐私技术专家

与 Anna Rose

https://zeroknowledge.fm/

ZK 职位板

https://jobsboard.zeroknowledge.fm/

零知识经典文献，第二部分

……由 Justin Thaler 按主题和时间顺序附注的阅读清单：

SNARKs 从线性 PCPs（即具有电路特定设置的 SNARKs）

无需短 PCP 的高效论证 （2007 年）——由 Yuval Ishai、Eyal Kushilevitz 和 Rafail Ostrovsky

在 2007 年之前，SNARKs 主要通过 Kilian–Micali 模式设计，通过采用“短”的可概率检查证明（PCP）并通过 Merkle 哈希和 Fiat-Shamir 转换将其“加密编译”成简洁的论证。不幸的是，即使在今天，短 PCP 也复杂且不切实际。本文（IKO）展示了如何使用同态加密从“长但结构化”的 PCP 获得简洁（非透明的）交互论证。这些论证可以比短 PCP 更简单，而得到的 SNARKs 具有更短的证明和更快的验证。首次意识到这些论证具有实际高效潜力，并在 Pepper 中进行了改进和实施。不幸的是，IKO 的论证具备二次时间验证者和二次大小的结构化参考字符串，因此它们不适合大计算。

二次跨度程序和无 PCP 的简洁 NIZKs （2012 年）——由 Rosario Gennaro、Craig Gentry、Bryan Parno 和 Mariana Raykova

这篇突破性论文（GGPR）将 IKO 方法的验证者成本从电路大小的二次降低到准线性。在早期的 Groth 和 Lipmaa 工作的基础上，它还通过成对加密（而非 IKO 中的交互论证）提供 SNARKs。它在目前称为秩-1约束满足（R1CS）问题的背景下描述了其 SNARKs，这是算术电路可满足性的概括。

这篇论文也为第一个商业部署的 SNARKs（例如，ZCash 中）提供了理论基础，直接导致了目前仍受欢迎的 SNARKs（例如，Groth16）。GGPR 论证的初步实现出现在 Zaatar 和 [Pinocchio](https://eprint.iacr.org/2013/279） 中，后来的变种包括 SNARKs for C 和 BCTV 。BCIOP 提供了一个通用框架，阐明了这些线性-PCPs 到 SNARK 转换（参见 Zaatar 的附录 A）并描述了各种实例。

关于基于配对的非交互式论证大小的讨论 （2016 年）——由 Jens Groth

这篇论文通常称为 Groth16，展示了 GGPR 的 SNARKs 的改进，尽管今天仍能达到最先进的具体验证成本（证明是 3 个群体元素且验证主要由三个配对操作主导，假设公共输入较短）。安全性在通用群模型中得到证明。

具有通用可信设置的 SNARKs

PlonK：基于拉格朗日基础的非交互式知识论证的排列 （2019 年）——由 Ariel Gabizon、Zachary Williamson 和 Oana Ciobotaru

Marlin：使用通用和可更新 SRS 的预处理 zkSNARKs （2019 年）——由 Alessandro Chiesa、Yuncong Hu、Mary Maller、Pratyush Mishra、Psi Vesely 和 Nicholas Ward

PlonK 和 Marlin 替换了 Groth16 中的电路特定可信设置，使用通用设置。这是以证明大小增大 4 倍至 6 倍为代价的。可以将 PlonK 和 Marlin 理解为将 Groth16 及其前身中的电路特定工作移入在可信设置之后和 SNARK 证明生成期间发生的预处理阶段。

以这种方式处理任意电路和 R1CS 系统的能力有时被称为全息或计算承诺，也在 Spartan 中进行了描述（稍后在本编纂中讨论）。由于证明生成期间的工作更多，因此 PlonK 和 Marlin 的验证者比 Groth16 对给定电路或 R1CS 实例的处理要慢。然而，PlonK 和 Marlin 可以实现与更通用的中间表示合作，而 Groth16 则不能。

在 SNARKs 中的多项式承诺方案，这是一种关键的密码学原语

对多项式的常量大小承诺及其应用 （2010 年）——由 Aniket Kate、Gregory Zaverucha 和 Ian Goldberg

这篇论文引入了多项式承诺方案的概念。给出了单变量多项式的方案（通常称为 KZG 承诺），具有常量大小的承诺和评估证明。该方案使用可信设置（即结构化参考字符串）和成对加密。目前在实践中仍然非常流行，并在包括 PlonK 和 Marlin（以及 Groth16 使用极其相似的密码技术）在内的 SNARKs 中使用。

快速的 Reed-Solomon 交互式神谕证明的接近性 （2017 年）——由 Eli Ben-Sasson、Iddo Bentov、Ynon Horesh、Michael Riabzev

给出了 Reed-Solomon 测试的交互式神谕证明（IOP）——即，证明承诺的字符串接近单变量多项式的评估表。结合 Merkle 哈希和 Fiat-Shamir 转换，这产生了一种透明的多项式承诺方案，具有多对数大小的评估证明（详情见 VP19）。如今，在可信后量子多项式承诺方案中，它仍然是最短的。

Ligero: 无需可信设置的轻量级亚线性论证 （2017 年）——由 Scott Ames、Carmit Hazay、Yuval Ishai 和 Muthuramakrishnan Venkitasubramaniam

类似于 FRI，这项工作为 Reed-Solomon 测试提供了一种 IOP，但使用的是平方根证明长度，而不是多对数。对比 理论 工作 显示，通过将 Reed-Solomon 代码换为更快编码的不同纠错代码，可以获得线性时间的证明者，且可以在任何字段上原生工作。这种方法已在 Brakedown 和 Orion 中进行了改进和实施，提供了最先进的证明者性能。

Bulletproofs: 针对保密交易长期以来短小的证明及更多 （2017 年）——由 Benedikt Bunz、Jonathan Bootle、Dan Boneh、Andrew Poelstra、Pieter Wuille 和 Greg Maxwell

改进了 BCCGP 的先前工作，Bulletproofs 提供了一种透明的多项式承诺方案（事实上，是一种称为内部积论证的推广），基于计算离散对数的难度，具有对数大小的证明，却需要线性验证时间。该方案由于其透明性和简短的证明（例如，它在 ZCash Orchard 和 Monero 中使用）而在今天仍然受欢迎。

Dory: 有效的、透明的针对普适内积和多项式承诺的论证 （2020 年）——由 Jonathan Lee

Dory 将 Bulletproofs 中的验证时间从线性降低到对数，同时保持透明性和对数大小的证明（尽管与 Bulletproofs 相比略大），并保持透明性。使用配对并基于 SXDH 假设。

交互式证明、多证明者交互式证明及相关 SNARKs

委托计算：平民的交互式证明 （ 2008 年 )——由 Shafi Goldwasser、Yael Tauman Kalai 和 Guy Rothblum

在这篇论文之前，通用的交互式证明要求验证者为 超多项式时间。该论文给出了一个交互式证明协议，通常称为 GKR 协议，具有多项式时间的证明者和准线性时间的验证者，适用于任何拥有高效并行算法的问题（等价地，该交互式证明适用于任何具有小深度的算术电路）。

具有流媒体交互证明的实用验证计算 （2011 年）——由 Graham Cormode、Michael Mitzenmacher、Justin Thaler

这篇论文（有时称为 CMT）将 GKR 协议中的证明者时间从电路大小的四次降低到准线性。产生了一种通用交互式证明的初次实现。随后的工作（Allspice、Thaler13、Giraffe和Libra）将验证时间进一步降低，从准线性减至线性。

vSQL：在动态外包数据库上验证 SQL 查询 （2017 年）——由 Yupeng Zhang、Daniel Genkin、Jonathan Katz、Dimitrios Papadopoulos 和 Charalampos Papamanthou

尽管标题中提到的是特定应用领域（数据库），但这篇论文所作的贡献更加普遍。特别是，它观察到通过将交互式证明与多项式承诺方案结合，所获得的电路可满足性可以获得简洁论证（对于多项式的多线性）。

后来的 工作 使这些论证零知识并引入针对多线性多项式的不同承诺方案。

Spartan：高效且通用的无可信设置 zkSNARKs （2019 年）——由 Srinath Setty

通过将多证明者交互式证明（MIPs）与多项式承诺方案结合，获得电路可满足性和 R1CS 的 SNARKs，从而进一步改进之前称为 Clover 的具体高效 MIPs 工作。效果是获得比上述 GKR 协议所衍生的交互式证明更短的 SNARKs。类似于 PlonK 和 Marlin，Spartan 还展示了如何通过预处理和 SNARK 证明生成来处理任意电路和 R1CS 系统。Spartan 使用了一种来自 Hyrax 的多项式承诺方案。后续工作 Brakedown 和 Orion 将 Spartan 的 MIP 与其他多项式承诺方案结合，得出了首个实现的 SNARK，其具备线性时间的证明者。

短 PCP 和 IOP

具有多对数查询复杂性的短 PCP (2005)

作者：Eli Ben-Sasson 和 Madhu Sudan

这项理论工作的第一项概率检查证明（PCP）提供了一个证明长度在要被验证计算大小的准线性与聚合查询成本多对数的。然而，验证者的时间是线性的。在 Kilian-Micali 将 PCP 转换为 SNARK 的工作后，这是迈向具有准线性时间证明者和多对数时间验证者的 SNARK 的一步。

后来的理论工作 将验证者时间减少到多对数。后续 实用导向的工作进一步完善了这种方法，但短 PCP 在今天仍不实用。为了获得实用的 SNARK，后来的 工作 转向 称为 的交互式广义 PCP 叫做 交互式 oracle 证明 (IOP)。这些努力导致并构建了 FRI，这是一个流行的多项式承诺方案，在本汇编的多项式承诺部分中进行了讨论。

此类别的其他工作包括 ZKBoo 及其后续工作。这些方法没有实现简洁的证明，但具有良好的常数因子，因此在证明小语句方面具有吸引力。它们导致了一些后量子签名的家族，例如 Picnic，并且已经在 几篇 工作中 得到优化 在 多项 中。ZKBoo 被呈现为遵循一种称为 MPC-in-the-head 的独特设计范式，但它产生了一个 IOP。

递归 SNARK

可逐步验证的计算或知识证明暗示时间/空间效率 (2008)

作者：Paul Valiant

这项工作引入了可逐步验证计算 (IVC) 的基本概念，其中证明者运行一个计算并在所有时候保持一个证明，证明截至目前的计算是正确的。通过递归组合 SNARK 构建了 IVC。在这里，SNARK 的 知识健壮性 属性对于建立递归组合的非交互式论证的健壮性至关重要。该论文还为 PCP 派生的 SNARK 提供了一个极高效的知识提取器（按照 Kilian-Micali 范式）。

通过椭圆曲线循环实现可扩展的零知识 (2014) 作者：Eli Ben-Sasson、Alessandro Chiesa、Eran Tromer 和 Madars Virza

在 理论工作 的基础上，本文通过递归应用 GGPR 的 SNARK 的一个变体，提供了一个简单虚拟机 (TinyRAM) 的 IVC 的首个实现（来自 SNARKs for C 论文）。

还引入了椭圆曲线循环的概念，这对于递归组合使用椭圆曲线加密的 SNARK 非常有用。

在没有可信设置下的递归证明组合 (2019) 作者：Sean Bowe、Jack Grigg 和 Daira Hopwood

这项工作（称为 Halo）研究如何递归组合透明 SNARK。这比组合非透明 SNARK 更具挑战性，因为透明 SNARK 中的验证过程可能花费更多。

这引发了一系列的 工作 成果，最终在如 Nova 这样的系统中实现了最先进的 IVC 性能，甚至超过了通过组合非透明 SNARK（如 Groth16）获得的性能。

应用

Zerocash: 从 Bitcoin 的去中心化匿名支付 (2014)

作者：Eli Ben Sasson、Alessandro Chiesa、Christina Garman、Matthew Green、Ian Miers、Eran Tromer、Madars Virza

在包括 Zerocoin（与 [Pinnochio Coin](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/pinocoin.pdf）为同时进行的工作）的先前工作基础上，本文使用 GGPR 派生的 SNARK 来设计一种私有加密货币，导致 ZCash 的出现。

Geppetto: 多功能可验证计算 (2014) 作者：Craig Costello、Cédric Fournet、Jon Howell、Markulf Kohlweiss、Benjamin Kreuter、Michael Naehrig、Bryan Parno 和 Samee Zahur

Geppetto 可以说早于人们对私有智能合约执行的广泛关注，它在以太坊创建大约一年后书写。因此，它没有以私有智能合约执行的背景进行展示。然而，它使用 SNARK 的有界深度递归来方便不受信的证明者在私密数据上执行任何私有（被承诺/签名的）计算程序，而不透露有关运行的程序或所处理数据的信息。因此，它是关于私有智能合约平台的工作前身，例如 Zexe [下面描述]。

可验证的 ASIC (2015) 作者：Riad Wahby、Max Howald、Siddharth Garg、abhi shelat、Michael Walfish

本文考虑了如何在不受信的晶圆厂制造的 ASIC 中安全和富有成效地使用的问题（在 2015 年，只有五个国家拥有顶级晶圆厂）。方法是让快速但不受信的 ASIC 向在更慢但可信的 ASIC 中运行的验证者证明其输出的正确性。只要系统的总执行时间（即证明者和验证者运行时间的总和加上任何数据传输成本）少于保守的基线：在 slower-but-trusted ASIC 上完整运行计算所需的时间。这项工作表明某些证明系统比其他系统更适合硬件实现。目前，针对硬件实现优化证明系统的研究受到了 相当大的关注，但仍需探讨许多内容。

可验证的延迟函数 (2018) 作者：Dan Boneh、Joseph Bonneau、Benedikt Bünz 和 Ben Fisch

引入了可验证延迟函数（VDF）的符号，这是一种在区块链应用中广泛有用的密码学原语，例如，在减轻证明权益共识协议的潜在操纵方面。SNARK（特别是为了增量可验证计算）提供了一条通往先进 VDF 的途径。

Zexe: 实现去中心化私有计算 (2018) 作者：Sean Bowe、Alessandro Chiesa、Matthew Green、Ian Miers、Pratyush Mishra 和 Howard Wu

Zexe 是一种私有智能合约平台的设计。在某种程度上，Zexe 可以看作是 Zerocash（上述描述）的扩展。Zerocash 使单一应用程序可以在链上运行（使用户能够转移代币），同时保护用户数据的隐私，例如，他们发送代币的对象、接收代币的对象、转移的代币数量等。Zexe 允许许多不同的应用程序（智能合约）在同一区块链上运行并相互交互。事务在链下执行，正确执行的证明被发在链上。这样，数据隐私和功能隐私都得到了保护。这意味着与每个事务相关的证明甚至不会透露涉及的应用程序。这一更泛化的工程贡献是，它引入了 BLS12-377，一种对于有效深度-1 配对 SNARK 组合非常有用的椭圆曲线组。

没有重复执行的重复状态机 (2020) 作者：Jonathan Lee、Kirill Nikitin 和 Srinath Setty

这是一篇关于区块链可扩展性中 rollups 的少数学术论文之一。它没有使用 rollups 一词，因为它早于或与这一概念的介绍在学术文献之外是同时进行的。

前端（将计算机程序有效转化为中间表示，例如电路可满足性、R1CS 等）

从 RAM 到可委托的简洁约束满足问题的快速减少 (2012)

作者：Eli Ben-Sasson、Alessandro Chiesa、Daniel Genkin 和 Eran Tromer

从现代的角度来看，这是一项关于虚拟机 (VM) 抽象的实用计算机程序到电路 SAT 转换的早期工作。此论文建立在从 1970 年代末到 1990 年代的工作（例如 Robson 的工作）基础上，详细阐述了从执行 T 步 VM 到大小为 O(T*polylog(T)) 的电路可满足性的确定性减少。

后续的论文，例如 SNARKs for C 和 BCTV，继续通过 VM 抽象开发前端，现代实例包括项目，如 Cairo、RISC Zero 和 Polygon Miden。

将基于证据的已验证计算更进一步到实用性 (2012) 作者：Srinath Setty、Victor Vu、Nikhil Panpalia、Benjamin Braun、Muqeet Ali、Andrew Blumberg 和 Michael Walfish

这篇论文被称为 Ginger，是实用前端技术的又一早期贡献。Ginger 引入了用于一般编程原语的工具，例如条件句、逻辑表达式、比较和位运算，以及基本浮点运算等。它利用这些工具提供了从高级语言到低度算数约束的第一个实际前端（类似于现在被称为 R1CS 的东西），这是一个可应用 SNARK 后端的中间表示（IR）。

“快速减少”论文及其后代采用“CPU-模拟器”的方法生成 IR（即，IR 强制证明者通过为指定步数应用 CPU 的转移函数来正确运行特定程序），而 Ginger 及其后代采取了更类似 ASIC 的方法，生成专为证明者声称正确执行的程序量身定制的 IR。

例如， Buffet 显示在 ASIC 模型中可以处理复杂控制流， 通过将这样的控制流转化为与正在执行的程序相适应的有限状态机，并且这种方法可能比构建通用 CPU 模拟器显著更有效。xJsnark 为多精度算数提供了高效的构造，针对 RAM 和 ROM 的优化，并向程序员暴露了类似 Java 的高级语言，该语言至今仍然流行。CirC 观察到，将计算机程序编译为 R1CS 与程序分析中的知名技术密切相关，并构建了一个编译器构造工具包，结合了来自两个社区的思想（“电路样式表示的 LLVM”）。更早的对 ASIC 风格前端做出贡献的工作包括 Pinocchio 和 Geppetto。

“快速减少”论文采用了一种复杂且昂贵的构造，称为“路由网络”，用于所谓的 内存检查（即，确保不受信的证明者在执行其校验正确性的 VM 整个过程中正确维护了 VM 的随机访问存储器）。这一选择是因为早期工作的目标是获取 PCP，这要求前端同时是非交互的和信息论上安全的。后来的工作 Pantry（是上面提到的 Buffet 工作的前身）使用 Merkle 树代替路由网络，通过将代数（即“SNARK 友好”）哈希函数（根据 Ajtai）编译到约束中来实现效率。这导致了“计算安全”的前端。如今，关于 SNARK 友好哈希函数的研究文献丰富，其中包括 Poseidon、MiMC、Reinforced Concrete、Rescue 等。

确保证明者正确维护 RAM 的最先进技术依赖于所谓的“置换不变指纹识别”方法，这些方法可以追溯到至少 Lipton（1989）并被 Blum et al（1991）用于内存检查。这些技术本质上涉及证明者与验证者之间的互动，但可以通过 Fiat-Shamir 转换实现非交互式。据我们所知，它们是首次引入可实践 SNARK 前端文献的系统 vRAM。

置换不变指纹识别技术如今用于许多虚拟机抽象的前端和 SNARK，包括例如 Cairo。相关的想法在下面两项工作中再次出现，这些思想在今天被广泛应用。

几乎线性时间的零知识证明保证程序正确执行 (2018) 作者：Jonathan Bootle、Andrea Cerulli、Jens Groth、Sune Jakobsen 和 Mary Maller

Plookup: 适用于查找表的简化多项式协议 (2020) 作者：Ariel Gabizon 和 Zachary Williamson

早期的前端工作通过将字段元素分解为位、对这些位执行操作，然后“打包”结果回到一个字段元素中，来表示电路和相关 IR 中的“非算术”操作（如范围检查、按位操作和整数比较）。就结果电路的大小而言，这会导致每个操作的对数开销。

上述两篇工作（BCGJM 和 Plookup）提供有影响力的技术（基于所谓的“查找表”），用于以更有效的方式在电路内部表示这些操作，以摊销的方式。大致而言，对于前端设计者选择的某个参数 B，这些技术将代表电路中每个非算术操作所需的门数减少了一个对数因子，代价是证明者加密承诺了一个额外长度约为 B 的“建议”向量。

• 原文链接： a16zcrypto.com/posts/art...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～