Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

P2PKH is correct against Core's concrete signature checker

Proved
BitcoinSig.p2pkh_concrete

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

bitcoinbitcoin-mainnetconsensusderecdsaformal-verificationschnorrsecp256k1sighash

For every flag setting, transaction, input index, amount and signature version, and every signature, key and hash within the 520-byte push limit:

verifyScriptPlain(legacyOracle(tx,nIn,p2pkhBytes(h)), [⟨sig⟩,⟨pk⟩], DUP HASH160 ⟨h⟩ EQUALVERIFY CHECKSIG)=true\mathrm{verifyScriptPlain}\big(\mathrm{legacyOracle}(tx, nIn, \text{p2pkhBytes}(h)),\ [\langle sig\rangle, \langle pk\rangle],\ \mathtt{DUP\ HASH160}\ \langle h\rangle\ \mathtt{EQUALVERIFY\ CHECKSIG}\big) = \mathtt{true}verifyScriptPlain(legacyOracle(tx,nIn,p2pkhBytes(h)), [⟨sig⟩,⟨pk⟩], DUP HASH160 ⟨h⟩ EQUALVERIFY CHECKSIG)=true   ⟺  Hash160(pk)=h  ∧  checkSigPreTapscript(tx,nIn,p2pkhBytes(h),sig,pk)=some true,\iff \mathrm{Hash160}(pk) = h \;\wedge\; \mathrm{checkSigPreTapscript}(tx, nIn, \text{p2pkhBytes}(h), sig, pk) = \mathrm{some}\ \mathtt{true},⟺Hash160(pk)=h∧checkSigPreTapscript(tx,nIn,p2pkhBytes(h),sig,pk)=some true,

where the oracle is Core's RIPEMD-160∘SHA-256 and the pre-tapscript checker. Composed with checkSig_base_iff, the right-hand side is: valid encodings, a valid key, and ECDSA verification of the legacy sighash. This instantiates the Script mission's abstract P2PKH theorem with the concrete cryptography and sighash of the pinned source.

Preamble
import Definitions.Def_BitcoinSig
import Definitions.Def_BitcoinScript
import Definitions.Def_BitcoinSer
open BitcoinSig BitcoinSer
Formal statement
theorem BitcoinSig.p2pkh_concrete (f : SigFlags) (fl : BitcoinScript.Flags) (tx : Tx) (nIn : Nat) (amount : Int)
    (v : SigVersion) (sig pk h : Bytes)
    (hsig : sig.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE)
    (hpk : pk.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE)
    (hh : h.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE) :
    BitcoinScript.verifyScriptPlain fl (BitcoinSig.legacyOracle f tx nIn amount v (BitcoinSig.p2pkhBytes h))
        [.push sig, .push pk] (BitcoinScript.p2pkhScript h) = true ↔
      BitcoinSer.hash160 pk = h ∧
      BitcoinSig.checkSigPreTapscript f tx nIn amount v (BitcoinSig.p2pkhBytes h) sig pk = some 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.p2pkh_concrete

Binders and hypothesis. Universally quantified over: a signature-layer flag record fff (Booleans dersig, lowS, strictenc, witnessPubkeyType); an interpreter flag record flflfl (Booleans cltv, csv, nulldummy); a transaction txtxtx; a natural number nInnInnIn; an integer amountamountamount; a signature version v∈{base,witnessV0}v \in \{\text{base}, \text{witnessV0}\}v∈{base,witnessV0}; and three byte strings sigsigsig, pkpkpk, hhh. Three hypotheses, each bounding a length by MAX_SCRIPT_ELEMENT_SIZE =520= 520=520:

  • hsighsighsig: ∣sig∣≤520|sig| \leq 520∣sig∣≤520;
  • hpkhpkhpk: ∣pk∣≤520|pk| \leq 520∣pk∣≤520;
  • hhhhhh: ∣h∣≤520|h| \leq 520∣h∣≤520. Nothing else is assumed: nInnInnIn may be out of range, amountamountamount may be negative, hhh need not have length 20, vvv may be witnessV0 even though the interpreter being run is the legacy one.

Conclusion. Let OOO denote the oracle legacyOracle f tx nIn amount vf\,tx\,nIn\,amount\,vftxnInamountv (p2pkhBytes hhh): the record whose hash functions are the serialization file's RIPEMD-160, SHA-1, SHA-256, Hash160 (RIPEMD-160 of SHA-256) and Hash256 (double SHA-256), whose checkSig s ks\,ksk is checkSigPreTapscript f tx nIn amount vf\,tx\,nIn\,amount\,vftxnInamountv (p2pkhBytes hhh) s ks\,ksk, and whose lock-time and sequence checks are checkLockTime tx nIntx\,nIntxnIn and checkSequence tx nIntx\,nIntxnIn. Then

verifyScriptPlain fl O [push sig, push pk] (p2pkhScript h)=true\text{verifyScriptPlain}\ fl\ O\ [\text{push}\ sig,\ \text{push}\ pk]\ (\text{p2pkhScript}\ h) = \text{true}verifyScriptPlain fl O [push sig, push pk] (p2pkhScript h)=true

if and only if

hash160 pk=h∧checkSigPreTapscript f tx nIn amount v (p2pkhBytes h) sig pk=some true.\text{hash160}\ pk = h \quad\land\quad \text{checkSigPreTapscript}\ f\ tx\ nIn\ amount\ v\ (\text{p2pkhBytes}\ h)\ sig\ pk = \text{some true}.hash160 pk=h∧checkSigPreTapscript f tx nIn amount v (p2pkhBytes h) sig pk=some true.

