Script-path soundness at the Merkle level: a verified path opens a committed leaf
ProvedBitcoinTapSoundness.script_path_soundnessFor a tree , a control block of length , a leaf version and a script : if taprootMerkleRoot control (tapleafHash v s) = T.hash (Core's ComputeTaprootMerkleRoot lands on the root) then tapleafHash v s ∈ T.leaves or Sha256Collision. The path nodes of a well-sized control block are 32 bytes each, path_lands gives a subtree with the leaf's hash, and that subtree is a leaf (else leaf_ne_branch).
Deprecated. Superseded by BitcoinTapSoundnessV2.script_path_soundness (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.script_path_soundness (T : BitcoinTapSoundness.TapTree) (control : BitcoinSer.Bytes) (k : Nat)
(hc : control.length = BitcoinTaproot.TAPROOT_CONTROL_BASE_SIZE + BitcoinTaproot.TAPROOT_CONTROL_NODE_SIZE * k)
(v : BitcoinSer.Byte) (s : BitcoinSer.Bytes)
(h : BitcoinTaproot.taprootMerkleRoot control (BitcoinTaproot.tapleafHash v s) = T.hash) :
BitcoinTaproot.tapleafHash v s ∈ T.leaves ∨ 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.script_path_soundness
Statement. Let be a tap tree (a finite binary tree in which every internal node has exactly two ordered children and every leaf carries a byte and a byte string ). Let ("control") be a byte string and a natural number (possibly ) with
Let be a byte and a byte string (of any length). Assume
Then at least one of the following holds:
- is an element of the list ; or
- : there exist two byte strings (of any lengths, unrelated to the theorem's variables) 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, and for a tag string ,
- is the compact-size encoding of (one byte if ; + 2 little-endian bytes if ; + 4 bytes if ; + 8 bytes of otherwise).
- , with used as given (no masking).
- is lexicographic order on byte strings (first differing byte decides; a proper prefix is smaller; no string is itself) and
- The path nodes of a control string : let , where is truncated natural-number subtraction (so whenever ). Discard the first bytes of and cut what remains into consecutive blocks of bytes, ; any leftover bytes (fewer than 32) are ignored. Under the hypothesis there are exactly nodes, each exactly 32 bytes long, and nothing is left over. The first 33 bytes of play no role in this theorem.
- The Merkle root computed from and a starting hash is the left fold
which equals itself when .
- and .
- and : the list of leaf hashes of , left to right, with repetitions. Membership in disjunct (1) is membership of a 32-byte string in this list; it does not say that the pair itself appears in , only that its leaf hash equals the leaf hash of some leaf of .
- is the closed proposition , independent of all the theorem's variables; 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. is allowed: then has exactly 33 bytes, there are no path nodes, and the hypothesis reads . No upper bound on (such as 128) is imposed. may be empty. The tree may be a single leaf. No relation between 's first 33 bytes and anything else is assumed or concluded.