Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

BIP327 end to end: partial signatures that verify aggregate to a BIP340 signature that verifies

Proved
BitcoinMuSig.partialSigAgg_schnorrVerify

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

bip327bip340bitcoinelliptic-curveformal-verificationfrostmathlibmultisignaturemusig2schnorrsecp256k1

For a session over a nonempty list of signers whose keys are the session's keys, whose nonces aggregate to the session's aggregate nonce, whose keys have order dividing nnn, and whose aggregate nonce point is not infinity: if every partial signature passes partialSigVerifyInternal, then the session values exist, partialSigAgg returns some sig, and the signature mission's schnorrVerify (xbytes Q) msg sig = true. All of BIP327's tweak accumulation, parity negations and encodings are included.

Preamble
import Definitions.Def_BitcoinMuSig
import Definitions.Def_BitcoinSer
open BitcoinMuSig BitcoinSig BitcoinTaproot
Formal statement
theorem BitcoinMuSig.partialSigAgg_schnorrVerify (ctx : SessionCtx)
    (sigs : List (BitcoinSer.Bytes × BitcoinSer.Bytes × BitcoinSer.Bytes)) (hne : sigs ≠ [])
    (hpks : ctx.pks = sigs.map fun t => t.2.2) (hkeys : ∀ pk ∈ ctx.pks, n • tp (cpoint pk) = 0)
    (hagg : nonceAgg (sigs.map fun t => t.2.1) = some ctx.aggnonce)
    (hver : ∀ t ∈ sigs, partialSigVerifyInternal t.1 t.2.1 t.2.2 ctx = true)
    (hR : ∀ sv, getSessionValues ctx = some sv → sv.R' ≠ none) :
    ∃ sv sig, getSessionValues ctx = some sv ∧ partialSigAgg (sigs.map fun t => t.1) ctx = some sig ∧
      schnorrVerify (xbytes sv.Q) ctx.msg sig = true := 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.partialSigAgg_schnorrVerify

Source file: Thm_BitcoinMuSig_partialSigAgg_schnorrVerify.lean (one theorem; it builds on the MuSig definition file, which itself uses the secp256k1 signature and Taproot definition files).

Statement. Let ctx=(aggnonce,pks,tweaks,msg)ctx = (\mathit{aggnonce}, pks, \mathit{tweaks}, \mathit{msg})ctx=(aggnonce,pks,tweaks,msg) be any session context (any byte strings, any list of keys, any list of (tweak, x-only flag) pairs of any length, any message), and let

sigs=[(psig1,pn1,pk1), …, (psigu,pnu,pku)]\mathit{sigs} = \big[(\mathit{psig}_1, pn_1, pk_1),\ \dots,\ (\mathit{psig}_u, pn_u, pk_u)\big]sigs=[(psig1​,pn1​,pk1​), …, (psigu​,pnu​,pku​)]

be a list of triples of byte strings (a partial signature, a public nonce, a public key; repetitions allowed). Assume all of the following.

  1. Non-empty: u≥1u \ge 1u≥1.
  2. Keys match: pks=[pk1,…,pku]pks = [pk_1, \dots, pk_u]pks=[pk1​,…,pku​] exactly (same entries, same order, same multiplicities).
  3. Key torsion: for every entry pkpkpk of pkspkspks,  n⋅tp(cpoint(pk))=0\ n \cdot \mathrm{tp}(\mathrm{cpoint}(pk)) = 0 n⋅tp(cpoint(pk))=0 in the group W(Fp)W(\mathbb{F}_p)W(Fp​). Here cpoint(pk)\mathrm{cpoint}(pk)cpoint(pk) is used as an executable point, so a key that fails to parse contributes the value ∞\infty∞, for which tp(∞)=0\mathrm{tp}(\infty) = 0tp(∞)=0 and the condition holds automatically; for a key parsing to (x,y)(x, y)(x,y), tp(x,y)\mathrm{tp}(x, y)tp(x,y) is the point (x mod p,y mod p)(x \bmod p, y \bmod p)(xmodp,ymodp) of W(Fp)W(\mathbb{F}_p)W(Fp​) if onCurve(x,y)\mathrm{onCurve}(x, y)onCurve(x,y) and 000 otherwise, and n⋅( ⋅ )n\cdot(\,\cdot\,)n⋅(⋅) is the nnn-fold sum.
  4. Aggregate nonce: nonceAgg(pn1,…,pnu)\mathrm{nonceAgg}(pn_1, \dots, pn_u)nonceAgg(pn1​,…,pnu​) succeeds and is exactly the byte string aggnonce\mathit{aggnonce}aggnonce.
  5. Every partial signature verifies: for each i=1,…,ui = 1, \dots, ui=1,…,u,  partialSigVerifyInternal(psigi,pni,pki,ctx)=true\ \mathrm{partialSigVerifyInternal}(\mathit{psig}_i, pn_i, pk_i, ctx) = \text{true} partialSigVerifyInternal(psigi​,pni​,pki​,ctx)=true.
  6. Non-degenerate nonce: for every session-values record svsvsv, if getSessionValues(ctx)\mathrm{getSessionValues}(ctx)getSessionValues(ctx) succeeds with svsvsv then its raw aggregate nonce R′R'R′ is not ∞\infty∞. (This quantifies over all records, but only the actual output of the deterministic function getSessionValues(ctx)\mathrm{getSessionValues}(ctx)getSessionValues(ctx) is constrained; the hypothesis would hold vacuously if getSessionValues(ctx)\mathrm{getSessionValues}(ctx)getSessionValues(ctx) failed, although hypothesis 5 with u≥1u \ge 1u≥1 already requires it to succeed, since partialSigVerifyInternal\mathrm{partialSigVerifyInternal}partialSigVerifyInternal returns false when it fails.)

Conclusion. There exist a session-values record sv=(Q,gacc,tacc,b,R′,R,e)sv = (Q, \mathit{gacc}, \mathit{tacc}, b, R', R, e)sv=(Q,gacc,tacc,b,R′,R,e) and a byte string sig\mathit{sig}sig such that

  • getSessionValues(ctx)\mathrm{getSessionValues}(ctx)getSessionValues(ctx) succeeds with svsvsv;
  • partialSigAgg(psig1,…,psigu; ctx)\mathrm{partialSigAgg}(\mathit{psig}_1, \dots, \mathit{psig}_u;\ ctx)partialSigAgg(psig1​,…,psigu​; ctx) succeeds with sig\mathit{sig}sig;
  • schnorrVerify(xbytes(Q), msg, sig)=true\mathrm{schnorrVerify}\big(\mathrm{xbytes}(Q),\ \mathit{msg},\ \mathit{sig}\big) = \text{true}schnorrVerify(xbytes(Q), msg, sig)=true.

Since both functions are deterministic, svsvsv is the output of getSessionValues(ctx)\mathrm{getSessionValues}(ctx)getSessionValues(ctx) and sig=xbytes(R)∥be32(s)\mathit{sig} = \mathrm{xbytes}(R) \Vert \mathrm{be32}(s)sig=xbytes(R)∥be32(s) with s=(∑ibeVal(psigi)+e g tacc) mod ns = \big(\sum_i \mathrm{beVal}(\mathit{psig}_i) + e\,g\,\mathit{tacc}\big) \bmod ns=(∑i​beVal(psigi​)+egtacc)modn as computed by partialSigAgg\mathrm{partialSigAgg}partialSigAgg. The verification key is the 323232-byte big-endian encoding be32(Qx)\mathrm{be32}(Q_x)be32(Qx​) of the first coordinate of the (tweaked) aggregate key QQQ held in the session values. All hypotheses concern only the public byte strings and the functions below; nothing is assumed about how the triples were produced.

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).

The Mathlib curve WWW and its point group W(Fp)W(\mathbb{F}_p)W(Fp​)

  • Fp\mathbb{F}_pFp​ denotes Mathlib's Z/pZ\mathbb{Z}/p\mathbb{Z}Z/pZ. For a natural number xxx, (x:Fp)(x : \mathbb{F}_p)(x:Fp​) is its residue x mod px \bmod pxmodp. The definition file registers, as a global instance, the fact that ppp is prime (proved there by a Lucas–Pratt certificate); this instance is what makes Z/pZ\mathbb{Z}/p\mathbb{Z}Z/pZ a field, which Mathlib needs to put a group structure on curve points.
  • WWW is the Weierstrass curve 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, i.e. the curve
y2=x3+7.y^2 = x^3 + 7 .y2=x3+7.
  • W(Fp)W(\mathbb{F}_p)W(Fp​) is Mathlib's type of points of WWW: a point is either the point at infinity, written 000, or an affine point (x,y)∈Fp2(x, y) \in \mathbb{F}_p^2(x,y)∈Fp2​ with y2=x3+7y^2 = x^3 + 7y2=x3+7 (carrying a proof that it is nonsingular). It is equipped with Mathlib's chord-and-tangent addition, which makes it an additive commutative group with neutral element 000 and negation −(x,y)=(x,−y)-(x, y) = (x, -y)−(x,y)=(x,−y), −0=0-0 = 0−0=0.
  • For k∈Nk \in \mathbb{N}k∈N and P∈W(Fp)P \in W(\mathbb{F}_p)P∈W(Fp​), k⋅P=P+⋯+Pk \cdot P = P + \dots + Pk⋅P=P+⋯+P (kkk summands, 0⋅P=00 \cdot P = 00⋅P=0). For k∈Zk \in \mathbb{Z}k∈Z, k⋅Pk \cdot Pk⋅P is the usual integer multiple (k⋅P=−(∣k∣⋅P)k \cdot P = -(|k|\cdot P)k⋅P=−(∣k∣⋅P) for k<0k<0k<0).
  • 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).

