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