Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

One level distributes over an even split

Proved
BitcoinMerkle.pairUp_append_even

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

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

For every ccc and lists ℓ,r\ell, rℓ,r with ∣ℓ∣|\ell|∣ℓ∣ even, pairUpc(ℓ+ ⁣ ⁣+r)=pairUpc(ℓ)+ ⁣ ⁣+pairUpc(r)\mathrm{pairUp}_c(\ell \mathbin{+\!\!+} r) = \mathrm{pairUp}_c(\ell) \mathbin{+\!\!+} \mathrm{pairUp}_c(r)pairUpc​(ℓ++r)=pairUpc​(ℓ)++pairUpc​(r). When the prefix has even length the pair boundaries of the concatenation align with those of the two parts, so a level can be computed blockwise. The hypothesis is necessary: an odd prefix would pair its last element with the first element of rrr.

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

Binders and assumptions. The statement is about an arbitrary type HHH (implicit), equipped with a decidable-equality structure on HHH (an instance assumption that is part of the theorem's hypotheses, even though the conclusion below never tests two elements of HHH for equality), and an arbitrary function c:H×H→Hc : H \times H \to Hc:H×H→H (explicit, written c(a,b)c(a,b)c(a,b) below; no property of ccc is assumed — it need not be associative, commutative, injective, or anything else). The theorem then 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 (a natural number) is even. This includes ∣l∣=0|l| = 0∣l∣=0, the empty list. There is no hypothesis on the length of rrr: rrr may be empty, of even length, or of odd length. The hypothesis is satisfiable (e.g. l=[]l = []l=[] or any two-element list), so the theorem is not vacuous.

The function being compared. pairUpc\mathrm{pairUp}_cpairUpc​ is the bundle's own function from lists over HHH to lists over HHH, defined by recursion on the list with three cases:

  • pairUpc(a::b::rest)=c(a,b)::pairUpc(rest)\mathrm{pairUp}_c(a :: b :: \mathit{rest}) = c(a,b) :: \mathrm{pairUp}_c(\mathit{rest})pairUpc​(a::b::rest)=c(a,b)::pairUpc​(rest) — if the list has at least two elements, hash the first two together with ccc and recurse on the remainder;
  • pairUpc([a])=[ c(a,a) ]\mathrm{pairUp}_c([a]) = [\,c(a,a)\,]pairUpc​([a])=[c(a,a)] — a single leftover element is hashed with itself;
  • pairUpc([])=[]\mathrm{pairUp}_c([]) = []pairUpc​([])=[] — the empty list maps to the empty list.

So pairUpc\mathrm{pairUp}_cpairUpc​ splits its input into consecutive aligned pairs (x0,x1),(x2,x3),…(x_0,x_1), (x_2,x_3), \dots(x0​,x1​),(x2​,x3​),…, replaces each by c(x2i,x2i+1)c(x_{2i}, x_{2i+1})c(x2i​,x2i+1​), and if the length is odd replaces the final unpaired element xn−1x_{n-1}xn−1​ by c(xn−1,xn−1)c(x_{n-1},x_{n-1})c(xn−1​,xn−1​). The output has length ⌊(∣⋅∣+1)/2⌋\lfloor (|{\cdot}|+1)/2 \rfloor⌊(∣⋅∣+1)/2⌋.

Conclusion. Under the hypothesis that ∣l∣|l|∣l∣ is even, the theorem asserts the following equality of lists over HHH (where + ⁣ ⁣++\!\!+++ is list concatenation):

pairUpc(l+ ⁣ ⁣+r)  =  pairUpc(l)  + ⁣ ⁣+  pairUpc(r).\mathrm{pairUp}_c(l +\!\!+ r) \;=\; \mathrm{pairUp}_c(l) \;+\!\!+\; \mathrm{pairUp}_c(r).pairUpc​(l++r)=pairUpc​(l)++pairUpc​(r).

In words: pairing-up the concatenation of lll and rrr yields exactly the same list as pairing-up lll and pairing-up rrr separately and concatenating the two results. This is an equality of lists, so it asserts equal length and element-wise equality, in order.

What happens at the boundary. Because ∣l∣|l|∣l∣ is even, every element of lll falls into a complete aligned pair inside lll, and the first element of rrr (if any) begins a new pair at an even position of l+ ⁣ ⁣+rl +\!\!+ rl++r. Consequently no pair (x2i,x2i+1)(x_{2i}, x_{2i+1})(x2i​,x2i+1​) of the concatenated list straddles the join between lll and rrr. If ∣r∣|r|∣r∣ is odd, the last element of rrr is the unpaired trailing element both of rrr alone and of l+ ⁣ ⁣+rl +\!\!+ rl++r, and is sent to c(x,x)c(x,x)c(x,x) on both sides. If r=[]r = []r=[], both sides reduce to pairUpc(l)\mathrm{pairUp}_c(l)pairUpc​(l). If l=[]l = []l=[], both sides reduce to pairUpc(r)\mathrm{pairUp}_c(r)pairUpc​(r).

What the statement does not cover. The theorem says nothing when ∣l∣|l|∣l∣ is odd; in that case the hypothesis fails and no claim is made. It also makes no claim about hasEqualPair\mathrm{hasEqualPair}hasEqualPair, about rootLoop\mathrm{rootLoop}rootLoop, or about computeMerkleRoot\mathrm{computeMerkleRoot}computeMerkleRoot; it concerns only the single-level function pairUpc\mathrm{pairUp}_cpairUpc​ and holds for every choice of ccc whatsoever.

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