Merkle Tree
A structure that hashes items in pairs repeatedly until one hash represents them all, so any single item can be checked cheaply.
The leaves are hashes of individual items such as transactions, each level hashes pairs together, and the single hash at the top, the Merkle root, is placed in the block header. To prove that one transaction is in the set, a verifier needs only the sibling hashes along the path to the root, a number that grows with the logarithm of the set size rather than its size, which is what makes light clients and rollup proofs practical. Ethereum uses a Merkle-Patricia trie for its state so that balances and storage slots can be proven the same way. The structure is named after Ralph Merkle, who described it in the late 1970s, long before blockchains existed.
En pratique
Exchange proof-of-reserves attestations often publish a Merkle root so each customer can verify that their balance was included in the total that was attested.
Le malentendu courant
A Merkle proof shows that an item was included in a committed set, not that the set is complete or honest, which is why proof of inclusion is not proof of solvency.