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