snarkvm_curves/traits/
group.rs

1// Copyright (c) 2019-2025 Provable Inc.
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16use crate::{PairingEngine, templates::short_weierstrass_jacobian};
17use snarkvm_fields::{Field, PrimeField, SquareRootField, Zero};
18use snarkvm_utilities::{FromBytes, ToBytes, rand::Uniform, serialize::*};
19
20use core::{
21    fmt::{Debug, Display},
22    hash::Hash,
23    iter,
24    ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
25};
26use serde::{Serialize, de::DeserializeOwned};
27
28/// Projective representation of an elliptic curve point guaranteed to be in the prime order subgroup.
29pub trait ProjectiveCurve:
30    CanonicalSerialize
31    + CanonicalDeserialize
32    + Copy
33    + Clone
34    + Debug
35    + Display
36    + Default
37    + FromBytes
38    + Send
39    + Sync
40    + 'static
41    + Eq
42    + Hash
43    + Neg<Output = Self>
44    + Uniform
45    + Zero
46    + Add<Self, Output = Self>
47    + Sub<Self, Output = Self>
48    + Mul<Self::ScalarField, Output = Self>
49    + AddAssign<Self>
50    + SubAssign<Self>
51    + MulAssign<Self::ScalarField>
52    + for<'a> Add<&'a Self, Output = Self>
53    + for<'a> Sub<&'a Self, Output = Self>
54    + for<'a> AddAssign<&'a Self>
55    + for<'a> SubAssign<&'a Self>
56    + PartialEq<Self::Affine>
57    + Sized
58    + ToBytes
59    + iter::Sum
60    + From<<Self as ProjectiveCurve>::Affine>
61{
62    type Affine: AffineCurve<Projective = Self, ScalarField = Self::ScalarField> + From<Self> + Into<Self>;
63    type BaseField: Field;
64    type ScalarField: PrimeField + SquareRootField + Into<<Self::ScalarField as PrimeField>::BigInteger>;
65
66    /// Returns a fixed generator of unknown exponent.
67    #[must_use]
68    fn prime_subgroup_generator() -> Self;
69
70    /// Normalizes a slice of projective elements so that
71    /// conversion to affine is cheap.
72    fn batch_normalization(v: &mut [Self]);
73
74    /// Normalizes a slice of projective elements and outputs a vector
75    /// containing the affine equivalents.
76    fn batch_normalization_into_affine(mut v: Vec<Self>) -> Vec<Self::Affine> {
77        Self::batch_normalization(&mut v);
78        v.into_iter().map(|v| v.into()).collect()
79    }
80
81    /// Checks if the point is already "normalized" so that
82    /// cheap affine conversion is possible.
83    #[must_use]
84    fn is_normalized(&self) -> bool;
85
86    /// Adds an affine element to this element.
87    fn add_assign_mixed(&mut self, other: &Self::Affine);
88
89    /// Adds an affine element to this element.
90    fn add_mixed(&self, other: &Self::Affine) -> Self {
91        let mut copy = *self;
92        copy.add_assign_mixed(other);
93        copy
94    }
95
96    /// Adds an affine element to this element.
97    fn sub_assign_mixed(&mut self, other: &Self::Affine) {
98        self.add_assign_mixed(&-*other);
99    }
100
101    /// Returns `self + self`.
102    #[must_use]
103    fn double(&self) -> Self;
104
105    /// Sets `self := self + self`.
106    fn double_in_place(&mut self);
107
108    /// Converts this element into its affine representation.
109    #[must_use]
110    #[allow(clippy::wrong_self_convention)]
111    fn to_affine(&self) -> Self::Affine;
112}
113
114/// Affine representation of an elliptic curve point guaranteed to be
115/// in the correct prime order subgroup.
116#[allow(clippy::wrong_self_convention)]
117pub trait AffineCurve:
118    CanonicalSerialize
119    + CanonicalDeserialize
120    + Copy
121    + Clone
122    + Debug
123    + Display
124    + Default
125    + FromBytes
126    + Send
127    + Sync
128    + 'static
129    + Eq
130    + Hash
131    + Neg<Output = Self>
132    + Uniform
133    + PartialEq<Self::Projective>
134    + Mul<Self::ScalarField, Output = Self::Projective>
135    + Sized
136    + Serialize
137    + DeserializeOwned
138    + ToBytes
139    + From<<Self as AffineCurve>::Projective>
140    + Zero
141{
142    type Projective: ProjectiveCurve<Affine = Self, ScalarField = Self::ScalarField> + From<Self> + Into<Self>;
143    type BaseField: Field + SquareRootField;
144    type ScalarField: PrimeField + SquareRootField + Into<<Self::ScalarField as PrimeField>::BigInteger>;
145    type Coordinates;
146
147    /// Initializes a new affine group element from the given coordinates.
148    fn from_coordinates(coordinates: Self::Coordinates) -> Option<Self>;
149
150    /// Initializes a new affine group element from the given coordinates.
151    /// Note: The resulting point is **not** enforced to be on the curve or in the correct subgroup.
152    fn from_coordinates_unchecked(coordinates: Self::Coordinates) -> Self;
153
154    /// Returns the cofactor of the curve.
155    fn cofactor() -> &'static [u64];
156
157    /// Returns a fixed generator of unknown exponent.
158    #[must_use]
159    fn prime_subgroup_generator() -> Self;
160
161    /// Attempts to construct an affine point given an x-coordinate. The
162    /// point is not guaranteed to be in the prime order subgroup.
163    ///
164    /// If and only if `greatest` is set will the lexicographically
165    /// largest y-coordinate be selected.
166    fn from_x_coordinate(x: Self::BaseField, greatest: bool) -> Option<Self>;
167
168    /// Attempts to construct both possible affine points given an x-coordinate.
169    /// Points are not guaranteed to be in the prime order subgroup.
170    ///
171    /// The affine points returned should be in lexicographically growing order.
172    ///
173    /// Calling this should be equivalent (but likely more performant) to
174    /// `(AffineCurve::from_x_coordinate(x, false), AffineCurve::from_x_coordinate(x, true))`.
175    fn pair_from_x_coordinate(x: Self::BaseField) -> Option<(Self, Self)>;
176
177    /// Attempts to construct an affine point given a y-coordinate. The
178    /// point is not guaranteed to be in the prime order subgroup.
179    ///
180    /// If and only if `greatest` is set will the lexicographically
181    /// largest y-coordinate be selected.
182    fn from_y_coordinate(y: Self::BaseField, greatest: bool) -> Option<Self>;
183
184    /// Multiply this element by the cofactor and output the
185    /// resulting projective element.
186    #[must_use]
187    fn mul_by_cofactor_to_projective(&self) -> Self::Projective;
188
189    /// Converts this element into its projective representation.
190    #[must_use]
191    fn to_projective(&self) -> Self::Projective;
192
193    /// Returns a group element if the set of bytes forms a valid group element,
194    /// otherwise returns None. This function is primarily intended for sampling
195    /// random group elements from a hash-function or RNG output.
196    fn from_random_bytes(bytes: &[u8]) -> Option<Self>;
197
198    /// Multiply this element by a big-endian boolean representation of
199    /// an integer.
200    fn mul_bits(&self, bits: impl Iterator<Item = bool>) -> Self::Projective;
201
202    /// Multiply this element by the cofactor.
203    #[must_use]
204    fn mul_by_cofactor(&self) -> Self {
205        self.mul_by_cofactor_to_projective().into()
206    }
207
208    /// Multiply this element by the inverse of the cofactor modulo the size of
209    /// `Self::ScalarField`.
210    #[must_use]
211    fn mul_by_cofactor_inv(&self) -> Self;
212
213    /// Checks that the point is in the prime order subgroup given the point on the curve.
214    #[must_use]
215    fn is_in_correct_subgroup_assuming_on_curve(&self) -> bool;
216
217    /// Returns the x-coordinate of the point.
218    #[must_use]
219    fn to_x_coordinate(&self) -> Self::BaseField;
220
221    /// Returns the y-coordinate of the point.
222    #[must_use]
223    fn to_y_coordinate(&self) -> Self::BaseField;
224
225    /// Checks that the current point is on the elliptic curve.
226    fn is_on_curve(&self) -> bool;
227
228    /// Performs the first half of batch addition in-place.
229    fn batch_add_loop_1(
230        a: &mut Self,
231        b: &mut Self,
232        half: &Self::BaseField, // The value 2.inverse().
233        inversion_tmp: &mut Self::BaseField,
234    );
235
236    /// Performs the second half of batch addition in-place.
237    fn batch_add_loop_2(a: &mut Self, b: Self, inversion_tmp: &mut Self::BaseField);
238}
239
240pub trait PairingCurve: AffineCurve {
241    type Engine: PairingEngine<Fr = Self::ScalarField>;
242    type Prepared: CanonicalSerialize
243        + CanonicalDeserialize
244        + ToBytes
245        + FromBytes
246        + PartialEq
247        + Eq
248        + Default
249        + Clone
250        + Send
251        + Sync
252        + Debug
253        + 'static;
254    type PairWith: PairingCurve<PairWith = Self>;
255    type PairingResult: Field;
256
257    /// Prepares this element for pairing purposes.
258    #[must_use]
259    fn prepare(&self) -> Self::Prepared;
260
261    /// Perform a pairing
262    #[must_use]
263    fn pairing_with(&self, other: &Self::PairWith) -> Self::PairingResult;
264}
265
266pub trait ModelParameters: 'static + Copy + Clone + Debug + PartialEq + Eq + Hash + Send + Sync + Sized {
267    type BaseField: Field + SquareRootField;
268    type ScalarField: PrimeField + SquareRootField + Into<<Self::ScalarField as PrimeField>::BigInteger>;
269}
270
271pub trait ShortWeierstrassParameters: ModelParameters {
272    /// The coefficient `A` of the short Weierstrass curve.
273    const WEIERSTRASS_A: Self::BaseField;
274    /// The coefficient `B` of the short Weierstrass curve.
275    const WEIERSTRASS_B: Self::BaseField;
276    /// The cofactor of the short Weierstrass curve.
277    const COFACTOR: &'static [u64];
278    /// The cofactor inverse of the short Weierstrass curve.
279    const COFACTOR_INV: Self::ScalarField;
280    /// The affine generator of the short Weierstrass curve.
281    const AFFINE_GENERATOR_COEFFS: (Self::BaseField, Self::BaseField);
282
283    const PHI: Self::BaseField;
284
285    // Decomposition parameters
286    /// Q1 = x^2 * R / q
287    const Q1: [u64; 4] = [9183663392111466540, 12968021215939883360, 3, 0];
288    /// Q2 = R / q = 13
289    const Q2: [u64; 4] = [13, 0, 0, 0];
290    /// B1 = x^2 - 1
291    const B1: Self::ScalarField;
292    /// B2 = x^2
293    const B2: Self::ScalarField;
294    /// R128 = 2^128 - 1
295    const R128: Self::ScalarField;
296    /// HALF_R = 2^256 / 2
297    const HALF_R: [u64; 8] = [0, 0, 0, 0x8000000000000000, 0, 0, 0, 0];
298
299    #[inline(always)]
300    fn mul_by_a(elem: &Self::BaseField) -> Self::BaseField {
301        let mut copy = *elem;
302        copy *= &Self::WEIERSTRASS_A;
303        copy
304    }
305
306    #[inline(always)]
307    fn add_b(elem: &Self::BaseField) -> Self::BaseField {
308        let mut copy = *elem;
309        copy += &Self::WEIERSTRASS_B;
310        copy
311    }
312
313    fn is_in_correct_subgroup_assuming_on_curve(p: &short_weierstrass_jacobian::Affine<Self>) -> bool;
314
315    fn glv_endomorphism(p: short_weierstrass_jacobian::Affine<Self>) -> short_weierstrass_jacobian::Affine<Self>;
316
317    fn mul_projective(
318        p: short_weierstrass_jacobian::Projective<Self>,
319        by: Self::ScalarField,
320    ) -> short_weierstrass_jacobian::Projective<Self>;
321}
322
323pub trait TwistedEdwardsParameters: ModelParameters {
324    /// The coefficient `A` of the twisted Edwards curve.
325    const EDWARDS_A: Self::BaseField;
326    /// The coefficient `D` of the twisted Edwards curve.
327    const EDWARDS_D: Self::BaseField;
328    /// The cofactor of the twisted Edwards curve.
329    const COFACTOR: &'static [u64];
330    /// The cofactor inverse of the twisted Edwards curve.
331    const COFACTOR_INV: Self::ScalarField;
332    /// The affine generator of the twisted Edwards curve.
333    const AFFINE_GENERATOR_COEFFS: (Self::BaseField, Self::BaseField);
334
335    type MontgomeryParameters: MontgomeryParameters<BaseField = Self::BaseField>;
336
337    #[inline(always)]
338    fn mul_by_a(elem: &Self::BaseField) -> Self::BaseField {
339        let mut copy = *elem;
340        copy *= &Self::EDWARDS_A;
341        copy
342    }
343}
344
345pub trait MontgomeryParameters: ModelParameters {
346    /// The coefficient `A` of the Montgomery curve.
347    const MONTGOMERY_A: Self::BaseField;
348    /// The coefficient `B` of the Montgomery curve.
349    const MONTGOMERY_B: Self::BaseField;
350
351    type TwistedEdwardsParameters: TwistedEdwardsParameters<BaseField = Self::BaseField>;
352}
snarkvm_curves/traits/group.rs

snarkvm_curves/traits/
group.rs
