Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

CPubKey::IsValid characterized

Proved
BitcoinSig.pubkeyValid_iff

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

bitcoinbitcoin-mainnetconsensusderecdsaformal-verificationschnorrsecp256k1sighash

A byte string is a valid CPubKey iff it has 33 bytes with header 02/03, or 65 bytes with header 04/06/07.

Preamble
import Definitions.Def_BitcoinSig
open BitcoinSig BitcoinSer
Formal statement
theorem BitcoinSig.pubkeyValid_iff (pk : Bytes) :
    BitcoinSig.pubkeyValid pk = true ↔
      (pk.length = 33 ∧ ((pk.getD 0 0).toNat = 2 ∨ (pk.getD 0 0).toNat = 3)) ∨
      (pk.length = 65 ∧ ((pk.getD 0 0).toNat = 4 ∨ (pk.getD 0 0).toNat = 6 ∨ (pk.getD 0 0).toNat = 7)) := 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.pubkeyValid_iff

Binders and hypothesis. Universally quantified over a byte string pkpkpk. No hypotheses.

Conclusion. pubkeyValid pkpkpk = true if and only if

(∣pk∣=33 ∧ (pk[0]=2∨pk[0]=3)) ∨ (∣pk∣=65 ∧ (pk[0]=4∨pk[0]=6∨pk[0]=7)),\big(|pk| = 33 \ \land\ (pk[0] = 2 \lor pk[0] = 3)\big)\ \lor\ \big(|pk| = 65 \ \land\ (pk[0] = 4 \lor pk[0] = 6 \lor pk[0] = 7)\big),(∣pk∣=33 ∧ (pk[0]=2∨pk[0]=3)) ∨ (∣pk∣=65 ∧ (pk[0]=4∨pk[0]=6∨pk[0]=7)),

where pk[0]pk[0]pk[0] denotes the numeric value of the first byte, taken to be 000 if pkpkpk is empty (the "get with default 000" accessor). In the right side the length conjuncts make the empty case irrelevant: an empty string has length 000, so neither disjunct can hold.

Unfolding the left side. pubkeyValid pkpkpk is: false if pkpkpk is empty; otherwise, with hhh the first byte, the Boolean decision of pubkeyLen hhh =∣pk∣= |pk|=∣pk∣, where pubkeyLen hhh is 333333 if h∈{2,3}h \in \{2,3\}h∈{2,3}, 656565 if h∈{4,6,7}h \in \{4,6,7\}h∈{4,6,7}, and 000 for every other header value. Since a non-empty string has positive length, the "000" case can never equal ∣pk∣|pk|∣pk∣, so validity amounts to: header 222 or 333 with length exactly 333333, or header 444, 666 or 777 with length exactly 656565. That is precisely the right side; the biconditional is a direct restatement of the definition with the default-accessor phrasing.

Edge cases. A 33-byte string starting with 0x04 is not valid; a 65-byte string starting with 0x02 is not valid; a string starting with any byte outside {2,3,4,6,7}\{2,3,4,6,7\}{2,3,4,6,7} is never valid regardless of length; the hybrid headers 0x06/0x07 are accepted at length 65.

What is not said. The statement does not say anything about whether the remaining bytes encode a point on the curve, whether the abscissa is below the field prime, or whether the parity announced by the header is consistent with the ordinate — pubkeyValid is a header/length test only, and the biconditional faithfully says no more. It does not relate pubkeyValid to parsePubkey, to isCompressedOrUncompressedPubKey (which rejects headers 6 and 7), or to isCompressedPubKey. It does not say anything about the flags or the encoding checks. It does not say that the right side is decidable or exclusive (the two disjuncts are in fact mutually exclusive by length, but that is not asserted).

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