Unfolding the left side. verifyScriptPlain fl O ss spkfl\,O\,ss\,spkflOssspk evaluates the script ssssss on the empty stack; if that fails ("none") the result is false; otherwise it evaluates spkspkspk on the resulting stack; if that fails or leaves an empty stack the result is false; otherwise the result is castToBool of the top element (some byte is non-zero, except that a lone 0x80 after zeros counts as false). Evaluation starts from the state (main stack [ ][\,][], alt stack [ ][\,][], condition stack [ ][\,][], op count 000) and processes instructions in order; at the end the condition stack must be empty (it is, since no OP_IF occurs). Stacks are written top-first.

Script 1: push sigsigsig — fails if ∣sig∣>520|sig| > 520∣sig∣>520 (excluded by hsighsighsig), else pushes; stack [sig][sig][sig]. push pkpkpk — likewise; stack [pk,sig][pk, sig][pk,sig]. The 1000-element stack limit is never approached.

Script 2: p2pkhScript hhh is [op 0x76, op 0xa9, push h, op 0x88, op 0xac][\text{op}\ \texttt{0x76},\ \text{op}\ \texttt{0xa9},\ \text{push}\ h,\ \text{op}\ \texttt{0x88},\ \text{op}\ \texttt{0xac}][op 0x76, op 0xa9, push h, op 0x88, op 0xac] (OP_DUP, OP_HASH160, the push, OP_EQUALVERIFY, OP_CHECKSIG). Each opcode byte exceeds OP_16 and so is counted toward the 201-op limit (reaching 4, far below); none is disabled. OP_DUP duplicates the top: [pk,pk,sig][pk, pk, sig][pk,pk,sig]. OP_HASH160 replaces the top by O.hash160O.\text{hash160}O.hash160 of it, i.e. BitcoinSer.hash160 pkpkpk: [hash160 pk,pk,sig][\text{hash160}\ pk, pk, sig][hash160 pk,pk,sig]. push hhh — fails if ∣h∣>520|h| > 520∣h∣>520 (excluded by hhhhhh): [h,hash160 pk,pk,sig][h, \text{hash160}\ pk, pk, sig][h,hash160 pk,pk,sig]. OP_EQUALVERIFY pops two elements a=ha = ha=h, b=hash160 pkb = \text{hash160}\ pkb=hash160 pk and succeeds (removing both) exactly when b=ab = ab=a as byte strings, failing the whole script otherwise: [pk,sig][pk, sig][pk,sig]. OP_CHECKSIG pops pubkey=pkpubkey = pkpubkey=pk and sigsigsig and calls O.checkSig sig pkO.\text{checkSig}\ sig\ pkO.checkSig sig pk = checkSigPreTapscript f tx nIn amount vf\,tx\,nIn\,amount\,vftxnInamountv (p2pkhBytes hhh) sig pksig\,pksigpk: "none" fails the script; "some okokok" pushes [1][1][1] if okokok is true, or [ ][\,][] if false. Final stack: [[1]][[1]][[1]] or [[ ]][[\,]][[]]; castToBool gives true exactly for [1][1][1]. So the left side is true precisely when the equality check passed and the oracle returned "some true".

Unfolding the right side's second conjunct. checkSigPreTapscript with script code p2pkhBytes hhh =[0x76,0xa9] ∥ pushBytes h ∥ [0x88,0xac]= [\texttt{0x76}, \texttt{0xa9}] \,\|\, \text{pushBytes}\ h \,\|\, [\texttt{0x88}, \texttt{0xac}]=[0x76,0xa9]∥pushBytes h∥[0x88,0xac]: if vvv = base the script code first has every raw-byte occurrence of pushBytes sigsigsig at instruction boundaries deleted (findAndDelete); if vvv = witnessV0 it is used unchanged. The result is "none" if checkSignatureEncoding f sigf\,sigfsig or checkPubKeyEncoding f v pkf\,v\,pkfvpk fails, else "some" of checkECDSASignature tx nIn amount v sig pk sctx\,nIn\,amount\,v\,sig\,pk\,sctxnInamountvsigpksc: false unless pubkeyValid pkpkpk and sigsigsig non-empty; otherwise, with hththt the last byte of sigsigsig and sig′sig'sig′ the rest, the signature hash is sigHashLegacy sc tx nIn htsc\,tx\,nIn\,htsctxnInht (for base) or sigHashWitnessV0 sc tx nIn ht amountsc\,tx\,nIn\,ht\,amountsctxnInhtamount (for witnessV0, with "false" if amount<0amount < 0amount<0), and the verdict is pubkeyVerify pk sighash sig′pk\,sighash\,sig'pksighashsig′.

What is not said. The statement does not say anything if any of the three lengths exceeds 520 (then the left side is false by a push failure while the right side may still hold; the hypotheses are what make the backward direction true). It does not say the interpreter flags flflfl matter — they are never consulted on this script path (no CLTV, CSV or multisig), and the statement quantifies over them without using them. It does not restrict vvv to base: for witnessV0 the oracle still runs the legacy interpreter but hashes with the BIP143 algorithm, and the statement covers that combination too. It does not say ∣h∣=20|h| = 20∣h∣=20. It does not say that p2pkhBytes hhh is the byte serialization of p2pkhScript hhh (that is a separate statement), nor that the script code passed to the oracle "is" the executed script in any sense beyond the way OOO was built. It does not distinguish the script-error outcome "none" of the signature check from "some false": both make the left side false and the right side false. It does not say anything about OP_CODESEPARATOR, about the findAndDelete step altering p2pkhBytes hhh (it can, if pushBytes sigsigsig happens to occur in it), or about the cryptographic meaning of the verdict.

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