How to Build a Merkle Tree in Python to Detect Tampering Without Re-Hashing Everything

Imagine you run a small static website with 20 files. Every night you want to check that none of them were quietly modified, whether by a bad deploy, a compromised build server, or an attacker who got write access to your storage bucket. The naive way is to re-read and re-hash all 20 files every time and compare the results to yesterday’s hashes. That works, but it does not tell you which file changed without extra bookkeeping, and it gets slower in direct proportion to how much data you are protecting. A Merkle tree solves both problems at once, and by the end of this tutorial you will have built one from scratch, broken it the way an early version of Bitcoin was broken, fixed it the way Certificate Transparency actually fixes it, and used it to prove a single file belongs to a dataset without sending the dataset itself.

What a Merkle Tree Actually Solves

A cryptographic hash function takes data of any size and produces a short, fixed-length fingerprint called a digest. Change even one byte of the input and the digest comes out completely different. Two different inputs are not supposed to ever produce the same digest either (a “collision”), and you cannot work backward from a digest to recover the original input. Python’s hashlib.sha256 is one such function, and it is the only building block this tutorial needs.

A Merkle tree (named after cryptographer Ralph Merkle) takes that one idea and applies it to a whole list of things at once. You hash each item individually (these are called the leaves), then you hash pairs of those hashes together, then hash pairs of those results, and so on, until exactly one hash remains at the top: the root. That single root hash is a fingerprint of the entire list. If any leaf changes, the root changes. If nothing changes, rebuilding the tree from the same data always produces the same root.

The part that makes this genuinely useful, rather than just a slower way to hash a list, is that the tree’s internal structure lets you do two things a flat hash cannot: find exactly which leaf changed without re-hashing every other leaf, and prove that one specific leaf belongs to the set without handing over the whole set. Both of those are exactly why this data structure sits underneath git, Certificate Transparency, BitTorrent, and most blockchain implementations.

What You Will Build

Over the next several steps you will:

• Build a Merkle tree from scratch in pure Python, using only hashlib from the standard library.
• Reproduce a real, historical vulnerability class (CVE-2012-2459, which affected early versions of Bitcoin Core) inside your own code, and watch two genuinely different inputs collide on the same root hash.
• Fix it the way the IETF’s Certificate Transparency standard (RFC 6962) actually fixes it, and empirically isolate which part of the fix was doing the work.
• Write an efficient tree-diff function that finds exactly which file changed in a 20-file set using 11 hash comparisons instead of 20.
• Generate and verify Merkle inclusion proofs, the same mechanism a browser uses to confirm a certificate is really logged without downloading an entire Certificate Transparency log.
• Look at git’s own object store and confirm, with real commands, that it is built from the same core idea.

Prerequisites

• Python 3.10 or newer (this tutorial was built and tested on Python 3.13.14). Only the standard library’s hashlib module is required for the tree itself.
• pip install pytest if you want to run the test suite at the end (tested against pytest 9.1.1).
• Git installed, for the last section only (tested against Git 2.55.0).
• Comfort with basic Python functions and recursion is helpful. Recursion is explained as it comes up, so prior experience is not required.
• About 45 to 60 minutes.

One note on how to follow along: the steps below build on each other inside one running merkle.py file (plus a separate naive_merkle.py for Step 3), the same way you would build up a module interactively. Variables like files, three_leaves, and four_leaves carry forward from the step that introduces them into the ones that follow.

Step 1: Hash Each Piece of Data on Its Own

Before building any tree, get comfortable with the one operation everything else is built from: hashing a single piece of data.

import hashlib

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

# Pretend these are four small files in a deployed directory.
files = {
    "index.html": b"<h1>Welcome</h1>",
    "app.js": b"console.log('v1');",
    "style.css": b"body { margin: 0; }",
    "readme.txt": b"Build 42",
}

for name, content in files.items():
    digest = sha256(content).hex()
    print(f"{name:12s} sha256={digest}")

Running it prints one fingerprint per file:

