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