The executable scalar multiplication is Mathlib's scalar action
ProvedBitcoinMuSig.tp_pmulbip327bip340bitcoinelliptic-curveformal-verificationfrostmathlibmultisignaturemusig2schnorrsecp256k1
For valid and : tp (pmul k P) = k • tp P.
Preamble
import Definitions.Def_BitcoinMuSig open BitcoinMuSig BitcoinSig BitcoinTaproot
Formal statement
theorem BitcoinMuSig.tp_pmul (k : ℕ) (P : Point) (hP : Valid P) (hk : k < 2 ^ 257) :
tp (pmul k P) = k • tp 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.tp_pmul
Source file: Thm_BitcoinMuSig_tp_pmul.lean (one theorem; it builds on the MuSig definition file, which itself uses the secp256k1 signature and Taproot definition files).
Statement. For every natural number with and every executable point that is Valid (, or a pair of naturals with ; coordinates need not be below ),
in the group , where the right side is the -fold sum of (for , the point ). Scalars are not covered.
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 ).
The Mathlib curve and its point group
- denotes Mathlib's . For a natural number , is its residue . The definition file registers, as a global instance, the fact that is prime (proved there by a Lucas–Pratt certificate); this instance is what makes a field, which Mathlib needs to put a group structure on curve points.
- is the Weierstrass curve over with coefficients and , i.e. the curve
- is Mathlib's type of points of : a point is either the point at infinity, written , or an affine point with (carrying a proof that it is nonsingular). It is equipped with Mathlib's chord-and-tangent addition, which makes it an additive commutative group with neutral element and negation , .
- For and , ( summands, ). For , is the usual integer multiple ( for ).
- is the affine point .
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 .
From executable points to Mathlib points
- takes values in (an optional Mathlib point):
- , the Mathlib point at infinity (a genuine point, not );
- if holds;
- otherwise.
- is with replaced by . Thus , for on-curve pairs, and for every off-curve pair (an off-curve pair has the same image as ). Pairs differing by multiples of in their coordinates have the same image.
- means: if is a pair then holds. is Valid. Validity does not require reduced coordinates.
- means: if is a pair then and . is Reduced. Reducedness does not require being on the curve.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.