Commentary: merkle-tree

A valid inclusion proof for a block that was never in the file — forged with two concatenations and a list slice, no cryptography. A study guide for merkle.py.

cd merkle-tree
python3 demo.py         # the aha (§6)
python3 test_merkle.py  # pins the two failures this page describes

1. Orientation

This toy implements two Merkle trees side by side — the naive one you get from the usual whiteboard explanation ("hash the blocks, hash pairs of hashes, repeat"), and RFC 6962's, the one Certificate Transparency actually deploys. They differ in two places totalling about four lines. The demo runs the same script against both.

The mechanism is the inclusion proof: given a 32-byte root you trust, and log n sibling hashes, decide whether a block you were just handed is part of the committed data — without holding the data.

The aha is what the root does not commit to. Against the naive tree you can build a valid inclusion proof for a block that was never in the file, using no cryptography at all: two concatenations and a list slice. It verifies against the real, honest root.

By the end you should be able to:

• fold an inclusion proof by hand and say exactly what a True from verify() entitles you to conclude — which is less than you think;
• explain why H(0x00 ‖ leaf) and H(0x01 ‖ left ‖ right) are one byte of overhead that closes a whole attack class, and why the two bytes have to differ;
• name which of RFC 6962's two departures from the naive tree fixes which defect (they are not the same fix, and neither covers for the other);
• recognise, in a system you're reading, whether its Merkle root binds the shape of its tree or only its contents.

2. The problem this mechanism exists to solve

You have a large collection — a file split into blocks, a block of Bitcoin transactions, every TLS certificate a CA has ever issued — and someone who only holds a 32-byte digest of it wants to check one member.

Hashing the whole collection into a single digest gives you integrity but no selectivity: to check one block you need all of them. Hashing each block separately gives you selectivity but no compactness: the verifier now stores n digests, which is the problem you started with.

A Merkle tree is the standard resolution. One digest at the top; log n digests to check any member. That buys three things at once, and real systems want different ones:

• Bandwidth. BitTorrent and IPFS verify a chunk on arrival, against a root fetched once, instead of downloading everything before trusting anything.
• Tamper-evidence. Certificate Transparency logs publish a signed root (a Signed Tree Head). Any monitor can demand proof that a certificate is in the log, and a log that lies has to lie consistently, forever, to everyone.
• Cheap difference. Two replicas compare roots; equal means done. Unequal means descend, and the tree localises the disagreement in log n round-trips. This is Cassandra's and Dynamo's anti-entropy repair.

The competing goals that make more than one design defensible:

• Balanced vs. append-only. Padding a tree out to a power of two makes every proof the same length and the code trivial. But a transparency log grows, and you want the digests you already computed to stay valid when it does. RFC 6962 therefore builds a deliberately unbalanced tree, which costs uniform proof lengths and buys stable subtrees.
• Compactness vs. binding. The whole appeal of the root is that it is 32 bytes. Everything you want it to commit to — contents, order, count, tree shape — must be squeezed into the hashing rule itself, because there is no room for anything else. This toy is about a rule that squeezes in less than it looks like it does.
• Simplicity vs. domain separation. "Just hash the concatenation" is the version that fits on a slide. It is also the version with the hole.

3. Background you need

None of this is deep, but the commentary below leans on it hard.

The two that carry the result are the first two. Domain separation is the fix; ambiguous concatenation is the hole it fixes. If you only internalise one row, take the second: SHA-256 is not broken here. Nothing on this page involves finding a hash collision. The attack works because a 64-byte string of bytes and a pair of 32-byte digests are the same thing, and the naive hashing rule never records which one it meant.

4. The mental model

Before any code. Four 64-byte blocks, hashed pairwise up to one root. These are the real digests from demo.py, truncated to 8 hex characters:

That last line is the whole toy. An inclusion proof is a fold: start at a leaf, absorb siblings, land on the root. The verifier is handed a starting value and a list of steps, and it has no way to check how far down the starting value was supposed to be. So the attacker starts higher up:

