Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Script-path soundness at the Merkle level: a verified path opens a committed leaf, or scriptPathWitness names a collision

Proved
BitcoinTapSoundnessV2.script_path_soundness

by pitimespi · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

bip341bitcoinbitcoin-mainnetcollisionformal-verificationmerklesoundnesstagged-hashtaproot

For a tree TTT, a control block of length 33+32k33 + 32k33+32k, a leaf version vvv and a script sss with taprootMerkleRoot control (tapleafHash v s) = T.hash: either scriptPathWitness T control v s = none and tapleafHash v s ∈ T.leaves, or scriptPathWitness T control v s = some (x, y) with Collides x y.

Preamble
import Definitions.Def_BitcoinTapSoundnessV2
import Definitions.Def_BitcoinSer
import Definitions.Def_BitcoinTaproot
open BitcoinTapSoundnessV2 BitcoinSer BitcoinTaproot
Formal statement
theorem BitcoinTapSoundnessV2.script_path_soundness (T : BitcoinTapSoundnessV2.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) :
    (BitcoinTapSoundnessV2.scriptPathWitness T control v s = none ∧ BitcoinTaproot.tapleafHash v s ∈ T.leaves) ∨
      (∃ x y, BitcoinTapSoundnessV2.scriptPathWitness T control v s = some (x, y) ∧ BitcoinTapSoundnessV2.Collides x y) := by sorry
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: VerifyTaprootCommitment, ComputeTaprootMerkleRoot, ComputeTapleafHash, ComputeTapbranchHash (src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp); XOnlyPubKey::CheckTapTweak, ComputeTapTweakHash (src/pubkey.cpp); secp256k1_xonly_pubkey_tweak_add_check; BIP341
Read-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: BitcoinTapSoundnessV2.script_path_soundness

Binders and hypotheses. For every tree TTT of type TapTree\mathrm{TapTree}TapTree (built from leaf(v′,s′)\mathrm{leaf}(v', s')leaf(v′,s′), v′v'v′ a byte and s′s's′ a byte string, and branch(l,r)\mathrm{branch}(l, r)branch(l,r)), every byte string control\mathit{control}control, every natural number kkk (including 000), every byte vvv, and every byte string sss, such that

  • hc\mathit{hc}hc: ∣control∣=33+32k|\mathit{control}| = 33 + 32k∣control∣=33+32k;
  • hhh: taprootMerkleRoot(control,tapleafHash(v,s))=hash(T)\mathrm{taprootMerkleRoot}(\mathit{control}, \mathrm{tapleafHash}(v, s)) = \mathrm{hash}(T)taprootMerkleRoot(control,tapleafHash(v,s))=hash(T);

Conclusion. at least one of the following holds (inclusive disjunction), writing L=tapleafHash(v,s)L = \mathrm{tapleafHash}(v, s)L=tapleafHash(v,s):

  1. scriptPathWitness(T,control,v,s)=none\mathrm{scriptPathWitness}(T, \mathit{control}, v, s) = \mathrm{none}scriptPathWitness(T,control,v,s)=none and L∈leaves(T)L \in \mathrm{leaves}(T)L∈leaves(T); or
  2. there exist byte strings x,yx, yx,y with scriptPathWitness(T,control,v,s)=some(x,y)\mathrm{scriptPathWitness}(T, \mathit{control}, v, s) = \mathrm{some}(x, y)scriptPathWitness(T,control,v,s)=some(x,y) and Collides(x,y)\mathrm{Collides}(x, y)Collides(x,y).

Unfoldings. SHA256\mathrm{SHA256}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)\mathrm{ascii}(t)ascii(t) is the UTF-8 byte list of ttt; tagged(t,m)=SHA256(SHA256(ascii(t))∥SHA256(ascii(t))∥m)\mathrm{tagged}(t, m) = \mathrm{SHA256}(\mathrm{SHA256}(\mathrm{ascii}(t)) \| \mathrm{SHA256}(\mathrm{ascii}(t)) \| m)tagged(t,m)=SHA256(SHA256(ascii(t))∥SHA256(ascii(t))∥m); taggedPre(t,m)=SHA256(ascii(t))∥SHA256(ascii(t))∥m\mathrm{taggedPre}(t, m) = \mathrm{SHA256}(\mathrm{ascii}(t)) \| \mathrm{SHA256}(\mathrm{ascii}(t)) \| mtaggedPre(t,m)=SHA256(ascii(t))∥SHA256(ascii(t))∥m. Collides(x,y)\mathrm{Collides}(x, y)Collides(x,y) is x≠y∧SHA256(x)=SHA256(y)x \neq y \wedge \mathrm{SHA256}(x) = \mathrm{SHA256}(y)x=y∧SHA256(x)=SHA256(y).

