Flock：让证明逼近计算极限的哈希SNARK系统 | BitMart 币市资讯

证明的开销远高于计算开销

简洁的非交互式知识论证 (SNARK) 允许不受信任的一方通过提交一份小型收据来证明他们正确完成了某项计算，任何人只需花费重新计算所需时间的一小部分即可验证该收据。

但证明是有代价的：生成证明比单纯执行计算更昂贵。没有一个统一的衡量标准来量化这种代价，不同指标在细节上可能不一致，但在结论上是统一的——开销非常巨大。

那么，问题在于，证明实际上需要做到多小？

正如 Justin Thaler 所阐述的，对于最先进的 zkVM 而言，证明一项计算的成本可能比单纯执行计算高出一万到一百万倍。尽管听起来如此高昂，但就在几年前，证明通用计算在任何速度下都几乎不可行。得益于工程和研究的飞跃，开销已稳步下降。

Flock 是降低证明成本的又一个持续进展。

Flock：低开销的标准哈希证明

Flock 是一个用于证明批量布尔运算的 SNARK，与 Benedikt Bünz (Espresso, NYU) 和 William Wang (NYU) 共同开发。

专注于布尔运算已经与大多数 SNARK 的工作方式不同，后者原生用于证明大素数域上的算术运算。Flock 直接基于布尔电路运作——即构成真实计算和标准密码学的比特级 AND 和 XOR 操作。我们特别针对实践中占据主导的工作负载：大批量的标准密码哈希函数，例如 Keccak、SHA-256 和 BLAKE3。

在 Apple M4 Max 的单核上，Flock 证明标准哈希函数的成本不到计算它们成本的 250 倍。这测量的是挂钟时间，这是一个依赖于底层硬件和一些测量选择的棘手指标。首先，原生基线未使用 Apple 专用的 SHA-256 和 SHA-3 指令。它们只加速这些特定函数，但不适用于其他布尔运算。其次，原生哈希是逐一执行的，这使得利用 SIMD 更加困难。

确切数字也因哈希而异。大约 SHA-256 为 170 倍，Keccak 为 245 倍。尽管存在这些注意事项，我们发现证明标准哈希的成本仅比计算它高出几百倍，这令人震惊。具体而言，在单核上，Flock 证明：

每秒 82,100 次 BLAKE3 压缩，
每秒 42,100 次 SHA-256 压缩，
每秒 30,700 次 Keccak-f[1600] 排列。

该实现可以轻松并行化：在十核上，BLAKE3 吞吐量超过每秒 660,000 次压缩。

据我们所知，Flock 是每种标准哈希最快的证明器：

对于 SHA-256，比之前最先进的 Binius64 快约 8.4 倍。
对于 BLAKE3，比 Binius64 和 Plonky3 都快约 14 倍。
对于 Keccak，单核上比 Hashcaster 快约 1.8 倍（多线程约 4 倍）。

基于素数域和群的系统远远落后：Flock 比 Plonky3 快约 10–40 倍，比 Spartan 快数百倍。

与通用 zkVM 相比，差距急剧扩大，后者相比原生执行慢四个到六个数量级。Flock 完全放弃了通用性，证明批量固定布尔电路而非任意程序。对于许多以标准哈希为主导的应用来说，这是一个非常值得的权衡。此外，我们相信 Flock 背后的想法最终可以应用到 zkVM 中。

为什么是布尔、标准、批量？

剥离任何在生产环境中运行的 SNARK，审视其时间主要消耗在哪里，最终都会发现同样的东西：一遍又一遍评估的密码学哈希。哈希是实际运行系统的主力，因此重要的目标是证明批量哈希，并且要快。这就是 Flock 的构建目的。从这个目标出发，产生了三个设计选择：布尔电路模型、标准化哈希函数和批量证明。

为什么是布尔电路。 SNARK 构造依赖于深厚的数学结构，其原生运算通常是大素数域上的算术。模拟非原生运算（例如任何位级操作）会带来高昂的代价。标准密码哈希并非为 SNARK 友好性而设计。它们本质上是位操作原语，迫使它们通过素数域 SNARK 处理正是代价最高的情况。相比之下，将它们表示为布尔电路则非常简单。更好的是，使计算运行成本低的原因——更少的位操作——也是使 Flock 证明成本低的原因。在优化原生代码上已经付出的努力直接传递到证明器中。

