CVE-2012-2459 in general: duplicating an aligned trailing block
ProvedBitcoinMerkle.dup_blockFor every pairwise hash , zero hash , level , non-empty list whose length is a multiple of , and block of exactly hashes,
where root and mutated are the two components of , the transcription of ComputeMerkleRoot.
Under the alignment hypotheses, occupies a complete aligned subtree that collapses to a single node after levels; at that level has odd length and the source duplicates the node, while already carries the copy as an equal aligned pair. The two computations then coincide, and the copy is detected by the per-level check. With this is the duplicated last transaction; with and of length four it is the versus example of the source comment.
This is the general statement of the defence against CVE-2012-2459: every duplication of this shape is root-preserving, which is the attack, and is flagged, which is the defence. Nothing is assumed about ; the result is about the loop structure alone.
Formalization Note. The non-emptiness of is necessary, since a single-node list is returned without processing while its doubled form is hashed once more. The statement is proved for the loop with an arbitrary incoming flag and specialized to computeMerkleRoot.
import Definitions.Def_BitcoinMerkle
theorem BitcoinMerkle.dup_block {H : Type} [DecidableEq H] (c : H → H → H) (z : H) :
∀ (k : Nat) (l t : List H), l ≠ [] → l.length % 2 ^ (k + 1) = 0 → t.length = 2 ^ k →
(BitcoinMerkle.computeMerkleRoot c z (l ++ t)).1 = (BitcoinMerkle.computeMerkleRoot c z (l ++ t ++ t)).1 ∧
(BitcoinMerkle.computeMerkleRoot c z (l ++ t ++ t)).2 = true := by sorryRead-back
What the Lean code literally says, in plain math · claude-fable-5-1 (independent sub-agent, blind: Lean code + auditor instructions only)
Read-back: BitcoinMerkle.dup_block
Binders and assumptions. is an arbitrary type with decidable equality (for the Boolean is exactly when ). is an arbitrary two-argument operation and an arbitrary element; nothing whatsoever is assumed about or . The theorem then universally quantifies over a natural number and two finite lists over , subject to three hypotheses:
- ( is nonempty);
- (the length of is a multiple of ; together with (1) this forces );
- (so is automatically nonempty, having at least one entry; its entries are arbitrary and need not be distinct).
Under these hypotheses the conclusion is the conjunction
where is list concatenation (so is followed by two consecutive copies of ), is the first component of the pair and its Boolean second component.
Unfolding (computeMerkleRoot). , where (rootLoop) is defined on a list and Boolean flag by
with the first entry of , or if is empty, and Boolean "or". Here (pairUp) is given by , , — adjacent aligned pairs are combined by , and an odd trailing element is combined with itself. (hasEqualPair) is the Boolean and ; that is, iff some even with has — only aligned positions are tested, never , never a non-adjacent pair, and never the trailing element of an odd-length list against itself.
What is and is not claimed. The first conjunct equates only the first components (the elements of ) of the two results; it says nothing about the second component of , which may be or . The second conjunct asserts that the Boolean flag for the input with the duplicated block is — i.e. at some level of the iteration (the input itself or some -image of it with at least two entries) some aligned pair consists of equal elements. No claim is made about inputs where is empty, where is not a multiple of , or where . The hypotheses are jointly satisfiable (e.g. , ), so the statement is not vacuous. The case reads: nonempty of even length, a single element. The statement holds for every , including degenerate ones such as constant functions or .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.