index.html   sha256=7a6d79396a55e7b3cc2ef10a0ce5d74501e1242121de5ed35b922f6967d463d9
app.js       sha256=8083771caed3c171df740c701926d142d5d5dae18cb9de3f573018b532aa9e60
style.css    sha256=3e67b4a9505b24600272f1ce6b6776c4ae2ebde88f76559d4a2a51f602d800c4
readme.txt   sha256=28f0af4218c1142c0f307bed0c1d6a97c687ba65a98c451c52b4f640ffcb139a

That is already useful on its own (it is how tools like sha256sum work), but comparing four hashes one by one does not scale, and it still cannot prove that any single file belongs to a specific, agreed-upon set without handing over the whole set. That is where the tree comes in.

Step 2: Combine Leaf Hashes Upward Into One Root

The simplest way to combine hashes is to pair them up: hash leaf 1 and leaf 2 together, hash leaf 3 and leaf 4 together, then hash those two results together, and so on until one hash remains. That works perfectly when you have a power-of-two number of leaves (2, 4, 8, 16). Real directories almost never cooperate with that, so the tree needs a rule for handling any number of leaves, not just convenient ones.

The rule this tutorial uses is the same one Certificate Transparency’s RFC 6962 defines: given n leaves, split them at k, the largest power of two smaller than n, recursively build a tree over the first k leaves and another over the remaining n - k, then combine the two resulting hashes. A single leaf is its own base case. This never needs to invent, duplicate, or pad anything, which turns out to matter a great deal in the next step.

"""From-scratch Merkle tree matching RFC 6962's MTH definition."""
from __future__ import annotations
import hashlib
from dataclasses import dataclass, field
from typing import Optional

LEAF_PREFIX = b"\x00"
NODE_PREFIX = b"\x01"


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


@dataclass
class Node:
    digest: bytes
    start: int
    end: int
    left: Optional["Node"] = None
    right: Optional["Node"] = None

    @property
    def is_leaf(self) -> bool:
        return self.left is None


def _largest_power_of_two_less_than(n: int) -> int:
    """k such that k is a power of two and k < n."""
    k = 1
    while k * 2 < n:
        k *= 2
    return k


def build_tree(leaves: list[bytes], start: int = 0, end: int | None = None) -> Node:
    if end is None:
        end = len(leaves)
    n = end - start
    if n < 1:
        raise ValueError("cannot build a tree over zero leaves")
    if n == 1:
        digest = sha256(LEAF_PREFIX + leaves[start])
        return Node(digest=digest, start=start, end=end)
    k = _largest_power_of_two_less_than(n)
    left = build_tree(leaves, start, start + k)
    right = build_tree(leaves, start + k, end)
    digest = sha256(NODE_PREFIX + left.digest + right.digest)
    return Node(digest=digest, start=start, end=end, left=left, right=right)


def root_hash(leaves: list[bytes]) -> bytes:
    if not leaves:
        return sha256(b"")
    return build_tree(leaves).digest

Notice the LEAF_PREFIX and NODE_PREFIX bytes glued onto every hash input. Ignore them for a moment; you will see exactly why they exist in the next step. Try it against five files:

files = [
    b"index.html:v1",
    b"app.js:v1",
    b"style.css:v1",
    b"readme.txt:v1",
    b"logo.png:v1",
]

root = build_tree(files)
print("n =", len(files))
print("root =", root.digest.hex())

n = 5
root = 4c6191cc385a27248966f12ee4a4193ea7a48253aeae47202e2d8d7bf537565a

Rebuild the exact same list again and you will get the exact same root, every time. That determinism is the entire point: the root is a fingerprint of the full list’s content, not of when or how you happened to build the tree.

Step 3: A Bug That Once Threatened Bitcoin’s Block Validation

Before RFC 6962’s approach became common, a more obvious construction was popular: hash the leaves with no prefix at all, pair them up, and when a level has an odd number of hashes, just duplicate the last one so it has a partner. It looks harmless. It is not.

