Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

FROST correctness with Shamir shares

Proved
BitcoinMuSig.frost_correct

by pitimespi · Oct 30, 2026 · Mathlib 0df444a (Lean v4.33.1)

bip327bip340bitcoinelliptic-curveformal-verificationfrostmathlibmultisignaturemusig2schnorrsecp256k1

In a ZMod n-module, with shares f(i)f(i)f(i) of a polynomial of degree below ∣S∣|S|∣S∣: (∑zi)G=R+c (f(0)G)(\sum z_i)G = R + c\,(f(0)G)(∑zi​)G=R+c(f(0)G), the Schnorr equation for the group key f(0)Gf(0)Gf(0)G.

Preamble
import Definitions.Def_BitcoinMuSig
open BitcoinMuSig BitcoinSig BitcoinTaproot
Formal statement
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 sorry
Source
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.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 MMM be any type equipped with an additive commutative group structure and a Z/n\mathbb{Z}/nZ/n-module structure (a scalar multiplication Z/n×M→M\mathbb{Z}/n \times M \to MZ/n×M→M, written kxkxkx, satisfying the module axioms with respect to the addition of MMM; MMM may be the trivial group). Let

  • G∈MG \in MG∈M be arbitrary (a universally quantified element of MMM, not the secp256k1 generator);
  • SSS be a finite set of natural numbers with i<ni < ni<n for every i∈Si \in Si∈S (so distinct elements of SSS have distinct residues mod nnn; 0∈S0 \in S0∈S is allowed, and SSS may be empty);
  • f∈(Z/n)[X]f \in (\mathbb{Z}/n)[X]f∈(Z/n)[X] be a polynomial with deg⁡f<∣S∣\deg f < |S|degf<∣S∣ (i.e. f=0f = 0f=0, or deg⁡f≤∣S∣−1\deg f \le |S| - 1degf≤∣S∣−1; for S=∅S = \emptysetS=∅ this forces f=0f = 0f=0);
  • D,E:N→MD, E : \mathbb{N} \to MD,E:N→M and ρ,z:N→Z/n\rho, z : \mathbb{N} \to \mathbb{Z}/nρ,z:N→Z/n be arbitrary families (written Di,Ei,ρi,ziD_i, E_i, \rho_i, z_iDi​,Ei​,ρi​,zi​), and c∈Z/nc \in \mathbb{Z}/nc∈Z/n arbitrary.

Assume that for every i∈Si \in Si∈S

zi G=Di+ρiEi+(c λiS)(f(i) G),z_i\, G = D_i + \rho_i E_i + \big(c\,\lambda_i^S\big)\big(f(i)\, G\big),zi​G=Di​+ρi​Ei​+(cλiS​)(f(i)G),

where f(i)f(i)f(i) means fff evaluated at the residue (i:Z/n)(i : \mathbb{Z}/n)(i:Z/n) and λiS=lagrangeCoeff(S,i)∈Z/n\lambda_i^S = \mathrm{lagrangeCoeff}(S, i) \in \mathbb{Z}/nλiS​=lagrangeCoeff(S,i)∈Z/n. Then

(∑i∈Szi)G=∑i∈S(Di+ρiEi)+c (f(0) G).\Big(\sum_{i \in S} z_i\Big) G = \sum_{i \in S} \big(D_i + \rho_i E_i\big) + c\,\big(f(0)\, G\big).(i∈S∑​zi​)G=i∈S∑​(Di​+ρi​Ei​)+c(f(0)G).

All scalars and sums of scalars are computed in Z/n\mathbb{Z}/nZ/n. Values of D,E,ρ,zD, E, \rho, zD,E,ρ,z at indices outside SSS play no role. If S=∅S = \emptysetS=∅ (so f=0f = 0f=0) both sides are 000.

Definitions used, unfolded

Constants

  • p=2256−232−977p = 2^{256} - 2^{32} - 977p=2256−232−977 is a fixed natural number (the field modulus).
  • n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141n = \mathtt{0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141}n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 is a fixed natural number (written in hexadecimal).
  • Gx=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798G_x = \mathtt{0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798}Gx​=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 and Gy=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8G_y = \mathtt{0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8}Gy​=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 are fixed natural numbers (GyG_yGy​ is even: its last hexadecimal digit is 888).

Residues mod nnn, Lagrange coefficients and polynomials

  • Z/n\mathbb{Z}/nZ/n is Mathlib's Z/nZ\mathbb{Z}/n\mathbb{Z}Z/nZ; for a natural iii, (i:Z/n)(i : \mathbb{Z}/n)(i:Z/n) is its residue i mod ni \bmod nimodn. Mathlib's inverse x−1x^{-1}x−1 on Z/n\mathbb{Z}/nZ/n is a total function: it is the multiplicative inverse when xxx is coprime to nnn, and 0−1=00^{-1} = 00−1=0. (The definition file does not register primality of nnn as an instance.)
  • For a finite set S⊆NS \subseteq \mathbb{N}S⊆N and i∈Ni \in \mathbb{N}i∈N,
λiS=lagrangeCoeff(S,i)=∏j∈S∖{i}(j:Z/n)⋅((j:Z/n)−(i:Z/n))−1∈Z/n,\lambda_i^S = \mathrm{lagrangeCoeff}(S, i) = \prod_{j \in S \setminus \{i\}} (j : \mathbb{Z}/n)\cdot\big((j : \mathbb{Z}/n) - (i : \mathbb{Z}/n)\big)^{-1} \in \mathbb{Z}/n,λiS​=lagrangeCoeff(S,i)=j∈S∖{i}∏​(j:Z/n)⋅((j:Z/n)−(i:Z/n))−1∈Z/n,

where the subtraction is in Z/n\mathbb{Z}/nZ/n. The empty product is 111 (e.g. S={i}S = \{i\}S={i} or S=∅S = \emptysetS=∅), and iii need not belong to SSS (then nothing is removed). A factor with j≡i(modn)j \equiv i \pmod nj≡i(modn), j≠ij \ne ij=i, would be j⋅0−1=0j \cdot 0^{-1} = 0j⋅0−1=0.

  • For a polynomial f∈(Z/n)[X]f \in (\mathbb{Z}/n)[X]f∈(Z/n)[X], f(a)f(a)f(a) is its evaluation at a∈Z/na \in \mathbb{Z}/na∈Z/n. Its degree deg⁡f\deg fdegf takes values in {−∞}∪N\{-\infty\} \cup \mathbb{N}{−∞}∪N with deg⁡0=−∞\deg 0 = -\inftydeg0=−∞, which is smaller than every natural number. So deg⁡f<∣S∣\deg f < |S|degf<∣S∣ means: f=0f = 0f=0, or f≠0f \ne 0f=0 and deg⁡f≤∣S∣−1\deg f \le |S| - 1degf≤∣S∣−1. For S=∅S = \emptysetS=∅ it forces f=0f = 0f=0.
  • For x∈Z/nx \in \mathbb{Z}/nx∈Z/n, val(x)∈{0,1,…,n−1}\mathrm{val}(x) \in \{0, 1, \dots, n-1\}val(x)∈{0,1,…,n−1} is its canonical natural representative.
Human review
  • Endorsed by Shuze Chen · Oct 30, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Oct 30, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me