RFC 6962's fix is to put the level into the hash — one byte, 0x00 for a leaf and 0x01 for an internal node — so the two roles can never produce the same digest.

5. Reading the source

156 lines, two classes, one of which is four methods of the other. Read it in this order.

5.1 The whole difference, stated in the module docstring

  NaiveTree   leaf = H(block)          node = H(left || right)
  TaggedTree  leaf = H(0x00 || block)  node = H(0x01 || left || right)

  NaiveTree   an odd level duplicates its last node to make a pair
  TaggedTree  an n-leaf tree splits at the largest power of two below n

Two differences, four lines of code, and it is worth being clear now that they are independent fixes for independent bugs. The tags fix the forgery (§6.2). The split rule fixes the root collision (§6.3). Neither covers for the other, which I checked rather than assumed — §7.3 has the 2×2.

Everything else in TaggedTree is machinery to express those two changes.

5.2 NaiveTree.__init__ — building the levels, and the CVE line

    def __init__(self, blocks):
        if not blocks:
            raise ValueError("a Merkle tree needs at least one block")
        level = [self.leaf_hash(b) for b in blocks]
        self.levels = []
        while len(level) > 1:
            if len(level) % 2:
                level = level + [level[-1]]   # the CVE-2012-2459 line
            self.levels.append(level)
            level = [self.node_hash(level[i], level[i + 1])
                     for i in range(0, len(level), 2)]
        self.levels.append(level)

Note self.leaf_hash(b) and self.node_hash(...) — dispatched through self, not called as NaiveTree.leaf_hash. That single choice is why TaggedTree can inherit this entire constructor's logic while replacing its hashes, and why verify gets written once (§7.6).

self.levels is a list of levels, bottom-up, and the whole tree is materialised eagerly. A production tree stores only what it needs and recomputes the rest; here, keeping every level is what makes proof() a three-line loop instead of a recursion, and it makes the tree inspectable, which §6.3 uses.

The commented line is the famous one. If a level has an odd number of nodes you cannot pair them all, and you must do something. Duplicating the last node is the cheapest something: no new hash function, no special empty value, no change to the pairing loop. Bitcoin does exactly this. What it costs is that the padded level [a, b, c, c] is now indistinguishable from a genuine 4-element level [a, b, c, c] — and there is a real block list that produces one. §6.3.

Note also if not blocks: raise. An empty tree has no natural root, and the alternatives (return H(""), return 32 zero bytes) both create a root that some other input might also produce. Refusing is the honest option.

5.3 The two hashes, and the walk that collects siblings

    @staticmethod
    def leaf_hash(block):
        return hashlib.sha256(block).digest()

    @staticmethod
    def node_hash(left, right):
        return hashlib.sha256(left + right).digest()

Six lines, and the entire vulnerability is in them. leaf_hash is sha256(x) for a 64-byte x. node_hash is sha256(left + right) — which, since digests are 32 bytes, is sha256(x) for a 64-byte x. They are the same function. The names are the only thing distinguishing a leaf from an internal node, and names don't survive into the digest.

    def proof(self, index):
        """The sibling digests needed to recompute the root from block
        `index`, bottom level first.
        """
        path = []
        for level in self.levels[:-1]:
            sibling = index ^ 1
            path.append((level[sibling], RIGHT if index % 2 == 0 else LEFT))
            index //= 2
        return path

index ^ 1 flips the low bit: even index → its right neighbour, odd index → its left. index //= 2 is the move to the parent. Two integer ops per level, no tree traversal, because the level lists are already laid out in order.

The side tag matters, and I checked how much: a verifier that ignored it and always folded H(running ‖ sibling) still verifies blk0 (whose siblings all sit on the right) and fails on blk3 (whose siblings all sit on the left):

