Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Taproot key-path spending is correct

Proved
BitcoinTaproot.keypath_correct

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

bip341bip342bitcoinbitcoin-mainnetconsensusformal-verificationschnorrtaproottapscript

For every list of spent outputs, context ccc (flags, transaction, input index, amount), signature and 32-byte output key qqq:

taprootHandler(spent,c,[sig],q)=true  ⟺  ∃ body ht h. ∣body∣=64∧((sig=body∧ht=0)∨(∃b. sig=body ∥ [b]∧b=ht≠0))∧sigHashSchnorr(c.tx,spent,c.nIn,ht,tapscript=false,⟨false,[],[],0xFFFFFFFF⟩)=some h∧schnorrVerify(q,h,body)=true.\mathrm{taprootHandler}(spent, c, [sig], q) = \mathtt{true} \iff \exists\, body\ ht\ h.\ |body| = 64 \wedge \big((sig = body \wedge ht = 0) \vee (\exists b.\ sig = body \,\|\, [b] \wedge b = ht \ne 0)\big) \wedge \mathrm{sigHashSchnorr}(c.tx, spent, c.nIn, ht, \mathrm{tapscript}{=}\mathtt{false}, \langle \mathtt{false}, [], [], \mathtt{0xFFFFFFFF}\rangle) = \mathrm{some}\ h \wedge \mathrm{schnorrVerify}(q, h, body) = \mathtt{true}.taprootHandler(spent,c,[sig],q)=true⟺∃body ht h. ∣body∣=64∧((sig=body∧ht=0)∨(∃b. sig=body∥[b]∧b=ht=0))∧sigHashSchnorr(c.tx,spent,c.nIn,ht,tapscript=false,⟨false,[],[],0xFFFFFFFF⟩)=some h∧schnorrVerify(q,h,body)=true.

A key-path spend verifies exactly when the witness is a BIP340 signature by the output key of the BIP341 signature hash: 64 bytes under SIGHASH_DEFAULT, or 65 bytes under the non-zero hash type of the last byte.

Formalization Note. taprootHandler is the version-1 branch of VerifyWitnessProgram as plugged into the published VerifyScript; the equivalence holds for every flag set, transaction and amount. The script path is covered by scriptpath_commitment.

Preamble
import Definitions.Def_BitcoinTaproot
import Definitions.Def_BitcoinVerify
import Definitions.Def_BitcoinSig
open BitcoinTaproot BitcoinSer BitcoinSig BitcoinVerify
open BitcoinScript hiding Bytes Byte
Formal statement
theorem BitcoinTaproot.keypath_correct (spent : List TxOut) (c : BitcoinVerify.Ctx) (sig q : Bytes) :
    BitcoinTaproot.taprootHandler spent c [sig] q = true ↔
      ∃ (body : Bytes) (ht : Nat) (h : Bytes), body.length = 64 ∧
        ((sig = body ∧ ht = 0) ∨ (∃ b : Byte, sig = body ++ [b] ∧ b.toNat = ht ∧ ht ≠ 0)) ∧
        BitcoinTaproot.sigHashSchnorr c.tx spent c.nIn ht false ⟨false, [], [], 0xFFFFFFFF⟩ = some h ∧
        BitcoinSig.schnorrVerify q h body = true := by sorry
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: VerifyWitnessProgram (version 1), ExecuteWitnessScript, EvalScript under SigVersion::TAPSCRIPT, EvalChecksigTapscript, CheckSchnorrSignature, SignatureHashSchnorr, ComputeTapleafHash, ComputeTapbranchHash, ComputeTaprootMerkleRoot, VerifyTaprootCommitment, 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, src/secp256k1/src/modules/extrakeys/main_impl.h; IsOpSuccess, src/script/script.cpp; BIP340, BIP341, BIP342 at bips revision 100ba872c808946155b1eeb8c4568058f2eea0a7
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: BitcoinTaproot.keypath_correct