Executable points and their arithmetic

  • 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 powers and inversion. powMod(b,e,m)\mathrm{powMod}(b, e, m)powMod(b,e,m) is a square-and-multiply loop; the definition file proves powMod(b,e,m)=be mod m\mathrm{powMod}(b, e, m) = b^e \bmod mpowMod(b,e,m)=bemodm for all naturals b,e,mb, e, mb,e,m. The field inverse is 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​).

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}.

From executable points to Mathlib points

  • toPoint(P)\mathrm{toPoint}(P)toPoint(P) takes values in W(Fp)∪{fail}W(\mathbb{F}_p) \cup \{\mathsf{fail}\}W(Fp​)∪{fail} (an optional Mathlib point):
    • 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)∈W(Fp)\mathrm{toPoint}(x, y) = (x \bmod p,\ y \bmod p) \in W(\mathbb{F}_p)toPoint(x,y)=(xmodp, ymodp)∈W(Fp​) if onCurve(x,y)\mathrm{onCurve}(x, y)onCurve(x,y) holds;
    • toPoint(x,y)=fail\mathrm{toPoint}(x, y) = \mathsf{fail}toPoint(x,y)=fail otherwise.
  • tp(P)∈W(Fp)\mathrm{tp}(P) \in W(\mathbb{F}_p)tp(P)∈W(Fp​) is toPoint(P)\mathrm{toPoint}(P)toPoint(P) with fail\mathsf{fail}fail replaced by 000. Thus 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 tp(x,y)=0\mathrm{tp}(x, y) = 0tp(x,y)=0 for every off-curve pair (an off-curve pair has the same image as ∞\infty∞). Pairs differing by multiples of ppp in their coordinates have the same image.
  • Valid(P)\mathrm{Valid}(P)Valid(P) means: if PPP is a pair (x,y)(x, y)(x,y) then onCurve(x,y)\mathrm{onCurve}(x, y)onCurve(x,y) holds. ∞\infty∞ is Valid. Validity does not require reduced coordinates.
  • Reduced(P)\mathrm{Reduced}(P)Reduced(P) means: if PPP is a pair (x,y)(x, y)(x,y) then x<px < px<p and y<py < py<p. ∞\infty∞ is Reduced. Reducedness does not require being on the curve.

