Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The key path commits to the annex

Proved
BitcoinTaproot.keypath_annex

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

bip341bip342bitcoinbitcoin-mainnetconsensusformal-verificationschnorrtaproottapscript

For a witness [sig, annex] with a non-empty annex starting with 0x50, the Taproot handler equals the Schnorr check with execution data recording the annex and its hash SHA256(compactSize(∣annex∣) ∥ annex)\mathrm{SHA256}(\mathrm{compactSize}(|annex|)\,\|\,annex)SHA256(compactSize(∣annex∣)∥annex).

Preamble
import Definitions.Def_BitcoinTaproot
import Definitions.Def_BitcoinVerify
import Definitions.Def_BitcoinSer
open BitcoinTaproot BitcoinSer BitcoinSig BitcoinVerify
open BitcoinScript hiding Bytes Byte
Formal statement
theorem BitcoinTaproot.keypath_annex (spent : List TxOut) (c : BitcoinVerify.Ctx) (sig annex q : Bytes)
    (ha : (annex.getD 0 0).toNat = BitcoinTaproot.ANNEX_TAG) (hne : annex ≠ []) :
    BitcoinTaproot.taprootHandler spent c [sig, annex] q =
      BitcoinTaproot.checkSchnorrSignature c.tx spent c.nIn sig q false
        ⟨true, BitcoinSer.sha256 (BitcoinSer.serBytes annex), [], 0xFFFFFFFF⟩ := 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_annex

Binders. spent\mathrm{spent}spent : a list of transaction outputs; ccc : a verification context BitcoinVerify.Ctx (fields flags\mathrm{flags}flags — Booleans p2sh, witness, taproot, dersig, cltv, csv, nulldummy —, tx\mathrm{tx}tx, nIn∈N\mathrm{nIn} \in \mathbb{N}nIn∈N, amount∈Z\mathrm{amount} \in \mathbb{Z}amount∈Z); sig,annex,q\mathrm{sig}, \mathrm{annex}, qsig,annex,q : byte strings.

Hypotheses.

  1. (annex0)(\mathrm{annex}_0)(annex0​), the first byte of annex\mathrm{annex}annex read as a natural (default 000 if annex\mathrm{annex}annex is empty), equals 0x50=80\texttt{0x50} = 800x50=80 (the constant ANNEX_TAG);
  2. annex≠[ ]\mathrm{annex} \neq [\,]annex=[].

Conclusion (an equality of Booleans).

taprootHandler(spent)(c,[sig,annex],q)  =  checkSchnorrSignature(c.tx,spent,c.nIn,sig,q,false,(true,SHA256(serBytes(annex)),[ ],0xFFFFFFFF)),\mathrm{taprootHandler}(\mathrm{spent})(c, [\mathrm{sig}, \mathrm{annex}], q) \;=\; \mathrm{checkSchnorrSignature}\big(c.\mathrm{tx}, \mathrm{spent}, c.\mathrm{nIn}, \mathrm{sig}, q, \mathrm{false}, (\mathrm{true}, \mathrm{SHA256}(\mathrm{serBytes}(\mathrm{annex})), [\,], \texttt{0xFFFFFFFF})\big),taprootHandler(spent)(c,[sig,annex],q)=checkSchnorrSignature(c.tx,spent,c.nIn,sig,q,false,(true,SHA256(serBytes(annex)),[],0xFFFFFFFF)),

where serBytes(annex)=CompactSize(∣annex∣) ∥ annex\mathrm{serBytes}(\mathrm{annex}) = \mathrm{CompactSize}(|\mathrm{annex}|) \,\Vert\, \mathrm{annex}serBytes(annex)=CompactSize(∣annex∣)∥annex and the last argument is the ExecData record with annexPresent =true= \mathrm{true}=true, annexHash =SHA256(serBytes(annex))= \mathrm{SHA256}(\mathrm{serBytes}(\mathrm{annex}))=SHA256(serBytes(annex)), empty tapleafHash, and codeseparatorPos =232−1= 2^{32} - 1=232−1.

The left side, unfolded. taprootHandler(spent)(c,W,q)\mathrm{taprootHandler}(\mathrm{spent})(c, W, q)taprootHandler(spent)(c,W,q): false\mathrm{false}false if W=[ ]W = [\,]W=[]; otherwise hasAnnex(W)\mathrm{hasAnnex}(W)hasAnnex(W) is "∣W∣≥2|W| \ge 2∣W∣≥2 and the last element of WWW is non-empty with first byte 0x50\texttt{0x50}0x50"; when it holds the annex is the last element and the stack is WWW minus its last element, otherwise there is no annex and the stack is WWW; e0e_0e0​ is (annex present, SHA256(serBytes(annex))\mathrm{SHA256}(\mathrm{serBytes}(\mathrm{annex}))SHA256(serBytes(annex)) if present else [ ][\,][], [ ][\,][], 0xFFFFFFFF\texttt{0xFFFFFFFF}0xFFFFFFFF); if the stack has exactly one element xxx the result is 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 the script path is taken (control block and script from the end of the stack, control size checks, commitment check, Tapscript execution or acceptance of an unknown leaf version). For W=[sig,annex]W = [\mathrm{sig}, \mathrm{annex}]W=[sig,annex]: ∣W∣=2|W| = 2∣W∣=2, and by hypotheses 1–2 the last element annex\mathrm{annex}annex is non-empty with first byte 0x50\texttt{0x50}0x50, so hasAnnex\mathrm{hasAnnex}hasAnnex holds, the stack is [sig][\mathrm{sig}][sig] of length 111, e0=(true,SHA256(serBytes(annex)),[ ],0xFFFFFFFF)e_0 = (\mathrm{true}, \mathrm{SHA256}(\mathrm{serBytes}(\mathrm{annex})), [\,], \texttt{0xFFFFFFFF})e0​=(true,SHA256(serBytes(annex)),[],0xFFFFFFFF), and the key path is taken. Neither c.flags.taprootc.\mathrm{flags}.\mathrm{taproot}c.flags.taproot nor c.amountc.\mathrm{amount}c.amount is consulted.

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=truea = \mathrm{true}a=true, so ς=1\varsigma = 1ς=1, the message contains SHA256(serBytes(annex))\mathrm{SHA256}(\mathrm{serBytes}(\mathrm{annex}))SHA256(serBytes(annex)) right after the per-input data, and no tapscript extension.

Edge cases the quantifiers include. Hypothesis 2 is implied by hypothesis 1 (an empty annex\mathrm{annex}annex would give first byte 0≠800 \neq 800=80), so it adds nothing; annex=[0x50]\mathrm{annex} = [\texttt{0x50}]annex=[0x50] (one byte); sig\mathrm{sig}sig of any length (both sides false\mathrm{false}false unless 64 or 65 with non-zero last byte); qqq of any length; c.nInc.\mathrm{nIn}c.nIn out of range (default input and default output (−1,[ ])(-1,[\,])(−1,[]) in the hash); spent\mathrm{spent}spent of any length; arbitrary flags.

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