So side is load-bearing, but it is not a security control — it is the index, re-encoded. LEFT/RIGHT are the strings "L"/"R" (merkle.py:23-24) rather than booleans purely so the printed proofs in §6 read as R:d2030d4e.

5.4 verify — and the argument that is deliberately missing

    @classmethod
    def verify(cls, root, block, proof):
        """Does `block` sit under `root`, given `proof`?

        Note what is NOT an argument: the number of leaves, or the expected
        proof length. The verifier folds whatever it is handed and compares.
        See commentary section 5.4 — this omission is the attack surface.
        """
        running = cls.leaf_hash(block)
        for sibling, side in proof:
            if side == LEFT:
                running = cls.node_hash(sibling, running)
            else:
                running = cls.node_hash(running, sibling)
        return running == root

This is the subsection the source docstring points at, so read it slowly.

The omission is a design decision, not an oversight. verify takes a root, a block, and a proof. It does not take n, or the expected depth, and it will happily fold a proof of length 0, 1, or 40. That is written down in the docstring on purpose, because the honest version of this toy's claim is not "here is a bug I found" — it is "here is the interface almost every tutorial gives you, and here is what that interface cannot check."

Ask what verify would need in order to reject a shortened proof. It would need to know how tall the tree is, which means knowing n, which means n has to reach the verifier over an authenticated channel — and the verifier's whole selling point was that it holds 32 bytes and nothing else. So the omission is exactly the thing that makes an inclusion proof cheap. §7.2 is about what pinning the length would buy, and what it wouldn't.

Second thing to notice: cls.leaf_hash(block) — the fold starts by applying the leaf hash. Under NaiveTree that is sha256(block), identical to what node_hash does to a 64-byte input. Under TaggedTree it is sha256(b"\x00" + block), which no internal node can ever equal. The one-line fix lives entirely inside this one call.

Third: verify never looks at len(block). Blocks being 64 bytes is a convention of demo.py, not an invariant merkle.py enforces — see §7.5, where that turns out to matter less than you'd expect and more than you'd like.

5.5 TaggedTree — the two changes

    @staticmethod
    def leaf_hash(block):
        return hashlib.sha256(b"\x00" + block).digest()

    @staticmethod
    def node_hash(left, right):
        return hashlib.sha256(b"\x01" + left + right).digest()

    @staticmethod
    def _split(n):
        """RFC 6962 section 2.1: k is the largest power of two strictly less
        than n. So a 5-leaf tree is a perfect 4-leaf tree beside a 1-leaf
        tree, never a padded 8-leaf one.
        """
        return 1 << ((n - 1).bit_length() - 1)

These are RFC 6962 §2.1 transcribed. The RFC writes them as

with k "the largest power of two smaller than n (i.e., k < n <= 2k)". The RFC's own justification for the prefixes, restated in its successor RFC 9162, is one sentence: "this domain separation is required to give second preimage resistance."

_split is 1 << ((n - 1).bit_length() - 1), which is the largest power of two strictly below n. The - 1 before .bit_length() is what makes it strict: for n = 8, (8-1).bit_length() is 3, giving 4, not 8. Get that wrong and _subtree(0, 8) splits into (0,8) and (8,8) and recurses forever — I wrote the broken version, and it raises RecursionError on the first 8-leaf tree.

The consequence of splitting instead of padding: an odd count never duplicates anything, so no two distinct block lists can produce the same level. A 5-leaf tree is a perfect 4-leaf tree next to a lone leaf, with a proof of length 3 for the first four blocks and length 1 for the fifth. Non-uniform, on purpose — §7.2.

5.6 _subtree — the tree as a memoised recursion

    def _subtree(self, lo, hi):
        if (lo, hi) not in self._cache:
            if hi - lo == 1:
                self._cache[lo, hi] = self.leaves[lo]
            else:
                k = lo + self._split(hi - lo)
                self._cache[lo, hi] = self.node_hash(self._subtree(lo, k),
                                                     self._subtree(k, hi))
        return self._cache[lo, hi]

