正文

Binary GKR：刷新Keccak证明速度记录的全新零知识证明系统

星球日报2025-05-23 04:50:11

原文作者：Weikeng Chen

在以太坊虚拟机（EVM）中，Keccak 哈希函数广泛用于状态树（Merkle Patricia Trees）的构造与验证，占据了零知识证明中的主要计算开销。如何高效地对 Keccak 进行证明，是零知识证明领域长期未解的技术难题。

为应对这一挑战，Polyhedra 团队推出了 Binary GKR——一种专为 Keccak 及其他二进制操作设计的高性能证明系统。

核心进展：对 Keccak 的证明速度提升 5.7 倍

Binary GKR 实现了迄今为止最快的 Keccak 零知识证明性能，相比现有二进制证明系统最优解 FRI-Binius 提速约 5.7 倍。这一突破不仅在理论上具有重要意义，也为实际应用打开了新的可能性。

应用前景：zkEVM 的“通用加速侧车”

我们认为，Binary GKR 可作为多种 zkEVM 架构中的“通用加速侧车”，高效处理 Ethereum 状态树中大量的 Keccak 运算，从而显著降低证明成本、提升系统吞吐与响应速度。

Polyhedra 将持续推动 Binary GKR 的产品化与开源进程，赋能以太坊及更广泛生态中的 zk 架构升级。

Keccak：零知识以太坊的“圣杯”

以太坊正逐步向零知识证明原生的 Layer-1 演进。由 21 个团队参与、涵盖 22 种 ZK(E)VM 实现的 Ethproofs 计划，正在尝试对以太坊历史区块进行完整证明，迈出关键一步。

Binary GKR：刷新Keccak证明速度记录的全新零知识证明系统

在 Ethproofs 官网上可以实时查看多个团队的进展：ZkCloud、Succinct、Snarkify 和 ZKM 等项目，已开始持续提交最新区块的 ZK 证明。这一趋势的最终目标，是将以太坊打造为以零知识证明驱动的执行层，而共识层仅需完成交易列表的提议等轻量任务。

zkEVM 架构面临的最大挑战：Keccak 的证明效率瓶颈

目前已有多个以太坊兼容 zkRollup 项目（如 Polygon、Taiko、Scroll）尝试实现 zkEVM。然而，传统 EVM 中一些在 CPU 上高效的操作，在零知识证明系统中却代价高昂。其中最主要的性能瓶颈，正是 Keccak 哈希函数。

Keccak 被广泛用于构建以太坊的 Merkle Patricia Tree，以哈希形式记录全链状态。然而 Keccak 的底层运算基于位运算（bit-level operations），这与大多数 ZK 系统使用的素数域（prime field）运算模型并不兼容，从而导致性能显著下降。

为了帮助理解 Keccak 哈希函数为何本质上是“位运算”的集合，我们在此简要展示其中的五个核心操作：θ（theta）、ρ（rho）、π（pi）、χ（chi）和 ι（iota）。这些操作应用于一个 5 × 5 的矩阵结构，每个单元格为一个 64 位整数，我们称之为“字”（word）。整个矩阵共包含 5 行 5 列。

θ（Theta）：首先计算每一列的奇偶校验值（ parity ），然后将该奇偶值与左侧相邻列进行异或运算（exclusive-or）；同时，对右侧相邻列执行一次左旋转（rotate-left）后，再进行异或。这一过程涉及基本的二进制操作，如“异或”与“左旋”。
ρ（Rho）：对矩阵中的每一个字按位左旋转，每个字的旋转距离不同，但均为预设的固定值。该步骤完全由“左旋”操作构成。
π（Pi）：根据固定模式重新排列矩阵中的字。由于该过程仅为位置置换，在零知识证明中通常被视为“零成本操作”。
χ（Chi）：沿每一行进行按位组合操作，每个字会与该行中其左右相邻的两个字进行组合。该操作包括“异或”、“取反”（negation）与“与”（and）。
ι（Iota）：将矩阵中第一个字与一个固定常数进行异或操作，仅涉及“异或”运算。

