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.script_path_soundness
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 byte string control, every natural number k (including 0), every byte v, and every byte string s, such that
- hc: ∣control∣=33+32k;
- h: taprootMerkleRoot(control,tapleafHash(v,s))=hash(T);
Conclusion. at least one of the following holds (inclusive disjunction), writing L=tapleafHash(v,s):
- scriptPathWitness(T,control,v,s)=none and L∈leaves(T); or
- there exist byte strings x,y with scriptPathWitness(T,control,v,s)=some(x,y) and Collides(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 byte 253 + 2 little-endian bytes if n≤0xffff; else byte 254 + 4 LE bytes if n≤0xffffffff; else byte 255 + 8 LE bytes. 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)). leaves(leaf(v′,s′))=[tapleafHash(v′,s′)]; leaves(branch(l,r))=leaves(l)∥leaves(r); L∈leaves(T) is membership of the 32-byte hash L in that list of hashes.
controlNodes(control): with m=⌊(∣control∣−˙33)/32⌋ (−˙ truncated natural subtraction), the list of m consecutive 32-byte chunks of control after its first 33 bytes. Under hc this is exactly the k trailing 32-byte blocks n1,…,nk (empty when k=0). taprootMerkleRoot(control,L) is the left fold h0=L, hi=tapbranchHash(hi−1,ni), result hk; for k=0 it is L itself.
walk(T,path,h) returns either a tree (inl) or a pair of byte strings (inr): walk(T,[],h)=inl(T); for n::rest, let W=walk(T,rest,tapbranchHash(h,n)); if W=inr(c) return inr(c); if W=inl(leaf(v′,s′)) return inr(taggedPre("TapLeaf",leafMsg(v′,s′)),taggedPre("TapBranch",branchMsg(h,n))); if W=inl(branch(l,r)) return inl(l) if h=hash(l), else inl(r) if h=hash(r), else inr(taggedPre("TapBranch",branchMsg(hash(l),hash(r))),taggedPre("TapBranch",branchMsg(h,n))). The tree is descended from the root while the list is read from its end; walk itself checks no lengths and does not check that the folded value equals hash(T).
scriptPathWitness(T,control,v,s) is computed from W=walk(T,controlNodes(control),L): inr(c)↦some(c); inl(leaf(⋅,⋅))↦none (the reached leaf's version and script are not compared with v,s); inl(branch(l,r))↦some(taggedPre("TapLeaf",leafMsg(v,s)),taggedPre("TapBranch",branchMsg(hash(l),hash(r)))).
Edge cases and what is silently included. k=0 is allowed: then control is 33 bytes, the path is empty, h reads L=hash(T), walk returns inl(T), and the witness is none if T is a leaf and some(leaf preimage,root-branch preimage) if T is a branch. No upper bound on k is stated. The first 33 bytes of control (the parity/version byte and the 32-byte internal key) play no role in this statement; neither does any tweak or output key. v is any byte and s any byte string. Alternative 1 asserts no collision, only that the hash L occurs in the list leaves(T) (a list of hashes, possibly with repeats). Alternative 2 asserts that the specific pair returned by scriptPathWitness — an explicit expression in T, the ni, v and s — consists of two different byte strings with equal SHA-256. The disjunction is inclusive.
Confirmed by the moderator at approval.