NaiveTree stores levels; TaggedTree stores subtree ranges, keyed (lo, hi). That is not decoration — it is the shape of RFC 6962's tree. The levels representation assumes every node has a level, which an unbalanced tree makes meaningless (the fifth leaf of a 5-leaf tree is one hop from the root while the first is three). Ranges are the only description that survives.

The _cache also previews the real reason CT builds trees this way: the digest of (0, k) for a perfect power-of-two range never changes when the log grows past k. Append entries and the old subtree digests are still valid, still cacheable, still servable. Padding out to a power of two would invalidate everything above the fill line on every append.

5.7 TaggedTree.proof — same proof, different walk

    def proof(self, index):
        """Same walk as NaiveTree's, but down the recursive split instead of
        along stored levels. Collected top-down, so it is reversed to hand
        back the same bottom-up order.
        """
        path = []
        lo, hi = 0, len(self.leaves)
        while hi - lo > 1:
            k = lo + self._split(hi - lo)
            if index < k:
                path.append((self._subtree(k, hi), RIGHT))
                hi = k
            else:
                path.append((self._subtree(lo, k), LEFT))
                lo = k
        path.reverse()
        return path

Descending from the root means siblings arrive top-down, but verify folds bottom-up, so the list is reversed. That path.reverse() is load-bearing and not merely cosmetic — I removed it and re-ran, including at n=5 where the path is genuinely lopsided:

The point of paying that cost is that both classes hand back proofs in one format, so verify is written once and inherited. The two schemes then run the identical fold, and the only variable left in the experiment is the two hash functions.

6. The demo, and what it proves

demo.py builds four 64-byte blocks and runs three acts against each scheme. The block size is the interesting constant:

CHUNK = 64  # bytes per block — deliberately equal to two SHA-256 digests


def block(text):
    """A fixed-size storage block: 64 bytes, dot-padded. Fixed-size chunking
    is what real content-addressed stores do, and 64 = 2 x 32 is the size
    that makes act 2 work.
    """
    raw = text.encode()
    assert len(raw) <= CHUNK, text
    return raw.ljust(CHUNK, b".")

Fixed-size blocks are what real content-addressed storage does. 64 bytes is a plausible choice and also exactly two SHA-256 digests, which is what makes the forged string a legal block rather than obvious garbage. §7.5 has the counterfactual on how much that actually buys.

python3 demo.py

6.1 Act 1: the honest proof, folded by hand

The four leaf hashes, and the two internal nodes, from the shipped code:

proof(0) is ['R:68204a56', 'R:d2030d4e'] — the two right-hand siblings, which are exactly H(blk1) and n1. The verifier folds:

1. running = leaf_hash(blk0) = 00463edd…
2. sibling 68204a56… is on the right, so running = H(00463edd… ‖ 68204a56…) = fb235ee5…, which is n0
3. sibling d2030d4e… is on the right, so running = H(fb235ee5… ‖ d2030d4e…) = fff2e8dd…, which is the root

True. Two hashes, 64 bytes of proof, and the verifier never touched blk1, blk2 or blk3.

6.2 Act 2: the forgery — THE AHA

    scheme = type(tree)
    forged = scheme.leaf_hash(BLOCKS[0]) + proof0[0][0]
    forged_proof = proof0[1:]

That is the entire attack. scheme.leaf_hash(BLOCKS[0]) is H(blk0), which the attacker computes from a block they were legitimately given. proof0[0][0] is H(blk1), which the honest proof handed them. Concatenate the two:

32 + 32 = 64 bytes, which is a legal block. The demo confirms in BLOCKS? False — it was never in the file. And:

Of course they're equal — leaf_hash(forged) is sha256 of those 64 bytes, and n0 = node_hash(H(blk0), H(blk1)) is sha256 of the same 64 bytes. Identical input, identical output. No collision was found; there was never anything to find.

