CVE-2012-2459 at the leaf level: duplicate last transaction
ProvedBitcoinMerkle.dup_leafFor every , , non-empty list of even length and hash ,
The list has odd length, so the loop duplicates its last element; appending a second copy of explicitly produces the same first level, hence the same root, while the explicit copy forms an equal aligned pair and is flagged. Non-emptiness of is required: is its own root but hashes to .
import Definitions.Def_BitcoinMerkle
theorem BitcoinMerkle.dup_leaf {H : Type} [DecidableEq H] (c : H → H → H) (z : H)
(l : List H) (a : H) (hne : l ≠ []) (heven : l.length % 2 = 0) :
(BitcoinMerkle.computeMerkleRoot c z (l ++ [a])).1 = (BitcoinMerkle.computeMerkleRoot c z (l ++ [a, a])).1 ∧
(BitcoinMerkle.computeMerkleRoot c z (l ++ [a, a])).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_leaf
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 is assumed about either. is a finite list over and is an element, subject to two hypotheses:
- ( is nonempty);
- ( is even; with (1) this forces ).
The conclusion is the conjunction
where is list concatenation ( is with appended once; is with appended twice), 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". (pairUp) is , , — aligned adjacent pairs combined by , an odd trailing element combined with itself. (hasEqualPair) is the Boolean , : iff some even with has ; positions are not tested and a trailing odd element is never tested against itself.
What is and is not claimed. Since is even, in the element sits at an even index and is the odd trailing element (so combines it as and does not test it), while in the two copies of occupy an aligned pair . The first conjunct equates only the first components of the two results; it makes no claim about the flag . The second conjunct says the flag of the input with the doubled is . Nothing is claimed when is empty or of odd length. The hypotheses are satisfiable (any of length works), so the statement is not vacuous. It is asserted for every and without restriction.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.