Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Strict DER accepts only the canonical layout

Proved
BitcoinSig.derEncode_complete

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

bitcoinbitcoin-mainnetconsensusderecdsaformal-verificationschnorrsecp256k1sighash

Every signature IsValidSignatureEncoding accepts is derEncode r s ht for minimal r,sr, sr,s with ∣r∣+∣s∣≤66|r| + |s| \le 66∣r∣+∣s∣≤66. Together with soundness this characterizes BIP66's strict encoding: exactly the sequences 30 L 02 |r| r 02 |s| s ht with minimal positive integers and at most 73 bytes.

Formalization Note. The characterization is the goal because it is what every later layer consumes: the DERSIG rule is "the signature has this shape", and with it the lax parser and the strict test agree on their accepted values.

Preamble
import Definitions.Def_BitcoinSig
open BitcoinSig BitcoinSer
Formal statement
theorem BitcoinSig.derEncode_complete (sig : Bytes) (h : BitcoinSig.isValidSignatureEncoding sig = true) :
    ∃ (r s : Bytes) (ht : Byte), sig = BitcoinSig.derEncode r s ht ∧ BitcoinSig.minimalInt r ∧
      BitcoinSig.minimalInt s ∧ r.length + s.length ≤ 66 := 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.derEncode_complete

Binders and hypothesis. Universally quantified over a byte string sigsigsig, with one hypothesis hhh: isValidSignatureEncoding sigsigsig = true. Unfolded, with ℓ=∣sig∣\ell = |sig|ℓ=∣sig∣ and sig[i]sig[i]sig[i] denoting the byte at index iii read as a number in [0,255][0,255][0,255] (and 000 if out of range), this means all of: 9≤ℓ≤739 \leq \ell \leq 739≤ℓ≤73; sig[0]=sig[0] = sig[0]= 0x30; sig[1]=ℓ−3sig[1] = \ell - 3sig[1]=ℓ−3; with lenR=sig[3]lenR = sig[3]lenR=sig[3], 5+lenR<ℓ5 + lenR < \ell5+lenR<ℓ; with lenS=sig[5+lenR]lenS = sig[5 + lenR]lenS=sig[5+lenR], lenR+lenS+7=ℓlenR + lenS + 7 = \elllenR+lenS+7=ℓ; sig[2]=sig[2] = sig[2]= 0x02; lenR≠0lenR \neq 0lenR=0; sig[4]<sig[4] < sig[4]< 0x80; not (lenR>1lenR > 1lenR>1 and sig[4]=0sig[4] = 0sig[4]=0 and sig[5]<sig[5] <sig[5]< 0x80); sig[lenR+4]=sig[lenR + 4] =sig[lenR+4]= 0x02; lenS≠0lenS \neq 0lenS=0; sig[lenR+6]<sig[lenR+6] <sig[lenR+6]< 0x80; not (lenS>1lenS > 1lenS>1 and sig[lenR+6]=0sig[lenR+6] = 0sig[lenR+6]=0 and sig[lenR+7]<sig[lenR+7] <sig[lenR+7]< 0x80). The last byte sig[ℓ−1]sig[\ell - 1]sig[ℓ−1] is unconstrained.

Conclusion. There exist byte strings rrr, sss and a byte hththt such that

sig=derEncode r s ht∧minimalInt r∧minimalInt s∧∣r∣+∣s∣≤66.sig = \text{derEncode}\ r\ s\ ht \quad\land\quad \text{minimalInt}\ r \quad\land\quad \text{minimalInt}\ s \quad\land\quad |r| + |s| \leq 66 .sig=derEncode r s ht∧minimalInt r∧minimalInt s∧∣r∣+∣s∣≤66.

Unfolding. derEncode r s htr\,s\,htrsht is the byte string

[ 0x30, (∣r∣+∣s∣+4) mod 256, 0x02, ∣r∣ mod 256 ] ∥ r ∥ [ 0x02, ∣s∣ mod 256 ] ∥ s ∥ [ ht ],[\,\texttt{0x30},\ (|r|+|s|+4) \bmod 256,\ \texttt{0x02},\ |r| \bmod 256\,] \,\|\, r \,\|\, [\,\texttt{0x02},\ |s| \bmod 256\,] \,\|\, s \,\|\, [\,ht\,],[0x30, (∣r∣+∣s∣+4)mod256, 0x02, ∣r∣mod256]∥r∥[0x02, ∣s∣mod256]∥s∥[ht],

of length ∣r∣+∣s∣+7|r| + |s| + 7∣r∣+∣s∣+7. minimalInt vvv is the proposition: vvv is non-empty, its first byte is <<< 0x80, and if ∣v∣>1|v| > 1∣v∣>1 and its first byte is 000 then its second byte is ≥\geq≥ 0x80. So the conclusion says: sigsigsig decomposes as a 0x30 byte, a length byte, a 0x02 tag, a length byte, the bytes rrr, a 0x02 tag, a length byte, the bytes sss, and one trailing byte hththt, where the two length bytes are the actual lengths of rrr and sss (reduced mod 256, which is harmless since each is at most 65), the sequence-length byte is ∣r∣+∣s∣+4|r|+|s|+4∣r∣+∣s∣+4, both rrr and sss are non-empty with a clear top bit in their first byte and no superfluous leading zero, and together they occupy at most 66 bytes.

Relationship between hypothesis and conclusion. The hypothesis bound ℓ≤73\ell \leq 73ℓ≤73 together with ℓ=lenR+lenS+7\ell = lenR + lenS + 7ℓ=lenR+lenS+7 gives lenR+lenS≤66lenR + lenS \leq 66lenR+lenS≤66, and the hypothesis conditions on sig[4]sig[4]sig[4], sig[5]sig[5]sig[5], sig[lenR+6]sig[lenR+6]sig[lenR+6], sig[lenR+7]sig[lenR+7]sig[lenR+7] are exactly the minimalInt conditions on r=sig[4..4+lenR)r = sig[4 .. 4 + lenR)r=sig[4..4+lenR) and s=sig[lenR+6..lenR+6+lenS)s = sig[lenR + 6 .. lenR + 6 + lenS)s=sig[lenR+6..lenR+6+lenS). The theorem is thus the "completeness" direction: every string accepted by the strict encoding check has the derEncode shape with minimal integers.

What is not said. The statement does not say the witnesses rrr, sss, hththt are unique (they are determined by sigsigsig, but uniqueness is not asserted). It does not bound ∣r∣|r|∣r∣ or ∣s∣|s|∣s∣ individually (e.g. it allows ∣r∣=65|r| = 65∣r∣=65, ∣s∣=1|s| = 1∣s∣=1); only the sum is bounded. It does not say that rrr or sss, read as big-endian integers, are below nnn or non-zero as numbers (e.g. r=[0]r = [0]r=[0] satisfies minimalInt). It does not say anything about hththt (any byte). It does not relate sigsigsig to the lax parser parseDerLax, to checkLowS, or to signature verification. It does not say the converse (that every derEncode of minimal integers is accepted) — that is a separate statement. It says nothing about strings for which the encoding check fails.

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