Technical › FCMP++

Input rerandomization

How to spend an output from the tree without showing which one

In short

In FCMP++ a transaction input isn't a reference to an output but a "repainted" copy of it: a random multiple of a separate generator is added to each point of the output. The resulting points are indistinguishable from random, but the spender knows the "paint" and can prove: (1) removing it gives some leaf of the tree, and (2) they know that leaf's key.

Why rerandomize at all

A membership proof proves the statement "point X is a leaf of the tree". If we publish the output O itself, there's nothing left to hide: everyone sees which output is spent. If we publish nothing, there's nothing to tie the key image and the amount commitment to. We need the middle ground: publish something mathematically linked to the output, where only the spender can see the link.

That trick is rerandomization. In RingCT a similar trick was the pseudo-output C̃: the same amount commitment, but with a new mask. FCMP++ applies the same idea to every part of the output.

What a leaf consists of

leaf = ( O.x, I.x, C.x ) x-coordinates of three Ed25519 points: the output key O, the key image generator I = Hp(O), the commitment C

O and C come straight from the output on the chain; I is computed by the node when adding the output to the tree. Only coordinates (numbers) go into the tree, not the points themselves — that makes them easier to "hash" at the next level (see Curve Trees).

The rerandomization formulas

The spender picks four random scalars r_o, r_i, r_r_i, r_c and publishes:

Published	Formula	What it hides
Õ	`O + r_o·T`	which output key is spent
Ĩ	`I + r_i·U`	that output's key image generator
R	`r_i·V + r_r_i·T`	a commitment to `r_i` — needed to link Ĩ to the key image
C̃	`C + r_c·G`	which amount commitment is spent (like the RingCT pseudo-output)

T, U, V are fixed generators obtained by hashing to a point; nobody knows their logarithms with respect to G or each other. That's critical: if someone knew T = t·G, they could "repaint" one component into another.

What is proven about these points

The transaction carries two proofs that split the work:

The membership proof (inside an arithmetic circuit over Helios/Selene) proves: there is a leaf (O, I, C) in the tree with root ρ, and there exist r_o, r_i, r_r_i, r_c such that the published Õ, Ĩ, R, C̃ follow the formulas above.
SA+L (outside the circuit, on Ed25519) proves: the spender knows x, y with Õ = x·G + (y + r_o)·T, and the key image is L = x·I — using only the published Õ, Ĩ, R.

Note the membership proof knows nothing about spend keys, and SA+L knows nothing about the tree. This separation allows, for example, delegating the membership proof to another device without giving it the right to spend.

Why it's secure

Hiding: r_o·T is a random subgroup point, so Õ is uniformly distributed whatever O looks like. Comparing Õ with outputs is pointless — the tool shows this.
No fake leaves: to "remove the paint" from a made-up point and land on a real leaf you'd need to solve a discrete log between generators.
No amount swap: balance is checked on C̃, and the membership proof guarantees C̃ differs from the leaf's real C only by a multiple of G — so the amount is the same.
No double spend: L = x·I depends only on the output, not on r; a second spend yields the same L.