Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Native P2WPKH is correct

Proved
BitcoinVerify.p2wpkh_correct

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

bip141bitcoinbitcoin-mainnetconsensusformal-verificationp2shsegwitverifyscript

With the WITNESS flag, for a 20-byte hhh and signature and key within 520 bytes:

verifyScript([ ], OP_0 ⟨h⟩, [sig,pk])=true  ⟺  castToBool(h)∧Hash160(pk)=h∧checkSigPreTapscriptWITNESS_V0(p2pkhBytes(h),sig,pk)=some true,\mathrm{verifyScript}\big([\,],\ \mathtt{OP\_0}\ \langle h\rangle,\ [sig, pk]\big) = \mathtt{true} \iff \mathrm{castToBool}(h) \wedge \mathrm{Hash160}(pk) = h \wedge \mathrm{checkSigPreTapscript}_{\mathrm{WITNESS\_V0}}(\text{p2pkhBytes}(h), sig, pk) = \mathrm{some}\ \mathtt{true},verifyScript([], OP_0 ⟨h⟩, [sig,pk])=true⟺castToBool(h)∧Hash160(pk)=h∧checkSigPreTapscriptWITNESS_V0​(p2pkhBytes(h),sig,pk)=some true,

where the signature check is the signature mission's checker under witness v0 (BIP143 sighash, DERSIG from the flags) on the implied script DUP HASH160 <h> EQUALVERIFY CHECKSIG. The first conjunct records that an all-zero key hash is unspendable: the base evaluation of OP_0 <h> leaves hhh on top and requires it true.

Formalization Note. verifyScript is the full VerifyScript control flow with the consensus flags; the equivalence holds for every flag set with WITNESS on, every transaction and amount, and every Taproot handler.

Preamble
import Definitions.Def_BitcoinVerify
import Definitions.Def_BitcoinScript
import Definitions.Def_BitcoinSer
import Definitions.Def_BitcoinSig
open BitcoinVerify BitcoinSer BitcoinSig
open BitcoinScript hiding Bytes Byte
Formal statement
theorem BitcoinVerify.p2wpkh_correct (tap : TaprootHandler) (c : Ctx) (sig pk h : Bytes)
    (hf : c.flags.witness = true) (hh : h.length = 20)
    (hsig : sig.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE)
    (hpk : pk.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE) :
    BitcoinVerify.verifyScript tap c [] (BitcoinVerify.witnessBytes 0 h) [sig, pk] = true ↔
      BitcoinScript.castToBool h = true ∧ BitcoinSer.hash160 pk = h ∧
      BitcoinSig.checkSigPreTapscript (BitcoinVerify.sigFlagsOf c.flags) c.tx c.nIn c.amount .witnessV0
        (BitcoinSig.p2pkhBytes h) sig pk = some true := by sorry
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: VerifyScript, VerifyWitnessProgram, ExecuteWitnessScript, src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp; CScript::IsPayToScriptHash, IsWitnessProgram, IsPushOnly, IsPayToAnchor, DecodeOP_N, src/script/script.cpp and script.h; MAX_SCRIPT_SIZE, WITNESS_V0_SCRIPTHASH_SIZE, WITNESS_V0_KEYHASH_SIZE, WITNESS_V1_TAPROOT_SIZE; BIP16, BIP141, BIP143 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: BitcoinVerify.p2wpkh_correct

Binders and hypothesis. Universally quantified: tap, a Taproot handler (any function from a context, a list of byte strings and a byte string to a Boolean); ccc, a verification context with fields c.flags (consensus flags), c.tx (a transaction), c.nIn (a natural number), c.amount (an integer); sig, pk, hhh, byte strings. Four hypotheses:

  • hf: c.flags.witness = true;
  • hh: ∣h∣=20|h| = 20∣h∣=20;
  • hsig: ∣sig∣≤520|\mathrm{sig}| \le 520∣sig∣≤520;
  • hpk: ∣pk∣≤520|\mathrm{pk}| \le 520∣pk∣≤520.

Conclusion. With π=witnessBytes(0,h)=0x00 0x14 h\pi = \mathrm{witnessBytes}(0, h) = \mathtt{0x00}\ \mathtt{0x14}\ hπ=witnessBytes(0,h)=0x00 0x14 h (22 bytes) and witness stack [sig,pk][\mathrm{sig}, \mathrm{pk}][sig,pk] (serialized order, pk last):

verifyScript(tap,c,[],π,[sig,pk])=true  ⟺  castToBool(h)=true ∧ hash160(pk)=h ∧ checkSigPreTapscript(F,c.tx,c.nIn,c.amount,witnessV0,p2pkhBytes(h),sig,pk)=some(true),\mathrm{verifyScript}(\mathrm{tap}, c, [], \pi, [\mathrm{sig}, \mathrm{pk}]) = \mathrm{true} \iff \mathrm{castToBool}(h) = \mathrm{true} \ \wedge\ \mathrm{hash160}(\mathrm{pk}) = h \ \wedge\ \mathrm{checkSigPreTapscript}(F, c.\mathrm{tx}, c.\mathrm{nIn}, c.\mathrm{amount}, \mathrm{witnessV0}, \mathrm{p2pkhBytes}(h), \mathrm{sig}, \mathrm{pk}) = \mathrm{some}(\mathrm{true}),verifyScript(tap,c,[],π,[sig,pk])=true⟺castToBool(h)=true ∧ hash160(pk)=h ∧ checkSigPreTapscript(F,c.tx,c.nIn,c.amount,witnessV0,p2pkhBytes(h),sig,pk)=some(true),

