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.path_lands
Binders and hypotheses. For every tree T of type TapTree (built from leaf(v,s), v a byte and s a byte string, and branch(l,r)), every list of byte strings nodes=[n1,…,nk] (with k≥0), and every byte string h, such that
- hn: every element n of nodes has ∣n∣=32;
- hh: ∣h∣=32;
- heq: the left fold of tapbranchHash over nodes starting from h equals hash(T), i.e. with h0=h and hi=tapbranchHash(hi−1,ni), hk=hash(T);
Conclusion. at least one of the following holds (inclusive disjunction):
- there exists a tree U such that
walk(T,nodes,h)=inl(U),U∈subtreesAt(T,k),hash(U)=h;
or
2. there exist byte strings x,y such that
walk(T,nodes,h)=inr(x,y)andCollides(x,y).
Unfoldings. SHA256 is the bundle's executable SHA-256 (MD padding, 64-byte-chunk compression from the standard IV, eight big-endian words out), total on byte strings. ascii(t) is the UTF-8 byte list of t; tagged(t,m)=SHA256(SHA256(ascii(t))∥SHA256(ascii(t))∥m); taggedPre(t,m)=SHA256(ascii(t))∥SHA256(ascii(t))∥m. Collides(x,y) is x=y∧SHA256(x)=SHA256(y).
writeCompactSize(n): one byte n if n<253, else a marker byte (253/254/255) followed by 2/4/8 little-endian bytes according to n≤0xffff / ≤0xffffffff / larger. leafMsg(v,s)=[v]∥writeCompactSize(∣s∣)∥s; tapleafHash(v,s)=tagged("TapLeaf",leafMsg(v,s)). lexLt is Boolean strict lexicographic order on byte strings; branchMsg(a,b)=a∥b if lexLt(a,b) else b∥a; tapbranchHash(a,b)=tagged("TapBranch",branchMsg(a,b)).
hash(leaf(v,s))=tapleafHash(v,s); hash(branch(l,r))=tapbranchHash(hash(l),hash(r)).
subtreesAt(T,0)=[T]; subtreesAt(leaf(v,s),d+1)=[]; subtreesAt(branch(l,r),d+1)=subtreesAt(l,d)∥subtreesAt(r,d). U∈subtreesAt(T,k) is list membership (equality of trees, which is decidable).
walk(T,path,h) returns either a tree (inl) or a pair of byte strings (inr), case by case: walk(T,[],h)=inl(T) for every h. For a path n::rest, let W=walk(T,rest,tapbranchHash(h,n)); if W=inr(c) the result is inr(c); if W=inl(leaf(v,s)) the result is inr(taggedPre("TapLeaf",leafMsg(v,s)),taggedPre("TapBranch",branchMsg(h,n))); if W=inl(branch(l,r)) the result is inl(l) when h=hash(l), otherwise inl(r) when h=hash(r), otherwise inr(taggedPre("TapBranch",branchMsg(hash(l),hash(r))),taggedPre("TapBranch",branchMsg(h,n))). Unwound on [n1,…,nk]: the innermost call is on hk and the empty path and returns inl(T); the step for nk compares hk−1 with the children of T; the step for nk−1 compares hk−2 with the children of the chosen child; and so on, so the tree is descended from the root while the list is read from its end, and the final comparison (for n1) is of h0=h. The function performs no length or root check of its own.
Edge cases and what is silently included. When k=0 (nodes empty): hn is vacuous, heq reads h=hash(T), walk returns inl(T), and subtreesAt(T,0)=[T], so alternative 1 is U=T. When k exceeds the depth of every node reached, subtreesAt(T,k) is empty, so alternative 1 cannot hold and the statement reduces to alternative 2. Alternative 2 asserts that the specific pair (x,y) returned by walk — an explicit expression in T, the ni and h — consists of two different byte strings with equal SHA-256; alternative 1 asserts no collision. The disjunction is inclusive. The trees' leaves are unconstrained (any byte v, any script length), and hash(T) is always a 32-byte string by construction, so heq compares 32-byte strings.
Confirmed by the moderator at approval.