1use crate::{
  2    boolean::Boolean,
  3    fields::{fp::FpVar, FieldVar},
  4    prelude::*,
  5    ToBitsGadget,
  6};
  7use algebra::PrimeField;
  8use core::cmp::Ordering;
  9use r1cs_core::{lc, SynthesisError, Variable};
 10
 11impl<F: PrimeField> FpVar<F> {
 12    /// This function enforces the ordering between `self` and `other`. The
 13    /// constraint system will not be satisfied otherwise. If `self` should
 14    /// also be checked for equality, e.g. `self <= other` instead of `self < other`, set
 15    /// `should_also_check_quality` to `true`. This variant verifies `self` and `other`
 16    /// are `<= (p-1)/2`.
 17    pub fn enforce_cmp(
 18        &self,
 19        other: &FpVar<F>,
 20        ordering: Ordering,
 21        should_also_check_equality: bool,
 22    ) -> Result<(), SynthesisError> {
 23        let (left, right) = self.process_cmp_inputs(other, ordering, should_also_check_equality)?;
 24        left.enforce_smaller_than(&right)
 25    }
 26
 27    /// This function enforces the ordering between `self` and `other`. The
 28    /// constraint system will not be satisfied otherwise. If `self` should
 29    /// also be checked for equality, e.g. `self <= other` instead of `self < other`, set
 30    /// `should_also_check_quality` to `true`. This variant assumes `self` and `other`
 31    /// are `<= (p-1)/2` and does not generate constraints to verify that.
 32    pub fn enforce_cmp_unchecked(
 33        &self,
 34        other: &FpVar<F>,
 35        ordering: Ordering,
 36        should_also_check_equality: bool,
 37    ) -> Result<(), SynthesisError> {
 38        let (left, right) = self.process_cmp_inputs(other, ordering, should_also_check_equality)?;
 39        left.enforce_smaller_than_unchecked(&right)
 40    }
 41
 42    /// This function checks the ordering between `self` and `other`. It outputs self
 43    /// `Boolean` that contains the result - `1` if true, `0` otherwise. The
 44    /// constraint system will be satisfied in any case. If `self` should
 45    /// also be checked for equality, e.g. `self <= other` instead of `self < other`, set
 46    /// `should_also_check_quality` to `true`. This variant verifies `self` and `other`
 47    /// are `<= (p-1)/2`.
 48    pub fn is_cmp(
 49        &self,
 50        other: &FpVar<F>,
 51        ordering: Ordering,
 52        should_also_check_equality: bool,
 53    ) -> Result<Boolean<F>, SynthesisError> {
 54        let (left, right) = self.process_cmp_inputs(other, ordering, should_also_check_equality)?;
 55        left.is_smaller_than(&right)
 56    }
 57
 58    /// This function checks the ordering between `self` and `other`. It outputs a
 59    /// `Boolean` that contains the result - `1` if true, `0` otherwise. The
 60    /// constraint system will be satisfied in any case. If `self` should
 61    /// also be checked for equality, e.g. `self <= other` instead of `self < other`, set
 62    /// `should_also_check_quality` to `true`. This variant assumes `self` and `other`
 63    /// are `<= (p-1)/2` and does not generate constraints to verify that.
 64    pub fn is_cmp_unchecked(
 65        &self,
 66        other: &FpVar<F>,
 67        ordering: Ordering,
 68        should_also_check_equality: bool,
 69    ) -> Result<Boolean<F>, SynthesisError> {
 70        let (left, right) = self.process_cmp_inputs(other, ordering, should_also_check_equality)?;
 71        left.is_smaller_than_unchecked(&right)
 72    }
 73
 74    fn process_cmp_inputs(
 75        &self,
 76        other: &Self,
 77        ordering: Ordering,
 78        should_also_check_equality: bool,
 79    ) -> Result<(Self, Self), SynthesisError> {
 80        let (left, right) = match ordering {
 81            Ordering::Less => (self, other),
 82            Ordering::Greater => (other, self),
 83            Ordering::Equal => Err(SynthesisError::Unsatisfiable)?,
 84        };
 85        let right_for_check = if should_also_check_equality {
 86            right + F::one()
 87        } else {
 88            right.clone()
 89        };
 90
 91        Ok((left.clone(), right_for_check))
 92    }
 93
 94    // Helper function to enforce `self <= (p-1)/2`.
 95    pub fn enforce_smaller_or_equal_than_mod_minus_one_div_two(
 96        &self,
 97    ) -> Result<(), SynthesisError> {
 98        let _ = Boolean::enforce_smaller_or_equal_than(
 99            &self.to_bits()?,
100            F::modulus_minus_one_div_two(),
101        )?;
102        Ok(())
103    }
104
105    /// Helper function to check `self < other` and output a result bit. This function
106    /// verifies `self` and `other` are `<= (p-1)/2`.
107    fn is_smaller_than(&self, other: &FpVar<F>) -> Result<Boolean<F>, SynthesisError> {
108        self.enforce_smaller_or_equal_than_mod_minus_one_div_two()?;
109        other.enforce_smaller_or_equal_than_mod_minus_one_div_two()?;
110        self.is_smaller_than_unchecked(other)
111    }
112
113    /// Helper function to check `self < other` and output a result bit. This function
114    /// assumes `self` and `other` are `<= (p-1)/2` and does not generate constraints
115    /// to verify that.
116    fn is_smaller_than_unchecked(&self, other: &FpVar<F>) -> Result<Boolean<F>, SynthesisError> {
117        Ok((self - other).double()?.to_bits()?.last().unwrap().clone())
118    }
119
120    /// Helper function to enforce `self < other`. This function verifies `self` and `other`
121    /// are `<= (p-1)/2`.
122    fn enforce_smaller_than(&self, other: &FpVar<F>) -> Result<(), SynthesisError> {
123        self.enforce_smaller_or_equal_than_mod_minus_one_div_two()?;
124        other.enforce_smaller_or_equal_than_mod_minus_one_div_two()?;
125        self.enforce_smaller_than_unchecked(other)
126    }
127
128    /// Helper function to enforce `self < other`. This function assumes `self` and `other`
129    /// are `<= (p-1)/2` and does not generate constraints to verify that.
130    fn enforce_smaller_than_unchecked(&self, other: &FpVar<F>) -> Result<(), SynthesisError> {
131        let cs = [self, other].cs().unwrap();
132        let is_smaller_than = self.is_smaller_than_unchecked(other)?;
133        let lc_one = lc!() + Variable::One;
134        cs.enforce_constraint(is_smaller_than.lc(), lc_one.clone(), lc_one)
135    }
136}
137
138#[cfg(test)]
139mod test {
140    use rand::{Rng, SeedableRng};
141    use rand_xorshift::XorShiftRng;
142    use std::cmp::Ordering;
143
144    use crate::{alloc::AllocVar, fields::fp::FpVar};
145    use algebra::{bls12_381::Fr, PrimeField, UniformRand};
146    use r1cs_core::ConstraintSystem;
147
148    #[test]
149    fn test_cmp() {
150        let mut rng = &mut XorShiftRng::from_seed([
151            0x5d, 0xbe, 0x62, 0x59, 0x8d, 0x31, 0x3d, 0x76, 0x32, 0x37, 0xdb, 0x17, 0xe5, 0xbc,
152            0x06, 0x54,
153        ]);
154        fn rand_in_range<R: Rng>(rng: &mut R) -> Fr {
155            let pminusonedivtwo: Fr = Fr::modulus_minus_one_div_two().into();
156            let mut r;
157            loop {
158                r = Fr::rand(rng);
159                if r <= pminusonedivtwo {
160                    break;
161                }
162            }
163            r
164        }
165        for i in 0..10 {
166            let cs = ConstraintSystem::<Fr>::new_ref();
167            let a = rand_in_range(&mut rng);
168            let a_var = FpVar::<Fr>::new_witness(cs.ns("a"), || Ok(a)).unwrap();
169            let b = rand_in_range(&mut rng);
170            let b_var = FpVar::<Fr>::new_witness(cs.ns("b"), || Ok(b)).unwrap();
171
172            match a.cmp(&b) {
173                Ordering::Less => {
174                    a_var.enforce_cmp(&b_var, Ordering::Less, false).unwrap();
175                    a_var.enforce_cmp(&b_var, Ordering::Less, true).unwrap();
176                }
177                Ordering::Greater => {
178                    a_var.enforce_cmp(&b_var, Ordering::Greater, false).unwrap();
179                    a_var.enforce_cmp(&b_var, Ordering::Greater, true).unwrap();
180                }
181                _ => {}
182            }
183
184            if i == 0 {
185                println!("number of constraints: {}", cs.num_constraints());
186            }
187            assert!(cs.is_satisfied().unwrap());
188        }
189
190        for _i in 0..10 {
191            let cs = ConstraintSystem::<Fr>::new_ref();
192            let a = rand_in_range(&mut rng);
193            let a_var = FpVar::<Fr>::new_witness(cs.ns("a"), || Ok(a)).unwrap();
194            let b = rand_in_range(&mut rng);
195            let b_var = FpVar::<Fr>::new_witness(cs.ns("b"), || Ok(b)).unwrap();
196
197            match b.cmp(&a) {
198                Ordering::Less => {
199                    a_var.enforce_cmp(&b_var, Ordering::Less, false).unwrap();
200                    a_var.enforce_cmp(&b_var, Ordering::Less, true).unwrap();
201                }
202                Ordering::Greater => {
203                    a_var.enforce_cmp(&b_var, Ordering::Greater, false).unwrap();
204                    a_var.enforce_cmp(&b_var, Ordering::Greater, true).unwrap();
205                }
206                _ => {}
207            }
208
209            assert!(!cs.is_satisfied().unwrap());
210        }
211
212        for _i in 0..10 {
213            let cs = ConstraintSystem::<Fr>::new_ref();
214            let a = rand_in_range(&mut rng);
215            let a_var = FpVar::<Fr>::new_witness(cs.ns("a"), || Ok(a)).unwrap();
216            a_var.enforce_cmp(&a_var, Ordering::Less, false).unwrap();
217
218            assert!(!cs.is_satisfied().unwrap());
219        }
220
221        for _i in 0..10 {
222            let cs = ConstraintSystem::<Fr>::new_ref();
223            let a = rand_in_range(&mut rng);
224            let a_var = FpVar::<Fr>::new_witness(cs.ns("a"), || Ok(a)).unwrap();
225            a_var.enforce_cmp(&a_var, Ordering::Less, true).unwrap();
226            assert!(cs.is_satisfied().unwrap());
227        }
228    }
229}