Generalized Bulletproofs and divisors

What the tree-path proof rests on — with no trusted setup

What an "arithmetic circuit" is

Any computation can be broken into elementary steps "multiply two numbers" and "add with coefficients" in a finite field. A set of such steps is an arithmetic circuit. A zero-knowledge proof shows "I know values for all wires of the circuit such that all equations hold" without revealing the values.

In Bulletproofs the circuit is simple and fixed: "these 64 numbers are bits, and they add up to the amount". In FCMP++ it's more complex: at each tree level we must check that the chosen child is among the node's children and that the node is correctly computed from them.

Generalized Bulletproofs

Ordinary Bulletproofs take separate Pedersen commitments as input. Generalized Bulletproofs (Eagen, Kamp, Parker et al.) let you feed vector commitments into the circuit — one point fixes many numbers at once. That's exactly what the tree needs: a node's "hash" is a vector commitment to its children's coordinates (see Curve Trees). The circuit receives the node as input and can reason about its contents.

Same properties as Bulletproofs:

• no trusted setup;
• proof size grows logarithmically with circuit size;
• verification is linear in circuit size but batches well — verifying many proofs together is cheaper than one by one.

The problem: scalar multiplication inside a circuit

Rerandomization requires checking something like Õ = O + r_o·T in the circuit. Multiplying a point by a 255-bit scalar "head-on" means hundreds of point doublings and additions, each several field multiplications. That's thousands of constraints per operation, and the proof would be huge.

Divisors: check instead of compute

Liam Eagen's idea ("Zero Knowledge Proofs of Elliptic Curve Inner Products from Principal Divisors and Weil Reciprocity"): to make sure points P₁ … Pₙ sum to zero, you don't have to add them. It's enough to present a rational function f on the curve whose zeros are exactly at those points (its divisor) and check one algebraic identity at a random point (a challenge from the verifier).

The multiplication r·T is written as a sum Σ bᵢ·(2ⁱ·T) over the bits of r, i.e. as a sum of points — and is checked with one divisor. The constraint count drops by roughly an order of magnitude.

Two circuits — two curves

Tree levels alternate between Selene and Helios. Each level's arithmetic is natural in one curve's field, so the membership proof consists of two Generalized Bulletproofs: one over Selene (Selene levels and the leaf rerandomization check, whose coordinates are Ed25519 field elements), the other over Helios. They're connected through shared rerandomized nodes.

Size and cost

Proof size depends on tree depth and node width. With hundreds of millions of outputs and nodes dozens of children wide, the depth is a few levels. Roughly, one FCMP++ input takes several kilobytes, and verification is an order of magnitude costlier than CLSAG; developers keep optimising both (batch verification, multi-input proofs). Exact figures are in the benchmark reports for the release.