One level distributes over an even split
ProvedBitcoinMerkle.pairUp_append_evenFor every and lists with even, . 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 .
import Definitions.Def_BitcoinMerkle
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 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.pairUp_append_even
Binders and assumptions. The statement is about an arbitrary type (implicit), equipped with a decidable-equality structure on (an instance assumption that is part of the theorem's hypotheses, even though the conclusion below never tests two elements of for equality), and an arbitrary function (explicit, written below; no property of is assumed — it need not be associative, commutative, injective, or anything else). The theorem then universally quantifies over two finite lists and of elements of , and takes one hypothesis:
i.e. the length of (a natural number) is even. This includes , the empty list. There is no hypothesis on the length of : may be empty, of even length, or of odd length. The hypothesis is satisfiable (e.g. or any two-element list), so the theorem is not vacuous.
The function being compared. is the bundle's own function from lists over to lists over , defined by recursion on the list with three cases:
- — if the list has at least two elements, hash the first two together with and recurse on the remainder;
- — a single leftover element is hashed with itself;
- — the empty list maps to the empty list.
So splits its input into consecutive aligned pairs , replaces each by , and if the length is odd replaces the final unpaired element by . The output has length .
Conclusion. Under the hypothesis that is even, the theorem asserts the following equality of lists over (where is list concatenation):
In words: pairing-up the concatenation of and yields exactly the same list as pairing-up and pairing-up 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 is even, every element of falls into a complete aligned pair inside , and the first element of (if any) begins a new pair at an even position of . Consequently no pair of the concatenated list straddles the join between and . If is odd, the last element of is the unpaired trailing element both of alone and of , and is sent to on both sides. If , both sides reduce to . If , both sides reduce to .
What the statement does not cover. The theorem says nothing when is odd; in that case the hypothesis fails and no claim is made. It also makes no claim about , about , or about ; it concerns only the single-level function and holds for every choice of whatsoever.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.