Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

secp256k1 as a Mathlib elliptic curve, the bridge from the executable curve, and BIP327 MuSig2 session algorithms

Definition
BitcoinMuSig

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

bip327bip340bitcoinelliptic-curveformal-verificationfrostmathlibmultisignaturemusig2schnorrsecp256k1

Over Mathlib and the signature and Taproot missions.

Primality. powMod_eq, prime_of_cert (a Lucas–Pratt certificate checker) and p_prime_cert : Nat.Prime p with the instance Fact (Nat.Prime p): the field prime of secp256k1 is certified, so ZMod p is a field. W — the curve y2=x3+7y^2 = x^3 + 7y2=x3+7 over ZMod p as a Mathlib WeierstrassCurve.Affine, with discriminant −21168≠0-21168 \ne 0−21168=0 and nonsingular_of_onCurve.

The bridge. toPoint, tp — the executable point (an optional pair of naturals) as a Mathlib point (0 for infinity); Valid P — on the curve; Reduced P — coordinates below ppp; ofPoint, Gpt (the generator as a Mathlib point), pneg, hasEvenY, evenY.

BIP327. tagged, xbytes (32-byte x-coordinate), cbytes (33-byte compressed point), cpoint (parse a compressed point), KeyAggCtx (aggregate point, gacc, tacc), hashKeys, getSecondKey, keyAggCoeffInternal, keyAggCoeff, keyAggSum, keyAgg, applyTweak, applyTweaks, keyAggTweaked, nonceSum, nonceAgg, SessionCtx, SessionValues, getSessionValues, partialSigVerifyInternal, partialSigAgg — the BIP's algorithms over byte strings and the executable curve, including the second-key exception, plain and x-only tweaks, the negations for odd Q.y and R.y, and the substitution R=GR = GR=G at infinity.

FROST. lagrangeCoeff S i — the Lagrange coefficient at 0 for identifier set SSS, in ZMod n.

Formalization Note. Imports Mathlib, BitcoinSig, BitcoinTaproot. The file carries the primality certificate and the curve's nonsingularity as lemmas because Mathlib's group structure on points needs them; they are checked by decide +kernel, never native_decide.

Definition code
import Mathlib
import Definitions.Def_BitcoinSig
import Definitions.Def_BitcoinTaproot

/-!
# MuSig2 (BIP327) over secp256k1, bridged to Mathlib's Weierstrass group law

Two layers.

* **The bridge.** `W` is secp256k1 (`y² = x³ + 7`) as a `WeierstrassCurve.Affine (ZMod p)`.
  `toPoint` sends an executable point of `Def_BitcoinSig` (`none` = infinity, `some (x, y)` with
  `onCurve`) to a Mathlib point; `tp` is its total version (off-curve data maps to `0`) and
  `ofPoint` the canonical representative (coordinates reduced below `p`). The theorems of the
  mission show that `padd`, `pmul`, `pneg` are Mathlib's `+`, `•`, `-` through this map. The group
  law needs `ZMod p` to be a field, so `Nat.Prime p` is certified here once and for all by a
  Lucas–Pratt certificate (`p - 1 = 2 · 3 · 7 · 13441 · q₅`, recursively), with the modular
  exponentiations kernel-checked through the executable `powMod` of `Def_BitcoinSig`.
* **MuSig2.** Executable transcription of BIP327's `KeyAgg`, `ApplyTweak`, `NonceAgg`,
  `GetSessionValues`, `PartialSigVerifyInternal` and `PartialSigAgg` on the byte strings and
  executable points of `Def_BitcoinSig` (`cpoint`/`cbytes` are the 33-byte compressed encodings,
  tagged hashes are `BitcoinSig.taggedHash`).
-/

namespace BitcoinMuSig

open BitcoinSer (Byte Bytes)
open BitcoinSig (p n Point G Gx Gy onCurve padd pmul powMod powModAux finv liftX liftXParity beVal)

/-! ### `powMod` computes modular powers -/

