What is a Merkle tree?

A Merkle tree is a structure that turns a long list of data into one short fingerprint by repeatedly hashing items in pairs. In a blockchain, the items are usually transactions, and the single hash at the top is called the Merkle root. Because every transaction feeds into the root, the root stands for the whole set.

What is a Merkle tree in blockchain?

Start with a list of transactions. Each one already has an ID, which is a hash of its contents. The Bitcoin developer reference describes how bitcoin builds the tree:

• Put the transaction IDs in order, with the miner's reward transaction first.
• Join each neighboring pair and hash them together, using SHA-256 twice.
• If a row has an odd number of hashes, pair the last one with a copy of itself.
• Repeat on each new, shorter row until a single hash remains.

The result looks like an upside-down tree, with transactions as leaves and the root at the top.

What is a Merkle root?

The Merkle root is that final hash. In bitcoin it is a 32-byte field in the 80-byte block header, next to the previous block's hash, the time, the difficulty target and the nonce.

This is what makes past transactions so hard to alter. The developer guide explains that editing a transaction changes its ID, which changes every hash above it, which changes the Merkle root and so the block header. The block would then fail its proof of work, and every later block would need redoing as well.

What is a Merkle tree used for in blockchain?

Two uses stand out.

Proving a transaction is included. The white paper describes simplified payment verification, where a light wallet keeps only block headers instead of full blocks. When it needs to check a payment, it asks a full node for the Merkle branch, the short chain of hashes linking that transaction to the root in a header. The developer guide notes these hashes cannot be faked without the check failing. The method proves a transaction is in a block, but not that the transaction is valid, and a dishonest node could still hide transactions from the wallet.

Saving space. The white paper also notes that since only the root is included in the block's hash, old spent transactions can be pruned away without breaking the chain.

What is a Merkle Patricia tree?

Ethereum uses a variant called the Merkle Patricia trie. It combines a Merkle tree with a Patricia trie, a structure that stores key and value pairs efficiently by sharing common parts of their paths. ethereum.org says this lets Ethereum store account data, prove that a value exists, and compare two states just by comparing their root hashes. It hashes with Keccak-256 rather than SHA-256.

Ethereum keeps several of these tries: one global state trie for every account, a storage trie for each contract, and a transactions trie and receipts trie for every block. Each block header records the state, transactions and receipts roots.