writeCompactSize(n)\mathrm{writeCompactSize}(n)writeCompactSize(n): one byte nnn if n<253n < 253n<253; else byte 253253253 + 2 little-endian bytes if n≤0xffffn \le \mathtt{0xffff}n≤0xffff; else byte 254254254 + 4 LE bytes if n≤0xffffffffn \le \mathtt{0xffffffff}n≤0xffffffff; else byte 255255255 + 8 LE bytes. leafMsg(v,s)=[v]∥writeCompactSize(∣s∣)∥s\mathrm{leafMsg}(v, s) = [v] \| \mathrm{writeCompactSize}(|s|) \| sleafMsg(v,s)=[v]∥writeCompactSize(∣s∣)∥s; tapleafHash(v,s)=tagged("TapLeaf",leafMsg(v,s))\mathrm{tapleafHash}(v, s) = \mathrm{tagged}(\text{"TapLeaf"}, \mathrm{leafMsg}(v, s))tapleafHash(v,s)=tagged("TapLeaf",leafMsg(v,s)). lexLt\mathrm{lexLt}lexLt is Boolean strict lexicographic order on byte strings; branchMsg(a,b)=a∥b\mathrm{branchMsg}(a, b) = a \| bbranchMsg(a,b)=a∥b if lexLt(a,b)\mathrm{lexLt}(a, b)lexLt(a,b) else b∥ab \| ab∥a; tapbranchHash(a,b)=tagged("TapBranch",branchMsg(a,b))\mathrm{tapbranchHash}(a, b) = \mathrm{tagged}(\text{"TapBranch"}, \mathrm{branchMsg}(a, b))tapbranchHash(a,b)=tagged("TapBranch",branchMsg(a,b)).

hash(leaf(v′,s′))=tapleafHash(v′,s′)\mathrm{hash}(\mathrm{leaf}(v', s')) = \mathrm{tapleafHash}(v', s')hash(leaf(v′,s′))=tapleafHash(v′,s′); hash(branch(l,r))=tapbranchHash(hash(l),hash(r))\mathrm{hash}(\mathrm{branch}(l, r)) = \mathrm{tapbranchHash}(\mathrm{hash}(l), \mathrm{hash}(r))hash(branch(l,r))=tapbranchHash(hash(l),hash(r)). leaves(leaf(v′,s′))=[tapleafHash(v′,s′)]\mathrm{leaves}(\mathrm{leaf}(v', s')) = [\mathrm{tapleafHash}(v', s')]leaves(leaf(v′,s′))=[tapleafHash(v′,s′)]; leaves(branch(l,r))=leaves(l)∥leaves(r)\mathrm{leaves}(\mathrm{branch}(l, r)) = \mathrm{leaves}(l) \| \mathrm{leaves}(r)leaves(branch(l,r))=leaves(l)∥leaves(r); L∈leaves(T)L \in \mathrm{leaves}(T)L∈leaves(T) is membership of the 32-byte hash LLL in that list of hashes.

controlNodes(control)\mathrm{controlNodes}(\mathit{control})controlNodes(control): with m=⌊(∣control∣−˙33)/32⌋m = \lfloor(|\mathit{control}| \dot- 33)/32\rfloorm=⌊(∣control∣−˙​33)/32⌋ (−˙\dot-−˙​ truncated natural subtraction), the list of mmm consecutive 32-byte chunks of control\mathit{control}control after its first 33 bytes. Under hc\mathit{hc}hc this is exactly the kkk trailing 32-byte blocks n1,…,nkn_1, \dots, n_kn1​,…,nk​ (empty when k=0k = 0k=0). taprootMerkleRoot(control,L)\mathrm{taprootMerkleRoot}(\mathit{control}, L)taprootMerkleRoot(control,L) is the left fold h0=Lh_0 = Lh0​=L, hi=tapbranchHash(hi−1,ni)h_i = \mathrm{tapbranchHash}(h_{i-1}, n_i)hi​=tapbranchHash(hi−1​,ni​), result hkh_khk​; for k=0k = 0k=0 it is LLL itself.

