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.cpoint_cbytes
Source file: Thm_BitcoinMuSig_cpoint_cbytes.lean (one theorem; it builds on the MuSig definition file, which itself uses the secp256k1 signature and Taproot definition files).
Statement. For every pair P=(x,y) of natural numbers such that
- onCurve(x,y) holds, i.e. y2≡x3+7(modp),
- x<p, and
- y<p,
parsing the 33-byte compressed encoding of P succeeds and returns P itself:
cpoint(cbytes(x,y))=(x,y)(a successful parse, not a failure).
Here cbytes(x,y)=[2 if y even, else 3]∥be32(x), so the claim is that liftXParity(x,odd=(y odd)) returns exactly (x,y) (the length check and the check beVal(be32(x))=x<p being part of the parse). Pairs with x≥p or y≥p are not covered.
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).
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).
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.)
Confirmed by the moderator at approval.