Strict DER accepts only the canonical layout
ProvedBitcoinSig.derEncode_completeEvery signature IsValidSignatureEncoding accepts is derEncode r s ht for minimal with . 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.
import Definitions.Def_BitcoinSig open BitcoinSig BitcoinSer
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 sorryRead-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 , with one hypothesis : isValidSignatureEncoding = true. Unfolded, with and denoting the byte at index read as a number in (and if out of range), this means all of: ; 0x30; ; with , ; with , ; 0x02; ; 0x80; not ( and and 0x80); 0x02; ; 0x80; not ( and and 0x80). The last byte is unconstrained.
Conclusion. There exist byte strings , and a byte such that
Unfolding. derEncode is the byte string
of length . minimalInt is the proposition: is non-empty, its first byte is 0x80, and if and its first byte is then its second byte is 0x80. So the conclusion says: decomposes as a 0x30 byte, a length byte, a 0x02 tag, a length byte, the bytes , a 0x02 tag, a length byte, the bytes , and one trailing byte , where the two length bytes are the actual lengths of and (reduced mod 256, which is harmless since each is at most 65), the sequence-length byte is , both and 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 together with gives , and the hypothesis conditions on , , , are exactly the minimalInt conditions on and . 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 , , are unique (they are determined by , but uniqueness is not asserted). It does not bound or individually (e.g. it allows , ); only the sum is bounded. It does not say that or , read as big-endian integers, are below or non-zero as numbers (e.g. satisfies minimalInt). It does not say anything about (any byte). It does not relate 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.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.