1use crate::prelude::*;
  2use algebra::{Field, Group};
  3use r1cs_core::{ConstraintSystem, SynthesisError};
  4
  5use core::{borrow::Borrow, fmt::Debug};
  6
  7pub mod curves;
  8
  9pub use self::curves::{
 10    short_weierstrass::bls12,
 11    twisted_edwards::{edwards_sw6, jubjub},
 12};
 13
 14pub trait GroupGadget<G: Group, ConstraintF: Field>:
 15    Sized
 16    + ToBytesGadget<ConstraintF>
 17    + NEqGadget<ConstraintF>
 18    + EqGadget<ConstraintF>
 19    + ToBitsGadget<ConstraintF>
 20    + CondSelectGadget<ConstraintF>
 21    + AllocGadget<G, ConstraintF>
 22    + Clone
 23    + Debug
 24{
 25    type Value: Debug;
 26    type Variable;
 27
 28    fn get_value(&self) -> Option<Self::Value>;
 29
 30    fn get_variable(&self) -> Self::Variable;
 31
 32    fn zero<CS: ConstraintSystem<ConstraintF>>(cs: CS) -> Result<Self, SynthesisError>;
 33
 34    fn add<CS: ConstraintSystem<ConstraintF>>(
 35        &self,
 36        cs: CS,
 37        other: &Self,
 38    ) -> Result<Self, SynthesisError>;
 39
 40    fn sub<CS: ConstraintSystem<ConstraintF>>(
 41        &self,
 42        mut cs: CS,
 43        other: &Self,
 44    ) -> Result<Self, SynthesisError> {
 45        let neg_other = other.negate(cs.ns(|| "Negate other"))?;
 46        self.add(cs.ns(|| "Self - other"), &neg_other)
 47    }
 48
 49    fn add_constant<CS: ConstraintSystem<ConstraintF>>(
 50        &self,
 51        cs: CS,
 52        other: &G,
 53    ) -> Result<Self, SynthesisError>;
 54
 55    fn sub_constant<CS: ConstraintSystem<ConstraintF>>(
 56        &self,
 57        mut cs: CS,
 58        other: &G,
 59    ) -> Result<Self, SynthesisError> {
 60        let neg_other = -(*other);
 61        self.add_constant(cs.ns(|| "Self - other"), &neg_other)
 62    }
 63
 64    fn double_in_place<CS: ConstraintSystem<ConstraintF>>(
 65        &mut self,
 66        cs: CS,
 67    ) -> Result<(), SynthesisError>;
 68
 69    fn negate<CS: ConstraintSystem<ConstraintF>>(&self, cs: CS) -> Result<Self, SynthesisError>;
 70
 71    /// Inputs must be specified in *little-endian* form.
 72    /// If the addition law is incomplete for the identity element,
 73    /// `result` must not be the identity element.
 74    fn mul_bits<'a, CS: ConstraintSystem<ConstraintF>>(
 75        &self,
 76        mut cs: CS,
 77        result: &Self,
 78        bits: impl Iterator<Item = &'a Boolean>,
 79    ) -> Result<Self, SynthesisError> {
 80        let mut power = self.clone();
 81        let mut result = result.clone();
 82        for (i, bit) in bits.enumerate() {
 83            let new_encoded = result.add(&mut cs.ns(|| format!("Add {}-th power", i)), &power)?;
 84            result = Self::conditionally_select(
 85                &mut cs.ns(|| format!("Select {}", i)),
 86                bit.borrow(),
 87                &new_encoded,
 88                &result,
 89            )?;
 90            power.double_in_place(&mut cs.ns(|| format!("{}-th Doubling", i)))?;
 91        }
 92        Ok(result)
 93    }
 94
 95    fn precomputed_base_scalar_mul<'a, CS, I, B>(
 96        &mut self,
 97        mut cs: CS,
 98        scalar_bits_with_base_powers: I,
 99    ) -> Result<(), SynthesisError>
