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    /// Inputs must be specified in *little-endian* form.
 76    /// If the addition law is incomplete for the identity element,
 77    /// `result` must not be the identity element.
 78    fn mul_bits<'a>(
 79        &self,
 80        bits: impl Iterator<Item = &'a Boolean<ConstraintF>>,
 81    ) -> Result<Self, SynthesisError> {
 82        let mut power = self.clone();
 83        let mut result = Self::zero();
 84        for bit in bits {
 85            let new_encoded = result.clone() + &power;
 86            result = bit.borrow().select(&new_encoded, &result)?;
 87            power.double_in_place()?;
 88        }
 89        Ok(result)
 90    }
 91
 92    fn precomputed_base_scalar_mul<'a, I, B>(
 93        &mut self,
 94        scalar_bits_with_base_powers: I,
 95    ) -> Result<(), SynthesisError>
 96    where
 97        I: Iterator<Item = (B, &'a C)>,
 98        B: Borrow<Boolean<ConstraintF>>,
 99        C: 'a,
100    {
101        for (bit, base_power) in scalar_bits_with_base_powers {
102            let new_encoded = self.clone() + *base_power;
103            *self = bit.borrow().select(&new_encoded, self)?;
104        }
105        Ok(())
106    }
107
108    fn precomputed_base_3_bit_signed_digit_scalar_mul<'a, I, J, B>(
109        _: &[B],
110        _: &[J],
111    ) -> Result<Self, SynthesisError>
112    where
113        I: Borrow<[Boolean<ConstraintF>]>,
114        J: Borrow<[I]>,
115        B: Borrow<[C]>,
116    {
117        Err(SynthesisError::AssignmentMissing)
118    }
119
120    fn precomputed_base_multiscalar_mul<'a, T, I, B>(
121        bases: &[B],
122        scalars: I,
123    ) -> Result<Self, SynthesisError>
124    where
125        T: 'a + ToBitsGadget<ConstraintF> + ?Sized,
126        I: Iterator<Item = &'a T>,
127        B: Borrow<[C]>,
128    {
129        let mut result = Self::zero();
130        // Compute ∏(h_i^{m_i}) for all i.
131        for (bits, base_powers) in scalars.zip(bases) {
132            let base_powers = base_powers.borrow();
133            let bits = bits.to_bits()?;
134            result.precomputed_base_scalar_mul(bits.iter().zip(base_powers))?;
135        }
136        Ok(result)
137    }
138}
139
140#[cfg(test)]
141mod test {
142    use algebra::{test_rng, Field, ProjectiveCurve};
143    use r1cs_core::{ConstraintSystem, SynthesisError};
144
145    use crate::prelude::*;
146
147    pub(crate) fn group_test<C: ProjectiveCurve, ConstraintF: Field, GG: CurveVar<C, ConstraintF>>(
148    ) -> Result<(), SynthesisError>
149    where
150        for<'a> &'a GG: GroupOpsBounds<'a, C, GG>,
151    {
152        let cs = ConstraintSystem::<ConstraintF>::new_ref();
153
154        let mut rng = test_rng();
155        let a_native = C::rand(&mut rng);
156        let b_native = C::rand(&mut rng);
157        let a = GG::new_witness(cs.ns("generate_a"), || Ok(a_native)).unwrap();
158        let b = GG::new_witness(cs.ns("generate_b"), || Ok(b_native)).unwrap();
159
160        let zero = GG::zero();
161        assert_eq!(zero.value()?, zero.value()?);
162
163        // a == a
164        assert_eq!(a.value()?, a.value()?);
165        // a + 0 = a
166        assert_eq!((&a + &zero).value()?, a.value()?);
167        // a - 0 = a
168        assert_eq!((&a - &zero).value()?, a.value()?);
169        // a - a = 0
170        assert_eq!((&a - &a).value()?, zero.value()?);
171        // a + b = b + a
172        let a_b = &a + &b;
173        let b_a = &b + &a;
174        assert_eq!(a_b.value()?, b_a.value()?);
175        a_b.enforce_equal(&b_a)?;
176        assert!(cs.is_satisfied().unwrap());
177
178        // (a + b) + a = a + (b + a)
179        let ab_a = &a_b + &a;
180        let a_ba = &a + &b_a;
181        assert_eq!(ab_a.value()?, a_ba.value()?);
182        ab_a.enforce_equal(&a_ba)?;
183        assert!(cs.is_satisfied().unwrap());
184
185        // a.double() = a + a
186        let a_a = &a + &a;
187        let mut a2 = a.clone();
188        a2.double_in_place()?;
189        a2.enforce_equal(&a_a)?;
190        assert_eq!(a2.value()?, a_native.double());
191        assert_eq!(a_a.value()?, a_native.double());
192        assert_eq!(a2.value()?, a_a.value()?);
193        assert!(cs.is_satisfied().unwrap());
194
195        // b.double() = b + b
196        let mut b2 = b.clone();
197        b2.double_in_place()?;
198        let b_b = &b + &b;
199        b2.enforce_equal(&b_b)?;
200        assert!(cs.is_satisfied().unwrap());
201        assert_eq!(b2.value()?, b_b.value()?);
202
203        let _ = a.to_bytes()?;
204        let _ = a.to_non_unique_bytes()?;
205
206        let _ = b.to_bytes()?;
207        let _ = b.to_non_unique_bytes()?;
208        if !cs.is_satisfied().unwrap() {
209            println!("{:?}", cs.which_is_unsatisfied().unwrap());
210        }
211        assert!(cs.is_satisfied().unwrap());
212        Ok(())
213    }
214}