"""The historical, unsafe construction: plain concatenation, no domain
separation, and 'duplicate the last node' when a level has an odd count.
This mirrors the algorithm Bitcoin used before CVE-2012-2459 was fixed."""
import hashlib


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


def naive_root(leaves: list[bytes]) -> bytes:
    if not leaves:
        return sha256(b"")
    level = [sha256(leaf) for leaf in leaves]
    while len(level) > 1:
        if len(level) % 2 == 1:
            level.append(level[-1])  # hash the unbalanced element with itself
        level = [sha256(level[i] + level[i + 1]) for i in range(0, len(level), 2)]
    return level[0]

Now compare two lists that are genuinely different lengths: three items, and the same three items with the last one appearing a second time for real.

from naive_merkle import naive_root

A, B, C = b"tx-A", b"tx-B", b"tx-C"

three_leaves = [A, B, C]
four_leaves = [A, B, C, C]  # C appears twice for real this time

r3 = naive_root(three_leaves)
r4 = naive_root(four_leaves)
print("root([A,B,C])    =", r3.hex())
print("root([A,B,C,C])  =", r4.hex())
print("SAME ROOT?", r3 == r4)

root([A,B,C])    = 365d0495232b924a41ce17bec437b4dcfeaee9b38cd104d3932162cd106b784f
root([A,B,C,C])  = 365d0495232b924a41ce17bec437b4dcfeaee9b38cd104d3932162cd106b784f
SAME ROOT? True

A three-item list and a four-item list, containing meaningfully different data, produce the identical root hash. Nothing was broken about SHA-256 itself; the tree’s own construction rule made the ambiguity possible, because “duplicate the last item to balance an odd level” and “the last item genuinely appears twice” are computed exactly the same way once you throw away the original count.

This is not a hypothetical. It is CVE-2012-2459, an officially documented vulnerability in bitcoind and Bitcoin-Qt (the software that later became Bitcoin Core) before version 0.4.6, 0.5.x before 0.5.5, 0.6.0.x before 0.6.0.7, and 0.6.x before 0.6.2. Bitcoin Optech’s own technical writeup explains the concrete attack this enabled: “the attacker can modify that block by duplicating the final transaction to create a block with an identical merkle root but which is invalid,” since the duplicated transaction spends a UTXO that the original already spent. If a node saw the invalid version of the block first, it cached that block header’s hash as invalid and rejected the legitimate version from every peer afterward until the node restarted, a denial-of-service condition usable for eclipse attacks. The bug was reported in 2012, assigned a CVE, and quietly fixed without (as far as is publicly known) ever being exploited in the wild.

Step 4: Fixing It the Way Certificate Transparency Does

The build_tree function from Step 2 already avoids this. Run the identical comparison through it instead:

from merkle import root_hash

r3_fixed = root_hash(three_leaves)
r4_fixed = root_hash(four_leaves)
print("root([A,B,C])    =", r3_fixed.hex())
print("root([A,B,C,C])  =", r4_fixed.hex())
print("SAME ROOT?", r3_fixed == r4_fixed)

root([A,B,C])    = bb16c6b2cb8b02ab288f2515cb53df45a478b37611757a4f5755f7501cd09d4c
root([A,B,C,C])  = 0fdf42f043419683712a041f1d2edb78343b65a0e5add738685258022aa926fe
SAME ROOT? False

RFC 6962 defines the Merkle Tree Hash (MTH) precisely: the hash of an empty list is SHA-256(), a single entry hashes as SHA-256(0x00 || d(0)), and n > 1 entries hash as SHA-256(0x01 || MTH(D[0:k]) || MTH(D[k:n])), where k is the largest power of two smaller than n. The RFC states the reason for the leaf-versus-node prefix directly: “the hash calculations for leaves and nodes differ. This domain separation is required to give second preimage resistance.” build_tree in Step 2 is a direct implementation of that formula, which is exactly why it does not collide.

Which part of the fix actually mattered?

