ComputeMerkleRoot with Bitcoin's odd-level duplication and mutation check
DefinitionBitcoinMerkleHashes form an arbitrary type with decidable equality. The pairwise hash (SHA256D64 on two concatenated hashes in the source) is an abstract function , and the all-zero hash returned for an empty list is an abstract .
One level. maps a list to the list of over aligned pairs; an odd trailing element contributes , which is the source's hashes.push_back(hashes.back()) followed by pairwise hashing. Its length is (pairUp_length, used to justify termination).
The mutation test. is true when some aligned pair with has equal entries. The duplicated trailing element is not tested, because in the source the test runs before the duplication.
The loop. : while , replace by and by ; on exit return the remaining hash (or for an empty list) together with .
The root. , a pair (root, mutated), as ComputeMerkleRoot(hashes, &mutated).
These definitions fix the semantics of the block Merkle root and of the CVE-2012-2459 defence for use by block-structure validation.
Formalization Note. rootLoop is defined by well-founded recursion on the list length. Equality in hasEqualPair is decide (a = b) on . Nothing is assumed about ; in particular no collision-resistance. Only Std is imported.
import Std
namespace BitcoinMerkle
/-! Transcription of `ComputeMerkleRoot` (`src/consensus/merkle.cpp`, Bitcoin Core revision
`a773e1e33b349dc819b5a0edc1c7a4839dc73b48`). Hashes are an arbitrary type `H` with decidable
equality; the pairwise hash `SHA256D64` on two concatenated hashes is an abstract function
`c : H → H → H`, and `uint256()` (the all-zero hash returned for an empty list) is an abstract
`z : H`. The loop body is: flag any equal aligned pair `(pos, pos + 1)` of the current level
(`pos` even, `pos + 1 < size`), duplicate the last element when the level has odd length, hash
adjacent pairs, and continue while more than one hash remains. -/
variable {H : Type} [DecidableEq H]
/-- One level of the tree: hash adjacent pairs; an odd trailing element is hashed with itself,
which is `hashes.push_back(hashes.back())` followed by `SHA256D64`. -/
def pairUp (c : H → H → H) : List H → List H
| a :: b :: rest => c a b :: pairUp c rest
| [a] => [c a a]
| [] => []
/-- The mutation test of one level: some aligned pair `(pos, pos + 1)` with `pos` even and
`pos + 1 < size` consists of equal hashes. The duplicated trailing element is not tested. -/
def hasEqualPair : List H → Bool
| a :: b :: rest => decide (a = b) || hasEqualPair rest
| _ => false
omit [DecidableEq H] in
theorem pairUp_length (c : H → H → H) : ∀ l : List H, (pairUp c l).length = (l.length + 1) / 2
| a :: b :: rest => by
simp only [pairUp, List.length_cons, pairUp_length c rest]
omega
| [a] => by simp [pairUp]
| [] => by simp [pairUp]
/-- The `while (hashes.size() > 1)` loop with its running `mutation` flag. -/
def rootLoop (c : H → H → H) (z : H) (hs : List H) (mutation : Bool) : H × Bool :=
if _h : 1 < hs.length then
rootLoop c z (pairUp c hs) (mutation || hasEqualPair hs)
else
(hs.headD z, mutation)
termination_by hs.length
decreasing_by
simp_wf
rw [pairUp_length]
omega
/-- `ComputeMerkleRoot(hashes, mutated)`: the root and the mutation flag. -/
def computeMerkleRoot (c : H → H → H) (z : H) (hs : List H) : H × Bool :=
rootLoop c z hs false
end BitcoinMerkle
Read-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: Def_BitcoinMerkle (five declarations)
Shared setting for every declaration in this file. Throughout, is an arbitrary type (any type whatsoever; nothing says it consists of 256-bit words, hashes, or anything else), and is assumed to carry decidable equality: for any the proposition can be mechanically evaluated to a Boolean, which I write (equal to exactly when and to otherwise). Several declarations take a function , i.e. a two-argument operation , and an element . Both are completely abstract parameters: nothing is assumed about (it need not be injective, collision-resistant, associative, commutative, or distinct from any projection), and nothing is assumed about . The file carries prose comments mentioning Bitcoin Core source files, SHA256D64, and uint256(); these comments are not part of any formal statement and impose no constraint on , , or .
pairUp
For a fixed , pairUp is a function from finite lists over to finite lists over , defined by structural recursion with three cases:
Here denotes a list whose first two entries are and and whose remaining (possibly empty) tail is . Concretely, for a list : if is even, returns ; if is odd, it returns , so the unpaired trailing element is combined with itself via . The empty list maps to the empty list, and a singleton maps to the singleton (not to ). Only adjacent aligned pairs are combined; is always applied with the earlier element as its first argument. The output has exactly entries (see pairUp_length below). This definition does not use decidable equality of .
hasEqualPair
hasEqualPair is a function from finite lists over to the Booleans (a Boolean value, not a proposition), defined by recursion with two cases:
The symbol here is Boolean "or". Unfolding, for :
So tests exactly the positions for equality of the two entries. It does not test any non-aligned adjacent pair such as or , does not test any non-adjacent pair, and when is odd it does not test the trailing element against anything (in particular, the self-pairing that performs on never causes to return ). and for every . The definition uses the decidable equality on to form .
pairUp_length
This is a theorem. For every type (here no decidable-equality assumption is made, as the declaration explicitly omits it), every , and every finite list over ,
where is list length and the division is natural-number (floor) division. Equivalently . Edge values: ; ; ; . The theorem is stated for all lists including the empty list, and asserts only the length, nothing about the entries.
rootLoop
For fixed and , rootLoop is a function taking a finite list over and a Boolean (the running "mutation" flag) and returning an ordered pair in . It is defined by recursion on the length of :
where and are pairUp and hasEqualPair as unfolded above, is Boolean "or", and is the first entry of if is nonempty and is the default value if . Thus: on each pass where the current list has at least two entries, the flag is updated to (with evaluated on the current list, before pairing), the list is replaced by , and the loop repeats; once the list has at most one entry, the loop stops and returns the pair (first-or-, current flag). In particular and for every and ; a singleton input is returned unchanged in its first component, not as . Because the flag is only ever combined with , once it is it remains through all subsequent passes. The loop condition is strictly (so it runs precisely when ). Termination is justified by the fact that whenever . The hypothesis name attached to the if test is unused in the body.
computeMerkleRoot
For fixed and , computeMerkleRoot is the function from finite lists over to given by
i.e. rootLoop as unfolded above, started with the mutation flag equal to . Its first component is the value left after repeatedly applying until at most one entry remains (or if was empty), and its second component is the Boolean "or" of evaluated on and on every intermediate level that had at least two entries. For the empty list the result is ; for a singleton it is . No assumption on , , or (length, distinctness, etc.) is built into the definition.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.