ark_r1cs_std/groups/
mod.rs

1use crate::{
2    convert::{ToBitsGadget, ToBytesGadget, ToConstraintFieldGadget},
3    fields::emulated_fp::EmulatedFpVar,
4    prelude::*,
5};
6use ark_ff::PrimeField;
7use ark_relations::r1cs::{Namespace, SynthesisError};
8use core::ops::{Add, AddAssign, Mul, MulAssign, Sub, SubAssign};
9
10use ark_ec::CurveGroup;
11use core::{borrow::Borrow, fmt::Debug};
12
13/// This module contains implementations of arithmetic for various curve models.
14pub mod curves;
15
16pub use self::curves::short_weierstrass::{bls12, mnt4, mnt6};
17
18/// A hack used to work around the lack of implied bounds.
19pub trait GroupOpsBounds<'a, G, T: 'a>:
20    Sized
21    + Add<&'a T, Output = T>
22    + Sub<&'a T, Output = T>
23    + Add<T, Output = T>
24    + Sub<T, Output = T>
25    + Add<G, Output = T>
26    + Sub<G, Output = T>
27{
28}
29
30/// A variable that represents a curve point for
31/// the curve `C`.
32pub trait CurveVar<C: CurveGroup, ConstraintF: PrimeField>:
33    'static
34    + Sized
35    + Clone
36    + Debug
37    + R1CSVar<ConstraintF, Value = C>
38    + ToBitsGadget<ConstraintF>
39    + ToBytesGadget<ConstraintF>
40    + EqGadget<ConstraintF>
41    + CondSelectGadget<ConstraintF>
42    + AllocVar<C, ConstraintF>
43    + AllocVar<C::Affine, ConstraintF>
44    + ToConstraintFieldGadget<ConstraintF>
45    + for<'a> GroupOpsBounds<'a, C, Self>
46    + for<'a> AddAssign<&'a Self>
47    + for<'a> SubAssign<&'a Self>
48    + AddAssign<C>
49    + SubAssign<C>
50    + AddAssign<Self>
51    + SubAssign<Self>
52    + Mul<EmulatedFpVar<C::ScalarField, ConstraintF>, Output = Self>
53    + for<'a> Mul<&'a EmulatedFpVar<C::ScalarField, ConstraintF>, Output = Self>
54    + MulAssign<EmulatedFpVar<C::ScalarField, ConstraintF>>
55{
56    /// Returns the constant `F::zero()`. This is the identity
57    /// of the group.
58    fn zero() -> Self;
59
60    /// Returns a `Boolean` representing whether `self == Self::zero()`.
61    #[tracing::instrument(target = "r1cs")]
62    fn is_zero(&self) -> Result<Boolean<ConstraintF>, SynthesisError> {
63        self.is_eq(&Self::zero())
64    }
65
66    /// Returns a constant with value `v`.
67    ///
68    /// This *should not* allocate any variables.
69    fn constant(other: C) -> Self;
70
71    /// Allocates a variable in the subgroup without checking if it's in the
72    /// prime-order subgroup.
73    fn new_variable_omit_prime_order_check(
74        cs: impl Into<Namespace<ConstraintF>>,
75        f: impl FnOnce() -> Result<C, SynthesisError>,
76        mode: AllocationMode,
77    ) -> Result<Self, SynthesisError>;
78
79    /// Enforce that `self` is in the prime-order subgroup.
80    fn enforce_prime_order(&self) -> Result<(), SynthesisError>;
81
82    /// Computes `self + self`.
83    #[tracing::instrument(target = "r1cs")]
84    fn double(&self) -> Result<Self, SynthesisError> {
85        let mut result = self.clone();
86        result.double_in_place()?;
87        Ok(result)
88    }
89
90    /// Sets `self = self + self`.
91    fn double_in_place(&mut self) -> Result<(), SynthesisError>;
92
93    /// Coputes `-self`.
94    fn negate(&self) -> Result<Self, SynthesisError>;
95
96    /// Computes `bits * self`, where `bits` is a little-endian
97    /// `Boolean` representation of a scalar.
98    #[tracing::instrument(target = "r1cs", skip(bits))]
99    fn scalar_mul_le<'a>(
100        &self,
101        bits: impl Iterator<Item = &'a Boolean<ConstraintF>>,
102    ) -> Result<Self, SynthesisError> {
103        // TODO: in the constant case we should call precomputed_scalar_mul_le,
104        // but rn there's a bug when doing this with TE curves.
105
106        // Computes the standard little-endian double-and-add algorithm
107        // (Algorithm 3.26, Guide to Elliptic Curve Cryptography)
108        let mut res = Self::zero();
109        let mut multiple = self.clone();
110        for bit in bits {
111            let tmp = res.clone() + &multiple;
112            res = bit.select(&tmp, &res)?;
113            multiple.double_in_place()?;
114        }
115        Ok(res)
116    }
117
118    /// Computes a `I * self` in place, where `I` is a `Boolean` *little-endian*
119    /// representation of the scalar.
120    ///
121    /// The bases are precomputed power-of-two multiples of a single
122    /// base.
123    #[tracing::instrument(target = "r1cs", skip(scalar_bits_with_bases))]
124    fn precomputed_base_scalar_mul_le<'a, I, B>(
125        &mut self,
126        scalar_bits_with_bases: I,
127    ) -> Result<(), SynthesisError>
128    where
129        I: Iterator<Item = (B, &'a C)>,
130        B: Borrow<Boolean<ConstraintF>>,
131        C: 'a,
132    {
133        // Computes the standard little-endian double-and-add algorithm
134        // (Algorithm 3.26, Guide to Elliptic Curve Cryptography)
135
136        // Let `original` be the initial value of `self`.
137        let mut result = Self::zero();
138        for (bit, base) in scalar_bits_with_bases {
139            // Compute `self + 2^i * original`
140            let self_plus_base = result.clone() + *base;
141            // If `bit == 1`, set self = self + 2^i * original;
142            // else, set self = self;
143            result = bit.borrow().select(&self_plus_base, &result)?;
144        }
145        *self += result;
146        Ok(())
147    }
148
149    /// Computes `Σⱼ(scalarⱼ * baseⱼ)` for all j,
150    /// where `scalarⱼ` is a `Boolean` *little-endian*
151    /// representation of the j-th scalar.
152    #[tracing::instrument(target = "r1cs", skip(bases, scalars))]
153    fn precomputed_base_multiscalar_mul_le<'a, T, I, B>(
154        bases: &[B],
155        scalars: I,
156    ) -> Result<Self, SynthesisError>
157    where
158        T: 'a + ToBitsGadget<ConstraintF> + ?Sized,
159        I: Iterator<Item = &'a T>,
160        B: Borrow<[C]>,
161    {
162        let mut result = Self::zero();
163        // Compute Σᵢ(bitᵢ * baseᵢ) for all i.
164        for (bits, bases) in scalars.zip(bases) {
165            let bases = bases.borrow();
166            let bits = bits.to_bits_le()?;
167            result.precomputed_base_scalar_mul_le(bits.iter().zip(bases))?;
168        }
169        Ok(result)
170    }
171}