Merkle Tree


A Merkle tree is a data structure with unique properties which make it useful for Bitcoin. Merkle trees are used to store all transactions in a given block. The advantage of this system is that one node can easily prove to another that a given transaction was contained in a specific block. This is useful for SPV nodes and light clients, who do not store the entire blockchain and are only interested in certain transactions or blocks.

For example, if Alice runs a wallet and is waiting for her transaction to confirm, but she does not run a node, she can request a Merkle proof from Bob, who runs a full node. This proof will convince Alice that the transaction she is interested in was included in a valid block, without Bob needing to share all of the transactions or the entire block with Alice.

From a technical point of view, a Merkle tree has layers. The first layer is the list of all transaction ids (txids) in a block. To produce the second layer, these transactions are hashed using SHA-256 in pairs (two txids are concatenated). Thus, the second layer will be half as long as the first layer. This process is continued until the last layer contains exactly one hash. This is called the Merkle root. Given the properties of a hash, if a single transaction id is changed, that change will trickle up the tree and change the root hash entirely.