零知识证明专题第3期：证明压缩与递归聚合：从 Nova 到 Binius 的效率革命

一、引言：一张 gas 账单引发的效率觉醒

2022 年夏天，以太坊 Goerli 测试网上的一桩实验让社区感到几分沮丧。一个中等规模的 DeFi 聚合交易批次，通过当时的 PLONK 证明系统生成链上可验证的零知识证明，结果累积证明数据达到了 47 MB，链上验证所消耗的 gas 费用几乎抵消了整批交易原本能节省下来的所有成本。项目团队在论坛里发出了一张截图：左侧是"证明数据 47 MB"，右侧是"gas 费 0.18 ETH"——这笔 gas 费足以在当时的以太坊主网做十几笔普通转账。问题的本质并不在于零知识证明"没用"，而在于每一步计算都被独立地包裹进了一个完整的 SNARK，积沙成塔，最终让系统背上了沉重的验证与数据负担。

与此同时，微软研究院的 Srinivasan Setty 团队发表了一篇名为 Nova 的论文。它的核心问题异常简洁：如果有两百万步计算，为什么非要生成两百万个独立证明？有没有可能，把两个待证明的实例"折叠"成一个，只保留一条恒定大小的"证人追踪器"，等所有步骤走完后再统一做一个最终证明？这个被称为折叠方案（folding scheme）的范式，彻底改写了_incrementally verifiable computation_（IVC，增量可验证计算）的设计哲学。两年后，2024 年 Irreducible 团队发布了 Binius，又将底层证明运算从 256 位椭圆曲线域下沉到二进制塔域，让同一批计算的证明者时间再降一个数量级。从"每一步都单独证明"到"百万步折叠后再证明"，再到"证明本身在二进制上运行"——这一压缩主线条理清晰，正在把零知识系统从实验室原型推向生产级基础设施。

本期（ZKP 专题第 3 期）将沿着这条主线，系统梳理 2022—2026 年间证明压缩与递归聚合的关键技术跃迁。第 1 期搭建了全面对照的坐标系，第 2 期聚焦 zkVM 的工程生态，本期则深入证明系统本身的效率机制，回答一个核心问题：为什么主流方案在不同阶段选择了不同的压缩路线？开发者应该如何为自己的场景选型？

二、折叠方案：从松弛 R1CS 到 Nova

2.1 问题的困境

传统的 IVC 方案遵循一个朴素的流程：程序执行的第 $t$ 步产生一个计算状态，证明系统为这个状态生成一个完整性证明 $\pi_t$ ，验证者检查 $\pi_t$ 后进入第 $t+1$ 步。理论上是可行的，但工程上极其痛苦：每一步都要付出一次完整的 SNARK 证明者开销—— FFT、多项式承诺、配对计算——这些操作的代价与证明规模都和当前步的状态规模相关，长期累加后总成本随步数线性增长。对于百万步的 zkVM 执行轨迹，这种方案在服务器端也难以承受。

折叠方案的洞察在于一个看似悖论的观察：与其分别验证两个 NP 实例，不如把它们的约束关系"折叠"成一个等价的实例，只验证这个折叠实例即可。 如果两个原始实例都可满足，那么折叠后的实例也可满足；反之亦然。这样一来，每一步不再产生新的独立证明，而是将当前步的约束连同历史累积的折叠状态一起推进，最终只需一个恒定大小的折叠实例，再叠加一个最终 SNARK 压缩即可上链。

2.2 松弛 R1CS 与核心折叠协议

Nova 采用的核心代数结构是松弛 R1CS（Relaxed R1CS）。标准的 R1CS 将电路约束写成矩阵方程 $A \cdot z \circ B \cdot z = C \cdot z$ ，其中 $z$ 为证人向量。松弛版本引入了一个误差向量 $E$ 和一个标量 $u$ ，将约束改写为：

A \cdot z \circ B \cdot z = u \cdot (C \cdot z) + E

