Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

CVE-2012-2459 in general: duplicating an aligned trailing block

Proved
BitcoinMerkle.dup_block

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

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

For every pairwise hash ccc, zero hash zzz, level k∈Nk \in \mathbb Nk∈N, non-empty list ℓ\ellℓ whose length is a multiple of 2k+12^{k+1}2k+1, and block ttt of exactly 2k2^{k}2k hashes,

root(ℓ+ ⁣ ⁣+t)=root(ℓ+ ⁣ ⁣+t+ ⁣ ⁣+t)andmutated(ℓ+ ⁣ ⁣+t+ ⁣ ⁣+t)=true,\mathrm{root}(\ell \mathbin{+\!\!+} t) = \mathrm{root}(\ell \mathbin{+\!\!+} t \mathbin{+\!\!+} t) \qquad\text{and}\qquad \mathrm{mutated}(\ell \mathbin{+\!\!+} t \mathbin{+\!\!+} t) = \mathtt{true},root(ℓ++t)=root(ℓ++t++t)andmutated(ℓ++t++t)=true,

where root and mutated are the two components of computeMerkleRootc,z\mathrm{computeMerkleRoot}_{c,z}computeMerkleRootc,z​, the transcription of ComputeMerkleRoot.

Under the alignment hypotheses, ttt occupies a complete aligned subtree that collapses to a single node after kkk levels; at that level ℓ+ ⁣ ⁣+t\ell \mathbin{+\!\!+} tℓ++t has odd length and the source duplicates the node, while ℓ+ ⁣ ⁣+t+ ⁣ ⁣+t\ell \mathbin{+\!\!+} t \mathbin{+\!\!+} tℓ++t++t already carries the copy as an equal aligned pair. The two computations then coincide, and the copy is detected by the per-level check. With k=0k = 0k=0 this is the duplicated last transaction; with k=1k = 1k=1 and ℓ\ellℓ of length four it is the [1,2,3,4,5,6][1,2,3,4,5,6][1,2,3,4,5,6] versus [1,2,3,4,5,6,5,6][1,2,3,4,5,6,5,6][1,2,3,4,5,6,5,6] example of the source comment.

This is the general statement of the defence against CVE-2012-2459: every duplication of this shape is root-preserving, which is the attack, and is flagged, which is the defence. Nothing is assumed about ccc; the result is about the loop structure alone.

Formalization Note. The non-emptiness of ℓ\ellℓ is necessary, since a single-node list is returned without processing while its doubled form is hashed once more. The statement is proved for the loop with an arbitrary incoming flag and specialized to computeMerkleRoot.

Preamble
import Definitions.Def_BitcoinMerkle
Formal statement
theorem BitcoinMerkle.dup_block {H : Type} [DecidableEq H] (c : H → H → H) (z : H) :
    ∀ (k : Nat) (l t : List H), l ≠ [] → l.length % 2 ^ (k + 1) = 0 → t.length = 2 ^ k →
      (BitcoinMerkle.computeMerkleRoot c z (l ++ t)).1 = (BitcoinMerkle.computeMerkleRoot c z (l ++ t ++ t)).1 ∧
      (BitcoinMerkle.computeMerkleRoot c z (l ++ t ++ t)).2 = true := 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.dup_block

Binders and assumptions. HHH is an arbitrary type with decidable equality (for x,y∈Hx, y \in Hx,y∈H the Boolean [x=y][x = y][x=y] is true\mathrm{true}true exactly when x=yx = yx=y). c:H→H→Hc : H \to H \to Hc:H→H→H is an arbitrary two-argument operation and z∈Hz \in Hz∈H an arbitrary element; nothing whatsoever is assumed about ccc or zzz. The theorem then universally quantifies over a natural number k≥0k \ge 0k≥0 and two finite lists l,tl, tl,t over HHH, subject to three hypotheses:

  1. l≠[ ]l \neq [\,]l=[] (lll is nonempty);
  2. ∣l∣ mod 2k+1=0|l| \bmod 2^{k+1} = 0∣l∣mod2k+1=0 (the length of lll is a multiple of 2k+12^{k+1}2k+1; together with (1) this forces ∣l∣≥2k+1|l| \ge 2^{k+1}∣l∣≥2k+1);
  3. ∣t∣=2k|t| = 2^k∣t∣=2k (so ttt is automatically nonempty, having at least one entry; its entries are arbitrary and need not be distinct).

Under these hypotheses the conclusion is the conjunction

