1use crate::prelude::*;
  2use algebra::{Field, ProjectiveCurve};
  3use core::ops::{Add, AddAssign, Sub, SubAssign};
  4use r1cs_core::{Namespace, SynthesisError};
  5
  6use core::{borrow::Borrow, fmt::Debug};
  7
  8/// This module contains implementations of arithmetic for various curve models.
  9pub mod curves;
 10
 11pub use self::curves::short_weierstrass::bls12;
 12pub use self::curves::short_weierstrass::mnt4;
 13pub use self::curves::short_weierstrass::mnt6;
 14
 15/// A hack used to work around the lack of implied bounds.
 16pub trait GroupOpsBounds<'a, F, T: 'a>:
 17    Sized
 18    + Add<&'a T, Output = T>
 19    + Sub<&'a T, Output = T>
 20    + Add<T, Output = T>
 21    + Sub<T, Output = T>
 22    + Add<F, Output = T>
 23    + Sub<F, Output = T>
 24{
 25}
 26
 27/// A variable that represents a curve point for
 28/// the curve `C`.
 29pub trait CurveVar<C: ProjectiveCurve, ConstraintF: Field>:
 30    'static
 31    + Sized
 32    + Clone
 33    + Debug
 34    + R1CSVar<ConstraintF, Value = C>
 35    + ToBitsGadget<ConstraintF>
 36    + ToBytesGadget<ConstraintF>
 37    + EqGadget<ConstraintF>
 38    + CondSelectGadget<ConstraintF>
 39    + AllocVar<C, ConstraintF>
 40    + AllocVar<C::Affine, ConstraintF>
 41    + for<'a> GroupOpsBounds<'a, C, Self>
 42    + for<'a> AddAssign<&'a Self>
 43    + for<'a> SubAssign<&'a Self>
 44    + AddAssign<C>
 45    + SubAssign<C>
 46    + AddAssign<Self>
 47    + SubAssign<Self>
 48{
 49    /// Returns the constant `F::zero()`. This is the identity
 50    /// of the group.
 51    fn zero() -> Self;
 52
 53    /// Returns a `Boolean` representing whether `self == Self::zero()`.
 54    #[tracing::instrument(target = "r1cs")]
 55    fn is_zero(&self) -> Result<Boolean<ConstraintF>, SynthesisError> {
 56        self.is_eq(&Self::zero())
 57    }
 58
 59    /// Returns a constant with value `v`.
 60    ///
 61    /// This *should not* allocate any variables.
 62    fn constant(other: C) -> Self;
 63
 64    /// Allocates a variable in the subgroup without checking if it's in the
 65    /// prime-order subgroup.
 66    fn new_variable_omit_prime_order_check(
 67        cs: impl Into<Namespace<ConstraintF>>,
 68        f: impl FnOnce() -> Result<C, SynthesisError>,
 69        mode: AllocationMode,
 70    ) -> Result<Self, SynthesisError>;
 71
 72    /// Enforce that `self` is in the prime-order subgroup.
 73    fn enforce_prime_order(&self) -> Result<(), SynthesisError>;
 74
 75    /// Computes `self + self`.
 76    #[tracing::instrument(target = "r1cs")]
 77    fn double(&self) -> Result<Self, SynthesisError> {
 78        let mut result = self.clone();
 79        result.double_in_place()?;
 80        Ok(result)
 81    }
 82
 83    /// Sets `self = self + self`.
 84    fn double_in_place(&mut self) -> Result<(), SynthesisError>;
 85
 86    /// Coputes `-self`.
 87    fn negate(&self) -> Result<Self, SynthesisError>;
 88
 89    /// Computes `bits * self`, where `bits` is a little-endian
 90    /// `Boolean` representation of a scalar.
 91    #[tracing::instrument(target = "r1cs", skip(bits))]
 92    fn scalar_mul_le<'a>(
 93        &self,
 94        bits: impl Iterator<Item = &'a Boolean<ConstraintF>>,
 95    ) -> Result<Self, SynthesisError> {
 96        let mut res = Self::zero();
 97        let mut multiple = self.clone();
 98        for bit in bits {
 99            let tmp = res.clone() + &multiple;
100            res = bit.select(&tmp, &res)?;
101            multiple.double_in_place()?;
102        }
103        Ok(res)
104    }
105
106    /// Computes a `I * self` in place, where `I` is a `Boolean` *little-endian*
107    /// representation of the scalar.
108    ///
109    /// The base powers are precomputed power-of-two multiples of a single
110    /// base.
111    #[tracing::instrument(target = "r1cs", skip(scalar_bits_with_base_powers))]
112    fn precomputed_base_scalar_mul_le<'a, I, B>(
113        &mut self,
114        scalar_bits_with_base_powers: I,
115    ) -> Result<(), SynthesisError>
116    where
117        I: Iterator<Item = (B, &'a C)>,
118        B: Borrow<Boolean<ConstraintF>>,
119        C: 'a,
120    {
121        for (bit, base_power) in scalar_bits_with_base_powers {
122            let new_encoded = self.clone() + *base_power;
123            *self = bit.borrow().select(&new_encoded, self)?;
124        }
125        Ok(())
126    }
127
128    /// Computes a `\sum_j I_j * B_j`, where `I_j` is a `Boolean`
129    /// representation of the j-th scalar.
130    #[tracing::instrument(target = "r1cs", skip(bases, scalars))]
131    fn precomputed_base_multiscalar_mul_le<'a, T, I, B>(
132        bases: &[B],
133        scalars: I,
134    ) -> Result<Self, SynthesisError>
135    where
136        T: 'a + ToBitsGadget<ConstraintF> + ?Sized,
137        I: Iterator<Item = &'a T>,
138        B: Borrow<[C]>,
139    {
140        let mut result = Self::zero();
141        // Compute ∏(h_i^{m_i}) for all i.
142        for (bits, base_powers) in scalars.zip(bases) {
143            let base_powers = base_powers.borrow();
144            let bits = bits.to_bits_le()?;
145            result.precomputed_base_scalar_mul_le(bits.iter().zip(base_powers))?;
146        }
147        Ok(result)
148    }
149}
150
151#[cfg(test)]
152mod test {
153    use algebra::{test_rng, Field, ProjectiveCurve};
154    use r1cs_core::{ConstraintSystem, SynthesisError};
155
156    use crate::prelude::*;
157
158    pub(crate) fn group_test<C: ProjectiveCurve, ConstraintF: Field, GG: CurveVar<C, ConstraintF>>(
159    ) -> Result<(), SynthesisError>
160    where
161        for<'a> &'a GG: GroupOpsBounds<'a, C, GG>,
162    {
163        let cs = ConstraintSystem::<ConstraintF>::new_ref();
164
165        let mut rng = test_rng();
166        let a_native = C::rand(&mut rng);
167        let b_native = C::rand(&mut rng);
168        let a = GG::new_witness(r1cs_core::ns!(cs, "generate_a"), || Ok(a_native)).unwrap();
169        let b = GG::new_witness(r1cs_core::ns!(cs, "generate_b"), || Ok(b_native)).unwrap();
170
171        let zero = GG::zero();
172        assert_eq!(zero.value()?, zero.value()?);
173
174        // a == a
175        assert_eq!(a.value()?, a.value()?);
176        // a + 0 = a
177        assert_eq!((&a + &zero).value()?, a.value()?);
178        // a - 0 = a
179        assert_eq!((&a - &zero).value()?, a.value()?);
180        // a - a = 0
181        assert_eq!((&a - &a).value()?, zero.value()?);
182        // a + b = b + a
183        let a_b = &a + &b;
184        let b_a = &b + &a;
185        assert_eq!(a_b.value()?, b_a.value()?);
186        a_b.enforce_equal(&b_a)?;
187        assert!(cs.is_satisfied().unwrap());
188
189        // (a + b) + a = a + (b + a)
190        let ab_a = &a_b + &a;
191        let a_ba = &a + &b_a;
192        assert_eq!(ab_a.value()?, a_ba.value()?);
193        ab_a.enforce_equal(&a_ba)?;
194        assert!(cs.is_satisfied().unwrap());
195
196        // a.double() = a + a
197        let a_a = &a + &a;
198        let mut a2 = a.clone();
199        a2.double_in_place()?;
200        a2.enforce_equal(&a_a)?;
201        assert_eq!(a2.value()?, a_native.double());
202        assert_eq!(a_a.value()?, a_native.double());
203        assert_eq!(a2.value()?, a_a.value()?);
204        assert!(cs.is_satisfied().unwrap());
205
206        // b.double() = b + b
207        let mut b2 = b.clone();
208        b2.double_in_place()?;
209        let b_b = &b + &b;
210        b2.enforce_equal(&b_b)?;
211        assert!(cs.is_satisfied().unwrap());
212        assert_eq!(b2.value()?, b_b.value()?);
213
214        let _ = a.to_bytes()?;
215        assert!(cs.is_satisfied().unwrap());
216        let _ = a.to_non_unique_bytes()?;
217        assert!(cs.is_satisfied().unwrap());
218
219        let _ = b.to_bytes()?;
220        let _ = b.to_non_unique_bytes()?;
221        if !cs.is_satisfied().unwrap() {
222            println!("{:?}", cs.which_is_unsatisfied().unwrap());
223        }
224        assert!(cs.is_satisfied().unwrap());
225        Ok(())
226    }
227}