Byte strings, hashing and point encodings

  • A byte string is a finite list of bytes (values 0,…,2550, \dots, 2550,…,255). ∣b∣|b|∣b∣ is its length, ∥\Vert∥ is concatenation. takek(b)\mathrm{take}_k(b)takek​(b) is the first min⁡(k,∣b∣)\min(k, |b|)min(k,∣b∣) bytes of bbb and dropk(b)\mathrm{drop}_k(b)dropk​(b) is bbb with its first min⁡(k,∣b∣)\min(k, |b|)min(k,∣b∣) bytes removed, so a slice of a too-short string is silently shorter (possibly empty).
  • 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 is the big-endian value of bbb (any length; beVal\mathrm{beVal}beVal of the empty string is 000).
  • be32(x)\mathrm{be32}(x)be32(x) is the 323232-byte big-endian encoding of x mod 2256x \bmod 2^{256}xmod2256 (bits of xxx above 22562^{256}2256 are silently dropped).
  • For a pair P=(x,y)P = (x, y)P=(x,y) of naturals: xbytes(P)=be32(x)\mathrm{xbytes}(P) = \mathrm{be32}(x)xbytes(P)=be32(x); hasEvenY(P)\mathrm{hasEvenY}(P)hasEvenY(P) holds iff y mod 2=0y \bmod 2 = 0ymod2=0 (parity of the raw natural yyy, no reduction mod ppp); cbytes(P)=[c] ∥ be32(x)\mathrm{cbytes}(P) = [c] \,\Vert\, \mathrm{be32}(x)cbytes(P)=[c]∥be32(x), a 333333-byte string whose first byte ccc is 222 if hasEvenY(P)\mathrm{hasEvenY}(P)hasEvenY(P) and 333 otherwise.
  • zero33\mathrm{zero}_{33}zero33​ is the string of 333333 zero bytes. 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.
  • SHA256\mathrm{SHA256}SHA256 is the executable SHA-256 function of the serialization definition file. ascii(s)\mathrm{ascii}(s)ascii(s) is the UTF-8 byte string of a text string sss. The tagged hash is
