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