Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

ComputeMerkleRoot with Bitcoin's odd-level duplication and mutation check

Definition
BitcoinMerkle

by pitimespi · Oct 26, 2026 · Mathlib 0df444a (Lean v4.33.1)

bitcoinbitcoin-mainnetconsensuscve-2012-2459formal-verificationmerkle-tree

Hashes form an arbitrary type HHH with decidable equality. The pairwise hash (SHA256D64 on two concatenated hashes in the source) is an abstract function c:H→H→Hc : H \to H \to Hc:H→H→H, and the all-zero hash returned for an empty list is an abstract z:Hz : Hz:H.

One level. pairUpc\mathrm{pairUp}_cpairUpc​ maps a list to the list of c(ℓ2i,ℓ2i+1)c(\ell_{2i}, \ell_{2i+1})c(ℓ2i​,ℓ2i+1​) over aligned pairs; an odd trailing element aaa contributes c(a,a)c(a, a)c(a,a), which is the source's hashes.push_back(hashes.back()) followed by pairwise hashing. Its length is ⌈∣ℓ∣/2⌉\lceil |\ell| / 2 \rceil⌈∣ℓ∣/2⌉ (pairUp_length, used to justify termination).

The mutation test. hasEqualPair(ℓ)\mathrm{hasEqualPair}(\ell)hasEqualPair(ℓ) is true when some aligned pair (ℓ2i,ℓ2i+1)(\ell_{2i}, \ell_{2i+1})(ℓ2i​,ℓ2i+1​) with 2i+1<∣ℓ∣2i+1 < |\ell|2i+1<∣ℓ∣ has equal entries. The duplicated trailing element is not tested, because in the source the test runs before the duplication.

The loop. rootLoopc,z(ℓ,m)\mathrm{rootLoop}_{c,z}(\ell, m)rootLoopc,z​(ℓ,m): while ∣ℓ∣>1|\ell| > 1∣ℓ∣>1, replace mmm by m∨hasEqualPair(ℓ)m \lor \mathrm{hasEqualPair}(\ell)m∨hasEqualPair(ℓ) and ℓ\ellℓ by pairUpc(ℓ)\mathrm{pairUp}_c(\ell)pairUpc​(ℓ); on exit return the remaining hash (or zzz for an empty list) together with mmm.

The root. computeMerkleRootc,z(ℓ)=rootLoopc,z(ℓ,false)\mathrm{computeMerkleRoot}_{c,z}(\ell) = \mathrm{rootLoop}_{c,z}(\ell, \mathtt{false})computeMerkleRootc,z​(ℓ)=rootLoopc,z​(ℓ,false), 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 HHH. Nothing is assumed about ccc; in particular no collision-resistance. Only Std is imported.

Definition code
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
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48, ComputeMerkleRoot, src/consensus/merkle.cpp lines 51-73, with the CVE-2012-2459 comment at lines 16-50: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/consensus/merkle.cpp#L51
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, HHH is an arbitrary type (any type whatsoever; nothing says it consists of 256-bit words, hashes, or anything else), and HHH is assumed to carry decidable equality: for any x,y∈Hx, y \in Hx,y∈H the proposition x=yx = yx=y can be mechanically evaluated to a Boolean, which I write [x=y][x = y][x=y] (equal to true\mathrm{true}true exactly when x=yx = yx=y and to false\mathrm{false}false otherwise). Several declarations take a function c:H→H→Hc : H \to H \to Hc:H→H→H, i.e. a two-argument operation c(x,y)∈Hc(x, y) \in Hc(x,y)∈H, and an element z∈Hz \in Hz∈H. Both are completely abstract parameters: nothing is assumed about ccc (it need not be injective, collision-resistant, associative, commutative, or distinct from any projection), and nothing is assumed about zzz. 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 HHH, ccc, or zzz.


pairUp

For a fixed c:H→H→Hc : H \to H \to Hc:H→H→H, pairUp is a function PcP_cPc​ from finite lists over HHH to finite lists over HHH, defined by structural recursion with three cases:

Pc(a::b::r)=c(a,b)::Pc(r),Pc([a])=[ c(a,a) ],Pc([ ])=[ ].P_c(a :: b :: r) = c(a, b) :: P_c(r), \qquad P_c([a]) = [\,c(a, a)\,], \qquad P_c([\,]) = [\,].Pc​(a::b::r)=c(a,b)::Pc​(r),Pc​([a])=[c(a,a)],Pc​([])=[].

