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.padd_comm
Source file: Thm_BitcoinMuSig_padd_comm.lean (one theorem; it builds on the MuSig definition file, which itself uses the secp256k1 signature and Taproot definition files).
Statement. For all executable points P,Q that are Valid (each is ∞, or a pair (x,y) of naturals with y2≡x3+7(modp); coordinates are not required to be below p), the executable addition is commutative as a literal equality of executable points:
padd(P,Q)=padd(Q,P).
(Both sides are ∞ or the same pair of natural numbers; if one argument is ∞, each side returns the other argument unchanged.)
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).
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.
Confirmed by the moderator at approval.