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

snarkvm_circuit_types_group/
lib.rs