Two things changed between the naive version and the fixed version: the padding scheme (no more duplicating the last node) and the domain separation (the 0x00/0x01 prefixes). It is worth checking which one was actually doing the work for this specific collision, rather than assuming.

"""Which part of the fix actually matters: no-padding (power-of-two split),
domain separation (leaf/node prefixes), or both? Test them independently."""
import hashlib


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


def _k(n: int) -> int:
    k = 1
    while k * 2 < n:
        k *= 2
    return k


def build_no_padding_no_prefix(leaves: list[bytes], start: int, end: int) -> bytes:
    """Power-of-two split (no duplicate-padding), but plain concatenation
    with NO leaf/node domain separation."""
    n = end - start
    if n == 1:
        return sha256(leaves[start])
    k = _k(n)
    left = build_no_padding_no_prefix(leaves, start, start + k)
    right = build_no_padding_no_prefix(leaves, start + k, end)
    return sha256(left + right)


def root_no_prefix(leaves: list[bytes]) -> bytes:
    return build_no_padding_no_prefix(leaves, 0, len(leaves))


r3 = root_no_prefix([A, B, C])
r4 = root_no_prefix([A, B, C, C])
print("root([A,B,C])   =", r3.hex())
print("root([A,B,C,C]) =", r4.hex())
print("SAME ROOT?", r3 == r4)

root([A,B,C])   = ceacb4db92be7f4e34e49366968a3922a2ff46254bf2fd9c6e151f51bd7a832a
root([A,B,C,C]) = 365d0495232b924a41ce17bec437b4dcfeaee9b38cd104d3932162cd106b784f
SAME ROOT? False

Interesting: with no domain separation at all, just switching from “pad the odd level” to “recursively split at the nearest power of two” already breaks this specific collision, because a three-leaf list and a four-leaf list no longer get combined the same way. So for this exact attack, the padding scheme was the load-bearing fix.

Domain separation is still solving a real, distinct problem, and it is not optional in a production design. RFC 6962 calls it out specifically for second preimage resistance: without a prefix marking whether a given hash was originally a leaf or an already-combined internal node, nothing structurally stops a hash that appears as a leaf somewhere from being reinterpreted as an internal node’s combined hash somewhere else in the tree. That is a broader, more general weakness than the specific duplicate-padding bug, and it is the reason production Merkle tree implementations, including Certificate Transparency’s, use both fixes together rather than relying on either one alone.

Step 5: Finding Exactly What Changed, Without Re-Hashing Everything

Now the payoff for using an actual tree instead of a single flat hash. If you keep the tree’s internal nodes (not just its root), you can compare two trees level by level and stop descending the moment two subtrees have identical hashes, since an identical hash means nothing underneath it changed.

from merkle import build_tree, Node

# Simulate a deployed directory of 20 files. Only one changes between builds.
original = [f"file-{i:02d}.js:content-v1".encode() for i in range(20)]
modified = list(original)
modified[13] = b"file-13.js:content-v2-BUG-FIX"

tree_a = build_tree(original)
tree_b = build_tree(modified)

print("root before:", tree_a.digest.hex())
print("root after: ", tree_b.digest.hex())
print("roots differ:", tree_a.digest != tree_b.digest)
print()

comparisons = 0
changed_indexes: list[int] = []


def diff(a: Node, b: Node) -> None:
    global comparisons
    comparisons += 1
    if a.digest == b.digest:
        return  # whole subtree is identical, nothing below here changed
    if a.is_leaf:
        changed_indexes.append(a.start)
        return
    diff(a.left, b.left)
    diff(a.right, b.right)


diff(tree_a, tree_b)

print(f"hash comparisons made: {comparisons} (naive approach would re-hash all {len(original)} files)")
print("changed leaf index(es):", changed_indexes)

root before: 0db45d6506cc8b86afabbf0f83eb65ab29e6e0b549ef3b5f3c611036feef291a
root after:  866d6737f59e01da1fc31eec92f9e3c0a3e897cac88645e4886870bbdaa36a3b
roots differ: True

