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.commitment_soundness
Binders and hypotheses. The theorem quantifies universally over:
- byte strings q and internal32 (finite lists of 8-bit bytes; no length hypothesis is stated for either);
- a Boolean parity;
- a tree T of type TapTree (built from leaf(v′,s′) with v′ a byte and s′ a byte string, and branch(l,r));
- a hypothesis hT: HonestOutput(q,internal32,parity,T), i.e. checkTapTweak(q,internal32,hash(T),parity)=true;
- a byte string control and a natural number k (including k=0);
- a hypothesis hc: ∣control∣=33+32k;
- a hypothesis hkey: take32(drop1(control))=internal32 (bytes 1 through 32 of control equal internal32; together with hc this forces ∣internal32∣=32);
- a hypothesis hpar: [control[0]mod2=1]=parity (the first byte of control is odd iff parity; the default byte 0 is used if control is empty, which hc excludes);
- a byte v and a byte string s (no constraint on v's value or on ∣s∣);
- a hypothesis h: verifyTaprootCommitment(control,q,tapleafHash(v,s))=true.
Write L=tapleafHash(v,s) and R=taprootMerkleRoot(control,L).
Conclusion. At least one of the following three alternatives holds (inclusive disjunction):
(A) R=hash(T), and moreover either
- 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).
(B) R=hash(T), and
Collides(taggedPre("TapTweak",internal32∥R),taggedPre("TapTweak",internal32∥hash(T))).
(C) R=hash(T), and there exists a pair of natural numbers P such that liftX(beVal(internal32))=some(P) and
TweakCollision(q,parity,P,tapTweakHash(internal32,R),tapTweakHash(internal32,hash(T))).
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) means 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 and tapleafHash(v,s)=tagged("TapLeaf",leafMsg(v,s)).
lexLt is Boolean strict lexicographic order on byte strings (empty < non-empty; compare first bytes, recurse on equal). 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 list membership of the hash L (not of the pair (v,s)).
controlNodes(control): with m=⌊(∣control∣−˙33)/32⌋ (−˙ truncated subtraction), the list of m consecutive 32-byte chunks of control after its first 33 bytes. Under hc, m=k and the chunks are exactly the k trailing 32-byte blocks, n1,…,nk. taprootMerkleRoot(control,L) is the left fold h0=L, hi=tapbranchHash(hi−1,ni), result hk; for k=0, R=L.
tapTweakHash(i,r)=tagged("TapTweak",i∥r). beVal(b) is the big-endian natural-number value of b. With p=2256−232−977: liftX(x) is none if x≥p; else with y=(x3+7)(p+1)/4modp, it is some(x,y′) with y′ the even one of y and (p−y)modp if y2≡x3+7(modp), and none otherwise.
xonlyTweakAddCheck(out,par,P,tw): let t=beVal(tw); false if t≥n (n the secp256k1 order constant); else Q=padd(some(P),pmul(t,G)) with G the base-point constant, pmul double-and-add with 257 fuel from infinity (so pmul(0,G) is infinity), and padd affine addition mod p with infinity as identity, infinity on x1≡x2 with y1+y2≡0, doubling formula otherwise on equal x, chord formula on distinct x, field inverses by Fermat exponentiation (0↦0); false if Q is infinity; else with Q=(qx,qy) the value is [be32(qx)=out]∧[(qymod2=1)=par], be32 being 32-byte big-endian encoding mod 2256.
checkTapTweak(q,i,r,par): false if liftX(beVal(i))=none; else, with some(P), xonlyTweakAddCheck(q,par,P,tapTweakHash(i,r)). verifyTaprootCommitment(c,prog,ℓ)=checkTapTweak(prog,take32(drop1(c)),taprootMerkleRoot(c,ℓ),[c[0]mod2=1]) (default byte 0 for c[0] when c is empty). So, given hkey and hpar, hypothesis h unfolds to checkTapTweak(q,internal32,R,parity)=true, and hT to checkTapTweak(q,internal32,hash(T),parity)=true; both therefore require liftX(beVal(internal32)) to be some(P) for the same P, beVal of each tweak hash to be <n, and the resulting point to be non-infinite with abscissa encoding q and the stated parity.
TweakCollision(q,par,P,t1,t2) is t1=t2∧∣t1∣=32∧∣t2∣=32∧xonlyTweakAddCheck(q,par,P,t1)=true∧xonlyTweakAddCheck(q,par,P,t2)=true.
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 path is consumed so that the tree is descended from the root while the list is read from its last element; no length or root check is performed inside walk.
scriptPathWitness(T,control,v,s): from W=walk(T,controlNodes(control),L): inr(c)↦some(c); inl(leaf(⋅,⋅))↦none (the leaf's contents 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 appears only in hc; k=0 (a 33-byte control block, empty path, R=L) is allowed, and so is any k, with no upper bound such as 128. v is an arbitrary byte: nothing restricts the leaf version or ties v to the first byte of control. Neither q nor s carries a length hypothesis; ∣internal32∣=32 follows from hkey and hc but is not stated directly. The three alternatives are not asserted to be exclusive. In (A), both sub-alternatives may be true simultaneously in principle; the first sub-alternative asserts membership of the hash L in leaves(T), which is a list of hashes and may contain repeats. In (B) and (C) the colliding objects are explicit expressions in internal32, R, hash(T), q and parity: (B) names two (64+64)-byte strings and asserts they differ and have the same SHA-256; (C) names two 32-byte tweak hashes and asserts they differ, both have length 32, and both pass xonlyTweakAddCheck against q, parity and the lifted point P of internal32. Alternative (A) does not itself assert any collision when its first sub-alternative is used. The hypotheses hT and h are both Boolean equalities to true; if either computation yields false for every choice of inputs in some situation (e.g. liftX failing on internal32), the theorem is vacuous there.
Confirmed by the moderator at approval.