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