walk(T,path,h)\mathrm{walk}(T, \mathit{path}, h)walk(T,path,h) returns either a tree (inl\mathrm{inl}inl) or a pair of byte strings (inr\mathrm{inr}inr): walk(T,[],h)=inl(T)\mathrm{walk}(T, [], h) = \mathrm{inl}(T)walk(T,[],h)=inl(T); for n::restn :: \mathit{rest}n::rest, let W=walk(T,rest,tapbranchHash(h,n))W = \mathrm{walk}(T, \mathit{rest}, \mathrm{tapbranchHash}(h, n))W=walk(T,rest,tapbranchHash(h,n)); if W=inr(c)W = \mathrm{inr}(c)W=inr(c) return inr(c)\mathrm{inr}(c)inr(c); if W=inl(leaf(v′,s′))W = \mathrm{inl}(\mathrm{leaf}(v', s'))W=inl(leaf(v′,s′)) return inr(taggedPre("TapLeaf",leafMsg(v′,s′)),taggedPre("TapBranch",branchMsg(h,n)))\mathrm{inr}\big(\mathrm{taggedPre}(\text{"TapLeaf"}, \mathrm{leafMsg}(v', s')), \mathrm{taggedPre}(\text{"TapBranch"}, \mathrm{branchMsg}(h, n))\big)inr(taggedPre("TapLeaf",leafMsg(v′,s′)),taggedPre("TapBranch",branchMsg(h,n))); if W=inl(branch(l,r))W = \mathrm{inl}(\mathrm{branch}(l, r))W=inl(branch(l,r)) return inl(l)\mathrm{inl}(l)inl(l) if h=hash(l)h = \mathrm{hash}(l)h=hash(l), else inl(r)\mathrm{inl}(r)inl(r) if h=hash(r)h = \mathrm{hash}(r)h=hash(r), else inr(taggedPre("TapBranch",branchMsg(hash(l),hash(r))),taggedPre("TapBranch",branchMsg(h,n)))\mathrm{inr}\big(\mathrm{taggedPre}(\text{"TapBranch"}, \mathrm{branchMsg}(\mathrm{hash}(l), \mathrm{hash}(r))), \mathrm{taggedPre}(\text{"TapBranch"}, \mathrm{branchMsg}(h, n))\big)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\mathrm{walk}walk itself checks no lengths and does not check that the folded value equals hash(T)\mathrm{hash}(T)hash(T).

scriptPathWitness(T,control,v,s)\mathrm{scriptPathWitness}(T, \mathit{control}, v, s)scriptPathWitness(T,control,v,s) is computed from W=walk(T,controlNodes(control),L)W = \mathrm{walk}(T, \mathrm{controlNodes}(\mathit{control}), L)W=walk(T,controlNodes(control),L): inr(c)↦some(c)\mathrm{inr}(c) \mapsto \mathrm{some}(c)inr(c)↦some(c); inl(leaf(⋅,⋅))↦none\mathrm{inl}(\mathrm{leaf}(\cdot, \cdot)) \mapsto \mathrm{none}inl(leaf(⋅,⋅))↦none (the reached leaf's version and script are not compared with v,sv, sv,s); inl(branch(l,r))↦some(taggedPre("TapLeaf",leafMsg(v,s)),taggedPre("TapBranch",branchMsg(hash(l),hash(r))))\mathrm{inl}(\mathrm{branch}(l, r)) \mapsto \mathrm{some}\big(\mathrm{taggedPre}(\text{"TapLeaf"}, \mathrm{leafMsg}(v, s)), \mathrm{taggedPre}(\text{"TapBranch"}, \mathrm{branchMsg}(\mathrm{hash}(l), \mathrm{hash}(r)))\big)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=0k = 0k=0 is allowed: then control\mathit{control}control is 33 bytes, the path is empty, hhh reads L=hash(T)L = \mathrm{hash}(T)L=hash(T), walk\mathrm{walk}walk returns inl(T)\mathrm{inl}(T)inl(T), and the witness is none\mathrm{none}none if TTT is a leaf and some(leaf preimage,root-branch preimage)\mathrm{some}(\text{leaf preimage}, \text{root-branch preimage})some(leaf preimage,root-branch preimage) if TTT is a branch. No upper bound on kkk is stated. The first 33 bytes of control\mathit{control}control (the parity/version byte and the 32-byte internal key) play no role in this statement; neither does any tweak or output key. vvv is any byte and sss any byte string. Alternative 1 asserts no collision, only that the hash LLL occurs in the list leaves(T)\mathrm{leaves}(T)leaves(T) (a list of hashes, possibly with repeats). Alternative 2 asserts that the specific pair returned by scriptPathWitness\mathrm{scriptPathWitness}scriptPathWitness — an explicit expression in TTT, the nin_ini​, vvv and sss — consists of two different byte strings with equal SHA-256. The disjunction is inclusive.

Human review
  • Endorsed by Shuze Chen · Nov 20, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Nov 20, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me