当今SNARKs全景

1. 引言

前序博客有：

• ZKP历史总览
• SNARK原理示例
• SNARK性能及安全——Prover篇
• SNARK性能及安全——Verifier篇
• Transparent 且 Post-quantum zkSNARKs
• SNARK Design
• Rollup项目的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包括：

• Plonk
• Marlin
• Groth16

等证明系统，如果人们熟悉 ZK，大多数人会想到 Groth16 证明系统。

这些Pairing-based SNARKs的特点为：

• proof size非常小，且大小恒定
• 验证速度非常快
• 但证明速度通常较慢。

这是因为Pairing-based SNARKs需要：

• 在大素数域上工作，这很慢，
• 而且需要使用配对友好的椭圆曲线。

由于Pairing-based SNARKs使用椭圆曲线，因此：

• 其无法抵御量子攻击。

值得注意的是，并非所有可信设置 SNARK 都具有相同类型的可信设置：

• 1）Groth16 要求每个电路都有一个可信设置，
• 2）而 Plonk、Marlin 和其他基于 KZG 的证明系统可以对所有有限大小的电路使用单个可信设置。
  • 这种“universal 通用”可信设置也是可更新的：
    • 给定一个可信设置，任何人都可以稍后向可信设置添加随机性。
    • 这对于 Groth16 来说是不可能的，因为Groth16 要求每个电路都有一个新设置。

1.2 Hash-based SNARKs（或，Code-based SNARKs）

Hash-based SNARKs（或，Code-based SNARKs）中的典型代表有：

• STARKs
• Plonky2：带预处理的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 或 fflonk（Plonk 的变体）。从而提供了两种方案的主要优点：

• 非常快的prover和非常小的proof，
• 但牺牲了量子抗性并需要可信的设置。
• 这也是“proof recursion递归证明”这一非常强大想法的示例：
  • 通过在另一个证明中验证证明，可以将更大的证明或可能将许多更大的证明压缩为较小的证明。

1.3 Non-Pairing Elliptic curve-based SNARKs

Non-Pairing Elliptic curve-based SNARKs中包括：

• Bulletproofs
• Folding Schemes

其中Bulletproofs：

• 具有 concretely small proofs，
• 证明时长与Pairing-based SNARKs 相当，
• 且没有可信设置。
• 但其验证复杂性非常差：
  • 验证Bulletproofs proof所需的时间与构建该proof所需的时间成正比。
  • 这意味着Bulletproofs-based协议仅限于像范围证明这样的小电路，更根本的是，这意味着人们无法有效地、递归地用一个Bulletproofs来验证另一个Bulletproofs——因为验证Bulletproofs的电路将比被证明的原始电路更大！

Halo改变了这一现状：

• 展示了如何以递归方式“accumulate 积累” Bulletproofs，而无需以递归方式验证整个 Bulletproofs。

这一系列工作成果颇丰，最终催生出各种folding方案，如：

• Nova
• HyperNova
• ProtoStar
• ProtoGalaxy等等（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)$，并且非常昂贵。
    • 特别是，当使用大域时，FFT 计算需要大量内存。这对于快速prover来说是一个主要瓶颈。

最近，人们开始使用一种称为“Sumcheck协议”的替代协议。sumcheck协议最初于 1992 年作为纯理论成果发表（见1992年论文《Algebraic Methods for Interactive Proof Systems》），现在sumcheck协议，重新成为单变量 SNARKs 的主要痛点之一的解决方案：

• 不再需要计算商多项式。
• 相反，prover使用多线性多项式对witness进行编码，并与verifier进行$O(\log n)$轮交互以“fold”（注意：与“folding方案”中的“fold”不同，更像 Bulletproofs 和 FRI中的“fold”）这些多项式。
  • 这意味着，其它条件相同的情况下，sumcheck-based proof 通常比单变量proof更大，但可以在线性时间内证明，且内存要求更低。

一些sumcheck-based SNARKs 包括：

• Spartan
• HyperPlonk
• Honk

从某种意义上说，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)$的总工作量。

通过改变用于实例化 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$是这些值之一，则要简单得多。

• 这正是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.