递归证明里的三种压缩：Bulletproofs、Halo 与 Nova

Scope. Bulletproofs、原始 Halo 与 Nova 维护三种不同对象：inner-product relation、verification accumulator、relaxed R1CS instance。共同出现的 compression 和 folding 词汇不足以构成一条协议谱系。

路线	被压缩的对象	每轮保持的条件	典型终点
Bulletproofs / IPA	向量与内积关系	承诺和内积在折叠后仍一致	常数维内积检查
Halo	尚待完成的验证义务	新 accumulator 忠实代表旧义务与新 claim	accumulator decider
Nova	两个 relaxed R1CS instance/witness	折叠后的 relaxed equation 闭合	持续更新的 IVC state

IPA 是 Bulletproofs 和原始 Halo 的重要组件。Nova 的入口则是 relaxed R1CS 与加法同态承诺。理解三者需要分别写出各自 invariant，再讨论它们如何服务递归证明。^{1 2 3}

Bulletproofs：关系维度的压缩

上一篇多项式承诺文章已经写过 IPA 的单轮更新。这里保留与递归讨论直接相关的对象。设

\[ P=\langle \mathbf a,\mathbf G\rangle +\langle \mathbf b,\mathbf H\rangle +\langle \mathbf a,\mathbf b\rangle U. \]

prover 把向量和基底分成左右两半，发送包含交叉项的 \(L,R\)。transcript 在二者固定后给出 \(x\)，双方按 \(x,x^{-1}\) 折叠向量和基底，并更新

