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) 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)]
be a list of triples of byte strings (a partial signature, a public nonce, a public key; repetitions allowed). Assume all of the following.
- Non-empty: u≥1.
- Keys match: pks=[pk1,…,pku] exactly (same entries, same order, same multiplicities).
- Key torsion: for every entry pk of pks, n⋅tp(cpoint(pk))=0 in the group W(Fp). Here cpoint(pk) is used as an executable point, so a key that fails to parse contributes the value ∞, for which tp(∞)=0 and the condition holds automatically; for a key parsing to (x,y), tp(x,y) is the point (xmodp,ymodp) of W(Fp) if onCurve(x,y) and 0 otherwise, and n⋅(⋅) is the n-fold sum.
- Aggregate nonce: nonceAgg(pn1,…,pnu) succeeds and is exactly the byte string aggnonce.
- Every partial signature verifies: for each i=1,…,u, partialSigVerifyInternal(psigi,pni,pki,ctx)=true.
- Non-degenerate nonce: for every session-values record sv, if getSessionValues(ctx) succeeds with sv then its raw aggregate nonce R′ is not ∞. (This quantifies over all records, but only the actual output of the deterministic function getSessionValues(ctx) is constrained; the hypothesis would hold vacuously if getSessionValues(ctx) failed, although hypothesis 5 with u≥1 already requires it to succeed, since partialSigVerifyInternal returns false when it fails.)
Conclusion. There exist a session-values record sv=(Q,gacc,tacc,b,R′,R,e) and a byte string sig such that
- getSessionValues(ctx) succeeds with sv;
- partialSigAgg(psig1,…,psigu; ctx) succeeds with sig;
- schnorrVerify(xbytes(Q), msg, sig)=true.
Since both functions are deterministic, sv is the output of getSessionValues(ctx) and sig=xbytes(R)∥be32(s) with s=(∑ibeVal(psigi)+egtacc)modn as computed by partialSigAgg. The verification key is the 32-byte big-endian encoding be32(Qx) of the first coordinate of the (tweaked) aggregate key Q 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−977 is a fixed natural number (the field modulus).
- n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 is a fixed natural number (written in hexadecimal).
- Gx=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 and Gy=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 are fixed natural numbers (Gy is even: its last hexadecimal digit is 8).
The Mathlib curve W and its point group W(Fp)
- Fp denotes Mathlib's Z/pZ. For a natural number x, (x:Fp) is its residue xmodp. The definition file registers, as a global instance, the fact that p is prime (proved there by a Lucas–Pratt certificate); this instance is what makes Z/pZ a field, which Mathlib needs to put a group structure on curve points.
- W is the Weierstrass curve over Fp with coefficients a1=a2=a3=a4=0 and a6=7, i.e. the curve
y2=x3+7.
- W(Fp) is Mathlib's type of points of W: a point is either the point at infinity, written 0, or an affine point (x,y)∈Fp2 with y2=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 0 and negation −(x,y)=(x,−y), −0=0.
- For k∈N and P∈W(Fp), k⋅P=P+⋯+P (k summands, 0⋅P=0). For k∈Z, k⋅P is the usual integer multiple (k⋅P=−(∣k∣⋅P) for k<0).
- Gpt∈W(Fp) is the affine point (Gxmodp, Gymodp).
Executable points and their arithmetic
- 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 (x,y) of natural numbers of arbitrary size. Nothing in the type requires x,y<p or that the pair lies on the curve. Equality of executable points is literal equality: both ∞, or equal pairs of natural numbers (so (x,y) and (x+p,y) are different executable points).
- Curve test. For naturals x,y: onCurve(x,y) holds iff
(y⋅y)modp=(x⋅x⋅x+7)modp,
i.e. y2≡x3+7(modp). Pairs with unreduced coordinates (x≥p or y≥p) can pass this test.
- Modular powers and inversion. powMod(b,e,m) is a square-and-multiply loop; the definition file proves powMod(b,e,m)=bemodm for all naturals b,e,m. The field inverse is finv(a)=ap−2modp; in particular finv(a)=0 when p∣a.
- Addition padd(P,Q):
- padd(∞,Q)=Q and padd(P,∞)=P, returned unchanged (unreduced coordinates stay unreduced).
- For P=(x1,y1), Q=(x2,y2) with x1≡x2(modp):
- if y1+y2≡0(modp) the result is ∞;
- otherwise (tangent branch, which uses only x1,y1):
λ=(3x12⋅finv(2y1modp))modp,x3=(λ2+2(p−x1modp))modp,
y3=(λ⋅((x1+p−x3)modp)+(p−y1modp))modp,
and the result is $(x_3, y_3)$.
- For P=(x1,y1), Q=(x2,y2) with x1≡x2(modp) (chord branch):
λ=(((y2+p−y1modp)modp)⋅finv((x2+p−x1modp)modp))modp,
x3=(λ2+(p−x1modp)+(p−x2modp))modp,y3=(λ⋅((x1+p−x3)modp)+(p−y1modp))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 ∞ or a pair with both coordinates <p.
- Scalar multiplication pmul(k,P) for k∈N: a least-significant-bit-first double-and-add loop with a fuel of exactly 257 iterations. Starting from (k,P,acc=∞), each iteration does: if k=0, stop and return acc; otherwise replace acc by padd(acc,P) if k is odd (else keep it), then replace P by padd(P,P) and k by ⌊k/2⌋. When the 257 iterations are exhausted the current acc is returned. Consequently only the 257 lowest bits of k are ever used: pmul(k,P)=pmul(kmod2257,P). Also pmul(0,P)=∞ and pmul(k,∞)=∞.
- G denotes the executable point (Gx,Gy).
Executable negation
- pneg(∞)=∞ and 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 in {0,…,p−1}.
From executable points to Mathlib points
- toPoint(P) takes values in W(Fp)∪{fail} (an optional Mathlib point):
- toPoint(∞)=0, the Mathlib point at infinity (a genuine point, not fail);
- toPoint(x,y)=(xmodp, ymodp)∈W(Fp) if onCurve(x,y) holds;
- toPoint(x,y)=fail otherwise.
- tp(P)∈W(Fp) is toPoint(P) with fail replaced by 0. Thus tp(∞)=0, tp(x,y)=(xmodp,ymodp) for on-curve pairs, and tp(x,y)=0 for every off-curve pair (an off-curve pair has the same image as ∞). Pairs differing by multiples of p in their coordinates have the same image.
- Valid(P) means: if P is a pair (x,y) then onCurve(x,y) holds. ∞ is Valid. Validity does not require reduced coordinates.
- Reduced(P) means: if P is a pair (x,y) then x<p and y<p. ∞ 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,…,255). ∣b∣ is its length, ∥ is concatenation. takek(b) is the first min(k,∣b∣) bytes of b and dropk(b) is b with its first min(k,∣b∣) bytes removed, so a slice of a too-short string is silently shorter (possibly empty).
- beVal(b)=∑i=0∣b∣−1bi256∣b∣−1−i is the big-endian value of b (any length; beVal of the empty string is 0).
- be32(x) is the 32-byte big-endian encoding of xmod2256 (bits of x above 2256 are silently dropped).
- For a pair P=(x,y) of naturals: xbytes(P)=be32(x); hasEvenY(P) holds iff ymod2=0 (parity of the raw natural y, no reduction mod p); cbytes(P)=[c]∥be32(x), a 33-byte string whose first byte c is 2 if hasEvenY(P) and 3 otherwise.
- zero33 is the string of 33 zero bytes. cbytesExt(∞)=zero33 and cbytesExt(P)=cbytes(P) for a pair P.
- SHA256 is the executable SHA-256 function of the serialization definition file. ascii(s) is the UTF-8 byte string of a text string s. The tagged hash is
tagged(s,m)=SHA256(SHA256(ascii(s))∥SHA256(ascii(s))∥m).
Parsing compressed points
- liftXParity(x,odd) for a natural x and a requested parity: let y=(x3+7)(p+1)/4modp (computed by powMod; (p+1)/4 is natural-number division). If y2modp=(x3+7)modp, the result is the pair (x,y∗) where y∗=y if the parity of y is the requested one and y∗=(p−y)modp otherwise (if y=0 then y∗=0 whatever parity was requested); if not, the result is a failure.
- cpoint(b) parses a byte string as a compressed point. If ∣b∣=33 it fails. If ∣b∣=33, write b=[t]∥r with ∣r∣=32: if t∈/{2,3} it fails; otherwise let x=beVal(r); if x≥p it fails, and if x<p the result is liftXParity(x,odd=(t=3)) (which may itself fail). A successful result is a pair (x,y) of naturals.
- Important typing fact. The result of cpoint has the same type as an executable point, and its failure value is literally the value ∞. So wherever cpoint(b) is used as an executable point, a parse failure is the point at infinity.
- cpointExt(b): if b=zero33 the result is "success with ∞"; otherwise it is "success with the pair cpoint(b)" when cpoint(b) succeeds, and failure when it fails. (Here failure and ∞ are distinct outcomes.)
The MuSig2 (BIP327-style) algorithms of the definition file
Notation: aP for a natural a and an executable point P means pmul(a,P); "fails" means the optional result is absent.
- Key-aggregation context: a record (Q,gacc,tacc) with Q=(Qx,Qy) a pair of naturals (never ∞) and gacc,tacc naturals.
- hashKeys(pk1,…,pku)=tagged("KeyAgg list", pk1∥⋯∥pku).
- getSecondKey(pks): zero33 if pks is empty; otherwise the first entry of pks (in list order) that differs from pk1, or zero33 if every entry equals pk1.
- keyAggCoeff(pks,pk)=1 if pk=getSecondKey(pks), and otherwise beVal(tagged("KeyAgg coefficient", hashKeys(pks)∥pk))modn. (pk need not occur in pks.)
- keyAggSum(pks,ℓ) for a list ℓ of byte strings: for ℓ empty it succeeds with ∞; for ℓ=pk::rest it succeeds with padd(pmul(keyAggCoeff(pks,pk),cpoint(pk)), acc) provided cpoint(pk) succeeds and keyAggSum(pks,rest) succeeds with acc, and fails otherwise. For ℓ=(pk1,…,pku) with parsed points Pi and coefficients ai=keyAggCoeff(pks,pki) this is the right-nested sum
padd(a1P1, padd(a2P2, … padd(auPu,∞)⋯)).
- keyAgg(pks): if keyAggSum(pks,pks) succeeds with a pair Q, the result is the context (Q,1,0); it fails if some key does not parse or the sum is ∞ (in particular it fails for the empty list).
- applyTweak(ctx,tweak,isXonly) with ctx=(Q,gacc,tacc): let g=n−1 if isXonly is true and hasEvenY(Q) is false, else g=1; let t=beVal(tweak) (the length of tweak is not checked). If t≥n it fails. Otherwise let Q′=padd(gQ,tG); if Q′=∞ it fails, else the result is (Q′, (g⋅gacc)modn, (t+g⋅tacc)modn).
- applyTweaks(ctx,[(tw1,x1),…,(twv,xv)]) applies applyTweak with (tw1,x1), then (tw2,x2), etc., failing as soon as one step fails; with no tweaks it returns ctx.
- keyAggTweaked(pks,tweaks): keyAgg(pks) followed by applyTweaks; fails if either fails.
- nonceSum(j,ℓ) for j∈N and a list ℓ of byte strings: for ℓ empty it succeeds with ∞; for ℓ=pn::rest it succeeds with padd(R,acc) provided R=cpoint(take33(drop33j(pn))) succeeds (a pair; an individual nonce half can never be ∞) and nonceSum(j,rest) succeeds with acc, and fails otherwise. The total length of each pn is not checked; for j=0 its first 33 bytes are used, for j=1 its bytes 33 to 65.
- nonceAgg(pn1,…,pnu): if nonceSum(0,⋅) succeeds with R1 and nonceSum(1,⋅) succeeds with R2, the result is the 66-byte string cbytesExt(R1)∥cbytesExt(R2); otherwise it fails. For the empty list it is zero33∥zero33.
- Session context ctx: a record of a byte string aggnonce, a list pks of byte strings, a list tweaks of (byte string, boolean) pairs, and a byte string msg. No constraint relates the fields.
- Session values: a record (Q,gacc,tacc,b,R′,R,e) where Q and R are pairs of naturals, R′ is an executable point, and gacc,tacc,b,e are naturals.
- getSessionValues(ctx):
- Compute keyAggTweaked(pks,tweaks); if it fails, fail; else call the result (Q,gacc,tacc).
- b=beVal(tagged("MuSig/noncecoef", aggnonce∥xbytes(Q)∥msg))modn (the whole aggnonce, whatever its length).
- R1=cpointExt(take33(aggnonce)) and R2=cpointExt(take33(drop33(aggnonce))); if either fails, fail. Each is ∞ (when its slice is zero33) or a parsed pair.
- R′=padd(R1,pmul(b,R2)).
- R=(Gx,Gy) if R′=∞, otherwise R=R′.
- e=beVal(tagged("BIP0340/challenge", xbytes(R)∥xbytes(Q)∥msg))modn.
- Succeed with (Q,gacc,tacc,b,R′,R,e).
- partialSigVerifyInternal(psig,pubnonce,pk,ctx) is a boolean:
- If getSessionValues(ctx) fails, false; otherwise use its values (Q,gacc,tacc,b,R′,R,e).
- Let s=beVal(psig). If ∣psig∣=32 or s≥n, false.
- Let R1=cpoint(take33(pubnonce)), R2=cpoint(take33(drop33(pubnonce))), P=cpoint(pk); if any of the three fails, false.
- If pk is not an entry of pks, false.
- Re′=padd(R1,pmul(b,R2)); Re=Re′ if hasEvenY(R), else Re=pneg(Re′).
- a=keyAggCoeff(pks,pk); g=1 if hasEvenY(Q), else g=n−1; g′=(g⋅gacc)modn.
- The result is true iff the executable points
pmul(s,G)andpadd(Re, pmul((e⋅a⋅g′)modn, P))
are literally equal.
- partialSigAgg(psig1,…,psigu;ctx):
- If getSessionValues(ctx) fails, fail; otherwise use its values.
- If some psigi has ∣psigi∣=32 or beVal(psigi)≥n, fail.
- g=1 if hasEvenY(Q), else g=n−1.
- s=(∑ibeVal(psigi)+e⋅g⋅tacc)modn (empty sum =0).
- Succeed with the 64-byte string xbytes(R)∥be32(s).
BIP340-style Schnorr verification
- liftX(x): if x<p it is liftXParity(x,even), otherwise it fails.
- schnorrVerify(pk32,msg,sig) is a boolean:
- If ∣pk32∣=32 or ∣sig∣=64, false.
- r=beVal(first 32 bytes of sig), s=beVal(last 32 bytes of sig). If r≥p or s≥n, false.
- P=liftX(beVal(pk32)); if it fails, false.
- e=beVal(tagged("BIP0340/challenge", take32(sig)∥pk32∥msg))modn.
- T=padd(pmul(s,G), pmul((n−e)modn, P)). If T=∞, false; if T=(tx,ty), the result is true iff ty is even and tx=r.
Confirmed by the moderator at approval.