Curve Trees、Helios 与 Selene

用点代替哈希的 Merkle 树，证明一条路径只需几 KB

Merkle 树回顾

Merkle 树把数据成对（或成组）哈希，再对这些哈希进行哈希，直到得到唯一的根。要证明某个元素在树中，你需要给出路径——每一层的兄弟节点。路径长度为 log n。

但我们需要以零知识的方式证明这条路径——既不展示叶子，也不展示兄弟节点。这意味着要把“计算哈希”编码进算术电路并证明这个电路。普通哈希（Keccak、SHA）在这种电路中开销非常大：每次哈希需要数万个约束。

Curve Trees 的思路

用向量 Pedersen 承诺作为“哈希”：

对我们的用途而言，这是一个好的哈希（找到碰撞与求解离散对数一样难），而且在算术电路中几乎不花成本——前提是数 xᵢ 是 Gᵢ 所在曲线的标量。

问题在于：子节点是曲线 E₁ 上的点，所以它们的坐标是 E₁ 基域中的元素。要把它们当作标量使用，我们需要一条曲线 E₂，其标量域等于 E₁ 的基域。到了下一层，则反过来。这样一对曲线被称为曲线循环。

Helios 与 Selene

门罗币选择了一个“锚定”在 Ed25519 上的特殊曲线循环：Ed25519 点的坐标位于域 F_p 中，p = 2²⁵⁵ − 19，而循环中的一条曲线（Selene）的标量域恰好就是这个 F_p。因此，叶子（Ed25519 上 O, I, C 的坐标）可以直接在 Selene 上“哈希”，然后 Selene 点的坐标在 Helios 上哈希，如此交替进行。

这两个名字来自希腊神话中的太阳神（赫利俄斯，Helios）和月亮女神（塞勒涅，Selene）：两条相互“环绕”的曲线。

路径如何证明

对于每一层，证明者展示的不是父节点本身，而是它的重随机化（该点加上另一个生成元的随机倍数），并在相应曲线上的电路中证明：

1. “我知道这些子节点，其中一个是上一层的重随机化点”；
2. “这些子节点与生成元组合后，得到（重随机化的）父节点”。

为了在电路中高效地检查曲线运算，使用了除子（Liam Eagen 的技术）：不再一步步地进行标量乘法，而是证明曲线上某个有理函数的一个性质，成本要低得多。见 Generalized Bulletproofs 与除子。

同一条曲线上的所有层由一个 Generalized Bulletproof 证明，另一条曲线上的则由第二个证明。最终得到两个证明，其大小随树的深度增长，也就是随输出数量按对数增长。

更新树

当一个输出度过 10 个区块的锁定期后，节点把它加入树中，并重新计算到根的路径。向量承诺可以增量更新：添加一个子节点就是给父节点加上 x·Gᵢ，无需重新计算其他部分。如果发生链重组，这些更改会被回滚。