1use crate::{
  2    boolean::Boolean,
  3    fields::{fp::FpGadget, FieldGadget},
  4    ToBitsGadget,
  5};
  6use algebra::PrimeField;
  7use r1cs_core::{ConstraintSystem, SynthesisError};
  8use std::marker::PhantomData;
  9
 10pub struct SmallerThanGadget<ConstraintF: PrimeField> {
 11    constraint_field_type: PhantomData<ConstraintF>,
 12}
 13
 14impl<ConstraintF: PrimeField> SmallerThanGadget<ConstraintF> {
 15    // the function assumes a and b are known to be <= (p-1)/2
 16    pub fn is_smaller_than<CS: ConstraintSystem<ConstraintF>>(
 17        mut cs: CS,
 18        a: &FpGadget<ConstraintF>,
 19        b: &FpGadget<ConstraintF>,
 20    ) -> Result<Boolean, SynthesisError> {
 21        let two = ConstraintF::one() + ConstraintF::one();
 22        let d0 = a.sub(cs.ns(|| "a - b"), b)?;
 23        let d = d0.mul_by_constant(cs.ns(|| "mul 2"), &two)?;
 24        let d_bits = d.to_bits_strict(cs.ns(|| "d to bits"))?;
 25        let d_bits_len = d_bits.len();
 26        Ok(d_bits[d_bits_len - 1])
 27    }
 28
 29    // the function assumes a and b are known to be <= (p-1)/2
 30    pub fn is_smaller_than_or_equal_to<CS: ConstraintSystem<ConstraintF>>(
 31        mut cs: CS,
 32        a: &FpGadget<ConstraintF>,
 33        b: &FpGadget<ConstraintF>,
 34    ) -> Result<Boolean, SynthesisError> {
 35        let b_plus_one = b.add_constant(cs.ns(|| "plus one"), &ConstraintF::one())?;
 36        Self::is_smaller_than(cs.ns(|| "is smaller than"), a, &b_plus_one)
 37    }
 38
 39    // the function assumes a and b are known to be <= (p-1)/2
 40    pub fn enforce_smaller_than<CS: ConstraintSystem<ConstraintF>>(
 41        mut cs: CS,
 42        a: &FpGadget<ConstraintF>,
 43        b: &FpGadget<ConstraintF>,
 44    ) -> Result<(), SynthesisError> {
 45        let is_smaller_than = Self::is_smaller_than(cs.ns(|| "is smaller than"), a, b)?;
 46        cs.enforce(
 47            || "enforce smaller than",
 48            |_| is_smaller_than.lc(CS::one(), ConstraintF::one()),
 49            |lc| lc + (ConstraintF::one(), CS::one()),
 50            |lc| lc + (ConstraintF::one(), CS::one()),
 51        );
 52
 53        Ok(())
 54    }
 55
 56    // the function assumes a and b are known to be <= (p-1)/2
 57    pub fn enforce_smaller_than_or_equal_to<CS: ConstraintSystem<ConstraintF>>(
 58        mut cs: CS,
 59        a: &FpGadget<ConstraintF>,
 60        b: &FpGadget<ConstraintF>,
 61    ) -> Result<(), SynthesisError> {
 62        let b_plus_one = b.add_constant(cs.ns(|| "plus one"), &ConstraintF::one())?;
 63        Self::enforce_smaller_than(cs.ns(|| "enforce smaller than"), a, &b_plus_one)
 64    }
 65
 66    pub fn enforce_smaller_than_strict<CS: ConstraintSystem<ConstraintF>>(
 67        mut cs: CS,
 68        a: &FpGadget<ConstraintF>,
 69        b: &FpGadget<ConstraintF>,
 70    ) -> Result<(), SynthesisError> {
 71        let a_bits = a.to_bits(cs.ns(|| "a to bits"))?;
 72        Boolean::enforce_smaller_or_equal_than::<_, _, ConstraintF, _>(
 73            cs.ns(|| "enforce a smaller than modulus minus one div two"),
 74            &a_bits,
 75            ConstraintF::modulus_minus_one_div_two(),
 76        )?;
 77        let b_bits = b.to_bits(cs.ns(|| "b to bits"))?;
 78        Boolean::enforce_smaller_or_equal_than::<_, _, ConstraintF, _>(
 79            cs.ns(|| "enforce b smaller than modulus minus one div two"),
 80            &b_bits,
 81            ConstraintF::modulus_minus_one_div_two(),
 82        )?;
 83
 84        let is_smaller_than = Self::is_smaller_than(cs.ns(|| "is smaller than"), a, b)?;
 85        cs.enforce(
 86            || "enforce smaller than",
 87            |_| is_smaller_than.lc(CS::one(), ConstraintF::one()),
 88            |lc| lc + (ConstraintF::one(), CS::one()),
 89            |lc| lc + (ConstraintF::one(), CS::one()),
 90        );
 91
 92        Ok(())
 93    }
 94
 95    pub fn enforce_smaller_than_or_equal_to_strict<CS: ConstraintSystem<ConstraintF>>(
 96        mut cs: CS,
 97        a: &FpGadget<ConstraintF>,
 98        b: &FpGadget<ConstraintF>,
 99    ) -> Result<(), SynthesisError> {
100        let b_plus_one = b.add_constant(cs.ns(|| "plus one"), &ConstraintF::one())?;
101        Self::enforce_smaller_than_strict(cs.ns(|| "enforce smaller than strict"), a, &b_plus_one)
102    }
103}
104
105#[cfg(test)]
106mod test {
107    use rand::{Rng, SeedableRng};
108    use rand_xorshift::XorShiftRng;
109    use std::cmp::Ordering;
110
111    use super::SmallerThanGadget;
112    use crate::{
113        alloc::AllocGadget, fields::fp::FpGadget, test_constraint_system::TestConstraintSystem,
114    };
115    use algebra::{bls12_381::Fr, PrimeField, UniformRand};
116    use r1cs_core::ConstraintSystem;
117
118    #[test]
119    fn test_smaller_than() {
120        let mut rng = &mut XorShiftRng::from_seed([
121            0x5d, 0xbe, 0x62, 0x59, 0x8d, 0x31, 0x3d, 0x76, 0x32, 0x37, 0xdb, 0x17, 0xe5, 0xbc,
122            0x06, 0x54,
123        ]);
124        fn rand_in_range<R: Rng>(rng: &mut R) -> Fr {
125            let pminusonedivtwo = Fr::from_repr(Fr::modulus_minus_one_div_two());
126            let mut r;
127            loop {
128                r = Fr::rand(rng);
129                if r <= pminusonedivtwo {
130                    break;
131                }
132            }
133            r
134        }
135        for i in 0..10 {
136            let mut cs = TestConstraintSystem::<Fr>::new();
137            let a = rand_in_range(&mut rng);
138            let a_var = FpGadget::<Fr>::alloc(cs.ns(|| "a"), || Ok(a)).unwrap();
139            let b = rand_in_range(&mut rng);
140            let b_var = FpGadget::<Fr>::alloc(cs.ns(|| "b"), || Ok(b)).unwrap();
141
142            match a.cmp(&b) {
143                Ordering::Less => {
144                    SmallerThanGadget::<Fr>::enforce_smaller_than_strict(
145                        cs.ns(|| "smaller than test"),
146                        &a_var,
147                        &b_var,
148                    )
149                    .unwrap();
150                    SmallerThanGadget::<Fr>::enforce_smaller_than_or_equal_to_strict(
151                        cs.ns(|| "smaller than test 2"),
152                        &a_var,
153                        &b_var,
154                    )
155                    .unwrap();
156                },
157                Ordering::Greater => {
158                    SmallerThanGadget::<Fr>::enforce_smaller_than_strict(
159                        cs.ns(|| "smaller than test"),
160                        &b_var,
161                        &a_var,
162                    )
163                    .unwrap();
164                    SmallerThanGadget::<Fr>::enforce_smaller_than_or_equal_to_strict(
165                        cs.ns(|| "smaller than test 2"),
166                        &b_var,
167                        &a_var,
168                    )
169                    .unwrap();
170                },
171                _ => {},
172            }
173
174            if i == 0 {
175                println!("number of constraints: {}", cs.num_constraints());
176            }
177            assert!(cs.is_satisfied());
178        }
179
180        for _i in 0..10 {
181            let mut cs = TestConstraintSystem::<Fr>::new();
182            let a = rand_in_range(&mut rng);
183            let a_var = FpGadget::<Fr>::alloc(cs.ns(|| "a"), || Ok(a)).unwrap();
184            let b = rand_in_range(&mut rng);
185            let b_var = FpGadget::<Fr>::alloc(cs.ns(|| "b"), || Ok(b)).unwrap();
186
187            match b.cmp(&a) {
188                Ordering::Less => {
189                    SmallerThanGadget::<Fr>::enforce_smaller_than_strict(
190                        cs.ns(|| "smaller than test"),
191                        &a_var,
192                        &b_var,
193                    )
194                    .unwrap();
195                    SmallerThanGadget::<Fr>::enforce_smaller_than_or_equal_to_strict(
196                        cs.ns(|| "smaller than test 2"),
197                        &a_var,
198                        &b_var,
199                    )
200                    .unwrap();
201                },
202                Ordering::Greater => {
203                    SmallerThanGadget::<Fr>::enforce_smaller_than_strict(
204                        cs.ns(|| "smaller than test"),
205                        &b_var,
206                        &a_var,
207                    )
208                    .unwrap();
209                    SmallerThanGadget::<Fr>::enforce_smaller_than_or_equal_to(
210                        cs.ns(|| "smaller than test 2"),
211                        &b_var,
212                        &a_var,
213                    )
214                    .unwrap();
215                },
216                _ => {},
217            }
218
219            assert!(!cs.is_satisfied());
220        }
221
222        for _i in 0..10 {
223            let mut cs = TestConstraintSystem::<Fr>::new();
224            let a = rand_in_range(&mut rng);
225            let a_var = FpGadget::<Fr>::alloc(cs.ns(|| "a"), || Ok(a)).unwrap();
226            SmallerThanGadget::<Fr>::enforce_smaller_than_strict(
227                cs.ns(|| "smaller than test"),
228                &a_var,
229                &a_var,
230            )
231            .unwrap();
232
233            assert!(!cs.is_satisfied());
234        }
235
236        for _i in 0..10 {
237            let mut cs = TestConstraintSystem::<Fr>::new();
238            let a = rand_in_range(&mut rng);
239            let a_var = FpGadget::<Fr>::alloc(cs.ns(|| "a"), || Ok(a)).unwrap();
240            SmallerThanGadget::<Fr>::enforce_smaller_than_or_equal_to(
241                cs.ns(|| "smaller than or equal to test"),
242                &a_var,
243                &a_var,
244            )
245            .unwrap();
246
247            assert!(cs.is_satisfied());
248        }
249    }
250}