halo2curves/curve.rs
1//! This module contains the `Curve`/`CurveAffine` abstractions that allow us to
2//! write code that generalizes over a pair of groups.
3
4use core::ops::{Add, Mul, Sub};
5
6use group::prime::{PrimeCurve, PrimeCurveAffine};
7use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
8
9/// This trait is a common interface for dealing with elements of an elliptic
10/// curve group in a "projective" form, where that arithmetic is usually more
11/// efficient.
12///
13/// Requires the `alloc` feature flag because of `hash_to_curve`.
14pub trait CurveExt:
15 PrimeCurve<Affine = <Self as CurveExt>::AffineExt>
16 + group::Group<Scalar = <Self as CurveExt>::ScalarExt>
17 + Default
18 + ConditionallySelectable
19 + ConstantTimeEq
20 + From<<Self as PrimeCurve>::Affine>
21{
22 /// The scalar field of this elliptic curve.
23 type ScalarExt: ff::WithSmallOrderMulGroup<3>;
24 /// The base field over which this elliptic curve is constructed.
25 type Base: ff::WithSmallOrderMulGroup<3>;
26 /// The affine version of the curve
27 type AffineExt: CurveAffine<CurveExt = Self, ScalarExt = <Self as CurveExt>::ScalarExt>
28 + Mul<Self::ScalarExt, Output = Self>
29 + for<'r> Mul<Self::ScalarExt, Output = Self>;
30
31 /// CURVE_ID used for hash-to-curve.
32 const CURVE_ID: &'static str;
33
34 /// Apply the curve endomorphism by multiplying the x-coordinate
35 /// by an element of multiplicative order 3.
36 fn endo(&self) -> Self;
37
38 /// Return the Jacobian coordinates of this point.
39 fn jacobian_coordinates(&self) -> (Self::Base, Self::Base, Self::Base);
40
41 /// Requests a hasher that accepts messages and returns near-uniformly
42 /// distributed elements in the group, given domain prefix `domain_prefix`.
43 ///
44 /// This method is suitable for use as a random oracle.
45 #[allow(clippy::type_complexity)]
46 fn hash_to_curve<'a>(domain_prefix: &'a str) -> Box<dyn Fn(&[u8]) -> Self + 'a>;
47
48 /// Returns whether or not this element is on the curve; should
49 /// always be true unless an "unchecked" API was used.
50 fn is_on_curve(&self) -> Choice;
51
52 /// Returns the curve constant a.
53 fn a() -> Self::Base;
54
55 /// Returns the curve constant b.
56 fn b() -> Self::Base;
57
58 /// Obtains a point given Jacobian coordinates $X : Y : Z$, failing
59 /// if the coordinates are not on the curve.
60 fn new_jacobian(x: Self::Base, y: Self::Base, z: Self::Base) -> CtOption<Self>;
61}
62/// This trait is the affine counterpart to `Curve` and is used for
63/// serialization, storage in memory, and inspection of $x$ and $y$ coordinates.
64///
65/// Requires the `alloc` feature flag because of `hash_to_curve` on
66/// [`CurveExt`].
67pub trait CurveAffine:
68 PrimeCurveAffine<
69 Scalar = <Self as CurveAffine>::ScalarExt,
70 Curve = <Self as CurveAffine>::CurveExt,
71 > + Default
72 + Add<Output = <Self as PrimeCurveAffine>::Curve>
73 + Sub<Output = <Self as PrimeCurveAffine>::Curve>
74 + ConditionallySelectable
75 + ConstantTimeEq
76 + From<<Self as PrimeCurveAffine>::Curve>
77{
78 /// The scalar field of this elliptic curve.
79 type ScalarExt: ff::WithSmallOrderMulGroup<3> + Ord;
80 /// The base field over which this elliptic curve is constructed.
81 type Base: ff::WithSmallOrderMulGroup<3> + Ord;
82 /// The projective form of the curve
83 type CurveExt: CurveExt<AffineExt = Self, ScalarExt = <Self as CurveAffine>::ScalarExt>;
84
85 /// Gets the coordinates of this point.
86 ///
87 /// Returns None if this is the identity.
88 fn coordinates(&self) -> CtOption<Coordinates<Self>>;
89
90 /// Obtains a point given $(x, y)$, failing if it is not on the
91 /// curve.
92 fn from_xy(x: Self::Base, y: Self::Base) -> CtOption<Self>;
93
94 /// Returns whether or not this element is on the curve; should
95 /// always be true unless an "unchecked" API was used.
96 fn is_on_curve(&self) -> Choice;
97
98 /// Returns the curve constant $a$.
99 fn a() -> Self::Base;
100
101 /// Returns the curve constant $b$.
102 fn b() -> Self::Base;
103}
104
105/// The affine coordinates of a point on an elliptic curve.
106#[derive(Clone, Copy, Debug, Default)]
107pub struct Coordinates<C: CurveAffine> {
108 pub(crate) x: C::Base,
109 pub(crate) y: C::Base,
110}
111
112impl<C: CurveAffine> Coordinates<C> {
113 /// Obtains a `Coordinates` value given $(x, y)$, failing if it is not on
114 /// the curve.
115 pub fn from_xy(x: C::Base, y: C::Base) -> CtOption<Self> {
116 // We use CurveAffine::from_xy to validate the coordinates.
117 C::from_xy(x, y).map(|_| Coordinates { x, y })
118 }
119 /// Returns the x-coordinate.
120 ///
121 /// Equivalent to `Coordinates::u`.
122 pub fn x(&self) -> &C::Base {
123 &self.x
124 }
125
126 /// Returns the y-coordinate.
127 ///
128 /// Equivalent to `Coordinates::v`.
129 pub fn y(&self) -> &C::Base {
130 &self.y
131 }
132
133 /// Returns the u-coordinate.
134 ///
135 /// Equivalent to `Coordinates::x`.
136 pub fn u(&self) -> &C::Base {
137 &self.x
138 }
139
140 /// Returns the v-coordinate.
141 ///
142 /// Equivalent to `Coordinates::y`.
143 pub fn v(&self) -> &C::Base {
144 &self.y
145 }
146}
147
148impl<C: CurveAffine> ConditionallySelectable for Coordinates<C> {
149 fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
150 Coordinates {
151 x: C::Base::conditional_select(&a.x, &b.x, choice),
152 y: C::Base::conditional_select(&a.y, &b.y, choice),
153 }
154 }
155}