tagged(s,m)=SHA256(SHA256(ascii(s)) ∥ SHA256(ascii(s)) ∥ m).\mathrm{tagged}(s, m) = \mathrm{SHA256}\big(\mathrm{SHA256}(\mathrm{ascii}(s)) \,\Vert\, \mathrm{SHA256}(\mathrm{ascii}(s)) \,\Vert\, m\big).tagged(s,m)=SHA256(SHA256(ascii(s))∥SHA256(ascii(s))∥m).

Parsing compressed points

  • liftXParity(x,odd)\mathrm{liftXParity}(x, \mathit{odd})liftXParity(x,odd) for a natural xxx and a requested parity: let y=(x3+7)(p+1)/4 mod py = (x^3 + 7)^{(p+1)/4} \bmod py=(x3+7)(p+1)/4modp (computed by powMod\mathrm{powMod}powMod; (p+1)/4(p+1)/4(p+1)/4 is 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∗) where y∗=yy^\ast = yy∗=y if the parity of yyy is the requested one and y∗=(p−y) mod py^\ast = (p - y) \bmod py∗=(p−y)modp otherwise (if y=0y = 0y=0 then y∗=0y^\ast = 0y∗=0 whatever parity was requested); if not, the result is a failure.
  • cpoint(b)\mathrm{cpoint}(b)cpoint(b) parses a byte string as a compressed point. If ∣b∣≠33|b| \neq 33∣b∣=33 it fails. If ∣b∣=33|b| = 33∣b∣=33, write b=[t]∥rb = [t] \Vert rb=[t]∥r with ∣r∣=32|r| = 32∣r∣=32: if t∉{2,3}t \notin \{2, 3\}t∈/{2,3} it fails; otherwise let x=beVal(r)x = \mathrm{beVal}(r)x=beVal(r); if x≥px \ge px≥p it fails, and if x<px < px<p the result is liftXParity(x,odd=(t=3))\mathrm{liftXParity}(x, \mathit{odd} = (t = 3))liftXParity(x,odd=(t=3)) (which may itself fail). A successful result is a pair (x,y)(x, y)(x,y) of naturals.
  • Important typing fact. The result of cpoint\mathrm{cpoint}cpoint has the same type as an executable point, and its failure value is literally the value ∞\infty∞. So wherever cpoint(b)\mathrm{cpoint}(b)cpoint(b) is used as an executable point, a parse failure is the point at infinity.
  • cpointExt(b)\mathrm{cpointExt}(b)cpointExt(b): if b=zero33b = \mathrm{zero}_{33}b=zero33​ the result is "success with ∞\infty∞"; otherwise it is "success with the pair cpoint(b)\mathrm{cpoint}(b)cpoint(b)" when cpoint(b)\mathrm{cpoint}(b)cpoint(b) succeeds, and failure when it fails. (Here failure and ∞\infty∞ are distinct outcomes.)

