A leaf hash equal to a branch hash is a SHA-256 collision
ProvedBitcoinTapSoundness.leaf_ne_branchFor any leaf version , script and byte strings : tapleafHash v s = tapbranchHash a b implies Sha256Collision. From tagged_collision and tapleaf_ne_tapbranch.
Deprecated. Superseded by BitcoinTapSoundnessV2.leaf_ne_branch (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 open BitcoinTapSoundness BitcoinSer BitcoinTaproot
theorem BitcoinTapSoundness.leaf_ne_branch (v : BitcoinSer.Byte) (s a b : BitcoinSer.Bytes)
(h : BitcoinTaproot.tapleafHash v s = BitcoinTaproot.tapbranchHash a b) : 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.leaf_ne_branch
Statement. For every byte (an 8-bit value) and all byte strings (finite sequences of 8-bit values, of any lengths, including empty — there are no length hypotheses at all in this theorem), if
then holds, i.e. there exist two byte strings (of any lengths, unrelated to ) with .
Unfolded notions.
- is the bundle's own executable implementation of SHA-256, a total function from all finite byte strings to 32-byte strings.
- is UTF-8 encoding; for a tag string ,
- is Bitcoin's "compact size" encoding of the natural number : the single byte if ; the byte followed by as 2 little-endian bytes if ; the byte followed by 4 little-endian bytes if ; otherwise the byte followed by 8 little-endian bytes of .
- The leaf hash is
where is the one-byte string containing (used as given, with no masking of its low bit).
- is lexicographic order on byte strings (first differing byte decides; a proper prefix is smaller; no string is itself), and
- is the closed proposition ; it does not depend on . Since it concerns a fixed total function from infinitely many inputs to finitely many 32-byte outputs, its truth value is a fixed mathematical fact (such a pair exists by counting), not an assumption.
Edge cases made explicit. , , may be empty or of arbitrary and unequal lengths; may equal . Both sides of the hypothesis are 32-byte digests, so the hypothesis is an equality of 32-byte strings. The conclusion mentions none of .