So the forged block's leaf hash is the internal node one level up. Drop the now-redundant first step of the proof and the fold is:

1. running = leaf_hash(forged) = fb235ee5… = n0
2. sibling d2030d4e… on the right: running = H(n0 ‖ n1) = fff2e8dd…

which is the honest root. verify(forged) True, against a proof of length 1 instead of 2. Nothing checked the length, because verify was never told what the length should be (§5.4).

test_forged_leaf_verifies_under_naive (test_merkle.py lines 34–46) asserts all four parts of this: 64 bytes, not in BLOCKS, honest proof length 2, forged proof verifies.

6.3 Act 3: two block lists, one root

Dumping the levels of both trees shows why there is nothing subtle here:

[a, b, c] has an odd level 0, so merkle.py:40 appends H(c) again. The result is [H(a), H(b), H(c), H(c)] — character for character the level 0 of [a, b, c, c]. From there the two computations are the same computation.

This is CVE-2012-2459. NVD's entry is famously uninformative ("Unspecified vulnerability in bitcoind and Bitcoin-Qt … allows remote attackers to cause a denial of service (block-processing outage and incorrect block count)"). The Bitcoin wiki says what actually happened: "Block hash collisions can easily be made by duplicating transactions in the merkle tree." An attacker takes a valid block, duplicates its last transaction (or last pair — see below), and relays the mutated block. It has the same merkle root, therefore the same block hash, but it is invalid because it contains a duplicate transaction. A vulnerable node rejects it and remembers the hash as invalid — so when the real block arrives, it is rejected too. Fixed in 0.4.6, 0.5.5, 0.6.0.7 and 0.6.1rc2 by detecting the mutation rather than by changing the hash rule, which Bitcoin could not do without a hard fork. The comment survives in src/consensus/merkle.cpp to this day, with the example [1,2,3,4,5,6] and [1,2,3,4,5,6,5,6].

Which sizes collide is worth knowing, because "duplicate the last one" is not the general rule. I enumerated every n from 1 to 12 against every "repeat the last k" for k in 1..4:

The pattern: a duplication collides exactly when it reproduces the padding the tree was going to do anyway. n = 4 is already a perfect tree, so adding a fifth block creates a whole new level and a different root — the attack does not apply. n = 6 is even at level 0 but odd at level 1, so the duplication has to happen a level up, which at level 0 means repeating the last two blocks. That is exactly the [1,2,3,4,5,6,5,6] in Bitcoin's source comment. test_duplicating_the_last_block_keeps_the_naive_root (test_merkle.py lines 64–72) pins 3-vs-4, 5-vs-6 and 6-vs-8.

6.4 The tagged column: what survives

Same three acts, TaggedTree. Act 1 still passes — the fix is not "reject everything." Act 2 gives verify(forged) False: the forged block's leaf hash is sha256(0x00 ‖ 64 bytes), a 65-byte input, while the internal node above it is sha256(0x01 ‖ 64 bytes), a different 65-byte input. 68379ffb… versus 095b82eb…. The two roles now live in disjoint domains and no amount of concatenating can move a value between them.

Act 3 gives two different roots, 39012668… and 0d1f66ce…, because _split(3) is 2 — the 3-leaf tree is (a,b) beside c — while the 4-leaf tree is (a,b) beside (c,c). Nothing was duplicated, so nothing collided.

6.5 A third attack the demo doesn't run: the zero-length proof

The forgery generalises upward. The two level-1 nodes concatenated, n0 ‖ n1, are also 64 bytes, and sha256 of them is the root itself. So:

A valid inclusion proof of length zero. The verifier hashes the block, finds it equal to the root, and returns True. Under the naive scheme the root of any 2^k-leaf tree is itself a legal forged block for that tree, at every level of the tree at once.

6.6 The tests

python3 test_merkle.py

