Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A leaf hash equal to a branch hash: the TapLeaf and TapBranch preimages collide

Proved
BitcoinTapSoundnessV2.leaf_ne_branch

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

bip341bitcoinbitcoin-mainnetcollisionformal-verificationmerklesoundnesstagged-hashtaproot

For any leaf version vvv, script sss and byte strings a,ba, ba,b: tapleafHash v s = tapbranchHash a b implies Collides (taggedPre "TapLeaf" (leafMsg v s)) (taggedPre "TapBranch" (branchMsg a b)). The two strings differ in their first 32 bytes (tapleaf_ne_tapbranch).

Preamble
import Definitions.Def_BitcoinTapSoundnessV2
import Definitions.Def_BitcoinSer
import Definitions.Def_BitcoinTaproot
open BitcoinTapSoundnessV2 BitcoinSer BitcoinTaproot
Formal statement
theorem BitcoinTapSoundnessV2.leaf_ne_branch (v : BitcoinSer.Byte) (s a b : BitcoinSer.Bytes)
    (h : BitcoinTaproot.tapleafHash v s = BitcoinTaproot.tapbranchHash a b) :
    BitcoinTapSoundnessV2.Collides (BitcoinTapSoundnessV2.taggedPre "TapLeaf" (BitcoinTapSoundnessV2.leafMsg v s))
      (BitcoinTapSoundnessV2.taggedPre "TapBranch" (BitcoinTapSoundnessV2.branchMsg a b)) := by sorry
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: VerifyTaprootCommitment, ComputeTaprootMerkleRoot, ComputeTapleafHash, ComputeTapbranchHash (src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp); XOnlyPubKey::CheckTapTweak, ComputeTapTweakHash (src/pubkey.cpp); secp256k1_xonly_pubkey_tweak_add_check; BIP341
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: BitcoinTapSoundnessV2.leaf_ne_branch

Statement. For every byte vvv (an 8-bit vector) and all byte strings s,a,bs, a, bs,a,b (finite lists of bytes, of any length including empty), if

tapleafHash(v,s)=tapbranchHash(a,b),\mathrm{tapleafHash}(v, s) = \mathrm{tapbranchHash}(a, b),tapleafHash(v,s)=tapbranchHash(a,b),

then

Collides(taggedPre("TapLeaf",leafMsg(v,s)),  taggedPre("TapBranch",branchMsg(a,b))).\mathrm{Collides}\big(\mathrm{taggedPre}(\text{"TapLeaf"}, \mathrm{leafMsg}(v, s)),\; \mathrm{taggedPre}(\text{"TapBranch"}, \mathrm{branchMsg}(a, b))\big).Collides(taggedPre("TapLeaf",leafMsg(v,s)),taggedPre("TapBranch",branchMsg(a,b))).

Unfoldings. SHA256\mathrm{SHA256}SHA256 is the bundle's executable SHA-256 (MD padding with 0x80\mathtt{0x80}0x80, zeros to 56 mod 6456 \bmod 6456mod64, 8-byte big-endian bit length; compression of each 64-byte chunk from the standard initial state; eight big-endian 32-bit words out), a total function on byte strings. ascii(t)\mathrm{ascii}(t)ascii(t) is the UTF-8 byte list of the string ttt. tagged(t,m)=SHA256(SHA256(ascii(t))∥SHA256(ascii(t))∥m)\mathrm{tagged}(t, m) = \mathrm{SHA256}\big(\mathrm{SHA256}(\mathrm{ascii}(t)) \| \mathrm{SHA256}(\mathrm{ascii}(t)) \| m\big)tagged(t,m)=SHA256(SHA256(ascii(t))∥SHA256(ascii(t))∥m) and taggedPre(t,m)=SHA256(ascii(t))∥SHA256(ascii(t))∥m\mathrm{taggedPre}(t, m) = \mathrm{SHA256}(\mathrm{ascii}(t)) \| \mathrm{SHA256}(\mathrm{ascii}(t)) \| mtaggedPre(t,m)=SHA256(ascii(t))∥SHA256(ascii(t))∥m.