hash comparisons made: 11 (naive approach would re-hash all 20 files)
changed leaf index(es): [13]

Eleven comparisons instead of twenty is a modest saving at this size, but the gap widens fast: the diff walk only pays a cost proportional to the depth of the tree along the path to whatever actually changed, while re-hashing everything always costs the full file count no matter how small the change was. This is the same principle backup tools, container image layers, and CDN cache-invalidation systems lean on to avoid re-scanning an entire dataset every time something small changes.

Step 6: Proving One File Belongs, Without Sending the Whole Tree

The second capability a Merkle tree gives you: proving a specific leaf is part of a specific, already-agreed-upon root, by handing over only a small handful of sibling hashes (an “audit path” or “inclusion proof”) rather than the entire dataset. This is exactly how a browser or monitor checks that a specific certificate is really present in a Certificate Transparency log without downloading the whole log. Add these two functions to the same merkle.py file from Step 2, since they reuse its Node, sha256, LEAF_PREFIX, and NODE_PREFIX:

def generate_proof(root: Node, leaf_index: int) -> list[tuple[bytes, str]]:
    """Sibling hashes from leaf up to root, each tagged with the side the
    sibling sits on (the side you must place it on when recombining)."""
    proof: list[tuple[bytes, str]] = []

    def walk(node: Node) -> None:
        if node.is_leaf:
            return
        if leaf_index < node.left.end:
            walk(node.left)
            proof.append((node.right.digest, "right"))
        else:
            walk(node.right)
            proof.append((node.left.digest, "left"))

    walk(root)
    return proof


def verify_proof(
    leaf_data: bytes,
    leaf_index: int,
    tree_size: int,
    proof: list[tuple[bytes, str]],
    expected_root: bytes,
) -> bool:
    """Recompute the root from a leaf plus its audit path.

    leaf_index and tree_size are NOT derived from the proof itself. Per
    RFC 6962 Section 2.1.1, they must be supplied by the verifier from a
    source it independently trusts.
    """
    if not (0 <= leaf_index < tree_size):
        raise ValueError("leaf_index out of range for tree_size")
    digest = sha256(LEAF_PREFIX + leaf_data)
    for sibling_digest, side in proof:
        if side == "right":
            digest = sha256(NODE_PREFIX + digest + sibling_digest)
        else:
            digest = sha256(NODE_PREFIX + sibling_digest + digest)
    return digest == expected_root

Try it against all five files from Step 2, then deliberately try to cheat it twice:

root = build_tree(files)

for i in range(len(files)):
    proof = generate_proof(root, i)
    ok = verify_proof(files[i], i, len(files), proof, root.digest)
    print(f"leaf {i}: proof_len={len(proof)} verify={ok}")

# Tamper: verifying the WRONG content against a proof generated for leaf 0
proof0 = generate_proof(root, 0)
tampered = verify_proof(b"index.html:v1-EVIL", 0, len(files), proof0, root.digest)
print("tampered leaf 0 verify (should be False):", tampered)

# Tamper: correct leaf, correct index, but one proof hash flipped
proof0_bad = list(proof0)
bad_digest = bytearray(proof0_bad[0][0])
bad_digest[0] ^= 0xFF
proof0_bad[0] = (bytes(bad_digest), proof0_bad[0][1])
tampered_proof = verify_proof(files[0], 0, len(files), proof0_bad, root.digest)
print("tampered proof entry verify (should be False):", tampered_proof)

leaf 0: proof_len=3 verify=True
leaf 1: proof_len=3 verify=True
leaf 2: proof_len=3 verify=True
leaf 3: proof_len=3 verify=True
leaf 4: proof_len=1 verify=True
tampered leaf 0 verify (should be False): False
tampered proof entry verify (should be False): False

