Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A tagged hash is the SHA-256 of its preimage

Proved
BitcoinTapSoundnessV2.tagged_pre

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

bip341bitcoinbitcoin-mainnetcollisionformal-verificationmerklesoundnesstagged-hashtaproot

tagged t m = sha256 (taggedPre t m), by definition of taggedHash.

Preamble
import Definitions.Def_BitcoinTapSoundnessV2
import Definitions.Def_BitcoinSer
import Definitions.Def_BitcoinTaproot
open BitcoinTapSoundnessV2 BitcoinSer BitcoinTaproot
Formal statement
theorem BitcoinTapSoundnessV2.tagged_pre (t : String) (m : BitcoinSer.Bytes) :
    BitcoinTaproot.tagged t m = BitcoinSer.sha256 (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_pre

Statement. For every string ttt and every byte string mmm (a finite list of 8-bit bytes, of any length including empty),

tagged(t,m)  =  SHA256(taggedPre(t,m)).\mathrm{tagged}(t, m) \;=\; \mathrm{SHA256}\big(\mathrm{taggedPre}(t, m)\big).tagged(t,m)=SHA256(taggedPre(t,m)).

Unfoldings. SHA256\mathrm{SHA256}SHA256 is the bundle's executable SHA-256: a total function on byte strings that appends the byte 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; splits into 64-byte chunks; folds the SHA-256 compression function over them from the standard initial state; and emits the eight 32-bit state words as big-endian 4-byte groups. ascii(t)\mathrm{ascii}(t)ascii(t) is the list of UTF-8 code units of ttt, each as a byte.

The left-hand side, tagged(t,m)\mathrm{tagged}(t, m)tagged(t,m), is defined in the preamble as taggedHash(ascii(t),m)\mathrm{taggedHash}(\mathrm{ascii}(t), m)taggedHash(ascii(t),m), where taggedHash(tag,m)\mathrm{taggedHash}(\mathit{tag}, m)taggedHash(tag,m) lets θ=SHA256(tag)\theta = \mathrm{SHA256}(\mathit{tag})θ=SHA256(tag) and returns SHA256(θ∥θ∥m)\mathrm{SHA256}(\theta \| \theta \| m)SHA256(θ∥θ∥m); so

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).

The right-hand side uses 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, so the right-hand side is

SHA256(SHA256(ascii(t)) ∥ SHA256(ascii(t)) ∥ m).\mathrm{SHA256}\big(\mathrm{SHA256}(\mathrm{ascii}(t)) \,\|\, \mathrm{SHA256}(\mathrm{ascii}(t)) \,\|\, m\big).SHA256(SHA256(ascii(t))∥SHA256(ascii(t))∥m).

Edge cases and what is silently included. The statement is an equality of byte strings (32-byte outputs of SHA256\mathrm{SHA256}SHA256) with no hypotheses; it holds for the empty string ttt and the empty byte string mmm as well. Both sides unfold to the same expression; the theorem asserts nothing about collisions, distinctness, or any property of SHA256\mathrm{SHA256}SHA256 beyond its being a function.

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