\[ P'=x^2L+P+x^{-2}R. \]

更新后的对象仍满足同一形状的承诺关系，维度从 \(n\) 降到 \(n/2\)：

\[ n\longrightarrow n/2\longrightarrow n/4\longrightarrow\cdots\longrightarrow1. \]

Bulletproofs 将 range-proof 等约束归约到这类内积声明，证明中每轮只增加常数个群元素，所以 proof length 随维度对数增长。这里有两条容易遗漏的边界：

• 对数级 proof length 不会自动把 verifier 的基底 MSM 降到对数复杂度；
• 一份可折叠的 relation transcript 本身不提供跨多个 proof 的递归组合。

这一层的 invariant 是“同一份内积承诺在更短向量上继续成立”。它解释 relation compression，不承担 accumulator 或 IVC state 的语义。

Halo：累积待验证义务

递归电路若逐层完整执行前一层 verifier，成本会包含 transcript、curve arithmetic、PCS openings，以及具体方案要求的其他代数检查。Halo 的 accumulator 把其中可延迟的验证义务维护成固定形状的对象。

可用一个抽象接口表示：

\[ \mathsf{Accumulate}(A_{i-1},c_i;r_i)\longrightarrow A_i, \]

其中 \(A_{i-1}\) 是旧 accumulator，\(c_i\) 是新 verification claim，\(r_i\) 是在二者承诺后产生的随机挑战。递归电路检查本轮 accumulation transition，最终由

\[ \mathsf{Decide}(A_k)=1 \]

结清累积义务。

“延迟”不等于跳过验证。每次更新都要证明三件事：

1. 旧 accumulator 进入了本轮 transcript；
2. 新 claim 的全部公开对象在挑战前固定；
3. 输出 accumulator 按协议规定的随机线性组合生成。

原始 Halo 利用 IPA-based polynomial commitment 的结构来压缩这类 opening obligations。这里的主对象是 PCS/verifier claim；Bulletproofs 中被折叠的 witness vectors 不能直接当作 Halo accumulator。

Accumulator 的失败边界

若挑战没有吸收某个 commitment，prover 可以在看到挑战后再选择该对象。若 terminal decider 没有执行，accumulator 只是一份待结清债务。若递归电路没有绑定旧 \(A_{i-1}\) 与新 \(A_i\)，每层都可能从任意状态重新开始。

因此，accumulation soundness 同时依赖承诺绑定、完整 transcript、更新关系和最终 decider。proof 数量被压缩后，这些义务仍然存在。

Accumulation 与 Folding 的对象差异

本文按对象区分这两个词：

问题	Accumulation	Folding
输入	accumulator 与新 verification claim	两个同结构 relation instances
输出	新 accumulator	一个 folded instance
保持的陈述	待验证义务被忠实合并	两个满足性问题被随机归约为一个
主要风险	漏吸收 claim、漏跑 decider	交叉项漏记、挑战顺序错误、承诺不绑定

形式化文献中的术语边界会随框架变化；上表用于避免把 Halo 的 verifier accumulation 直接等同于 Nova 的 relaxed-R1CS folding。

Nova：Relaxed R1CS 的闭合折叠

固定同一组 R1CS matrices \(A,B,C\)。一个 relaxed R1CS assignment 写成

\[ \mathbf z=(\mathbf W,\mathbf x,u), \]

并满足

\[ (A\mathbf z)\circ(B\mathbf z)=u(C\mathbf z)+\mathbf E, \]

其中 \(\circ\) 表示逐分量乘法。普通 R1CS 是 \(u=1,\mathbf E=\mathbf0\) 的特例。

现在取两个满足 relaxed relation 的对象

\[ (\mathbf z_1,u_1,\mathbf E_1),\qquad (\mathbf z_2,u_2,\mathbf E_2). \]

直接令 \(\mathbf z=\mathbf z_1+\rho\mathbf z_2\) 会产生一次交叉项。prover 先计算

\[ \begin{aligned} \mathbf T={}&(A\mathbf z_1)\circ(B\mathbf z_2) +(A\mathbf z_2)\circ(B\mathbf z_1)\\ &-u_1(C\mathbf z_2)-u_2(C\mathbf z_1), \end{aligned} \]

并在挑战产生前发送 \(\mathsf{Com}(\mathbf T)\)。transcript 随后导出 \(\rho\)，折叠结果定义为

\[ \mathbf z=\mathbf z_1+\rho\mathbf z_2, \qquad u=u_1+\rho u_2, \]\[ \mathbf E=\mathbf E_1+\rho\mathbf T+\rho^2\mathbf E_2. \]

把定义展开即可看到闭合性：

\[ \begin{aligned} &(A\mathbf z)\circ(B\mathbf z)-u(C\mathbf z)-\mathbf E\\ ={}&\bigl((A\mathbf z_1)\circ(B\mathbf z_1)-u_1C\mathbf z_1-\mathbf E_1\bigr)\\ &+\rho^2\bigl((A\mathbf z_2)\circ(B\mathbf z_2)-u_2C\mathbf z_2-\mathbf E_2\bigr)\\ &+\rho\bigl((A\mathbf z_1)\circ(B\mathbf z_2) +(A\mathbf z_2)\circ(B\mathbf z_1)\\ &\hspace{4.5em}-u_1C\mathbf z_2-u_2C\mathbf z_1-\mathbf T\bigr)\\ ={}&\mathbf0. \end{aligned} \]

前两组括号由输入 relation 消掉，最后一组由 \(\mathbf T\) 的定义消掉。relaxation scalar \(u\) 与 error vector \(\mathbf E\) 让二次 relation 对这种随机线性组合保持闭合。

承诺与挑战顺序

实际协议公开的是 witness 和 error vector 的承诺。加法同态使双方能更新

\[ \mathsf{Com}(\mathbf W) =\mathsf{Com}(\mathbf W_1)+\rho\mathsf{Com}(\mathbf W_2), \]\[ \mathsf{Com}(\mathbf E) =\mathsf{Com}(\mathbf E_1)+\rho\mathsf{Com}(\mathbf T) +\rho^2\mathsf{Com}(\mathbf E_2). \]

顺序必须是

\[ (U_1,U_2,\mathsf{Com}(\mathbf T)) \xrightarrow{\mathsf{FS}}\rho \xrightarrow{}U. \]

若 \(\rho\) 先公开，prover 可以针对它选择 \(\mathbf T\)，随机归约失去约束力。两个实例还必须共享 \(A,B,C\) 与维度；矩阵不同就没有上面的逐项展开。

这段代数证明的是 completeness 和 relation closure。soundness 还需要承诺 binding、挑战不可预测，以及 folding protocol 对坏输入形成的低度随机等式分析。一个 folded equation 单独成立，并不能在逻辑上推出两个输入各自满足；论文中的随机挑战和承诺顺序负责把作弊概率压到域大小相关的界内。

从 Folding 到 IVC

IVC 维护一条带状态连续性的计算：

\[ s_{i+1}=F(s_i,x_i). \]

每一步产生一个新的严格 R1CS step instance，再与此前的 running relaxed instance 折叠。递归 step circuit 至少要绑定：

• 旧状态 \(s_i\) 与本步输入 \(x_i\)；
• step function 的输出与新状态 \(s_{i+1}\)；
• 旧 running instance、\(\mathsf{Com}(\mathbf T)\)、挑战 \(\rho\) 和新 running instance；
• step counter、初始状态与最终公开输出。

缺少其中一条连接时，折叠等式仍可能成立，但它承载的是断裂的执行片段。Nova 系统还需要 hiding/binding commitments、Fiat–Shamir 域分离和用于结清 running instance 的 argument。folding primitive 只完成“两份 relation instance 到一份 relation instance”的随机归约。

复核三种 Invariant

读一篇递归证明设计时，可以先问三个问题：

1. 被压缩的是 witness relation、verification claim，还是 computation instance？
2. 当前轮结束后，哪个对象仍待下一轮处理？
3. 哪个 decider 或终局 argument 最终结清它？

Bulletproofs 的答案是内积承诺与常数维终点检查；Halo 的答案是 accumulator 与 decider；Nova 的答案是 running relaxed R1CS instance 与终局 argument。它们共享随机线性组合、承诺和 transcript 等工具，同时保持不同的安全陈述。

Summary

• Bulletproofs/IPA 通过 repeated halving 压缩 relation dimension。
• Halo 累积 PCS/verifier obligations，并要求最终 decider。
• Nova 用 \(u,\mathbf E,\mathbf T\) 吸收二次交叉项，使 relaxed R1CS 对 folding 闭合。
• \(\mathsf{Com}(\mathbf T)\) 必须早于 \(\rho\)，状态连续性必须显式进入 IVC step circuit。
• 代数闭合只覆盖 completeness；soundness 与 knowledge 结论还依赖承诺和随机归约分析。

下一篇讨论 zkEVM 时，这套区分会落到具体审计问题：一个 accumulator、queue 或 state commitment 究竟绑定了哪些 execution facts。

References