Leaf 4 needed only a single sibling hash to reach the root, because with 5 leaves the recursive split puts leaves 0 to 3 in one subtree and leaf 4 alone in the other, so proving leaf 4 only requires the pre-combined hash of the other four. That is the practical value of a proof: you can verify inclusion in a dataset of any size using a number of hashes proportional to the tree’s depth, not its total size.

A subtlety: the proof alone does not prove position

verify_proof requires leaf_index and tree_size as explicit arguments, and that is deliberate, not an oversight. RFC 6962 defines the audit path for “the (m+1)th input d(m), 0 <= m < n” as a function of m and n supplied to it, not something the proof format derives or guarantees on its own. In practice, that means you must already know, from a source you trust separately from whatever handed you the proof, which position and which root you are checking against. If you instead read the leaf index off the same untrusted response that handed you the proof, and you trust whatever root hash that same response claims is current, you have not verified anything: a dishonest server can satisfy its own claims about its own data every time. The guarantee only exists once the root hash and the expected position both come from somewhere independent, such as a value you pinned earlier, a value a second party cross-checked, or, in Certificate Transparency’s case, a signed tree head gossiped between multiple monitors.

Common Mistakes and Gotchas

• Padding an odd level by duplicating the last hash. This is the exact mechanism behind CVE-2012-2459. Use a split rule that never needs padding, such as the largest-power-of-two recursion this tutorial uses.
• Skipping domain separation. Even with a padding-free split, a production tree should still hash leaves and internal nodes differently, per RFC 6962’s own stated reasoning, to close off second preimage ambiguity in general, not just the one collision this tutorial reproduced.
• Trusting a root hash that arrived alongside the data you are checking. A Merkle proof only proves consistency with whatever root you check it against. If an attacker controls both the data and the root you are comparing to, the proof will happily “verify” a lie. The root has to come from somewhere independently trustworthy.
• Reading the leaf index out of the same response that supplied the proof. As shown above, position must be a trusted input, not a claimed one.
• Reaching for a fast, non-cryptographic hash (like Python’s built-in hash() or a CRC) instead of SHA-256 or another cryptographic hash. The entire security property rests on it being infeasible to find two inputs that hash the same way; a non-cryptographic hash offers no such guarantee.

Where This Idea Already Lives: git’s Object Model

You almost certainly already run a Merkle-tree-shaped structure daily. Git describes itself, in its own documentation, as “a content-addressable filesystem,” meaning every object is retrieved by the hash of its own content. A blob stores raw file content. A tree object lists filenames alongside the hashes of the blobs (or subtrees) they point to. A commit object points to one top-level tree plus its parent commit(s). Try it directly:

git init -q
git config user.email "[email protected]"
git config user.name "Demo"
echo "hello merkle" > file.txt
git add file.txt
git commit -q -m "first commit"

git cat-file -p HEAD^{tree}
git cat-file -p HEAD
git hash-object file.txt

100644 blob 469ab67d8b5d22022121299748f7015003c2c655	file.txt

tree 8e63d4f86e288a52a6b3690f43e41b437bc4fd9f
author Demo <[email protected]> 1788692285 -0400
committer Demo <[email protected]> 1788692285 -0400

first commit

469ab67d8b5d22022121299748f7015003c2c655

The blob’s hash and the hash git hash-object computes independently are identical, because both are the same operation: hash the object’s content. You can even reproduce git’s blob hash by hand, since git’s documented object format is simply "<type> <size>\0" followed by the raw content, hashed as one unit:

import hashlib
content = open('file.txt', 'rb').read()
header = f'blob {len(content)}\0'.encode()
digest = hashlib.sha1(header + content).hexdigest()
print(digest)

469ab67d8b5d22022121299748f7015003c2c655

That matches git’s own output exactly. A tree points to blobs by hash, a commit points to a tree by hash, and each parent commit is itself referenced by hash, forming the same “hash of the content below me, all the way up” chain this tutorial built by hand. Git generalizes the idea rather than using a strict binary tree: a tree object can list any number of blobs and subtrees, not just two, and a merge commit can have more than one parent, so what git actually builds is a Merkle DAG (directed acyclic graph) rather than a strictly binary Merkle tree. The core property, that changing any file changes every hash above it up to the commit, is identical.

