Equal branch hashes of 32-byte children have the same children up to order, or exhibit a collision
ProvedBitcoinTapSoundness.branch_eqFor 32-byte strings : tapbranchHash a b = tapbranchHash c d implies , or Sha256Collision. The branch hash sorts its two children lexicographically before concatenating; the length hypotheses split the concatenation.
Deprecated. Superseded by BitcoinTapSoundnessV2.branch_eq (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.branch_eq (a b c d : BitcoinSer.Bytes) (ha : a.length = 32) (hb : b.length = 32)
(hc : c.length = 32) (hd : d.length = 32) (h : BitcoinTaproot.tapbranchHash a b = BitcoinTaproot.tapbranchHash c d) :
((a = c ∧ b = d) ∨ (a = d ∧ b = c)) ∨ 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.branch_eq
Statement. For all byte strings (finite sequences of 8-bit values), under the four hypotheses
if
then at least one of the following holds:
- and ; or
- and ; or
- : there exist two byte strings (of any lengths, unrelated to ) with .
(The parenthesization in the code is , which is logically the same three-way disjunction.)
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 of a string; the tagged hash with tag is
- Lexicographic order on byte strings: compare position by position by numeric byte value; at the first differing position the smaller byte wins; if one string is a proper prefix of the other, the shorter one is smaller; a string is never itself.
- The branch hash is
As a consequence of this definition, for all .
- is the closed proposition . It has no parameters, so it is the same proposition in every instance of the theorem; 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. All four inputs are required to be exactly 32 bytes long, so the two 64-byte strings fed to the tagged hash are and . The case (and/or ) is included; then disjuncts (1) and (2) coincide. Nothing is asserted when any of the length hypotheses fails.