Merkle root

A merkle root is one 32-byte hash that stands for every transaction in a block. The miner stores it in the block header. If any transaction in the block changes, the root no longer matches, and the block is invalid. In that sense, the merkle root ties the header to the transactions it describes.

How is a merkle root built?

You build the root from the transaction IDs, which are the txids of the transactions. Hash them in pairs, level by level, until only one hash is left:

1. Take the txids in their order inside the block.
2. Join each pair, then run the joined bytes through HASH256, which is SHA-256 applied twice.
3. If an item is left over with no partner, hash it with itself.
4. Repeat steps 2 and 3 on the new list until one hash remains.

What does a four-transaction example look like?

Block 100,000 holds four transactions, so it makes a small and checkable example. Its txids, in explorer order, are:

8c14f0db3df150123e6f3dbbf30f8b955a8249b62ac1d1ff16284aefa3d06d87
fff2525b8931402dd09222c50775608f75787bd2b87e56995a7bdd30f79702c4
6359f0868171b1d194cbee1af2f16ea598ae8fad666d9b012c8ed2b79a236ec4
e9a66845e05d5abc0ad04ec80f774a7e585c6e8db975962d069a522137b80c1d

Pair the first two and the last two. Hashing the first pair gives ccdafb73d8dcd0173d5d5c3c9a0770d0b3953db889dab99ef05b1907518cb815. Hashing the second pair gives 8e30899078ca1813be036a073bbf80b86cdddde1c96e9e9c99e9e3782df4ae49. Hash those two together, and the merkle root is f3e94742aca4b5ef85488dc37c06c3282295ffec960994b2c0d5ac2a25a95766, which matches block 100,000's header. Both pair hashes are shown in explorer order here.

The code below does the same steps for any list of txids:

import hashlib

def hash256(data: bytes) -> bytes:
    return hashlib.sha256(hashlib.sha256(data).digest()).digest()

def merkle_root(txids: list[str]) -> str:
    # Explorer order in, natural byte order while hashing, explorer order out.
    level = [bytes.fromhex(t)[::-1] for t in txids]
    while len(level) > 1:
        if len(level) % 2:              # odd count: hash the last item with itself
            level.append(level[-1])
        level = [hash256(level[i] + level[i + 1]) for i in range(0, len(level), 2)]
    return level[0][::-1].hex()

txids = [
    "8c14f0db3df150123e6f3dbbf30f8b955a8249b62ac1d1ff16284aefa3d06d87",
    "fff2525b8931402dd09222c50775608f75787bd2b87e56995a7bdd30f79702c4",
    "6359f0868171b1d194cbee1af2f16ea598ae8fad666d9b012c8ed2b79a236ec4",
    "e9a66845e05d5abc0ad04ec80f774a7e585c6e8db975962d069a522137b80c1d",
]
print(merkle_root(txids))  # f3e94742aca4b5ef85488dc37c06c3282295ffec960994b2c0d5ac2a25a95766

Two byte orders are in play, and mixing them up is the most common mistake. Txids are shown in explorer order, but they must be reversed into natural order before hashing. The root comes out in natural order, and you reverse it again to compare it with an explorer. The byte order page covers the rule.

A block with a single transaction has a merkle root equal to that transaction's txid. No pairing is needed.

Why not hash all the transactions at once?

You could hash every txid in one long string. That also gives a fingerprint, but it proves nothing about one transaction without the rest. To check that one transaction is in the block, you would need every other txid as well.

A tree solves that. To prove one transaction is inside the block, you only need the sibling hashes along its path to the root. That path is called a merkle proof. Each step pairs the current hash with one sibling, on the left or the right, and hashes them together.

Block 562,943 holds 2,352 transactions. Here is the merkle proof that transaction f66f6ab609d242edf266782139ddd6214777c4e5080f017d15cb9aa431dda351 is in it. The transaction page in our explorer shows which block holds it. The sibling hashes below are in natural byte order, as they come out of the hash function:

50ba87bdd484f07c8c55f76a22982f987c0465fdc345381b4634a70dc0ea0b38 left
96b8787b1e3abed802cff132c891c2e511edd200b08baa9eb7d8942d7c5423c6 right
65e5a4862b807c83b588e0f4122d4ca2d46691d17a1ec1ebce4485dccc3380d4 left
1ee9441ddde02f8ffb910613cd509adbc21282c6e34728599f3ae75e972fb815 left
ec950fc02f71fc06ed71afa4d2c49fcba04777f353a001b0bba9924c63cfe712 left
5d874040a77de7182f7a68bf47c02898f519cb3b58092b79fa2cff614a0f4d50 left
0a1c958af3e30ad07f659f44f708f8648452d1427463637b9039e5b721699615 left
d94d24d2dcaac111f5f638983122b0e55a91aeb999e0e4d58e0952fa346a1711 left
c4709bc9f860e5dff01b5fc7b53fb9deecc622214aba710d495bccc7f860af4a left
d4ed5f5e4334c0a4ccce6f706f3c9139ac0f6d2af3343ad3fae5a02fee8df542 left
b5aed07505677c8b1c6703742f4558e993d7984dc03d2121d3712d81ee067351 left
f9a14bf211c857f61ff9a1de95fc902faebff67c5d4898da8f48c9d306f1f80f left

Start from the txid, reversed into natural byte order, and hash it with each sibling in turn. Each line says whether the sibling sits on the left or the right, so you join the two byte strings in that order. After the twelfth step you should land on the block's merkle root, 17663ab10c2e13d92dccb4514b05b18815f5f38af1f21e06931c71d62b36d8af, in explorer order.

Twelve siblings cover 2,352 transactions, because 2 to the power of 12 is 4,096. Proving one transaction takes 12 × 32 = 384 bytes. Listing all 2,352 txids would take 2,352 × 32 = 75,264 bytes.

Why does this help light wallets?

A full node keeps every block. A light wallet keeps only the 80-byte headers, and it asks a full node for the merkle proof of each transaction it cares about. It checks the proof against the root in the header. That way it confirms a payment is in a block without downloading the block. For what a full node keeps, see the node page.

Does the root protect against changes?

Yes. The root commits to the exact list of transactions. Change one transaction, add one, or reorder the list, and the root changes. The header then names a different root, so its hash changes too.

Because an odd item is hashed with itself, two different lists can produce the same root. A list that ends in a copy of its last transaction looks like the list without that copy. This flaw is known as CVE-2012-2459. Bitcoin Core checks for it and rejects a block that shows the pattern, with the reason bad-txns-duplicate (validation.cpp).

What comes next?

Next is time, the field the miner sets to the current time.