Curve Trees, Helios and Selene

A Merkle tree with points instead of hashes, where proving a path takes kilobytes

Merkle tree refresher

A Merkle tree hashes data in pairs (or groups), then hashes the hashes, up to a single root. To prove an element is in the tree you show the path — the siblings at each level. The path has length log n.

But we need to prove the path in zero knowledge — showing neither the leaf nor the siblings. That means encoding "computing a hash" into an arithmetic circuit and proving the circuit. Ordinary hashes (Keccak, SHA) are very expensive in such circuits: tens of thousands of constraints per hash.

The Curve Trees idea

Use a vector Pedersen commitment as the "hash":

It's a good hash for our purpose (finding a collision is as hard as discrete log), and in an arithmetic circuit it's almost free — if the numbers xᵢ are scalars of the curve the Gᵢ live on.

The problem: children are points on curve E₁, so their coordinates are elements of E₁'s base field. To use them as scalars we need a curve E₂ whose scalar field equals E₁'s base field. At the next level, the other way round. Such a pair is called a cycle of curves.

Helios and Selene

For Monero a special cycle "anchored" to Ed25519 was chosen: Ed25519 point coordinates live in the field F_p, p = 2²⁵⁵ − 19, and one curve of the cycle (Selene) has exactly this F_p as its scalar field. So leaves (coordinates of O, I, C on Ed25519) can be "hashed" directly on Selene, then Selene point coordinates on Helios, and so on, alternating.

The names come from the Greek gods of the Sun (Helios) and the Moon (Selene): two curves that "orbit" each other.

How the path is proven

For each level the prover shows not the parent point itself but its rerandomization (the point plus a random multiple of another generator), and proves in a circuit over the corresponding curve:

1. "I know the children, one of which is the rerandomized point of the previous level";
2. "these children, combined with the generators, give the (rerandomized) parent".

To check curve operations inside the circuit efficiently, divisors are used (Liam Eagen's technique): instead of step-by-step scalar multiplication, a property of a rational function on the curve is proven, which is far cheaper. See Generalized Bulletproofs and divisors.

All levels over one curve are proven by one Generalized Bulletproof, over the other — by a second one. The result is two proofs whose size grows with tree depth, i.e. logarithmically with the number of outputs.

Updating the tree

When an output passes the 10-block lock, the node adds it to the tree and recomputes the path to the root. A vector commitment updates incrementally: adding a child means adding x·Gᵢ to the parent, without recomputing the others. On a chain reorganisation, changes are rolled back.