Merkle Tree

What it is. A Merkle tree is a way to fingerprint a large set of data with a single short hash, while still being able to prove that any one piece of it belongs to the set, without handing over the whole set.

You build one bottom-up: hash each piece of data (a "leaf"). Pair up the leaf hashes and hash each pair together, forming the next layer up. Keep pairing and hashing until only one hash remains, the "root." That root is a fingerprint of everything below it: change a single leaf, anywhere in the tree, and the root changes too.

The useful trick is the inclusion proof. To prove "this one piece of data is part of the set behind this root," you don't send the whole set: you send just the handful of sibling hashes along the path from your leaf up to the root (for a million leaves, that's about 20 hashes, not a million). Anyone can recompute the path and check it matches the known root.

Who built it. Ralph Merkle described the construction in his 1979 Stanford work on hash-based digital signatures, and patented it the same year. It quietly became one of the most reused ideas in computing: Certificate Transparency logs use it to make CA misissuance publicly auditable, git uses a close cousin of it for every commit, and Bitcoin's 2008 design put a Merkle root of all transactions into every block header. The pattern nearly every blockchain since has copied.

How Solidus uses it. This is testnet-grade and unaudited. Solidus's chain commits one hash of its entire account/DID/credential/validator state into every block header, so a client can verify a specific balance or DID document is really part of the chain's current state without downloading all of it. The specific data structure Solidus actually runs is a Sparse Merkle Tree: a variant covering the full key space rather than just the leaves you happen to have (see that entry for what that buys you).

Worth telling honestly: an earlier build of this code had a real bug. The state-root function rewrote the entire tree into RocksDB on every block, including blocks with no transactions in them at all, writing roughly 257 tree nodes and several megabytes of write-ahead log per block, into a column family nothing ever read back. Combined with an unthrottled block proposer producing empty blocks nonstop, that drove the node's disk usage up by an estimated 1.16 GB/day. The fix was to make the proposer event-driven and switch to an in-memory tree that recomputes only the paths actually touched by a block, verified to produce bit-identical roots to the old approach. Measured after the fix: CPU load around 0.2%, and +50 MB of disk growth on the first night (including two seed runs), that single measurement, not an extrapolated daily rate.

Check it yourself. The fix and the bug it replaced are both described, with numbers, in the doc comment at crates/solidus-state/src/executor.rs in the public github.com/solidusnetwork/protocol repository.