zzstoatzz.io
this repo has no description
1const std = @import("std");
2const Secp256k1 = std.crypto.ecc.Secp256k1;
3const Fe = @import("field.zig").Fe;
4const StdFe = Secp256k1.Fe;
5const StdAffineCoordinates = @TypeOf(Secp256k1.basePoint.affineCoordinates());
6
7/// Affine point in Fe representation.
8pub const AffinePoint = struct {
9 x: Fe,
10 y: Fe,
11
12 pub const identity: AffinePoint = .{ .x = Fe.zero, .y = Fe.zero };
13
14 pub fn neg(self: AffinePoint) AffinePoint {
15 return .{ .x = self.x, .y = self.y.neg(1) };
16 }
17
18 pub fn fromStdlib(ac: StdAffineCoordinates) AffinePoint {
19 return .{
20 .x = Fe.fromBytes(ac.x.toBytes(.big), .big),
21 .y = Fe.fromBytes(ac.y.toBytes(.big), .big),
22 };
23 }
24
25 pub fn fromStdlibIdentity(ac: StdAffineCoordinates) AffinePoint {
26 // check if this is the identity element (x=0, y=0 in stdlib)
27 if (ac.x.isZero() and ac.y.isZero()) return identity;
28 return fromStdlib(ac);
29 }
30};
31
32/// Jacobian point on secp256k1 using Fe: affine (X/Z², Y/Z³).
33/// Uses a=0 specialized formulas for fewer field operations than
34/// the stdlib's complete projective formulas.
35pub const JacobianPoint = struct {
36 x: Fe,
37 y: Fe,
38 z: Fe,
39
40 pub const identity: JacobianPoint = .{ .x = Fe.zero, .y = Fe.one, .z = Fe.zero };
41
42 /// Convert Fe affine (x, y) to Jacobian (x, y, 1).
43 pub fn fromAffine(p: AffinePoint) JacobianPoint {
44 return .{ .x = p.x, .y = p.y, .z = Fe.one };
45 }
46
47 /// Convert stdlib affine to Jacobian via Fe.
48 pub fn fromStdlibAffine(ac: StdAffineCoordinates) JacobianPoint {
49 return fromAffine(AffinePoint.fromStdlib(ac));
50 }
51
52 /// Doubling for a=0 curves (secp256k1). 2M + 5S + 3 normalize.
53 /// EFD dbl-2009-l with a=0 specialization.
54 pub fn dbl(self: JacobianPoint) JacobianPoint {
55 if (self.z.isZero()) return self;
56
57 const a = self.x.sq(); // mag 1
58 const b = self.y.sq(); // mag 1
59 const c = b.sq(); // mag 1
60 const xb = self.x.add(b); // mag 2
61 const d = xb.sq().subMag(a, 1).subMag(c, 1).dbl().normalize();
62 const e = a.dbl().add(a); // 3a = mag 3
63 const f = e.sq();
64 const x3 = f.subMag(d.dbl(), 2).normalize();
65 const c8 = c.dbl().dbl().dbl(); // mag 8
66 const y3 = e.mul(d.subMag(x3, 1)).subMag(c8, 8).normalize();
67 const z3 = self.y.mul(self.z).dbl(); // mag 2
68
69 return .{ .x = x3, .y = y3, .z = z3 };
70 }
71
72 /// Mixed addition: Jacobian + Affine → Jacobian. 7M + 4S + 4 normalize.
73 /// EFD madd-2007-bl. Falls back to dbl() when both points are equal.
74 pub fn addMixed(self: JacobianPoint, q: AffinePoint) JacobianPoint {
75 if (self.z.isZero()) return fromAffine(q);
76
77 const z1z1 = self.z.sq(); // mag 1
78 const qx_z2 = q.x.mul(z1z1); // mag 1
79 const s2 = q.y.mul(self.z.mul(z1z1)); // mag 1
80 const h = qx_z2.subMag(self.x, 1).normalize();
81
82 // Degenerate case: same x-coordinate
83 if (h.isZero()) {
84 if (s2.subMag(self.y, 1).normalize().isZero()) return self.dbl();
85 return identity;
86 }
87
88 const hh = h.sq();
89 const i = hh.dbl().dbl(); // mag 4
90 const j = h.mul(i);
91 const r = s2.subMag(self.y, 1).dbl().normalize();
92 const v = self.x.mul(i);
93 const x3 = r.sq().subMag(j, 1).subMag(v.dbl(), 2).normalize();
94 const y3 = r.mul(v.subMag(x3, 1)).subMag(self.y.mul(j).dbl(), 2).normalize();
95 const z3 = self.z.add(h).sq().subMag(z1z1, 1).subMag(hh, 1);
96
97 return .{ .x = x3, .y = y3, .z = z3 };
98 }
99
100 /// Mixed subtraction: Jacobian - Affine → Jacobian.
101 pub fn subMixed(self: JacobianPoint, q: AffinePoint) JacobianPoint {
102 return self.addMixed(q.neg());
103 }
104
105 /// Negate the Y coordinate: returns (X, -Y, Z).
106 pub fn negY(self: JacobianPoint) JacobianPoint {
107 return .{ .x = self.x, .y = self.y.normalize().neg(1), .z = self.z };
108 }
109
110 /// Full Jacobian addition: J + J → J. ~12M + 4S.
111 /// Needed for combining r1 + r2 at end of verify.
112 pub fn add(self: JacobianPoint, other: JacobianPoint) JacobianPoint {
113 if (self.z.isZero()) return other;
114 if (other.z.isZero()) return self;
115
116 const z1z1 = self.z.sq();
117 const z2z2 = other.z.sq();
118 const p1 = self.x.mul(z2z2); // X1*Z2²
119 const p2 = other.x.mul(z1z1); // X2*Z1²
120 const s1 = self.y.mul(other.z.mul(z2z2)); // Y1*Z2³
121 const s2 = other.y.mul(self.z.mul(z1z1)); // Y2*Z1³
122
123 // h = p2 - p1 ; both mag 1
124 const h = p2.subMag(p1, 1).normalize();
125 const r = s2.subMag(s1, 1).normalize();
126
127 // check for doubling case (h == 0 && r == 0)
128 if (h.isZero()) {
129 if (r.isZero()) return self.dbl();
130 return identity;
131 }
132
133 const hh = h.sq(); // mag 1
134 const hhh = h.mul(hh); // mag 1
135 const v = p1.mul(hh); // mag 1
136 const r2 = r.sq(); // mag 1
137 // x3 = r² - hhh - 2v ; sub(1)=3, sub(2v=2, 2)=6
138 const x3 = r2.subMag(hhh, 1).subMag(v.dbl(), 2).normalize();
139 // y3 = r*(v-x3) - s1*hhh ; v.sub(x3,1)→3, mul=1; s1.mul(hhh)=1; sub(1)=3
140 const y3 = r.mul(v.subMag(x3, 1)).subMag(s1.mul(hhh), 1).normalize();
141 const z3 = self.z.mul(other.z).mul(h); // mag 1
142
143 return .{ .x = x3, .y = y3, .z = z3 };
144 }
145
146 /// Compare signature r against R's x-coordinate in Jacobian space.
147 /// Checks r * Z² == X (mod p), avoiding field inversion.
148 /// Returns true if the x-coordinates match.
149 pub fn jacobianCompare(self: JacobianPoint, r_fe: Fe) bool {
150 // Jacobian: x_affine = X / Z²
151 // So check: r * Z² == X
152 const z2 = self.z.sq();
153 const rz2 = r_fe.mul(z2);
154 if (rz2.equivalent(self.x)) return true;
155
156 // rare overflow case: x_affine could be in [n, p)
157 // check (r + n) * Z² == X
158 const n_fe26 = comptime Fe.fromInt(Secp256k1.scalar.field_order);
159 const p_minus_n: u256 = StdFe.field_order - Secp256k1.scalar.field_order;
160 const r_norm = r_fe.normalize();
161 const r_bytes = r_norm.toBytes(.big);
162 const r_int = std.mem.readInt(u256, &r_bytes, .big);
163 if (r_int < p_minus_n) {
164 const rn_z2 = r_fe.add(n_fe26).mul(z2);
165 if (rn_z2.equivalent(self.x)) return true;
166 }
167
168 return false;
169 }
170
171 /// Convert to stdlib projective for backward compatibility.
172 /// Jacobian: x = X/Z², y = Y/Z³. Projective: x = X'/Z', y = Y'/Z'.
173 /// Set X' = X*Z, Y' = Y, Z' = Z³.
174 pub fn toProjective(self: JacobianPoint) Secp256k1 {
175 if (self.z.isZero()) return Secp256k1.identityElement;
176 return .{
177 .x = self.x.mul(self.z).toStdlib(),
178 .y = self.y.toStdlib(),
179 .z = self.z.sq().mul(self.z).toStdlib(),
180 };
181 }
182};
183
184// ============================================================
185// tests — verify Fe Jacobian matches stdlib results
186// ============================================================
187
188fn toStdlibAffine(j: JacobianPoint) StdAffineCoordinates {
189 return j.toProjective().affineCoordinates();
190}
191
192test "dbl matches stdlib" {
193 const G = Secp256k1.basePoint;
194 const g_affine = G.affineCoordinates();
195
196 const j_2g = JacobianPoint.fromStdlibAffine(g_affine).dbl();
197 const j_2g_affine = toStdlibAffine(j_2g);
198
199 const stdlib_2g_affine = G.dbl().affineCoordinates();
200
201 try std.testing.expect(j_2g_affine.x.equivalent(stdlib_2g_affine.x));
202 try std.testing.expect(j_2g_affine.y.equivalent(stdlib_2g_affine.y));
203}
204
205test "addMixed matches stdlib add" {
206 const G = Secp256k1.basePoint;
207 const g_affine = G.affineCoordinates();
208 const g26 = AffinePoint.fromStdlib(g_affine);
209
210 // 2G + G = 3G
211 const j_3g = JacobianPoint.fromAffine(g26).dbl().addMixed(g26);
212 const j_3g_affine = toStdlibAffine(j_3g);
213
214 const stdlib_3g_affine = G.dbl().add(G).affineCoordinates();
215
216 try std.testing.expect(j_3g_affine.x.equivalent(stdlib_3g_affine.x));
217 try std.testing.expect(j_3g_affine.y.equivalent(stdlib_3g_affine.y));
218}
219
220test "identity + affine = affine" {
221 const G = Secp256k1.basePoint;
222 const g_affine = G.affineCoordinates();
223 const g26 = AffinePoint.fromStdlib(g_affine);
224
225 const result = JacobianPoint.identity.addMixed(g26);
226 const result_affine = toStdlibAffine(result);
227
228 try std.testing.expect(result_affine.x.equivalent(g_affine.x));
229 try std.testing.expect(result_affine.y.equivalent(g_affine.y));
230}
231
232test "subMixed is inverse of addMixed" {
233 const G = Secp256k1.basePoint;
234 const g_affine = G.affineCoordinates();
235 const g26 = AffinePoint.fromStdlib(g_affine);
236
237 // 3G - G = 2G
238 const j_3g = JacobianPoint.fromAffine(g26).dbl().addMixed(g26);
239 const j_2g = j_3g.subMixed(g26);
240 const j_2g_affine = toStdlibAffine(j_2g);
241
242 const stdlib_2g_affine = G.dbl().affineCoordinates();
243
244 try std.testing.expect(j_2g_affine.x.equivalent(stdlib_2g_affine.x));
245 try std.testing.expect(j_2g_affine.y.equivalent(stdlib_2g_affine.y));
246}
247
248test "repeated doubling" {
249 const G = Secp256k1.basePoint;
250 const g_affine = G.affineCoordinates();
251
252 // 16G via 4 doublings
253 const j = JacobianPoint.fromStdlibAffine(g_affine).dbl().dbl().dbl().dbl();
254 const j_affine = toStdlibAffine(j);
255
256 const stdlib_affine = G.dbl().dbl().dbl().dbl().affineCoordinates();
257
258 try std.testing.expect(j_affine.x.equivalent(stdlib_affine.x));
259 try std.testing.expect(j_affine.y.equivalent(stdlib_affine.y));
260}
261
262test "full Jacobian add matches stdlib" {
263 const G = Secp256k1.basePoint;
264 const g_affine = G.affineCoordinates();
265 const g26 = AffinePoint.fromStdlib(g_affine);
266
267 // 2G + 3G = 5G
268 const j_2g = JacobianPoint.fromAffine(g26).dbl();
269 const j_3g = j_2g.addMixed(g26);
270 const j_5g = j_2g.add(j_3g);
271 const j_5g_affine = toStdlibAffine(j_5g);
272
273 const stdlib_5g = G.dbl().add(G.dbl().add(G));
274 const stdlib_5g_affine = stdlib_5g.affineCoordinates();
275
276 try std.testing.expect(j_5g_affine.x.equivalent(stdlib_5g_affine.x));
277 try std.testing.expect(j_5g_affine.y.equivalent(stdlib_5g_affine.y));
278}
279
280test "add with identity" {
281 const G = Secp256k1.basePoint;
282 const g_affine = G.affineCoordinates();
283 const g26 = AffinePoint.fromStdlib(g_affine);
284
285 const j_g = JacobianPoint.fromAffine(g26);
286 const result = j_g.add(JacobianPoint.identity);
287 const result_affine = toStdlibAffine(result);
288
289 try std.testing.expect(result_affine.x.equivalent(g_affine.x));
290 try std.testing.expect(result_affine.y.equivalent(g_affine.y));
291
292 const result2 = JacobianPoint.identity.add(j_g);
293 const result2_affine = toStdlibAffine(result2);
294
295 try std.testing.expect(result2_affine.x.equivalent(g_affine.x));
296 try std.testing.expect(result2_affine.y.equivalent(g_affine.y));
297}