where F=sigFlagsOf(c.flags)=⟨dersig=c.flags.dersig, false, false, false⟩F = \mathrm{sigFlagsOf}(c.\mathrm{flags}) = \langle \mathrm{dersig} = c.\mathrm{flags.dersig},\ \mathrm{false},\ \mathrm{false},\ \mathrm{false}\rangleF=sigFlagsOf(c.flags)=⟨dersig=c.flags.dersig, false, false, false⟩ and p2pkhBytes(h)=0x76 0xa9 0x14 h 0x88 0xac\mathrm{p2pkhBytes}(h) = \mathtt{0x76}\ \mathtt{0xa9}\ \mathtt{0x14}\ h\ \mathtt{0x88}\ \mathtt{0xac}p2pkhBytes(h)=0x76 0xa9 0x14 h 0x88 0xac.

Unfolding the left-hand side. The scriptSig is empty: evalBytes c base [] [] parses to no instructions and yields the empty stack. Then π\piπ is evaluated on it with version base: the byte 0x00\mathtt{0x00}0x00 parses as a push of the empty string, and 0x14 h\mathtt{0x14}\ h0x14 h as a push of hhh; the resulting top-first stack is [h,[]][h, []][h,[]]. topTrue of it is castToBool(h)\mathrm{castToBool}(h)castToBool(h): false when all 20 bytes are zero, or all zero except a final 0x80\mathtt{0x80}0x80; so the verification is false in that case. Otherwise the native branch: c.flags.witness is true (hf); isWitnessProgram π is some(0,h)\mathrm{some}(0, h)some(0,h) (length 22∈[4,42]22 \in [4, 42]22∈[4,42], first byte 000, second byte 20=22−220 = 22 - 220=22−2); the scriptSig is empty, so the verdict is verifyWitnessProgram tap c [sig, pk] 0 h false and verifyScript returns exactly that Boolean (no P2SH branch, no further witness check).

Unfolding verifyWitnessProgram here. Version 000 and ∣h∣=20|h| = 20∣h∣=20 (the keyhash size), so the witness must have exactly 222 elements (it does), and the result is executeWitnessScriptV0 c [pk, sig] (p2wpkhExec h): the witness is reversed, so pk is the interpreter's top and sig is beneath it, and p2wpkhExec h = p2pkhBytes h.

Unfolding executeWitnessScriptV0. No stack element may exceed 520 bytes (hsig, hpk ensure this); then evalBytes c witnessV0 [pk, sig] (p2pkhBytes h) runs: the 26-byte script passes the 100001000010000 test and parses as OP_DUP, OP_HASH160, push hhh, OP_EQUALVERIFY, OP_CHECKSIG. The interpreter (flags scriptFlagsOf c.flags, oracle legacyOracle F c.tx c.nIn c.amount witnessV0 (p2pkhBytes h)) does: OP_DUP → [pk,pk,sig][\mathrm{pk}, \mathrm{pk}, \mathrm{sig}][pk,pk,sig]; OP_HASH160 → [hash160(pk),pk,sig][\mathrm{hash160}(\mathrm{pk}), \mathrm{pk}, \mathrm{sig}][hash160(pk),pk,sig]; push → [h,hash160(pk),pk,sig][h, \mathrm{hash160}(\mathrm{pk}), \mathrm{pk}, \mathrm{sig}][h,hash160(pk),pk,sig]; OP_EQUALVERIFY → fails unless h=hash160(pk)h = \mathrm{hash160}(\mathrm{pk})h=hash160(pk), else [pk,sig][\mathrm{pk}, \mathrm{sig}][pk,sig]; OP_CHECKSIG pops pubkey pk and signature sig and consults the oracle, which is checkSigPreTapscript F c.tx c.nIn c.amount witnessV0 (p2pkhBytes h) sig pk: a result of "nothing" (an encoding check failed: dersig on and sig not valid DER, the other encoding flags being off) fails the script; some ok pushes [0x01][\mathtt{0x01}][0x01] if ok else the empty string. The final stack has exactly one element and topTrue of it equals ok. Hence the left side is true iff castToBool(h)\mathrm{castToBool}(h)castToBool(h), hash160(pk)=h\mathrm{hash160}(\mathrm{pk}) = hhash160(pk)=h, and the oracle returns some true — which is the right side. In checkSigPreTapscript with version witnessV0, the script code is p2pkhBytes h unchanged, and the ECDSA check uses the BIP143-style digest with c.amount and returns false when c.amount < 0.

What is not said. Nothing about any witness stack other than exactly two elements in the order [sig, pk]; nothing when the witness flag is off; nothing about ∣h∣≠20|h| \ne 20∣h∣=20; nothing about elements over 520 bytes; nothing about what checkSigPreTapscript means cryptographically — it appears unexpanded on the right; nothing about the handler tap or the taproot, p2sh flags, which are not consulted on this path. The theorem does not claim the key is compressed or that the signature is low-S (those flags are hard-wired off by sigFlagsOf).

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