Binders. spent\mathrm{spent}spent : a list of transaction outputs (integer value, byte-string script); ccc : a verification context BitcoinVerify.Ctx (fields flags\mathrm{flags}flags — Booleans p2sh, witness, taproot, dersig, cltv, csv, nulldummy —, tx\mathrm{tx}tx a transaction with natural version\mathrm{version}version, inputs vin\mathrm{vin}vin, outputs vout\mathrm{vout}vout, natural nLockTime\mathrm{nLockTime}nLockTime, nIn∈N\mathrm{nIn} \in \mathbb{N}nIn∈N, amount∈Z\mathrm{amount} \in \mathbb{Z}amount∈Z); sig,q\mathrm{sig}, qsig,q : byte strings.

Hypotheses. None.

Conclusion (an equivalence).

taprootHandler(spent)(c,[sig],q)=true\mathrm{taprootHandler}(\mathrm{spent})(c, [\mathrm{sig}], q) = \mathrm{true}taprootHandler(spent)(c,[sig],q)=true

if and only if there exist a byte string body\mathrm{body}body, a natural ht\mathrm{ht}ht and a byte string hhh with

  1. ∣body∣=64|\mathrm{body}| = 64∣body∣=64;
  2. either (sig=body\mathrm{sig} = \mathrm{body}sig=body and ht=0\mathrm{ht} = 0ht=0) or (there is an 8-bit value bbb with sig=body∥[b]\mathrm{sig} = \mathrm{body} \Vert [b]sig=body∥[b], b=htb = \mathrm{ht}b=ht as naturals, and ht≠0\mathrm{ht} \neq 0ht=0);
  3. sigHashSchnorr(c.tx,spent,c.nIn,ht,false,(false,[ ],[ ],0xFFFFFFFF))=some(h)\mathrm{sigHashSchnorr}\big(c.\mathrm{tx}, \mathrm{spent}, c.\mathrm{nIn}, \mathrm{ht}, \mathrm{false}, (\mathrm{false}, [\,], [\,], \texttt{0xFFFFFFFF})\big) = \mathrm{some}(h)sigHashSchnorr(c.tx,spent,c.nIn,ht,false,(false,[],[],0xFFFFFFFF))=some(h), the last argument being the ExecData with no annex, empty annex hash, empty tapleaf hash and code-separator position 232−12^{32}-1232−1;
  4. schnorrVerify(q,h,body)=true\mathrm{schnorrVerify}(q, h, \mathrm{body}) = \mathrm{true}schnorrVerify(q,h,body)=true.

The left side, unfolded. taprootHandler(spent)(c,W,q)\mathrm{taprootHandler}(\mathrm{spent})(c, W, q)taprootHandler(spent)(c,W,q) returns false\mathrm{false}false for empty WWW; otherwise computes hasAnnex(W)\mathrm{hasAnnex}(W)hasAnnex(W) ("∣W∣≥2|W| \ge 2∣W∣≥2 and the last element is non-empty and starts with 0x50\texttt{0x50}0x50"), strips the annex if present, builds e0e_0e0​ = (annex present, SHA-256 of the CompactSize-prefixed annex or [ ][\,][], [ ][\,][], 0xFFFFFFFF\texttt{0xFFFFFFFF}0xFFFFFFFF), and if the remaining stack has exactly one element xxx returns checkSchnorrSignature(c.tx,spent,c.nIn,x,q,false,e0)\mathrm{checkSchnorrSignature}(c.\mathrm{tx}, \mathrm{spent}, c.\mathrm{nIn}, x, q, \mathrm{false}, e_0)checkSchnorrSignature(c.tx,spent,c.nIn,x,q,false,e0​); otherwise it takes the script path. For W=[sig]W = [\mathrm{sig}]W=[sig] there is no annex (∣W∣=1|W| = 1∣W∣=1), the stack is [sig][\mathrm{sig}][sig], e0=(false,[ ],[ ],0xFFFFFFFF)e_0 = (\mathrm{false}, [\,], [\,], \texttt{0xFFFFFFFF})e0​=(false,[],[],0xFFFFFFFF), and the left side equals checkSchnorrSignature(c.tx,spent,c.nIn,sig,q,false,e0)=true\mathrm{checkSchnorrSignature}(c.\mathrm{tx}, \mathrm{spent}, c.\mathrm{nIn}, \mathrm{sig}, q, \mathrm{false}, e_0) = \mathrm{true}checkSchnorrSignature(c.tx,spent,c.nIn,sig,q,false,e0​)=true. The flag c.flags.taprootc.\mathrm{flags}.\mathrm{taproot}c.flags.taproot and c.amountc.\mathrm{amount}c.amount play no role.