Here a::b::ra :: b :: ra::b::r denotes a list whose first two entries are aaa and bbb and whose remaining (possibly empty) tail is rrr. Concretely, for a list [x0,x1,…,xn−1][x_0, x_1, \dots, x_{n-1}][x0​,x1​,…,xn−1​]: if nnn is even, PcP_cPc​ returns [ c(x0,x1), c(x2,x3), …, c(xn−2,xn−1) ][\,c(x_0, x_1),\ c(x_2, x_3),\ \dots,\ c(x_{n-2}, x_{n-1})\,][c(x0​,x1​), c(x2​,x3​), …, c(xn−2​,xn−1​)]; if nnn is odd, it returns [ c(x0,x1), …, c(xn−3,xn−2), c(xn−1,xn−1) ][\,c(x_0, x_1),\ \dots,\ c(x_{n-3}, x_{n-2}),\ c(x_{n-1}, x_{n-1})\,][c(x0​,x1​), …, c(xn−3​,xn−2​), c(xn−1​,xn−1​)], so the unpaired trailing element is combined with itself via ccc. The empty list maps to the empty list, and a singleton [a][a][a] maps to the singleton [c(a,a)][c(a, a)][c(a,a)] (not to [a][a][a]). Only adjacent aligned pairs (x2i,x2i+1)(x_{2i}, x_{2i+1})(x2i​,x2i+1​) are combined; ccc is always applied with the earlier element as its first argument. The output has exactly ⌈n/2⌉\lceil n/2 \rceil⌈n/2⌉ entries (see pairUp_length below). This definition does not use decidable equality of HHH.


hasEqualPair

hasEqualPair is a function EEE from finite lists over HHH to the Booleans {true,false}\{\mathrm{true}, \mathrm{false}\}{true,false} (a Boolean value, not a proposition), defined by recursion with two cases:

E(a::b::r)=[a=b]  ∨  E(r),E(l)=false  whenever l=[ ] or l=[a] for some a.E(a :: b :: r) = [a = b] \;\lor\; E(r), \qquad E(l) = \mathrm{false} \ \text{ whenever } l = [\,] \text{ or } l = [a] \text{ for some } a.E(a::b::r)=[a=b]∨E(r),E(l)=false  whenever l=[] or l=[a] for some a.

The symbol ∨\lor∨ here is Boolean "or". Unfolding, for l=[x0,…,xn−1]l = [x_0, \dots, x_{n-1}]l=[x0​,…,xn−1​]:

E(l)=true  ⟺  ∃ i with i even, i+1<n, xi=xi+1.E(l) = \mathrm{true} \iff \exists\, i \text{ with } i \text{ even},\ i + 1 < n,\ x_i = x_{i+1}.E(l)=true⟺∃i with i even, i+1<n, xi​=xi+1​.

So EEE tests exactly the positions (0,1),(2,3),(4,5),…(0,1), (2,3), (4,5), \dots(0,1),(2,3),(4,5),… for equality of the two entries. It does not test any non-aligned adjacent pair such as (1,2)(1,2)(1,2) or (3,4)(3,4)(3,4), does not test any non-adjacent pair, and when nnn is odd it does not test the trailing element xn−1x_{n-1}xn−1​ against anything (in particular, the self-pairing that PcP_cPc​ performs on xn−1x_{n-1}xn−1​ never causes EEE to return true\mathrm{true}true). E([ ])=falseE([\,]) = \mathrm{false}E([])=false and E([a])=falseE([a]) = \mathrm{false}E([a])=false for every aaa. The definition uses the decidable equality on HHH to form [a=b][a = b][a=b].


pairUp_length

This is a theorem. For every type HHH (here no decidable-equality assumption is made, as the declaration explicitly omits it), every c:H→H→Hc : H \to H \to Hc:H→H→H, and every finite list lll over HHH,

∣Pc(l)∣=⌊∣l∣+12⌋,\bigl|P_c(l)\bigr| = \left\lfloor \frac{|l| + 1}{2} \right\rfloor,​Pc​(l)​=⌊2∣l∣+1​⌋,

where ∣⋅∣|\cdot|∣⋅∣ is list length and the division is natural-number (floor) division. Equivalently ∣Pc(l)∣=⌈∣l∣/2⌉|P_c(l)| = \lceil |l| / 2 \rceil∣Pc​(l)∣=⌈∣l∣/2⌉. Edge values: ∣l∣=0⇒0|l| = 0 \Rightarrow 0∣l∣=0⇒0; ∣l∣=1⇒1|l| = 1 \Rightarrow 1∣l∣=1⇒1; ∣l∣=2⇒1|l| = 2 \Rightarrow 1∣l∣=2⇒1; ∣l∣=3⇒2|l| = 3 \Rightarrow 2∣l∣=3⇒2. The theorem is stated for all lists including the empty list, and asserts only the length, nothing about the entries.


