Generalized Bulletproofs 与除子

树路径证明的基础——无需可信设置

什么是“算术电路”

任何计算都可以分解为有限域中“两数相乘”和“带系数相加”的基本步骤。这样一组步骤就是算术电路。零知识证明表明“我知道电路中所有导线的取值，使得所有方程都成立”，而不泄露这些取值。

在 Bulletproofs 中，电路简单且固定：“这 64 个数都是比特，并且加起来等于金额”。在 FCMP++ 中则更复杂：在树的每一层，都要检查所选的子节点确实在该节点的子节点之中，并且该节点是由这些子节点正确计算出来的。

Generalized Bulletproofs

普通的 Bulletproofs 以单独的 Pedersen 承诺作为输入。Generalized Bulletproofs（Eagen、Kamp、Parker 等人）允许把向量承诺输入电路——一个点同时锁定许多个数。这正是树所需要的：一个节点的“哈希”就是对其子节点坐标的向量承诺（见 Curve Trees）。电路以该节点作为输入，并可以对其内容进行推理。

与 Bulletproofs 具有相同的性质：

• 无需可信设置；
• 证明大小随电路规模按对数增长；
• 验证时间与电路规模成线性关系，但很适合批量处理——一起验证许多证明比逐个验证便宜。

问题：电路内的标量乘法

重随机化需要在电路中检查类似 Õ = O + r_o·T 的关系。“硬算”一个点乘以 255 位标量，意味着数百次点倍加和点加法，每一次又需要若干次域乘法。每个运算就是数千个约束，证明会变得极其庞大。

除子：验证而非计算

Liam Eagen 的思路（"Zero Knowledge Proofs of Elliptic Curve Inner Products from Principal Divisors and Weil Reciprocity"）：要确认点 P₁ … Pₙ 之和为零，不必真的把它们加起来。只需给出曲线上的一个有理函数 f，其零点恰好位于这些点上（即它的除子），然后在一个随机点（来自验证者的挑战）上检查一个代数恒等式即可。

乘法 r·T 按 r 的比特写成求和 Σ bᵢ·(2ⁱ·T)，即一组点之和——再用一个除子来检查。约束数量大约减少一个数量级。

两个电路——两条曲线

树的各层在 Selene 和 Helios 之间交替。每一层的算术在其中一条曲线的域上进行最为自然，因此成员证明由两个 Generalized Bulletproofs 组成：一个基于 Selene（Selene 层以及叶子的重随机化检查，叶子的坐标是 Ed25519 的域元素），另一个基于 Helios。两者通过共享的重随机化节点连接起来。

大小与开销

证明大小取决于树的深度和节点宽度。在有数亿个输出、每个节点有几十个子节点的情况下，树的深度只有几层。粗略来说，一个 FCMP++ 输入占几千字节，验证开销比 CLSAG 高一个数量级；开发者在持续优化这两方面（批量验证、多输入证明）。确切数字见发布版本的基准测试报告。