halo2curves_axiom/derive/
curve.rs

Help
1#[macro_export]
2macro_rules! endo {
3    ($name:ident, $field:ident, $params:expr) => {
4        impl CurveEndo for $name {
5            fn decompose_scalar(k: &$field) -> (u128, bool, u128, bool) {
6                let to_limbs = |e: &$field| {
7                    let repr = e.to_repr();
8                    let repr = repr.as_ref();
9                    let tmp0 = u64::from_le_bytes(repr[0..8].try_into().unwrap());
10                    let tmp1 = u64::from_le_bytes(repr[8..16].try_into().unwrap());
11                    let tmp2 = u64::from_le_bytes(repr[16..24].try_into().unwrap());
12                    let tmp3 = u64::from_le_bytes(repr[24..32].try_into().unwrap());
13                    [tmp0, tmp1, tmp2, tmp3]
14                };
15
16                let get_lower_128 = |e: &$field| {
17                    let e = to_limbs(e);
18                    u128::from(e[0]) | (u128::from(e[1]) << 64)
19                };
20
21                let is_neg = |e: &$field| {
22                    let e = to_limbs(e);
23                    let (_, borrow) = sbb(0xffffffffffffffff, e[0], 0);
24                    let (_, borrow) = sbb(0xffffffffffffffff, e[1], borrow);
25                    let (_, borrow) = sbb(0xffffffffffffffff, e[2], borrow);
26                    let (_, borrow) = sbb(0x00, e[3], borrow);
27                    borrow & 1 != 0
28                };
29
30                let input = to_limbs(&k);
31                let c1 = mul_512($params.gamma2, input);
32                let c2 = mul_512($params.gamma1, input);
33                let c1 = [c1[4], c1[5], c1[6], c1[7]];
34                let c2 = [c2[4], c2[5], c2[6], c2[7]];
35                let q1 = mul_512(c1, $params.b1);
36                let q2 = mul_512(c2, $params.b2);
37                let q1 = $field::from_raw([q1[0], q1[1], q1[2], q1[3]]);
38                let q2 = $field::from_raw([q2[0], q2[1], q2[2], q2[3]]);
39                let k2 = q2 - q1;
40                let k1 = k + k2 * $field::ZETA;
41                let k1_neg = is_neg(&k1);
42                let k2_neg = is_neg(&k2);
43                let k1 = if k1_neg { -k1 } else { k1 };
44                let k2 = if k2_neg { -k2 } else { k2 };
45
46                (get_lower_128(&k1), k1_neg, get_lower_128(&k2), k2_neg)
47            }
48        }
49    };
50}
51
52#[macro_export]
53macro_rules! new_curve_impl {
54    (($($privacy:tt)*),
55    $name:ident,
56    $name_affine:ident,
57    $flags_extra_byte:expr,
58    $base:ident,
59    $scalar:ident,
60    $generator:expr,
61    $constant_a:expr,
62    $constant_b:expr,
63    $curve_id:literal,
64    $hash_to_curve:expr,
65    ) => {
66
67        macro_rules! impl_compressed {
68            () => {
69                paste::paste! {
70
71                #[allow(non_upper_case_globals)]
72                const [< $name _COMPRESSED_SIZE >]: usize = if $flags_extra_byte {$base::size() + 1} else {$base::size()};
73                #[derive(Copy, Clone, PartialEq, Eq)]
74                #[cfg_attr(feature = "derive_serde", derive(Serialize, Deserialize))]
75                pub struct [<$name Compressed >](#[cfg_attr(feature = "derive_serde", serde(with = "serde_arrays"))] [u8; [< $name _COMPRESSED_SIZE >]]);
76
77                // Compressed
78                impl std::fmt::Debug for [< $name Compressed >] {
79                    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
80                        self.0[..].fmt(f)
81                    }
82                }
83
84                impl Default for [< $name Compressed >] {
85                    fn default() -> Self {
86                        [< $name Compressed >]([0; [< $name _COMPRESSED_SIZE >]])
87                    }
88                }
89
90                impl AsRef<[u8]> for [< $name Compressed >] {
91                    fn as_ref(&self) -> &[u8] {
92                        &self.0
93                    }
94                }
95
96                impl AsMut<[u8]> for [< $name Compressed >] {
97                    fn as_mut(&mut self) -> &mut [u8] {
98                        &mut self.0
99                    }
100                }
101
102                impl group::GroupEncoding for $name_affine {
103                    type Repr = [< $name Compressed >];
104
105
106                    fn from_bytes(bytes: &Self::Repr) -> CtOption<Self> {
107                        let bytes = &bytes.0;
108                        let mut tmp = *bytes;
109                        let is_inf = Choice::from(tmp[[< $name _COMPRESSED_SIZE >] - 1] >> 7);
110                        let ysign = Choice::from((tmp[[< $name _COMPRESSED_SIZE >] - 1] >> 6) & 1);
111                        tmp[[< $name _COMPRESSED_SIZE >] - 1] &= 0b0011_1111;
112                        let mut xbytes = [0u8; $base::size()];
113                        xbytes.copy_from_slice(&tmp[ ..$base::size()]);
114
115                        $base::from_bytes(&xbytes).and_then(|x| {
116                            CtOption::new(Self::identity(), x.is_zero() & (is_inf)).or_else(|| {
117                                $name_affine::y2(x).sqrt().and_then(|y| {
118                                    let sign = Choice::from(y.to_bytes()[0] & 1);
119
120                                    let y = $base::conditional_select(&y, &-y, ysign ^ sign);
121
122                                    CtOption::new(
123                                        $name_affine {
124                                            x,
125                                            y,
126                                        },
127                                        Choice::from(1u8),
128                                    )
129                                })
130                            })
131                        })
132                    }
133
134                    fn from_bytes_unchecked(bytes: &Self::Repr) -> CtOption<Self> {
135                        Self::from_bytes(bytes)
136                    }
137
138                    fn to_bytes(&self) -> Self::Repr {
139                        if bool::from(self.is_identity()) {
140                            let mut bytes = [0; [< $name _COMPRESSED_SIZE >]];
141                            bytes[[< $name _COMPRESSED_SIZE >] - 1] |= 0b1000_0000;
142                            [< $name Compressed >](bytes)
143                        } else {
144                            let (x, y) = (self.x, self.y);
145                            let sign = (y.to_bytes()[0] & 1) << 6;
146                            let mut xbytes = [0u8; [< $name _COMPRESSED_SIZE >]];
147                            xbytes[..$base::size()].copy_from_slice(&x.to_bytes());
148                            xbytes[[< $name _COMPRESSED_SIZE >] - 1] |= sign;
149                            [< $name Compressed >](xbytes)
150                        }
151                    }
152                }
153
154                impl GroupEncoding for $name {
155                    type Repr = [< $name Compressed >];
156
157                    fn from_bytes(bytes: &Self::Repr) -> CtOption<Self> {
158                        $name_affine::from_bytes(bytes).map(Self::from)
159                    }
160
161                    fn from_bytes_unchecked(bytes: &Self::Repr) -> CtOption<Self> {
162                        $name_affine::from_bytes(bytes).map(Self::from)
163                    }
164
165                    fn to_bytes(&self) -> Self::Repr {
166                        $name_affine::from(self).to_bytes()
167                    }
168                }
169
170                }
171            };
172        }
173
174        macro_rules! impl_uncompressed {
175            () => {
176
177                paste::paste! {
178
179                #[allow(non_upper_case_globals)]
180                const [< $name _UNCOMPRESSED_SIZE >]: usize = if $flags_extra_byte {
181                    2 * $base::size() + 1
182                } else{
183                    2 *$base::size()
184                };
185                #[derive(Copy, Clone)]
186                pub struct [< $name Uncompressed >]([u8; [< $name _UNCOMPRESSED_SIZE >]]);
187                    impl std::fmt::Debug for [< $name Uncompressed >] {
188                        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
189                            self.0[..].fmt(f)
190                        }
191                    }
192
193                    impl Default for [< $name Uncompressed >] {
194                        fn default() -> Self {
195                            [< $name Uncompressed >]([0; [< $name _UNCOMPRESSED_SIZE >] ])
196                        }
197                    }
198
199                    impl AsRef<[u8]> for [< $name Uncompressed >] {
200                        fn as_ref(&self) -> &[u8] {
201                            &self.0
202                        }
203                    }
204
205                    impl AsMut<[u8]> for [< $name Uncompressed >] {
206                        fn as_mut(&mut self) -> &mut [u8] {
207                            &mut self.0
208                        }
209                    }
210
211                    impl ConstantTimeEq for [< $name Uncompressed >] {
212                        fn ct_eq(&self, other: &Self) -> Choice {
213                            self.0.ct_eq(&other.0)
214                        }
215                    }
216
217                    impl Eq for [< $name Uncompressed >] {}
218
219                    impl PartialEq for [< $name Uncompressed >] {
220                        #[inline]
221                        fn eq(&self, other: &Self) -> bool {
222                            bool::from(self.ct_eq(other))
223                        }
224                    }
225
226                    impl group::UncompressedEncoding for $name_affine{
227                        type Uncompressed = [< $name Uncompressed >];
228
229                        fn from_uncompressed(bytes: &Self::Uncompressed) -> CtOption<Self> {
230                            Self::from_uncompressed_unchecked(bytes).and_then(|p| CtOption::new(p, p.is_on_curve()))
231                        }
232
233                        fn from_uncompressed_unchecked(bytes: &Self::Uncompressed) -> CtOption<Self> {
234                            let bytes = &bytes.0;
235                            let infinity_flag_set = Choice::from((bytes[[< $name _UNCOMPRESSED_SIZE >] - 1] >> 6) & 1);
236                            // Attempt to obtain the x-coordinate
237                            let x = {
238                                let mut tmp = [0; $base::size()];
239                                tmp.copy_from_slice(&bytes[0..$base::size()]);
240                                $base::from_bytes(&tmp)
241                            };
242
243                            // Attempt to obtain the y-coordinate
244                            let y = {
245                                let mut tmp = [0; $base::size()];
246                                tmp.copy_from_slice(&bytes[$base::size()..2*$base::size()]);
247                                $base::from_bytes(&tmp)
248                            };
249
250                            x.and_then(|x| {
251                                y.and_then(|y| {
252                                    // Create a point representing this value
253                                    let p = $name_affine::conditional_select(
254                                        &$name_affine{
255                                            x,
256                                            y,
257                                        },
258                                        &$name_affine::identity(),
259                                        infinity_flag_set,
260                                    );
261
262                                    CtOption::new(
263                                        p,
264                                        // If the infinity flag is set, the x and y coordinates should have been zero.
265                                        ((!infinity_flag_set) | (x.is_zero() & y.is_zero()))
266                                    )
267                                })
268                            })
269                        }
270
271                        fn to_uncompressed(&self) -> Self::Uncompressed {
272                            let mut res = [0; [< $name _UNCOMPRESSED_SIZE >]];
273
274                            res[0..$base::size()].copy_from_slice(
275                                &$base::conditional_select(&self.x, &$base::zero(), self.is_identity()).to_bytes()[..],
276                            );
277                            res[$base::size().. 2*$base::size()].copy_from_slice(
278                                &$base::conditional_select(&self.y, &$base::zero(), self.is_identity()).to_bytes()[..],
279                            );
280
281                            res[[< $name _UNCOMPRESSED_SIZE >] - 1] |= u8::conditional_select(&0u8, &(1u8 << 6), self.is_identity());
282
283                            [< $name Uncompressed >](res)
284                        }
285                    }
286                }
287            };
288
289        }
290
291        /// A macro to help define point serialization using the [`group::GroupEncoding`] trait
292        /// This assumes both point types ($name, $nameaffine) implement [`group::GroupEncoding`].
293        #[cfg(feature = "derive_serde")]
294        macro_rules! serialize_deserialize_to_from_bytes {
295            () => {
296                impl ::serde::Serialize for $name {
297                    fn serialize<S: ::serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
298                        let bytes = &self.to_bytes();
299                        if serializer.is_human_readable() {
300                            ::hex::serde::serialize(&bytes.0, serializer)
301                        } else {
302                            ::serde_arrays::serialize(&bytes.0, serializer)
303                        }
304                    }
305                }
306
307                paste::paste! {
308                    impl<'de> ::serde::Deserialize<'de> for $name {
309                        fn deserialize<D: ::serde::Deserializer<'de>>(
310                            deserializer: D,
311                        ) -> Result<Self, D::Error> {
312                            use ::serde::de::Error as _;
313                            let bytes = if deserializer.is_human_readable() {
314                                ::hex::serde::deserialize(deserializer)?
315                            } else {
316                                ::serde_arrays::deserialize::<_, u8, [< $name _COMPRESSED_SIZE >]>(deserializer)?
317                            };
318                            Option::from(Self::from_bytes(&[< $name Compressed >](bytes))).ok_or_else(|| {
319                                D::Error::custom("deserialized bytes don't encode a valid field element")
320                            })
321                        }
322                    }
323                }
324
325                impl ::serde::Serialize for $name_affine {
326                    fn serialize<S: ::serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
327                        let bytes = &self.to_bytes();
328                        if serializer.is_human_readable() {
329                            ::hex::serde::serialize(&bytes.0, serializer)
330                        } else {
331                            ::serde_arrays::serialize(&bytes.0, serializer)
332                        }
333                    }
334                }
335
336                paste::paste! {
337                    impl<'de> ::serde::Deserialize<'de> for $name_affine {
338                        fn deserialize<D: ::serde::Deserializer<'de>>(
339                            deserializer: D,
340                        ) -> Result<Self, D::Error> {
341                            use ::serde::de::Error as _;
342                            let bytes = if deserializer.is_human_readable() {
343                                ::hex::serde::deserialize(deserializer)?
344                            } else {
345                                ::serde_arrays::deserialize::<_, u8, [< $name _COMPRESSED_SIZE >]>(deserializer)?
346                            };
347                            Option::from(Self::from_bytes(&[< $name Compressed >](bytes))).ok_or_else(|| {
348                                D::Error::custom("deserialized bytes don't encode a valid field element")
349                            })
350                        }
351                    }
352                }
353            };
354        }
355
356        #[derive(Copy, Clone, Debug)]
357        $($privacy)* struct $name {
358            pub x: $base,
359            pub y: $base,
360            pub z: $base,
361        }
362
363        #[derive(Copy, Clone, PartialEq)]
364        $($privacy)* struct $name_affine {
365            pub x: $base,
366            pub y: $base,
367        }
368
369        #[cfg(feature = "derive_serde")]
370        serialize_deserialize_to_from_bytes!();
371
372        impl_compressed!();
373        impl_uncompressed!();
374
375
376
377        impl $name {
378            pub fn generator() -> Self {
379                let generator = $name_affine::generator();
380                Self {
381                    x: generator.x,
382                    y: generator.y,
383                    z: $base::one(),
384                }
385            }
386
387            #[inline]
388            fn curve_constant_3b() -> $base {
389                lazy_static::lazy_static! {
390                    static ref CONST_3B: $base = $constant_b + $constant_b + $constant_b;
391                }
392                *CONST_3B
393            }
394
395            fn mul_by_3b(input: &$base) -> $base {
396                if $name::CURVE_ID == "bn256_g1"{
397                    input.double().double().double() + input
398                } else {
399                    input * $name::curve_constant_3b()
400                }
401            }
402        }
403
404        impl $name_affine {
405            pub fn generator() -> Self {
406                Self {
407                    x: $generator.0,
408                    y: $generator.1,
409                }
410            }
411
412            #[inline(always)]
413            fn y2(x: $base) -> $base {
414                if $constant_a == $base::ZERO {
415                    let x3 = x.square() * x;
416                    (x3 + $constant_b)
417                } else {
418                    let x2 = x.square();
419                    ((x2 + $constant_a) * x + $constant_b)
420                }
421            }
422
423            pub fn random(mut rng: impl RngCore) -> Self {
424                loop {
425                    let x = $base::random(&mut rng);
426                    let ysign = (rng.next_u32() % 2) as u8;
427
428                    let y2 = $name_affine::y2(x);
429                    if let Some(y) = Option::<$base>::from(y2.sqrt()) {
430                        let sign = y.to_bytes()[0] & 1;
431                        let y = if ysign ^ sign == 0 { y } else { -y };
432
433                        let p = $name_affine {
434                            x,
435                            y,
436                        };
437
438
439                        use $crate::group::cofactor::CofactorGroup;
440                        let p = p.to_curve();
441                        return p.clear_cofactor().to_affine()
442                    }
443                }
444            }
445        }
446
447
448
449        // Jacobian implementations
450
451        impl<'a> From<&'a $name_affine> for $name {
452            fn from(p: &'a $name_affine) -> $name {
453                p.to_curve()
454            }
455        }
456
457        impl From<$name_affine> for $name {
458            fn from(p: $name_affine) -> $name {
459                p.to_curve()
460            }
461        }
462
463        impl Default for $name {
464            fn default() -> $name {
465                $name::identity()
466            }
467        }
468
469        impl subtle::ConstantTimeEq for $name {
470            fn ct_eq(&self, other: &Self) -> Choice {
471                // Is (x, y, z) equal to (x', y, z') when converted to affine?
472                // => (x/z , y/z) equal to (x'/z' , y'/z')
473                // => (xz' == x'z) & (yz' == y'z)
474
475                let x1 = self.x * other.z;
476                let y1 = self.y * other.z;
477
478                let x2 = other.x * self.z;
479                let y2 = other.y * self.z;
480
481                let self_is_zero = self.is_identity();
482                let other_is_zero = other.is_identity();
483
484                (self_is_zero & other_is_zero) // Both point at infinity
485                            | ((!self_is_zero) & (!other_is_zero) & x1.ct_eq(&x2) & y1.ct_eq(&y2))
486                // Neither point at infinity, coordinates are the same
487            }
488
489        }
490
491        impl subtle::ConditionallySelectable for $name {
492            fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
493                $name {
494                    x: $base::conditional_select(&a.x, &b.x, choice),
495                    y: $base::conditional_select(&a.y, &b.y, choice),
496                    z: $base::conditional_select(&a.z, &b.z, choice),
497                }
498            }
499        }
500
501        impl PartialEq for $name {
502            fn eq(&self, other: &Self) -> bool {
503                self.ct_eq(other).into()
504            }
505        }
506
507        impl cmp::Eq for $name {}
508
509        impl CurveExt for $name {
510
511            type ScalarExt = $scalar;
512            type Base = $base;
513            type AffineExt = $name_affine;
514
515            const CURVE_ID: &'static str = $curve_id;
516
517            fn endo(&self) -> Self {
518                Self {
519                    x: self.x * Self::Base::ZETA,
520                    y: self.y,
521                    z: self.z,
522                }
523            }
524
525            fn jacobian_coordinates(&self) -> ($base, $base, $base) {
526                // Homogenous to Jacobian
527                let x = self.x * self.z;
528                let y = self.y * self.z.square();
529                (x, y, self.z)
530            }
531
532
533            #[allow(clippy::redundant_closure_call)]
534            fn hash_to_curve<'a>(domain_prefix: &'a str) -> Box<dyn Fn(&[u8]) -> Self + 'a> {
535                $hash_to_curve($curve_id, domain_prefix)
536            }
537
538            fn is_on_curve(&self) -> Choice {
539                if $constant_a == $base::ZERO {
540                    // Check (Y/Z)^2 = (X/Z)^3 + b
541                    // <=>    Z Y^2 - X^3 = Z^3 b
542
543                    (self.z * self.y.square() - self.x.square() * self.x)
544                        .ct_eq(&(self.z.square() * self.z * $constant_b))
545                        | self.z.is_zero()
546                } else {
547                    // Check (Y/Z)^2 = (X/Z)^3 + a(X/Z) + b
548                    // <=>    Z Y^2 - X^3 - a(X Z^2) = Z^3 b
549
550                    let z2 = self.z.square();
551                    (self.z * self.y.square() - (self.x.square() + $constant_a * z2) * self.x)
552                        .ct_eq(&(z2 * self.z * $constant_b))
553                        | self.z.is_zero()
554                }
555            }
556
557            fn b() -> Self::Base {
558                $constant_b
559            }
560
561            fn a() -> Self::Base {
562                $constant_a
563            }
564
565            fn new_jacobian(x: Self::Base, y: Self::Base, z: Self::Base) -> CtOption<Self> {
566                // Jacobian to homogenous
567                let z_inv = z.invert().unwrap_or($base::zero());
568                let p_x = x * z_inv;
569                let p_y = y * z_inv.square();
570                let p = $name {
571                    x:p_x,
572                    y:$base::conditional_select(&p_y, &$base::one(), z.is_zero()),
573                    z
574                };
575                CtOption::new(p, p.is_on_curve())
576            }
577        }
578
579        impl group::Curve for $name {
580
581            type AffineRepr = $name_affine;
582
583            fn batch_normalize(p: &[Self], q: &mut [Self::AffineRepr]) {
584                assert_eq!(p.len(), q.len());
585
586                let mut acc = $base::one();
587                for (p, q) in p.iter().zip(q.iter_mut()) {
588                    // We use the `x` field of $name_affine to store the product
589                    // of previous z-coordinates seen.
590                    q.x = acc;
591
592                    // We will end up skipping all identities in p
593                    acc = $base::conditional_select(&(acc * p.z), &acc, p.is_identity());
594                }
595
596                // This is the inverse, as all z-coordinates are nonzero and the ones
597                // that are not are skipped.
598                acc = acc.invert().unwrap();
599
600                for (p, q) in p.iter().rev().zip(q.iter_mut().rev()) {
601                    let skip = p.is_identity();
602
603                    // Compute tmp = 1/z
604                    let tmp = q.x * acc;
605
606                    // Cancel out z-coordinate in denominator of `acc`
607                    acc = $base::conditional_select(&(acc * p.z), &acc, skip);
608
609                    q.x = p.x * tmp;
610                    q.y = p.y * tmp;
611
612                    *q = $name_affine::conditional_select(&q, &$name_affine::identity(), skip);
613                }
614            }
615
616            fn to_affine(&self) -> Self::AffineRepr {
617                let zinv = self.z.invert().unwrap_or($base::zero());
618                let x = self.x * zinv;
619                let y = self.y * zinv;
620                let tmp = $name_affine {
621                    x,
622                    y,
623                };
624                $name_affine::conditional_select(&tmp, &$name_affine::identity(), zinv.is_zero())
625            }
626        }
627
628        impl group::Group for $name {
629            type Scalar = $scalar;
630
631            fn random(mut rng: impl RngCore) -> Self {
632                $name_affine::random(&mut rng).to_curve()
633            }
634
635            fn double(&self) -> Self {
636                if $constant_a == $base::ZERO {
637                    // Algorithm 9, https://eprint.iacr.org/2015/1060.pdf
638                    let t0 = self.y.square();
639                    let z3 = t0 + t0;
640                    let z3 = z3 + z3;
641                    let z3 = z3 + z3;
642                    let t1 = self.y * self.z;
643                    let t2 = self.z.square();
644                    let t2 = $name::mul_by_3b(&t2);
645                    let x3 = t2 * z3;
646                    let y3 = t0 + t2;
647                    let z3 = t1 * z3;
648                    let t1 = t2 + t2;
649                    let t2 = t1 + t2;
650                    let t0 = t0 - t2;
651                    let y3 = t0 * y3;
652                    let y3 = x3 + y3;
653                    let t1 = self.x * self.y;
654                    let x3 = t0 * t1;
655                    let x3 = x3 + x3;
656
657                    let tmp = $name {
658                        x: x3,
659                        y: y3,
660                        z: z3,
661                    };
662
663                    $name::conditional_select(&tmp, &$name::identity(), self.is_identity())
664                } else {
665                    // Algorithm 3, https://eprint.iacr.org/2015/1060.pdf
666                    let t0 = self.x.square();
667                    let t1 = self.y.square();
668                    let t2 = self.z.square();
669                    let t3 = self.x * self.y;
670                    let t3 = t3 + t3;
671                    let z3 = self.x * self.z;
672                    let z3 = z3 + z3;
673                    let x3 = $constant_a * z3;
674                    let y3 = $name::mul_by_3b(&t2);
675                    let y3 = x3 + y3;
676                    let x3 = t1 - y3;
677                    let y3 = t1 + y3;
678                    let y3 = x3 * y3;
679                    let x3 = t3 * x3;
680                    let z3 = $name::mul_by_3b(&z3);
681                    let t2 = $constant_a * t2;
682                    let t3 = t0 - t2;
683                    let t3 = $constant_a * t3;
684                    let t3 = t3 + z3;
685                    let z3 = t0 + t0;
686                    let t0 = z3 + t0;
687                    let t0 = t0 + t2;
688                    let t0 = t0 * t3;
689                    let y3 = y3 + t0;
690                    let t2 = self.y * self.z;
691                    let t2 = t2 + t2;
692                    let t0 = t2 * t3;
693                    let x3 = x3 - t0;
694                    let z3 = t2 * t1;
695                    let z3 = z3 + z3;
696                    let z3 = z3 + z3;
697
698                    let tmp = $name {
699                        x: x3,
700                        y: y3,
701                        z: z3,
702                    };
703
704                    $name::conditional_select(&tmp, &$name::identity(), self.is_identity())
705                }
706            }
707
708            fn generator() -> Self {
709                $name::generator()
710            }
711
712            fn identity() -> Self {
713                Self {
714                    x: $base::zero(),
715                    y: $base::one(),
716                    z: $base::zero(),
717                }
718            }
719
720            fn is_identity(&self) -> Choice {
721                self.z.is_zero()
722            }
723        }
724
725        impl $crate::serde::SerdeObject for $name {
726            fn from_raw_bytes_unchecked(bytes: &[u8]) -> Self {
727                debug_assert_eq!(bytes.len(), 3 * $base::size());
728                let [x, y, z] = [0, 1, 2]
729                    .map(|i| $base::from_raw_bytes_unchecked(&bytes[i * $base::size()..(i + 1) * $base::size()]));
730                Self { x, y, z }
731            }
732            fn from_raw_bytes(bytes: &[u8]) -> Option<Self> {
733                if bytes.len() != 3 * $base::size() {
734                    return None;
735                }
736                let [x, y, z] =
737                    [0, 1, 2].map(|i| $base::from_raw_bytes(&bytes[i * $base::size()..(i + 1) * $base::size()]));
738                x.zip(y).zip(z).and_then(|((x, y), z)| {
739                    let res = Self { x, y, z };
740                    // Check that the point is on the curve.
741                    bool::from(res.is_on_curve()).then(|| res)
742                })
743            }
744            fn to_raw_bytes(&self) -> Vec<u8> {
745                let mut res = Vec::with_capacity(3 * $base::size());
746                Self::write_raw(self, &mut res).unwrap();
747                res
748            }
749            fn read_raw_unchecked<R: std::io::Read>(reader: &mut R) -> Self {
750                let [x, y, z] = [(); 3].map(|_| $base::read_raw_unchecked(reader));
751                Self { x, y, z }
752            }
753            fn read_raw<R: std::io::Read>(reader: &mut R) -> std::io::Result<Self> {
754                let x = $base::read_raw(reader)?;
755                let y = $base::read_raw(reader)?;
756                let z = $base::read_raw(reader)?;
757                Ok(Self { x, y, z })
758            }
759            fn write_raw<W: std::io::Write>(&self, writer: &mut W) -> std::io::Result<()> {
760                self.x.write_raw(writer)?;
761                self.y.write_raw(writer)?;
762                self.z.write_raw(writer)
763            }
764        }
765
766        impl group::prime::PrimeGroup for $name {}
767
768        impl group::prime::PrimeCurve for $name {
769            type Affine = $name_affine;
770        }
771
772        impl group::cofactor::CofactorCurve for $name {
773            type Affine = $name_affine;
774        }
775
776        // Affine implementations
777
778        impl std::fmt::Debug for $name_affine {
779            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
780                if self.is_identity().into() {
781                    write!(f, "Infinity")
782                } else {
783                    write!(f, "({:?}, {:?})", self.x, self.y)
784                }
785            }
786        }
787
788        impl<'a> From<&'a $name> for $name_affine {
789            fn from(p: &'a $name) -> $name_affine {
790                p.to_affine()
791            }
792        }
793
794        impl From<$name> for $name_affine {
795            fn from(p: $name) -> $name_affine {
796                p.to_affine()
797            }
798        }
799
800        impl Default for $name_affine {
801            fn default() -> $name_affine {
802                $name_affine::identity()
803            }
804        }
805
806        impl subtle::ConstantTimeEq for $name_affine {
807            fn ct_eq(&self, other: &Self) -> Choice {
808                let z1 = self.is_identity();
809                let z2 = other.is_identity();
810
811                (z1 & z2) | ((!z1) & (!z2) & (self.x.ct_eq(&other.x)) & (self.y.ct_eq(&other.y)))
812            }
813        }
814
815        impl subtle::ConditionallySelectable for $name_affine {
816            fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
817                $name_affine {
818                    x: $base::conditional_select(&a.x, &b.x, choice),
819                    y: $base::conditional_select(&a.y, &b.y, choice),
820                }
821            }
822        }
823
824        impl cmp::Eq for $name_affine {}
825
826
827        impl $crate::serde::SerdeObject for $name_affine {
828            fn from_raw_bytes_unchecked(bytes: &[u8]) -> Self {
829                debug_assert_eq!(bytes.len(), 2 * $base::size());
830                let [x, y] =
831                    [0, $base::size()].map(|i| $base::from_raw_bytes_unchecked(&bytes[i..i + $base::size()]));
832                Self { x, y }
833            }
834            fn from_raw_bytes(bytes: &[u8]) -> Option<Self> {
835                if bytes.len() != 2 * $base::size() {
836                    return None;
837                }
838                let [x, y] = [0, $base::size()].map(|i| $base::from_raw_bytes(&bytes[i..i + $base::size()]));
839                x.zip(y).and_then(|(x, y)| {
840                    let res = Self { x, y };
841                    // Check that the point is on the curve.
842                    bool::from(res.is_on_curve()).then(|| res)
843                })
844            }
845            fn to_raw_bytes(&self) -> Vec<u8> {
846                let mut res = Vec::with_capacity(2 * $base::size());
847                Self::write_raw(self, &mut res).unwrap();
848                res
849            }
850            fn read_raw_unchecked<R: std::io::Read>(reader: &mut R) -> Self {
851                let [x, y] = [(); 2].map(|_| $base::read_raw_unchecked(reader));
852                Self { x, y }
853            }
854            fn read_raw<R: std::io::Read>(reader: &mut R) -> std::io::Result<Self> {
855                let x = $base::read_raw(reader)?;
856                let y = $base::read_raw(reader)?;
857                Ok(Self { x, y })
858            }
859            fn write_raw<W: std::io::Write>(&self, writer: &mut W) -> std::io::Result<()> {
860                self.x.write_raw(writer)?;
861                self.y.write_raw(writer)
862            }
863        }
864
865        impl group::prime::PrimeCurveAffine for $name_affine {
866            type Curve = $name;
867            type Scalar = $scalar;
868
869
870            fn generator() -> Self {
871                $name_affine::generator()
872            }
873
874            fn identity() -> Self {
875                Self {
876                    x: $base::zero(),
877                    y: $base::zero(),
878                }
879            }
880
881            fn is_identity(&self) -> Choice {
882                self.x.is_zero() & self.y.is_zero()
883            }
884
885            fn to_curve(&self) -> Self::Curve {
886                let tmp = $name {
887                    x: self.x,
888                    y: self.y,
889                    z: $base::one(),
890                };
891                $name::conditional_select(&tmp, &$name::identity(), self.is_identity())
892            }
893        }
894
895        impl group::cofactor::CofactorCurveAffine for $name_affine {
896            type Curve = $name;
897            type Scalar = $scalar;
898
899            fn identity() -> Self {
900                <Self as group::prime::PrimeCurveAffine>::identity()
901            }
902
903            fn generator() -> Self {
904                <Self as group::prime::PrimeCurveAffine>::generator()
905            }
906
907            fn is_identity(&self) -> Choice {
908                <Self as group::prime::PrimeCurveAffine>::is_identity(self)
909            }
910
911            fn to_curve(&self) -> Self::Curve {
912                <Self as group::prime::PrimeCurveAffine>::to_curve(self)
913            }
914        }
915
916
917        impl CurveAffine for $name_affine {
918            type ScalarExt = $scalar;
919            type Base = $base;
920            type CurveExt = $name;
921
922            fn is_on_curve(&self) -> Choice {
923                if $constant_a == $base::ZERO {
924                    // y^2 - x^3 ?= b
925                    (self.y.square() - self.x.square() * self.x).ct_eq(&$constant_b)
926                        | self.is_identity()
927                } else {
928                    // y^2 - x^3 - ax ?= b
929                    (self.y.square() - (self.x.square() + $constant_a) * self.x).ct_eq(&$constant_b)
930                        | self.is_identity()
931                }
932            }
933
934            fn coordinates(&self) -> CtOption<Coordinates<Self>> {
935                Coordinates::from_xy( self.x, self.y )
936            }
937
938            fn from_xy(x: Self::Base, y: Self::Base) -> CtOption<Self> {
939                let p = $name_affine {
940                    x, y
941                };
942                CtOption::new(p, p.is_on_curve())
943            }
944
945            fn a() -> Self::Base {
946                $constant_a
947            }
948
949            fn b() -> Self::Base {
950                $constant_b
951            }
952        }
953
954        impl CurveAffineExt for $name_affine {
955            fn into_coordinates(self) -> (Self::Base, Self::Base) {
956                (self.x, self.y)
957            }
958        }
959
960        impl_binops_additive!($name, $name);
961        impl_binops_additive!($name, $name_affine);
962        impl_binops_additive_specify_output!($name_affine, $name_affine, $name);
963        impl_binops_additive_specify_output!($name_affine, $name, $name);
964        impl_binops_multiplicative!($name, $scalar);
965        impl_binops_multiplicative_mixed!($name_affine, $scalar, $name);
966
967        impl<'a> Neg for &'a $name {
968            type Output = $name;
969
970            fn neg(self) -> $name {
971                $name {
972                    x: self.x,
973                    y: -self.y,
974                    z: self.z,
975                }
976            }
977        }
978
979        impl Neg for $name {
980            type Output = $name;
981
982            fn neg(self) -> $name {
983                -&self
984            }
985        }
986
987        impl<T> Sum<T> for $name
988        where
989            T: core::borrow::Borrow<$name>,
990        {
991            fn sum<I>(iter: I) -> Self
992            where
993                I: Iterator<Item = T>,
994            {
995                iter.fold(Self::identity(), |acc, item| acc + item.borrow())
996            }
997        }
998
999        impl<'a, 'b> Add<&'a $name> for &'b $name {
1000            type Output = $name;
1001
1002            fn add(self, rhs: &'a $name) -> $name {
1003                if $constant_a == $base::ZERO {
1004                    // Algorithm 7, https://eprint.iacr.org/2015/1060.pdf
1005                    let t0 = self.x * rhs.x;
1006                    let t1 = self.y * rhs.y;
1007                    let t2 = self.z * rhs.z;
1008                    let t3 = self.x + self.y;
1009                    let t4 = rhs.x + rhs.y;
1010                    let t3 = t3 * t4;
1011                    let t4 = t0 + t1;
1012                    let t3 = t3 - t4;
1013                    let t4 = self.y + self.z;
1014                    let x3 = rhs.y + rhs.z;
1015                    let t4 = t4 * x3;
1016                    let x3 = t1 + t2;
1017                    let t4 = t4 - x3;
1018                    let x3 = self.x + self.z;
1019                    let y3 = rhs.x + rhs.z;
1020                    let x3 = x3 * y3;
1021                    let y3 = t0 + t2;
1022                    let y3 = x3 - y3;
1023                    let x3 = t0 + t0;
1024                    let t0 = x3 + t0;
1025                    let t2 = $name::mul_by_3b(&t2);
1026                    let z3 = t1 + t2;
1027                    let t1 = t1 - t2;
1028                    let y3 = $name::mul_by_3b(&y3);
1029                    let x3 = t4 * y3;
1030                    let t2 = t3 * t1;
1031                    let x3 = t2 - x3;
1032                    let y3 = y3 * t0;
1033                    let t1 = t1 * z3;
1034                    let y3 = t1 + y3;
1035                    let t0 = t0 * t3;
1036                    let z3 = z3 * t4;
1037                    let z3 = z3 + t0;
1038
1039                    $name {
1040                        x: x3,
1041                        y: y3,
1042                        z: z3,
1043                    }
1044                } else {
1045                    // Algorithm 1, https://eprint.iacr.org/2015/1060.pdf
1046                    let t0 = self.x * rhs.x;
1047                    let t1 = self.y * rhs.y;
1048                    let t2 = self.z * rhs.z;
1049                    let t3 = self.x + self.y;
1050                    let t4 = rhs.x + rhs.y;
1051                    let t3 = t3 * t4;
1052                    let t4 = t0 + t1;
1053                    let t3 = t3 - t4;
1054                    let t4 = self.x + self.z;
1055                    let t5 = rhs.x + rhs.z;
1056                    let t4 = t4 * t5;
1057                    let t5 = t0 + t2;
1058                    let t4 = t4 - t5;
1059                    let t5 = self.y + self.z;
1060                    let x3 = rhs.y + rhs.z;
1061                    let t5 = t5 * x3;
1062                    let x3 = t1 + t2;
1063                    let t5 = t5 - x3;
1064                    let z3 = $constant_a * t4;
1065                    let x3 = $name::mul_by_3b(&t2);
1066                    let z3 = x3 + z3;
1067                    let x3 = t1 - z3;
1068                    let z3 = t1 + z3;
1069                    let y3 = x3 * z3;
1070                    let t1 = t0 + t0;
1071                    let t1 = t1 + t0;
1072                    let t2 = $constant_a * t2;
1073                    let t4 = $name::mul_by_3b(&t4);
1074                    let t1 = t1 + t2;
1075                    let t2 = t0 - t2;
1076                    let t2 = $constant_a * t2;
1077                    let t4 = t4 + t2;
1078                    let t0 = t1 * t4;
1079                    let y3 = y3 + t0;
1080                    let t0 = t5 * t4;
1081                    let x3 = t3 * x3;
1082                    let x3 = x3 - t0;
1083                    let t0 = t3 * t1;
1084                    let z3 = t5 * z3;
1085                    let z3 = z3 + t0;
1086
1087                    $name {
1088                        x: x3,
1089                        y: y3,
1090                        z: z3,
1091                    }
1092                }
1093            }
1094        }
1095
1096        impl<'a, 'b> Add<&'a $name_affine> for &'b $name {
1097            type Output = $name;
1098
1099            // Mixed addition
1100            fn add(self, rhs: &'a $name_affine) -> $name {
1101                if $constant_a == $base::ZERO {
1102                    // Algorithm 8, https://eprint.iacr.org/2015/1060.pdf
1103                    let t0 = self.x * rhs.x;
1104                    let t1 = self.y * rhs.y;
1105                    let t3 = rhs.x + rhs.y;
1106                    let t4 = self.x + self.y;
1107                    let t3 = t3 * t4;
1108                    let t4 = t0 + t1;
1109                    let t3 = t3 - t4;
1110                    let t4 = rhs.y * self.z;
1111                    let t4 = t4 + self.y;
1112                    let y3 = rhs.x * self.z;
1113                    let y3 = y3 + self.x;
1114                    let x3 = t0 + t0;
1115                    let t0 = x3 + t0;
1116                    let t2 = $name::mul_by_3b(&self.z);
1117                    let z3 = t1 + t2;
1118                    let t1 = t1 - t2;
1119                    let y3 = $name::mul_by_3b(&y3);
1120                    let x3 = t4 * y3;
1121                    let t2 = t3 * t1;
1122                    let x3 = t2 - x3;
1123                    let y3 = y3 * t0;
1124                    let t1 = t1 * z3;
1125                    let y3 = t1 + y3;
1126                    let t0 = t0 * t3;
1127                    let z3 = z3 * t4;
1128                    let z3 = z3 + t0;
1129
1130                    let tmp = $name{
1131                        x: x3,
1132                        y: y3,
1133                        z: z3,
1134                    };
1135
1136                    $name::conditional_select(&tmp, self, rhs.is_identity())
1137                } else {
1138                    // Algorithm 2, https://eprint.iacr.org/2015/1060.pdf
1139                    let t0 = self.x * rhs.x;
1140                    let t1 = self.y * rhs.y;
1141                    let t3 = rhs.x + rhs.y;
1142                    let t4 = self.x + self.y;
1143                    let t3 = t3 * t4;
1144                    let t4 = t0 + t1;
1145                    let t3 = t3 - t4;
1146                    let t4 = rhs.x * self.z;
1147                    let t4 = t4 + self.x;
1148                    let t5 = rhs.y * self.z;
1149                    let t5 = t5 + self.y;
1150                    let z3 = $constant_a * t4;
1151                    let x3 = $name::mul_by_3b(&self.z);
1152                    let z3 = x3 + z3;
1153                    let x3 = t1 - z3;
1154                    let z3 = t1 + z3;
1155                    let y3 = x3 * z3;
1156                    let t1 = t0 + t0;
1157                    let t1 = t1 + t0;
1158                    let t2 = $constant_a * self.z;
1159                    let t4 = $name::mul_by_3b(&t4);
1160                    let t1 = t1 + t2;
1161                    let t2 = t0 - t2;
1162                    let t2 = $constant_a * t2;
1163                    let t4 = t4 + t2;
1164                    let t0 = t1 * t4;
1165                    let y3 = y3 + t0;
1166                    let t0 = t5 * t4;
1167                    let x3 = t3 * x3;
1168                    let x3 = x3 - t0;
1169                    let t0 = t3 * t1;
1170                    let z3 = t5 * z3;
1171                    let z3 = z3 + t0;
1172
1173                    let tmp = $name{
1174                        x: x3,
1175                        y: y3,
1176                        z: z3,
1177                    };
1178
1179                    $name::conditional_select(&tmp, self, rhs.is_identity())
1180                }
1181            }
1182        }
1183
1184        impl<'a, 'b> Sub<&'a $name> for &'b $name {
1185            type Output = $name;
1186
1187            fn sub(self, other: &'a $name) -> $name {
1188                self + (-other)
1189            }
1190        }
1191
1192        impl<'a, 'b> Sub<&'a $name_affine> for &'b $name {
1193            type Output = $name;
1194
1195            fn sub(self, other: &'a $name_affine) -> $name {
1196                self + (-other)
1197            }
1198        }
1199
1200
1201
1202        #[allow(clippy::suspicious_arithmetic_impl)]
1203        impl<'a, 'b> Mul<&'b $scalar> for &'a $name {
1204            type Output = $name;
1205
1206            // This is a simple double-and-add implementation of point
1207            // multiplication, moving from most significant to least
1208            // significant bit of the scalar.
1209
1210            fn mul(self, other: &'b $scalar) -> Self::Output {
1211                let mut acc = $name::identity();
1212                for bit in other
1213                    .to_repr()
1214                    .iter()
1215                    .rev()
1216                    .flat_map(|byte| (0..8).rev().map(move |i| Choice::from((byte >> i) & 1u8)))
1217                {
1218                    acc = acc.double();
1219                    acc = $name::conditional_select(&acc, &(acc + self), bit);
1220                }
1221
1222                acc
1223            }
1224        }
1225
1226        impl<'a> Neg for &'a $name_affine {
1227            type Output = $name_affine;
1228
1229            fn neg(self) -> $name_affine {
1230                $name_affine {
1231                    x: self.x,
1232                    y: -self.y,
1233                }
1234            }
1235        }
1236
1237        impl Neg for $name_affine {
1238            type Output = $name_affine;
1239
1240            fn neg(self) -> $name_affine {
1241                -&self
1242            }
1243        }
1244
1245        impl<'a, 'b> Add<&'a $name> for &'b $name_affine {
1246            type Output = $name;
1247
1248            fn add(self, rhs: &'a $name) -> $name {
1249                rhs + self
1250            }
1251        }
1252
1253        impl<'a, 'b> Add<&'a $name_affine> for &'b $name_affine {
1254            type Output = $name;
1255
1256            fn add(self, rhs: &'a $name_affine) -> $name {
1257                rhs.to_curve() + self.to_curve()
1258            }
1259        }
1260
1261        impl<'a, 'b> Sub<&'a $name_affine> for &'b $name_affine {
1262            type Output = $name;
1263
1264            fn sub(self, other: &'a $name_affine) -> $name {
1265                self + (-other)
1266            }
1267        }
1268
1269        impl<'a, 'b> Sub<&'a $name> for &'b $name_affine {
1270            type Output = $name;
1271
1272            fn sub(self, other: &'a $name) -> $name {
1273                self + (-other)
1274            }
1275        }
1276
1277        #[allow(clippy::suspicious_arithmetic_impl)]
1278        impl<'a, 'b> Mul<&'b $scalar> for &'a $name_affine {
1279            type Output = $name;
1280
1281            fn mul(self, other: &'b $scalar) -> Self::Output {
1282                let mut acc = $name::identity();
1283
1284                // This is a simple double-and-add implementation of point
1285                // multiplication, moving from most significant to least
1286                // significant bit of the scalar.
1287
1288                for bit in other
1289                    .to_repr()
1290                    .iter()
1291                    .rev()
1292                    .flat_map(|byte| (0..8).rev().map(move |i| Choice::from((byte >> i) & 1u8)))
1293                {
1294                    acc = acc.double();
1295                    acc = $name::conditional_select(&acc, &(acc + self), bit);
1296                }
1297
1298                acc
1299            }
1300        }
1301    };
1302}
halo2curves_axiom/derive/curve.rs

halo2curves_axiom/derive/
curve.rs