Eight tests, stdlib asserts, no pytest. Four of them pin the two failures and the two fixes. test_honest_proofs_round_trip is the guard rail that stops a "fix" from being return False: it verifies every block at every tree size from 1 to 9, under both schemes.

6.7 The boundary condition — where the attack vanishes

• Tagged hashing. H(0x00 ‖ leaf) and H(0x01 ‖ l ‖ r) end it outright, including the zero-length variant. RFC 6962, RFC 9162, Certificate Transparency, Go's checksum database, and Sigstore all do this. If your tree tags, stop worrying.
• A verifier that pins the depth. If verify is told how tall the tree is, the length-1 proof is rejected before any hashing. It works — see §7.2 for the transcript, and for why it is a weaker guarantee than tagging.
• Blocks that can't be 64 bytes of arbitrary binary. The forged string is a digest pair; it is not printable, not valid JSON, not a valid protobuf, not a Bitcoin transaction. A system whose leaves are parsed before they are trusted rejects it at the parser. Note the order of operations though: verify still returns True (§7.5). The parser is a second line of defence, not the same line.
• Leaves that aren't the same size as two digests. With 100-byte blocks a digest pair is not a legal block. This is the weakest of the four — the attacker can still hit some level of the tree if any legal leaf length is a multiple of the digest size, and the tree's own internal nodes are always exactly that.

Conversely, the attack is at its strongest where this toy puts it: fixed-size binary blocks, a verifier that holds only a root, and downstream logic that cares about membership rather than content.

7. Design decisions and roads not taken

7.1 Why verify accepts a variable-length proof

This is the decision the whole page rests on, so it is stated in the source docstring rather than left implicit. verify(root, block, proof) is the interface you will find in most Merkle tutorials, most blog posts, and a fair number of libraries. Adding n to it is not free:

• the verifier's entire value proposition is that it holds 32 bytes, so any extra input has to be transported and authenticated alongside the root;
• an unauthenticated n is worse than none, because it lets an attacker who controls the transport choose which depth you'll accept;
• in a growing log, n changes constantly, so pinning it means re-fetching it, and now your "offline verifier" is online.

RFC 6962 makes a different call — its inclusion proof carries the tree size and the leaf index — but it does that in addition to domain separation, not instead of it. Writing verify without them here is what makes the toy show the failure at all; a verifier that pinned depth would hide the hashing bug behind an unrelated check, and you'd learn nothing about why the tags exist.

7.2 The cheap defence: pin the proof length

The obvious cheap fix, and worth taking seriously because it does work against this forgery. Add one line: reject unless len(proof) == ceil(log2 n). Under the naive tree every proof at a given n is the same length — the levels are shared — so this is well-defined. I ran it:

The forgery dies. And it cannot be repaired by padding the proof back out to length 2 — a longer forged proof would require an actual preimage:

So why is this the partial defence and tagging the real one? Three reasons, all of them things I ran rather than reasoned about.

It does nothing about the collision. test_proof_length_would_have_caught_the_forgery_but_not_the_collision (test_merkle.py lines 83–93) is named after this. A 3-leaf tree and a 4-leaf tree both produce length-2 proofs and the same root:

The length check cannot distinguish them, because the whole problem is that the root doesn't commit to n. Which means, circularly, that you cannot derive the n you need for the check from the thing you trust.

It moves the trust problem rather than solving it. Now n must arrive authenticated. Tagging costs one byte per hash and no protocol changes at all.

The length isn't uniform in the tree you actually want. Under RFC 6962's unbalanced tree there is no single depth to pin:

The check that works is per-index, not per-tree — which means the verifier needs the leaf index too, authenticated. That is exactly what RFC 6962's inclusion proof carries, and it is a much bigger interface than "one byte in front of each hash."

7.3 Which change fixes which defect — the 2×2

TaggedTree makes two changes at once (§5.1), which is a bad experiment. I split them into four schemes and ran all three properties against each:

Clean separation, and it is the most useful thing on this page after the aha itself:

