Scalar multiplications compose
ProvedBitcoinMuSig.pmul_pmulbip327bip340bitcoinelliptic-curveformal-verificationfrostmathlibmultisignaturemusig2schnorrsecp256k1
pmul a (pmul b P) = pmul (a·b) P within the fuel bound.
Preamble
import Definitions.Def_BitcoinMuSig open BitcoinMuSig BitcoinSig BitcoinTaproot
Formal statement
theorem BitcoinMuSig.pmul_pmul (a b : ℕ) (P : Point) (hP : Valid P) (hPr : Reduced P)
(ha : a < 2 ^ 257) (hb : b < 2 ^ 257) (hab : a * b < 2 ^ 257) :
pmul a (pmul b P) = pmul (a * b) 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.pmul_pmul
Source file: Thm_BitcoinMuSig_pmul_pmul.lean (one theorem; it builds on the MuSig definition file, which itself uses the secp256k1 signature and Taproot definition files).
Statement. For all natural numbers and every executable point such that
- is Valid (, or a pair with ),
- is Reduced (if then and ),
- , , and ,
the following literal equality of executable points holds:
(The product is the natural-number product, not reduced mod .)
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.