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