• Domain separation fixes the forgery, and only the forgery. Tag the hashes but keep duplicating odd levels and the CVE-2012-2459 collision is right back.
• Not padding fixes the collision, and only the collision. Adopt RFC 6962's split rule but keep the naive hashes and the forged block still verifies.

If you had guessed that "use RFC 6962's hashing" was one fix, this is the correction. It is two, and a system can easily ship one.

7.4 Why two distinct tag bytes rather than one

0x00 and 0x01 look like ceremony — surely one tag is enough to separate the domains? On this toy's fixed 64-byte blocks, it is:

Two things there. The last row first: tagging both with the same byte restores the attack completely. H(0x00 ‖ block) and H(0x00 ‖ l ‖ r) are the same function of a 64-byte argument again; the prefix cancels. What separates domains is that the tags differ, not that they exist.

The middle rows are more interesting and I nearly wrote them up as "one tag is enough." It isn't — the separation there is accidental, coming from the input lengths (65 bytes vs 64), and it evaporates the moment a shorter block is legal. Under leaf-tagging only, leaf_hash(b) = H(0x00 ‖ b) equals node_hash(l, r) = H(l ‖ r) whenever l begins with 0x00 and b is the remaining 63 bytes. That is a 1-in-256 chance per node, so I searched for one:

458 tries on a laptop. Two distinct prefixes are immune because the tag is inside the hash input on both sides and the two inputs differ in their first byte no matter how the rest lines up.

7.5 Why 64-byte blocks — and what that choice does not do

The natural claim is "64-byte blocks are what make the forgery possible." I ran it, and that claim is wrong in an instructive way. Rebuilding the demo with 96-byte blocks:

verify never looks at len(block) (§5.4), so the forged 64-byte string still verifies against a tree whose blocks are all 96 bytes. What the 64-byte choice buys is not the acceptance — it's the plausibility. At 64 bytes the forged string is a well-formed block: the right size, indistinguishable from data, something a storage layer would hand to an application without comment. At 96 it is a malformed block that verify blesses and the layer above throws out.

That distinction is the entire practical severity argument, and it's why the boundary condition in §6.7 lists parsing separately from verifying. It is also the honest version of the caveat in Dean Jerkovich's write-up of this attack: you get a colliding input, but you do not get to choose what it says.

7.6 Why TaggedTree inherits from NaiveTree

verify is written once, on NaiveTree, and inherited unchanged (merkle.py:69-83). TaggedTree overrides leaf_hash, node_hash, __init__, and proof — but the fold itself is shared code.

This is not code golf; it is the experimental control. If each class had its own verify, every "tagged rejects it, naive accepts it" result on this page would be open to the objection that the two verifiers differ somewhere else. They can't: it is literally the same function object, and the only thing that varies is which leaf_hash/node_hash cls resolves to.

The cost is a TaggedTree that inherits an __init__ it immediately overrides and a self.levels it never has. A shared abstract base with two concrete subclasses would be tidier and would also add a third class to a two-class file. For a toy whose point is "these differ in four lines," inheritance says it better than an ABC would.

8. What's simplified vs. the real thing

