Merkle Tree
A Merkle tree is a data structure that repeatedly hashes pairs of data hashes until a single hash, the Merkle root, remains. That root acts as a compact fingerprint for a whole dataset, such as all transactions in a block.
A Merkle tree is built from the bottom up. Each piece of data, such as a transaction, is passed through a hash function to create a leaf. Pairs of hashes are then combined and hashed again, level by level, until one hash remains: the Merkle root. Bitcoin stores the Merkle root of a block's transactions in the block header. Ethereum uses a modified version, the Merkle Patricia trie, to encode its state of accounts, balances and smart contracts.
Changing any piece of data changes the root, so the root works as a tamper-evident summary of everything beneath it. This lets a lightweight wallet confirm that a transaction is in a block without downloading the whole block. It needs only the transaction, the root from the block header, and a short list of sibling hashes called a Merkle proof or Merkle path.
In a block of eight transactions, proving that one is included takes just three sibling hashes, one per level. Even with thousands of transactions, the proof stays small, because its size grows only with the logarithm of the number of items. Some exchanges also use Merkle trees in proof of reserves, so each customer can check that their balance was counted.
A common misconception is that a Merkle proof proves more than it does. It shows that data belongs to the set committed to by the root, not that the data is valid or that the root itself can be trusted. A light wallet still depends on the header being part of the accepted chain. A Merkle-based reserve proof cannot reveal liabilities that were left out.