在零知识证明中实现 Keccak 的主要挑战，正是如何有效表示这些位级操作，尤其是在每个操作都作用于 64 位整数的前提下。这也是我们称其为 Keccak-1600 的原因——因为每一轮的状态空间为 5 × 5 × 64 = 1600 位。而这样的操作过程需重复 24 轮。

接下来，我们将简要回顾一些此前实现 Keccak 的尝试。

尝试一：基于 Groth 16 或其他 R 1 CS 的证明系统

目前最流行且最直接的方式，是使用 Groth 16 或其他 R 1 CS（Rank-1 Constraint System）证明系统来实现 Keccak。为了在 Groth 16 中表达位运算，我们将每个位表示为 0 或 1 ，并通过算术关系来模拟如下逻辑运算：

异或（exclusive-or）：使用表达式 a + b − 2 ab
取反（negation）：使用表达式 1 − a（通常可无成本地融合进其他约束中）
与（and）：使用表达式 a × b

而像“左旋”（rotate-left）和其他置换操作在 ZK 环境中通常被视为无成本操作，不需要额外约束。

根据计算，Keccak 每一轮中的约束数量如下：

θ 操作约产生 4480 个约束
ρ 与 π 操作为“零成本”
χ 操作约产生 3200 个约束
ι 操作约产生 64 个约束

因此完整的 Keccak-1600 （共 24 轮）将在 Groth 16 中产生 185, 856 个约束。

参考 Ingonyama 的 ICICLE 库中的数据，在一块 Nvidia 4090 GPU 上生成一个 Keccak 的 ZK 证明大约需要 30-40 毫秒，在 CPU 上则约为 450 毫秒。如果需要证明 8192 次 Keccak 运算，GPU 至少需要 250 至 300 秒，而 CPU 可能需要接近一小时。

尝试二：基于查找表的证明系统（Lookup-based Proof Systems）

一种更现代的优化方案是对数据进行批量处理（例如每 4 位或 8 位一组），并通过查找表来执行所有的位运算。换句话说，将每个 64 位整数切分成若干小块（例如 8 个 8 位 chunk），再使用查找表完成逻辑操作。

具体包括以下几种查找表：

异或操作查找表（XOR）：一个大小为 2 ⁸ × 2 ⁸ 的查找表，用于计算两个 8 位 chunk 的异或值。这样可以用一个约束完成 8 位异或，而不是传统的 8 个约束。

与操作查找表（AND）：同样是一个 2 ⁸ × 2 ⁸ 的查找表，用于两个 8 位 chunk 的按位与操作，节省约束的效果与 XOR 类似。

左旋操作查找表（Rotate-left）：为了处理 Keccak 中频繁出现的 rotate-left 操作，引入了多个查找表。具体为：七个大小为 2 ⁸ 的查找表，分别对应旋转距离为 8 k+ 1、 8 k+ 2 等（其中 k 为非负整数）。相较于尝试一（Attempt 1）完全不处理旋转操作，这种方式会引入额外开销——每轮大约增加 192 个约束。不过与其他部分相比，这个开销仍然相对较小。

为了实现这种系统，我们不再使用 Groth 16 ，而是更适合采用 Stwo、Plonky 3 等小域证明系统，这类系统对查找表支持更加完善。在该方案下，每次完整的 Keccak 运算大约需要 27, 264 个约束，并结合查找表的调用，可大幅减少整体约束数，相较 Groth 16 显著优化。

然而，这种优化在性能上并非绝对占优。因为查找表本身的调用和管理也会带来开销，若处理不当，可能抵消约束数量减少所带来的优势。因此，其实际运行效率在某些场景下可能不如基于 Groth 16 的实现。

尝试三：Binius

鉴于查找表（lookup）或定制门电路（customized gates）所带来的加速在实际中可能不及预期，原因在于查找本身的开销可能抵消其带来的约束优化效果，因此我们需探索其他路径来进一步提升 Keccak 的证明效率。

