FROST correctness on secp256k1
ProvedBitcoinMuSig.frost_correct_secp256k1frost_correct on Mathlib's points of with ZMod n scalars acting through their representatives.
import Definitions.Def_BitcoinMuSig open BitcoinMuSig BitcoinSig BitcoinTaproot
theorem BitcoinMuSig.frost_correct_secp256k1 (S : Finset ℕ) (hS : ∀ i ∈ S, i < n)
(f : Polynomial (ZMod n)) (hdeg : f.degree < S.card) (D E : ℕ → W.Point) (ρ z : ℕ → ZMod n)
(c : ZMod n)
(hz : ∀ i ∈ S, (z i).val • Gpt =
D i + (ρ i).val • E i + (c * lagrangeCoeff S i).val • ((f.eval (i : ZMod n)).val • Gpt)) :
(∑ i ∈ S, z i).val • Gpt = ∑ i ∈ S, (D i + (ρ i).val • E i) + c.val • ((f.eval 0).val • Gpt) := 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: BitcoinMuSig.frost_correct_secp256k1
Source file: Thm_BitcoinMuSig_frost_correct_secp256k1.lean (one theorem; it builds on the MuSig definition file, which itself uses the secp256k1 signature and Taproot definition files).
Statement. Let
- be a finite set of natural numbers with for every ( allowed, may be empty);
- with (i.e. , or ; for this forces );
- be arbitrary families of curve points (written );
- be arbitrary families of residues and arbitrary.
Write for the canonical representative of , and . Assume that for every
in , where is evaluated at the residue , the product is computed in before taking , and "" is the natural-number multiple in the group. Then
where is computed in (reduced mod ) before taking , and the right-hand sum is in the group .
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 .
Residues mod , Lagrange coefficients and polynomials
- is Mathlib's ; for a natural , is its residue . Mathlib's inverse on is a total function: it is the multiplicative inverse when is coprime to , and . (The definition file does not register primality of as an instance.)
- For a finite set and ,
where the subtraction is in . The empty product is (e.g. or ), and need not belong to (then nothing is removed). A factor with , , would be .
- For a polynomial , is its evaluation at . Its degree takes values in with , which is smaller than every natural number. So means: , or and . For it forces .
- For , is its canonical natural representative.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.