Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The legacy checker unfolded

Proved
BitcoinSig.checkSig_base_iff

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

bitcoinbitcoin-mainnetconsensusderecdsaformal-verificationschnorrsecp256k1sighash

checkSigPreTapscript f tx nIn amount BASE scriptCode sig pk = some true iff CheckSignatureEncoding and CheckPubKeyEncoding pass, the key is valid, and sig=sig′++[ht]sig = sig' ++ [ht]sig=sig′++[ht] with pubkeyVerify pk (sigHashLegacy (FindAndDelete scriptCode ⟨sig⟩) tx nIn ht) sig': the signature check is ECDSA verification of the legacy sighash of the signature-deleted script code, under the hash type given by the last byte.

Preamble
import Definitions.Def_BitcoinSig
open BitcoinSig BitcoinSer
Formal statement
theorem BitcoinSig.checkSig_base_iff (f : SigFlags) (tx : Tx) (nIn : Nat) (amount : Int)
    (scriptCode sig pk : Bytes) :
    BitcoinSig.checkSigPreTapscript f tx nIn amount .base scriptCode sig pk = some true ↔
      BitcoinSig.checkSignatureEncoding f sig = true ∧ BitcoinSig.checkPubKeyEncoding f .base pk = true ∧
      BitcoinSig.pubkeyValid pk = true ∧
      ∃ (sig' : Bytes) (ht : Byte), sig = sig' ++ [ht] ∧
        BitcoinSig.pubkeyVerify pk
          (BitcoinSig.sigHashLegacy (BitcoinSig.findAndDelete scriptCode (BitcoinSig.pushBytes sig)).1 tx nIn ht.toNat)
          sig' = true := by sorry
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: IsValidSignatureEncoding, IsLowDERSignature, IsCompressedOrUncompressedPubKey, IsCompressedPubKey, IsDefinedHashtypeSignature, CheckSignatureEncoding, CheckPubKeyEncoding, FindAndDelete, CTransactionSignatureSerializer, SignatureHash (BASE and WITNESS_V0), EvalChecksigPreTapscript, GenericTransactionSignatureChecker::CheckECDSASignature/CheckLockTime/CheckSequence, src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp; GetScriptOp, src/script/script.cpp; CPubKey::IsValid/Verify/CheckLowS and ecdsa_signature_parse_der_lax, src/pubkey.cpp and pubkey.h; secp256k1_eckey_pubkey_parse (src/secp256k1/src/eckey_impl.h), secp256k1_ecdsa_sig_verify (ecdsa_impl.h), secp256k1_schnorrsig_verify (modules/schnorrsig/main_impl.h); BIP66, BIP143, BIP340 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: BitcoinSig.checkSig_base_iff

Binders and hypothesis. The statement is universally quantified over: a flag record fff (four Booleans: dersig, lowS, strictenc, witnessPubkeyType); a transaction txtxtx (fields: natural-number version, list of inputs vin, list of outputs vout, natural-number nLockTime); a natural number nInnInnIn (an input index, not required to be in range); an integer amountamountamount; and three byte strings scriptCodescriptCodescriptCode, sigsigsig, pkpkpk. There are no hypotheses: the statement is an unconditional biconditional.

Conclusion. The following two statements are equivalent.

Left side. The pre-tapscript signature check in base mode, namely checkSigPreTapscript f tx nIn amount base scriptCode sig pkf\,tx\,nIn\,amount\,\text{base}\,scriptCode\,sig\,pkftxnInamountbasescriptCodesigpk, returns the value "some true". Unfolding that definition: let scscsc be the first component of findAndDelete scriptCodescriptCodescriptCode (pushBytes sigsigsig), i.e. scriptCodescriptCodescriptCode with every raw-byte occurrence of the canonical push encoding of sigsigsig removed at instruction boundaries (the push encoding is the length byte followed by sigsigsig when ∣sig∣<76|sig| < 76∣sig∣<76, and the 0x4c/0x4d/0x4e forms for longer data; for the empty signature it is the single byte 0x00). The result is "none" if checkSignatureEncoding f sigf\,sigfsig is false or checkPubKeyEncoding f base pkf\,\text{base}\,pkfbasepk is false; otherwise it is "some" of checkECDSASignature tx nIn amount base sig pk sctx\,nIn\,amount\,\text{base}\,sig\,pk\,sctxnInamountbasesigpksc, which is: false if pubkeyValid pkpkpk fails or sigsigsig is empty; otherwise, writing sig=sig′ ∥ [ht]sig = sig' \,\|\, [ht]sig=sig′∥[ht] with hththt the last byte, the Boolean pubkeyVerify pkpkpk (sigHashLegacy sc tx nIn htsc\,tx\,nIn\,htsctxnInht) sig′sig'sig′. In base mode the amount is never consulted.

Right side. The conjunction of four things:

  1. checkSignatureEncoding f sigf\,sigfsig = true — which holds vacuously if sigsigsig is empty, and otherwise requires: strict DER structure (isValidSignatureEncoding) whenever any of fff.dersig, fff.lowS, fff.strictenc is set; additionally low-SSS of the signature without its final byte (isLowDERSignature) when fff.lowS is set; additionally that the last byte masked with 0x7f lies in {1,2,3}\{1,2,3\}{1,2,3} when fff.strictenc is set;
  2. checkPubKeyEncoding f base pkf\,\text{base}\,pkfbasepk = true — i.e. if fff.strictenc then pkpkpk is 65 bytes starting with 0x04 or 33 bytes starting with 0x02/0x03; the witnessPubkeyType flag has no effect in base mode;
  3. pubkeyValid pkpkpk = true — pkpkpk is non-empty and its length equals the length its first byte announces (33 for 0x02/0x03, 65 for 0x04/0x06/0x07, otherwise an impossible 0);
  4. there exist a byte string sig′sig'sig′ and a byte hththt with sig=sig′ ∥ [ht]sig = sig' \,\|\, [ht]sig=sig′∥[ht] and
pubkeyVerify pk (sigHashLegacy sc tx nIn ht) sig′=true,\text{pubkeyVerify}\ pk\ \big(\text{sigHashLegacy}\ sc\ tx\ nIn\ ht\big)\ sig' = \text{true},pubkeyVerify pk (sigHashLegacy sc tx nIn ht) sig′=true,

where scscsc is exactly the findAndDelete result described above and hththt is used as the natural number in [0,255][0,255][0,255] it denotes.

Further unfolding of the verification. pubkeyVerify pk hash sig′pk\,hash\,sig'pkhashsig′ is: false unless pubkeyValid pkpkpk; false unless parsePubkey pkpkpk yields an affine point QQQ (compressed keys are lifted from the abscissa with the announced parity; uncompressed/hybrid keys must have both coordinates below ppp, satisfy y2≡x3+7y^2 \equiv x^3 + 7y2≡x3+7, and for hybrid tags the announced parity); false unless the lax DER parser accepts sig′sig'sig′ with some pair (r,s)(r,s)(r,s) (overflowing or over-long integers give (0,0)(0,0)(0,0) rather than rejection); otherwise the raw ECDSA check with message e=e = e= (big-endian value of hashhashhash)  mod n\bmod nmodn, with rrr, and with sss replaced by n−sn - sn−s whenever s>⌊n/2⌋s > \lfloor n/2 \rfloors>⌊n/2⌋: false if rrr or sss is 000 or ≥n\geq n≥n, else R=(es−1 mod n) G+(rs−1 mod n) QR = (e s^{-1} \bmod n)\,G + (r s^{-1} \bmod n)\,QR=(es−1modn)G+(rs−1modn)Q must be finite with Rx mod n=rR_x \bmod n = rRx​modn=r. sigHashLegacy sc tx nIn htsc\,tx\,nIn\,htsctxnInht is the constant uint256One (byte 1 followed by 31 zero bytes) if ht&31=3ht \mathbin{\&} 31 = 3ht&31=3 and ∣tx.vout∣≤nIn|tx.\text{vout}| \leq nIn∣tx.vout∣≤nIn, and otherwise the double SHA-256 of the legacy signature serialization of txtxtx with script code scscsc (with OP_CODESEPARATOR instructions removed) at input nInnInnIn under hash type hththt, followed by the 4-byte little-endian hththt.

What is not said. The statement does not say anything about witnessV0 mode. It does not say that amountamountamount matters (it is bound but inert). It does not assert that the existential decomposition sig=sig′∥[ht]sig = sig' \| [ht]sig=sig′∥[ht] is unique (though it is, since hththt is the last byte). It does not say what happens when the left side is "none" versus "some false": both are lumped into "not some true", so the right side being false does not distinguish an encoding failure from a failed verification. It does not say that the findAndDelete step leaves scriptCodescriptCodescriptCode unchanged, nor that any of the four conjuncts is independent of the others (e.g. conjunct 3 is already implied by conjunct 4's pubkeyVerify). It does not relate the result to any notion of a "correct" signature; it is a restatement of the checker's control flow as a conjunction.

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

    Confirmed by the moderator at approval.

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