Equal tagged hashes have equal tag hashes and messages, or exhibit a SHA-256 collision
ProvedBitcoinTapSoundness.tagged_collisionFor tags and messages : if tagged t m = tagged t' m' then either sha256 (ascii t) = sha256 (ascii t') and , or Sha256Collision. The tagged hash is sha256 (sha256 tag ++ sha256 tag ++ m) and sha256 always returns 32 bytes, so equal outer digests of different inputs are a collision and equal inputs split at the 64-byte boundary.
Deprecated. Superseded by BitcoinTapSoundnessV2.tagged_collision (revision 2, BitcoinTapSoundnessV2): this revision's collision alternatives were closed propositions (Sha256Collision, and TweakCollision without a length constraint), which are provable by counting and so made the statement trivially true; the V2 declarations name the colliding strings and the two 32-byte tweaks explicitly, computed from the inputs.
import Definitions.Def_BitcoinTapSoundness import Definitions.Def_BitcoinSer import Definitions.Def_BitcoinTaproot import Definitions.Def_BitcoinSig open BitcoinTapSoundness BitcoinSer BitcoinTaproot
theorem BitcoinTapSoundness.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') ∨
BitcoinTapSoundness.Sha256Collision := 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: BitcoinTapSoundness.tagged_collision
Statement. For every pair of strings (arbitrary Unicode strings, possibly empty, possibly equal) and every pair of byte strings (finite sequences of 8-bit values, of any lengths, possibly empty), if
then at least one of the following holds:
- and (equality of byte strings, so in particular ); or
- holds, i.e. there exist two byte strings (of any lengths, not necessarily the same length, and unrelated to ) with .
The first disjunct does not require ; it only requires that the digests of their UTF-8 encodings agree.
Unfolded notions.
- is the list of bytes of the UTF-8 encoding of the string .
- is the bundle's own executable implementation of SHA-256 (Merkle–Damgård padding with , zero bytes, and the 64-bit big-endian bit length; 64 compression rounds with the standard constants; a 32-byte big-endian digest). It is a total function defined on every finite byte string, not an abstract or axiomatized hash.
- The tagged hash is
where is concatenation of byte strings. Because every digest is 32 bytes long, the input to the outer always begins with a 64-byte prefix followed by .
- is a closed proposition (it has no parameters and does not depend on ):
Since here is a fixed total function from the infinite set of byte strings to the finite set of 32-byte strings, the truth value of this proposition is a fixed mathematical fact (by counting, such a pair exists); it is not a hypothesis, assumption, or axiom of the theorem.
Edge cases made explicit. No hypothesis constrains the lengths of or the contents of . If and the hypothesis holds trivially and the first disjunct holds. The theorem does not assert anything about versus as strings, only about the SHA-256 digests of their UTF-8 encodings.