Glossary / Mining & consensus
Merkle tree
- Definition
- A merkle tree is the hash pyramid that compresses every transaction in a block down to a single 32 byte value, so any one payment can be proved without the rest.
Pair up the transaction hashes, hash each pair, and repeat until one hash is left. That single value goes in the block header, and proving a transaction belongs under it takes only the hashes along one path: eleven of them, 352 bytes, for a block holding 2,000 payments. This is why a phone wallet can check that your coins arrived without downloading the block.
How it works
A merkle tree turns a list into a pyramid by hashing neighbours together, level by level, until only one hash remains.
The leaves are the transaction ids in the order the miner placed them. Bitcoin combines each pair by concatenating the two 32 byte values and running SHA-256 over the result twice. When a level holds an odd number of entries, the last one is paired with a copy of itself, which keeps the algorithm simple and once caused real trouble: the vulnerability catalogued as CVE-2012-2459, disclosed in May 2012 and patched the same month, abused that duplication to construct a block that looked invalid to nodes even though the underlying transactions were fine.
The payoff is logarithmic. Doubling the number of transactions adds one level, not one hash per transaction. A block with 1,024 payments needs ten hashes to prove membership, 320 bytes. Four thousand and ninety six needs twelve, 384 bytes. Whoever checks the proof recomputes the path upward and compares the result with the root they already trust from the header, and there is no way to fake a path without breaking SHA-256.
None of this originates with bitcoin. Ralph Merkle described the construction in the patent application that became US 4,309,569, filed in 1979 and granted in January 1982. The whitepaper cites his work and puts the tree to two uses: pruning spent transactions from old blocks to save disk, in section 7, and letting a client verify a payment while holding only headers, in section 8.
Where you see it
Merkle trees appear anywhere a system needs to prove that one item belongs to a large set without shipping the set.
Inside bitcoin, every block header carries the top of one. A node rebuilds the tree from the transactions it received and rejects the block if the result disagrees. Bitcoin Core exposes the machinery directly: gettxoutproof produces a serialized proof that a transaction was included in a block, and verifytxoutproof checks one, which is a practical way to hand somebody evidence of a payment without giving them a wallet.
Elsewhere in bitcoin, Taproot builds a second one: the alternative spending conditions of a Taproot output are arranged as a tree, so revealing the branch you used discloses nothing about the branches you did not. Outside bitcoin, the same shape underpins Git commit history, Certificate Transparency logs that catch mis-issued web certificates, and the ZFS filesystem's data integrity checks.
For a wallet user the visible consequence is small and useful. A lightweight client that holds a few dozen megabytes of headers can confirm that your transaction is in a specific block, at a specific depth, and get a false answer only if somebody has produced valid proof of work on a fake chain, which costs real money.
Merkle tree vs merkle root
The merkle tree is the working structure; the merkle root is the one value kept afterwards. A node builds the whole pyramid in memory while validating a block and then throws it away, storing only the 32 bytes that ended up on top, because everything below can be regenerated from the transactions. When an explorer shows you a field called the merkle root, that is the survivor. Nobody stores the tree, and nobody needs to.