(Mc,z(l+ ⁣ ⁣+t)).1  =  (Mc,z(l+ ⁣ ⁣+t+ ⁣ ⁣+t)).1and(Mc,z(l+ ⁣ ⁣+t+ ⁣ ⁣+t)).2  =  true,\bigl(M_{c,z}(l \mathbin{+\!\!+} t)\bigr).1 \;=\; \bigl(M_{c,z}(l \mathbin{+\!\!+} t \mathbin{+\!\!+} t)\bigr).1 \quad\text{and}\quad \bigl(M_{c,z}(l \mathbin{+\!\!+} t \mathbin{+\!\!+} t)\bigr).2 \;=\; \mathrm{true},(Mc,z​(l++t)).1=(Mc,z​(l++t++t)).1and(Mc,z​(l++t++t)).2=true,

where + ⁣ ⁣++\!\!+++ is list concatenation (so l+ ⁣ ⁣+t+ ⁣ ⁣+tl +\!\!+ t +\!\!+ tl++t++t is lll followed by two consecutive copies of ttt), (⋅).1∈H(\cdot).1 \in H(⋅).1∈H is the first component of the pair and (⋅).2(\cdot).2(⋅).2 its Boolean second component.

Unfolding Mc,zM_{c,z}Mc,z​ (computeMerkleRoot). Mc,z(hs)=Rc,z(hs,false)M_{c,z}(hs) = R_{c,z}(hs, \mathrm{false})Mc,z​(hs)=Rc,z​(hs,false), where Rc,zR_{c,z}Rc,z​ (rootLoop) is defined on a list hshshs and Boolean flag mmm by

Rc,z(hs,m)={Rc,z(Pc(hs), m∨E(hs))if 1<∣hs∣,(headz(hs), m)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|,\\ \bigl(\mathrm{head}_z(hs),\ m\bigr) & \text{if } |hs| \le 1, \end{cases}Rc,z​(hs,m)={Rc,z​(Pc​(hs), m∨E(hs))(headz​(hs), m)​if 1<∣hs∣,if ∣hs∣≤1,​

with headz(hs)\mathrm{head}_z(hs)headz​(hs) the first entry of hshshs, or zzz if hshshs is empty, and ∨\lor∨ Boolean "or". Here PcP_cPc​ (pairUp) is given by Pc(a::b::r)=c(a,b)::Pc(r)P_c(a :: b :: r) = c(a,b) :: P_c(r)Pc​(a::b::r)=c(a,b)::Pc​(r), Pc([a])=[c(a,a)]P_c([a]) = [c(a,a)]Pc​([a])=[c(a,a)], Pc([ ])=[ ]P_c([\,]) = [\,]Pc​([])=[] — adjacent aligned pairs are combined by ccc, and an odd trailing element is combined with itself. EEE (hasEqualPair) is the Boolean E(a::b::r)=[a=b]∨E(r)E(a :: b :: r) = [a = b] \lor E(r)E(a::b::r)=[a=b]∨E(r) and E([ ])=E([a])=falseE([\,]) = E([a]) = \mathrm{false}E([])=E([a])=false; that is, E([x0,…,xn−1])=trueE([x_0,\dots,x_{n-1}]) = \mathrm{true}E([x0​,…,xn−1​])=true iff some even iii with i+1<ni+1 < ni+1<n has xi=xi+1x_i = x_{i+1}xi​=xi+1​ — only aligned positions (0,1),(2,3),…(0,1),(2,3),\dots(0,1),(2,3),… are tested, never (1,2)(1,2)(1,2), never a non-adjacent pair, and never the trailing element of an odd-length list against itself.

What is and is not claimed. The first conjunct equates only the first components (the elements of HHH) of the two results; it says nothing about the second component of Mc,z(l+ ⁣ ⁣+t)M_{c,z}(l +\!\!+ t)Mc,z​(l++t), which may be true\mathrm{true}true or false\mathrm{false}false. The second conjunct asserts that the Boolean flag for the input with the duplicated block is true\mathrm{true}true — i.e. at some level of the iteration (the input itself or some PcP_cPc​-image of it with at least two entries) some aligned pair (2i,2i+1)(2i, 2i+1)(2i,2i+1) consists of equal elements. No claim is made about inputs where lll is empty, where ∣l∣|l|∣l∣ is not a multiple of 2k+12^{k+1}2k+1, or where ∣t∣≠2k|t| \neq 2^k∣t∣=2k. The hypotheses are jointly satisfiable (e.g. ∣l∣=2k+1|l| = 2^{k+1}∣l∣=2k+1, ∣t∣=2k|t| = 2^k∣t∣=2k), so the statement is not vacuous. The case k=0k = 0k=0 reads: lll nonempty of even length, ttt a single element. The statement holds for every ccc, including degenerate ones such as constant functions or c(x,y)=xc(x,y) = xc(x,y)=x.

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