为什么是标准哈希，而不是"SNARK 友好型"哈希。 许多 SNARK 文献倾向于使用与证明系统共同设计的哈希函数——Poseidon、Rescue、MiMC——选择它们正是因为证明成本低。但这也带来了两个问题。

安全性：这些设计远不如 SHA-256、Keccak 或 BLAKE3 经过实战检验，其强烈的代数结构一再为攻击打开大门。

锁定效应：一个 SNARK 友好的哈希只有在基于其设计的某个域构建的证明系统内才廉价。它实际上固化在该域上。如果证明系统被替换或在不同域上组合，效率优势就会消失，迫使应用设计者面临虚假选择：为证明器优化哈希，并在每次原生运行哈希时付出代价；或者为原生速度优化，并在证明器中付出代价。

针对标准哈希消除了这种选择。哈希由应用固定，无论是否生成证明，其运行方式完全相同，因此唯一剩下的问题是如何廉价地证明它。

为什么是批量。 最后的选择是证明一个批次——同一电路的许多独立运行——而不是一个任意计算。这听起来像是一个限制，但实际上非常务实：典型的 SNARK 应用将其绝大部分时间花费在证明大量哈希的正确性上。批处理还通过规避昂贵的置换和内存检查机制，使证明器保持快速，系统保持简单，并使验证者的工作始终与单个实例绑定，即使批次增长到数百万规模。

内部原理

我们的出发点是关于"证明速度接近计算速度"的一系列工作（RR24，RR25，HR22，ARR25），这些工作表明重复的布尔运算可以以几乎与运行相同的速度被证明。Flock 依赖于二进制域，而不是大多数其他项目中使用的更流行的素数阶域。虽然二进制域此前已在这些理论工作中被使用，但其卓越的实用性是由 Binius 系列工作（Binius，Binius64）首次展示的；特别是，Flock 依赖于它们优雅的环切换技术。

相当一部分加速来自非常简单的设计选择：(1) 二进制域，(2) 批量设置，(3) 使用 R1CS 减少见证大小。这些选择剥离了其他证明系统所付出的大部分开销，并将内部机制集中到单个瓶颈上：一个用于检查位向量逻辑 AND 的简单 zerocheck 协议。一旦 zerocheck 被孤立为唯一值得攻击的目标，回报就会非常巨大。延续优化 sumcheck 协议的工作线，Flock 引入了全新想法，显著加速了比特 zerocheck 协议。

然而值得注意的是，Flock 是一个研究原型，我们尚不推荐将其用于生产环境。存在一些重要的限制，论文中详细讨论了这些限制。

面向后量子的哈希签名

上述吞吐量可以转化为实际的应用级别速率。我们最感兴趣的是后量子迁移。

足够大的量子计算机会破坏目前保护几乎所有区块链的椭圆曲线签名。最保守、最受信任的替代方案是哈希签名（Lamport、Winternitz、XMSS）——这些方案的安全性完全依赖于哈希函数本身，其成本几乎全部是哈希运算。验证一个签名需要几百次哈希评估；验证并聚合一个区块中的数千个签名正是 Flock 为之构建的批量哈希工作负载。

以太坊基金会正在设计的 Lean VM（leanvm）专门用于通过 SNARK 进行后量子迁移，其中哈希是其主导成本。在以太坊量子迁移提议的多签名方案中，单个签名大约需要 160 次哈希调用（DKKW25）。以 BLAKE3 实例化，Flock 的十核吞吐量达到每秒 660,000 次压缩，足以证明大约每秒 4,000 笔交易的哈希量——轻松超过 Vitalik Buterin 估计的（Buterin）每秒 200,000 次哈希即可满足后量子以太坊的需求。比特币更为保守，可能采用基于 SHA-256 的签名；在这种情况下，Flock 可以在消费级硬件上在不到 3 秒的时间内证明 5,000 个签名（即一个完整区块）的哈希量。这些数字仅计算签名验证内部的哈希——这是主导成本，但并非整个交易。