snarkvm_circuit_types_group/
lib.rs

1// Copyright 2024 Aleo Network Foundation
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
16#![forbid(unsafe_code)]
17#![allow(clippy::too_many_arguments)]
18#![cfg_attr(test, allow(clippy::assertions_on_result_states))]
19
20mod helpers;
21
22pub mod add;
23pub mod double;
24pub mod equal;
25pub mod mul;
26pub mod neg;
27pub mod sub;
28pub mod ternary;
29
30#[cfg(test)]
31use console::{TestRng, Uniform};
32#[cfg(test)]
33use snarkvm_circuit_environment::{assert_count, assert_output_mode, assert_scope, count, output_mode};
34
35use console::AffineCurve;
36use snarkvm_circuit_environment::prelude::*;
37use snarkvm_circuit_types_boolean::Boolean;
38use snarkvm_circuit_types_field::Field;
39use snarkvm_circuit_types_scalar::Scalar;
40
41#[derive(Clone)]
42pub struct Group<E: Environment> {
43    x: Field<E>,
44    y: Field<E>,
45}
46
47impl<E: Environment> GroupTrait<Scalar<E>> for Group<E> {}
48
49impl<E: Environment> Group<E> {
50    /// Returns the generator of the prime-order subgroup.
51    pub fn generator() -> Self {
52        Group::constant(console::Group::generator())
53    }
54}
55
56#[cfg(feature = "console")]
57impl<E: Environment> Inject for Group<E> {
58    type Primitive = console::Group<E::Network>;
59
60    /// Initializes a new affine group element.
61    ///
62    /// For safety, the resulting point is always enforced to be on the curve with constraints.
63    /// regardless of whether the y-coordinate was recovered.
64    fn new(mode: Mode, group: Self::Primitive) -> Self {
65        // Allocate two new variables for the coordinates, with the mode and values given as inputs.
66        let x = Field::new(mode, group.to_x_coordinate());
67        let y = Field::new(mode, group.to_y_coordinate());
68        // Put the coordinates together into a point.
69        let point = Self { x, y };
70        // Enforce in the circuit that the point is in the group.
71        point.enforce_in_group();
72        // Return the point.
73        point
74    }
75}
76
77impl<E: Environment> Group<E> {
78    /// Enforces that `self` is on the curve.
79    ///
80    /// Ensure ax^2 + y^2 = 1 + dx^2y^2
81    /// by checking that y^2 * (dx^2 - 1) = (ax^2 - 1)
82    pub fn enforce_on_curve(&self) {
83        let a = Field::constant(console::Field::new(E::EDWARDS_A));
84        let d = Field::constant(console::Field::new(E::EDWARDS_D));
85
86        let x2 = self.x.square();
87        let y2 = self.y.square();
88
89        let first = y2;
90        let second = (d * &x2) - &Field::one();
91        let third = (a * x2) - Field::one();
92
93        // Ensure y^2 * (dx^2 - 1) = (ax^2 - 1).
94        E::enforce(|| (first, second, third));
95    }
96}
97
98impl<E: Environment> Group<E> {
99    /// Enforces that `self` is on the curve and in the largest prime-order subgroup.
100    pub fn enforce_in_group(&self) {
101        let self_witness = self.eject_value();
102
103        // Each point in the subgroup is the quadruple of some point on the curve,
104        // where 'quadruple' refers to the cofactor 4 of the curve.
105        // Thus, to enforce that a given point is in the group,
106        // there must exist some point on the curve such that 4 times the latter yields the former.
107        // The point on the curve is existentially quantified,
108        // so the constraints introduce new coordinate variables for that point.
109
110        // For the internal variables of this circuit,
111        // the mode is constant if the input point is constant, otherwise private.
112        let mode = if self.eject_mode().is_constant() { Mode::Constant } else { Mode::Private };
113
114        // Postulate a point (two new R1CS variables) on the curve,
115        // whose witness is the witness of the input point divided by the cofactor.
116        let point_witness = self_witness.div_by_cofactor();
117        let point_x = Field::new(mode, point_witness.to_x_coordinate());
118        let point_y = Field::new(mode, point_witness.to_y_coordinate());
119        let point = Self { x: point_x, y: point_y };
120        point.enforce_on_curve();
121
122        // (For advanced users) The cofactor for this curve is `4`. Thus doubling is used to be performant.
123        debug_assert!(E::Affine::cofactor().len() == 1 && E::Affine::cofactor()[0] == 4);
124
125        // Double the point on the curve.
126        // This introduces two new R1CS variables for the doubled point.
127        let double_point = point.double();
128
129        // Enforce that the input point (self) is double the double of the point on the curve,
130        // i.e. that it is 4 (= cofactor) times the postulated point on the curve.
131        double_point.enforce_double(self);
132    }
133
134    /// Returns a `Boolean` indicating if `self` is in the largest prime-order subgroup,
135    /// assuming that `self` is on the curve.
136    pub fn is_in_group(&self) -> Boolean<E> {
137        // Initialize the order of the subgroup as a bits.
138        let order = E::ScalarField::modulus();
139        let order_bits_be = order.to_bits_be();
140        let mut order_bits_be_constants = Vec::with_capacity(order_bits_be.len());
141        for bit in order_bits_be.iter() {
142            order_bits_be_constants.push(Boolean::constant(*bit));
143        }
144        // Multiply `self` by the order of the subgroup.
145        let self_times_order = order_bits_be_constants.mul(self);
146        // Check if the result is zero.
147        self_times_order.is_zero()
148    }
149}
150
151#[cfg(feature = "console")]
152impl<E: Environment> Eject for Group<E> {
153    type Primitive = console::Group<E::Network>;
154
155    /// Ejects the mode of the group element.
156    fn eject_mode(&self) -> Mode {
157        (&self.x, &self.y).eject_mode()
158    }
159
160    /// Ejects the group as a constant group element.
161    fn eject_value(&self) -> Self::Primitive {
162        console::Group::from_xy_coordinates_unchecked(self.x.eject_value(), self.y.eject_value())
163    }
164}
165
166#[cfg(feature = "console")]
167impl<E: Environment> Parser for Group<E> {
168    /// Parses a string into a group circuit.
169    #[inline]
170    fn parse(string: &str) -> ParserResult<Self> {
171        // Parse the group from the string.
172        let (string, group) = console::Group::parse(string)?;
173        // Parse the mode from the string.
174        let (string, mode) = opt(pair(tag("."), Mode::parse))(string)?;
175
176        match mode {
177            Some((_, mode)) => Ok((string, Group::new(mode, group))),
178            None => Ok((string, Group::new(Mode::Constant, group))),
179        }
180    }
181}
182
183#[cfg(feature = "console")]
184impl<E: Environment> FromStr for Group<E> {
185    type Err = Error;
186
187    /// Parses a string into a group circuit.
188    #[inline]
189    fn from_str(string: &str) -> Result<Self> {
190        match Self::parse(string) {
191            Ok((remainder, object)) => {
192                // Ensure the remainder is empty.
193                ensure!(remainder.is_empty(), "Failed to parse string. Found invalid character in: \"{remainder}\"");
194                // Return the object.
195                Ok(object)
196            }
197            Err(error) => bail!("Failed to parse string. {error}"),
198        }
199    }
200}
201
202#[cfg(feature = "console")]
203impl<E: Environment> TypeName for Group<E> {
204    /// Returns the type name of the circuit as a string.
205    #[inline]
206    fn type_name() -> &'static str {
207        console::Group::<E::Network>::type_name()
208    }
209}
210
211#[cfg(feature = "console")]
212impl<E: Environment> Debug for Group<E> {
213    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
214        Display::fmt(self, f)
215    }
216}
217
218#[cfg(feature = "console")]
219impl<E: Environment> Display for Group<E> {
220    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
221        write!(f, "{}.{}", self.eject_value(), self.eject_mode())
222    }
223}
224
225impl<E: Environment> From<Group<E>> for LinearCombination<E::BaseField> {
226    fn from(group: Group<E>) -> Self {
227        From::from(&group)
228    }
229}
230
231impl<E: Environment> From<&Group<E>> for LinearCombination<E::BaseField> {
232    fn from(group: &Group<E>) -> Self {
233        group.to_x_coordinate().into()
234    }
235}
236
237#[cfg(test)]
238mod tests {
239    use super::*;
240    use snarkvm_circuit_environment::Circuit;
241
242    use core::str::FromStr;
243
244    const ITERATIONS: u64 = 128;
245
246    /// Attempts to construct an affine group element from the given x-coordinate and mode.
247    fn check_display(mode: Mode, point: console::Group<<Circuit as Environment>::Network>) {
248        let x = *point.to_x_coordinate();
249        let candidate = Group::<Circuit>::new(mode, point);
250        assert_eq!(format!("{x}{}.{mode}", Group::<Circuit>::type_name()), format!("{candidate}"));
251    }
252
253    #[test]
254    fn test_new() {
255        let mut rng = TestRng::default();
256
257        // Constant variables
258        for i in 0..ITERATIONS {
259            // Sample a random element.
260            let point = Uniform::rand(&mut rng);
261
262            Circuit::scope(format!("Constant {i}"), || {
263                let affine = Group::<Circuit>::new(Mode::Constant, point);
264                assert_eq!(point, affine.eject_value());
265                assert_scope!(10, 0, 0, 0);
266            });
267        }
268
269        // Public variables
270        for i in 0..ITERATIONS {
271            // Sample a random element.
272            let point = Uniform::rand(&mut rng);
273
274            Circuit::scope(format!("Public {i}"), || {
275                let affine = Group::<Circuit>::new(Mode::Public, point);
276                assert_eq!(point, affine.eject_value());
277                assert_scope!(4, 2, 12, 13);
278            });
279        }
280
281        // Private variables
282        for i in 0..ITERATIONS {
283            // Sample a random element.
284            let point = Uniform::rand(&mut rng);
285
286            Circuit::scope(format!("Private {i}"), || {
287                let affine = Group::<Circuit>::new(Mode::Private, point);
288                assert_eq!(point, affine.eject_value());
289                assert_scope!(4, 0, 14, 13);
290            });
291        }
292    }
293
294    #[test]
295    fn test_display() {
296        let mut rng = TestRng::default();
297
298        for _ in 0..ITERATIONS {
299            // Sample a random element.
300            let point = Uniform::rand(&mut rng);
301
302            // Constant
303            check_display(Mode::Constant, point);
304            // Public
305            check_display(Mode::Public, point);
306            // Private
307            check_display(Mode::Private, point);
308        }
309    }
310
311    #[test]
312    fn test_display_zero() {
313        let zero = console::Group::<<Circuit as Environment>::Network>::zero();
314
315        // Constant
316        let candidate = Group::<Circuit>::new(Mode::Constant, zero);
317        assert_eq!("0group.constant", &format!("{candidate}"));
318
319        // Public
320        let candidate = Group::<Circuit>::new(Mode::Public, zero);
321        assert_eq!("0group.public", &format!("{candidate}"));
322
323        // Private
324        let candidate = Group::<Circuit>::new(Mode::Private, zero);
325        assert_eq!("0group.private", &format!("{candidate}"));
326    }
327
328    #[rustfmt::skip]
329    #[test]
330    fn test_parser() {
331        type Primitive = console::Group<<Circuit as Environment>::Network>;
332
333        // Constant
334
335        let (_, candidate) = Group::<Circuit>::parse("2group").unwrap();
336        assert_eq!(Primitive::from_str("2group").unwrap(), candidate.eject_value());
337        assert!(candidate.is_constant());
338
339        let (_, candidate) = Group::<Circuit>::parse("2_group").unwrap();
340        assert_eq!(Primitive::from_str("2group").unwrap(), candidate.eject_value());
341        assert!(candidate.is_constant());
342
343        let (_, candidate) = Group::<Circuit>::parse("6124_8679069_09631996143302_21072113214281104_6555821040_573308695_4291647607832_31_group", ).unwrap();
344        assert_eq!(Primitive::from_str("6124867906909631996143302210721132142811046555821040573308695429164760783231group").unwrap(), candidate.eject_value());
345        assert!(candidate.is_constant());
346
347        let (_, candidate) = Group::<Circuit>::parse("2group.constant").unwrap();
348        assert_eq!(Primitive::from_str("2group").unwrap(), candidate.eject_value());
349        assert!(candidate.is_constant());
350
351        let (_, candidate) = Group::<Circuit>::parse("2_group.constant").unwrap();
352        assert_eq!(Primitive::from_str("2group").unwrap(), candidate.eject_value());
353        assert!(candidate.is_constant());
354
355        let (_, candidate) = Group::<Circuit>::parse("6124_8679069_09631996143302_21072113214281104_6555821040_573308695_4291647607832_31_group.constant", ).unwrap();
356        assert_eq!(Primitive::from_str("6124867906909631996143302210721132142811046555821040573308695429164760783231group").unwrap(), candidate.eject_value());
357        assert!(candidate.is_constant());
358
359        // Public
360
361        let (_, candidate) = Group::<Circuit>::parse("2group.public").unwrap();
362        assert_eq!(Primitive::from_str("2group").unwrap(), candidate.eject_value());
363        assert!(candidate.is_public());
364
365        let (_, candidate) = Group::<Circuit>::parse("2_group.public").unwrap();
366        assert_eq!(Primitive::from_str("2group").unwrap(), candidate.eject_value());
367        assert!(candidate.is_public());
368
369        let (_, candidate) = Group::<Circuit>::parse("6124_8679069_09631996143302_21072113214281104_6555821040_573308695_4291647607832_31_group.public", ).unwrap();
370        assert_eq!(Primitive::from_str("6124867906909631996143302210721132142811046555821040573308695429164760783231group").unwrap(), candidate.eject_value());
371        assert!(candidate.is_public());
372
373        // Private
374
375        let (_, candidate) = Group::<Circuit>::parse("2group.private").unwrap();
376        assert_eq!(Primitive::from_str("2group").unwrap(), candidate.eject_value());
377        assert!(candidate.is_private());
378
379        let (_, candidate) = Group::<Circuit>::parse("2_group.private").unwrap();
380        assert_eq!(Primitive::from_str("2group").unwrap(), candidate.eject_value());
381        assert!(candidate.is_private());
382
383        let (_, candidate) = Group::<Circuit>::parse("6124_8679069_09631996143302_21072113214281104_6555821040_573308695_4291647607832_31_group.private", ).unwrap();
384        assert_eq!(Primitive::from_str("6124867906909631996143302210721132142811046555821040573308695429164760783231group").unwrap(), candidate.eject_value());
385        assert!(candidate.is_private());
386
387        // Random
388
389        let mut rng = TestRng::default();
390
391        for mode in [Mode::Constant, Mode::Public, Mode::Private] {
392            for _ in 0..ITERATIONS {
393                let point = Uniform::rand(&mut rng);
394                let expected = Group::<Circuit>::new(mode, point);
395
396                let (_, candidate) = Group::<Circuit>::parse(&format!("{expected}")).unwrap();
397                assert_eq!(expected.eject_value(), candidate.eject_value());
398                assert_eq!(mode, candidate.eject_mode());
399            }
400        }
401    }
402
403    #[test]
404    fn test_is_in_group() {
405        type PrimitiveField = console::Field<<Circuit as Environment>::Network>;
406
407        // First test the points that have low order.
408
409        // The two halves of (0,1) in group arithmetic are (0,1) and (0,-1).
410        let minus1_string = "8444461749428370424248824938781546531375899335154063827935233455917409239040field";
411        // The two halves of (0,-1) in group arithmetic are (q1x,0) and (q2x,0),
412        // where q1x = sqrt(-1) mod F_q  and  q2x = -sqrt(-1) mod F_q.
413        let q1x_string = "880904806456922042258150504921383618666682042621506879489field";
414        let q2x_string = "8444461749428370423367920132324624489117748830232680209268551413295902359552field";
415
416        // (0,1) is in the large prime subgroup.
417        let y1: Field<Circuit> = Field::new(Mode::Public, PrimitiveField::from_str("1field").unwrap());
418        let group0 = Group::<Circuit>::from_xy_coordinates_unchecked(Field::zero(), y1);
419        Circuit::scope("group0", || {
420            let group0_is_in_group = group0.is_in_group();
421            assert!(group0_is_in_group.eject_value());
422            assert_scope!(750, 0, 2253, 2253);
423        });
424        Circuit::reset();
425
426        // The other three low order points are on the curve but not in the large prime subgroup.
427        // Make sure is_in_group returns false for these.
428        let minus1: Field<Circuit> = Field::new(Mode::Public, PrimitiveField::from_str(minus1_string).unwrap());
429        let half0 = Group::<Circuit>::from_xy_coordinates_unchecked(Field::zero(), minus1);
430        Circuit::scope("half0", || {
431            let half0_is_not_in_group = !half0.is_in_group();
432            assert!(half0_is_not_in_group.eject_value());
433            assert_scope!(750, 0, 2253, 2253);
434        });
435        Circuit::reset();
436
437        let q1x: Field<Circuit> = Field::new(Mode::Public, PrimitiveField::from_str(q1x_string).unwrap());
438        let quarter1 = Group::<Circuit>::from_xy_coordinates_unchecked(q1x, Field::zero());
439        Circuit::scope("quarter1", || {
440            let quarter1_is_not_in_group = !quarter1.is_in_group();
441            assert!(quarter1_is_not_in_group.eject_value());
442            assert_scope!(750, 0, 2253, 2253);
443        });
444        Circuit::reset();
445
446        let q2x: Field<Circuit> = Field::new(Mode::Public, PrimitiveField::from_str(q2x_string).unwrap());
447        let quarter2 = Group::<Circuit>::from_xy_coordinates_unchecked(q2x, Field::zero());
448        Circuit::scope("quarter2", || {
449            let quarter2_is_not_in_group = !quarter2.is_in_group();
450            assert!(quarter2_is_not_in_group.eject_value());
451            assert_scope!(750, 0, 2253, 2253);
452        });
453        Circuit::reset();
454
455        fn check_is_in_group(mode: Mode, num_constants: u64, num_public: u64, num_private: u64, num_constraints: u64) {
456            let mut rng = TestRng::default();
457
458            for i in 0..ITERATIONS {
459                // Sample a random element.
460                let point: console::Group<<Circuit as Environment>::Network> = Uniform::rand(&mut rng);
461
462                // Inject the x-coordinate.
463                let x_coordinate = Field::new(mode, point.to_x_coordinate());
464
465                // Initialize the group element.
466                let element = Group::<Circuit>::from_x_coordinate(x_coordinate);
467
468                Circuit::scope(format!("{mode} {i}"), || {
469                    let is_in_group = element.is_in_group();
470                    assert!(is_in_group.eject_value());
471                    assert_scope!(num_constants, num_public, num_private, num_constraints);
472                });
473                Circuit::reset();
474            }
475        }
476        check_is_in_group(Mode::Constant, 1752, 0, 0, 0);
477        check_is_in_group(Mode::Public, 750, 0, 2755, 2755);
478        check_is_in_group(Mode::Private, 750, 0, 2755, 2755);
479    }
480}
snarkvm_circuit_types_group/lib.rs

snarkvm_circuit_types_group/
lib.rs
