group.go raw
1 package p256k1
2
3 // No imports needed for basic group operations
4
5 // GroupElementAffine represents a point on the secp256k1 curve in affine coordinates (x, y)
6 type GroupElementAffine struct {
7 x, y FieldElement
8 infinity bool
9 }
10
11 // GroupElementJacobian represents a point on the secp256k1 curve in Jacobian coordinates (x, y, z)
12 // where the affine coordinates are (x/z^2, y/z^3)
13 type GroupElementJacobian struct {
14 x, y, z FieldElement
15 infinity bool
16 }
17
18 // GroupElementStorage represents a point in storage format (compressed coordinates)
19 type GroupElementStorage struct {
20 x [32]byte
21 y [32]byte
22 }
23
24 // Generator point G for secp256k1 curve
25 var (
26 // Generator point in affine coordinates
27 // G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
28 // 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
29 GeneratorX FieldElement
30 GeneratorY FieldElement
31 Generator GroupElementAffine
32 )
33
34 // Initialize generator point
35 func init() {
36 // Generator X coordinate: 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
37 gxBytes := []byte{
38 0x79, 0xBE, 0x66, 0x7E, 0xF9, 0xDC, 0xBB, 0xAC, 0x55, 0xA0, 0x62, 0x95, 0xCE, 0x87, 0x0B, 0x07,
39 0x02, 0x9B, 0xFC, 0xDB, 0x2D, 0xCE, 0x28, 0xD9, 0x59, 0xF2, 0x81, 0x5B, 0x16, 0xF8, 0x17, 0x98,
40 }
41
42 // Generator Y coordinate: 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
43 gyBytes := []byte{
44 0x48, 0x3A, 0xDA, 0x77, 0x26, 0xA3, 0xC4, 0x65, 0x5D, 0xA4, 0xFB, 0xFC, 0x0E, 0x11, 0x08, 0xA8,
45 0xFD, 0x17, 0xB4, 0x48, 0xA6, 0x85, 0x54, 0x19, 0x9C, 0x47, 0xD0, 0x8F, 0xFB, 0x10, 0xD4, 0xB8,
46 }
47
48 GeneratorX.setB32(gxBytes)
49 GeneratorY.setB32(gyBytes)
50
51 // Create generator point
52 Generator = GroupElementAffine{
53 x: GeneratorX,
54 y: GeneratorY,
55 infinity: false,
56 }
57 }
58
59 // NewGroupElementAffine creates a new affine group element
60 func NewGroupElementAffine() *GroupElementAffine {
61 return &GroupElementAffine{
62 x: FieldElementZero,
63 y: FieldElementZero,
64 infinity: true,
65 }
66 }
67
68 // NewGroupElementJacobian creates a new Jacobian group element
69 func NewGroupElementJacobian() *GroupElementJacobian {
70 return &GroupElementJacobian{
71 x: FieldElementZero,
72 y: FieldElementZero,
73 z: FieldElementZero,
74 infinity: true,
75 }
76 }
77
78 // setXY sets a group element to the point with given coordinates
79 func (r *GroupElementAffine) setXY(x, y *FieldElement) {
80 r.x = *x
81 r.y = *y
82 r.infinity = false
83 }
84
85 // setXOVar sets a group element to the point with given X coordinate and Y oddness
86 func (r *GroupElementAffine) setXOVar(x *FieldElement, odd bool) bool {
87 // Compute y^2 = x^3 + 7 (secp256k1 curve equation)
88 var x2, x3, y2 FieldElement
89 x2.sqr(x)
90 x3.mul(&x2, x)
91
92 // Add 7 (the curve parameter b)
93 var seven FieldElement
94 seven.setInt(7)
95 y2 = x3
96 y2.add(&seven)
97
98 // Try to compute square root
99 var y FieldElement
100 if !y.sqrt(&y2) {
101 return false // x is not on the curve
102 }
103
104 // Choose the correct square root based on oddness
105 y.normalize()
106 if y.isOdd() != odd {
107 y.negate(&y, 1)
108 y.normalize()
109 }
110
111 r.setXY(x, &y)
112 return true
113 }
114
115 // isInfinity returns true if the group element is the point at infinity
116 func (r *GroupElementAffine) isInfinity() bool {
117 return r.infinity
118 }
119
120 // isValid checks if the group element is valid (on the curve)
121 func (r *GroupElementAffine) isValid() bool {
122 if r.infinity {
123 return true
124 }
125
126 // Check curve equation: y^2 = x^3 + 7
127 var lhs, rhs, x2, x3 FieldElement
128
129 // Normalize coordinates
130 var xNorm, yNorm FieldElement
131 xNorm = r.x
132 yNorm = r.y
133 xNorm.normalize()
134 yNorm.normalize()
135
136 // Compute y^2
137 lhs.sqr(&yNorm)
138
139 // Compute x^3 + 7
140 x2.sqr(&xNorm)
141 x3.mul(&x2, &xNorm)
142 rhs = x3
143 var seven FieldElement
144 seven.setInt(7)
145 rhs.add(&seven)
146
147 // Normalize both sides
148 lhs.normalize()
149 rhs.normalize()
150
151 return lhs.equal(&rhs)
152 }
153
154 // negate sets r to the negation of a (mirror around X axis)
155 func (r *GroupElementAffine) negate(a *GroupElementAffine) {
156 if a.infinity {
157 r.setInfinity()
158 return
159 }
160
161 r.x = a.x
162 r.y.negate(&a.y, a.y.magnitude)
163 r.infinity = false
164 }
165
166 // mulLambda applies the GLV endomorphism: λ·(x, y) = (β·x, y)
167 // This is the key operation that enables the GLV optimization.
168 // Since λ is a cube root of unity mod n, and β is a cube root of unity mod p,
169 // multiplying a point by λ (scalar) is equivalent to multiplying x by β (field).
170 // Reference: libsecp256k1 group_impl.h:secp256k1_ge_mul_lambda
171 func (r *GroupElementAffine) mulLambda(a *GroupElementAffine) {
172 if a.infinity {
173 r.setInfinity()
174 return
175 }
176
177 // r.x = β * a.x
178 r.x.mul(&a.x, &fieldBeta)
179 // r.y = a.y (unchanged)
180 r.y = a.y
181 r.infinity = false
182 }
183
184 // setInfinity sets the group element to the point at infinity
185 func (r *GroupElementAffine) setInfinity() {
186 r.x = FieldElementZero
187 r.y = FieldElementZero
188 r.infinity = true
189 }
190
191 // equal returns true if two group elements are equal
192 func (r *GroupElementAffine) equal(a *GroupElementAffine) bool {
193 if r.infinity && a.infinity {
194 return true
195 }
196 if r.infinity || a.infinity {
197 return false
198 }
199
200 // Normalize both points
201 var rNorm, aNorm GroupElementAffine
202 rNorm = *r
203 aNorm = *a
204 rNorm.x.normalize()
205 rNorm.y.normalize()
206 aNorm.x.normalize()
207 aNorm.y.normalize()
208
209 return rNorm.x.equal(&aNorm.x) && rNorm.y.equal(&aNorm.y)
210 }
211
212 // Jacobian coordinate operations
213
214 // setInfinity sets the Jacobian group element to the point at infinity
215 func (r *GroupElementJacobian) setInfinity() {
216 r.x = FieldElementZero
217 r.y = FieldElementOne
218 r.z = FieldElementZero
219 r.infinity = true
220 }
221
222 // isInfinity returns true if the Jacobian group element is the point at infinity
223 func (r *GroupElementJacobian) isInfinity() bool {
224 return r.infinity
225 }
226
227 // setGE sets a Jacobian element from an affine element
228 func (r *GroupElementJacobian) setGE(a *GroupElementAffine) {
229 if a.infinity {
230 r.setInfinity()
231 return
232 }
233
234 r.x = a.x
235 r.y = a.y
236 r.z = FieldElementOne
237 r.infinity = false
238 }
239
240 // setGEJ sets an affine element from a Jacobian element
241 // This follows the C secp256k1_ge_set_gej_var implementation exactly
242 // Optimized: avoid copy when we can modify in-place or when caller guarantees no reuse
243 func (r *GroupElementAffine) setGEJ(a *GroupElementJacobian) {
244 if a.infinity {
245 r.setInfinity()
246 return
247 }
248
249 // Optimization: if r == a (shouldn't happen but handle gracefully), or if we can work directly
250 // For now, we still need a copy since we modify fields, but we can optimize the copy
251 var aCopy GroupElementJacobian
252 aCopy = *a // Copy once, then work with copy
253
254 r.infinity = false
255
256 // secp256k1_fe_inv_var(&a->z, &a->z);
257 // Note: inv normalizes the input internally
258 aCopy.z.inv(&aCopy.z)
259
260 // secp256k1_fe_sqr(&z2, &a->z);
261 var z2 FieldElement
262 z2.sqr(&aCopy.z)
263
264 // secp256k1_fe_mul(&z3, &a->z, &z2);
265 var z3 FieldElement
266 z3.mul(&aCopy.z, &z2)
267
268 // secp256k1_fe_mul(&a->x, &a->x, &z2);
269 aCopy.x.mul(&aCopy.x, &z2)
270
271 // secp256k1_fe_mul(&a->y, &a->y, &z3);
272 aCopy.y.mul(&aCopy.y, &z3)
273
274 // secp256k1_fe_set_int(&a->z, 1);
275 aCopy.z.setInt(1)
276
277 // secp256k1_ge_set_xy(r, &a->x, &a->y);
278 r.x = aCopy.x
279 r.y = aCopy.y
280 }
281
282 // negate sets r to the negation of a Jacobian point
283 func (r *GroupElementJacobian) negate(a *GroupElementJacobian) {
284 if a.infinity {
285 r.setInfinity()
286 return
287 }
288
289 r.x = a.x
290 r.y.negate(&a.y, a.y.magnitude)
291 r.z = a.z
292 r.infinity = false
293 }
294
295 // mulLambda applies the GLV endomorphism to a Jacobian point: λ·(X, Y, Z) = (β·X, Y, Z)
296 // In Jacobian coordinates, only the X coordinate is multiplied by β.
297 func (r *GroupElementJacobian) mulLambda(a *GroupElementJacobian) {
298 if a.infinity {
299 r.setInfinity()
300 return
301 }
302
303 // r.x = β * a.x
304 r.x.mul(&a.x, &fieldBeta)
305 // r.y and r.z unchanged
306 r.y = a.y
307 r.z = a.z
308 r.infinity = false
309 }
310
311 // double sets r = 2*a (point doubling in Jacobian coordinates)
312 // This follows the C secp256k1_gej_double implementation exactly
313 func (r *GroupElementJacobian) double(a *GroupElementJacobian) {
314 // Exact C translation - no early return for infinity
315 // From C code - exact translation with proper variable reuse:
316 // secp256k1_fe_mul(&r->z, &a->z, &a->y); /* Z3 = Y1*Z1 (1) */
317 // secp256k1_fe_sqr(&s, &a->y); /* S = Y1^2 (1) */
318 // secp256k1_fe_sqr(&l, &a->x); /* L = X1^2 (1) */
319 // secp256k1_fe_mul_int(&l, 3); /* L = 3*X1^2 (3) */
320 // secp256k1_fe_half(&l); /* L = 3/2*X1^2 (2) */
321 // secp256k1_fe_negate(&t, &s, 1); /* T = -S (2) */
322 // secp256k1_fe_mul(&t, &t, &a->x); /* T = -X1*S (1) */
323 // secp256k1_fe_sqr(&r->x, &l); /* X3 = L^2 (1) */
324 // secp256k1_fe_add(&r->x, &t); /* X3 = L^2 + T (2) */
325 // secp256k1_fe_add(&r->x, &t); /* X3 = L^2 + 2*T (3) */
326 // secp256k1_fe_sqr(&s, &s); /* S' = S^2 (1) */
327 // secp256k1_fe_add(&t, &r->x); /* T' = X3 + T (4) */
328 // secp256k1_fe_mul(&r->y, &t, &l); /* Y3 = L*(X3 + T) (1) */
329 // secp256k1_fe_add(&r->y, &s); /* Y3 = L*(X3 + T) + S^2 (2) */
330 // secp256k1_fe_negate(&r->y, &r->y, 2); /* Y3 = -(L*(X3 + T) + S^2) (3) */
331
332 var l, s, t FieldElement
333
334 r.infinity = a.infinity
335
336 // Z3 = Y1*Z1 (1)
337 r.z.mul(&a.z, &a.y)
338
339 // S = Y1^2 (1)
340 s.sqr(&a.y)
341
342 // L = X1^2 (1)
343 l.sqr(&a.x)
344
345 // L = 3*X1^2 (3)
346 l.mulInt(3)
347
348 // L = 3/2*X1^2 (2)
349 l.half(&l)
350
351 // T = -S (2) where S = Y1^2
352 t.negate(&s, 1)
353
354 // T = -X1*S = -X1*Y1^2 (1)
355 t.mul(&t, &a.x)
356
357 // X3 = L^2 (1)
358 r.x.sqr(&l)
359
360 // X3 = L^2 + T (2)
361 r.x.add(&t)
362
363 // X3 = L^2 + 2*T (3)
364 r.x.add(&t)
365
366 // S = S^2 = (Y1^2)^2 = Y1^4 (1)
367 s.sqr(&s)
368
369 // T = X3 + T = X3 + (-X1*Y1^2) (4)
370 t.add(&r.x)
371
372 // Y3 = L*(X3 + T) = L*(X3 + (-X1*Y1^2)) (1)
373 r.y.mul(&t, &l)
374
375 // Y3 = L*(X3 + T) + S^2 = L*(X3 + (-X1*Y1^2)) + Y1^4 (2)
376 r.y.add(&s)
377
378 // Y3 = -(L*(X3 + T) + S^2) (3)
379 r.y.negate(&r.y, 2)
380 }
381
382 // addVar sets r = a + b (variable-time point addition in Jacobian coordinates)
383 // This follows the C secp256k1_gej_add_var implementation exactly
384 // Operations: 12 mul, 4 sqr, 11 add/negate/normalizes_to_zero
385 func (r *GroupElementJacobian) addVar(a, b *GroupElementJacobian) {
386 // Handle infinity cases
387 if a.infinity {
388 *r = *b
389 return
390 }
391 if b.infinity {
392 *r = *a
393 return
394 }
395
396 // Following C code exactly: secp256k1_gej_add_var
397 // z22 = b->z^2
398 // z12 = a->z^2
399 // u1 = a->x * z22
400 // u2 = b->x * z12
401 // s1 = a->y * z22 * b->z
402 // s2 = b->y * z12 * a->z
403 // h = u2 - u1
404 // i = s2 - s1
405 // If h == 0 and i == 0: double(a)
406 // If h == 0 and i != 0: infinity
407 // Otherwise: add
408
409 var z22, z12, u1, u2, s1, s2, h, i, h2, h3, t FieldElement
410
411 // z22 = b->z^2
412 z22.sqr(&b.z)
413
414 // z12 = a->z^2
415 z12.sqr(&a.z)
416
417 // u1 = a->x * z22
418 u1.mul(&a.x, &z22)
419
420 // u2 = b->x * z12
421 u2.mul(&b.x, &z12)
422
423 // s1 = a->y * z22 * b->z
424 s1.mul(&a.y, &z22)
425 s1.mul(&s1, &b.z)
426
427 // s2 = b->y * z12 * a->z
428 s2.mul(&b.y, &z12)
429 s2.mul(&s2, &a.z)
430
431 // h = u2 - u1
432 h.negate(&u1, 1)
433 h.add(&u2)
434
435 // i = s2 - s1
436 i.negate(&s2, 1)
437 i.add(&s1)
438
439 // Check if h normalizes to zero
440 if h.normalizesToZeroVar() {
441 if i.normalizesToZeroVar() {
442 // Points are equal - double
443 r.double(a)
444 return
445 } else {
446 // Points are negatives - result is infinity
447 r.setInfinity()
448 return
449 }
450 }
451
452 // General addition case
453 r.infinity = false
454
455 // t = h * b->z
456 t.mul(&h, &b.z)
457
458 // r->z = a->z * t
459 r.z.mul(&a.z, &t)
460
461 // h2 = h^2
462 h2.sqr(&h)
463
464 // h2 = -h2
465 h2.negate(&h2, 1)
466
467 // h3 = h2 * h
468 h3.mul(&h2, &h)
469
470 // t = u1 * h2
471 t.mul(&u1, &h2)
472
473 // r->x = i^2
474 r.x.sqr(&i)
475
476 // r->x = i^2 + h3
477 r.x.add(&h3)
478
479 // r->x = i^2 + h3 + t
480 r.x.add(&t)
481
482 // r->x = i^2 + h3 + 2*t
483 r.x.add(&t)
484
485 // t = t + r->x
486 t.add(&r.x)
487
488 // r->y = t * i
489 r.y.mul(&t, &i)
490
491 // h3 = h3 * s1
492 h3.mul(&h3, &s1)
493
494 // r->y = t * i + h3
495 r.y.add(&h3)
496 }
497
498 // addGEWithZR sets r = a + b where a is Jacobian and b is affine
499 // If rzr is not nil, sets *rzr = h such that r->z == a->z * h
500 // This follows the C secp256k1_gej_add_ge_var implementation exactly
501 // Operations: 8 mul, 3 sqr, 11 add/negate/normalizes_to_zero
502 func (r *GroupElementJacobian) addGEWithZR(a *GroupElementJacobian, b *GroupElementAffine, rzr *FieldElement) {
503 if a.infinity {
504 if rzr != nil {
505 // C code: VERIFY_CHECK(rzr == NULL) for infinity case
506 // But we'll handle it gracefully
507 }
508 r.setGE(b)
509 return
510 }
511 if b.infinity {
512 if rzr != nil {
513 // C code: secp256k1_fe_set_int(rzr, 1)
514 rzr.setInt(1)
515 }
516 *r = *a
517 return
518 }
519
520 // Following C code exactly: secp256k1_gej_add_ge_var
521 var z12, u1, u2, s1, s2, h, i, h2, h3, t FieldElement
522
523 // z12 = a->z^2
524 z12.sqr(&a.z)
525
526 // u1 = a->x
527 u1 = a.x
528
529 // u2 = b->x * z12
530 u2.mul(&b.x, &z12)
531
532 // s1 = a->y
533 s1 = a.y
534
535 // s2 = b->y * z12 * a->z
536 s2.mul(&b.y, &z12)
537 s2.mul(&s2, &a.z)
538
539 // h = u2 - u1
540 // C code uses SECP256K1_GEJ_X_MAGNITUDE_MAX but we use a.x.magnitude
541 h.negate(&u1, a.x.magnitude)
542 h.add(&u2)
543
544 // i = s2 - s1
545 i.negate(&s2, 1)
546 i.add(&s1)
547
548 // Check if h normalizes to zero
549 if h.normalizesToZeroVar() {
550 if i.normalizesToZeroVar() {
551 // Points are equal - double
552 // C code: secp256k1_gej_double_var(r, a, rzr)
553 // For doubling, rzr should be set to 2*a->y (but we'll use a simpler approach)
554 // Actually, rzr = 2*a->y based on the double_var implementation
555 // But for our use case (building odd multiples), we shouldn't hit this case
556 if rzr != nil {
557 // Approximate: rzr = 2*a->y (from double_var logic)
558 // But simpler: just set to 0 since we shouldn't hit this
559 rzr.setInt(0)
560 }
561 r.double(a)
562 return
563 } else {
564 // Points are negatives - result is infinity
565 if rzr != nil {
566 // C code: secp256k1_fe_set_int(rzr, 0)
567 rzr.setInt(0)
568 }
569 r.setInfinity()
570 return
571 }
572 }
573
574 // General addition case
575 r.infinity = false
576
577 // C code: if (rzr != NULL) *rzr = h;
578 if rzr != nil {
579 *rzr = h
580 }
581
582 // r->z = a->z * h
583 r.z.mul(&a.z, &h)
584
585 // h2 = h^2
586 h2.sqr(&h)
587
588 // h2 = -h2
589 h2.negate(&h2, 1)
590
591 // h3 = h2 * h
592 h3.mul(&h2, &h)
593
594 // t = u1 * h2
595 t.mul(&u1, &h2)
596
597 // r->x = i^2
598 r.x.sqr(&i)
599
600 // r->x = i^2 + h3
601 r.x.add(&h3)
602
603 // r->x = i^2 + h3 + t
604 r.x.add(&t)
605
606 // r->x = i^2 + h3 + 2*t
607 r.x.add(&t)
608
609 // t = t + r->x
610 t.add(&r.x)
611
612 // r->y = t * i
613 r.y.mul(&t, &i)
614
615 // h3 = h3 * s1
616 h3.mul(&h3, &s1)
617
618 // r->y = t * i + h3
619 r.y.add(&h3)
620 }
621
622 // addGE sets r = a + b where a is Jacobian and b is affine
623 // This follows the C secp256k1_gej_add_ge_var implementation exactly
624 // Operations: 8 mul, 3 sqr, 11 add/negate/normalizes_to_zero
625 func (r *GroupElementJacobian) addGE(a *GroupElementJacobian, b *GroupElementAffine) {
626 r.addGEWithZR(a, b, nil)
627 }
628
629 // clear clears a group element to prevent leaking sensitive information
630 func (r *GroupElementAffine) clear() {
631 r.x.clear()
632 r.y.clear()
633 r.infinity = true
634 }
635
636 // clear clears a Jacobian group element
637 func (r *GroupElementJacobian) clear() {
638 r.x.clear()
639 r.y.clear()
640 r.z.clear()
641 r.infinity = true
642 }
643
644 // toStorage converts a group element to storage format
645 // Optimized: normalize in-place when possible to avoid copy
646 func (r *GroupElementAffine) toStorage(s *GroupElementStorage) {
647 if r.infinity {
648 // Store infinity as all zeros
649 for i := range s.x {
650 s.x[i] = 0
651 s.y[i] = 0
652 }
653 return
654 }
655
656 // Normalize in-place if needed, then convert to bytes
657 // Optimization: check if already normalized before copying
658 if !r.x.normalized {
659 r.x.normalize()
660 }
661 if !r.y.normalized {
662 r.y.normalize()
663 }
664
665 r.x.getB32(s.x[:])
666 r.y.getB32(s.y[:])
667 }
668
669 // fromStorage converts from storage format to group element
670 func (r *GroupElementAffine) fromStorage(s *GroupElementStorage) {
671 // Check if it's the infinity point (all zeros)
672 var allZero bool = true
673 for i := range s.x {
674 if s.x[i] != 0 || s.y[i] != 0 {
675 allZero = false
676 break
677 }
678 }
679
680 if allZero {
681 r.setInfinity()
682 return
683 }
684
685 // Convert from bytes
686 r.x.setB32(s.x[:])
687 r.y.setB32(s.y[:])
688 r.infinity = false
689 }
690
691 // toBytes converts a group element to byte representation
692 // Optimized: normalize in-place when possible to avoid copy
693 func (r *GroupElementAffine) toBytes(buf []byte) {
694 if len(buf) < 64 {
695 panic("buffer too small for group element")
696 }
697
698 if r.infinity {
699 // Represent infinity as all zeros
700 for i := range buf[:64] {
701 buf[i] = 0
702 }
703 return
704 }
705
706 // Normalize in-place if needed, then convert to bytes
707 // Optimization: check if already normalized before copying
708 if !r.x.normalized {
709 r.x.normalize()
710 }
711 if !r.y.normalized {
712 r.y.normalize()
713 }
714
715 r.x.getB32(buf[:32])
716 r.y.getB32(buf[32:64])
717 }
718
719 // fromBytes converts from byte representation to group element
720 func (r *GroupElementAffine) fromBytes(buf []byte) {
721 if len(buf) < 64 {
722 panic("buffer too small for group element")
723 }
724
725 // Check if it's all zeros (infinity)
726 var allZero bool = true
727 for i := 0; i < 64; i++ {
728 if buf[i] != 0 {
729 allZero = false
730 break
731 }
732 }
733
734 if allZero {
735 r.setInfinity()
736 return
737 }
738
739 // Convert from bytes
740 r.x.setB32(buf[:32])
741 r.y.setB32(buf[32:64])
742 r.infinity = false
743 }
744
745 // BatchNormalize converts multiple Jacobian points to affine coordinates efficiently
746 // using Montgomery's batch inversion trick. This computes n inversions using only
747 // 1 actual inversion + 3(n-1) multiplications, which is much faster than n individual
748 // inversions when n > 1.
749 //
750 // The input slice 'points' contains the Jacobian points to convert.
751 // The output slice 'out' will contain the corresponding affine points.
752 // If out is nil or smaller than points, a new slice will be allocated.
753 //
754 // Points at infinity are handled correctly and result in affine infinity points.
755 func BatchNormalize(out []GroupElementAffine, points []GroupElementJacobian) []GroupElementAffine {
756 n := len(points)
757 if n == 0 {
758 return out
759 }
760
761 // Ensure output slice is large enough
762 if out == nil || len(out) < n {
763 out = make([]GroupElementAffine, n)
764 }
765
766 // Handle single point case - no batch optimization needed
767 if n == 1 {
768 out[0].setGEJ(&points[0])
769 return out
770 }
771
772 // Collect non-infinity Z coordinates for batch inversion
773 // We need to track which points are at infinity
774 zValues := make([]FieldElement, 0, n)
775 nonInfIndices := make([]int, 0, n)
776
777 for i := 0; i < n; i++ {
778 if points[i].isInfinity() {
779 out[i].setInfinity()
780 } else {
781 zValues = append(zValues, points[i].z)
782 nonInfIndices = append(nonInfIndices, i)
783 }
784 }
785
786 // If all points are at infinity, we're done
787 if len(zValues) == 0 {
788 return out
789 }
790
791 // Batch invert all Z values
792 zInvs := make([]FieldElement, len(zValues))
793 batchInverse(zInvs, zValues)
794
795 // Now compute affine coordinates for each non-infinity point
796 // affine.x = X * Z^(-2)
797 // affine.y = Y * Z^(-3)
798 for i, idx := range nonInfIndices {
799 var zInv2, zInv3 FieldElement
800
801 // zInv2 = Z^(-2)
802 zInv2.sqr(&zInvs[i])
803
804 // zInv3 = Z^(-3) = Z^(-2) * Z^(-1)
805 zInv3.mul(&zInv2, &zInvs[i])
806
807 // x = X * Z^(-2)
808 out[idx].x.mul(&points[idx].x, &zInv2)
809
810 // y = Y * Z^(-3)
811 out[idx].y.mul(&points[idx].y, &zInv3)
812
813 out[idx].infinity = false
814 }
815
816 return out
817 }
818
819 // BatchNormalizeInPlace converts multiple Jacobian points to affine coordinates
820 // in place, modifying the input slice. Each Jacobian point is converted such that
821 // Z becomes 1 (or the point is marked as infinity).
822 //
823 // This is useful when you want to normalize points without allocating new memory
824 // for a separate affine point array.
825 func BatchNormalizeInPlace(points []GroupElementJacobian) {
826 n := len(points)
827 if n == 0 {
828 return
829 }
830
831 // Handle single point case
832 if n == 1 {
833 if !points[0].isInfinity() {
834 var zInv, zInv2, zInv3 FieldElement
835 zInv.inv(&points[0].z)
836 zInv2.sqr(&zInv)
837 zInv3.mul(&zInv2, &zInv)
838 points[0].x.mul(&points[0].x, &zInv2)
839 points[0].y.mul(&points[0].y, &zInv3)
840 points[0].z.setInt(1)
841 }
842 return
843 }
844
845 // Collect non-infinity Z coordinates for batch inversion
846 zValues := make([]FieldElement, 0, n)
847 nonInfIndices := make([]int, 0, n)
848
849 for i := 0; i < n; i++ {
850 if !points[i].isInfinity() {
851 zValues = append(zValues, points[i].z)
852 nonInfIndices = append(nonInfIndices, i)
853 }
854 }
855
856 // If all points are at infinity, we're done
857 if len(zValues) == 0 {
858 return
859 }
860
861 // Batch invert all Z values
862 zInvs := make([]FieldElement, len(zValues))
863 batchInverse(zInvs, zValues)
864
865 // Now normalize each non-infinity point
866 for i, idx := range nonInfIndices {
867 var zInv2, zInv3 FieldElement
868
869 // zInv2 = Z^(-2)
870 zInv2.sqr(&zInvs[i])
871
872 // zInv3 = Z^(-3) = Z^(-2) * Z^(-1)
873 zInv3.mul(&zInv2, &zInvs[i])
874
875 // x = X * Z^(-2)
876 points[idx].x.mul(&points[idx].x, &zInv2)
877
878 // y = Y * Z^(-3)
879 points[idx].y.mul(&points[idx].y, &zInv3)
880
881 // Z = 1
882 points[idx].z.setInt(1)
883 }
884 }
885
886 // batchNormalize16 converts exactly 16 Jacobian points to affine coordinates
887 // with zero heap allocations. Optimized for GLV table building where
888 // tableSize = 16 (glvTableSize).
889 //
890 // Uses stack-allocated arrays throughout for optimal performance.
891 // Points at infinity are handled correctly.
892 func batchNormalize16(out *[16]GroupElementAffine, points *[16]GroupElementJacobian) {
893 // Collect Z coordinates for batch inversion
894 // For GLV table building, all points should be valid (no infinity)
895 var zValues [16]FieldElement
896 var validCount int
897
898 for i := 0; i < 16; i++ {
899 if points[i].isInfinity() {
900 out[i].setInfinity()
901 } else {
902 zValues[validCount] = points[i].z
903 validCount++
904 }
905 }
906
907 // If all points are at infinity, we're done
908 if validCount == 0 {
909 return
910 }
911
912 // For the common case where all 16 points are valid
913 if validCount == 16 {
914 // Batch invert all Z values with zero allocation
915 var zInvs [16]FieldElement
916 batchInverse16(&zInvs, &zValues)
917
918 // Compute affine coordinates for each point
919 for i := 0; i < 16; i++ {
920 var zInv2, zInv3 FieldElement
921
922 // zInv2 = Z^(-2)
923 zInv2.sqr(&zInvs[i])
924
925 // zInv3 = Z^(-3) = Z^(-2) * Z^(-1)
926 zInv3.mul(&zInv2, &zInvs[i])
927
928 // x = X * Z^(-2)
929 out[i].x.mul(&points[i].x, &zInv2)
930
931 // y = Y * Z^(-3)
932 out[i].y.mul(&points[i].y, &zInv3)
933
934 out[i].infinity = false
935 }
936 return
937 }
938
939 // Handle partial case (some points at infinity) - rare in practice
940 // Fall back to slice-based batch inversion for this edge case
941 zSlice := zValues[:validCount]
942 zInvSlice := make([]FieldElement, validCount)
943 batchInverse(zInvSlice, zSlice)
944
945 // Apply inversions to non-infinity points
946 invIdx := 0
947 for i := 0; i < 16; i++ {
948 if !points[i].isInfinity() {
949 var zInv2, zInv3 FieldElement
950
951 zInv2.sqr(&zInvSlice[invIdx])
952 zInv3.mul(&zInv2, &zInvSlice[invIdx])
953
954 out[i].x.mul(&points[i].x, &zInv2)
955 out[i].y.mul(&points[i].y, &zInv3)
956 out[i].infinity = false
957
958 invIdx++
959 }
960 }
961 }
962
963 // batchNormalize32 converts exactly 32 Jacobian points to affine coordinates
964 // with zero heap allocations. Optimized for GLV table building where
965 // tableSize = 32 (glvTableSize with window size 6).
966 //
967 // Uses stack-allocated arrays throughout for optimal performance.
968 // Points at infinity are handled correctly.
969 func batchNormalize32(out *[32]GroupElementAffine, points *[32]GroupElementJacobian) {
970 // Collect Z coordinates for batch inversion
971 // For GLV table building, all points should be valid (no infinity)
972 var zValues [32]FieldElement
973 var validCount int
974
975 for i := 0; i < 32; i++ {
976 if points[i].isInfinity() {
977 out[i].setInfinity()
978 } else {
979 zValues[validCount] = points[i].z
980 validCount++
981 }
982 }
983
984 // If all points are at infinity, we're done
985 if validCount == 0 {
986 return
987 }
988
989 // For the common case where all 32 points are valid
990 if validCount == 32 {
991 // Batch invert all Z values with zero allocation
992 var zInvs [32]FieldElement
993 batchInverse32(&zInvs, &zValues)
994
995 // Compute affine coordinates for each point
996 for i := 0; i < 32; i++ {
997 var zInv2, zInv3 FieldElement
998
999 // zInv2 = Z^(-2)
1000 zInv2.sqr(&zInvs[i])
1001
1002 // zInv3 = Z^(-3) = Z^(-2) * Z^(-1)
1003 zInv3.mul(&zInv2, &zInvs[i])
1004
1005 // x = X * Z^(-2)
1006 out[i].x.mul(&points[i].x, &zInv2)
1007
1008 // y = Y * Z^(-3)
1009 out[i].y.mul(&points[i].y, &zInv3)
1010
1011 out[i].infinity = false
1012 }
1013 return
1014 }
1015
1016 // Handle partial case (some points at infinity) - rare in practice
1017 // Fall back to slice-based batch inversion for this edge case
1018 zSlice := zValues[:validCount]
1019 zInvSlice := make([]FieldElement, validCount)
1020 batchInverse(zInvSlice, zSlice)
1021
1022 // Apply inversions to non-infinity points
1023 invIdx := 0
1024 for i := 0; i < 32; i++ {
1025 if !points[i].isInfinity() {
1026 var zInv2, zInv3 FieldElement
1027
1028 zInv2.sqr(&zInvSlice[invIdx])
1029 zInv3.mul(&zInv2, &zInvSlice[invIdx])
1030
1031 out[i].x.mul(&points[i].x, &zInv2)
1032 out[i].y.mul(&points[i].y, &zInv3)
1033 out[i].infinity = false
1034
1035 invIdx++
1036 }
1037 }
1038 }
1039
1040 // =============================================================================
1041 // GLV Endomorphism Support Functions
1042 // =============================================================================
1043
1044 // ecmultEndoSplit splits a scalar and point for the GLV endomorphism optimization.
1045 // Given a scalar s and point p, it computes:
1046 // s1, s2 such that s1 + s2*λ ≡ s (mod n)
1047 // p1 = p
1048 // p2 = λ*p = (β*p.x, p.y)
1049 //
1050 // It also normalizes s1 and s2 to be "low" (not high) by conditionally negating
1051 // both the scalar and corresponding point.
1052 //
1053 // After this function:
1054 // s1 * p1 + s2 * p2 = s * p
1055 //
1056 // Reference: libsecp256k1 ecmult_impl.h:secp256k1_ecmult_endo_split
1057 func ecmultEndoSplit(s1, s2 *Scalar, p1, p2 *GroupElementAffine, s *Scalar, p *GroupElementAffine) {
1058 // Split the scalar: s = s1 + s2*λ
1059 scalarSplitLambda(s1, s2, s)
1060
1061 // p1 = p (copy)
1062 *p1 = *p
1063
1064 // p2 = λ*p = (β*p.x, p.y)
1065 p2.mulLambda(p)
1066
1067 // If s1 is high, negate it and p1
1068 if s1.isHigh() {
1069 s1.negate(s1)
1070 p1.negate(p1)
1071 }
1072
1073 // If s2 is high, negate it and p2
1074 if s2.isHigh() {
1075 s2.negate(s2)
1076 p2.negate(p2)
1077 }
1078 }
1079
1080 // ecmultEndoSplitJac is the Jacobian version of ecmultEndoSplit.
1081 // Given a scalar s and Jacobian point p, it computes the split for GLV optimization.
1082 func ecmultEndoSplitJac(s1, s2 *Scalar, p1, p2 *GroupElementJacobian, s *Scalar, p *GroupElementJacobian) {
1083 // Split the scalar: s = s1 + s2*λ
1084 scalarSplitLambda(s1, s2, s)
1085
1086 // p1 = p (copy)
1087 *p1 = *p
1088
1089 // p2 = λ*p = (β*p.x, p.y, p.z)
1090 p2.mulLambda(p)
1091
1092 // If s1 is high, negate it and p1
1093 if s1.isHigh() {
1094 s1.negate(s1)
1095 p1.negate(p1)
1096 }
1097
1098 // If s2 is high, negate it and p2
1099 if s2.isHigh() {
1100 s2.negate(s2)
1101 p2.negate(p2)
1102 }
1103 }
1104