The signature check, unfolded. checkSchnorrSignature(tx,S,i,sig,pk,τ,e)\mathrm{checkSchnorrSignature}(\mathrm{tx}, S, i, \mathrm{sig}, \mathrm{pk}, \tau, e)checkSchnorrSignature(tx,S,i,sig,pk,τ,e) (with SSS the spent-output list, iii the input index, τ\tauτ the tapscript flag, eee the ExecData) is the Boolean computed as follows: if ∣sig∣≠64|\mathrm{sig}| \neq 64∣sig∣=64 and ∣sig∣≠65|\mathrm{sig}| \neq 65∣sig∣=65, false\mathrm{false}false; otherwise let t:=t := t:= the last byte of sig\mathrm{sig}sig as a natural if ∣sig∣=65|\mathrm{sig}| = 65∣sig∣=65, else t:=0t := 0t:=0, and sig′:=sig\mathrm{sig}' := \mathrm{sig}sig′:=sig without its last byte if ∣sig∣=65|\mathrm{sig}| = 65∣sig∣=65, else sig\mathrm{sig}sig; if ∣sig∣=65|\mathrm{sig}| = 65∣sig∣=65 and t=0t = 0t=0, false\mathrm{false}false; otherwise compute sigHashSchnorr(tx,S,i,t,τ,e)\mathrm{sigHashSchnorr}(\mathrm{tx}, S, i, t, \tau, e)sigHashSchnorr(tx,S,i,t,τ,e) — if that is none\mathrm{none}none, false\mathrm{false}false; if it is some(h)\mathrm{some}(h)some(h), the result is schnorrVerify(pk,h,sig′)\mathrm{schnorrVerify}(\mathrm{pk}, h, \mathrm{sig}')schnorrVerify(pk,h,sig′).

schnorrVerify(pk,m,σ)\mathrm{schnorrVerify}(\mathrm{pk}, m, \sigma)schnorrVerify(pk,m,σ) is: false\mathrm{false}false if ∣pk∣≠32|\mathrm{pk}| \neq 32∣pk∣=32 or ∣σ∣≠64|\sigma| \neq 64∣σ∣=64; let r:=BE(σ[0:32])r := \mathrm{BE}(\sigma[0{:}32])r:=BE(σ[0:32]) and s:=BE(σ[32:64])s := \mathrm{BE}(\sigma[32{:}64])s:=BE(σ[32:64]) (big-endian values); false\mathrm{false}false if p≤rp \le rp≤r or n≤sn \le sn≤s (p=2256−232−977p = 2^{256} - 2^{32} - 977p=2256−232−977 the field prime, nnn the secp256k1 group order); let P:=liftX(BE(pk))P := \mathrm{liftX}(\mathrm{BE}(\mathrm{pk}))P:=liftX(BE(pk)), which is none\mathrm{none}none if BE(pk)≥p\mathrm{BE}(\mathrm{pk}) \ge pBE(pk)≥p, and otherwise, with x:=BE(pk)x := \mathrm{BE}(\mathrm{pk})x:=BE(pk) and y:=(x3+7)(p+1)/4 mod py := (x^3 + 7)^{(p+1)/4} \bmod py:=(x3+7)(p+1)/4modp, is the point (x,y)(x, y)(x,y) if yyy is even, or (x,p−y)(x, p - y)(x,p−y) if yyy is odd, provided y2≡x3+7(modp)y^2 \equiv x^3 + 7 \pmod py2≡x3+7(modp), and none\mathrm{none}none otherwise; false\mathrm{false}false if PPP is none\mathrm{none}none; let c:=BE(tagged("BIP0340/challenge",σ[0:32] ∥ pk ∥ m)) mod nc := \mathrm{BE}\big(\mathrm{tagged}(\texttt{"BIP0340/challenge"}, \sigma[0{:}32] \,\Vert\, \mathrm{pk} \,\Vert\, m)\big) \bmod nc:=BE(tagged("BIP0340/challenge",σ[0:32]∥pk∥m))modn; let R:=s⋅G+((n−c) mod n)⋅PR := s\cdot G + ((n - c) \bmod n)\cdot PR:=s⋅G+((n−c)modn)⋅P computed with the bundle's affine addition/doubling formulas (with the point at infinity as none\mathrm{none}none) and a 257-step double-and-add; false\mathrm{false}false if RRR is none\mathrm{none}none; otherwise true\mathrm{true}true iff yRy_RyR​ is even and xR=rx_R = rxR​=r.