writeCompactSize(n)\mathrm{writeCompactSize}(n)writeCompactSize(n) is one byte nnn if n<253n < 253n<253; byte 253253253 then 2 little-endian bytes of nnn if n≤0xffffn \le \mathtt{0xffff}n≤0xffff; byte 254254254 then 4 LE bytes if n≤0xffffffffn \le \mathtt{0xffffffff}n≤0xffffffff; else byte 255255255 then 8 LE bytes. leafMsg(v,s)=[v]∥writeCompactSize(∣s∣)∥s\mathrm{leafMsg}(v, s) = [v] \| \mathrm{writeCompactSize}(|s|) \| sleafMsg(v,s)=[v]∥writeCompactSize(∣s∣)∥s, and tapleafHash(v,s)=tagged("TapLeaf",leafMsg(v,s))\mathrm{tapleafHash}(v, s) = \mathrm{tagged}(\text{"TapLeaf"}, \mathrm{leafMsg}(v, s))tapleafHash(v,s)=tagged("TapLeaf",leafMsg(v,s)).

lexLt\mathrm{lexLt}lexLt is the Boolean strict lexicographic order on byte strings ([][][] is below any non-empty string; otherwise compare leading bytes and recurse on ties; lexLt(x,x)\mathrm{lexLt}(x, x)lexLt(x,x) is false). branchMsg(a,b)=a∥b\mathrm{branchMsg}(a, b) = a \| bbranchMsg(a,b)=a∥b if lexLt(a,b)\mathrm{lexLt}(a, b)lexLt(a,b), else b∥ab \| ab∥a. tapbranchHash(a,b)=tagged("TapBranch",branchMsg(a,b))\mathrm{tapbranchHash}(a, b) = \mathrm{tagged}(\text{"TapBranch"}, \mathrm{branchMsg}(a, b))tapbranchHash(a,b)=tagged("TapBranch",branchMsg(a,b)).

Collides(x,y)\mathrm{Collides}(x, y)Collides(x,y) is x≠y∧SHA256(x)=SHA256(y)x \neq y \wedge \mathrm{SHA256}(x) = \mathrm{SHA256}(y)x=y∧SHA256(x)=SHA256(y).

Edge cases and what is silently included. There are no length hypotheses: sss, aaa and bbb may have any length (including 000), and a,ba, ba,b need not be 32 bytes or hashes of anything; vvv may be any byte. The conclusion names two explicit strings — the "TapLeaf"-prefixed preimage of the leaf hash, SHA256(ascii("TapLeaf"))2∥[v]∥writeCompactSize(∣s∣)∥s\mathrm{SHA256}(\mathrm{ascii}(\text{"TapLeaf"}))^{2} \| [v] \| \mathrm{writeCompactSize}(|s|) \| sSHA256(ascii("TapLeaf"))2∥[v]∥writeCompactSize(∣s∣)∥s, and the "TapBranch"-prefixed preimage of the branch hash, SHA256(ascii("TapBranch"))2∥branchMsg(a,b)\mathrm{SHA256}(\mathrm{ascii}(\text{"TapBranch"}))^{2} \| \mathrm{branchMsg}(a, b)SHA256(ascii("TapBranch"))2∥branchMsg(a,b) (where X2X^2X2 abbreviates X∥XX \| XX∥X) — and asserts (i) they are different byte strings and (ii) their SHA-256 outputs coincide. Part (ii) is, by unfolding, the hypothesis itself; part (i) is the additional content. The two strings differ in their first 64 bytes exactly when SHA256(ascii("TapLeaf"))≠SHA256(ascii("TapBranch"))\mathrm{SHA256}(\mathrm{ascii}(\text{"TapLeaf"})) \neq \mathrm{SHA256}(\mathrm{ascii}(\text{"TapBranch"}))SHA256(ascii("TapLeaf"))=SHA256(ascii("TapBranch")), which this theorem does not itself assert.

Human review
  • Endorsed by Shuze Chen · Nov 20, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Nov 20, 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