做网站购买空间多少钱,嘉定网站建设电脑培训,免费建站的方法,页面预加载wordpress1. 引言
前序博客有#xff1a;
ZKP历史总览SNARK原理示例SNARK性能及安全——Prover篇SNARK性能及安全——Verifier篇Transparent 且 Post-quantum zkSNARKsSNARK DesignRollup项目的SNARK景观
SNARKs因#xff1a;
proof size证明时长验证时长密码学信任假设是否需要tr…1. 引言
前序博客有
ZKP历史总览SNARK原理示例SNARK性能及安全——Prover篇SNARK性能及安全——Verifier篇Transparent 且 Post-quantum zkSNARKsSNARK DesignRollup项目的SNARK景观
SNARKs因
proof size证明时长验证时长密码学信任假设是否需要trusted setup
等而各不相同。从广义上讲实际所用证明系统可分为三大类
Pairing-based SNARKs必须基于pairing曲线构建需要可信设置是人们通常所认为的“SNARKs”。Hash-based SNARKs或Code-based SNARKs不需要基于曲线构建无需可信设置且具有合理的后量子安全性是人们通常所说的“STARKs”。Non-Pairing Elliptic curve-based SNARKs可基于非paiirng曲线构建且无需可信设置常见的如Bulletproofs和Folding schemes。
1.1 Pairing-based SNARKs
Pairing-based SNARKs包括
PlonkMarlinGroth16
等证明系统如果人们熟悉 ZK大多数人会想到 Groth16 证明系统。
这些Pairing-based SNARKs的特点为
proof size非常小且大小恒定验证速度非常快但证明速度通常较慢。
这是因为Pairing-based SNARKs需要
在大素数域上工作这很慢而且需要使用配对友好的椭圆曲线。
由于Pairing-based SNARKs使用椭圆曲线因此
其无法抵御量子攻击。
值得注意的是并非所有可信设置 SNARK 都具有相同类型的可信设置
1Groth16 要求每个电路都有一个可信设置2而 Plonk、Marlin 和其他基于 KZG 的证明系统可以对所有有限大小的电路使用单个可信设置。 这种“universal 通用”可信设置也是可更新的 给定一个可信设置任何人都可以稍后向可信设置添加随机性。这对于 Groth16 来说是不可能的因为Groth16 要求每个电路都有一个新设置。
1.2 Hash-based SNARKs或Code-based SNARKs
Hash-based SNARKs或Code-based SNARKs中的典型代表有
STARKsPlonky2带预处理的FRI-based证明系统
Hash-based SNARKs或Code-based SNARKs证明系统
1通常具有出色的prover性能 尤其是当其使用具有特殊结构的小域时如Goldilocks、Babybear或Mersenne 31 2但proof size要大得多。 具体而言FRI-based proof 可比 Groth16 proof 大 100 到 1000 倍200 字节 vs. 50-200kB。其他基于纠错码的证明系统——如Bininus其使用Brakedown PCS而不是 FRI PCS的proof可能更大或可能更小——若可借助STIR等类似技术则可实现更小的proof。 3不需要可信设置4且在使用合适的哈希函数实例化时具有抗量子性。5其安全性仅依赖于底层哈希函数的安全性。 然而与基于椭圆曲线的 SNARKs 相比FRI-based证明系统的安全性提供了更多可调的自由度这使得分析其安全性更加复杂。
大多数最先进的大型电路证明系统都针对证明时长进行了优化因此使用FRI-based证明系统。但是当希望在区块链上验证这些证明时即使在以太坊上对于纯 STARK proof 来说这也很昂贵。因此大多数已部署的系统将 STARK proof包装在pairing-based SNARK 中如 Groth16 或 fflonkPlonk 的变体。从而提供了两种方案的主要优点
非常快的prover和非常小的proof但牺牲了量子抗性并需要可信的设置。这也是“proof recursion递归证明”这一非常强大想法的示例 通过在另一个证明中验证证明可以将更大的证明或可能将许多更大的证明压缩为较小的证明。
1.3 Non-Pairing Elliptic curve-based SNARKs
Non-Pairing Elliptic curve-based SNARKs中包括
BulletproofsFolding Schemes
其中Bulletproofs
具有 concretely small proofs证明时长与Pairing-based SNARKs 相当且没有可信设置。但其验证复杂性非常差 验证Bulletproofs proof所需的时间与构建该proof所需的时间成正比。这意味着Bulletproofs-based协议仅限于像范围证明这样的小电路更根本的是这意味着人们无法有效地、递归地用一个Bulletproofs来验证另一个Bulletproofs——因为验证Bulletproofs的电路将比被证明的原始电路更大
Halo改变了这一现状
展示了如何以递归方式“accumulate 积累” Bulletproofs而无需以递归方式验证整个 Bulletproofs。
这一系列工作成果颇丰最终催生出各种folding方案如
NovaHyperNovaProtoStarProtoGalaxy等等folding方案有很多。
与folding方案结合使用时人们可以使用 Bulletproofs 构建具有小证明、无可信设置和相当快prover的 SNARKs。
基于folding的证明系统能否与小域 FRI 相媲美仍是一个悬而未决的问题。最近的一些工作如Benedikt Bunz ¨等人2024年论文Accumulation without Homomorphism实际上试图统一folding和 FRI但仅对小深度递归有效。
2. Sumcheck 和 GKR
从历史上看大多数 SNARKs 都使用单变量多项式将算术电路编码为 IOP。
这部分是由于底层多项式承诺方案特别是 FRI 和 KZG的结构也由于该方法相对简单。在基于单变量多项式的SNARKs方案中证明者必须计算“商多项式”来证明该单变量方程得到满足。 商多项式的有效计算需要具有超线性运行时间的快速傅里叶变换 (FFT) O ( n log n ) O(n\log n) O(nlogn)并且非常昂贵。 特别是当使用大域时FFT 计算需要大量内存。这对于快速prover来说是一个主要瓶颈。
最近人们开始使用一种称为“Sumcheck协议”的替代协议。sumcheck协议最初于 1992 年作为纯理论成果发表见1992年论文《Algebraic Methods for Interactive Proof Systems》现在sumcheck协议重新成为单变量 SNARKs 的主要痛点之一的解决方案
不再需要计算商多项式。相反prover使用多线性多项式对witness进行编码并与verifier进行 O ( log n ) O(\log n) O(logn)轮交互以“fold”注意与“folding方案”中的“fold”不同更像 Bulletproofs 和 FRI中的“fold”这些多项式。 这意味着其它条件相同的情况下sumcheck-based proof 通常比单变量proof更大但可以在线性时间内证明且内存要求更低。
一些sumcheck-based SNARKs 包括
SpartanHyperPlonkHonk
从某种意义上说sumcheck协议一直都隐藏在人们的视线中。
Bulletproofs 所基于的inner product argument与sumcheck协议具有相同的基本结构。事实上这可以变得严格详情见Jonathan Bootle等人2021年论文Sumcheck Arguments and their Applications。
这意味着人们可以非常有效地将inner product argument的结构与sumcheck-based SNARKs 结合使用。FRI 也是如此正如最近在 BaseFold 中观察到的那样。
最近GKR协议也引起了applied ZK 社区的新兴趣。
GKR 协议以 sumcheck 协议为基础通过“layering 分层”不同的 sumcheck 实例。 这限制了可以应用 GKR 的电路类型但值得注意的是其可完全避免对中间层进行commit。 回想一下承诺特别是对于elliptic curve-based SNARKs是证明中最昂贵的部分。 权衡是verifier必须与电路中的层数成比例地完成工作对于许多类型的电路verifier最终会有 O ( log 2 n ) O(\log^2 n) O(log2n)的总工作量。
通过改变用于实例化 GKR 的sumcheck类型已经出现了一些有希望的新研究成果来微调这种权衡如Benedikt B¨unz和Jessica Chen 2024年论文《Proofs for Deep Thought: Accumulation for large memories and deterministic computations》。
3. Lookup Arguments
传统上SNARKs 将要证明的陈述编码为算术电路中的加法和乘法“门”网络。
从技术意义上讲这已经足够了但并不总是很有效。 如若想证明 x x x位于某个范围内可能首先需要将该值拆分成位检查每个位是否有效然后检查合并这些位是否得到原始值。
若能简单地构造一组有效值并检查 x x x是这些值之一则要简单得多。
这正是Lookup Arguments所允许的在某个表中查找一个值。
事实证明查找表是一种非常强大的原语早期计算机广泛使用。Lookup Arguments 非常强大甚至可将其看成是一种“通用原语”因为人们可仅使用查找表来实现 SNARKs——被称为“lookup singularity查找奇点”。虽然仅使用查找的 SNARKs 现如今可能效率不高但Lookup Arguments对于许多无法高效算术化的操作类别如转换为加法、乘法和随机查询确实很有效。使用Lookup Arguments还可以简化 SNARKs 的分析。
有许多不同的lookup协议。
1动态表查找——最简单的协议只是在电路中构建表适用于当该表的内容是动态的但证明时间取决于该表的大小时 可使用plookup或log derivative Lookup Arguments来构建。 2静态表查找——当表是静态的时可使用另一组不同的Lookup Arguments 从Caulk到cq Lookup Arguments系列适用于静态表。 在这些方案中会对该静态表进行预处理以便在证明时prover所做的密码学工作仅与其想要查找的值的数量成比例。从而能够有效地构建对非常大的表的查找。 3结构化表查找——如Lasso 在这种情况下该结构化表是预先固定的但它具有一些结构因此不需要为表预先计算任何东西。Lasso 能够将对非常大的结构化表的查找转换为对一组较小表的查找。这些较小的查找可以使用不同的协议执行且当使用 GKR 时可以避免在证明lookup arguments时承诺任何“大”值。虽然对结构化表的限制似乎会限制该协议但配套论文 Jolt 表明所有 RISCV 操作都可以使用结构化查找表来实现。
4. BitVM
不幸的是以上这些SNARKs发展都与比特币本身不兼容因为比特币脚本和区块大小限制太有限无法在单个比特币区块中容纳 SNARKs verifier。即使是如 Groth16 或 BN254 上的 fflonk针对verifier简单性优化的 SNARKs verifier也过于复杂。随着 BitVM 和最近的 BitVM2 的出现这种情况发生了变化。
BitVM 是一种乐观协议可用于“证明”比特币可以原生执行的更复杂statement的执行。
乐观意味着 BitVM 不是由prover实际构建 SNARKs而是依靠多个预先指定的挑战者之一来提交欺诈证明。 BitVM2 放宽了这一点以便任何人都可以提交挑战但代价是链上通信量明显增多。
基于 BitVM 的协议还有许多额外的改进包括Alpen Labs团队的SNARKnado
可用于乐观地验证 SNARK从而为比特币带来零知识证明的力量。
5. 结论
在过去的十到十五年里SNARKs 已经从一门几乎完全局限于学术界的理论学科发展成为一项在世界范围内部署的实用技术。
实际计算的证明速度的提高速度甚至比摩尔定律的提高速度还要快得多现在以数百千赫兹为单位——详情见2024年5月视频 On Comparing Proof Systems and their Implementations - Matteo Campanelli (Matter Labs)。就目前而言这种不懈的改进步伐没有放缓的迹象。为此非常感谢 SNARK 密码学理论家和实践者的不懈努力。
人们还欠比特币诞生前的早期黑客和密码朋克很多东西并继承了他们的文化。
与传统密码学不同传统密码学往往受制于寻租知识产权从而限制了其采用如比特币中的 Schnorr 签名而 SNARKs 研究则一直保持自由和开放。这是一个了不起的情况不能视之为理所当然。毫无疑问这也是极速改进的必要先决条件。随着这个领域的成熟以及越来越多的项目寻求赚钱至关重要的是要保持这种微妙的平衡并在社会上强制执行本工作必须free的规范。
大部分改进都是由区块链应用推动的。与传统的中心化服务设置不同区块链没有可信任的第三方来委托验证。这使得区块链以及广义上的去中心化协议成为 SNARKs 的完美应用。在比特币的历史中人们很早就认识到了这一点见2013年8月Bitcoin论坛帖子Really Really ultimate blockchain compression: CoinWitness但当时这项技术还不够成熟。这种情况已经或至少几乎已经不再存在正如 SNARKs 在现实世界中的大量部署所证明的那样。现在是时候将 SNARKs 带回比特币了。
另外2024年5月视频 On Comparing Proof Systems and their Implementations - Matteo Campanelli (Matter Labs)中指出ZKP学术和工业实践之间存在分离并建议构建针对ZKP的L2BEAT平台以对各ZKP系统统一测试和评估标准。
参考资料
[1] Alpen Labs团队2024年5月29日博客 Current state of SNARKs: A survey of today’s SNARKs landscape.
