1use std::sync::OnceLock;
7use subtle::Choice;
8
9use crate::field::{FeStorage, FieldElement};
10
11const SECP256K1_B: u32 = 7;
13
14pub(crate) fn const_beta() -> FieldElement {
16 let b: [u8; 32] = [
17 0x7a, 0xe9, 0x6a, 0x2b, 0x65, 0x7c, 0x07, 0x10, 0x6e, 0x64, 0x47, 0x9e, 0xac, 0x34, 0x34,
18 0xe9, 0x9c, 0xf0, 0x49, 0x75, 0x12, 0xf5, 0x89, 0x95, 0xc1, 0x39, 0x6c, 0x28, 0x71, 0x95,
19 0x01, 0xee,
20 ];
21 let mut r = FieldElement::zero();
22 r.set_b32_mod(&b);
23 r
24}
25
26#[repr(C)]
28#[derive(Clone, Copy, Debug, Default)]
29pub struct Ge {
30 pub x: FieldElement,
31 pub y: FieldElement,
32 pub infinity: bool,
33}
34
35#[derive(Clone, Copy, Debug)]
37pub struct GeStorage {
38 pub x: FeStorage,
39 pub y: FeStorage,
40}
41
42impl GeStorage {
43 pub fn cmov(&mut self, a: &GeStorage, flag: Choice) {
44 self.x.cmov(&a.x, flag);
45 self.y.cmov(&a.y, flag);
46 }
47}
48
49#[repr(C)]
51#[derive(Clone, Copy, Debug, Default)]
52pub struct Gej {
53 pub x: FieldElement,
54 pub y: FieldElement,
55 pub z: FieldElement,
56 pub infinity: bool,
57}
58
59impl Ge {
60 pub fn set_xy(&mut self, x: &FieldElement, y: &FieldElement) {
61 self.infinity = false;
62 self.x = *x;
63 self.y = *y;
64 }
65
66 pub fn set_infinity(&mut self) {
67 self.infinity = true;
68 self.x.set_int(0);
69 self.y.set_int(0);
70 }
71
72 pub fn is_infinity(&self) -> bool {
73 self.infinity
74 }
75
76 pub fn neg(&mut self, a: &Ge) {
77 *self = *a;
78 if !a.infinity {
79 self.y.normalize_weak();
80 let y = self.y;
81 self.y.negate(&y, 1);
82 }
83 }
84
85 pub fn set_gej(&mut self, a: &mut Gej) {
87 if a.infinity {
88 self.set_infinity();
89 return;
90 }
91 self.infinity = false;
92 let z = a.z;
93 a.z.inv(&z);
94 let mut z2 = FieldElement::zero();
95 let mut z3 = FieldElement::zero();
96 z2.sqr(&a.z);
97 z3.mul(&z2, &a.z);
98 let ax = a.x;
99 let ay = a.y;
100 a.x.mul(&ax, &z2);
101 a.y.mul(&ay, &z3);
102 a.z.set_int(1);
103 self.x = a.x;
104 self.y = a.y;
105 }
106
107 #[inline(always)]
109 pub fn set_gej_var(&mut self, a: &Gej) {
110 if a.is_infinity() {
111 self.set_infinity();
112 return;
113 }
114 self.infinity = false;
115 let mut zi = FieldElement::zero();
116 zi.inv(&a.z);
117 let mut z2 = FieldElement::zero();
118 let mut z3 = FieldElement::zero();
119 z2.sqr(&zi);
120 z3.mul(&z2, &zi);
121 let mut x = FieldElement::zero();
122 let mut y = FieldElement::zero();
123 x.mul(&a.x, &z2);
124 y.mul(&a.y, &z3);
125 self.set_xy(&x, &y);
126 }
127
128 #[inline(always)]
130 pub fn set_gej_zinv(&mut self, a: &Gej, zi: &FieldElement) {
131 debug_assert!(!a.infinity);
132 self.infinity = false;
133 let mut zi2 = FieldElement::zero();
134 let mut zi3 = FieldElement::zero();
135 zi2.sqr(zi);
136 zi3.mul(&zi2, zi);
137 self.x.mul(&a.x, &zi2);
138 self.y.mul(&a.y, &zi3);
139 }
140
141 pub fn set_ge_zinv(&mut self, a: &Ge, zi: &FieldElement) {
143 debug_assert!(!a.infinity);
144 self.infinity = false;
145 let mut zi2 = FieldElement::zero();
146 let mut zi3 = FieldElement::zero();
147 zi2.sqr(zi);
148 zi3.mul(&zi2, zi);
149 self.x.mul(&a.x, &zi2);
150 self.y.mul(&a.y, &zi3);
151 }
152
153 pub fn mul_lambda(&mut self, a: &Ge) {
155 *self = *a;
156 if !a.infinity {
157 let beta = const_beta();
158 let x = self.x;
159 self.x.mul(&x, &beta);
160 }
161 }
162
163 pub fn from_storage(&mut self, a: &GeStorage) {
165 self.infinity = false;
166 self.x.from_storage(&a.x);
167 self.y.from_storage(&a.y);
168 }
169
170 #[cfg(any(target_arch = "x86_64", target_arch = "aarch64"))]
172 pub fn x_on_curve_var(x: &FieldElement) -> bool {
173 let mut c = FieldElement::zero();
174 c.sqr(x);
175 let c_val = c;
176 c.mul(&c_val, x);
177 c.add_int(SECP256K1_B);
178 FieldElement::is_square_var(&c)
179 }
180
181 #[cfg(any(target_arch = "x86_64", target_arch = "aarch64"))]
184 pub fn x_frac_on_curve_var(xn: &FieldElement, xd: &FieldElement) -> bool {
185 let mut r = FieldElement::zero();
186 let mut t = FieldElement::zero();
187 r.mul(xd, xn);
188 t.sqr(xn);
189 let r_val = r;
190 r.mul(&r_val, &t);
191 t.sqr(xd);
192 let t_val = t;
193 t.sqr(&t_val);
194 t.mul_int(SECP256K1_B);
195 r.add_assign(&t);
196 FieldElement::is_square_var(&r)
197 }
198
199 #[inline(always)]
201 pub fn set_xo_var(&mut self, x: &FieldElement, odd: bool) -> bool {
202 let mut x2 = FieldElement::zero();
203 let mut x3 = FieldElement::zero();
204 x2.sqr(x);
205 x3.mul(x, &x2);
206 self.x = *x;
207 self.infinity = false;
208 x3.add_int(SECP256K1_B);
209 let ok = self.y.sqrt(&x3);
210 self.y.normalize();
211 if self.y.is_odd() != odd {
212 let y = self.y;
213 self.y.negate(&y, 1);
214 }
215 ok
216 }
217}
218
219impl Gej {
220 pub fn set_infinity(&mut self) {
221 self.infinity = true;
222 self.x.set_int(0);
223 self.y.set_int(0);
224 self.z.set_int(0);
225 }
226
227 pub fn is_infinity(&self) -> bool {
228 self.infinity
229 }
230
231 #[inline(always)]
232 pub fn set_ge(&mut self, a: &Ge) {
233 self.infinity = a.infinity;
234 self.x = a.x;
235 self.y = a.y;
236 self.z.set_int(1);
237 }
238
239 pub fn neg(&mut self, a: &Gej) {
240 self.infinity = a.infinity;
241 self.x = a.x;
242 self.y = a.y;
243 self.z = a.z;
244 if !a.infinity {
245 self.y.normalize_weak();
246 let y = self.y;
247 self.y.negate(&y, 1);
248 }
249 }
250
251 #[inline(always)]
252 pub fn double(&mut self, a: &Gej) {
253 let mut l = FieldElement::zero();
254 let mut s = FieldElement::zero();
255 let mut t = FieldElement::zero();
256
257 self.infinity = a.infinity;
258 if a.infinity {
259 return;
260 }
261
262 self.z.mul(&a.z, &a.y);
263 s.sqr(&a.y);
264 l.sqr(&a.x);
265 l.mul_int(3);
266 l.half();
267 t.negate(&s, 1);
268 let t_in = t;
269 t.mul(&t_in, &a.x);
270 self.x.sqr(&l);
271 self.x.add_assign(&t);
272 self.x.add_assign(&t);
273 let s_in = s;
274 s.sqr(&s_in);
275 t.add_assign(&self.x);
276 self.y.mul(&t, &l);
277 self.y.add_assign(&s);
278 let y_in = self.y;
279 self.y.negate(&y_in, 2);
280 }
281
282 #[inline(always)]
283 pub fn double_var(&mut self, a: &Gej) {
284 if a.infinity {
285 self.set_infinity();
286 return;
287 }
288 self.double(a);
289 }
290
291 #[inline(always)]
292 pub fn add_var(&mut self, a: &Gej, b: &Gej) {
293 if a.infinity {
294 *self = *b;
295 return;
296 }
297 if b.infinity {
298 *self = *a;
299 return;
300 }
301
302 let mut z22 = FieldElement::zero();
303 let mut z12 = FieldElement::zero();
304 let mut u1 = FieldElement::zero();
305 let mut u2 = FieldElement::zero();
306 let mut s1 = FieldElement::zero();
307 let mut s2 = FieldElement::zero();
308 let mut h = FieldElement::zero();
309 let mut i = FieldElement::zero();
310 let mut h2 = FieldElement::zero();
311 let mut h3 = FieldElement::zero();
312 let mut t = FieldElement::zero();
313
314 z22.sqr(&b.z);
315 z12.sqr(&a.z);
316 u1.mul(&a.x, &z22);
317 u2.mul(&b.x, &z12);
318 s1.mul(&a.y, &z22);
319 let s1_in = s1;
320 s1.mul(&s1_in, &b.z);
321 s2.mul(&b.y, &z12);
322 let s2_in = s2;
323 s2.mul(&s2_in, &a.z);
324 h.negate(&u1, 1);
325 h.add_assign(&u2);
326 i.negate(&s2, 1);
327 i.add_assign(&s1);
328
329 if h.normalizes_to_zero_var() {
330 if i.normalizes_to_zero_var() {
331 self.double_var(a);
332 } else {
333 self.set_infinity();
334 }
335 return;
336 }
337
338 self.infinity = false;
339 t.mul(&h, &b.z);
340 self.z.mul(&a.z, &t);
341 h2.sqr(&h);
342 let h2_in = h2;
343 h2.negate(&h2_in, 1);
344 h3.mul(&h2, &h);
345 t.mul(&u1, &h2);
346 self.x.sqr(&i);
347 self.x.add_assign(&h3);
348 self.x.add_assign(&t);
349 self.x.add_assign(&t);
350 t.add_assign(&self.x);
351 self.y.mul(&t, &i);
352 let h3_in = h3;
353 h3.mul(&h3_in, &s1);
354 self.y.add_assign(&h3);
355 }
356
357 pub fn rescale(&mut self, s: &FieldElement) {
359 debug_assert!(!s.normalizes_to_zero_var());
360 let mut zz = FieldElement::zero();
361 zz.sqr(s);
362 let x = self.x;
363 let y = self.y;
364 let z = self.z;
365 self.x.mul(&x, &zz);
366 self.y.mul(&y, &zz);
367 let y_zz = self.y;
368 self.y.mul(&y_zz, s);
369 self.z.mul(&z, s);
370 }
371
372 #[inline(always)]
374 pub fn add_zinv_var(&mut self, a: &Gej, b: &Ge, bzinv: &FieldElement) {
375 if a.infinity {
376 self.infinity = b.infinity;
377 if !b.infinity {
378 let mut bzinv2 = FieldElement::zero();
379 let mut bzinv3 = FieldElement::zero();
380 bzinv2.sqr(bzinv);
381 bzinv3.mul(&bzinv2, bzinv);
382 self.x.mul(&b.x, &bzinv2);
383 self.y.mul(&b.y, &bzinv3);
384 self.z.set_int(1);
385 }
386 return;
387 }
388 if b.infinity {
389 *self = *a;
390 return;
391 }
392 let mut az = FieldElement::zero();
393 az.mul(&a.z, bzinv);
394 let mut z12 = FieldElement::zero();
395 z12.sqr(&az);
396 let u1 = a.x;
397 let mut u2 = FieldElement::zero();
398 u2.mul(&b.x, &z12);
399 let s1 = a.y;
400 let mut s2 = FieldElement::zero();
401 s2.mul(&b.y, &z12);
402 let s2_in = s2;
403 s2.mul(&s2_in, &az);
404 let mut h = FieldElement::zero();
405 h.negate(&u1, 4);
406 h.add_assign(&u2);
407 let mut i = FieldElement::zero();
408 i.negate(&s2, 1);
409 i.add_assign(&s1);
410 if h.normalizes_to_zero_var() {
411 if i.normalizes_to_zero_var() {
412 self.double_var(a);
413 } else {
414 self.set_infinity();
415 }
416 return;
417 }
418 self.infinity = false;
419 self.z.mul(&a.z, &h);
420 let mut h2 = FieldElement::zero();
421 h2.sqr(&h);
422 let h2_in = h2;
423 h2.negate(&h2_in, 1);
424 let mut h3 = FieldElement::zero();
425 h3.mul(&h2, &h);
426 let mut t = FieldElement::zero();
427 t.mul(&u1, &h2);
428 self.x.sqr(&i);
429 self.x.add_assign(&h3);
430 self.x.add_assign(&t);
431 self.x.add_assign(&t);
432 t.add_assign(&self.x);
433 self.y.mul(&t, &i);
434 let h3_in = h3;
435 h3.mul(&h3_in, &s1);
436 self.y.add_assign(&h3);
437 }
438
439 #[inline(always)]
441 pub fn add_ge_var_rzr(&mut self, a: &Gej, b: &Ge, rzr: Option<&mut FieldElement>) {
442 if a.infinity {
443 if let Some(rzr) = rzr {
444 rzr.set_int(1);
445 }
446 self.set_ge(b);
447 return;
448 }
449 if b.infinity {
450 if let Some(rzr) = rzr {
451 rzr.set_int(0);
452 }
453 *self = *a;
454 return;
455 }
456
457 let mut z12 = FieldElement::zero();
458 let u1 = a.x;
459 let mut u2 = FieldElement::zero();
460 let s1 = a.y;
461 let mut s2 = FieldElement::zero();
462 let mut h = FieldElement::zero();
463 let mut i = FieldElement::zero();
464 let mut h2 = FieldElement::zero();
465 let mut h3 = FieldElement::zero();
466 let mut t = FieldElement::zero();
467
468 z12.sqr(&a.z);
469 u2.mul(&b.x, &z12);
470 s2.mul(&b.y, &z12);
471 let s2_in = s2;
472 s2.mul(&s2_in, &a.z);
473 h.negate(&u1, 4); h.add_assign(&u2);
475 i.negate(&s2, 1);
476 i.add_assign(&s1);
477
478 if h.normalizes_to_zero_var() {
479 if let Some(rzr) = rzr {
480 rzr.set_int(0);
481 }
482 if i.normalizes_to_zero_var() {
483 self.double_var(a);
484 } else {
485 self.set_infinity();
486 }
487 return;
488 }
489
490 self.infinity = false;
491 if let Some(rzr) = rzr {
492 *rzr = h;
493 }
494 self.z.mul(&a.z, &h);
495 h2.sqr(&h);
496 let h2_in = h2;
497 h2.negate(&h2_in, 1);
498 h3.mul(&h2, &h);
499 t.mul(&u1, &h2);
500 self.x.sqr(&i);
501 self.x.add_assign(&h3);
502 self.x.add_assign(&t);
503 self.x.add_assign(&t);
504 t.add_assign(&self.x);
505 self.y.mul(&t, &i);
506 let h3_in = h3;
507 h3.mul(&h3_in, &s1);
508 self.y.add_assign(&h3);
509 }
510
511 #[inline(always)]
512 pub fn add_ge_var(&mut self, a: &Gej, b: &Ge) {
513 self.add_ge_var_rzr(a, b, None);
514 }
515
516 pub fn eq_x_var(&self, x: &FieldElement) -> bool {
519 debug_assert!(!self.infinity);
520 let mut z2 = FieldElement::zero();
521 z2.sqr(&self.z);
522 let mut r = FieldElement::zero();
523 r.mul(&z2, x);
524 FieldElement::fe_equal(&r, &self.x)
525 }
526
527 pub fn double_ct(&mut self, a: &Gej) {
530 let mut l = FieldElement::zero();
531 let mut s = FieldElement::zero();
532 let mut t = FieldElement::zero();
533 self.infinity = a.infinity;
534 self.z.mul(&a.z, &a.y);
535 s.sqr(&a.y);
536 l.sqr(&a.x);
537 l.mul_int(3);
538 l.half();
539 t.negate(&s, 1);
540 let t_in = t;
541 t.mul(&t_in, &a.x);
542 self.x.sqr(&l);
543 self.x.add_assign(&t);
544 self.x.add_assign(&t);
545 let s_in = s;
546 s.sqr(&s_in);
547 t.add_assign(&self.x);
548 self.y.mul(&t, &l);
549 self.y.add_assign(&s);
550 let y_in = self.y;
551 self.y.negate(&y_in, 2);
552 self.infinity = a.infinity;
553 }
554
555 pub fn add_ge(&mut self, a: &Gej, b: &Ge) {
558 debug_assert!(!b.infinity);
559 let mut zz = FieldElement::zero();
560 zz.sqr(&a.z);
561 let u1 = a.x;
562 let mut u2 = FieldElement::zero();
563 u2.mul(&b.x, &zz);
564 let s1 = a.y;
565 let mut s2 = FieldElement::zero();
566 let mut rr = FieldElement::zero();
567 let mut m_alt = FieldElement::zero();
568 let mut tt = FieldElement::zero();
569 s2.mul(&b.y, &zz);
570 let s2_in = s2;
571 s2.mul(&s2_in, &a.z);
572 let mut t = u1;
573 t.add_assign(&u2);
574 let mut m = s1;
575 m.add_assign(&s2);
576 rr.sqr(&t);
577 m_alt.negate(&u2, 1);
578 tt.mul(&u1, &m_alt);
579 rr.add_assign(&tt);
580 let degenerate = m.normalizes_to_zero();
581 let mut rr_alt = s1;
582 rr_alt.mul_int(2);
583 m_alt.add_assign(&u1);
584 let not_deg = !degenerate as u8;
585 rr_alt.cmov(&rr, Choice::from(not_deg));
586 m_alt.cmov(&m, Choice::from(not_deg));
587 let mut n = FieldElement::zero();
588 n.sqr(&m_alt);
589 let mut q = FieldElement::zero();
590 q.negate(&t, 5);
591 let q0 = q;
592 q.mul(&q0, &n);
593 n.sqr_assign();
594 n.cmov(&m, Choice::from(degenerate as u8));
595 t.sqr(&rr_alt);
596 self.z.mul(&a.z, &m_alt);
597 t.add_assign(&q);
598 self.x = t;
599 t.mul_int(2);
600 t.add_assign(&q);
601 let t0 = t;
602 t.mul(&t0, &rr_alt);
603 t.add_assign(&n);
604 self.y.negate(&t, 5);
605 self.y.half();
606 self.x.cmov(&b.x, Choice::from(a.infinity as u8));
607 self.y.cmov(&b.y, Choice::from(a.infinity as u8));
608 let mut one = FieldElement::zero();
609 one.set_int(1);
610 self.z.cmov(&one, Choice::from(a.infinity as u8));
611 self.infinity = self.z.normalizes_to_zero();
612 }
613}
614
615pub fn ge_set_all_gej_var(r: &mut [Ge], a: &[Gej]) {
618 let len = r.len().min(a.len());
619 let mut last_i: Option<usize> = None;
620
621 for i in 0..len {
622 if a[i].infinity {
623 r[i].set_infinity();
624 } else {
625 if let Some(li) = last_i {
626 let r_li_x = r[li].x;
627 let a_i_z = a[i].z;
628 r[i].x.mul(&r_li_x, &a_i_z);
629 } else {
630 r[i].x = a[i].z;
631 }
632 r[i].infinity = false; last_i = Some(i);
634 }
635 }
636
637 let Some(mut last_i) = last_i else {
638 return;
639 };
640
641 let mut u = FieldElement::zero();
642 u.inv(&r[last_i].x);
643
644 let mut i = last_i;
645 while i > 0 {
646 i -= 1;
647 if !a[i].infinity {
648 let r_i_x = r[i].x;
649 r[last_i].x.mul(&r_i_x, &u);
650 let u_in = u;
651 let a_last_z = a[last_i].z;
652 u.mul(&u_in, &a_last_z);
653 last_i = i;
654 }
655 }
656 r[last_i].x = u;
657
658 for i in 0..len {
659 if !a[i].infinity {
660 let zi = r[i].x;
661 r[i].set_gej_zinv(&a[i], &zi);
662 }
663 }
664}
665
666#[inline(always)]
669pub fn ge_table_set_globalz(len: usize, pre_a: &mut [Ge], zr: &[FieldElement]) {
670 if len == 0 {
671 return;
672 }
673 let mut i = len - 1;
674 pre_a[i].y.normalize_weak();
675 let mut zs = zr[i];
676 while i > 0 {
677 if i != len - 1 {
678 let zs_in = zs;
679 zs.mul(&zs_in, &zr[i]);
680 }
681 i -= 1;
682 let ai = pre_a[i];
683 pre_a[i].set_ge_zinv(&ai, &zs);
684 }
685}
686
687pub fn generator_g() -> Ge {
689 *GENERATOR_G.get_or_init(|| {
690 let gx = [
691 0x79, 0xbe, 0x66, 0x7e, 0xf9, 0xdc, 0xbb, 0xac, 0x55, 0xa0, 0x62, 0x95, 0xce, 0x87,
692 0x0b, 0x07, 0x02, 0x9b, 0xfc, 0xdb, 0x2d, 0xce, 0x28, 0xd9, 0x59, 0xf2, 0x81, 0x5b,
693 0x16, 0xf8, 0x17, 0x98,
694 ];
695 let gy = [
696 0x48, 0x3a, 0xda, 0x77, 0x26, 0xa3, 0xc4, 0x65, 0x5d, 0xa4, 0xfb, 0xfc, 0x0e, 0x11,
697 0x08, 0xa8, 0xfd, 0x17, 0xb4, 0x48, 0xa6, 0x85, 0x54, 0x19, 0x9c, 0x47, 0xd0, 0x8f,
698 0xfb, 0x10, 0xd4, 0xb8,
699 ];
700 let mut x = FieldElement::zero();
701 let mut y = FieldElement::zero();
702 x.set_b32_mod(&gx);
703 y.set_b32_mod(&gy);
704 let mut g = Ge {
705 x: FieldElement::zero(),
706 y: FieldElement::zero(),
707 infinity: false,
708 };
709 g.set_xy(&x, &y);
710 g
711 })
712}
713
714static GENERATOR_G: OnceLock<Ge> = OnceLock::new();