FROST correctness with Shamir shares
ProvedBitcoinMuSig.frost_correctIn a ZMod n-module, with shares of a polynomial of degree below : , the Schnorr equation for the group key .
import Definitions.Def_BitcoinMuSig open BitcoinMuSig BitcoinSig BitcoinTaproot
theorem BitcoinMuSig.frost_correct {M : Type*} [AddCommGroup M] [Module (ZMod n) M] (G : M)
(S : Finset ℕ) (hS : ∀ i ∈ S, i < n) (f : Polynomial (ZMod n)) (hdeg : f.degree < S.card)
(D E : ℕ → M) (ρ z : ℕ → ZMod n) (c : ZMod n)
(hz : ∀ i ∈ S, z i • G = D i + ρ i • E i + (c * lagrangeCoeff S i) • (f.eval (i : ZMod n) • G)) :
(∑ i ∈ S, z i) • G = ∑ i ∈ S, (D i + ρ i • E i) + c • (f.eval 0 • G) := 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
Source file: Thm_BitcoinMuSig_frost_correct.lean (one theorem; it builds on the MuSig definition file, which itself uses the secp256k1 signature and Taproot definition files).
Statement. Let be any type equipped with an additive commutative group structure and a -module structure (a scalar multiplication , written , satisfying the module axioms with respect to the addition of ; may be the trivial group). Let
- be arbitrary (a universally quantified element of , not the secp256k1 generator);
- be a finite set of natural numbers with for every (so distinct elements of have distinct residues mod ; is allowed, and may be empty);
- be a polynomial with (i.e. , or ; for this forces );
- and be arbitrary families (written ), and arbitrary.
Assume that for every
where means evaluated at the residue and . Then
All scalars and sums of scalars are computed in . Values of at indices outside play no role. If (so ) both sides are .
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 ).
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.