Parsed compressed points are reduced curve points
ProvedBitcoinMuSig.cpoint_specbip327bip340bitcoinelliptic-curveformal-verificationfrostmathlibmultisignaturemusig2schnorrsecp256k1
cpoint b = some P → onCurve P ∧ P.1 < p ∧ P.2 < p.
Preamble
import Definitions.Def_BitcoinMuSig import Definitions.Def_BitcoinSer open BitcoinMuSig BitcoinSig BitcoinTaproot
Formal statement
theorem BitcoinMuSig.cpoint_spec (b : BitcoinSer.Bytes) (P : ℕ × ℕ) (h : cpoint b = some P) :
onCurve P = true ∧ P.1 < p ∧ P.2 < p := by sorrySource
BIP327 MuSig2 for BIP340-compatible multi-signatures (KeyAgg, ApplyTweak, NonceAgg, GetSessionValues, PartialSigVerifyInternal, PartialSigAgg): https://github.com/bitcoin/bips/blob/master/bip-0327.mediawiki; BIP340 Schnorr signatures; RFC 9591 FROST (Lagrange-coefficient aggregation); secp256k1 (SEC 2); Mathlib's WeierstrassCurve.Affine group law; the signature mission's executable curve (BitcoinSig.padd, pmul, schnorrVerify)
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: BitcoinMuSig.cpoint_spec
Source file: Thm_BitcoinMuSig_cpoint_spec.lean (one theorem; it builds on the MuSig definition file, which itself uses the secp256k1 signature and Taproot definition files).
Statement. For every byte string and every pair of natural numbers: if succeeds and returns , then
- holds, i.e. ,
- , and
- .
Byte strings on which fails (wrong length, first byte not or , abscissa , or no square root) satisfy the hypothesis for no and are not constrained.
Definitions used, unfolded
Constants
- is a fixed natural number (the field modulus).
- is a fixed natural number (written in hexadecimal).
- and are fixed natural numbers ( is even: its last hexadecimal digit is ).
Executable points and their arithmetic
- An executable point is either the special value (the code's "no coordinates" value, which it uses for the point at infinity) or a pair of natural numbers of arbitrary size. Nothing in the type requires or that the pair lies on the curve. Equality of executable points is literal equality: both , or equal pairs of natural numbers (so and are different executable points).
- Curve test. For naturals : holds iff
i.e. . Pairs with unreduced coordinates ( or ) can pass this test.
- Modular powers and inversion. is a square-and-multiply loop; the definition file proves for all naturals . The field inverse is ; in particular when .
- Addition :
- and , returned unchanged (unreduced coordinates stay unreduced).
- For , with :
- if the result is ;
- otherwise (tangent branch, which uses only ):
and the result is $(x_3, y_3)$.
- For , with (chord branch):
and the result is $(x_3, y_3)$.
- All subtractions are of natural numbers but never truncate here (the subtracted quantity never exceeds the other). Whenever both inputs are pairs, the output is or a pair with both coordinates .
- Scalar multiplication for : a least-significant-bit-first double-and-add loop with a fuel of exactly iterations. Starting from , each iteration does: if , stop and return ; otherwise replace by if is odd (else keep it), then replace by and by . When the iterations are exhausted the current is returned. Consequently only the lowest bits of are ever used: . Also and .
- denotes the executable point .
Byte strings, hashing and point encodings
- A byte string is a finite list of bytes (values ). is its length, is concatenation. is the first bytes of and is with its first bytes removed, so a slice of a too-short string is silently shorter (possibly empty).
- is the big-endian value of (any length; of the empty string is ).
- is the -byte big-endian encoding of (bits of above are silently dropped).
- For a pair of naturals: ; holds iff (parity of the raw natural , no reduction mod ); , a -byte string whose first byte is if and otherwise.
- is the string of zero bytes. and for a pair .
- is the executable SHA-256 function of the serialization definition file. is the UTF-8 byte string of a text string . The tagged hash is
Parsing compressed points
- for a natural and a requested parity: let (computed by ; is natural-number division). If , the result is the pair where if the parity of is the requested one and otherwise (if then whatever parity was requested); if not, the result is a failure.
- parses a byte string as a compressed point. If it fails. If , write with : if it fails; otherwise let ; if it fails, and if the result is (which may itself fail). A successful result is a pair of naturals.
- Important typing fact. The result of has the same type as an executable point, and its failure value is literally the value . So wherever is used as an executable point, a parse failure is the point at infinity.
- : if the result is "success with "; otherwise it is "success with the pair " when succeeds, and failure when it fails. (Here failure and are distinct outcomes.)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.