在每一步折叠时，系统持有两个实例 $(E_1, u_1, x_1, W_1)$ 和 $(E_2, u_2, x_2, W_2)$ 。验证者选取一个随机挑战 $r$ ，两个实例被折叠为：

\begin{aligned} E &= E_1 + r \cdot (A \cdot z_2 \circ B \cdot z_1 + A \cdot z_1 \circ B \cdot z_2 - C \cdot z_1 \cdot u_2 - C \cdot z_2 \cdot u_1) + r^2 \cdot E_2 \\ u &= u_1 + r \cdot u_2 \end{aligned}

证人部分也类似地通过 $r$ 线性组合。关键性质在于：折叠后的实例可满足，当且仅当两个原始实例均可满足。 验证者只需要做 $O(|C|)$ 的域运算，而无需验证两个完整的 R1CS 满足性证明。整个 IVC 链条中，验证者的总工作量是恒定的，与步数无关——这从根本上解决了传统 IVC 的可扩展性瓶颈。

2.3 折叠 vs. 累加器：概念简化

Nova 之前，累加器（accumulation scheme）是解决类似问题的先驱框架。累加器将多个证明逐步积累成一个"待验证批次"，延迟到某个 checkpoint 统一检查。折叠方案可以被理解为累加器的一个简洁特例：它不需要维护复杂的内部证明结构，而是直接用线性组合将两个实例捏合成一个新的松弛实例。这种简化让工程实现更直接，也让后续的安全分析更为透明。