100    where
101        CS: ConstraintSystem<ConstraintF>,
102        I: Iterator<Item = (B, &'a G)>,
103        B: Borrow<Boolean>,
104        G: 'a,
105    {
106        for (i, (bit, base_power)) in scalar_bits_with_base_powers.enumerate() {
107            let new_encoded = self.add_constant(
108                &mut cs.ns(|| format!("Add {}-th base power", i)),
109                &base_power,
110            )?;
111            *self = Self::conditionally_select(
112                &mut cs.ns(|| format!("Conditional Select {}", i)),
113                bit.borrow(),
114                &new_encoded,
115                &self,
116            )?;
117        }
118        Ok(())
119    }
120
121    fn precomputed_base_3_bit_signed_digit_scalar_mul<'a, CS, I, J, B>(
122        _: CS,
123        _: &[B],
124        _: &[J],
125    ) -> Result<Self, SynthesisError>
126    where
127        CS: ConstraintSystem<ConstraintF>,
128        I: Borrow<[Boolean]>,
129        J: Borrow<[I]>,
130        B: Borrow<[G]>,
131    {
132        Err(SynthesisError::AssignmentMissing)
133    }
134
135    fn precomputed_base_multiscalar_mul<'a, CS, T, I, B>(
136        mut cs: CS,
137        bases: &[B],
138        scalars: I,
139    ) -> Result<Self, SynthesisError>
140    where
141        CS: ConstraintSystem<ConstraintF>,
142        T: 'a + ToBitsGadget<ConstraintF> + ?Sized,
143        I: Iterator<Item = &'a T>,
144        B: Borrow<[G]>,
145    {
146        let mut result = Self::zero(&mut cs.ns(|| "Declare Result"))?;
147        // Compute ∏(h_i^{m_i}) for all i.
148        for (i, (bits, base_powers)) in scalars.zip(bases).enumerate() {
149            let base_powers = base_powers.borrow();
150            let bits = bits.to_bits(&mut cs.ns(|| format!("Convert Scalar {} to bits", i)))?;
151            result.precomputed_base_scalar_mul(
152                cs.ns(|| format!("Chunk {}", i)),
153                bits.iter().zip(base_powers),
154            )?;
155        }
156        Ok(result)
157    }
158
159    fn cost_of_add() -> usize;
160
161    fn cost_of_double() -> usize;
162}
163
164#[cfg(test)]
165mod test {
166    use algebra::{test_rng, Field};
167    use r1cs_core::ConstraintSystem;
168    use rand::Rng;
169
170    use crate::{prelude::*, test_constraint_system::TestConstraintSystem};
171    use algebra::groups::Group;
172
173    pub(crate) fn group_test<
174        ConstraintF: Field,
175        G: Group,
176        GG: GroupGadget<G, ConstraintF>,
177        CS: ConstraintSystem<ConstraintF>,
178    >(
179        cs: &mut CS,
180        a: GG,
181        b: GG,
182    ) {
183        let zero = GG::zero(cs.ns(|| "Zero")).unwrap();
184        assert_eq!(zero, zero);
185
186        // a == a
187        assert_eq!(a, a);
188        // a + 0 = a
189        assert_eq!(a.add(cs.ns(|| "a_plus_zero"), &zero).unwrap(), a);
190        // a - 0 = a
191        assert_eq!(a.sub(cs.ns(|| "a_minus_zero"), &zero).unwrap(), a);
192        // a - a = 0
193        assert_eq!(a.sub(cs.ns(|| "a_minus_a"), &a).unwrap(), zero);
194        // a + b = b + a
195        let a_b = a.add(cs.ns(|| "a_plus_b"), &b).unwrap();
196        let b_a = b.add(cs.ns(|| "b_plus_a"), &a).unwrap();
197        assert_eq!(a_b, b_a);
198        // (a + b) + a = a + (b + a)
199        let ab_a = a_b.add(&mut cs.ns(|| "a_b_plus_a"), &a).unwrap();
200        let a_ba = a.add(&mut cs.ns(|| "a_plus_b_a"), &b_a).unwrap();
201        assert_eq!(ab_a, a_ba);
202        // a.double() = a + a
203        let a_a = a.add(cs.ns(|| "a + a"), &a).unwrap();
204        let mut a2 = a.clone();
205        a2.double_in_place(cs.ns(|| "2a")).unwrap();
206        assert_eq!(a2, a_a);
207        // b.double() = b + b
208        let mut b2 = b.clone();
209        b2.double_in_place(cs.ns(|| "2b")).unwrap();
210        let b_b = b.add(cs.ns(|| "b + b"), &b).unwrap();
211        assert_eq!(b2, b_b);
212
213        let _ = a.to_bytes(&mut cs.ns(|| "ToBytes")).unwrap();
214        let _ = a.to_bytes_strict(&mut cs.ns(|| "ToBytes Strict")).unwrap();
215
216        let _ = b.to_bytes(&mut cs.ns(|| "b ToBytes")).unwrap();
217        let _ = b
218            .to_bytes_strict(&mut cs.ns(|| "b ToBytes Strict"))
219            .unwrap();
220    }
221
222    #[test]
223    fn jubjub_group_gadgets_test() {
224        use crate::groups::jubjub::JubJubGadget;
225        use algebra::{curves::jubjub::JubJubProjective, fields::jubjub::fq::Fq};
226
227        let mut cs = TestConstraintSystem::<Fq>::new();
228
229        let mut rng = test_rng();
230        let a: JubJubProjective = rng.gen();
231        let b: JubJubProjective = rng.gen();
232
233        let a = JubJubGadget::alloc(&mut cs.ns(|| "generate_a"), || Ok(a)).unwrap();
234        let b = JubJubGadget::alloc(&mut cs.ns(|| "generate_b"), || Ok(b)).unwrap();
235        group_test::<_, JubJubProjective, _, _>(&mut cs.ns(|| "GroupTest(a, b)"), a, b);
236    }
237}