Merkle Tree

Your wallet says a payment was included in a block. How can you check without downloading the entire contents? This is where a Merkle Tree helps. Transactions are first represented by hashes: short cryptographic fingerprints. These are combined step by step into one shared fingerprint, the root. The block header contains this Merkle root, linking the block to its transactions. The root is not an archive from which every payment can be read back; it is used to verify data you are given. [1] [2]

Imagine four transactions labelled A, B, C and D. Take their fingerprints, join A with B and calculate a new hash AB from the pair. Do the same with C and D to get CD. Finally, combine the AB and CD fingerprints and calculate the root. Here the letters just label transactions and intermediate results; they are not actual hashes. The process resembles an upside-down tree: many leaves come together through branches into one root. More transactions add more levels, but the principle stays the same. [3]

To verify transaction B, you have its data and calculate its fingerprint. You only need the fingerprint of A and the combined fingerprint CD, along with their correct order. Use A and B to build AB, then AB and CD to calculate the root and compare it with the header’s root. This supporting path is called a Merkle proof. You do not need the contents of A, C or D. In a balanced tree of 1024 transactions, the path has 10 sibling hashes. As the block grows, the proof therefore grows much more slowly than the full transaction list. [2] [3]

A proof matching the root does not mean you can blindly trust the supplied header. You also need to check its Proof of Work: does the mining result meet the required difficulty? The header must also connect to the appropriate chain. Even then, a Merkle proof does not check every signature and every rule for all transactions in the block. A Full Node does that. Simplified Payment Verification, or SPV, described in the whitepaper therefore has different security assumptions from full validation. A reorganization can also move the block out of the active branch: its contents are still provable, but the payment’s place in the current history may change. [2]

In Bitcoin’s ordinary tree, leaves are txid identifiers in block transaction order, starting with the Coinbase Transaction, the special transaction through which the miner claims the block reward. Pairs are joined as bytes and hashed twice using SHA-256. If a level ends with an unpaired hash, it is duplicated for this calculation; no extra payment is created. For a single transaction, its txid is itself the root. This duplication requires careful checks for duplicates in the implementation. The SegWit protocol upgrade also separates witness data, such as signatures. Another cryptographic fingerprint, stored in the Coinbase Transaction, links this data to the block. This fingerprint is called the witness commitment. The ordinary txid tree and the witness tree must therefore not be confused. [3] [4]