Binary GKR：开创Keccak零知识证明新纪元，性能提升5.7倍

原文作者：Weikeng Chen

以太坊虚拟机（EVM）中，Keccak 哈希函数在状态树（Merkle Patricia Trees）的构造与验证过程中占据主导地位，成为零知识证明的主要计算瓶颈。针对这一长期未解的技术难题，Polyhedra 团队推出了一款全新的高性能证明系统——Binary GKR。

核心进展：将Keccak证明速度提升至全新高度

Binary GKR 系统实现了迄今为止最快的 Keccak 零知识证明性能，相比现有最优二进制证明系统 FRI-Binius 提速约 5.7 倍。这一突破不仅在技术理论上具有重要意义，更为实际应用场景提供了更强的性能支持。

应用前景：zkEVM 的“加速引擎”

Binary GKR 可作为多种 zkEVM 架构中的“加速引擎”，高效处理以太坊状态树中的大量 Keccak 运算，从而显著降低证明成本并提升系统吞吐量与响应速度。Polyhedra 团队将持续推动 Binary GKR 的产品化与开源进程，为以太坊及更广泛的生态系统提供升级支持。

Keccak：零知识以太坊的“终极挑战”

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

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

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

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

Keccak 被广泛用于构建以太坊的 Merkle Patricia Tree，以哈希形式记录全链状态。其底层运算基于位运算（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 轮。

过往尝试：Groth 16、查找表与 Binius

在 Binary GKR 出现之前，业界曾尝试多种方法优化 Keccak 的零知识证明性能：

• Groth 16 或其他 R 1 CS 系统：通过将每个位表示为 0 或 1，并使用算术关系模拟逻辑运算，但在 GPU 上生成单次 Keccak 证明仍需 30-40 毫秒，CPU 则需要 450 毫秒。

• 基于查找表的证明系统：通过对数据进行批量处理并通过查找表执行位运算，可大幅减少约束数量，但查找表本身的调用和管理开销可能抵消其优势。

• Binius：通过使用二进制域上的多项式承诺方案，Binius 显著提升了 Keccak 的证明效率。例如，在处理 8192 次 Keccak 运算时，Binius 仅需 12.35 秒，但仍存在进一步优化的空间。

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

Polyhedra 团队推出的 Binary GKR 是一个专为二进制操作高效证明设计的框架，特别适用于像 Keccak 这样以位运算为核心的函数。其核心技术优势包括以下三项：

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

Binary GKR 选择以 GKR 协议（Goldwasser–Kalai–Rothblum）为基础，利用其在处理重复性计算上的优势，大幅降低冗余开销。

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

通过采用线性码的多项式承诺方案，Binary GKR 直接在二进制域上运行，避免了使用更大数域所带来的冗余，从而显著提升性能。

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

Binary GKR 的关键创新在于通过充分利用电路结构的高稀疏性，显著提升了 GKR 协议的证明效率。预计算表可轻松放入 CPU 的 L3 缓存中，使得查表操作极为高效。

性能评估

在处理 8192 次 Keccak 调用时，Binius 生成证明耗时 12.35 秒，而 Binary GKR 仅需 2.18 秒。同时，得益于 Keccak 的结构简洁，Binary GKR 的验证时间也更短，仅为 0.035 秒，通信开销方面，证明大小为 1.052 MB。

结语

本文介绍了 Polyhedra 团队在零知识证明领域的最新进展，重点在于针对二进制函数（如 Keccak）的优化。这一成果可作为各类 zkEVM 构建的高效“辅助模块”。未来，团队计划将 Binary GKR 集成至 RISC Zero、SP 1 等 zkEVM 系统中，助力以太坊向 Layer-1 全面 SNARK 化迈进。

原文链接