Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Equal tagged hashes have equal tag hashes and messages, or their two preimages collide

Proved
BitcoinTapSoundnessV2.tagged_collision

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

bip341bitcoinbitcoin-mainnetcollisionformal-verificationmerklesoundnesstagged-hashtaproot

For tags t,t′t, t't,t′ and messages m,m′m, m'm,m′: if tagged t m = tagged t' m' then either sha256 (ascii t) = sha256 (ascii t') and m=m′m = m'm=m′, or Collides (taggedPre t m) (taggedPre t' m'): the two explicit 64-byte-prefixed preimages differ and hash alike.

Preamble
import Definitions.Def_BitcoinTapSoundnessV2
import Definitions.Def_BitcoinSer
import Definitions.Def_BitcoinTaproot
import Definitions.Def_BitcoinSig
open BitcoinTapSoundnessV2 BitcoinSer BitcoinTaproot
Formal statement
theorem BitcoinTapSoundnessV2.tagged_collision (t t' : String) (m m' : BitcoinSer.Bytes)
    (h : BitcoinTaproot.tagged t m = BitcoinTaproot.tagged t' m') :
    (BitcoinSer.sha256 (BitcoinSig.ascii t) = BitcoinSer.sha256 (BitcoinSig.ascii t') ∧ m = m') ∨
      BitcoinTapSoundnessV2.Collides (BitcoinTapSoundnessV2.taggedPre t m) (BitcoinTapSoundnessV2.taggedPre t' m') := 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.tagged_collision

Statement. For all strings t,t′t, t't,t′ and all byte strings m,m′m, m'm,m′ (finite lists of 8-bit bytes, any length), if

tagged(t,m)=tagged(t′,m′),\mathrm{tagged}(t, m) = \mathrm{tagged}(t', m'),tagged(t,m)=tagged(t′,m′),

then at least one of the following holds (inclusive disjunction):

  1. SHA256(ascii(t))=SHA256(ascii(t′))\mathrm{SHA256}(\mathrm{ascii}(t)) = \mathrm{SHA256}(\mathrm{ascii}(t'))SHA256(ascii(t))=SHA256(ascii(t′)) and m=m′m = m'm=m′; or
  2. Collides(taggedPre(t,m),  taggedPre(t′,m′))\mathrm{Collides}\big(\mathrm{taggedPre}(t, m),\; \mathrm{taggedPre}(t', m')\big)Collides(taggedPre(t,m),taggedPre(t′,m′)).

Unfoldings. SHA256\mathrm{SHA256}SHA256 is the bundle's executable SHA-256: a total function on byte strings that appends 0x80\mathtt{0x80}0x80, zero bytes until the length is ≡56(mod64)\equiv 56 \pmod{64}≡56(mod64), and the original bit-length as 8 big-endian bytes, then folds the SHA-256 compression function over the 64-byte chunks from the standard initial state and outputs the eight 32-bit state words big-endian (32 bytes). ascii(t)\mathrm{ascii}(t)ascii(t) is the list of UTF-8 code units of the string ttt, each as a byte. tagged(t,m)\mathrm{tagged}(t, m)tagged(t,m) is the preamble's taggedHash(ascii(t),m)\mathrm{taggedHash}(\mathrm{ascii}(t), m)taggedHash(ascii(t),m), i.e.

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, a string of length 64+∣m∣64 + |m|64+∣m∣. 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. Alternative 1 does not assert t=t′t = t't=t′: it asserts only that the two tag strings have the same SHA-256 (which holds in particular when t=t′t = t't=t′, and would also hold for two different strings with colliding hashes) together with m=m′m = m'm=m′. Alternative 2 names the two explicit (64+∣m∣)(64 + |m|)(64+∣m∣)- and (64+∣m′∣)(64 + |m'|)(64+∣m′∣)-byte preimages and asserts that they are different byte strings and have equal SHA-256; the equal-SHA-256 part is, by unfolding, the hypothesis itself, so the additional content of alternative 2 is taggedPre(t,m)≠taggedPre(t′,m′)\mathrm{taggedPre}(t, m) \neq \mathrm{taggedPre}(t', m')taggedPre(t,m)=taggedPre(t′,m′). Either or both alternatives may hold. The strings t,t′t, t't,t′ may be empty, and m,m′m, m'm,m′ may be empty or of different lengths.

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