secp256k1 as a Mathlib elliptic curve, the bridge from the executable curve, and BIP327 MuSig2 session algorithms
DefinitionBitcoinMuSigOver 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 over ZMod p as a Mathlib WeierstrassCurve.Affine, with discriminant 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 ; 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 at infinity.
FROST. lagrangeCoeff S i — the Lagrange coefficient at 0 for identifier set , 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.
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
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)
- and are fixed natural numbers.
- and are fixed natural numbers ( is even: its last hexadecimal digit is ).
Modular exponentiation (from the signature file)
- : if return ; otherwise, if return , else recurse with , base , exponent and accumulator if is odd ( unchanged if is even).
- . (In natural-number arithmetic .)
- .
Executable points (from the signature file)
- 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 inversion. ; the lemma below gives , 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 .
Bytes, hashing and parsing (from the serialization, signature and Taproot files)
- A byte string is a finite list of bytes (values ); is its length and concatenation. is the first bytes, removes the first bytes (slices of too-short strings are silently shorter).
- (big-endian value, any length; for the empty string).
- (Taproot file) is the -byte big-endian encoding of (higher bits silently dropped).
- is the executable SHA-256 of the serialization file; is the UTF-8 byte string of the text ; .
- : let (natural-number division). If the result is the pair with if the parity of is the requested one, else (so when , whatever was requested); otherwise it fails (returns , the "no point" value).
- : fails on the empty string. For : if and , let ; return if , else fail. Else if and , let , ; return if , , (for ) is odd iff , and ; else fail. Otherwise fail. Failure is the value .
The declarations of the file, in order
powModAux_eq (lemma). For every natural modulus and all naturals : if and (which means when , and is automatic when because ), then
powMod_eq (lemma). For all naturals (no hypotheses; and included), (with , so for this is ).
prime_of_cert (lemma, Pratt step). For naturals and a finite list of naturals: if (i) , (ii) every is prime, (iii) (list product with multiplicity; the empty product is ), (iv) , and (v) for every , , then is prime.
prime_13331831 (private lemma). The natural number is prime.
prime_173378833005251801 (private lemma). The natural number is prime.
prime_22149492674086928081353 (private lemma). The natural number is prime.
prime_132896956044521568488119 (private lemma). The natural number is prime.
prime_1206781 (private lemma). The natural number is prime.
prime_7240687 (private lemma). The natural number is prime.
prime_107590001 (private lemma). The natural number is prime.
prime_255515944373312847190720520512484175977 (private lemma). The natural number is prime.
prime_q5 (private lemma). The natural number is prime.
p_prime_cert (lemma). The natural number is prime ( and its only positive divisors are and ). (Its docstring records the certificate with witness .)
instFactPrimeP (instance). Registers, for automatic type-class inference everywhere this file is imported, the fact that is prime. Through Mathlib this makes a field, which is required for the group structure on the points of below.
W (definition). is the Weierstrass curve in affine coordinates over with coefficients and ; its equation is
Its type of points (Mathlib) consists of the point at infinity, written , and the affine points 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 , ), and denotes the -fold sum for (integer multiples for ).
W_Δ (lemma). The discriminant of (Mathlib's , which for these coefficients has , ) equals as an element of .
W_Δ_ne_zero (lemma). The discriminant of is nonzero in (equivalently, ).
equation_iff_onCurve (lemma). For all naturals : the residues satisfy the equation of in if and only if is true, i.e. iff .
nonsingular_of_onCurve (lemma). For all naturals with true, the pair of residues is a nonsingular point of (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 : (the Mathlib point at infinity — a genuine point, not ); (an affine point of , using the previous lemma for nonsingularity) if is true; and otherwise.
tp (definition). The total conversion : if that is not , and otherwise. So , for on-curve pairs, and every off-curve pair is sent to (the same image as ). Pairs differing by multiples of have the same image.
Valid (definition). For an executable point , is the proposition: for all naturals , if then is true. is Valid; coordinates are not required to be below .
Reduced (definition). For an executable point , is the proposition: for all naturals , if then and . is Reduced; being on the curve is not required.
ofPoint (definition). Converts a Mathlib point to an executable point: and an affine point with , where is the canonical representative in .
Gpt (definition). is the affine point ; its nonsingularity is obtained from , which is checked by evaluation.
pneg (definition). Executable negation: and ; the first coordinate is kept as is (unreduced if it was), the second becomes the residue of in .
hasEvenY (definition). For a pair of naturals, is the boolean "", computed on the raw natural (no reduction mod ).
evenY (definition). For a Mathlib point: (infinity counts as even), and is the boolean " is even", with .
tagged (definition). for a text tag and a byte string .
xbytes (definition). For a pair , , the -byte big-endian encoding of .
cbytes (definition). For a pair , , a -byte string whose first byte is if and otherwise.
zero33 (definition). is the byte string consisting of zero bytes.
cbytesExt (definition). For an executable point: and for a pair .
cpoint (definition). if , and failure otherwise. Unfolded: for of length , it fails unless ; then , it fails if , and otherwise returns (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 .
cpointExt (definition). is an optional executable point: if it succeeds with ; otherwise it succeeds with the pair when succeeds, and fails when fails (here failure and are distinct outcomes).
KeyAggCtx (record type). A key-aggregation context is a triple where is a pair of naturals (by its type it can never be ) and are naturals. The type is given automatically derived printing and decidable equality (componentwise).
hashKeys (definition). For a list of byte strings : (for the empty list, the tagged hash of the empty string).
getSecondKey (definition). For a list : if it is empty, ; otherwise, with its first entry, the first entry of (scanning from the start) that is different from , or if there is none.
keyAggCoeffInternal (definition). For a list and byte strings : the natural number if , and otherwise .
keyAggCoeff (definition). : it is when equals the second key, and the hash-derived value mod otherwise. need not occur in .
keyAggSum (definition). For a fixed list (used for the coefficients) and a list of byte strings, an optional executable point defined by recursion on : for empty it succeeds with ; for it succeeds with
if succeeds with a pair and succeeds with , and fails otherwise. For with all keys parsing to and this is the right-nested sum , with .
keyAgg (definition). : compute ; if it succeeds with a pair , the result is the context ; if it fails (some key does not parse) or yields , fails. For the empty list the sum is , so fails.
applyTweak (definition). For a context , a byte string and a boolean :
- if is true and is false; otherwise .
- (the length of is not checked).
- If , fail.
- ; if , fail.
- Otherwise succeed with .
applyTweaks (definition). For a context and a list of (tweak, flag) pairs: with the empty list, succeed with the context unchanged; otherwise apply with the first pair, fail if it fails, and continue with the remaining pairs from the new context.
keyAggTweaked (definition). : fail if fails; otherwise of its context with .
nonceSum (definition). For and a list of byte strings, an optional executable point by recursion on : for empty it succeeds with ; for it succeeds with if succeeds with a pair and succeeds with , and fails otherwise. Each individual slice must parse as a genuine pair (it cannot be ; does not parse). The total length of is not checked: for its first bytes are used, for its bytes to , other bytes are ignored.
nonceAgg (definition). For a list of public nonces: if succeeds with and succeeds with , the result is the -byte string ; otherwise it fails. For the empty list the result is .
SessionCtx (record type). A session context consists of a byte string , a list of byte strings , a list of pairs (byte string, boolean), and a byte string , with no constraints among them.
SessionValues (record type). A record with and pairs of naturals, naturals, and an executable point (possibly ).
getSessionValues (definition). For a session context , an optional session-values record:
- If fails, fail; otherwise let be its result.
- , hashing the whole whatever its length.
- and ; if either fails, fail. Each is (slice equal to ) or a parsed pair.
- .
- if , and otherwise.
- .
- Succeed with .
partialSigVerifyInternal (definition). For byte strings , , and a session context , a boolean:
- If fails, false; otherwise use its .
- ; if or , false.
- , , ; if any of them fails, false.
- If is not an entry of 's key list , false.
- ; if , otherwise .
- ; if , otherwise ; .
- The result is true iff the executable points and are literally equal (both or the same pair of naturals).
partialSigAgg (definition). For a list of byte strings and a session context, an optional byte string:
- If fails, fail; otherwise use its values.
- If some has or , fail.
- if , otherwise .
- (natural arithmetic; the empty sum is , so for , ).
- Succeed with the -byte string .
lagrangeCoeff (definition). For a finite set of natural numbers and a natural , the element of
where is the residue , subtraction is in , and is Mathlib's total inverse on (the multiplicative inverse for residues coprime to , and ; the file registers no primality instance for ). The empty product is (e.g. for or ); if nothing is removed from ; a factor with , , equals .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.