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