编者按: a16z 加密货币有很长的一系列“枪炮”,从我们的 道佳能 去年对我们 NFT 佳能 更早(在此之前我们原来的 加密佳能) — 请务必注册我们的 web3 每周通讯 获取更多更新以及其他精选资源。
所以下面,我们为那些寻求理解、更深入和构建万物的人挑选了一组资源 零知识:强大的基础技术,是区块链可扩展性的关键,代表着隐私保护应用程序的未来和无数其他创新。 如果您对添加高质量作品有任何建议,请告诉我们@a16z加密.
零知识证明系统已经存在了几十年:它们由 Shafi Goldwasser、Silvio Micali 和 Charles Rackoff 在 1985 年推出,对密码学领域产生了变革性影响,并获得了授予 Goldwasser 和 Micali 的 ACM 图灵奖 2012. 由于这项工作——包括它从理论到实践的转变以及今天在加密/web3 中的应用——已经进行了数十年,我们还在我们的经典系列中首次分享了第二部分(目前,包括在下面): 由注释的阅读列表 贾斯汀·泰勒,在下面的第一部分之后。
致谢:还要感谢 Michael Blau、Sam Ragsdale 和 Tim Roughgarden。
基础、背景、演变
其中一些论文也更多地涉及一般的密码学(并非都是零知识本身),包括概述当今零知识证明解决的问题或关键进展:如何确保开放网络中的隐私和身份验证。
密码学的新方向 (1976)
惠特菲尔德迪菲和马丁赫尔曼
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)
通过拉尔夫默克尔
http://www.merkle.com/papers/Protocols.pdf
通过不安全通道进行安全通信 (1978)
通过拉尔夫默克尔
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 Rackof
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf
计算合理的证明 (2000)
西尔维奥·米卡利
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)
斯蒂芬妮拜耳和延斯格罗斯
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
可扩展、透明和后量子安全的计算完整性 (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 论证在密码学中有无数的应用,并且在过去十年中已经从理论跃升到实践。
通过贾斯汀泰勒
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf
零知识证明模型的演变 — 对零知识证明的回顾,Meiklejohn(伦敦大学学院,谷歌)着眼于推动其发展的应用程序、为捕捉这些新交互而出现的不同模型、我们可以实现的结构以及工作剩下要做的。
莎拉·米克尔约翰
https://www.youtube.com/watch?v=HO97kVMI3SE
ZK 白板会议 — 介绍模块
与丹·博内 (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
即将到来的隐私层将如何修复损坏的网络
由霍华德·吴
https://future.com/a-privacy-layer-for-the-web-can-change-everything/
zkSNARKs 简介
与霍华德·吴、安娜·罗斯
https://zeroknowledge.fm/38-2/
zk-SNARK 为什么以及如何工作:一个明确的解释
马克西姆·佩特库斯
https://arxiv.org/pdf/1906.07221.pdf
零知识证明简介
弗雷德里克·哈里森和安娜·罗斯
https://www.zeroknowledge.fm/21 [+其他地方的总结文章 此处]
Zk-SNARKs:引擎盖下
通过 Vitalik Buterin
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
部分1, 部分2, 部分3
分散速度 ——关于零知识证明、去中心化硬件的进步
通过埃琳娜汉堡
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 的联合创始人之一
与亚历山德罗·基耶萨、安娜·罗斯
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/
深潜,建设者指南
概率证明的基础 — 包含 5 个单元的课程,来自交互式证明等
亚历山德罗·基耶萨
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC
STARK——第一、二、三部分
通过 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 证明系统的机制
通过艾伦 Szepieniec
https://aszepieniec.github.io/stark-anatomy/
SNARK 设计,第 1 部分 — 调查,在汇总中使用,更多
通过贾斯汀泰勒
https://www.youtube.com/watch?v=tg6lKPdR_e4
SNARK 设计,第 2 部分 — 汇总、性能、安全性
通过贾斯汀泰勒
https://www.youtube.com/watch?v=cMAI7g3UcoI
测量 SNARK 性能 - 前端,后端,更多
通过贾斯汀泰勒
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/
了解 PLONK
https://vitalik.ca/general/2019/09/22/plonk.html
PLONK 零知识证明系统 — 关于 PLONK 工作原理的 12 个短片系列
由大卫王
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC
从 AIR 到 RAP — PLONK 风格的算术是如何工作的
通过阿里尔加比松
https://hackmd.io/@aztec-network/plonk-arithmetiization-air
PLONK 和 Plookup 中的多集检查
通过阿里尔加比松
https://hackmd.io/@arielg/ByFgSDA7D
Halo2 设计 — 来自 ECC
https://zcash.github.io/halo2/design.html
笨笨2
https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf
应用程序和教程:概念证明、演示、工具等
应用zk — 学习资源
由 0xPARC
https://learn.0xparc.org/materials/intro
zkSNARKs 的在线开发环境 — zkREPL,一组用于与浏览器内的 Circom 工具栈交互的新工具
通过凯文郭
https://zkrepl.dev (+解释线程 此处)
从零到英雄的二次算术程序
通过 Vitalik Buterin
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
在 zkEVM 上
与 Alex Gluchowski 和 Anna Rose
https://zeroknowledge.fm/175-2/
不同类型的 zkEVM
通过 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 语言
与亚历克斯·奥兹德米尔和安娜·罗斯
https://zeroknowledge.fm/172-2/
黑暗森林——将 zk 密码学应用于游戏 — 完全去中心化且持久的 RTS(实时策略)游戏
https://blog.zkga.me/announcing-darkforest
面向工程师的 ZKP — 看看黑暗森林 ZKP
https://blog.zkga.me/df-init-circuit
潜入零知识
与埃琳娜·纳多林斯基、安娜·罗斯、詹姆斯·普雷斯特维奇
https://zeroknowledge.fm/182-2/
zkDocs:零知识信息共享
山姆·拉格斯代尔和丹·博内
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/
零知识证明的隐私保护加密空投
通过山姆拉格斯代尔
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/
链上可信设置仪式 -
瓦莱里娅·尼古拉恩科和山姆·拉格斯代尔
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 应用程序以及构建加密隐私技术的专家
与安娜·罗斯
https://zeroknowledge.fm/
...贾斯汀·泰勒(Justin Thaler)按主题和年表的带注释的阅读清单:
来自线性 PCP 的 SNARK(又名具有特定电路设置的 SNARK)
没有短 PCP 的有效论证 (2007)
作者:Yuval Ishai、Eyal Kushilevitz 和 Rafail Ostrovsky
大约在 2007 年之前,SNARK 主要是通过 基利安–米卡利 范式,采用“短”概率可检查证明(PCP)并通过 Merkle 散列和 Fiat-Shamir 转换将其“加密编译”为简洁的论点。 不幸的是,即使在今天,做空 PCP 也是复杂且不切实际的。 这篇论文 (IKO) 展示了如何使用同态加密从“长而结构化的”PCP 中获得简洁(非透明)的交互式参数。 这些可以比短 PCP 简单得多,并且由此产生的 SNARK 具有更短的证明和更快的验证。 这些论点首先被认为具有提高实际效率的潜力,并在 胡椒. 不幸的是,IKO 的论点有一个二次时间证明者和二次大小的结构化参考字符串,因此它们不能扩展到大型计算。
没有 PCP 的二次跨度程序和简洁的 NIZK (2012)
作者:罗萨里奥·根纳罗、克雷格·金特里、布莱恩·帕诺和玛丽安娜·雷科娃
这篇突破性论文 (GGPR) 将 IKO 方法的验证器成本从电路尺寸的二次方降低到准线性度。 在早期工作的基础上 格罗斯 和 利普马,它还通过基于配对的密码学提供 SNARK,而不是 IKO 中的交互式参数。 它在现在称为 rank-1 约束满足 (R1CS) 问题的上下文中描述了它的 SNARK,这是算术电路可满足性的概括。
这篇论文还作为第一个看到商业部署的 SNARK(例如,在 ZCash 中)的理论基础,并直接导致了今天仍然流行的 SNARK(例如,Groth16)。 GGPR 的论点的初步实现进来了 Zaatar 和 木偶奇遇记,后来的变体包括 C 的 SNARK 和 央视. 商务部 给出了阐明这些线性 PCP 到 SNARK 转换的一般框架(另见附录 A Zaatar) 并描述其各种实例。
关于基于配对的非交互式参数的大小 (2016)
通过延斯格罗斯
这篇通俗地称为 Groth16 的论文提出了 GGPR 的 SNARK 的改进,即使在今天也能实现最先进的具体验证成本(证明是 3 个组元素,验证由三个配对操作主导,至少假设公众输入短)。 安全性在通用组模型中得到证明。
具有通用可信设置的 SNARK
PlonK:在拉格朗日基上的排列,用于普遍的非交互式知识论证 (2019)
作者:Ariel Gabizon、Zachary Williamson 和 Oana Ciobotaru
Marlin:使用通用且可更新的 SRS 预处理 zkSNARK (2019)
作者:Alessandro Chiesa、Yuncong Hu、Mary Maller、Pratyush Mishra、Psi Vesely 和 Nicholas Ward
PlonK 和 Marlin 都用通用设置替换了 Groth16 中特定于电路的可信设置。 这是以 4 到 6 倍大的样张为代价的。 可以将 PlonK 和 Marlin 视为在 Groth16 和前辈的可信设置期间进行特定于电路的工作,并将其移动到发生的预处理阶段 after 受信任的设置,以及在 SNARK 证明生成期间。
以这种方式处理任意电路和 R1CS 系统的能力有时被称为全息或计算承诺,在 斯巴达 (在本汇编后面讨论)。 因为在证明生成过程中发生了更多的工作,对于给定的电路或 R16CS 实例,PlonK 和 Marlin 的证明器比 Groth1 慢。 然而,与 Groth16 不同,PlonK 和 Marlin 可以使用比 R1CS 更通用的中间表示。
多项式承诺方案,SNARK 中的关键密码原语
多项式及其应用的常数大小承诺 (2010)
通过 Aniket Kate、Gregory Zaverucha 和 Ian Goldberg
本文介绍了多项式承诺方案的概念。 它给出了具有恒定大小承诺和评估证明的单变量多项式(通常称为 KZG 承诺)的方案。 该方案使用可信设置(即结构化参考字符串)和基于配对的密码术。 它在今天的实践中仍然非常流行,并用于 SNARK,包括上面讨论的 PlonK 和 Marlin(Groth16 使用极其相似的加密技术)。
快速 Reed-Solomon 交互式 Oracle Proofs of Proximity (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 码换成具有更快编码的不同纠错码,可以获得一个线性时间证明器,该证明器还可以在任何领域本地工作。 该方法已在 分裂 和 猎户座,产生最先进的证明者性能。
Bulletproofs:机密交易的简短证明等 (2017)
作者: Benedikt Bunz、Jonathan Bootle、Dan Boneh、Andrew Poelstra、Pieter Wuille 和 Greg Maxwell
改进之前的工作 BCCGP, Bulletproofs 给出了一个透明的多项式承诺方案(实际上是一种称为内积参数的概括),它基于计算离散对数的难度,具有对数证明大小但线性验证器时间。 由于其透明性和简短证明(例如,它用于 ZCash Orchard 和 Monero),该方案在今天仍然很受欢迎。
Dory:广义内积和多项式承诺的高效、透明论证 (2020)
乔纳森·李
Dory 将 Bulletproofs 中的验证时间从线性减少到对数,同时保持透明度和对数大小的证明(尽管具体大于 Bulletproofs)和透明度。 使用配对并基于 SXDH 假设。
交互式证明、多证明者交互式证明和相关的 SNARK
委托计算:麻瓜的交互式证明 (2008)
作者:Shafi Goldwasser、Yael Tauman Kalai 和 Guy Rothblum
在本文之前,通用交互式证明需要一个 超多项式时间 证明者。 本文给出了一种交互式证明协议,通常称为 GKR 协议,具有多项式时间证明器和拟线性时间验证器,适用于任何具有高效并行算法的问题(等效地,交互式证明适用于任何深度较小的算术电路)。
具有流式交互证明的实际验证计算 (2011)
作者:Graham Cormode、Michael Mitzenmacher、Justin Thaler
这篇论文(有时称为 CMT)将 GKR 协议中的证明者时间从电路大小的四次减少到准线性。 产生了通用交互式证明的第一个实现。 一系列后续作品(多香果, 泰勒13, 长颈鹿及 天秤座) 进一步减少了验证器的运行时间,电路尺寸从准线性变为线性。
vSQL:验证动态外包数据库上的任意 SQL 查询 (2017)
作者:张玉鹏、丹尼尔·根金、乔纳森·卡茨、迪米特里奥斯·帕帕多普洛斯和 Charalampos Papamanthou
尽管标题指的是特定的应用领域(数据库),但本文的贡献更为笼统。 具体来说,它观察到通过将交互式证明与多项式承诺方案(对于多线性多项式)相结合,可以获得电路可满足性的简洁论据。
后来 合作 呈现 论点零知识并为多线性多项式引入了不同的承诺方案。
Spartan:高效且通用的 zkSNARK,无需可信设置 (2019)
通过 Srinath Setty
通过将多证明者交互证明 (MIP) 与多项式承诺方案相结合,获得电路可满足性和 R1CS 的 SNARK,建立在早期关于称为具体高效 MIP 的工作的基础上 三叶草. 其效果是获得比从交互式证明(如上面讨论的 GKR 协议)派生的证明更短的 SNARK。 与 PlonK 和 Marlin 类似,Spartan 还展示了如何通过预处理和 SNARK 证明生成来处理任意电路和 R1CS 系统。
Spartan 使用了多项式承诺方案 蹄兔. 随后的作品称为 分裂 和 猎户座 将 Spartan 的 MIP 与其他多项式承诺方案相结合,以产生第一个实施的 SNARK 与线性时间证明者。
短 PCP 和 IOP
具有 Polylog 查询复杂性的短 PCP (2005)
由 Eli Ben-Sasson 和 Madhu 苏丹
这项理论工作给出了第一个概率可检查证明(PCP),其证明长度与要验证的计算大小和多对数查询成本(尽管是线性验证器时间)准线性。 在 PCP 到 SNARK 的 Kilian-Micali 转换之后,这是向具有准线性时间证明器和多对数时间验证器的 SNARK 迈出的一步。
后期理论工作 将验证器时间减少到多对数。 随后 以实际为重点的工作改进了这种方法,但今天的短 PCP 仍然不切实际。 要获得实用的 SNARK, 后来 合作 转身 至 PCP 的交互式概括称为 交互式 Oracle 证明 (IOPS)。 这些努力导致并建立在 星期五,这是本汇编的多项式承诺部分中讨论的一种流行的多项式承诺方案。
此类别的其他作品包括 中科博 及其后代。 这些不能实现简洁的证明,但它们具有良好的常数因子,因此对于证明小陈述很有吸引力。 它们导致了一系列后量子签名,例如 野餐 有 很 优化 in 几个 合作. ZKBoo 遵循一种独特的设计范式,称为 头脑中的 MPC,但它会产生 IOP。
递归 SNARK
增量可验证的计算或知识证明意味着时间/空间效率 (2008)
通过保罗勇敢
这项工作引入了增量可验证计算 (IVC) 的基本概念,其中证明者运行计算并始终保持证明到目前为止计算是正确的。 它通过 SNARK 的递归组合构建 IVC。 在这里, 知识健全性 SNARKs 的属性对于建立递归组合的非交互式参数的可靠性至关重要。 本文还为 PCP 衍生的 SNARK 提供了一种极其有效的知识提取器(根据 Kilian-Micali 范式)。
通过椭圆曲线的循环可扩展零知识 (2014)
作者:Eli Ben-Sasson、Alessandro Chiesa、Eran Tromer 和 Madars Virza
跟随 理论工作,本文使用 GGPR 的 SNARK 变体的递归应用,为简单的虚拟机(TinyRAM,来自 C 的 SNARK 纸)。
还介绍了椭圆曲线循环的概念,这对于递归组合使用椭圆曲线密码学的 SNARK 很有用。
没有可信设置的递归证明组合 (2019)
作者:肖恩·鲍、杰克·格里格和戴拉·霍普伍德
这项工作(称为 Halo)研究如何递归组合透明的 SNARK。 这比编写非透明的更具挑战性,因为透明 SNARK 中的验证过程可能要昂贵得多。
这引发了一场 线 of 工作 最终在系统中达到顶峰,例如 新星 实现最先进的 IVC 性能,甚至优于通过 Groth16 等非透明 SNARK 组合获得的性能。
应用领域
Zerocash:来自比特币的去中心化匿名支付 (2014)
作者:Eli Ben Sasson、Alessandro Chiesa、Christina Garman、Matthew Green、Ian Miers、Eran Tromer、Madars Virza
以先前的工作为基础,包括 Zerocoin (与 匹诺曹硬币 作为并行工作),本文使用 GGPR 派生的 SNARK 来设计私有加密货币。 导致 ZCash。
Geppetto:多功能可验证计算 (2014)
作者:Craig Costello、Cédric Fournet、Jon Howell、Markulf Kohlweiss、Benjamin Kreuter、Michael Naehrig、Bryan Parno 和 Samee Zahur
Geppetto 可以说早于对私人智能合约执行的兴趣爆发,大约是在以太坊创建一年后编写的。 因此,它没有在私人智能合约执行的背景下呈现。 但是,它使用 SNARK 的有限深度递归来允许不受信任的证明者在私有数据上执行任何私有(提交/签名)计算机程序,而不会泄露有关正在运行的程序或运行它的数据的信息。 因此,它是私有智能合约平台工作的前身,例如 泽西 [如下面所描述的]。
可验证的 ASIC (2015)
作者:Riad Wahby、Max Howald、Siddharth Garg、abhi shelat、Michael Walfish
本文考虑了如何安全有效地使用在不受信任的代工厂中制造的 ASIC 的问题(2015 年,只有五个国家拥有高端代工厂)。 方法是让快速但不受信任的 ASIC 向运行在较慢但受信任的 ASIC 上的验证器证明其输出的正确性。 只要系统的总执行时间(即证明者和验证者的运行时间加上任何数据传输成本的总和)小于天真的基线:在较慢的系统上完全运行计算所需的时间,该解决方案就很有趣- 但值得信赖的 ASIC。 使用 GKR/CMT/Allspice 交互式证明的变体,该论文确实击败了许多基本问题的朴素基线,包括数论变换、模式匹配和椭圆曲线操作。 这项工作表明,一些证明系统比其他证明系统更适合硬件实现。 优化硬件实现的证明系统现在正在接收 大量 关注我们, 但仍有许多待探索。
可验证: 延迟函数 (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 允许许多不同的应用程序(智能合约)在同一个区块链上运行并相互交互。 交易在链下执行,正确执行的证明发布在链上。 不仅数据隐私受到保护,功能隐私也受到保护。 这意味着与每笔交易相关的证明甚至不会揭示该交易属于哪个应用程序。 Zexe 的一个更一般的工程贡献是它引入了 BLS12-377,这是一个椭圆曲线组,可用于基于配对的 SNARK 的有效深度 1 组合。
没有复制执行的复制状态机 (2020)
作者:Jonathan Lee、Kirill Nikitin 和 Srinath Setty
这是为数不多的关于区块链可扩展性汇总的学术论文之一。 它不使用术语汇总,因为它早于或与学术文献之外引入的概念同时出现。
前端(从计算机程序到中间表示的有效转换,例如电路可满足性、R1CS 等)
从 RAM 到可委托的简洁约束满足问题的快速缩减 (2012)
作者:Eli Ben-Sasson、Alessandro Chiesa、Daniel Genkin 和 Eran Tromer
从现代的角度来看,这是一项针对虚拟机 (VM) 抽象的实用计算机程序到电路 SAT 转换的早期工作。 以 1970 年代后期至 1990 年代的作品为基础(例如, 罗布森) 本文阐述了从执行 VM 执行 T 步到大小为 O(T*polylog(T)) 的电路的可满足性的确定性缩减。
随后的论文,例如, C 的 SNARK 和 央视,继续通过 VM 抽象开发前端,现代实例化包括诸如 开罗, RISC 零及 多边形米登.
使基于证明的验证计算更接近实用性 (2012)
作者:Srinath Setty、Victor Vu、Nikhil Panpalia、Benjamin Braun、Muqeet Ali、Andrew J. Blumberg 和 Michael Walfish
这篇论文被称为 Ginger,是对实用前端技术的另一个早期贡献。 Ginger 介绍了通用编程原语的小工具,例如条件和逻辑表达式、比较和通过位拆分的按位算术、原始浮点算术等。它使用这些小工具提供了从高级语言到低级语言的第一个实现前端算术约束(类似于现在称为 R1CS),一种可以应用 SNARK 后端的中间表示 (IR)。
而“Fast Reductions”论文及其后代在生成 IR 时使用“CPU 仿真器”方法(即,IR 通过应用 CPU 的转换函数执行指定数量的步骤来强制证明者正确运行特定程序) , Ginger 及其后代采用更类似于 ASIC 的方法,生成适合证明者声称正确执行的计算机程序的 IR。
例如, 自助餐 表明在 ASIC 模型中处理复杂的控制流是可能的,通过将这种控制流变成为正在执行的程序量身定制的有限状态机,并且这种方法比构建通用 CPU 仿真器要高效得多。 xJ蛇 为多精度算术提供了有效的构造,优化了 RAM 和 ROM,并向程序员公开了一种类似 Java 的高级语言,这种语言在今天仍然很流行。 圆环 观察到将计算机程序编译为 R1CS 与程序分析中众所周知的技术密切相关,并构建了一个编译器构建工具包,该工具包结合了两个社区的想法(“LLVM for circuit-like representations”)。 早期为 ASIC 风格的前端做出贡献的作品包括 木偶奇遇记 和 杰佩托.
“Fast-Reductions”论文使用了一种复杂且昂贵的结构,称为“路由网络”,用于所谓的“路由网络”。 内存检查 (即,确保不受信任的证明者在其正确性被证明的VM 的执行过程中正确地维护VM 的随机存取存储器)。 之所以做出这样的选择,是因为像这件作品这样的早期作品正在寻求获得一个 PCP,这需要前端是 都 非交互式和信息理论上的安全。 后来的工作叫 茶水 (前身 自助餐 上面提到的工作)使用 Merkle 树代替路由网络,通过编译代数(即“SNARK-friendly”)哈希函数来提高效率,因为 阿杰泰,进入约束。 这导致了“计算安全”的前端。 今天,有大量关于 SNARK 友好散列函数的研究文献,示例包括 波塞冬, 微机电, 钢筋混凝土, 营救等等。
确保证明者正确维护 RAM 的最先进技术依赖于所谓的“排列不变指纹”方法,至少可以追溯到 利普顿 (1989)并用于内存检查 布鲁姆等人。 (1991)。 这些技术本质上涉及证明者和验证者之间的交互,但可以通过 Fiat-Shamir 转换呈现非交互。 据我们所知,它们是通过一个名为 虚拟RAM.
置换不变指纹技术现在用于许多前端和虚拟机抽象的 SNARK,包括例如 开罗. 密切相关的思想在以下两部作品的相关语境中再次出现,并在当今的实践中得到广泛应用。
用于正确程序执行的近线性时间零知识证明 (2018)
作者:Jonathan Bootle、Andrea Cerulli、Jens Groth、Sune Jakobsen 和 Mary Maller
Plookup:用于查找表的简化多项式协议 (2020)
由 Ariel Gabizon 和 Zachary Williamson
前端的早期工作通过将字段元素分解为位,对这些位执行操作,然后“打包”来表示电路和相关 IR 内部的“非算术”操作(例如范围检查、按位操作和整数比较)结果返回到单个字段元素。 就最终电路的大小而言,这会导致每次操作的对数开销。
上述两部作品(BCGJM 和 Plookup)提供了有影响力的技术(基于所谓的“查找表”),以更有效地表示电路内部的这些操作,在摊销意义上。 粗略地说,对于前端设计人员选择的某些参数 B,这些参数将表示电路中每个非算术运算所需的门数减少了 B 中的对数因子,代价是证明者以密码方式承诺额外长度大致为 B 的“建议”向量。