这正是 Keccak 被誉为“零知识圣杯”的原因所在。与之相比，早期的哈希函数如 SHA-256 和 Blake 2/3 ，虽也依赖于异或（XOR）、与（AND）等位运算，但其最大性能瓶颈源于整数加法。而整数加法在证明系统中通常通过将其拆解为多个 4-bit 块来优化，从而大幅提升性能。但 Keccak 并不涉及任何整数加法，因此这些优化策略在此处失效。

目前最前沿的解决方案是 Binius。该系统的核心思想是：既然 Keccak 完全由位运算组成，我们便可以使用以位为基本单位的证明系统来实现。这便是 Binius 的突破之处。

在 Binius 中，Keccak 被表示为在有限域 ?₂（即二元域）上的运算。由于 XOR 本质上就是 ?₂ 中的加法，因此其相关开销几乎完全消除。整体过程被构造为一系列多项式运算，位旋转操作也可在按位处理模型中轻松实现。证明成本主要集中于 χ 步中出现的 AND 门。

Binius 的基准测试显示，其在证明 8192 次 Keccak 运算时，仅需约 12.35 秒，远优于 Groth 16 （尝试一）和查找表方法（尝试二）。

Binius 是终点吗？其实并非如此。我们发现通过去除 Keccak 证明中的某些冗余部分，还有可能进一步提升约五倍的性能，超过当前的 Binius 实现。

Polyhedra 推出 Binary GKR：专为 Keccak 优化的二进制证明系统

Polyhedra 团队正在构建全新的证明系统 —— Binary GKR（详见： ePrint 2025/717 ），这是一个专门针对二进制操作高效证明的框架，特别适用于像 Keccak 这样以位运算为核心的函数。Binary GKR 的核心优势来自以下三项关键技术创新：

1. 基于 GKR 协议，优化重复计算

我们在 Binary GKR 的设计中选择以 GKR 协议（Goldwasser–Kalai–Rothblum）为基础，原因在于它能够有效降低处理重复性计算所带来的冗余开销。

在典型的 zkEVM 场景中，Keccak 往往以 "外挂证明器（sidecar prover）" 的角色出现，用于批量处理 zkEVM 所委托的大量 Keccak 运算任务。因此，我们面向的电路结构天然具有大量的重复模式，例如： 8192 次 Keccak 调用是一种常见规模。

更重要的是，Keccak 算法本身就极具重复性：

它在 5 × 5 的状态矩阵上反复执行相似的布尔操作；
整个过程包含 24 轮几乎一致的步骤；
各轮之间结构相同，仅输入状态不同。

这样的特性，使得 Keccak 成为 GKR 协议的“天然适配对象”：

Verifier 成本较低，适合高频验证场景；
Prover 可充分利用结构重复性，重用计算路径，大幅简化证明开销；
相比传统通用证明系统，在批量 Keccak 场景中具备显著性能优势。

2. 基于二进制域的多项式承诺

我们采用了一种基于线性码的多项式承诺方案，该方案直接在二进制域上运行。正如我们此前提到的，使用原生的二进制表示，使我们能够“免费”获得诸如异或（XOR）这样的操作。此外，与 Binius 的方法类似，基于二进制域的多项式承诺避免了使用更大数域所带来的冗余，这使系统在性能和效率上都得到了显著提升。

3. 用于二进制操作的预计算表

Binary GKR 论文中的关键创新在于：通过充分利用电路结构的高稀疏性，显著提升了 GKR 协议的证明效率。即使在同时处理多个比特的情况下，这种稀疏性依然得以保留。们的做法是将多个比特“打包”进 GKR 协议中的多项式中（注意：这些是中间多项式，无需进行承诺），然后直接在这些打包的数据上执行 GKR 协议的运算。

由于稀疏性仍然很高，我们可以利用预计算表，让证明者以远低于传统 GKR 协议的计算开销来生成证明。这一优化显著提升了 GKR 在处理二进制关系时的效率。

本文将重点介绍上述第三项技术优化：用于二进制操作的预计算表。