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 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#[cfg(test)]
183mod test {
184 use rand::{Rng, SeedableRng};
185 use rand_xorshift::XorShiftRng;
186 use std::cmp::Ordering;
187
188 use crate::{
189 alloc::AllocGadget, fields::fp::FpGadget, test_constraint_system::TestConstraintSystem,
190 };
191 use algebra::{bls12_381::Fr, PrimeField, UniformRand};
192 use r1cs_core::ConstraintSystem;
193
194 #[test]
195 fn test_cmp() {
196 let mut rng = &mut XorShiftRng::from_seed([
197 0x5d, 0xbe, 0x62, 0x59, 0x8d, 0x31, 0x3d, 0x76, 0x32, 0x37, 0xdb, 0x17, 0xe5, 0xbc,
198 0x06, 0x54,
199 ]);
200 fn rand_in_range<R: Rng>(rng: &mut R) -> Fr {
201 let pminusonedivtwo = Fr::from_repr(Fr::modulus_minus_one_div_two());
202 let mut r;
203 loop {
204 r = Fr::rand(rng);
205 if r <= pminusonedivtwo {
206 break;
207 }
208 }
209 r
210 }
211 for i in 0..10 {
212 let mut cs = TestConstraintSystem::<Fr>::new();
213 let a = rand_in_range(&mut rng);
214 let a_var = FpGadget::<Fr>::alloc(cs.ns(|| "a"), || Ok(a)).unwrap();
215 let b = rand_in_range(&mut rng);
216 let b_var = FpGadget::<Fr>::alloc(cs.ns(|| "b"), || Ok(b)).unwrap();
217
218 match a.cmp(&b) {
219 Ordering::Less => {
220 a_var
221 .enforce_cmp(cs.ns(|| "smaller than test"), &b_var, Ordering::Less, false)
222 .unwrap();
223 a_var
224 .enforce_cmp(
225 cs.ns(|| "smaller than test 2"),
226 &b_var,
227 Ordering::Less,
228 true,
229 )
230 .unwrap();
231 },
232 Ordering::Greater => {
233 a_var
234 .enforce_cmp(
235 cs.ns(|| "smaller than test"),
236 &b_var,
237 Ordering::Greater,
238 false,
239 )
240 .unwrap();
241 a_var
242 .enforce_cmp(
243 cs.ns(|| "smaller than test 2"),
244 &b_var,
245 Ordering::Greater,
246 true,
247 )
248 .unwrap();
249 },
250 _ => {},
251 }
252
253 if i == 0 {
254 println!("number of constraints: {}", cs.num_constraints());
255 }
256 assert!(cs.is_satisfied());
257 }
258
259 for _i in 0..10 {
260 let mut cs = TestConstraintSystem::<Fr>::new();
261 let a = rand_in_range(&mut rng);
262 let a_var = FpGadget::<Fr>::alloc(cs.ns(|| "a"), || Ok(a)).unwrap();
263 let b = rand_in_range(&mut rng);
264 let b_var = FpGadget::<Fr>::alloc(cs.ns(|| "b"), || Ok(b)).unwrap();
265
266 match b.cmp(&a) {
267 Ordering::Less => {
268 a_var
269 .enforce_cmp(cs.ns(|| "smaller than test"), &b_var, Ordering::Less, false)
270 .unwrap();
271 a_var
272 .enforce_cmp(
273 cs.ns(|| "smaller than test 2"),
274 &b_var,
275 Ordering::Less,
276 true,
277 )
278 .unwrap();
279 },
280 Ordering::Greater => {
281 a_var
282 .enforce_cmp(
283 cs.ns(|| "smaller than test"),
284 &b_var,
285 Ordering::Greater,
286 false,
287 )
288 .unwrap();
289 a_var
290 .enforce_cmp(
291 cs.ns(|| "smaller than test 2"),
292 &b_var,
293 Ordering::Greater,
294 true,
295 )
296 .unwrap();
297 },
298 _ => {},
299 }
300
301 assert!(!cs.is_satisfied());
302 }
303
304 for _i in 0..10 {
305 let mut cs = TestConstraintSystem::<Fr>::new();
306 let a = rand_in_range(&mut rng);
307 let a_var = FpGadget::<Fr>::alloc(cs.ns(|| "a"), || Ok(a)).unwrap();
308 a_var
309 .enforce_cmp(cs.ns(|| "smaller than test"), &a_var, Ordering::Less, false)
310 .unwrap();
311
312 assert!(!cs.is_satisfied());
313 }
314
315 for _i in 0..10 {
316 let mut cs = TestConstraintSystem::<Fr>::new();
317 let a = rand_in_range(&mut rng);
318 let a_var = FpGadget::<Fr>::alloc(cs.ns(|| "a"), || Ok(a)).unwrap();
319 a_var
320 .enforce_cmp(
321 cs.ns(|| "smaller than or equal to test"),
322 &a_var,
323 Ordering::Less,
324 true,
325 )
326 .unwrap();
327
328 assert!(cs.is_satisfied());
329 }
330 }
331}