sigHashSchnorr(tx,S,i,t,τ,e)\mathrm{sigHashSchnorr}(\mathrm{tx}, S, i, t, \tau, e)sigHashSchnorr(tx,S,i,t,τ,e), with e=(a,A,L,κ)e = (a, A, L, \kappa)e=(a,A,L,κ) (annex present, annex hash, tapleaf hash, code-separator position), is: none\mathrm{none}none unless t∈{0,1,2,3,0x81,0x82,0x83}t \in \{0,1,2,3,\texttt{0x81},\texttt{0x82},\texttt{0x83}\}t∈{0,1,2,3,0x81,0x82,0x83}; let o:=1o := 1o:=1 if t=0t = 0t=0 else t & 3t \,\&\, 3t&3; ι:=t & 0x80\iota := t \,\&\, \texttt{0x80}ι:=t&0x80; ς:=2 [τ]+[a]\varsigma := 2\,[\tau] + [a]ς:=2[τ]+[a] (so 000, 111, 222 or 333); I:=I :=I:= the iii-th input of tx\mathrm{tx}tx, or, if i≥∣vin∣i \ge |\mathrm{vin}|i≥∣vin∣, the default input (prevout with empty hash and index 000, empty scriptSig, sequence 000, empty witness); if o=3o = 3o=3 then single:=\mathrm{single} :=single:= none\mathrm{none}none when ∣vout∣≤i|\mathrm{vout}| \le i∣vout∣≤i and otherwise SHA256(serTxOut(vouti))\mathrm{SHA256}(\mathrm{serTxOut}(\mathrm{vout}_i))SHA256(serTxOut(vouti​)), else single:=[ ]\mathrm{single} := [\,]single:=[]; if single\mathrm{single}single is none\mathrm{none}none the result is none\mathrm{none}none; otherwise the result is some\mathrm{some}some of

tagged("TapSighash", [0x00,t mod 256] ∥ le32(version) ∥ le32(nLockTime) ∥ Hin ∥ Hout ∥ [ς] ∥ D ∥ (A if a else [ ]) ∥ single ∥ (L∥[0x00]∥le32(κ) if τ else [ ]))\mathrm{tagged}\Big(\texttt{"TapSighash"},\ [\texttt{0x00}, t \bmod 256] \,\Vert\, \mathrm{le32}(\mathrm{version}) \,\Vert\, \mathrm{le32}(\mathrm{nLockTime}) \,\Vert\, H_{\mathrm{in}} \,\Vert\, H_{\mathrm{out}} \,\Vert\, [\varsigma] \,\Vert\, D \,\Vert\, (A \text{ if } a \text{ else } [\,]) \,\Vert\, \mathrm{single} \,\Vert\, (L \Vert [\texttt{0x00}] \Vert \mathrm{le32}(\kappa) \text{ if } \tau \text{ else } [\,])\Big)tagged("TapSighash", [0x00,tmod256]∥le32(version)∥le32(nLockTime)∥Hin​∥Hout​∥[ς]∥D∥(A if a else [])∥single∥(L∥[0x00]∥le32(κ) if τ else []))