• No consistency proofs. The tree is built once from a fixed list. A real transparency log is append-only, and its second proof type — RFC 6962 §2.1.2's consistency proof — shows that the tree behind root B contains everything behind an earlier root A, unmodified. That is what stops a log from quietly rewriting history, and it is at least as important as inclusion. Leaving it out is what keeps this toy at 156 lines.
• No non-membership. You cannot prove a block isn't in this tree. Real systems that need that (Certificate Revocation Transparency, blockchain state tries) use a sparse Merkle tree keyed by the hash of the item, where a proof of "this leaf is empty" is a proof of absence.
• No transport, no signature. The root is a Python value the demo reads out of the tree it just built, which is exactly the situation an attacker is not in. In production the root arrives signed — CT's Signed Tree Head — and the signature is what makes it trustworthy in the first place. This toy assumes you already have an authentic root and asks what it's worth.
• One block per leaf, one file. Real content-addressed stores chunk with content-defined boundaries (rolling hashes) so an insertion doesn't shift every subsequent block, and they nest trees: a root per file, a root over the file roots.
• Balanced-by-padding is not shown. The third design — pad the leaf list up to 2^k with a distinguished empty value, never with a real leaf. I built it to check where it lands, and it lands exactly where §7.3 predicts:
  pad-with-empty: root([a,b,c])==root([a,b,c,c])? False pad-with-empty: forgery still works? True
  It fixes the collision as thoroughly as RFC 6962's split does, and throws in uniform proof lengths — but it is a padding fix, so the forgery is untouched. Where it loses to RFC 6962 is append: growing past 2^k re-parents every node, so no cached subtree digest survives, which is why logs that grow don't use it.
• The whole tree is materialised in memory. NaiveTree keeps every level; TaggedTree memoises every subtree range. A CT log has billions of leaves and stores tiles of the tree on disk, computing the rest on demand.
• No concurrency, no incremental append. Adding a block means rebuilding from scratch. Real implementations append and recompute only the right spine, under a lock or a single-writer discipline.
• No proof size limits. verify will fold a proof of any length you hand it, which is a denial-of-service invitation as well as the attack surface in §5.4. Real verifiers cap the length before they start hashing.

9. Check yourself

Answer before expanding. Each answer is derivable from the source, and each was verified by running it.

10. Further reading

Every link below was fetched and confirmed live when this was written. Two candidates were dropped as dead: transparency.dev/articles/merkle-trees/ (404) and merkle.com/papers/Certified1979.pdf (404).

• RFC 6962: Certificate Transparency — the primary source, and short. §2.1 is the two lines this toy's TaggedTree implements verbatim, including k as "the largest power of two smaller than n." §2.1.1 is inclusion proofs, §2.1.2 the consistency proofs this toy leaves out. Read §2.1 even if you read nothing else.
• RFC 9162: Certificate Transparency Version 2.0 — the successor. Same 0x00/0x01 construction, and it states the reason outright where 6962 left it implicit: "the hash calculations for leaves and nodes differ; this domain separation is required to give second preimage resistance."
• Dean Jerkovich: Attacking Merkle trees with a second preimage attack — the same forgery as §6.2, demonstrated against real Python Merkle libraries rather than a toy. Also the source of the honest caveat in §7.5: you get a colliding input, but "zero control over the value" of it.
• Bitcoin Core: src/consensus/merkle.cpp — production code for the naive scheme, with a long comment explaining the duplication and its consequences, using the [1,2,3,4,5,6] / [1,2,3,4,5,6,5,6] example from §6.3. Read how ComputeMerkleRoot sets a mutated flag instead of changing the hash rule — the fix you take when a hard fork isn't available.
• Bitcoin wiki: CVEs — the CVE-2012-2459 entry, dated 2012-05-14, with the one-line statement of the bug and the four patched releases.
• NVD: CVE-2012-2459 — the official record, and worth opening mostly as a lesson in how little a CVE entry can say: "Unspecified vulnerability … via unknown behavior on a Bitcoin network." The mechanism is nowhere in it.
• Russ Cox: Transparent Logs for Skeptical Clients — the clearest walk-through of tree hashes, record vs. interior hashes, and both proof types, with the arithmetic for why an inclusion proof is lg N hashes and a consistency proof about 3 lg N. This is the design behind Go's checksum database.
• Certificate Transparency: How CT works — where the signed root comes from in practice: Signed Tree Heads, monitors, auditors. Short on mechanics, good on why anyone signs a Merkle root at all.
• Wikipedia: Merkle tree — the general treatment, Merkle's 1979 patent (US 4309569), and a short section on the second preimage attack that names the 0x00/0x01 fix as Certificate Transparency's.