ark-r1cs-std/r1cs-std/src/fields/fp/cmp.rs
r1cs-std/src/fields/fp/cmp.rsRaw
1use crate::{
2 boolean::Boolean,
3 fields::{fp::FpGadget, FieldGadget},
4 ToBitsGadget,
5};
6use algebra::PrimeField;
7use core::cmp::Ordering;
8use r1cs_core::{ConstraintSystem, SynthesisError};
9
10impl<F: PrimeField> FpGadget<F> {
11 /// This function enforces the ordering between `self` and `b`. The
12 /// constraint system will not be satisfied otherwise. If `self` should
13 /// also be checked for equality, e.g. `a <= b` instead of `a < b`, set
14 /// `should_also_check_quality` to `true`. This variant verifies `a` and `b`
15 /// are `<= (p-1)/2`.
16 pub fn enforce_cmp<CS: ConstraintSystem<F>>(
17 &self,
18 mut cs: CS,
19 b: &FpGadget<F>,
20 ordering: Ordering,
21 should_also_check_equality: bool,
22 ) -> Result<(), SynthesisError> {
23 let (left, right) = Self::process_cmp_inputs(
24 cs.ns(|| "process cmp inputs"),
25 &self,
26 b,
27 ordering,
28 should_also_check_equality,
29 )?;
30 Self::enforce_smaller_than(cs.ns(|| "enforce smaller than"), &left, &right)
31 }
32
33 /// This function enforces the ordering between `self` and `b`. The
34 /// constraint system will not be satisfied otherwise. If `self` should
35 /// also be checked for equality, e.g. `a <= b` instead of `a < b`, set
36 /// `should_also_check_quality` to `true`. This variant assumes `a` and `b`
37 /// are `<= (p-1)/2` and does not generate constraints to verify that.
38 pub fn enforce_cmp_unchecked<CS: ConstraintSystem<F>>(
39 &self,
40 mut cs: CS,
41 b: &FpGadget<F>,
42 ordering: Ordering,
43 should_also_check_equality: bool,
44 ) -> Result<(), SynthesisError> {
45 let (left, right) = Self::process_cmp_inputs(
46 cs.ns(|| "process cmp inputs"),
47 &self,
48 b,
49 ordering,
50 should_also_check_equality,
51 )?;
52 Self::enforce_smaller_than_unchecked(cs.ns(|| "enforce smaller than"), &left, &right)
53 }
54
55 /// This function checks the ordering between `self` and `b`. It outputs a
56 /// `Boolean` that contains the result - `1` if true, `0` otherwise. The
57 /// constraint system will be satisfied in any case. If `self` should
58 /// also be checked for equality, e.g. `a <= b` instead of `a < b`, set
59 /// `should_also_check_quality` to `true`. This variant verifies `a` and `b`
60 /// are `<= (p-1)/2`.
61 pub fn is_cmp<CS: ConstraintSystem<F>>(
62 &self,
63 mut cs: CS,
64 b: &FpGadget<F>,
65 ordering: Ordering,
66 should_also_check_equality: bool,
67 ) -> Result<Boolean, SynthesisError> {
68 let (left, right) = Self::process_cmp_inputs(
69 cs.ns(|| "process cmp inputs"),
70 &self,
71 b,
72 ordering,
73 should_also_check_equality,
74 )?;
75 Self::is_smaller_than(cs.ns(|| "enforce smaller than"), &left, &right)
76 }
77
78 /// This function checks the ordering between `self` and `b`. It outputs a
79 /// `Boolean` that contains the result - `1` if true, `0` otherwise. The
80 /// constraint system will be satisfied in any case. If `self` should
81 /// also be checked for equality, e.g. `a <= b` instead of `a < b`, set
82 /// `should_also_check_quality` to `true`. This variant assumes `a` and `b`
83 /// are `<= (p-1)/2` and does not generate constraints to verify that.
84 pub fn is_cmp_unchecked<CS: ConstraintSystem<F>>(
85 &self,
86 mut cs: CS,
87 b: &FpGadget<F>,
88 ordering: Ordering,
89 should_also_check_equality: bool,
90 ) -> Result<Boolean, SynthesisError> {
91 let (left, right) = Self::process_cmp_inputs(
92 cs.ns(|| "process cmp inputs"),
93 &self,
94 b,
95 ordering,
96 should_also_check_equality,
97 )?;
98 Self::is_smaller_than_unchecked(cs.ns(|| "enforce smaller than"), &left, &right)
99 }
100
101 fn process_cmp_inputs<CS: ConstraintSystem<F>>(
102 mut cs: CS,
103 a: &FpGadget<F>,
104 b: &FpGadget<F>,
105 ordering: Ordering,
106 should_also_check_equality: bool,
107 ) -> Result<(FpGadget<F>, FpGadget<F>), SynthesisError> {
108 let left;
109 let right;
110 match ordering {
111 Ordering::Less => {
112 left = a;
113 right = b;
114 }
115 Ordering::Greater => {
116 left = b;
117 right = a;
118 }
119 Ordering::Equal => {
120 return Err(SynthesisError::Unsatisfiable);
121 }
122 };
123 let right_for_check = if should_also_check_equality {
124 right.add_constant(cs.ns(|| "plus one"), &F::one())?
125 } else {
126 right.clone()
127 };
128
129 Ok((left.clone(), right_for_check))
130 }
131
132 // Helper function to enforce `a <= (p-1)/2`.
133 fn check_smaller_than_mod_minus_one_div_two<CS: ConstraintSystem<F>>(
134 mut cs: CS,
135 a: &FpGadget<F>,
136 ) -> Result<(), SynthesisError> {
137 let a_bits = a.to_bits(cs.ns(|| "a to bits"))?;
138 Boolean::enforce_smaller_or_equal_than::<_, _, F, _>(
139 cs.ns(|| "enforce smaller than modulus minus one div two"),
140 &a_bits,
141 F::modulus_minus_one_div_two(),
142 )?;
143
144 Ok(())
145 }
146
147 /// Helper function to check `a < b` and output a result bit. This function
148 /// verifies `a` and `b` are `<= (p-1)/2`.
149 fn is_smaller_than<CS: ConstraintSystem<F>>(
150 mut cs: CS,
151 a: &FpGadget<F>,
152 b: &FpGadget<F>,
153 ) -> Result<Boolean, SynthesisError> {
154 Self::check_smaller_than_mod_minus_one_div_two(cs.ns(|| "check a in range"), a)?;
155 Self::check_smaller_than_mod_minus_one_div_two(cs.ns(|| "check b in range"), b)?;
156 Self::is_smaller_than_unchecked(cs.ns(|| "enforce smaller than"), a, b)
157 }
158
159 /// Helper function to check `a < b` and output a result bit. This function
160 /// assumes `a` and `b` are `<= (p-1)/2` and does not generate constraints
161 /// to verify that.
162 fn is_smaller_than_unchecked<CS: ConstraintSystem<F>>(
163 mut cs: CS,
164 a: &FpGadget<F>,
165 b: &FpGadget<F>,
166 ) -> Result<Boolean, SynthesisError> {
167 let two = F::one() + F::one();
168 let d0 = a.sub(cs.ns(|| "a - b"), b)?;
169 let d = d0.mul_by_constant(cs.ns(|| "mul 2"), &two)?;
170 let d_bits = d.to_bits(cs.ns(|| "d to bits"))?;
171 let d_bits_len = d_bits.len();
172 Ok(d_bits[d_bits_len - 1])
173 }
174
175 /// Helper function to enforce `a < b`. This function verifies `a` and `b`
176 /// are `<= (p-1)/2`.
177 fn enforce_smaller_than<CS: ConstraintSystem<F>>(
178 mut cs: CS,
179 a: &FpGadget<F>,
180 b: &FpGadget<F>,
181 ) -> Result<(), SynthesisError> {
182 Self::check_smaller_than_mod_minus_one_div_two(cs.ns(|| "check a in range"), a)?;
183 Self::check_smaller_than_mod_minus_one_div_two(cs.ns(|| "check b in range"), b)?;
184 Self::enforce_smaller_than_unchecked(cs.ns(|| "enforce smaller than"), a, b)
185 }
186
187 /// Helper function to enforce `a < b`. This function assumes `a` and `b`
188 /// are `<= (p-1)/2` and does not generate constraints to verify that.
189 fn enforce_smaller_than_unchecked<CS: ConstraintSystem<F>>(
190 mut cs: CS,
191 a: &FpGadget<F>,
192 b: &FpGadget<F>,
193 ) -> Result<(), SynthesisError> {
194 let is_smaller_than = Self::is_smaller_than_unchecked(cs.ns(|| "is smaller than"), a, b)?;
195 cs.enforce(
196 || "enforce smaller than",
197 |_| is_smaller_than.lc(CS::one(), F::one()),
198 |lc| lc + (F::one(), CS::one()),
199 |lc| lc + (F::one(), CS::one()),
200 );
201
202 Ok(())
203 }
204}
205
206#[cfg(test)]
207mod test {
208 use rand::{Rng, SeedableRng};
209 use rand_xorshift::XorShiftRng;
210 use std::cmp::Ordering;
211
212 use crate::{
213 alloc::AllocGadget, fields::fp::FpGadget, test_constraint_system::TestConstraintSystem,
214 };
215 use algebra::{bls12_381::Fr, PrimeField, UniformRand};
216 use r1cs_core::ConstraintSystem;
217
218 #[test]
219 fn test_cmp() {
220 let mut rng = &mut XorShiftRng::from_seed([
221 0x5d, 0xbe, 0x62, 0x59, 0x8d, 0x31, 0x3d, 0x76, 0x32, 0x37, 0xdb, 0x17, 0xe5, 0xbc,
222 0x06, 0x54,
223 ]);
224 fn rand_in_range<R: Rng>(rng: &mut R) -> Fr {
225 let pminusonedivtwo = Fr::from_repr(Fr::modulus_minus_one_div_two());
226 let mut r;
227 loop {
228 r = Fr::rand(rng);
229 if r <= pminusonedivtwo {
230 break;
231 }
232 }
233 r
234 }
235 for i in 0..10 {
236 let mut cs = TestConstraintSystem::<Fr>::new();
237 let a = rand_in_range(&mut rng);
238 let a_var = FpGadget::<Fr>::alloc(cs.ns(|| "a"), || Ok(a)).unwrap();
239 let b = rand_in_range(&mut rng);
240 let b_var = FpGadget::<Fr>::alloc(cs.ns(|| "b"), || Ok(b)).unwrap();
241
242 match a.cmp(&b) {
243 Ordering::Less => {
244 a_var
245 .enforce_cmp(cs.ns(|| "smaller than test"), &b_var, Ordering::Less, false)
246 .unwrap();
247 a_var
248 .enforce_cmp(
249 cs.ns(|| "smaller than test 2"),
250 &b_var,
251 Ordering::Less,
252 true,
253 )
254 .unwrap();
255 }
256 Ordering::Greater => {
257 a_var
258 .enforce_cmp(
259 cs.ns(|| "smaller than test"),
260 &b_var,
261 Ordering::Greater,
262 false,
263 )
264 .unwrap();
265 a_var
266 .enforce_cmp(
267 cs.ns(|| "smaller than test 2"),
268 &b_var,
269 Ordering::Greater,
270 true,
271 )
272 .unwrap();
273 }
274 _ => {}
275 }
276
277 if i == 0 {
278 println!("number of constraints: {}", cs.num_constraints());
279 }
280 assert!(cs.is_satisfied());
281 }
282
283 for _i in 0..10 {
284 let mut cs = TestConstraintSystem::<Fr>::new();
285 let a = rand_in_range(&mut rng);
286 let a_var = FpGadget::<Fr>::alloc(cs.ns(|| "a"), || Ok(a)).unwrap();
287 let b = rand_in_range(&mut rng);
288 let b_var = FpGadget::<Fr>::alloc(cs.ns(|| "b"), || Ok(b)).unwrap();
289
290 match b.cmp(&a) {
291 Ordering::Less => {
292 a_var
293 .enforce_cmp(cs.ns(|| "smaller than test"), &b_var, Ordering::Less, false)
294 .unwrap();
295 a_var
296 .enforce_cmp(
297 cs.ns(|| "smaller than test 2"),
298 &b_var,
299 Ordering::Less,
300 true,
301 )
302 .unwrap();
303 }
304 Ordering::Greater => {
305 a_var
306 .enforce_cmp(
307 cs.ns(|| "smaller than test"),
308 &b_var,
309 Ordering::Greater,
310 false,
311 )
312 .unwrap();
313 a_var
314 .enforce_cmp(
315 cs.ns(|| "smaller than test 2"),
316 &b_var,
317 Ordering::Greater,
318 true,
319 )
320 .unwrap();
321 }
322 _ => {}
323 }
324
325 assert!(!cs.is_satisfied());
326 }
327
328 for _i in 0..10 {
329 let mut cs = TestConstraintSystem::<Fr>::new();
330 let a = rand_in_range(&mut rng);
331 let a_var = FpGadget::<Fr>::alloc(cs.ns(|| "a"), || Ok(a)).unwrap();
332 a_var
333 .enforce_cmp(cs.ns(|| "smaller than test"), &a_var, Ordering::Less, false)
334 .unwrap();
335
336 assert!(!cs.is_satisfied());
337 }
338
339 for _i in 0..10 {
340 let mut cs = TestConstraintSystem::<Fr>::new();
341 let a = rand_in_range(&mut rng);
342 let a_var = FpGadget::<Fr>::alloc(cs.ns(|| "a"), || Ok(a)).unwrap();
343 a_var
344 .enforce_cmp(
345 cs.ns(|| "smaller than or equal to test"),
346 &a_var,
347 Ordering::Less,
348 true,
349 )
350 .unwrap();
351
352 assert!(cs.is_satisfied());
353 }
354 }
355}