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.tp_G
Source file: Thm_BitcoinMuSig_tp_G.lean (one theorem; it builds on the MuSig definition file, which itself uses the secp256k1 signature and Taproot definition files).
Statement. There are no variables and no hypotheses. The total conversion of the executable generator G=(Gx,Gy) is the Mathlib point Gpt:
tp(G)=Gpt.
Unfolded: tp(Gx,Gy) is (Gxmodp,Gymodp)∈W(Fp) if onCurve(Gx,Gy) holds and 0 otherwise, and Gpt is the affine point (Gxmodp,Gymodp) of W(Fp).
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.