where HinH_{\mathrm{in}}Hin​ is empty if ι=0x80\iota = \texttt{0x80}ι=0x80 and otherwise is the concatenation of four SHA-256 digests: of all inputs' serialized outpoints (hash ∥\Vert∥ le32 index), of all elements of SSS's values as 8-byte little-endian two's complement, of all elements of SSS's scriptPubKeys each prefixed by its CompactSize length, and of all inputs' le32 sequences; HoutH_{\mathrm{out}}Hout​ is the SHA-256 of all outputs serialized (le64 two's-complement value ∥\Vert∥ CompactSize-prefixed script) if o=1o = 1o=1, and empty otherwise; DDD is serOutPoint(I.prevout) ∥ serTxOut(Si or the default output (−1,[ ]) if i≥∣S∣) ∥ le32(I.nSequence)\mathrm{serOutPoint}(I.\mathrm{prevout}) \,\Vert\, \mathrm{serTxOut}(S_i \text{ or the default output } (-1, [\,]) \text{ if } i \ge |S|) \,\Vert\, \mathrm{le32}(I.\mathrm{nSequence})serOutPoint(I.prevout)∥serTxOut(Si​ or the default output (−1,[]) if i≥∣S∣)∥le32(I.nSequence) if ι=0x80\iota = \texttt{0x80}ι=0x80, and le32(i)\mathrm{le32}(i)le32(i) otherwise. tagged(T,m)=SHA256(SHA256(T)∥SHA256(T)∥m)\mathrm{tagged}(T, m) = \mathrm{SHA256}(\mathrm{SHA256}(T)\Vert\mathrm{SHA256}(T)\Vert m)tagged(T,m)=SHA256(SHA256(T)∥SHA256(T)∥m) with TTT the UTF-8 bytes of the tag; le32(x)\mathrm{le32}(x)le32(x) is the 4-byte little-endian encoding of x mod 232x \bmod 2^{32}xmod232; CompactSize is 1 byte below 253253253, else 0xfd\texttt{0xfd}0xfd + 2 bytes up to 0xffff\texttt{0xffff}0xffff, else 0xfe\texttt{0xfe}0xfe + 4 bytes up to 0xffffffff\texttt{0xffffffff}0xffffffff, else 0xff\texttt{0xff}0xff + 8 bytes. All SHA-256 computations are the bundle's own implementation.

In this instance τ=false\tau = \mathrm{false}τ=false and a=falsea = \mathrm{false}a=false, so ς=0\varsigma = 0ς=0, no annex hash and no tapscript extension appear in the message, and t=htt = \mathrm{ht}t=ht must lie in {0,1,2,3,0x81,0x82,0x83}\{0,1,2,3,\texttt{0x81},\texttt{0x82},\texttt{0x83}\}{0,1,2,3,0x81,0x82,0x83} for clause 3 to hold; with ht∈{3,0x83}\mathrm{ht} \in \{3, \texttt{0x83}\}ht∈{3,0x83} it additionally requires c.nIn<∣vout∣c.\mathrm{nIn} < |\mathrm{vout}|c.nIn<∣vout∣.

Edge cases the quantifiers include. qqq not of length 323232 (both sides false); sig\mathrm{sig}sig empty, of length ≠64,65\neq 64, 65=64,65, or 65 bytes ending in 0x00\texttt{0x00}0x00 (both sides false); c.nIn≥∣vin∣c.\mathrm{nIn} \ge |\mathrm{vin}|c.nIn≥∣vin∣ (default input with empty prevout hash used in DDD when ht≥0x81\mathrm{ht} \ge \texttt{0x81}ht≥0x81) or ≥∣spent∣\ge |\mathrm{spent}|≥∣spent∣ (default output (−1,[ ])(-1, [\,])(−1,[])); spent\mathrm{spent}spent of any length; empty vin\mathrm{vin}vin or vout\mathrm{vout}vout; ht\mathrm{ht}ht, when it exists, is determined by sig\mathrm{sig}sig.

Human review
  • Endorsed by Shuze Chen · Oct 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Oct 27, 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