Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

An empty signature is a clean false

Proved
BitcoinTaproot.checksig_empty

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

bip341bip342bitcoinbitcoin-mainnetconsensusformal-verificationschnorrtaproottapscript

An executed OP_CHECKSIG with an empty signature and a 32-byte key pushes false (the empty vector), consumes no weight, and performs no signature check — the construction that makes OP_CHECKSIGADD thresholds work.

Preamble
import Definitions.Def_BitcoinTaproot
import Definitions.Def_BitcoinScript
open BitcoinTaproot BitcoinSer BitcoinSig BitcoinVerify
open BitcoinScript hiding Bytes Byte
Formal statement
theorem BitcoinTaproot.checksig_empty (c : TapCtx) (ed : ExecData) (ts : TapState) (pubkey : Bytes) (rest : List Bytes)
    (hs : ts.st.stack = pubkey :: [] :: rest) (hpk : pubkey.length = 32) :
    BitcoinTaproot.tapExecOp c ed true BitcoinScript.OP_CHECKSIG ts =
      some { ts with st := { ts.st with stack := BitcoinScript.boolBytes false :: rest } } := 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.checksig_empty

Binders. ccc : a TapCtx record (flags cltv, csv, nulldummy; transaction tx\mathrm{tx}tx; list spent\mathrm{spent}spent of outputs; index nIn∈N\mathrm{nIn} \in \mathbb{N}nIn∈N); ed\mathrm{ed}ed : an ExecData record; ts\mathrm{ts}ts : a TapState record with fields st\mathrm{st}st (interpreter state: main stack, alt stack, condition stack, op count), weightLeft∈Z\mathrm{weightLeft} \in \mathbb{Z}weightLeft∈Z, codeseparatorPos,opcodePos∈N\mathrm{codeseparatorPos}, \mathrm{opcodePos} \in \mathbb{N}codeseparatorPos,opcodePos∈N; pubkey\mathrm{pubkey}pubkey : a byte string; rest\mathrm{rest}rest : a list of byte strings.

Hypotheses.

  1. ts.st.stack=pubkey::[ ]::rest\mathrm{ts}.\mathrm{st}.\mathrm{stack} = \mathrm{pubkey} :: [\,] :: \mathrm{rest}ts.st.stack=pubkey::[]::rest — the main stack, top first, has pubkey\mathrm{pubkey}pubkey on top, then the empty byte string, then rest\mathrm{rest}rest;
  2. ∣pubkey∣=32|\mathrm{pubkey}| = 32∣pubkey∣=32.

Conclusion.

tapExecOp(c,ed,true,0xac,ts)=some(ts with st:=(ts.st with stack:=[ ]::rest)),\mathrm{tapExecOp}(c, \mathrm{ed}, \mathrm{true}, \texttt{0xac}, \mathrm{ts}) = \mathrm{some}\big(\mathrm{ts}\text{ with } \mathrm{st} := (\mathrm{ts}.\mathrm{st} \text{ with stack} := [\,] :: \mathrm{rest})\big),tapExecOp(c,ed,true,0xac,ts)=some(ts with st:=(ts.st with stack:=[]::rest)),

where 0xac\texttt{0xac}0xac is OP_CHECKSIG and [ ]=boolBytes(false)[\,] = \mathrm{boolBytes}(\mathrm{false})[]=boolBytes(false) is the empty byte string (vchFalse). All other fields — the alt stack, condition stack and op count of st\mathrm{st}st, and weightLeft\mathrm{weightLeft}weightLeft, codeseparatorPos\mathrm{codeseparatorPos}codeseparatorPos, opcodePos\mathrm{opcodePos}opcodePos of ts\mathrm{ts}ts — are those of ts\mathrm{ts}ts.

Unfolded. In tapExecOp\mathrm{tapExecOp}tapExecOp the opcode 0xac\texttt{0xac}0xac is neither OP_IF nor OP_NOTIF, so the second branch applies: the stack must match pubkey::sig::rest\mathrm{pubkey} :: \mathrm{sig} :: \mathrm{rest}pubkey::sig::rest (here sig=[ ]\mathrm{sig} = [\,]sig=[]), else the result would be none\mathrm{none}none. Then evalChecksigTapscript(c,ed′,sig,pubkey,ts.weightLeft)\mathrm{evalChecksigTapscript}(c, \mathrm{ed}', \mathrm{sig}, \mathrm{pubkey}, \mathrm{ts}.\mathrm{weightLeft})evalChecksigTapscript(c,ed′,sig,pubkey,ts.weightLeft) is computed, with ed′\mathrm{ed}'ed′ equal to ed\mathrm{ed}ed except codeseparatorPos :=ts.codeseparatorPos:= \mathrm{ts}.\mathrm{codeseparatorPos}:=ts.codeseparatorPos. That function sets success:=(sig≠[ ])\mathrm{success} := (\mathrm{sig} \neq [\,])success:=(sig=[]), here false\mathrm{false}false; weight:=weightLeft−50\mathrm{weight} := \mathrm{weightLeft} - 50weight:=weightLeft−50 if success\mathrm{success}success else weightLeft\mathrm{weightLeft}weightLeft, here unchanged; it returns none\mathrm{none}none if success∧weight<0\mathrm{success} \land \mathrm{weight} < 0success∧weight<0 (not the case), none\mathrm{none}none if ∣pubkey∣=0|\mathrm{pubkey}| = 0∣pubkey∣=0 (not the case), and for ∣pubkey∣=32|\mathrm{pubkey}| = 32∣pubkey∣=32 it returns none\mathrm{none}none only if success∧¬checkSchnorrSignature(… )\mathrm{success} \land \neg\mathrm{checkSchnorrSignature}(\dots)success∧¬checkSchnorrSignature(…), which is false since success\mathrm{success}success is false — so no signature verification is performed and the result is some(false,weightLeft)\mathrm{some}(\mathrm{false}, \mathrm{weightLeft})some(false,weightLeft). Back in tapExecOp\mathrm{tapExecOp}tapExecOp, since the opcode is not OP_CHECKSIGVERIFY, the new state has stack boolBytes(false)::rest=[ ]::rest\mathrm{boolBytes}(\mathrm{false}) :: \mathrm{rest} = [\,] :: \mathrm{rest}boolBytes(false)::rest=[]::rest and weightLeft:=weight=ts.weightLeft\mathrm{weightLeft} := \mathrm{weight} = \mathrm{ts}.\mathrm{weightLeft}weightLeft:=weight=ts.weightLeft.

Edge cases the quantifiers include. ts.weightLeft\mathrm{ts}.\mathrm{weightLeft}ts.weightLeft negative (no failure, since the budget test requires success\mathrm{success}success); rest\mathrm{rest}rest empty; a 32-byte pubkey\mathrm{pubkey}pubkey that is not a valid x-only key (never inspected); arbitrary transaction, spent\mathrm{spent}spent, nIn\mathrm{nIn}nIn and ed\mathrm{ed}ed; the condition stack of st\mathrm{st}st may be non-empty or contain false (the function is called with the execute flag true regardless).

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