A leaf hash equal to a branch hash: the TapLeaf and TapBranch preimages collide
ProvedBitcoinTapSoundnessV2.leaf_ne_branchFor any leaf version , script and byte strings : tapleafHash v s = tapbranchHash a b implies Collides (taggedPre "TapLeaf" (leafMsg v s)) (taggedPre "TapBranch" (branchMsg a b)). The two strings differ in their first 32 bytes (tapleaf_ne_tapbranch).
import Definitions.Def_BitcoinTapSoundnessV2 import Definitions.Def_BitcoinSer import Definitions.Def_BitcoinTaproot open BitcoinTapSoundnessV2 BitcoinSer BitcoinTaproot
theorem BitcoinTapSoundnessV2.leaf_ne_branch (v : BitcoinSer.Byte) (s a b : BitcoinSer.Bytes)
(h : BitcoinTaproot.tapleafHash v s = BitcoinTaproot.tapbranchHash a b) :
BitcoinTapSoundnessV2.Collides (BitcoinTapSoundnessV2.taggedPre "TapLeaf" (BitcoinTapSoundnessV2.leafMsg v s))
(BitcoinTapSoundnessV2.taggedPre "TapBranch" (BitcoinTapSoundnessV2.branchMsg a b)) := 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: BitcoinTapSoundnessV2.leaf_ne_branch
Statement. For every byte (an 8-bit vector) and all byte strings (finite lists of bytes, of any length including empty), if
then
Unfoldings. is the bundle's executable SHA-256 (MD padding with , zeros to , 8-byte big-endian bit length; compression of each 64-byte chunk from the standard initial state; eight big-endian 32-bit words out), a total function on byte strings. is the UTF-8 byte list of the string . and .
is one byte if ; byte then 2 little-endian bytes of if ; byte then 4 LE bytes if ; else byte then 8 LE bytes. , and .
is the Boolean strict lexicographic order on byte strings ( is below any non-empty string; otherwise compare leading bytes and recurse on ties; is false). if , else . .
is .
Edge cases and what is silently included. There are no length hypotheses: , and may have any length (including ), and need not be 32 bytes or hashes of anything; may be any byte. The conclusion names two explicit strings — the "TapLeaf"-prefixed preimage of the leaf hash, , and the "TapBranch"-prefixed preimage of the branch hash, (where abbreviates ) — and asserts (i) they are different byte strings and (ii) their SHA-256 outputs coincide. Part (ii) is, by unfolding, the hypothesis itself; part (i) is the additional content. The two strings differ in their first 64 bytes exactly when , which this theorem does not itself assert.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.