One honest caveat: git still defaults to SHA-1 for object hashing, not SHA-256. Git has hashed with a collision-detecting implementation of SHA-1 (SHA1DC, which specifically detects the kind of crafted collision used in the 2017 SHAttered attack) by default since Git 2.13, and an experimental SHA-256 repository format has existed since Git 2.29, but it is still an opt-in format, not the default. That does not weaken anything you built in this tutorial; SHA-256 throughout is a stronger, more conservative choice than git’s own current default.

How to Confirm Everything Works End to End

Pull the pieces together into one test suite so you have a repeatable way to know the implementation is correct, not just that it looked correct once:

import pytest
from merkle import build_tree, root_hash, generate_proof, verify_proof, sha256
from naive_merkle import naive_root


def test_single_leaf_root_matches_rfc6962_formula():
    leaf = b"only-file"
    assert root_hash([leaf]) == sha256(b"\x00" + leaf)


def test_empty_root_is_hash_of_empty_string():
    assert root_hash([]) == sha256(b"")


def test_every_leaf_has_a_valid_proof():
    leaves = [f"item-{i}".encode() for i in range(13)]  # deliberately not a power of two
    root = build_tree(leaves)
    for i, leaf in enumerate(leaves):
        proof = generate_proof(root, i)
        assert verify_proof(leaf, i, len(leaves), proof, root.digest)


def test_tampered_leaf_fails_verification():
    leaves = [f"item-{i}".encode() for i in range(13)]
    root = build_tree(leaves)
    proof = generate_proof(root, 4)
    assert not verify_proof(b"item-4-TAMPERED", 4, len(leaves), proof, root.digest)


def test_naive_construction_collides_on_duplicated_last_leaf():
    a, b, c = b"tx-A", b"tx-B", b"tx-C"
    assert naive_root([a, b, c]) == naive_root([a, b, c, c])


def test_rfc6962_construction_does_not_collide():
    a, b, c = b"tx-A", b"tx-B", b"tx-C"
    assert root_hash([a, b, c]) != root_hash([a, b, c, c])


def test_out_of_range_index_is_rejected():
    leaves = [b"x", b"y", b"z"]
    root = build_tree(leaves)
    proof = generate_proof(root, 0)
    with pytest.raises(ValueError):
        verify_proof(leaves[0], 0, 0, proof, root.digest)

$ pytest test_merkle.py -v
collected 7 items

test_merkle.py::test_single_leaf_root_matches_rfc6962_formula PASSED
test_merkle.py::test_empty_root_is_hash_of_empty_string PASSED
test_merkle.py::test_every_leaf_has_a_valid_proof PASSED
test_merkle.py::test_tampered_leaf_fails_verification PASSED
test_merkle.py::test_naive_construction_collides_on_duplicated_last_leaf PASSED
test_merkle.py::test_rfc6962_construction_does_not_collide PASSED
test_merkle.py::test_out_of_range_index_is_rejected PASSED

7 passed in 0.04s

Before you consider this working end to end, confirm each of these yourself rather than taking them on faith: rebuilding the tree from unchanged data reproduces the same root; changing a single byte anywhere in any one leaf changes the root; the naive construction can collide across two different-length inputs while the RFC 6962 construction on the same inputs cannot; and every leaf’s proof verifies against the true root while failing against either a tampered leaf or a tampered proof entry.

Next Steps

A Merkle tree is one of a handful of small, composable building blocks worth having in your own toolbox rather than only inside libraries. If you want to keep going, sxz.io has related from-scratch tutorials worth pairing with this one: how to build a Bloom filter for fast, approximate set membership; how to build consistent hashing for distributing load without a full reshuffle; and, since this tutorial’s last section only scratched the surface of git internals, how to use git bisect and how to rewrite git history safely with git filter-repo both lean on the same object model you just verified by hand.