Merkle tree: Definition & Examples

A Merkle tree is a tree of cryptographic hashes that commits to a collection of records in a single digest, called the Merkle root. In the ordered binary construction below, leaves represent records and each parent is computed by hashing its two child digests in left-to-right order. For a payments desk checking a Bitcoin deposit, the root in a block header lets it verify that a transaction appears in that block without downloading all the other transactions. Bitcoin white paper, §8

Follow the proof from leaf to root

To verify one record, start with its leaf hash. At each level, the proof supplies the missing sibling digest. Use the leaf index and the tree’s shape to put each sibling on the correct side, then hash the pair and move up. Compare the resulting digest with the root you already trust for that tree. A perfect binary tree with

2^k

leaves needs exactly

k

sibling digests per proof. A 4,096-leaf example therefore needs 12 digests, or 384 bytes of sibling data with SHA-256, before counting the record and proof metadata. RFC 9162, §2.1.3

A two-leaf check

Fix the tree size at two. Leaf 0 contains the raw ASCII bytes of alpha and leaf 1 contains beta. There are no quotes or newlines in either input. Let

H

mean SHA-256 and

\Vert

mean byte concatenation. Each leaf digest occupies 32 bytes, so the parent receives exactly 64 bytes.

r=H\bigl(H(\text{alpha})\Vert H(\text{beta})\bigr).

For the two-leaf proof, index 0 contains alpha and index 1 supplies the 32-byte sibling digest of beta. SHA-256 takes the 64-byte pair in left-to-right order. The candidate matches the fixed root beginning 8450e9a9.

Verification hashes the claimed leaf, inserts the supplied sibling on the right and compares the result with the independently fixed root. The diagram abbreviates hex digests.

The verifier receives the sibling digest and can check alpha without receiving beta itself. In Python, .digest() returns the raw bytes. Turning the two digests into hexadecimal strings first and hashing that text would feed SHA-256 128 ASCII bytes. Python hashlib documentation

from hashlib import sha256

expected_root = bytes.fromhex(
    "8450e9a90d144185def662fffc477da5e0325d80be5de388ec20d9c58d6c72d0"
)
right_sibling = bytes.fromhex(
    "f44e64e75f3948e9f73f8dfa94721c4ce8cbb4f265c4790c702b2d41cfbf2753"
)
left_leaf = sha256(b"alpha").digest()

candidate = sha256(left_leaf + right_sibling).digest()
print(candidate.hex())
# 8450e9a90d144185def662fffc477da5e0325d80be5de388ec20d9c58d6c72d0

print(candidate == expected_root)
# True
print(sha256(sha256(b"Alpha").digest() + right_sibling).digest() == expected_root)
# False
print(sha256(right_sibling + left_leaf).digest() == expected_root)
# False

Changing alpha to Alpha changes the claimed record. Swapping the two digests changes the byte order. Both fail against the original root. Computing a fresh root for either change would make a new commitment.

Which root are you checking?

The toy example uses one SHA-256 call at each node. Certificate Transparency v2, defined in RFC 9162, prefixes leaf inputs with the byte 0x00 and parent inputs with 0x01. This domain separation distinguishes the two input types. Bitcoin's block-header tree starts with ordered transaction IDs computed from transaction serialization that excludes witness data. It concatenates each pair of raw digests in internal byte order and applies SHA-256 twice. On a level with an odd number of nodes greater than one, Bitcoin pairs the last digest with a copy of itself. RFC 9162, §2.1.1 · Bitcoin Developer Reference · BIP 141, Transaction ID

The comparison root needs its own basis for trust. In Certificate Transparency that can be a tree head signed by a known log. In Bitcoin, a valid branch binds the transaction ID to a particular block header. Whether that block is in the accepted chain and how securely it will stay there are separate questions of blockchain transaction finality. RFC 9162, §4.10 · Bitcoin white paper, §8

A proof of reserves exercise can use the same idea for customer balances. Kraken, for example, describes how customers can check that their in-scope balances appear in the snapshot. Inclusion leaves open which other liabilities were recorded and which assets are available to meet them. Kraken verification guide PCAOB Office of the Investor Advocate, March 2023 advisory

Follow the proof from leaf to root

A two-leaf check

Which root are you checking?

Sources

Related terms

Bitcoin

Blockchain transaction finality

Proof of Reserves and Exchange Solvency