A Merkle path from a 32-byte hash to a tree's root lands on a subtree at the path's depth
ProvedBitcoinTapSoundness.path_landsFor a tree , a list of 32-byte path nodes and a 32-byte starting hash : if folding tapbranchHash over the nodes from gives T.hash, then there is a subtree of at depth equal to the number of nodes with U.hash = h, or Sha256Collision. By induction on the path: at each step the current hash is a branch hash, so the subtree it lands on is a branch (else leaf_ne_branch) and by branch_eq the previous hash is one of its children's.
Deprecated. Superseded by BitcoinTapSoundnessV2.path_lands (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.path_lands (T : BitcoinTapSoundness.TapTree) (nodes : List BitcoinSer.Bytes) (h : BitcoinSer.Bytes)
(hn : ∀ n ∈ nodes, n.length = 32) (hh : h.length = 32) (heq : nodes.foldl BitcoinTaproot.tapbranchHash h = T.hash) :
(∃ U ∈ T.subtreesAt nodes.length, U.hash = h) ∨ 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.path_lands
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 be a finite list of byte strings (possibly empty, ), and let be a byte string. Assume
- every element of has length exactly ;
- ;
- the left fold of the branch hash over the list starting from equals the hash of :
(for the left-hand side is just ).
Then at least one of the following holds:
- there exists a subtree occurring in the list of subtrees of at depth exactly (where ) such that ; or
- : 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, and for a tag string ,
- is the compact-size encoding of a natural number (one byte below 253; + 2 little-endian bytes up to ; + 4 bytes up to ; + 8 bytes of the value mod otherwise).
- .
- is lexicographic order on byte strings (first differing byte decides by numeric value; a proper prefix is smaller; no string is itself) and
which is symmetric in .
- The hash of a tap tree is defined recursively: and .
- The list of subtrees at depth is defined recursively: for any ; (the empty list); (list concatenation). So it lists, left to right, exactly the subtrees rooted at depth ; it is empty when exceeds the depth of every leaf along the way.
- 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. When is empty, the hypothesis reads and , so disjunct (1) is exactly that hypothesis. When is larger than the depth of (e.g. is a single leaf and ), is empty, so disjunct (1) is false and the theorem then asserts outright under the hypotheses. The fold passes the accumulator as the first argument of and the node as the second, but the result does not depend on this because is symmetric. The leaf-version bytes and scripts inside are unconstrained.