The MuSig2 (BIP327-style) algorithms of the definition file

Notation: aPaPaP for a natural aaa and an executable point PPP means pmul(a,P)\mathrm{pmul}(a, P)pmul(a,P); "fails" means the optional result is absent.

  • Key-aggregation context: a record (Q,gacc,tacc)(Q, \mathit{gacc}, \mathit{tacc})(Q,gacc,tacc) with Q=(Qx,Qy)Q = (Q_x, Q_y)Q=(Qx​,Qy​) a pair of naturals (never ∞\infty∞) and gacc,tacc\mathit{gacc}, \mathit{tacc}gacc,tacc naturals.
  • hashKeys(pk1,…,pku)=tagged("KeyAgg list", pk1∥⋯∥pku)\mathrm{hashKeys}(pk_1, \dots, pk_u) = \mathrm{tagged}(\text{"KeyAgg list"},\ pk_1 \Vert \cdots \Vert pk_u)hashKeys(pk1​,…,pku​)=tagged("KeyAgg list", pk1​∥⋯∥pku​).
  • getSecondKey(pks)\mathrm{getSecondKey}(pks)getSecondKey(pks): zero33\mathrm{zero}_{33}zero33​ if pkspkspks is empty; otherwise the first entry of pkspkspks (in list order) that differs from pk1pk_1pk1​, or zero33\mathrm{zero}_{33}zero33​ if every entry equals pk1pk_1pk1​.
  • keyAggCoeff(pks,pk)=1\mathrm{keyAggCoeff}(pks, pk) = 1keyAggCoeff(pks,pk)=1 if pk=getSecondKey(pks)pk = \mathrm{getSecondKey}(pks)pk=getSecondKey(pks), 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. (pkpkpk need not occur in pkspkspks.)
  • keyAggSum(pks,ℓ)\mathrm{keyAggSum}(pks, \ell)keyAggSum(pks,ℓ) for a list ℓ\ellℓ of byte strings: for ℓ\ellℓ empty it succeeds with ∞\infty∞; for ℓ=pk::rest\ell = pk :: \mathit{rest}ℓ=pk::rest it succeeds with padd(pmul(keyAggCoeff(pks,pk),cpoint(pk)), acc)\mathrm{padd}\big(\mathrm{pmul}(\mathrm{keyAggCoeff}(pks, pk), \mathrm{cpoint}(pk)),\ \mathit{acc}\big)padd(pmul(keyAggCoeff(pks,pk),cpoint(pk)), acc) provided cpoint(pk)\mathrm{cpoint}(pk)cpoint(pk) succeeds 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 parsed points PiP_iPi​ and coefficients 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}\big(a_1P_1,\ \mathrm{padd}(a_2P_2,\ \dots\ \mathrm{padd}(a_uP_u, \infty)\cdots)\big).padd(a1​P1​, padd(a2​P2​, … padd(au​Pu​,∞)⋯)).
  • keyAgg(pks)\mathrm{keyAgg}(pks)keyAgg(pks): if keyAggSum(pks,pks)\mathrm{keyAggSum}(pks, pks)keyAggSum(pks,pks) succeeds with a pair QQQ, the result is the context (Q,1,0)(Q, 1, 0)(Q,1,0); it fails if some key does not parse or the sum is ∞\infty∞ (in particular it fails for the empty list).
  • applyTweak(ctx,tweak,isXonly)\mathrm{applyTweak}(ctx, \mathit{tweak}, \mathit{isXonly})applyTweak(ctx,tweak,isXonly) with ctx=(Q,gacc,tacc)ctx = (Q, \mathit{gacc}, \mathit{tacc})ctx=(Q,gacc,tacc): let g=n−1g = n - 1g=n−1 if isXonly\mathit{isXonly}isXonly is true and hasEvenY(Q)\mathrm{hasEvenY}(Q)hasEvenY(Q) is false, else g=1g = 1g=1; let t=beVal(tweak)t = \mathrm{beVal}(\mathit{tweak})t=beVal(tweak) (the length of tweak\mathit{tweak}tweak is not checked). If t≥nt \ge nt≥n it fails. Otherwise let Q′=padd(gQ,tG)Q' = \mathrm{padd}(gQ, tG)Q′=padd(gQ,tG); if Q′=∞Q' = \inftyQ′=∞ it fails, else the result is (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(ctx,[(tw1,x1),…,(twv,xv)])\mathrm{applyTweaks}(ctx, [(tw_1, x_1), \dots, (tw_v, x_v)])applyTweaks(ctx,[(tw1​,x1​),…,(twv​,xv​)]) applies applyTweak\mathrm{applyTweak}applyTweak with (tw1,x1)(tw_1, x_1)(tw1​,x1​), then (tw2,x2)(tw_2, x_2)(tw2​,x2​), etc., failing as soon as one step fails; with no tweaks it returns ctxctxctx.
  • keyAggTweaked(pks,tweaks)\mathrm{keyAggTweaked}(pks, \mathit{tweaks})keyAggTweaked(pks,tweaks): keyAgg(pks)\mathrm{keyAgg}(pks)keyAgg(pks) followed by applyTweaks\mathrm{applyTweaks}applyTweaks; fails if either fails.
  • nonceSum(j,ℓ)\mathrm{nonceSum}(j, \ell)nonceSum(j,ℓ) for j∈Nj \in \mathbb{N}j∈N and a list ℓ\ellℓ of byte strings: 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) provided R=cpoint(take33(drop33j(pn)))R = \mathrm{cpoint}(\mathrm{take}_{33}(\mathrm{drop}_{33j}(pn)))R=cpoint(take33​(drop33j​(pn))) succeeds (a pair; an individual nonce half can never be ∞\infty∞) and nonceSum(j,rest)\mathrm{nonceSum}(j, \mathit{rest})nonceSum(j,rest) succeeds with acc\mathit{acc}acc, and fails otherwise. The total length of each 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.
  • nonceAgg(pn1,…,pnu)\mathrm{nonceAgg}(pn_1, \dots, pn_u)nonceAgg(pn1​,…,pnu​): 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 it is zero33∥zero33\mathrm{zero}_{33} \Vert \mathrm{zero}_{33}zero33​∥zero33​.
  • Session context ctxctxctx: a record of a byte string aggnonce\mathit{aggnonce}aggnonce, a list pkspkspks of byte strings, a list tweaks\mathit{tweaks}tweaks of (byte string, boolean) pairs, and a byte string msg\mathit{msg}msg. No constraint relates the fields.
  • Session values: 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) where QQQ and RRR are pairs of naturals, R′R'R′ is an executable point, and gacc,tacc,b,e\mathit{gacc}, \mathit{tacc}, b, egacc,tacc,b,e are naturals.
  • getSessionValues(ctx)\mathrm{getSessionValues}(ctx)getSessionValues(ctx):
    1. Compute keyAggTweaked(pks,tweaks)\mathrm{keyAggTweaked}(pks, \mathit{tweaks})keyAggTweaked(pks,tweaks); if it fails, fail; else call the result (Q,gacc,tacc)(Q, \mathit{gacc}, \mathit{tacc})(Q,gacc,tacc).
    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 (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∞ (when its slice is zero33\mathrm{zero}_{33}zero33​) or a parsed pair.
    4. R′=padd(R1,pmul(b,R2))R' = \mathrm{padd}(R_1, \mathrm{pmul}(b, R_2))R′=padd(R1​,pmul(b,R2​)).
    5. R=(Gx,Gy)R = (G_x, G_y)R=(Gx​,Gy​) if R′=∞R' = \inftyR′=∞, otherwise R=R′R = R'R=R′.
    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(psig,pubnonce,pk,ctx)\mathrm{partialSigVerifyInternal}(\mathit{psig}, \mathit{pubnonce}, pk, ctx)partialSigVerifyInternal(psig,pubnonce,pk,ctx) is a boolean:
    1. If getSessionValues(ctx)\mathrm{getSessionValues}(ctx)getSessionValues(ctx) fails, false; otherwise use its values (Q,gacc,tacc,b,R′,R,e)(Q, \mathit{gacc}, \mathit{tacc}, b, R', R, e)(Q,gacc,tacc,b,R′,R,e).
    2. Let 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. Let 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 the three fails, false.
    4. If pkpkpk is not an entry of pkspkspks, false.
    5. Re′=padd(R1,pmul(b,R2))R_e' = \mathrm{padd}(R_1, \mathrm{pmul}(b, R_2))Re′​=padd(R1​,pmul(b,R2​)); Re=Re′R_e = R_e'Re​=Re′​ if hasEvenY(R)\mathrm{hasEvenY}(R)hasEvenY(R), else 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), else 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)andpadd(Re, pmul((e⋅a⋅g′) mod n, P))\mathrm{pmul}(s, G) \quad\text{and}\quad \mathrm{padd}\big(R_e,\ \mathrm{pmul}((e \cdot a \cdot g') \bmod n,\ P)\big)pmul(s,G)andpadd(Re​, pmul((e⋅a⋅g′)modn, P))

are literally equal.

  • partialSigAgg(psig1,…,psigu;ctx)\mathrm{partialSigAgg}(\mathit{psig}_1, \dots, \mathit{psig}_u; ctx)partialSigAgg(psig1​,…,psigu​;ctx):
    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), else g=n−1g = n - 1g=n−1.
    4. s=(∑ibeVal(psigi)+e⋅g⋅tacc) mod ns = \big(\sum_i \mathrm{beVal}(\mathit{psig}_i) + e \cdot g \cdot \mathit{tacc}\big) \bmod ns=(∑i​beVal(psigi​)+e⋅g⋅tacc)modn (empty sum =0= 0=0).
    5. Succeed with the 646464-byte string xbytes(R)∥be32(s)\mathrm{xbytes}(R) \Vert \mathrm{be32}(s)xbytes(R)∥be32(s).

BIP340-style Schnorr verification

  • liftX(x)\mathrm{liftX}(x)liftX(x): if x<px < px<p it is liftXParity(x,even)\mathrm{liftXParity}(x, \text{even})liftXParity(x,even), otherwise it fails.
  • schnorrVerify(pk32,msg,sig)\mathrm{schnorrVerify}(pk_{32}, \mathit{msg}, \mathit{sig})schnorrVerify(pk32​,msg,sig) is a boolean:
    1. If ∣pk32∣≠32|pk_{32}| \neq 32∣pk32​∣=32 or ∣sig∣≠64|\mathit{sig}| \neq 64∣sig∣=64, false.
    2. r=beVal(first 32 bytes of sig)r = \mathrm{beVal}(\text{first 32 bytes of } \mathit{sig})r=beVal(first 32 bytes of sig), s=beVal(last 32 bytes of sig)s = \mathrm{beVal}(\text{last 32 bytes of } \mathit{sig})s=beVal(last 32 bytes of sig). If r≥pr \ge pr≥p or s≥ns \ge ns≥n, false.
    3. P=liftX(beVal(pk32))P = \mathrm{liftX}(\mathrm{beVal}(pk_{32}))P=liftX(beVal(pk32​)); if it fails, false.
    4. e=beVal(tagged("BIP0340/challenge", take32(sig)∥pk32∥msg)) mod ne = \mathrm{beVal}\big(\mathrm{tagged}(\text{"BIP0340/challenge"},\ \mathrm{take}_{32}(\mathit{sig}) \Vert pk_{32} \Vert \mathit{msg})\big) \bmod ne=beVal(tagged("BIP0340/challenge", take32​(sig)∥pk32​∥msg))modn.
    5. T=padd(pmul(s,G), pmul((n−e) mod n, P))T = \mathrm{padd}\big(\mathrm{pmul}(s, G),\ \mathrm{pmul}((n - e) \bmod n,\ P)\big)T=padd(pmul(s,G), pmul((n−e)modn, P)). If T=∞T = \inftyT=∞, false; if T=(tx,ty)T = (t_x, t_y)T=(tx​,ty​), the result is true iff tyt_yty​ is even and tx=rt_x = rtx​=r.
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