The Sparse Merkle Tree Behind Solidus State: Four Trees, 256 Levels, Rebuilt From Scratch Every Time and Then Thrown Away

What is actually there

Four trees, not one. Accounts, identifiers, credentials and validators each get their own, and their four roots are hashed together into the single state root that appears in every block header.

Each tree is 256 levels deep, which means it has room for every possible 256-bit key. A key's path is the hash of the key, read one bit per level from the most significant bit down.

How a tree with more leaves than atoms is possible

Almost every subtree is empty, and every empty subtree at a given level has the same hash.

So the empty hashes are precomputed once: the bottom one is the hash of two zero blocks, and each level up is the hash of the level below joined to itself. You only ever store the parts that are not empty, and you look up an empty sibling from the table instead of walking into nothing.

A leaf is the hash of its key path joined to the hash of its value. A parent is the hash of its two children, ordered by the path bit, so the structure is ordinary once the emptiness trick is out of the way.

The proofs are compact, and the verifier is strict

A proof does not carry 256 siblings. It carries a thirty-two-byte map with one bit per level, marking which levels have a non-empty sibling, and then only those siblings. For a tree holding a handful of entries that is a very short list.

And the verifier refuses a proof whose sibling count disagrees with its map. The comment calls it exactly what it is: no smuggled extras. That is a malleability guard somebody thought about rather than a happy accident.

The tree that produces the live root is not stored

On every root computation the node builds all four trees from scratch in memory, by scanning every entry in the corresponding column family, and then discards them.

The reason is written next to the code, and it is a good one. The stored version wrote around two hundred and fifty seven nodes per insert, so a root computation rewrote an entire tree into the database, which the comment names as the bulk of roughly a gigabyte a day of disk growth on the development network. And nothing ever read those nodes back.

So this is a considered trade, not neglect. It has a shape though: producing a root costs work proportional to the whole of state rather than to what changed. With this much state that is nothing. It is the first thing that stops being nothing.

The column family is still declared and opened, with nothing in production writing to it.

And here is the bug we shipped, because a page like this should carry it

Internal nodes used to be stored under the full key hash.

Which meant every leaf got its own private chain of 256 nodes instead of sharing the upper branches with its neighbours. The root at the end of the walk reflected only the last leaf inserted, joined all the way up through empty siblings.

So the state root was a function of whichever entry the database happened to iterate last, not of the state. The symptom in the wild was that a transfer would land and the state root would not move.

The fix is the reason the insert code canonicalises a node's path per level, zeroing the bits already consumed by the walk, so two leaves that agree from level L upward genuinely share the node at level L.

And the guard against it coming back is a test that asserts the in-memory tree and the stored one produce bit-identical roots, which is the correct shape of guard for exactly this class of defect.

None of it reaches a reader

There is no endpoint that returns a proof, so the compact proofs above are available to the node and to nobody else.

Which is the third page in a row to end in the same place: a resolution answer cannot be checked, and a light client cannot be written from outside.

The structure is not the bottleneck. The read surface is.

What you can check yourself

solidus_getBlock at two heights well apart, then compare state_root

They differ, so the field is live rather than a constant. Then look for a way to prove that any particular account, identifier or credential is underneath one of them, and notice there is none.