rootLoop

For fixed c:H→H→Hc : H \to H \to Hc:H→H→H and z∈Hz \in Hz∈H, rootLoop is a function Rc,zR_{c,z}Rc,z​ taking a finite list hshshs over HHH and a Boolean mmm (the running "mutation" flag) and returning an ordered pair in H×{true,false}H \times \{\mathrm{true}, \mathrm{false}\}H×{true,false}. It is defined by recursion on the length of hshshs:

Rc,z(hs,m)={Rc,z(Pc(hs), m∨E(hs))if 1<∣hs∣,(headz(hs), m)otherwise, i.e. if ∣hs∣≤1,R_{c,z}(hs, m) = \begin{cases} R_{c,z}\bigl(P_c(hs),\ m \lor E(hs)\bigr) & \text{if } 1 < |hs|, \\[4pt] \bigl(\mathrm{head}_z(hs),\ m\bigr) & \text{otherwise, i.e. if } |hs| \le 1, \end{cases}Rc,z​(hs,m)={Rc,z​(Pc​(hs), m∨E(hs))(headz​(hs), m)​if 1<∣hs∣,otherwise, i.e. if ∣hs∣≤1,​

where PcP_cPc​ and EEE are pairUp and hasEqualPair as unfolded above, ∨\lor∨ is Boolean "or", and headz(hs)\mathrm{head}_z(hs)headz​(hs) is the first entry of hshshs if hshshs is nonempty and is the default value zzz if hs=[ ]hs = [\,]hs=[]. Thus: on each pass where the current list has at least two entries, the flag is updated to m∨E(hs)m \lor E(hs)m∨E(hs) (with EEE evaluated on the current list, before pairing), the list is replaced by Pc(hs)P_c(hs)Pc​(hs), and the loop repeats; once the list has at most one entry, the loop stops and returns the pair (first-or-zzz, current flag). In particular Rc,z([ ],m)=(z,m)R_{c,z}([\,], m) = (z, m)Rc,z​([],m)=(z,m) and Rc,z([a],m)=(a,m)R_{c,z}([a], m) = (a, m)Rc,z​([a],m)=(a,m) for every aaa and mmm; a singleton input is returned unchanged in its first component, not as c(a,a)c(a,a)c(a,a). Because the flag is only ever combined with ∨\lor∨, once it is true\mathrm{true}true it remains true\mathrm{true}true through all subsequent passes. The loop condition is strictly 1<∣hs∣1 < |hs|1<∣hs∣ (so it runs precisely when ∣hs∣≥2|hs| \ge 2∣hs∣≥2). Termination is justified by the fact that ∣Pc(hs)∣=⌊(∣hs∣+1)/2⌋<∣hs∣|P_c(hs)| = \lfloor(|hs|+1)/2\rfloor < |hs|∣Pc​(hs)∣=⌊(∣hs∣+1)/2⌋<∣hs∣ whenever ∣hs∣≥2|hs| \ge 2∣hs∣≥2. The hypothesis name attached to the if test is unused in the body.


computeMerkleRoot

For fixed c:H→H→Hc : H \to H \to Hc:H→H→H and z∈Hz \in Hz∈H, computeMerkleRoot is the function Mc,zM_{c,z}Mc,z​ from finite lists over HHH to H×{true,false}H \times \{\mathrm{true}, \mathrm{false}\}H×{true,false} given by

Mc,z(hs)=Rc,z(hs,false),M_{c,z}(hs) = R_{c,z}(hs, \mathrm{false}),Mc,z​(hs)=Rc,z​(hs,false),

i.e. rootLoop as unfolded above, started with the mutation flag equal to false\mathrm{false}false. Its first component (Mc,z(hs)).1∈H(M_{c,z}(hs)).1 \in H(Mc,z​(hs)).1∈H is the value left after repeatedly applying PcP_cPc​ until at most one entry remains (or zzz if hshshs was empty), and its second component (Mc,z(hs)).2(M_{c,z}(hs)).2(Mc,z​(hs)).2 is the Boolean "or" of EEE evaluated on hshshs and on every intermediate level that had at least two entries. For the empty list the result is (z,false)(z, \mathrm{false})(z,false); for a singleton [a][a][a] it is (a,false)(a, \mathrm{false})(a,false). No assumption on ccc, zzz, or hshshs (length, distinctness, etc.) is built into the definition.

Human review
  • Endorsed by Shuze Chen · Oct 26, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Oct 26, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me