theorem powModAux_eq (m : ℕ) : ∀ (fuel b e acc : ℕ), e < 2 ^ fuel → acc % m = acc →
    powModAux m fuel b e acc = acc * b ^ e % m := by
  intro fuel
  induction fuel with
  | zero =>
    intro b e acc he hacc
    have h0 : e = 0 := by simpa using he
    subst h0
    simp [powModAux, hacc]
  | succ f ih =>
    intro b e acc he hacc
    have he' : e / 2 < 2 ^ f := by
      rw [pow_succ] at he; omega
    have hsplit : e = 2 * (e / 2) + e % 2 := (Nat.div_add_mod e 2).symm
    have hpow : b ^ e = (b * b) ^ (e / 2) * b ^ (e % 2) := by
      conv_lhs => rw [hsplit]
      rw [pow_add, pow_mul, pow_two]
    have hbb : (b * b % m) ^ (e / 2) ≡ (b * b) ^ (e / 2) [MOD m] := (Nat.mod_modEq _ _).pow _
    simp only [powModAux]
    split_ifs with h0 h1
    · subst h0; simp [hacc]
    · rw [ih _ _ _ he' (Nat.mod_mod _ _)]
      have : acc * b % m * (b * b % m) ^ (e / 2) ≡ acc * (b ^ e) [MOD m] := by
        rw [hpow, h1, pow_one]
        calc acc * b % m * (b * b % m) ^ (e / 2) ≡ acc * b * (b * b) ^ (e / 2) [MOD m] :=
              (Nat.mod_modEq _ _).mul hbb
          _ = acc * ((b * b) ^ (e / 2) * b) := by ring
      exact this
    · rw [ih _ _ _ he' hacc]
      have h2 : e % 2 = 0 := by omega
      have : acc * (b * b % m) ^ (e / 2) ≡ acc * (b ^ e) [MOD m] := by
        rw [hpow, h2, pow_zero, mul_one]
        exact hbb.mul_left _
      exact this

theorem powMod_eq (b e m : ℕ) : powMod b e m = b ^ e % m := by
  unfold powMod
  rw [powModAux_eq m (e + 1) (b % m) e (1 % m) (by
      have := Nat.lt_two_pow_self (n := e); calc e < 2 ^ e := this
        _ ≤ 2 ^ (e + 1) := Nat.pow_le_pow_right (by norm_num) (by omega)) (Nat.mod_mod _ _)]
  rw [Nat.mul_mod, Nat.mod_mod, ← Nat.pow_mod, ← Nat.mul_mod, one_mul]

/-! ### A Lucas–Pratt primality certificate -/

/-- One Pratt step: `q` is prime if `a ^ (q-1) ≡ 1`, and `a ^ ((q-1)/r) ≢ 1` for every prime
factor `r` of `q - 1` (listed with multiplicity in `fs`). -/
theorem prime_of_cert (q a : ℕ) (fs : List ℕ) (hq : 1 < q) (hfs : ∀ r ∈ fs, Nat.Prime r)
    (hprod : q - 1 = fs.prod) (ha : powMod a (q - 1) q = 1)
    (hb : ∀ r ∈ fs, powMod a ((q - 1) / r) q ≠ 1) : Nat.Prime q := by
  rw [powMod_eq] at ha
  apply lucas_primality q (a : ZMod q)
  · have h2 : ((a ^ (q - 1) : ℕ) : ZMod q) = ((1 : ℕ) : ZMod q) := by
      rw [ZMod.natCast_eq_natCast_iff', ha, Nat.one_mod_eq_one.mpr (by omega)]
    push_cast at h2
    exact h2
  · intro r hr hdvd h1
    have hmem : r ∈ fs := by
      rw [hprod] at hdvd
      obtain ⟨r', hr', hrr'⟩ := (Nat.prime_iff.mp hr).dvd_prod_iff.mp hdvd
      rwa [(Nat.prime_dvd_prime_iff_eq hr (hfs r' hr')).mp hrr']
    apply hb r hmem
    have h2 : ((a ^ ((q - 1) / r) : ℕ) : ZMod q) = ((1 : ℕ) : ZMod q) := by
      push_cast
      exact h1
    rw [ZMod.natCast_eq_natCast_iff'] at h2
    rw [powMod_eq, h2, Nat.one_mod_eq_one.mpr (by omega)]

set_option maxRecDepth 100000 in
private theorem prime_13331831 : Nat.Prime 13331831 := by norm_num

set_option maxRecDepth 100000 in
private theorem prime_173378833005251801 : Nat.Prime 173378833005251801 := by
  refine prime_of_cert _ 6 [2, 2, 2, 5, 5, 2621, 24809, 13331831] (by norm_num) ?_ (by decide +kernel)
    (by decide +kernel) (by decide +kernel)
  intro r hr
  simp only [List.mem_cons, List.not_mem_nil, or_false] at hr
  rcases hr with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> first | exact prime_13331831 | norm_num

set_option maxRecDepth 100000 in
private theorem prime_22149492674086928081353 : Nat.Prime 22149492674086928081353 := by
  refine prime_of_cert _ 5 [2, 2, 2, 3, 5323, 173378833005251801] (by norm_num) ?_ (by decide +kernel)
    (by decide +kernel) (by decide +kernel)
  intro r hr
  simp only [List.mem_cons, List.not_mem_nil, or_false] at hr
  rcases hr with rfl | rfl | rfl | rfl | rfl | rfl <;> first | exact prime_173378833005251801 | norm_num

set_option maxRecDepth 100000 in
private theorem prime_132896956044521568488119 : Nat.Prime 132896956044521568488119 := by
  refine prime_of_cert _ 6 [2, 3, 22149492674086928081353] (by norm_num) ?_ (by decide +kernel)
    (by decide +kernel) (by decide +kernel)
  intro r hr
  simp only [List.mem_cons, List.not_mem_nil, or_false] at hr
  rcases hr with rfl | rfl | rfl <;> first | exact prime_22149492674086928081353 | norm_num

set_option maxRecDepth 100000 in
private theorem prime_1206781 : Nat.Prime 1206781 := by norm_num

set_option maxRecDepth 100000 in
private theorem prime_7240687 : Nat.Prime 7240687 := by
  refine prime_of_cert _ 3 [2, 3, 1206781] (by norm_num) ?_ (by decide +kernel)
    (by decide +kernel) (by decide +kernel)
  intro r hr
  simp only [List.mem_cons, List.not_mem_nil, or_false] at hr
  rcases hr with rfl | rfl | rfl <;> first | exact prime_1206781 | norm_num

set_option maxRecDepth 100000 in
private theorem prime_107590001 : Nat.Prime 107590001 := by
  refine prime_of_cert _ 3 [2, 2, 2, 2, 5, 5, 5, 5, 7, 29, 53] (by norm_num) ?_ (by decide +kernel)
    (by decide +kernel) (by decide +kernel)
  intro r hr
  simp only [List.mem_cons, List.not_mem_nil, or_false] at hr
  rcases hr with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> norm_num

set_option maxRecDepth 100000 in
private theorem prime_255515944373312847190720520512484175977 :
    Nat.Prime 255515944373312847190720520512484175977 := by
  refine prime_of_cert _ 3 [2, 2, 2, 7, 7, 11, 1627, 2657, 4423, 96557, 41201, 107590001, 7240687]
    (by norm_num) ?_ (by decide +kernel) (by decide +kernel) (by decide +kernel)
  intro r hr
  simp only [List.mem_cons, List.not_mem_nil, or_false] at hr
  rcases hr with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl <;>
    first | exact prime_107590001 | exact prime_7240687 | norm_num

set_option maxRecDepth 100000 in
private theorem prime_q5 :
    Nat.Prime 205115282021455665897114700593932402728804164701536103180137503955397371 := by
  refine prime_of_cert _ 10 [2, 3, 5, 29, 29, 31, 7723, 132896956044521568488119,
    255515944373312847190720520512484175977]
    (by norm_num) ?_ (by decide +kernel) (by decide +kernel) (by decide +kernel)
  intro r hr
  simp only [List.mem_cons, List.not_mem_nil, or_false] at hr
  rcases hr with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl <;>
    first
      | exact prime_132896956044521568488119
      | exact prime_255515944373312847190720520512484175977
      | norm_num

set_option maxRecDepth 100000 in
/-- `p = 2^256 - 2^32 - 977` is prime (Lucas–Pratt certificate with witness `3`,
`p - 1 = 2 · 3 · 7 · 13441 · 205115282021455665897114700593932402728804164701536103180137503955397371`). -/
theorem p_prime_cert : Nat.Prime p := by
  refine prime_of_cert _ 3 [2, 3, 7, 13441,
    205115282021455665897114700593932402728804164701536103180137503955397371]
    (by decide) ?_ (by decide +kernel) (by decide +kernel) (by decide +kernel)
  intro r hr
  simp only [List.mem_cons, List.not_mem_nil, or_false] at hr
  rcases hr with rfl | rfl | rfl | rfl | rfl <;> first | exact prime_q5 | norm_num

instance instFactPrimeP : Fact (Nat.Prime p) := ⟨p_prime_cert⟩

/-! ### secp256k1 as a Mathlib Weierstrass curve -/

/-- secp256k1: `y² = x³ + 7` over `𝔽_p` (`a₁ = a₂ = a₃ = a₄ = 0`, `a₆ = 7`). -/
def W : WeierstrassCurve.Affine (ZMod p) := ⟨0, 0, 0, 0, 7⟩

theorem W_Δ : W.Δ = -21168 := by
  simp [W, WeierstrassCurve.Δ, WeierstrassCurve.b₂, WeierstrassCurve.b₄, WeierstrassCurve.b₆,
    WeierstrassCurve.b₈]
  norm_num

theorem W_Δ_ne_zero : W.Δ ≠ 0 := by
  rw [W_Δ, neg_ne_zero, show (21168 : ZMod p) = ((21168 : ℕ) : ZMod p) by norm_cast, Ne,
    ZMod.natCast_eq_zero_iff]
  decide

/-- The executable curve test is Mathlib's equation. -/
theorem equation_iff_onCurve (x y : ℕ) :
    W.Equation (x : ZMod p) (y : ZMod p) ↔ onCurve (x, y) = true := by
  rw [WeierstrassCurve.Affine.equation_iff]
  simp only [W, onCurve, decide_eq_true_eq]
  rw [← ZMod.natCast_eq_natCast_iff']
  push_cast
  constructor <;> intro h <;> linear_combination h

theorem nonsingular_of_onCurve {x y : ℕ} (h : onCurve (x, y) = true) :
    W.Nonsingular (x : ZMod p) (y : ZMod p) :=
  (WeierstrassCurve.Affine.equation_iff_nonsingular_of_Δ_ne_zero W_Δ_ne_zero).mp
    ((equation_iff_onCurve x y).mpr h)

/-- The Mathlib point of an executable point: `none` (infinity) ↦ `0`; `some (x, y)` ↦ the affine
point `(x mod p, y mod p)` if it is on the curve, and no point otherwise. -/
def toPoint : Point → Option W.Point
  | none => some 0
  | some (x, y) =>
    if h : onCurve (x, y) = true then
      some (.some (x : ZMod p) (y : ZMod p) (nonsingular_of_onCurve h))
    else none

/-- The total version of `toPoint` (data off the curve maps to `0`). -/
def tp (P : Point) : W.Point := (toPoint P).getD 0

/-- An executable point whose affine data (if any) lies on the curve. -/
def Valid (P : Point) : Prop := ∀ x y, P = some (x, y) → onCurve (x, y) = true

/-- An executable point whose coordinates (if any) are reduced below `p`. -/
def Reduced (P : Point) : Prop := ∀ x y, P = some (x, y) → x < p ∧ y < p

/-- The canonical executable representative of a Mathlib point. -/
def ofPoint : W.Point → Point
  | .zero => none
  | .some x y _ => some (x.val, y.val)

/-- The generator `G` as a Mathlib point. -/
def Gpt : W.Point := .some (Gx : ZMod p) (Gy : ZMod p) (nonsingular_of_onCurve (by decide))

/-- Executable negation `-(x, y) = (x, -y)`. -/
def pneg : Point → Point
  | none => none
  | some (x, y) => some (x, (p - y % p) % p)

/-- `has_even_y` of BIP340/BIP327 on affine data. -/
def hasEvenY (P : ℕ × ℕ) : Bool := decide (P.2 % 2 = 0)

/-- `has_even_y` on Mathlib points (infinity counts as even). -/
def evenY : W.Point → Bool
  | .zero => true
  | .some _ y _ => decide (y.val % 2 = 0)

/-! ### MuSig2 (BIP327): executable transcription -/

/-- `tagged_hash` with a string tag. -/
def tagged (tag : String) (m : Bytes) : Bytes := BitcoinSig.taggedHash (BitcoinSig.ascii tag) m

/-- `xbytes(P)`: the 32-byte big-endian abscissa. -/
def xbytes (P : ℕ × ℕ) : Bytes := BitcoinTaproot.be32 P.1

/-- `cbytes(P)`: compressed encoding `02/03 || xbytes(P)`. -/
def cbytes (P : ℕ × ℕ) : Bytes := (if hasEvenY P then 2 else 3) :: xbytes P

def zero33 : Bytes := List.replicate 33 0

/-- `cbytes_ext`: infinity is encoded as 33 zero bytes. -/
def cbytesExt : Point → Bytes
  | none => zero33
  | some P => cbytes P

/-- `cpoint(x)`: parse a 33-byte compressed point (`none` = failure). -/
def cpoint (b : Bytes) : Option (ℕ × ℕ) := if b.length = 33 then BitcoinSig.parsePubkey b else none

/-- `cpoint_ext(x)`: `none` = failure, `some none` = infinity. -/
def cpointExt (b : Bytes) : Option Point :=
  if b = zero33 then some none else (cpoint b).map some

/-- `KeyAggContext(Q, gacc, tacc)`; `Q` is never infinity. -/
structure KeyAggCtx where
  Q : ℕ × ℕ
  gacc : ℕ
  tacc : ℕ
  deriving Repr, DecidableEq

/-- `HashKeys(pk_1..pk_u) = hash_KeyAgg list(pk_1 || ... || pk_u)`. -/
def hashKeys (pks : List Bytes) : Bytes := tagged "KeyAgg list" pks.flatten

/-- `GetSecondKey`: the first key different from the first one, else `bytes(33, 0)`. -/
def getSecondKey (pks : List Bytes) : Bytes :=
  match pks with
  | [] => zero33
  | pk1 :: _ => (pks.find? (fun pk => pk ≠ pk1)).getD zero33

/-- `KeyAggCoeffInternal(pk_1..pk_u, pk', pk2)`. -/
def keyAggCoeffInternal (pks : List Bytes) (pk pk2 : Bytes) : ℕ :=
  if pk = pk2 then 1 else beVal (tagged "KeyAgg coefficient" (hashKeys pks ++ pk)) % n

/-- `KeyAggCoeff(pk_1..pk_u, pk')`. -/
def keyAggCoeff (pks : List Bytes) (pk : Bytes) : ℕ :=
  keyAggCoeffInternal pks pk (getSecondKey pks)

/-- `Σ_i a_i ⋅ P_i` over the keys `l` (coefficients with respect to the full list `pks`);
`none` if some key fails to parse. -/
def keyAggSum (pks : List Bytes) : List Bytes → Option Point
  | [] => some none
  | pk :: rest =>
    match cpoint pk, keyAggSum pks rest with
    | some P, some acc => some (padd (pmul (keyAggCoeff pks pk) (some P)) acc)
    | _, _ => none

/-- `KeyAgg(pk_1..pk_u)`: fails if a key does not parse or the aggregate is infinity. -/
def keyAgg (pks : List Bytes) : Option KeyAggCtx :=
  match keyAggSum pks pks with
  | some (some Q) => some ⟨Q, 1, 0⟩
  | _ => none

/-- `ApplyTweak(keyagg_ctx, tweak, is_xonly_t)`. -/
def applyTweak (ctx : KeyAggCtx) (tweak : Bytes) (isXonly : Bool) : Option KeyAggCtx :=
  let g := if isXonly ∧ ¬ hasEvenY ctx.Q then n - 1 else 1
  let t := beVal tweak
  if n ≤ t then none
  else match padd (pmul g (some ctx.Q)) (pmul t G) with
    | none => none
    | some Q' => some ⟨Q', g * ctx.gacc % n, (t + g * ctx.tacc) % n⟩

/-- The tweaks of a session applied in order. -/
def applyTweaks : KeyAggCtx → List (Bytes × Bool) → Option KeyAggCtx
  | ctx, [] => some ctx
  | ctx, (tw, x) :: rest =>
    match applyTweak ctx tw x with
    | none => none
    | some ctx' => applyTweaks ctx' rest

/-- `keyagg_ctx_v`: `KeyAgg` followed by the tweaks. -/
def keyAggTweaked (pks : List Bytes) (tweaks : List (Bytes × Bool)) : Option KeyAggCtx :=
  match keyAgg pks with
  | none => none
  | some ctx => applyTweaks ctx tweaks

/-- `R_j = Σ_i R_{i,j}` for `j ∈ {0, 1}`, with `R_{i,j} = cpoint(pubnonce_i[33j : 33(j+1)])`. -/
def nonceSum (j : ℕ) : List Bytes → Option Point
  | [] => some none
  | pn :: rest =>
    match cpoint ((pn.drop (33 * j)).take 33), nonceSum j rest with
    | some P, some acc => some (padd (some P) acc)
    | _, _ => none

/-- `NonceAgg(pubnonce_1..pubnonce_u) = cbytes_ext(R_1) || cbytes_ext(R_2)`. -/
def nonceAgg (pubnonces : List Bytes) : Option Bytes :=
  match nonceSum 0 pubnonces, nonceSum 1 pubnonces with
  | some R1, some R2 => some (cbytesExt R1 ++ cbytesExt R2)
  | _, _ => none

/-- `SessionContext(aggnonce, pk_1..pk_u, tweak_1..v, is_xonly_1..v, m)`. -/
structure SessionCtx where
  aggnonce : Bytes
  pks : List Bytes
  tweaks : List (Bytes × Bool)
  msg : Bytes

/-- The values `(Q, gacc, tacc, b, R, e)` of `GetSessionValues`, together with the raw aggregate
nonce `R' = R_1 + b⋅R_2` before the infinity substitution. -/
structure SessionValues where
  Q : ℕ × ℕ
  gacc : ℕ
  tacc : ℕ
  b : ℕ
  R' : Point
  R : ℕ × ℕ
  e : ℕ

/-- `GetSessionValues(session_ctx)`. -/
def getSessionValues (ctx : SessionCtx) : Option SessionValues :=
  match keyAggTweaked ctx.pks ctx.tweaks with
  | none => none
  | some kctx =>
    let b := beVal (tagged "MuSig/noncecoef" (ctx.aggnonce ++ xbytes kctx.Q ++ ctx.msg)) % n
    match cpointExt (ctx.aggnonce.take 33), cpointExt ((ctx.aggnonce.drop 33).take 33) with
    | some R1, some R2 =>
      let R' := padd R1 (pmul b R2)
      let R := match R' with
        | none => (Gx, Gy)
        | some R => R
      let e := beVal (tagged "BIP0340/challenge" (xbytes R ++ xbytes kctx.Q ++ ctx.msg)) % n
      some ⟨kctx.Q, kctx.gacc, kctx.tacc, b, R', R, e⟩
    | _, _ => none

/-- `PartialSigVerifyInternal(psig, pubnonce, pk, session_ctx)`. -/
def partialSigVerifyInternal (psig pubnonce pk : Bytes) (ctx : SessionCtx) : Bool :=
  match getSessionValues ctx with
  | none => false
  | some sv =>
    let s := beVal psig
    if psig.length ≠ 32 ∨ n ≤ s then false
    else match cpoint (pubnonce.take 33), cpoint ((pubnonce.drop 33).take 33), cpoint pk with
      | some R1, some R2, some P =>
        if pk ∉ ctx.pks then false
        else
          let Re' := padd (some R1) (pmul sv.b (some R2))
          let Re := if hasEvenY sv.R then Re' else pneg Re'
          let a := keyAggCoeff ctx.pks pk
          let g := if hasEvenY sv.Q then 1 else n - 1
          let g' := g * sv.gacc % n
          decide (pmul s G = padd Re (pmul (sv.e * a * g' % n) (some P)))
      | _, _, _ => false

/-- `PartialSigAgg(psig_1..psig_u, session_ctx) = xbytes(R) || bytes(32, s)`. -/
def partialSigAgg (psigs : List Bytes) (ctx : SessionCtx) : Option Bytes :=
  match getSessionValues ctx with
  | none => none
  | some sv =>
    if psigs.any (fun ps => decide (ps.length ≠ 32 ∨ n ≤ beVal ps)) then none
    else
      let g := if hasEvenY sv.Q then 1 else n - 1
      let s := ((psigs.map beVal).sum + sv.e * g * sv.tacc) % n
      some (xbytes sv.R ++ BitcoinTaproot.be32 s)

/-! ### FROST-style threshold combination: Lagrange coefficients at `0` -/

/-- The Lagrange coefficient `λ_i = ∏_{j ∈ S, j ≠ i} j / (j - i)` in `ZMod n` of the participant
identifier `i`, for the signing set `S`. -/
def lagrangeCoeff (S : Finset ℕ) (i : ℕ) : ZMod n :=
  ∏ j ∈ S.erase i, (j : ZMod n) * ((j : ZMod n) - (i : ZMod n))⁻¹

end BitcoinMuSig
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: Def_BitcoinMuSig.lean

This file (namespace BitcoinMuSig) imports Mathlib and the secp256k1 signature and Taproot definition files. Below, the first section unfolds the imported definitions it relies on; the second section has one paragraph per declaration of the file, in file order (lemmas, private lemmas, the instance, definitions and record types). The file supplies proofs for all of its lemmas; this read-back only states what each asserts.

Imported definitions, unfolded

Constants (from the signature file)

  • p=2256−232−977p = 2^{256} - 2^{32} - 977p=2256−232−977 and n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141n = \mathtt{0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141}n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 are fixed natural numbers.
  • 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).

Modular exponentiation (from the signature file)

  • powModAux(m,fuel,b,e,acc)\mathrm{powModAux}(m, \mathit{fuel}, b, e, \mathit{acc})powModAux(m,fuel,b,e,acc): if fuel=0\mathit{fuel} = 0fuel=0 return acc\mathit{acc}acc; otherwise, if e=0e = 0e=0 return acc\mathit{acc}acc, else recurse with fuel−1\mathit{fuel} - 1fuel−1, base b⋅b mod mb\cdot b \bmod mb⋅bmodm, exponent ⌊e/2⌋\lfloor e/2 \rfloor⌊e/2⌋ and accumulator acc⋅b mod m\mathit{acc}\cdot b \bmod macc⋅bmodm if eee is odd (acc\mathit{acc}acc unchanged if eee is even).
  • powMod(b,e,m)=powModAux(m, e+1, b mod m, e, 1 mod m)\mathrm{powMod}(b, e, m) = \mathrm{powModAux}(m,\ e + 1,\ b \bmod m,\ e,\ 1 \bmod m)powMod(b,e,m)=powModAux(m, e+1, bmodm, e, 1modm). (In natural-number arithmetic x mod 0=xx \bmod 0 = xxmod0=x.)
  • finv(a)=powMod(a,p−2,p)\mathrm{finv}(a) = \mathrm{powMod}(a, p - 2, p)finv(a)=powMod(a,p−2,p).

Executable points (from the signature file)

  • An executable point is either the special value ∞\infty∞ (the code's "no coordinates" value, which it uses for the point at infinity) or a pair (x,y)(x, y)(x,y) of natural numbers of arbitrary size. Nothing in the type requires x,y<px, y < px,y<p or that the pair lies on the curve. Equality of executable points is literal equality: both ∞\infty∞, or equal pairs of natural numbers (so (x,y)(x, y)(x,y) and (x+p,y)(x+p, y)(x+p,y) are different executable points).
  • Curve test. For naturals x,yx, yx,y: onCurve(x,y)\mathrm{onCurve}(x, y)onCurve(x,y) holds iff
(y⋅y) mod p=(x⋅x⋅x+7) mod p,(y \cdot y) \bmod p = (x \cdot x \cdot x + 7) \bmod p ,(y⋅y)modp=(x⋅x⋅x+7)modp,

i.e. y2≡x3+7(modp)y^2 \equiv x^3 + 7 \pmod py2≡x3+7(modp). Pairs with unreduced coordinates (x≥px \ge px≥p or y≥py \ge py≥p) can pass this test.

  • Modular inversion. finv(a)=powMod(a,p−2,p)\mathrm{finv}(a) = \mathrm{powMod}(a, p-2, p)finv(a)=powMod(a,p−2,p); the lemma powMod_eq\mathrm{powMod\_eq}powMod_eq below gives finv(a)=ap−2 mod p\mathrm{finv}(a) = a^{p-2} \bmod pfinv(a)=ap−2modp, in particular finv(a)=0\mathrm{finv}(a) = 0finv(a)=0 when p∣ap \mid ap∣a.
  • Addition padd(P,Q)\mathrm{padd}(P, Q)padd(P,Q):
    • padd(∞,Q)=Q\mathrm{padd}(\infty, Q) = Qpadd(∞,Q)=Q and padd(P,∞)=P\mathrm{padd}(P, \infty) = Ppadd(P,∞)=P, returned unchanged (unreduced coordinates stay unreduced).
    • For P=(x1,y1)P = (x_1, y_1)P=(x1​,y1​), Q=(x2,y2)Q = (x_2, y_2)Q=(x2​,y2​) with x1≡x2(modp)x_1 \equiv x_2 \pmod px1​≡x2​(modp):
      • if y1+y2≡0(modp)y_1 + y_2 \equiv 0 \pmod py1​+y2​≡0(modp) the result is ∞\infty∞;
      • otherwise (tangent branch, which uses only x1,y1x_1, y_1x1​,y1​):
λ=(3x12⋅finv(2y1 mod p)) mod p,x3=(λ2+2(p−x1 mod p)) mod p,\lambda = \big(3x_1^2 \cdot \mathrm{finv}(2y_1 \bmod p)\big) \bmod p,\quad x_3 = \big(\lambda^2 + 2(p - x_1 \bmod p)\big) \bmod p,λ=(3x12​⋅finv(2y1​modp))modp,x3​=(λ2+2(p−x1​modp))modp, y3=(λ⋅((x1+p−x3) mod p)+(p−y1 mod p)) mod p,y_3 = \big(\lambda \cdot ((x_1 + p - x_3) \bmod p) + (p - y_1 \bmod p)\big) \bmod p,y3​=(λ⋅((x1​+p−x3​)modp)+(p−y1​modp))modp,
and the result is $(x_3, y_3)$.
  • For P=(x1,y1)P = (x_1, y_1)P=(x1​,y1​), Q=(x2,y2)Q = (x_2, y_2)Q=(x2​,y2​) with x1≢x2(modp)x_1 \not\equiv x_2 \pmod px1​≡x2​(modp) (chord branch):
λ=(((y2+p−y1 mod p) mod p)⋅finv((x2+p−x1 mod p) mod p)) mod p,\lambda = \Big( \big((y_2 + p - y_1 \bmod p) \bmod p\big) \cdot \mathrm{finv}\big((x_2 + p - x_1 \bmod p) \bmod p\big) \Big) \bmod p,λ=(((y2​+p−y1​modp)modp)⋅finv((x2​+p−x1​modp)modp))modp, x3=(λ2+(p−x1 mod p)+(p−x2 mod p)) mod p,y3=(λ⋅((x1+p−x3) mod p)+(p−y1 mod p)) mod p,x_3 = \big(\lambda^2 + (p - x_1 \bmod p) + (p - x_2 \bmod p)\big) \bmod p,\quad y_3 = \big(\lambda \cdot ((x_1 + p - x_3) \bmod p) + (p - y_1 \bmod p)\big) \bmod p,x3​=(λ2+(p−x1​modp)+(p−x2​modp))modp,y3​=(λ⋅((x1​+p−x3​)modp)+(p−y1​modp))modp,
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 ∞\infty∞ or a pair with both coordinates <p< p<p.
  • Scalar multiplication pmul(k,P)\mathrm{pmul}(k, P)pmul(k,P) for k∈Nk \in \mathbb{N}k∈N: a least-significant-bit-first double-and-add loop with a fuel of exactly 257257257 iterations. Starting from (k,P,acc=∞)(k, P, \mathrm{acc} = \infty)(k,P,acc=∞), each iteration does: if k=0k = 0k=0, stop and return acc\mathrm{acc}acc; otherwise replace acc\mathrm{acc}acc by padd(acc,P)\mathrm{padd}(\mathrm{acc}, P)padd(acc,P) if kkk is odd (else keep it), then replace PPP by padd(P,P)\mathrm{padd}(P, P)padd(P,P) and kkk by ⌊k/2⌋\lfloor k/2 \rfloor⌊k/2⌋. When the 257257257 iterations are exhausted the current acc\mathrm{acc}acc is returned. Consequently only the 257257257 lowest bits of kkk are ever used: pmul(k,P)=pmul(k mod 2257,P)\mathrm{pmul}(k, P) = \mathrm{pmul}(k \bmod 2^{257}, P)pmul(k,P)=pmul(kmod2257,P). Also pmul(0,P)=∞\mathrm{pmul}(0, P) = \inftypmul(0,P)=∞ and pmul(k,∞)=∞\mathrm{pmul}(k, \infty) = \inftypmul(k,∞)=∞.
  • GGG denotes the executable point (Gx,Gy)(G_x, G_y)(Gx​,Gy​).

Bytes, hashing and parsing (from the serialization, signature and Taproot files)

  • A byte string is a finite list of bytes (values 0,…,2550, \dots, 2550,…,255); ∣b∣|b|∣b∣ is its length and ∥\Vert∥ concatenation. takek(b)\mathrm{take}_k(b)takek​(b) is the first min⁡(k,∣b∣)\min(k, |b|)min(k,∣b∣) bytes, dropk(b)\mathrm{drop}_k(b)dropk​(b) removes the first min⁡(k,∣b∣)\min(k, |b|)min(k,∣b∣) bytes (slices of too-short strings are silently shorter).
  • beVal(b)=∑i=0∣b∣−1bi 256 ∣b∣−1−i\mathrm{beVal}(b) = \sum_{i=0}^{|b|-1} b_i\,256^{\,|b|-1-i}beVal(b)=∑i=0∣b∣−1​bi​256∣b∣−1−i (big-endian value, any length; 000 for the empty string).
  • be32(x)\mathrm{be32}(x)be32(x) (Taproot file) is the 323232-byte big-endian encoding of x mod 2256x \bmod 2^{256}xmod2256 (higher bits silently dropped).
  • SHA256\mathrm{SHA256}SHA256 is the executable SHA-256 of the serialization file; ascii(s)\mathrm{ascii}(s)ascii(s) is the UTF-8 byte string of the text sss; taggedHash(t,m)=SHA256(SHA256(t)∥SHA256(t)∥m)\mathrm{taggedHash}(t, m) = \mathrm{SHA256}(\mathrm{SHA256}(t) \Vert \mathrm{SHA256}(t) \Vert m)taggedHash(t,m)=SHA256(SHA256(t)∥SHA256(t)∥m).
  • liftXParity(x,odd)\mathrm{liftXParity}(x, \mathit{odd})liftXParity(x,odd): let y=powMod(x3+7,(p+1)/4,p)y = \mathrm{powMod}(x^3 + 7, (p+1)/4, p)y=powMod(x3+7,(p+1)/4,p) (natural-number division). If y2 mod p=(x3+7) mod py^2 \bmod p = (x^3 + 7) \bmod py2modp=(x3+7)modp the result is the pair (x,y∗)(x, y^\ast)(x,y∗) with y∗=yy^\ast = yy∗=y if the parity of yyy is the requested one, else y∗=(p−y) mod py^\ast = (p - y) \bmod py∗=(p−y)modp (so y∗=0y^\ast = 0y∗=0 when y=0y = 0y=0, whatever was requested); otherwise it fails (returns ∞\infty∞, the "no point" value).
  • parsePubkey(b)\mathrm{parsePubkey}(b)parsePubkey(b): fails on the empty string. For b=[t]∥rb = [t] \Vert rb=[t]∥r: if ∣b∣=33|b| = 33∣b∣=33 and t∈{2,3}t \in \{2, 3\}t∈{2,3}, let x=beVal(r)x = \mathrm{beVal}(r)x=beVal(r); return liftXParity(x,t=3)\mathrm{liftXParity}(x, t = 3)liftXParity(x,t=3) if x<px < px<p, else fail. Else if ∣b∣=65|b| = 65∣b∣=65 and t∈{4,6,7}t \in \{4, 6, 7\}t∈{4,6,7}, let x=beVal(first 32 bytes of r)x = \mathrm{beVal}(\text{first 32 bytes of } r)x=beVal(first 32 bytes of r), y=beVal(rest of r)y = \mathrm{beVal}(\text{rest of } r)y=beVal(rest of r); return (x,y)(x, y)(x,y) if x<px < px<p, y<py < py<p, (for t∈{6,7}t \in \{6, 7\}t∈{6,7}) yyy is odd iff t=7t = 7t=7, and onCurve(x,y)\mathrm{onCurve}(x, y)onCurve(x,y); else fail. Otherwise fail. Failure is the value ∞\infty∞.

The declarations of the file, in order

powModAux_eq (lemma). For every natural modulus mmm and all naturals fuel,b,e,acc\mathit{fuel}, b, e, \mathit{acc}fuel,b,e,acc: if e<2fuele < 2^{\mathit{fuel}}e<2fuel and acc mod m=acc\mathit{acc} \bmod m = \mathit{acc}accmodm=acc (which means acc<m\mathit{acc} < macc<m when m>0m > 0m>0, and is automatic when m=0m = 0m=0 because x mod 0=xx \bmod 0 = xxmod0=x), then

powModAux(m,fuel,b,e,acc)=(acc⋅be) mod m.\mathrm{powModAux}(m, \mathit{fuel}, b, e, \mathit{acc}) = (\mathit{acc}\cdot b^e) \bmod m .powModAux(m,fuel,b,e,acc)=(acc⋅be)modm.

powMod_eq (lemma). For all naturals b,e,mb, e, mb,e,m (no hypotheses; m=0m = 0m=0 and m=1m = 1m=1 included), powMod(b,e,m)=be mod m\mathrm{powMod}(b, e, m) = b^e \bmod mpowMod(b,e,m)=bemodm (with x mod 0=xx \bmod 0 = xxmod0=x, so for m=0m = 0m=0 this is beb^ebe).

prime_of_cert (lemma, Pratt step). For naturals q,aq, aq,a and a finite list fs=[r1,…,rk]fs = [r_1, \dots, r_k]fs=[r1​,…,rk​] of naturals: if (i) 1<q1 < q1<q, (ii) every r∈fsr \in fsr∈fs is prime, (iii) q−1=r1r2⋯rkq - 1 = r_1 r_2 \cdots r_kq−1=r1​r2​⋯rk​ (list product with multiplicity; the empty product is 111), (iv) powMod(a,q−1,q)=1\mathrm{powMod}(a, q - 1, q) = 1powMod(a,q−1,q)=1, and (v) for every r∈fsr \in fsr∈fs, powMod(a,⌊(q−1)/r⌋,q)≠1\mathrm{powMod}(a, \lfloor (q-1)/r \rfloor, q) \neq 1powMod(a,⌊(q−1)/r⌋,q)=1, then qqq is prime.

prime_13331831 (private lemma). The natural number 133318311333183113331831 is prime.

prime_173378833005251801 (private lemma). The natural number 173378833005251801173378833005251801173378833005251801 is prime.

prime_22149492674086928081353 (private lemma). The natural number 221494926740869280813532214949267408692808135322149492674086928081353 is prime.

prime_132896956044521568488119 (private lemma). The natural number 132896956044521568488119132896956044521568488119132896956044521568488119 is prime.

prime_1206781 (private lemma). The natural number 120678112067811206781 is prime.

prime_7240687 (private lemma). The natural number 724068772406877240687 is prime.

prime_107590001 (private lemma). The natural number 107590001107590001107590001 is prime.

prime_255515944373312847190720520512484175977 (private lemma). The natural number 255515944373312847190720520512484175977255515944373312847190720520512484175977255515944373312847190720520512484175977 is prime.

prime_q5 (private lemma). The natural number q5=205115282021455665897114700593932402728804164701536103180137503955397371q_5 = 205115282021455665897114700593932402728804164701536103180137503955397371q5​=205115282021455665897114700593932402728804164701536103180137503955397371 is prime.

p_prime_cert (lemma). The natural number p=2256−232−977p = 2^{256} - 2^{32} - 977p=2256−232−977 is prime (p≥2p \ge 2p≥2 and its only positive divisors are 111 and ppp). (Its docstring records the certificate p−1=2⋅3⋅7⋅13441⋅q5p - 1 = 2\cdot 3\cdot 7\cdot 13441\cdot q_5p−1=2⋅3⋅7⋅13441⋅q5​ with witness 333.)

instFactPrimeP (instance). Registers, for automatic type-class inference everywhere this file is imported, the fact that ppp is prime. Through Mathlib this makes Fp:=Z/pZ\mathbb{F}_p := \mathbb{Z}/p\mathbb{Z}Fp​:=Z/pZ a field, which is required for the group structure on the points of WWW below.

W (definition). WWW is the Weierstrass curve in affine coordinates over Fp\mathbb{F}_pFp​ with coefficients a1=a2=a3=a4=0a_1 = a_2 = a_3 = a_4 = 0a1​=a2​=a3​=a4​=0 and a6=7a_6 = 7a6​=7; its equation y2+a1xy+a3y=x3+a2x2+a4x+a6y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6y2+a1​xy+a3​y=x3+a2​x2+a4​x+a6​ is

y2=x3+7.y^2 = x^3 + 7 .y2=x3+7.

Its type of points W(Fp)W(\mathbb{F}_p)W(Fp​) (Mathlib) consists of the point at infinity, written 000, and the affine points (x,y)∈Fp2(x, y) \in \mathbb{F}_p^2(x,y)∈Fp2​ satisfying the equation together with a proof of nonsingularity; with the field instance above it is an additive commutative group (chord-and-tangent law, neutral element 000, −(x,y)=(x,−y)-(x,y) = (x, -y)−(x,y)=(x,−y)), and k⋅Pk\cdot Pk⋅P denotes the kkk-fold sum for k∈Nk \in \mathbb{N}k∈N (integer multiples for k∈Zk \in \mathbb{Z}k∈Z).

W_Δ (lemma). The discriminant of WWW (Mathlib's Δ=−b22b8−8b43−27b62+9b2b4b6\Delta = -b_2^2 b_8 - 8b_4^3 - 27b_6^2 + 9b_2b_4b_6Δ=−b22​b8​−8b43​−27b62​+9b2​b4​b6​, which for these coefficients has b2=b4=b8=0b_2 = b_4 = b_8 = 0b2​=b4​=b8​=0, b6=4a6=28b_6 = 4a_6 = 28b6​=4a6​=28) equals −21168-21168−21168 as an element of Fp\mathbb{F}_pFp​.

W_Δ_ne_zero (lemma). The discriminant of WWW is nonzero in Fp\mathbb{F}_pFp​ (equivalently, p∤21168p \nmid 21168p∤21168).

equation_iff_onCurve (lemma). For all naturals x,yx, yx,y: the residues (x mod p,y mod p)(x \bmod p, y \bmod p)(xmodp,ymodp) satisfy the equation of WWW in Fp\mathbb{F}_pFp​ if and only if onCurve(x,y)\mathrm{onCurve}(x, y)onCurve(x,y) is true, i.e. iff (y⋅y) mod p=(x⋅x⋅x+7) mod p(y\cdot y) \bmod p = (x\cdot x\cdot x + 7) \bmod p(y⋅y)modp=(x⋅x⋅x+7)modp.

nonsingular_of_onCurve (lemma). For all naturals x,yx, yx,y with onCurve(x,y)\mathrm{onCurve}(x, y)onCurve(x,y) true, the pair of residues (x mod p,y mod p)(x \bmod p, y \bmod p)(xmodp,ymodp) is a nonsingular point of WWW (Mathlib's notion: it satisfies the equation and the two partial derivatives of the defining polynomial do not both vanish there).

toPoint (definition). Converts an executable point to an optional Mathlib point, with values in W(Fp)∪{fail}W(\mathbb{F}_p) \cup \{\mathsf{fail}\}W(Fp​)∪{fail}: toPoint(∞)=0\mathrm{toPoint}(\infty) = 0toPoint(∞)=0 (the Mathlib point at infinity — a genuine point, not fail\mathsf{fail}fail); toPoint(x,y)=(x mod p,y mod p)\mathrm{toPoint}(x, y) = (x \bmod p, y \bmod p)toPoint(x,y)=(xmodp,ymodp) (an affine point of WWW, using the previous lemma for nonsingularity) if onCurve(x,y)\mathrm{onCurve}(x, y)onCurve(x,y) is true; and toPoint(x,y)=fail\mathrm{toPoint}(x, y) = \mathsf{fail}toPoint(x,y)=fail otherwise.

tp (definition). The total conversion tp(P)∈W(Fp)\mathrm{tp}(P) \in W(\mathbb{F}_p)tp(P)∈W(Fp​): toPoint(P)\mathrm{toPoint}(P)toPoint(P) if that is not fail\mathsf{fail}fail, and 000 otherwise. So tp(∞)=0\mathrm{tp}(\infty) = 0tp(∞)=0, tp(x,y)=(x mod p,y mod p)\mathrm{tp}(x,y) = (x \bmod p, y \bmod p)tp(x,y)=(xmodp,ymodp) for on-curve pairs, and every off-curve pair is sent to 000 (the same image as ∞\infty∞). Pairs differing by multiples of ppp have the same image.

Valid (definition). For an executable point PPP, Valid(P)\mathrm{Valid}(P)Valid(P) is the proposition: for all naturals x,yx, yx,y, if P=(x,y)P = (x, y)P=(x,y) then onCurve(x,y)\mathrm{onCurve}(x, y)onCurve(x,y) is true. ∞\infty∞ is Valid; coordinates are not required to be below ppp.

Reduced (definition). For an executable point PPP, Reduced(P)\mathrm{Reduced}(P)Reduced(P) is the proposition: for all naturals x,yx, yx,y, if P=(x,y)P = (x, y)P=(x,y) then x<px < px<p and y<py < py<p. ∞\infty∞ is Reduced; being on the curve is not required.

ofPoint (definition). Converts a Mathlib point to an executable point: 0↦∞0 \mapsto \infty0↦∞ and an affine point (x,y)(x, y)(x,y) with x,y∈Fpx, y \in \mathbb{F}_px,y∈Fp​ ↦(val(x),val(y))\mapsto (\mathrm{val}(x), \mathrm{val}(y))↦(val(x),val(y)), where val\mathrm{val}val is the canonical representative in {0,…,p−1}\{0, \dots, p-1\}{0,…,p−1}.

Gpt (definition). Gpt∈W(Fp)G_{\mathrm{pt}} \in W(\mathbb{F}_p)Gpt​∈W(Fp​) is the affine point (Gx mod p, Gy mod p)(G_x \bmod p,\ G_y \bmod p)(Gx​modp, Gy​modp); its nonsingularity is obtained from onCurve(Gx,Gy)=true\mathrm{onCurve}(G_x, G_y) = \text{true}onCurve(Gx​,Gy​)=true, which is checked by evaluation.

pneg (definition). Executable negation: pneg(∞)=∞\mathrm{pneg}(\infty) = \inftypneg(∞)=∞ and pneg(x,y)=(x, (p−y mod p) mod p)\mathrm{pneg}(x, y) = \big(x,\ (p - y \bmod p) \bmod p\big)pneg(x,y)=(x, (p−ymodp)modp); the first coordinate is kept as is (unreduced if it was), the second becomes the residue of −y-y−y in {0,…,p−1}\{0, \dots, p-1\}{0,…,p−1}.

hasEvenY (definition). For a pair (x,y)(x, y)(x,y) of naturals, hasEvenY(x,y)\mathrm{hasEvenY}(x, y)hasEvenY(x,y) is the boolean "y mod 2=0y \bmod 2 = 0ymod2=0", computed on the raw natural yyy (no reduction mod ppp).

evenY (definition). For a Mathlib point: evenY(0)=true\mathrm{evenY}(0) = \text{true}evenY(0)=true (infinity counts as even), and evenY(x,y)\mathrm{evenY}(x, y)evenY(x,y) is the boolean "val(y)\mathrm{val}(y)val(y) is even", with val(y)∈{0,…,p−1}\mathrm{val}(y) \in \{0, \dots, p-1\}val(y)∈{0,…,p−1}.

tagged (definition). tagged(s,m)=taggedHash(ascii(s),m)=SHA256(SHA256(ascii(s))∥SHA256(ascii(s))∥m)\mathrm{tagged}(s, m) = \mathrm{taggedHash}(\mathrm{ascii}(s), m) = \mathrm{SHA256}\big(\mathrm{SHA256}(\mathrm{ascii}(s)) \Vert \mathrm{SHA256}(\mathrm{ascii}(s)) \Vert m\big)tagged(s,m)=taggedHash(ascii(s),m)=SHA256(SHA256(ascii(s))∥SHA256(ascii(s))∥m) for a text tag sss and a byte string mmm.

xbytes (definition). For a pair P=(x,y)P = (x, y)P=(x,y), xbytes(P)=be32(x)\mathrm{xbytes}(P) = \mathrm{be32}(x)xbytes(P)=be32(x), the 323232-byte big-endian encoding of x mod 2256x \bmod 2^{256}xmod2256.

cbytes (definition). For a pair P=(x,y)P = (x, y)P=(x,y), cbytes(P)=[c]∥xbytes(P)\mathrm{cbytes}(P) = [c] \Vert \mathrm{xbytes}(P)cbytes(P)=[c]∥xbytes(P), a 333333-byte string whose first byte is c=2c = 2c=2 if hasEvenY(P)\mathrm{hasEvenY}(P)hasEvenY(P) and c=3c = 3c=3 otherwise.

zero33 (definition). zero33\mathrm{zero}_{33}zero33​ is the byte string consisting of 333333 zero bytes.

cbytesExt (definition). For an executable point: cbytesExt(∞)=zero33\mathrm{cbytesExt}(\infty) = \mathrm{zero}_{33}cbytesExt(∞)=zero33​ and cbytesExt(P)=cbytes(P)\mathrm{cbytesExt}(P) = \mathrm{cbytes}(P)cbytesExt(P)=cbytes(P) for a pair PPP.

cpoint (definition). cpoint(b)=parsePubkey(b)\mathrm{cpoint}(b) = \mathrm{parsePubkey}(b)cpoint(b)=parsePubkey(b) if ∣b∣=33|b| = 33∣b∣=33, and failure otherwise. Unfolded: for b=[t]∥rb = [t] \Vert rb=[t]∥r of length 333333, it fails unless t∈{2,3}t \in \{2, 3\}t∈{2,3}; then x=beVal(r)x = \mathrm{beVal}(r)x=beVal(r), it fails if x≥px \ge px≥p, and otherwise returns liftXParity(x,odd=(t=3))\mathrm{liftXParity}(x, \mathit{odd} = (t = 3))liftXParity(x,odd=(t=3)) (which may fail). The result type is "optional pair of naturals", which is literally the same type as an executable point: a parse failure is the value ∞\infty∞.

cpointExt (definition). cpointExt(b)\mathrm{cpointExt}(b)cpointExt(b) is an optional executable point: if b=zero33b = \mathrm{zero}_{33}b=zero33​ it succeeds with ∞\infty∞; otherwise it succeeds with the pair cpoint(b)\mathrm{cpoint}(b)cpoint(b) when cpoint(b)\mathrm{cpoint}(b)cpoint(b) succeeds, and fails when cpoint(b)\mathrm{cpoint}(b)cpoint(b) fails (here failure and ∞\infty∞ are distinct outcomes).

KeyAggCtx (record type). A key-aggregation context is a triple (Q,gacc,tacc)(Q, \mathit{gacc}, \mathit{tacc})(Q,gacc,tacc) where QQQ is a pair of naturals (by its type it can never be ∞\infty∞) and gacc,tacc\mathit{gacc}, \mathit{tacc}gacc,tacc are naturals. The type is given automatically derived printing and decidable equality (componentwise).

hashKeys (definition). For a list of byte strings pk1,…,pkupk_1, \dots, pk_upk1​,…,pku​: hashKeys=tagged("KeyAgg list", pk1∥pk2∥⋯∥pku)\mathrm{hashKeys} = \mathrm{tagged}(\text{"KeyAgg list"},\ pk_1 \Vert pk_2 \Vert \cdots \Vert pk_u)hashKeys=tagged("KeyAgg list", pk1​∥pk2​∥⋯∥pku​) (for the empty list, the tagged hash of the empty string).

getSecondKey (definition). For a list pkspkspks: if it is empty, zero33\mathrm{zero}_{33}zero33​; otherwise, with pk1pk_1pk1​ its first entry, the first entry of pkspkspks (scanning from the start) that is different from pk1pk_1pk1​, or zero33\mathrm{zero}_{33}zero33​ if there is none.

keyAggCoeffInternal (definition). For a list pkspkspks and byte strings pk,pk2pk, pk_2pk,pk2​: the natural number 111 if pk=pk2pk = pk_2pk=pk2​, and otherwise beVal(tagged("KeyAgg coefficient", hashKeys(pks)∥pk)) mod n\mathrm{beVal}\big(\mathrm{tagged}(\text{"KeyAgg coefficient"},\ \mathrm{hashKeys}(pks) \Vert pk)\big) \bmod nbeVal(tagged("KeyAgg coefficient", hashKeys(pks)∥pk))modn.

keyAggCoeff (definition). keyAggCoeff(pks,pk)=keyAggCoeffInternal(pks,pk,getSecondKey(pks))\mathrm{keyAggCoeff}(pks, pk) = \mathrm{keyAggCoeffInternal}(pks, pk, \mathrm{getSecondKey}(pks))keyAggCoeff(pks,pk)=keyAggCoeffInternal(pks,pk,getSecondKey(pks)): it is 111 when pkpkpk equals the second key, and the hash-derived value mod nnn otherwise. pkpkpk need not occur in pkspkspks.

keyAggSum (definition). For a fixed list pkspkspks (used for the coefficients) and a list ℓ\ellℓ of byte strings, an optional executable point defined by recursion on ℓ\ellℓ: for ℓ\ellℓ empty it succeeds with ∞\infty∞; for ℓ=pk::rest\ell = pk :: \mathit{rest}ℓ=pk::rest it succeeds with

padd(pmul(keyAggCoeff(pks,pk), P), acc)\mathrm{padd}\big(\mathrm{pmul}(\mathrm{keyAggCoeff}(pks, pk),\ P),\ \mathit{acc}\big)padd(pmul(keyAggCoeff(pks,pk), P), acc)

if cpoint(pk)\mathrm{cpoint}(pk)cpoint(pk) succeeds with a pair PPP and keyAggSum(pks,rest)\mathrm{keyAggSum}(pks, \mathit{rest})keyAggSum(pks,rest) succeeds with acc\mathit{acc}acc, and fails otherwise. For ℓ=(pk1,…,pku)\ell = (pk_1, \dots, pk_u)ℓ=(pk1​,…,pku​) with all keys parsing to PiP_iPi​ and ai=keyAggCoeff(pks,pki)a_i = \mathrm{keyAggCoeff}(pks, pk_i)ai​=keyAggCoeff(pks,pki​) this is the right-nested sum padd(a1P1,padd(a2P2,…,padd(auPu,∞)⋯ ))\mathrm{padd}(a_1P_1, \mathrm{padd}(a_2P_2, \dots, \mathrm{padd}(a_uP_u, \infty)\cdots))padd(a1​P1​,padd(a2​P2​,…,padd(au​Pu​,∞)⋯)), with aiPi=pmul(ai,Pi)a_iP_i = \mathrm{pmul}(a_i, P_i)ai​Pi​=pmul(ai​,Pi​).

keyAgg (definition). keyAgg(pks)\mathrm{keyAgg}(pks)keyAgg(pks): compute keyAggSum(pks,pks)\mathrm{keyAggSum}(pks, pks)keyAggSum(pks,pks); if it succeeds with a pair QQQ, the result is the context (Q,gacc=1,tacc=0)(Q, \mathit{gacc} = 1, \mathit{tacc} = 0)(Q,gacc=1,tacc=0); if it fails (some key does not parse) or yields ∞\infty∞, keyAgg\mathrm{keyAgg}keyAgg fails. For the empty list the sum is ∞\infty∞, so keyAgg\mathrm{keyAgg}keyAgg fails.

applyTweak (definition). For a context (Q,gacc,tacc)(Q, \mathit{gacc}, \mathit{tacc})(Q,gacc,tacc), a byte string tweak\mathit{tweak}tweak and a boolean isXonly\mathit{isXonly}isXonly:

  1. g=n−1g = n - 1g=n−1 if isXonly\mathit{isXonly}isXonly is true and hasEvenY(Q)\mathrm{hasEvenY}(Q)hasEvenY(Q) is false; otherwise g=1g = 1g=1.
  2. t=beVal(tweak)t = \mathrm{beVal}(\mathit{tweak})t=beVal(tweak) (the length of tweak\mathit{tweak}tweak is not checked).
  3. If t≥nt \ge nt≥n, fail.
  4. Q′=padd(pmul(g,Q), pmul(t,G))Q' = \mathrm{padd}\big(\mathrm{pmul}(g, Q),\ \mathrm{pmul}(t, G)\big)Q′=padd(pmul(g,Q), pmul(t,G)); if Q′=∞Q' = \inftyQ′=∞, fail.
  5. Otherwise succeed with (Q′, (g⋅gacc) mod n, (t+g⋅tacc) mod n)\big(Q',\ (g\cdot\mathit{gacc}) \bmod n,\ (t + g\cdot\mathit{tacc}) \bmod n\big)(Q′, (g⋅gacc)modn, (t+g⋅tacc)modn).

applyTweaks (definition). For a context and a list of (tweak, flag) pairs: with the empty list, succeed with the context unchanged; otherwise apply applyTweak\mathrm{applyTweak}applyTweak with the first pair, fail if it fails, and continue with the remaining pairs from the new context.

keyAggTweaked (definition). keyAggTweaked(pks,tweaks)\mathrm{keyAggTweaked}(pks, \mathit{tweaks})keyAggTweaked(pks,tweaks): fail if keyAgg(pks)\mathrm{keyAgg}(pks)keyAgg(pks) fails; otherwise applyTweaks\mathrm{applyTweaks}applyTweaks of its context with tweaks\mathit{tweaks}tweaks.

nonceSum (definition). For j∈Nj \in \mathbb{N}j∈N and a list ℓ\ellℓ of byte strings, an optional executable point by recursion on ℓ\ellℓ: for ℓ\ellℓ empty it succeeds with ∞\infty∞; for ℓ=pn::rest\ell = pn :: \mathit{rest}ℓ=pn::rest it succeeds with padd(R,acc)\mathrm{padd}(R, \mathit{acc})padd(R,acc) if cpoint(take33(drop33j(pn)))\mathrm{cpoint}\big(\mathrm{take}_{33}(\mathrm{drop}_{33j}(pn))\big)cpoint(take33​(drop33j​(pn))) succeeds with a pair RRR and nonceSum(j,rest)\mathrm{nonceSum}(j, \mathit{rest})nonceSum(j,rest) succeeds with acc\mathit{acc}acc, and fails otherwise. Each individual slice must parse as a genuine pair (it cannot be ∞\infty∞; zero33\mathrm{zero}_{33}zero33​ does not parse). The total length of pnpnpn is not checked: for j=0j = 0j=0 its first 333333 bytes are used, for j=1j = 1j=1 its bytes 333333 to 656565, other bytes are ignored.

nonceAgg (definition). For a list of public nonces: if nonceSum(0,⋅)\mathrm{nonceSum}(0, \cdot)nonceSum(0,⋅) succeeds with R1R_1R1​ and nonceSum(1,⋅)\mathrm{nonceSum}(1, \cdot)nonceSum(1,⋅) succeeds with R2R_2R2​, the result is the 666666-byte string cbytesExt(R1)∥cbytesExt(R2)\mathrm{cbytesExt}(R_1) \Vert \mathrm{cbytesExt}(R_2)cbytesExt(R1​)∥cbytesExt(R2​); otherwise it fails. For the empty list the result is zero33∥zero33\mathrm{zero}_{33} \Vert \mathrm{zero}_{33}zero33​∥zero33​.

SessionCtx (record type). A session context consists of a byte string aggnonce\mathit{aggnonce}aggnonce, a list of byte strings pkspkspks, a list tweaks\mathit{tweaks}tweaks of pairs (byte string, boolean), and a byte string msg\mathit{msg}msg, with no constraints among them.

SessionValues (record type). A record (Q,gacc,tacc,b,R′,R,e)(Q, \mathit{gacc}, \mathit{tacc}, b, R', R, e)(Q,gacc,tacc,b,R′,R,e) with QQQ and RRR pairs of naturals, gacc,tacc,b,e\mathit{gacc}, \mathit{tacc}, b, egacc,tacc,b,e naturals, and R′R'R′ an executable point (possibly ∞\infty∞).

getSessionValues (definition). For a session context (aggnonce,pks,tweaks,msg)(\mathit{aggnonce}, pks, \mathit{tweaks}, \mathit{msg})(aggnonce,pks,tweaks,msg), an optional session-values record:

  1. If keyAggTweaked(pks,tweaks)\mathrm{keyAggTweaked}(pks, \mathit{tweaks})keyAggTweaked(pks,tweaks) fails, fail; otherwise let (Q,gacc,tacc)(Q, \mathit{gacc}, \mathit{tacc})(Q,gacc,tacc) be its result.
  2. b=beVal(tagged("MuSig/noncecoef", aggnonce∥xbytes(Q)∥msg)) mod nb = \mathrm{beVal}\big(\mathrm{tagged}(\text{"MuSig/noncecoef"},\ \mathit{aggnonce} \Vert \mathrm{xbytes}(Q) \Vert \mathit{msg})\big) \bmod nb=beVal(tagged("MuSig/noncecoef", aggnonce∥xbytes(Q)∥msg))modn, hashing the whole aggnonce\mathit{aggnonce}aggnonce whatever its length.
  3. R1=cpointExt(take33(aggnonce))R_1 = \mathrm{cpointExt}(\mathrm{take}_{33}(\mathit{aggnonce}))R1​=cpointExt(take33​(aggnonce)) and R2=cpointExt(take33(drop33(aggnonce)))R_2 = \mathrm{cpointExt}(\mathrm{take}_{33}(\mathrm{drop}_{33}(\mathit{aggnonce})))R2​=cpointExt(take33​(drop33​(aggnonce))); if either fails, fail. Each is ∞\infty∞ (slice equal to zero33\mathrm{zero}_{33}zero33​) or a parsed pair.
  4. R′=padd(R1,pmul(b,R2))R' = \mathrm{padd}\big(R_1, \mathrm{pmul}(b, R_2)\big)R′=padd(R1​,pmul(b,R2​)).
  5. R=(Gx,Gy)R = (G_x, G_y)R=(Gx​,Gy​) if R′=∞R' = \inftyR′=∞, and R=R′R = R'R=R′ otherwise.
  6. e=beVal(tagged("BIP0340/challenge", xbytes(R)∥xbytes(Q)∥msg)) mod ne = \mathrm{beVal}\big(\mathrm{tagged}(\text{"BIP0340/challenge"},\ \mathrm{xbytes}(R) \Vert \mathrm{xbytes}(Q) \Vert \mathit{msg})\big) \bmod ne=beVal(tagged("BIP0340/challenge", xbytes(R)∥xbytes(Q)∥msg))modn.
  7. Succeed with (Q,gacc,tacc,b,R′,R,e)(Q, \mathit{gacc}, \mathit{tacc}, b, R', R, e)(Q,gacc,tacc,b,R′,R,e).

partialSigVerifyInternal (definition). For byte strings psig\mathit{psig}psig, pubnonce\mathit{pubnonce}pubnonce, pkpkpk and a session context ctxctxctx, a boolean:

  1. If getSessionValues(ctx)\mathrm{getSessionValues}(ctx)getSessionValues(ctx) fails, false; otherwise use its (Q,gacc,tacc,b,R′,R,e)(Q, \mathit{gacc}, \mathit{tacc}, b, R', R, e)(Q,gacc,tacc,b,R′,R,e).
  2. s=beVal(psig)s = \mathrm{beVal}(\mathit{psig})s=beVal(psig); if ∣psig∣≠32|\mathit{psig}| \neq 32∣psig∣=32 or s≥ns \ge ns≥n, false.
  3. R1=cpoint(take33(pubnonce))R_1 = \mathrm{cpoint}(\mathrm{take}_{33}(\mathit{pubnonce}))R1​=cpoint(take33​(pubnonce)), R2=cpoint(take33(drop33(pubnonce)))R_2 = \mathrm{cpoint}(\mathrm{take}_{33}(\mathrm{drop}_{33}(\mathit{pubnonce})))R2​=cpoint(take33​(drop33​(pubnonce))), P=cpoint(pk)P = \mathrm{cpoint}(pk)P=cpoint(pk); if any of them fails, false.
  4. If pkpkpk is not an entry of ctxctxctx's key list pkspkspks, false.
  5. Re′=padd(R1,pmul(b,R2))R_e' = \mathrm{padd}\big(R_1, \mathrm{pmul}(b, R_2)\big)Re′​=padd(R1​,pmul(b,R2​)); Re=Re′R_e = R_e'Re​=Re′​ if hasEvenY(R)\mathrm{hasEvenY}(R)hasEvenY(R), otherwise Re=pneg(Re′)R_e = \mathrm{pneg}(R_e')Re​=pneg(Re′​).
  6. a=keyAggCoeff(pks,pk)a = \mathrm{keyAggCoeff}(pks, pk)a=keyAggCoeff(pks,pk); g=1g = 1g=1 if hasEvenY(Q)\mathrm{hasEvenY}(Q)hasEvenY(Q), otherwise g=n−1g = n - 1g=n−1; g′=(g⋅gacc) mod ng' = (g\cdot\mathit{gacc}) \bmod ng′=(g⋅gacc)modn.
  7. The result is true iff the executable points pmul(s,G)\mathrm{pmul}(s, G)pmul(s,G) and padd(Re, pmul((e⋅a⋅g′) mod n, P))\mathrm{padd}\big(R_e,\ \mathrm{pmul}((e\cdot a\cdot g') \bmod n,\ P)\big)padd(Re​, pmul((e⋅a⋅g′)modn, P)) are literally equal (both ∞\infty∞ or the same pair of naturals).

partialSigAgg (definition). For a list of byte strings psig1,…,psigu\mathit{psig}_1, \dots, \mathit{psig}_upsig1​,…,psigu​ and a session context, an optional byte string:

  1. If getSessionValues(ctx)\mathrm{getSessionValues}(ctx)getSessionValues(ctx) fails, fail; otherwise use its values.
  2. If some psigi\mathit{psig}_ipsigi​ has ∣psigi∣≠32|\mathit{psig}_i| \neq 32∣psigi​∣=32 or beVal(psigi)≥n\mathrm{beVal}(\mathit{psig}_i) \ge nbeVal(psigi​)≥n, fail.
  3. g=1g = 1g=1 if hasEvenY(Q)\mathrm{hasEvenY}(Q)hasEvenY(Q), otherwise g=n−1g = n - 1g=n−1.
  4. s=(∑i=1ubeVal(psigi)+e⋅g⋅tacc) mod ns = \big(\sum_{i=1}^{u} \mathrm{beVal}(\mathit{psig}_i) + e\cdot g\cdot\mathit{tacc}\big) \bmod ns=(∑i=1u​beVal(psigi​)+e⋅g⋅tacc)modn (natural arithmetic; the empty sum is 000, so for u=0u = 0u=0, s=(e g tacc) mod ns = (e\,g\,\mathit{tacc}) \bmod ns=(egtacc)modn).
  5. Succeed with the 646464-byte string xbytes(R)∥be32(s)\mathrm{xbytes}(R) \Vert \mathrm{be32}(s)xbytes(R)∥be32(s).

lagrangeCoeff (definition). For a finite set SSS of natural numbers and a natural iii, the element of Z/nZ\mathbb{Z}/n\mathbb{Z}Z/nZ

λiS=∏j∈S∖{i}(j:Z/n)⋅((j:Z/n)−(i:Z/n))−1,\lambda_i^S = \prod_{j \in S \setminus \{i\}} (j : \mathbb{Z}/n)\cdot\big((j : \mathbb{Z}/n) - (i : \mathbb{Z}/n)\big)^{-1},λiS​=j∈S∖{i}∏​(j:Z/n)⋅((j:Z/n)−(i:Z/n))−1,

where (j:Z/n)(j : \mathbb{Z}/n)(j:Z/n) is the residue j mod nj \bmod njmodn, subtraction is in Z/n\mathbb{Z}/nZ/n, and −1{}^{-1}−1 is Mathlib's total inverse on Z/n\mathbb{Z}/nZ/n (the multiplicative inverse for residues coprime to nnn, and 0−1=00^{-1} = 00−1=0; the file registers no primality instance for nnn). The empty product is 111 (e.g. for S={i}S = \{i\}S={i} or S=∅S = \emptysetS=∅); if i∉Si \notin Si∈/S nothing is removed from SSS; a factor with j≡i(modn)j \equiv i \pmod nj≡i(modn), j≠ij \neq ij=i, equals j⋅0−1=0j\cdot 0^{-1} = 0j⋅0−1=0.

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