Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The mutation test distributes over an even split

Proved
BitcoinMerkle.hasEqualPair_append_even

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

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

For all lists ℓ,r\ell, rℓ,r with ∣ℓ∣|\ell|∣ℓ∣ even, hasEqualPair(ℓ+ ⁣ ⁣+r)=hasEqualPair(ℓ)∨hasEqualPair(r)\mathrm{hasEqualPair}(\ell \mathbin{+\!\!+} r) = \mathrm{hasEqualPair}(\ell) \lor \mathrm{hasEqualPair}(r)hasEqualPair(ℓ++r)=hasEqualPair(ℓ)∨hasEqualPair(r). With aligned pair boundaries, an equal aligned pair of the concatenation lies entirely in ℓ\ellℓ or entirely in rrr.

Preamble
import Definitions.Def_BitcoinMerkle
Formal statement
theorem BitcoinMerkle.hasEqualPair_append_even {H : Type} [DecidableEq H] :
    ∀ (l r : List H), l.length % 2 = 0 →
      BitcoinMerkle.hasEqualPair (l ++ r) = (BitcoinMerkle.hasEqualPair l || BitcoinMerkle.hasEqualPair r) := by sorry
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: BitcoinMerkle.hasEqualPair_append_even

Binders and assumptions. The statement is about an arbitrary type HHH (implicit) together with a decidable-equality structure on HHH (an instance assumption; it is used below, since the predicate being discussed tests elements of HHH for equality and the result is a Boolean, so each test a=ba = ba=b must be computable as true or false). Unlike the companion pairUp theorem, there is no pairwise-hash function ccc in this statement. The theorem universally quantifies over two finite lists lll and rrr of elements of HHH and takes one hypothesis:

∣l∣ mod 2=0,|l| \bmod 2 = 0,∣l∣mod2=0,

i.e. the length of lll is an even natural number, which includes ∣l∣=0|l| = 0∣l∣=0. There is no hypothesis on ∣r∣|r|∣r∣: it may be zero, even, or odd. The hypothesis is satisfiable, so the theorem is not vacuous.

The predicate being compared. hasEqualPair\mathrm{hasEqualPair}hasEqualPair is the bundle's own Boolean-valued function on lists over HHH, defined by recursion with the following cases:

  • hasEqualPair(a::b::rest)=[a=b]  ∨  hasEqualPair(rest)\mathrm{hasEqualPair}(a :: b :: \mathit{rest}) = [a = b] \;\lor\; \mathrm{hasEqualPair}(\mathit{rest})hasEqualPair(a::b::rest)=[a=b]∨hasEqualPair(rest) — if the list has at least two elements, the answer is true exactly when the first two elements are equal, or (Boolean disjunction) when the recursive call on the remainder is true;
  • hasEqualPair([a])=false\mathrm{hasEqualPair}([a]) = \mathrm{false}hasEqualPair([a])=false — a single leftover element is never flagged (it is not compared with anything, and in particular not with itself);
  • hasEqualPair([])=false\mathrm{hasEqualPair}([]) = \mathrm{false}hasEqualPair([])=false — the empty list is not flagged.

(The last two cases are written in the source as a single catch-all pattern covering every list of length 000 or 111.) Here [a=b][a = b][a=b] denotes the Boolean value of the decidable proposition a=ba = ba=b. Thus, writing the list as x0,x1,…,xn−1x_0, x_1, \dots, x_{n-1}x0​,x1​,…,xn−1​, hasEqualPair\mathrm{hasEqualPair}hasEqualPair is true if and only if there exists an index iii with 2i+1<n2i+1 < n2i+1<n and x2i=x2i+1x_{2i} = x_{2i+1}x2i​=x2i+1​; it inspects only the aligned pairs (x0,x1),(x2,x3),…(x_0,x_1),(x_2,x_3),\dots(x0​,x1​),(x2​,x3​),… and never the pairs (x1,x2),(x3,x4),…(x_1,x_2),(x_3,x_4),\dots(x1​,x2​),(x3​,x4​),…, nor an unpaired trailing element when nnn is odd.

Conclusion. Under the hypothesis that ∣l∣|l|∣l∣ is even, the theorem asserts the following equality of Boolean values (where + ⁣ ⁣++\!\!+++ is list concatenation and ∨\lor∨ is Boolean "or"):

hasEqualPair(l+ ⁣ ⁣+r)  =  hasEqualPair(l)  ∨  hasEqualPair(r).\mathrm{hasEqualPair}(l +\!\!+ r) \;=\; \mathrm{hasEqualPair}(l) \;\lor\; \mathrm{hasEqualPair}(r).hasEqualPair(l++r)=hasEqualPair(l)∨hasEqualPair(r).

Since both sides are Booleans, this is a two-way statement: the concatenation is flagged if and only if lll is flagged or rrr is flagged (or both). Equivalently, in terms of the index description above: there is an aligned equal pair in l+ ⁣ ⁣+rl +\!\!+ rl++r exactly when there is one within lll or one within rrr, with "aligned" measured from the start of the respective list.

What happens at the boundary. Because ∣l∣|l|∣l∣ is even, the aligned pairs of l+ ⁣ ⁣+rl +\!\!+ rl++r are exactly the aligned pairs of lll followed by the aligned pairs of rrr (shifted by ∣l∣|l|∣l∣, which is even, so alignment is preserved): no inspected pair consists of the last element of lll and the first element of rrr. If ∣r∣|r|∣r∣ is odd, the final element of rrr is uninspected both in rrr alone and in l+ ⁣ ⁣+rl +\!\!+ rl++r. If r=[]r = []r=[], the right-hand side is hasEqualPair(l)∨false\mathrm{hasEqualPair}(l) \lor \mathrm{false}hasEqualPair(l)∨false and the left-hand side is hasEqualPair(l)\mathrm{hasEqualPair}(l)hasEqualPair(l). If l=[]l = []l=[], the right-hand side is false∨hasEqualPair(r)\mathrm{false} \lor \mathrm{hasEqualPair}(r)false∨hasEqualPair(r) and the left-hand side is hasEqualPair(r)\mathrm{hasEqualPair}(r)hasEqualPair(r).

What the statement does not cover. No claim is made when ∣l∣|l|∣l∣ is odd. The theorem concerns only this one-level predicate; it does not mention pairUp\mathrm{pairUp}pairUp, rootLoop\mathrm{rootLoop}rootLoop, computeMerkleRoot\mathrm{computeMerkleRoot}computeMerkleRoot, or the running mutation flag that those definitions thread through repeated levels.

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