flowchart LR
    subgraph 标准SNARK方案
    A1[步骤1状态] --> P1[生成证明π₁] --> V1[验证π₁]
    A2[步骤2状态] --> P2[生成证明π₂] --> V2[验证π₂]
    A3[...] --> P3[...] --> V3[...]
    end
    subgraph Nova折叠方案
    B1[实例₁] & B2[实例₂] --> F[折叠FOLD]
    F --> F1[折叠实例']
    F1 & B3[新实例₃] --> F2[折叠FOLD]
    F2 --> F3[折叠实例'']
    end
    style 标准SNARK方案 fill:#f5f5f5,stroke:#9e9e9e
    style Nova折叠方案 fill:#e8f5e9,stroke:#4caf50

图 1：标准 IVC 每一步都生成并验证独立证明，工作量随步数叠加；Nova 的折叠方案将每两个实例压缩为一个折叠实例，验证者工作量恒定。 示意图左侧展示了传统路径的线性增长困境；右侧展示了折叠如何形成一个恒定大小的"证人追踪器"，仅在最后进行一次最终压缩。

三、折叠体系的扩容：SuperNova 与 Protostar

3.1 SuperNova：非均匀电路的折叠

Nova 的原始设计假设每一步执行的是同一个统一电路——这在很多场景下并不成立。例如，一个 zkVM 可能在这一步执行加法指令，下一步执行内存读写，再下一步执行分支跳转。如果用一个包含所有可能指令的"超电路"来覆盖每一步，绝大多数门电路处于闲置状态，证明者代价按最大电路规模支付，而非实际执行路径。

SuperNova（Kothapalli, Setty, Tzialla, 2023 [2]）解决了这个问题。它允许每一步折叠一个非均匀电路实例，即每步可以有不同的指令和不同规模的约束系统。其核心思想是为每条指令维护一个独立的折叠关系，通过程序计数器（PC）在运行时动态选择当前应折叠的指令电路。代价模型从"全局电路规模"变为"单步实际执行指令的电路规模"，这意味着通用 zkVM 不必为未执行的指令支付证明代价。

在工程层面，SuperNova 为 zkVM 设计者打开了一扇门：指令集可以按真实程序行为动态扩展，而不必在一开始就硬编码一个巨型统一天电路。2024 年后，多项 zkVM 工程实践吸收了折叠范式，逐步将 IVC 框架从理论模板落地为可编译、可调试的工具链。

3.2 Protostar：将折叠推向 Plonkish 约束

Nova 的折叠原语建立在 R1CS 之上，而现代零知识系统越来越倾向于 Plonkish 约束系统——支持自定义门、查找表（lookup tables）和更高阶的算术化表达。Protostar 将折叠方案从 R1CS 推广到更广泛的约束形式，包括 Plonkish 与自定义门。它的核心贡献是证明折叠方案可以原生支持多线性多项式承诺和 Sumcheck 协议，而不仅是 R1CS 矩阵方程。

这意味着折叠层可以与 HyperPlonk、Binius 等底层证明系统更无缝地衔接——折叠负责处理"长程序的状态推进"，底层证明系统负责"最终压缩与打开证明"。两者的接口从"R1CS 实例"放宽为"多项式承诺打开的实例"，为整个栈的模块化与优化创造了空间。

3.3 折叠的工程代价

折叠方案并非零成本。首先，折叠本身不具零知识属性——折叠过程中传递的实例和误差向量如果直接公开，可能泄露中间计算细节。因此实际部署时，通常在 IVC 链条末端接一个标准的零知识 SNARK（如 Spartan、HyperPlonk），对最终的折叠实例做最后一道压缩与隐私保护。其次，折叠过程需要维持一个松弛误差向量 $E$ ，其大小与单步电路规模相当，内存占用与步数呈线性关系。对于极长程序，这条状态链的内存管理成为工程优化的重点。

graph TD
    A[程序执行轨迹：百万步] --> B[折叠层：Nova / SuperNova / Protostar]
    B --> C[折叠实例 + 误差向量]
    C --> D[最终SNARK：Spartan / HyperPlonk / STARK]
    D --> E[一次常数级验证]
    E --> F[链上结算 / 轻客户端验证]
    style B fill:#bbdefb,stroke:#1976d2
    style D fill:#fff3e0,stroke:#f57c00
    style F fill:#e8f5e9,stroke:#2e7d32

图 2：折叠方案的典型协议堆栈。 程序的长执行轨迹首先在 Nova/SuperNova 折叠层中被逐段压缩为恒定大小的折叠实例；随后由底层 SNARK（HyperPlonk、Spartan 或 STARK）对最终实例生成最终证明；验证者只需一次常数级运算即可确认整个长计算的完整性。绿色终点代表在链上或轻客户端上的最终验证。

四、递归聚合的另一条路径：证明之证明

4.1 递归 SNARK 的压缩逻辑

与折叠处理"同一程序的增量执行"不同，递归 SNARK 处理的是"批量不同陈述的统一压缩"。假设有 $N$ 个独立证明 $\pi_1, \pi_2, \ldots, \pi_N$ ，分别证明 $N$ 个不同的事务或状态转移。传统方案需要验证者检查 $N$ 个证明，时间和数据量都随 $N$ 增长。递归方案的思路是：将两个证明 $\pi_1, \pi_2$ 作为公共输入，生成一个新的证明 $\pi_{12}$ ，声明" $\pi_1$ 和 $\pi_2$ 都有效"。然后 $\pi_{12}$ 再与 $\pi_3$ 递归生成 $\pi_{123}$ ，如此迭代，最终将所有 $N$ 个证明压缩为单个证明，验证成本与 $N$ 无关。

Plonky2（Polygon Zero, 2022）是将递归 SNARK 工程化的标杆。它基于 FRI（Fast Reed-Solomon Interactive Oracle Proof）承诺，无需可信设置，在二进制 Goldilocks 域上实现极高速度的递归证明生成。FRI 的透明设置特性与递归树的结构天然契合：每一层的"验证电路"就是 FRI 验证算法本身，嵌入下一层证明的约束系统中，形成自底向上的压缩树。

4.2 折叠与递归的互补

在当前的工程实践中，折叠与递归并非二选一，而是构成一个双层压缩架构：

折叠层负责处理长程序的执行轨迹，将 $T$ 步状态推进压缩为一次最终实例；
递归/聚合层负责将多个不同来源的证明（可能是多个折叠链的终点）聚合成单个可验证证明。

例如，rollup 中的批量交易可以先在各自轨道上用折叠 IVC 处理状态机执行，再由递归树将多个轨道折叠为单个链上证明。这种"先折叠、再递归"的两层架构已在 2025—2026 年的多个生产级系统中成为标准设计。

4.3 2025—2026 年新动态：批量聚合系统

在折叠与递归之外，2025 年后出现了一批面向隐私保护批量聚合的系统，如 ZK-AMS 等。这类系统使用同态加密承诺保护单用户的证人数据，在聚合服务器上对加密的证人做批量折叠或递归处理，最终输出一个聚合证明，链上验证成本保持恒定。这类方向的重点从"压缩效率"扩展到"压缩+隐私"的双重目标，适合需要保护单用户参与明细的批量结算场景。

五、多项式承诺的下层革命：HyperPlonk

5.1 离开 FFT 的动机

折叠和递归都发生在协议的上层——它们回答"如何组合多个证明"。但证明本身的底层效率，在很大程度上取决于多项式承诺方案（PCS, Polynomial Commitment Scheme）。PlonK 及其早期变体依赖大域上的 FFT（快速傅里叶变换），其计算复杂度为 $O(n \log n)$ ，且对域的大小有严格要求（需要 $2^k$ 次本原单位根）。当电路规模达到千万门级别时，FFT 的时间与内存开销成为证明者的主要瓶颈。

另一维度是 custom gates。高阶自定义门（例如支持度为 4 或更高的约束）在单变量多项式框架下会导致承诺多项式的次数急剧上升，进一步放大 FFT 开销。而多线性多项式（multilinear polynomial）在布尔超立方体 $\{0,1\}^\ell$ 上操作，天然避免了 FFT，且支持任意阶数的算术门而不改变多项式结构——因为多线性多项式的次数始终被每个变量的次数限制为 1。

5.2 HyperPlonk 的设计

HyperPlonk（Chen, Bünz, Boneh, Zhang, 2022 [3]）将 PLONK 从单变量多项式承诺迁移到多线性多项式承诺。其核心流程如下：

算术化：将电路约束转化为在布尔超立方体上求值的多线性多项式 $f(X_1, \ldots, X_\ell)$ ，其中 $\ell = \log n$ ；
Sumcheck 协议：证明者通过 $\ell$ 轮交互，将超立方体上的求和 $\sum_{\mathbf{x} \in \{0,1\}^\ell} f(\mathbf{x}) = T$ 分解为单变量多项式序列，每轮将维度降低一维；
多线性 PCS：最终对一元多项式做承诺与打开，验证者只需一次线性时间检查。

与 PlonK 的 $O(n \log n)$ 证明者时间相比，HyperPlonk 实现了完全线性时间的证明者：算术化、Sumcheck、以及多线性 PCS 三部分均为 $O(n)$ 。对于高阶 custom gates，HyperPlonk 不需要扩大域或增加多项式次数，只需在 Sumcheck 中增加更多求和项，复杂度仍保持与电路规模线性相关。

graph LR
    A[电路约束] --> B[多线性多项式表示]
    B --> C[多线性PCS承诺]
    C --> D[Sumcheck协议：ℓ轮逐维分解]
    D --> E[最终打开证明]
    E --> F[验证者：线性时间检查]
    style C fill:#e3f2fd,stroke:#1565c0
    style F fill:#e8f5e9,stroke:#2e7d32

图 3：HyperPlonk 的技术流程。 电路约束首先被编码为定义在布尔超立方体上的多线性多项式；多线性 PCS 对该多项式做承诺；Sumcheck 协议通过逐轮降维将多变量求和转化为可验证的单变量序列；验证者的最终检查在承诺方案层面是线性时间的。

六、到底层去：Binius 与二进制塔域

6.1 字段压缩的趋势

多项式承诺的效率不仅取决于算法结构，还深深植根于底层有限域的大小。传统 SNARK 使用 256 位椭圆曲线域（如 BN254、BLS12-381），每次域乘法涉及大整数模运算，在 CPU 上代价高昂。领域优化的第一条路线是换小域：Goldilocks（64 位素数 $p = 2^{64} - 2^{32} + 1$ ）在 Plonky2 等系统中广泛应用；Mersenne31（31 位）进一步缩小。这些域仍属于大素数域，只是位数更小。

Binius 走出了另一条路：直接下沉到二元域 $\mathbb{F}_2$ （特征为 2 的域，每个元素只占 1 位），通过二进制塔域（binary tower fields）逐层构造更大的扩展域。塔域的构造方式是：从 $\mathbb{F}_2$ 出发，逐层添加不可约二次扩张 $\mathbb{F}_2 \subset \mathbb{F}_{2^2} \subset \mathbb{F}_{2^4} \subset \ldots \subset \mathbb{F}_{2^{2^k}}$ 。每一层扩张保留前一层作为子域，形成塔状包含关系。关键好处在于：在上层域的元素可以用下层的向量表示，域运算可以转化为二进制上的线性代数操作，在 CPU 上借助 SIMD 和位运算实现极高吞吐。

6.2 Binius 与 Brakedown 承诺

Binius（Irreducible 团队，2024 [5]）的技术栈由多个模块组成：

二进制塔域上的算术：所有约束求值在 $\mathbb{F}_{2^{128}}$ 或类似塔顶层域上完成，但底层运算大量使用位运算与异或；
Brakedown 多项式承诺：一种基于线性码（linear code）和张量积分解的透明设置 PCS。证明者将多项式系数编码为矩阵，利用张量积结构做分解与承诺，验证者通过哈希检查子矩阵的正确性；
FRI-Binius 优化：在 Brakedown 基础上引入 FRI 风格的折叠，进一步优化证明大小。

关键权衡在于：Binius 的证明大小大于 KZG 类承诺，更显著大于 Groth16 的 192 字节常数证明。但在证明者速度上，由于避开了椭圆曲线配对和大整数模乘，Binius 的代码路径在 CPU 上可以实现数倍乃至一个数量级的加速。其适用场景是服务器端批量证明生成——证明在服务器上高效生成，通过聚合或压缩后上链，而非在资源受限的轻客户端上直接生成。

6.3 性能口径与工程进展（2025—2026）

根据社区独立基准测试与公开工程报告，Binius 路径与 256 位 Groth16 的对比大致如下（具体数字因实现和基准场景而异，仅供参考）：

维度	256-bit Groth16	Binius / Brakedown	备注
证明者时间	基准 $1\times$	$5\times$ ~ $10\times$ 更快	依赖 SIMD 优化程度
证明大小	~192 字节	~数十 KB 到数百 KB	显著大于 SNARK
验证时间	~1.5 ms	线性于证明大小	多一次读取开销
可信设置	需要	透明设置（哈希/随机预言机）	工程便利
硬件亲和度	GPU 友好	CPU SIMD / 位运算高度友好	不同部署拓扑

上述数据来源于 2025—2026 年间 Irreducible 团队博客、Vitalik Buterin 技术评述 [5] 以及社区基准测试集合（如 zkp-benchmarks）。需要强调的是，这些数字会随具体实现（C vs Rust vs 汇编）、SIMD 指令集、以及哈希函数选择而显著波动，不应被视为绝对排名。

6.4 Plonky3 的工程视角

2024 年后，Polygon Zero 团队继续推出了 Plonky3，作为 Plonky2 的继任者。它在多项式承诺层引入了更广泛的域选择——包括 Goldilocks、Mersenne31 以及二元域——让开发者可以根据硬件拓扑和证明大小/速度权衡灵活切换底层 PCS。CSDN 等技术社区对 Brakedown 在 Plonky3 中的集成做了工程解析 [4]，指出张量积分解的内存布局对缓存友好性有显著影响，是实际优化中的关键瓶颈。

七、路线对比：三条压缩路线的选型指南

将折叠、递归与字段压缩放在一张对比表中，可以清晰看到它们的分工：

维度	折叠（Nova 系列）	递归 SNARK	字段压缩（Binius/Brakedown）
核心适用场景	长程序 IVC（状态机执行）	批量不同陈述的聚合	证明者资源受限、CPU 亲和
验证成本	最终为常数（需接 SNARK）	压缩后为常数	与承诺方案相关，通常更大
证明大小	折叠状态本身小，最终需 SNARK	递归压缩后可很小	大于 STARK，远大于 SNARK
证明者内存	与步数线性（误差向量累积）	与递归深度对数	极低（位运算+小域）
工程成熟度（2026）	高（Microsoft Nova 活跃维护）	高（Plonky2/3 生产级）	中（Irreducible/Plonky3 推进中）
最佳组合位置	长程序状态层	批量聚合层	底层证明加速层

选型逻辑：

如果你的核心问题是一个执行了百万步的状态机（zkVM、EVM 模拟），折叠层（Nova/SuperNova）是不可绕过的设计；
如果你需要将多用户的独立交易或状态证明聚合成一个链上证明，递归树是最成熟的路线；
如果你发现证明者在 CPU 上成为绝对瓶颈，且可以容忍较大的证明输出，字段压缩/Binius 提供了最激进的底层加速。

在实践中，三层往往并联出现：zkVM 的百万步轨迹由折叠层压缩，多个折叠终态由递归树聚合，递归树的叶子证明可以运行在 Binius 承诺上以加速证明者。2025—2026 年的前沿系统正朝着这种分层压缩的方向趋同。

八、结语：效率革命尚未完成

从 2022 年 Nova 的松弛 R1CS 折叠，到 2023 年 SuperNova 的非均匀电路推广，到 2024 年 Binius 的二进制塔域下沉，证明压缩的主线围绕两个核心变量展开："上层压缩什么"（折叠 / 递归 / 聚合）与 "下层用什么域运算"（256-bit 椭圆曲线 / 64-bit 素数 / 2-bit 二元域）。主网上线几年后，工程师们已逐渐认识到：不存在万能的"最快方案"，只有与场景与硬件拓扑相匹配的分层组合。随着 2025 年后更多 zkVM 进入生产部署，以及 Binius/Plonky3 在底层 PCS 上的持续优化，零知识证明的效率曲线仍在以肉眼可见的速度向右下移动——证明更快、更小、更易于部署，离成为互联网计算的默认信任层越来越近。

而这条压缩主线的下一个战场，可能已不再是"域的大小"或"折叠轮数"，而是证明生成与硬件的协同设计：专用 ASIC、GPU 流水线和 CPU SIMD 之间的取舍，将在未来几年进一步拉开不同证明系统之间的性能差距。

九、参考文献

[1] K. Setty, "Nova: Recursive Zero-Knowledge Arguments from Folding Schemes," in CRYPTO 2022. 开源实现：GitHub - microsoft/Nova.

[2] A. Kothapalli, S. Setty, I. Tzialla, "SuperNova: Proving Universal Machine Executions without Uniform Circuits," IACR ePrint 2023/819.

[3] B. Chen, B. Bünz, D. Boneh, Z. Zhang, "HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates," IACR ePrint 2022/1355.

[4] 技术社区综述, "Plonky3 和 Binius 中的 Brakedown 多项式承诺解析及优化," CSDN, June 2024.

[5] B. Diamond, P. Haböck, 等（Irreducible 团队）, "Binius: SNARKs over Binary Towers," 2024. 参见 irreducible.com/posts 与 Vitalik 技术评述.

[6] J. Thaler, "Proofs, Arguments, and Zero-Knowledge（教科书草稿）," 2024. 有关 Sumcheck、多线性多项式与证明组合的章节。

[7] Polygon Zero 团队, "Plonky2: Fast Recursive SNARKs," 2022. GitHub: 0xPolygonZero/plonky2.

（注：本文中引用的数学公式和示例为教学用途编写，代码片段（如有）均为概念演示，非审计级安全实现。生产环境中的密码学代码需经过形式化审计与同行评审。部分 2025—2026 年的技术演进来源于工程社区公开发表与开源实现状态，未全部定型为同行评审学术论文，本文以技术综述与工程报告口径为准。）