3 · The tree

Recap

Let's recap what is on chain after we run the SAL proof: the rerandomized enote $\tilde{O}$, its rerandomized hash point $\tilde{I}$, the auxiliary point $R$, the rerandomized amount commitment $\tilde{C}$, and the key image $L$. SAL proved two things about them: that we hold the secret keys behind $\tilde{O}$, and that $L$ is the one and only key image those secrets can produce. And it ended without confirming that $\tilde{O}$ is the disguise of a real output. I could have invented $\tilde{O}$ and the SAL proof would still pass.

The missing part

So let's write down precisely what is missing. Remember how the disguise was made: $\tilde{O}=O+r_o·T$, the enote pushed behind a random multiple of the reserved generator $T$. What we owe is exactly the reverse claim. In plain English: "the $\tilde{O}$ I published is not an invention: it is some real output $O$, already sitting on the chain, disguised behind a randomness that I know". In math terms:

We also want to prove that we know $r_i$ such that $\tilde{I}=I+r_i·U$ where $I={\mathcal{H}}_{\mathcal{p}}(O)$ is the hash to point of that same $O$ and that we know $r_c$ such that $\tilde{C}=C+r_c·G$ where $C$ is the amount commitment created next to it.

Everything therefore rests on proving "$(O,I,C)$ is on the chain". The raw material is all there, since every output ever created already sits on the chain somewhere. But "the chain" is hundreds of millions of outputs scattered across millions of transactions. Before we can prove anything about that set, we need to organize it. So let's take a step back and focus on organizing the outputs in a clever way so that it allows us to make operations with that huge set (so we can have fast and small proofs in the end), for that we will use a special kind of Merkle tree.

Every output ever made represented in just one number

Let's first start with the basic concepts. A Merkle tree is a way to represent a huge set of things by just one small value, the root. It starts by hashing every element of the set, then hashing the hashes in small groups (pairs, or threes, or any fixed width), then hashing those results in groups again, and keep going until a single hash remains: the root. The root depends on every leaf below it, so if a bit is changed anywhere, the root changes completely. If two parties agree on the 32-byte root, then they agree on the entire set.

Below is a Merkle tree of width 2 and depth 4, the classic binary choice, used here because it draws nicely. Wider trees work the same and we'll talk about them in a moment. Suppose I want to convince you that output 6 is in the tree whose root you already trust and is public:

■ the leaf I'm proving (output 6) ■ the 4 siblings I send you (s1–s4) ■ what you recompute yourself (p1–p3, root) ■ the rest of the tree: never sent, never needed

I send you exactly five things: the output itself and the four orange boxes, all the siblings per level (in this case 1), the neighbor of my path at each floor on the climb to the root. Then you rebuild the blue path from bottom up:

Start by hashing the output itself: that gives you my leaf. Then climb, one floor per 32-byte sibling: hash the leaf together with s1 and you have its parent p1. Hash p1 with s2 to get p2, then p2 with s3 to get p3 and finally p3 with s4. As you can see, four hashes later you are holding a candidate root, computed entirely by yourself.

If the final value matches the root you already had, the proof is done: I cannot fake any step without finding a SHA-256 collision (if we use SHA-256 as in this case). Note what you never saw: the 14 gray leaves, or any gray node. One sibling per level is enough to pin my leaf to the root.

Nothing forces width 2, and the recipe doesn't change with it: in a tree of width w, every node hashes w children, my path still climbs one node per level, and at each level I hand you the w − 1 siblings so you can re-hash the whole group.

What would this weigh in practice?

Stay with the binary tree and take round numbers. A tree with N leaves is ⌈log₂ N⌉ levels deep, and a proof ships one 32-byte sibling per level:

outputs N	depth ⌈log₂ N⌉	proof size
100,000,000	27	27 × 32 B = 864 B
1,000,000,000	30	30 × 32 B = 960 B

Monero currently has hundreds of millions of outputs. So that would give an idea how much it would cost if we wanted to do this naive membership proof.

The plan: build the tree in zero-knowledge

Now we understand how one could be convinced that an element belongs to a set: get the public root, receive the siblings, re-hash the leaf up to the top and compare with the root. The nodes could also maintain consensus regarding the root and the output records $(O,I,C)$ as the leaves. And this is exactly how the tree is organized in the FCMP++ era. But wait a moment, to prove that we know an enote in the tree, we can't just simply send it in the clear (obviously because everyone would know my enote!). So how could we do it? This is the issue we have to resolve now: keep the Merkle tree's logarithmic membership proof over the whole chain, but make the proof reveal nothing: not the leaf, not the path, not even a hint of the neighborhood. And the verifier must end up convinced that "some leaf of this tree is being spent, legitimately, and $\tilde{O}$ is its disguise" and learn nothing else.