plonky2-u32/src/gates/comparison.rs
src/gates/comparison.rsRaw
1use alloc::boxed::Box;
2use alloc::string::String;
3use alloc::vec::Vec;
4use alloc::{format, vec};
5use core::marker::PhantomData;
6
7use plonky2::field::extension::Extendable;
8use plonky2::field::packed::PackedField;
9use plonky2::field::types::{Field, Field64};
10use plonky2::gates::gate::Gate;
11use plonky2::gates::packed_util::PackedEvaluableBase;
12use plonky2::gates::util::StridedConstraintConsumer;
13use plonky2::hash::hash_types::RichField;
14use plonky2::iop::ext_target::ExtensionTarget;
15use plonky2::iop::generator::{GeneratedValues, SimpleGenerator, WitnessGenerator};
16use plonky2::iop::target::Target;
17use plonky2::iop::wire::Wire;
18use plonky2::iop::witness::{PartitionWitness, Witness, WitnessWrite};
19use plonky2::plonk::circuit_builder::CircuitBuilder;
20use plonky2::plonk::plonk_common::{reduce_with_powers, reduce_with_powers_ext_circuit};
21use plonky2::plonk::vars::{
22 EvaluationTargets, EvaluationVars, EvaluationVarsBase, EvaluationVarsBaseBatch,
23 EvaluationVarsBasePacked,
24};
25use plonky2::util::{bits_u64, ceil_div_usize};
26
27/// A gate for checking that one value is less than or equal to another.
28#[derive(Clone, Debug)]
29pub struct ComparisonGate<F: Field64 + Extendable<D>, const D: usize> {
30 pub(crate) num_bits: usize,
31 pub(crate) num_chunks: usize,
32 _phantom: PhantomData<F>,
33}
34
35impl<F: RichField + Extendable<D>, const D: usize> ComparisonGate<F, D> {
36 pub fn new(num_bits: usize, num_chunks: usize) -> Self {
37 debug_assert!(num_bits < bits_u64(F::ORDER));
38 Self {
39 num_bits,
40 num_chunks,
41 _phantom: PhantomData,
42 }
43 }
44
45 pub fn chunk_bits(&self) -> usize {
46 ceil_div_usize(self.num_bits, self.num_chunks)
47 }
48
49 pub fn wire_first_input(&self) -> usize {
50 0
51 }
52
53 pub fn wire_second_input(&self) -> usize {
54 1
55 }
56
57 pub fn wire_result_bool(&self) -> usize {
58 2
59 }
60
61 pub fn wire_most_significant_diff(&self) -> usize {
62 3
63 }
64
65 pub fn wire_first_chunk_val(&self, chunk: usize) -> usize {
66 debug_assert!(chunk < self.num_chunks);
67 4 + chunk
68 }
69
70 pub fn wire_second_chunk_val(&self, chunk: usize) -> usize {
71 debug_assert!(chunk < self.num_chunks);
72 4 + self.num_chunks + chunk
73 }
74
75 pub fn wire_equality_dummy(&self, chunk: usize) -> usize {
76 debug_assert!(chunk < self.num_chunks);
77 4 + 2 * self.num_chunks + chunk
78 }
79
80 pub fn wire_chunks_equal(&self, chunk: usize) -> usize {
81 debug_assert!(chunk < self.num_chunks);
82 4 + 3 * self.num_chunks + chunk
83 }
84
85 pub fn wire_intermediate_value(&self, chunk: usize) -> usize {
86 debug_assert!(chunk < self.num_chunks);
87 4 + 4 * self.num_chunks + chunk
88 }
89
90 /// The `bit_index`th bit of 2^n - 1 + most_significant_diff.
91 pub fn wire_most_significant_diff_bit(&self, bit_index: usize) -> usize {
92 4 + 5 * self.num_chunks + bit_index
93 }
94}
95
96impl<F: RichField + Extendable<D>, const D: usize> Gate<F, D> for ComparisonGate<F, D> {
97 fn id(&self) -> String {
98 format!("{self:?}<D={D}>")
99 }
100
101 fn eval_unfiltered(&self, vars: EvaluationVars<F, D>) -> Vec<F::Extension> {
102 let mut constraints = Vec::with_capacity(self.num_constraints());
103
104 let first_input = vars.local_wires[self.wire_first_input()];
105 let second_input = vars.local_wires[self.wire_second_input()];
106
107 // Get chunks and assert that they match
108 let first_chunks: Vec<F::Extension> = (0..self.num_chunks)
109 .map(|i| vars.local_wires[self.wire_first_chunk_val(i)])
110 .collect();
111 let second_chunks: Vec<F::Extension> = (0..self.num_chunks)
112 .map(|i| vars.local_wires[self.wire_second_chunk_val(i)])
113 .collect();
114
115 let first_chunks_combined = reduce_with_powers(
116 &first_chunks,
117 F::Extension::from_canonical_usize(1 << self.chunk_bits()),
118 );
119 let second_chunks_combined = reduce_with_powers(
120 &second_chunks,
121 F::Extension::from_canonical_usize(1 << self.chunk_bits()),
122 );
123
124 constraints.push(first_chunks_combined - first_input);
125 constraints.push(second_chunks_combined - second_input);
126
127 let chunk_size = 1 << self.chunk_bits();
128
129 let mut most_significant_diff_so_far = F::Extension::ZERO;
130
131 for i in 0..self.num_chunks {
132 // Range-check the chunks to be less than `chunk_size`.
133 let first_product: F::Extension = (0..chunk_size)
134 .map(|x| first_chunks[i] - F::Extension::from_canonical_usize(x))
135 .product();
136 let second_product: F::Extension = (0..chunk_size)
137 .map(|x| second_chunks[i] - F::Extension::from_canonical_usize(x))
138 .product();
139 constraints.push(first_product);
140 constraints.push(second_product);
141
142 let difference = second_chunks[i] - first_chunks[i];
143 let equality_dummy = vars.local_wires[self.wire_equality_dummy(i)];
144 let chunks_equal = vars.local_wires[self.wire_chunks_equal(i)];
145
146 // Two constraints to assert that `chunks_equal` is valid.
147 constraints.push(difference * equality_dummy - (F::Extension::ONE - chunks_equal));
148 constraints.push(chunks_equal * difference);
149
150 // Update `most_significant_diff_so_far`.
151 let intermediate_value = vars.local_wires[self.wire_intermediate_value(i)];
152 constraints.push(intermediate_value - chunks_equal * most_significant_diff_so_far);
153 most_significant_diff_so_far =
154 intermediate_value + (F::Extension::ONE - chunks_equal) * difference;
155 }
156
157 let most_significant_diff = vars.local_wires[self.wire_most_significant_diff()];
158 constraints.push(most_significant_diff - most_significant_diff_so_far);
159
160 let most_significant_diff_bits: Vec<F::Extension> = (0..self.chunk_bits() + 1)
161 .map(|i| vars.local_wires[self.wire_most_significant_diff_bit(i)])
162 .collect();
163
164 // Range-check the bits.
165 for &bit in &most_significant_diff_bits {
166 constraints.push(bit * (F::Extension::ONE - bit));
167 }
168
169 let bits_combined = reduce_with_powers(&most_significant_diff_bits, F::Extension::TWO);
170 let two_n = F::Extension::from_canonical_u64(1 << self.chunk_bits());
171 constraints.push((two_n + most_significant_diff) - bits_combined);
172
173 // Iff first <= second, the top (n + 1st) bit of (2^n + most_significant_diff) will be 1.
174 let result_bool = vars.local_wires[self.wire_result_bool()];
175 constraints.push(result_bool - most_significant_diff_bits[self.chunk_bits()]);
176
177 constraints
178 }
179
180 fn eval_unfiltered_base_one(
181 &self,
182 _vars: EvaluationVarsBase<F>,
183 _yield_constr: StridedConstraintConsumer<F>,
184 ) {
185 panic!("use eval_unfiltered_base_packed instead");
186 }
187
188 fn eval_unfiltered_base_batch(&self, vars_base: EvaluationVarsBaseBatch<F>) -> Vec<F> {
189 self.eval_unfiltered_base_batch_packed(vars_base)
190 }
191
192 fn eval_unfiltered_circuit(
193 &self,
194 builder: &mut CircuitBuilder<F, D>,
195 vars: EvaluationTargets<D>,
196 ) -> Vec<ExtensionTarget<D>> {
197 let mut constraints = Vec::with_capacity(self.num_constraints());
198
199 let first_input = vars.local_wires[self.wire_first_input()];
200 let second_input = vars.local_wires[self.wire_second_input()];
201
202 // Get chunks and assert that they match
203 let first_chunks: Vec<ExtensionTarget<D>> = (0..self.num_chunks)
204 .map(|i| vars.local_wires[self.wire_first_chunk_val(i)])
205 .collect();
206 let second_chunks: Vec<ExtensionTarget<D>> = (0..self.num_chunks)
207 .map(|i| vars.local_wires[self.wire_second_chunk_val(i)])
208 .collect();
209
210 let chunk_base = builder.constant(F::from_canonical_usize(1 << self.chunk_bits()));
211 let first_chunks_combined =
212 reduce_with_powers_ext_circuit(builder, &first_chunks, chunk_base);
213 let second_chunks_combined =
214 reduce_with_powers_ext_circuit(builder, &second_chunks, chunk_base);
215
216 constraints.push(builder.sub_extension(first_chunks_combined, first_input));
217 constraints.push(builder.sub_extension(second_chunks_combined, second_input));
218
219 let chunk_size = 1 << self.chunk_bits();
220
221 let mut most_significant_diff_so_far = builder.zero_extension();
222
223 let one = builder.one_extension();
224 // Find the chosen chunk.
225 for i in 0..self.num_chunks {
226 // Range-check the chunks to be less than `chunk_size`.
227 let mut first_product = one;
228 let mut second_product = one;
229 for x in 0..chunk_size {
230 let x_f = builder.constant_extension(F::Extension::from_canonical_usize(x));
231 let first_diff = builder.sub_extension(first_chunks[i], x_f);
232 let second_diff = builder.sub_extension(second_chunks[i], x_f);
233 first_product = builder.mul_extension(first_product, first_diff);
234 second_product = builder.mul_extension(second_product, second_diff);
235 }
236 constraints.push(first_product);
237 constraints.push(second_product);
238
239 let difference = builder.sub_extension(second_chunks[i], first_chunks[i]);
240 let equality_dummy = vars.local_wires[self.wire_equality_dummy(i)];
241 let chunks_equal = vars.local_wires[self.wire_chunks_equal(i)];
242
243 // Two constraints to assert that `chunks_equal` is valid.
244 let diff_times_equal = builder.mul_extension(difference, equality_dummy);
245 let not_equal = builder.sub_extension(one, chunks_equal);
246 constraints.push(builder.sub_extension(diff_times_equal, not_equal));
247 constraints.push(builder.mul_extension(chunks_equal, difference));
248
249 // Update `most_significant_diff_so_far`.
250 let intermediate_value = vars.local_wires[self.wire_intermediate_value(i)];
251 let old_diff = builder.mul_extension(chunks_equal, most_significant_diff_so_far);
252 constraints.push(builder.sub_extension(intermediate_value, old_diff));
253
254 let not_equal = builder.sub_extension(one, chunks_equal);
255 let new_diff = builder.mul_extension(not_equal, difference);
256 most_significant_diff_so_far = builder.add_extension(intermediate_value, new_diff);
257 }
258
259 let most_significant_diff = vars.local_wires[self.wire_most_significant_diff()];
260 constraints
261 .push(builder.sub_extension(most_significant_diff, most_significant_diff_so_far));
262
263 let most_significant_diff_bits: Vec<ExtensionTarget<D>> = (0..self.chunk_bits() + 1)
264 .map(|i| vars.local_wires[self.wire_most_significant_diff_bit(i)])
265 .collect();
266
267 // Range-check the bits.
268 for &this_bit in &most_significant_diff_bits {
269 let inverse = builder.sub_extension(one, this_bit);
270 constraints.push(builder.mul_extension(this_bit, inverse));
271 }
272
273 let two = builder.two();
274 let bits_combined =
275 reduce_with_powers_ext_circuit(builder, &most_significant_diff_bits, two);
276 let two_n =
277 builder.constant_extension(F::Extension::from_canonical_u64(1 << self.chunk_bits()));
278 let sum = builder.add_extension(two_n, most_significant_diff);
279 constraints.push(builder.sub_extension(sum, bits_combined));
280
281 // Iff first <= second, the top (n + 1st) bit of (2^n + most_significant_diff) will be 1.
282 let result_bool = vars.local_wires[self.wire_result_bool()];
283 constraints.push(
284 builder.sub_extension(result_bool, most_significant_diff_bits[self.chunk_bits()]),
285 );
286
287 constraints
288 }
289
290 fn generators(&self, row: usize, _local_constants: &[F]) -> Vec<Box<dyn WitnessGenerator<F>>> {
291 let gen = ComparisonGenerator::<F, D> {
292 row,
293 gate: self.clone(),
294 };
295 vec![Box::new(gen.adapter())]
296 }
297
298 fn num_wires(&self) -> usize {
299 4 + 5 * self.num_chunks + (self.chunk_bits() + 1)
300 }
301
302 fn num_constants(&self) -> usize {
303 0
304 }
305
306 fn degree(&self) -> usize {
307 1 << self.chunk_bits()
308 }
309
310 fn num_constraints(&self) -> usize {
311 6 + 5 * self.num_chunks + self.chunk_bits()
312 }
313}
314
315impl<F: RichField + Extendable<D>, const D: usize> PackedEvaluableBase<F, D>
316 for ComparisonGate<F, D>
317{
318 fn eval_unfiltered_base_packed<P: PackedField<Scalar = F>>(
319 &self,
320 vars: EvaluationVarsBasePacked<P>,
321 mut yield_constr: StridedConstraintConsumer<P>,
322 ) {
323 let first_input = vars.local_wires[self.wire_first_input()];
324 let second_input = vars.local_wires[self.wire_second_input()];
325
326 // Get chunks and assert that they match
327 let first_chunks: Vec<_> = (0..self.num_chunks)
328 .map(|i| vars.local_wires[self.wire_first_chunk_val(i)])
329 .collect();
330 let second_chunks: Vec<_> = (0..self.num_chunks)
331 .map(|i| vars.local_wires[self.wire_second_chunk_val(i)])
332 .collect();
333
334 let first_chunks_combined = reduce_with_powers(
335 &first_chunks,
336 F::from_canonical_usize(1 << self.chunk_bits()),
337 );
338 let second_chunks_combined = reduce_with_powers(
339 &second_chunks,
340 F::from_canonical_usize(1 << self.chunk_bits()),
341 );
342
343 yield_constr.one(first_chunks_combined - first_input);
344 yield_constr.one(second_chunks_combined - second_input);
345
346 let chunk_size = 1 << self.chunk_bits();
347
348 let mut most_significant_diff_so_far = P::ZEROS;
349
350 for i in 0..self.num_chunks {
351 // Range-check the chunks to be less than `chunk_size`.
352 let first_product: P = (0..chunk_size)
353 .map(|x| first_chunks[i] - F::from_canonical_usize(x))
354 .product();
355 let second_product: P = (0..chunk_size)
356 .map(|x| second_chunks[i] - F::from_canonical_usize(x))
357 .product();
358 yield_constr.one(first_product);
359 yield_constr.one(second_product);
360
361 let difference = second_chunks[i] - first_chunks[i];
362 let equality_dummy = vars.local_wires[self.wire_equality_dummy(i)];
363 let chunks_equal = vars.local_wires[self.wire_chunks_equal(i)];
364
365 // Two constraints to assert that `chunks_equal` is valid.
366 yield_constr.one(difference * equality_dummy - (P::ONES - chunks_equal));
367 yield_constr.one(chunks_equal * difference);
368
369 // Update `most_significant_diff_so_far`.
370 let intermediate_value = vars.local_wires[self.wire_intermediate_value(i)];
371 yield_constr.one(intermediate_value - chunks_equal * most_significant_diff_so_far);
372 most_significant_diff_so_far =
373 intermediate_value + (P::ONES - chunks_equal) * difference;
374 }
375
376 let most_significant_diff = vars.local_wires[self.wire_most_significant_diff()];
377 yield_constr.one(most_significant_diff - most_significant_diff_so_far);
378
379 let most_significant_diff_bits: Vec<_> = (0..self.chunk_bits() + 1)
380 .map(|i| vars.local_wires[self.wire_most_significant_diff_bit(i)])
381 .collect();
382
383 // Range-check the bits.
384 for &bit in &most_significant_diff_bits {
385 yield_constr.one(bit * (P::ONES - bit));
386 }
387
388 let bits_combined = reduce_with_powers(&most_significant_diff_bits, F::TWO);
389 let two_n = F::from_canonical_u64(1 << self.chunk_bits());
390 yield_constr.one((most_significant_diff + two_n) - bits_combined);
391
392 // Iff first <= second, the top (n + 1st) bit of (2^n - 1 + most_significant_diff) will be 1.
393 let result_bool = vars.local_wires[self.wire_result_bool()];
394 yield_constr.one(result_bool - most_significant_diff_bits[self.chunk_bits()]);
395 }
396}
397
398#[derive(Debug)]
399struct ComparisonGenerator<F: RichField + Extendable<D>, const D: usize> {
400 row: usize,
401 gate: ComparisonGate<F, D>,
402}
403
404impl<F: RichField + Extendable<D>, const D: usize> SimpleGenerator<F>
405 for ComparisonGenerator<F, D>
406{
407 fn dependencies(&self) -> Vec<Target> {
408 let local_target = |column| Target::wire(self.row, column);
409
410 vec![
411 local_target(self.gate.wire_first_input()),
412 local_target(self.gate.wire_second_input()),
413 ]
414 }
415
416 fn run_once(&self, witness: &PartitionWitness<F>, out_buffer: &mut GeneratedValues<F>) {
417 let local_wire = |column| Wire {
418 row: self.row,
419 column,
420 };
421
422 let get_local_wire = |column| witness.get_wire(local_wire(column));
423
424 let first_input = get_local_wire(self.gate.wire_first_input());
425 let second_input = get_local_wire(self.gate.wire_second_input());
426
427 let first_input_u64 = first_input.to_canonical_u64();
428 let second_input_u64 = second_input.to_canonical_u64();
429
430 let result = F::from_canonical_usize((first_input_u64 <= second_input_u64) as usize);
431
432 let chunk_size = 1 << self.gate.chunk_bits();
433 let first_input_chunks: Vec<F> = (0..self.gate.num_chunks)
434 .scan(first_input_u64, |acc, _| {
435 let tmp = *acc % chunk_size;
436 *acc /= chunk_size;
437 Some(F::from_canonical_u64(tmp))
438 })
439 .collect();
440 let second_input_chunks: Vec<F> = (0..self.gate.num_chunks)
441 .scan(second_input_u64, |acc, _| {
442 let tmp = *acc % chunk_size;
443 *acc /= chunk_size;
444 Some(F::from_canonical_u64(tmp))
445 })
446 .collect();
447
448 let chunks_equal: Vec<F> = (0..self.gate.num_chunks)
449 .map(|i| F::from_bool(first_input_chunks[i] == second_input_chunks[i]))
450 .collect();
451 let equality_dummies: Vec<F> = first_input_chunks
452 .iter()
453 .zip(second_input_chunks.iter())
454 .map(|(&f, &s)| if f == s { F::ONE } else { F::ONE / (s - f) })
455 .collect();
456
457 let mut most_significant_diff_so_far = F::ZERO;
458 let mut intermediate_values = Vec::new();
459 for i in 0..self.gate.num_chunks {
460 if first_input_chunks[i] != second_input_chunks[i] {
461 most_significant_diff_so_far = second_input_chunks[i] - first_input_chunks[i];
462 intermediate_values.push(F::ZERO);
463 } else {
464 intermediate_values.push(most_significant_diff_so_far);
465 }
466 }
467 let most_significant_diff = most_significant_diff_so_far;
468
469 let two_n = F::from_canonical_usize(1 << self.gate.chunk_bits());
470 let two_n_plus_msd = (two_n + most_significant_diff).to_canonical_u64();
471
472 let msd_bits_u64: Vec<u64> = (0..self.gate.chunk_bits() + 1)
473 .scan(two_n_plus_msd, |acc, _| {
474 let tmp = *acc % 2;
475 *acc /= 2;
476 Some(tmp)
477 })
478 .collect();
479 let msd_bits: Vec<F> = msd_bits_u64
480 .iter()
481 .map(|x| F::from_canonical_u64(*x))
482 .collect();
483
484 out_buffer.set_wire(local_wire(self.gate.wire_result_bool()), result);
485 out_buffer.set_wire(
486 local_wire(self.gate.wire_most_significant_diff()),
487 most_significant_diff,
488 );
489 for i in 0..self.gate.num_chunks {
490 out_buffer.set_wire(
491 local_wire(self.gate.wire_first_chunk_val(i)),
492 first_input_chunks[i],
493 );
494 out_buffer.set_wire(
495 local_wire(self.gate.wire_second_chunk_val(i)),
496 second_input_chunks[i],
497 );
498 out_buffer.set_wire(
499 local_wire(self.gate.wire_equality_dummy(i)),
500 equality_dummies[i],
501 );
502 out_buffer.set_wire(local_wire(self.gate.wire_chunks_equal(i)), chunks_equal[i]);
503 out_buffer.set_wire(
504 local_wire(self.gate.wire_intermediate_value(i)),
505 intermediate_values[i],
506 );
507 }
508 for i in 0..self.gate.chunk_bits() + 1 {
509 out_buffer.set_wire(
510 local_wire(self.gate.wire_most_significant_diff_bit(i)),
511 msd_bits[i],
512 );
513 }
514 }
515}
516
517#[cfg(test)]
518mod tests {
519 use anyhow::Result;
520 use plonky2::field::goldilocks_field::GoldilocksField;
521 use plonky2::field::types::{PrimeField64, Sample};
522 use plonky2::gates::gate_testing::{test_eval_fns, test_low_degree};
523 use plonky2::hash::hash_types::HashOut;
524 use plonky2::plonk::config::{GenericConfig, PoseidonGoldilocksConfig};
525 use rand::rngs::OsRng;
526 use rand::Rng;
527
528 use super::*;
529
530 #[test]
531 fn wire_indices() {
532 type CG = ComparisonGate<GoldilocksField, 4>;
533 let num_bits = 40;
534 let num_chunks = 5;
535
536 let gate = CG {
537 num_bits,
538 num_chunks,
539 _phantom: PhantomData,
540 };
541
542 assert_eq!(gate.wire_first_input(), 0);
543 assert_eq!(gate.wire_second_input(), 1);
544 assert_eq!(gate.wire_result_bool(), 2);
545 assert_eq!(gate.wire_most_significant_diff(), 3);
546 assert_eq!(gate.wire_first_chunk_val(0), 4);
547 assert_eq!(gate.wire_first_chunk_val(4), 8);
548 assert_eq!(gate.wire_second_chunk_val(0), 9);
549 assert_eq!(gate.wire_second_chunk_val(4), 13);
550 assert_eq!(gate.wire_equality_dummy(0), 14);
551 assert_eq!(gate.wire_equality_dummy(4), 18);
552 assert_eq!(gate.wire_chunks_equal(0), 19);
553 assert_eq!(gate.wire_chunks_equal(4), 23);
554 assert_eq!(gate.wire_intermediate_value(0), 24);
555 assert_eq!(gate.wire_intermediate_value(4), 28);
556 assert_eq!(gate.wire_most_significant_diff_bit(0), 29);
557 assert_eq!(gate.wire_most_significant_diff_bit(8), 37);
558 }
559
560 #[test]
561 fn low_degree() {
562 let num_bits = 40;
563 let num_chunks = 5;
564
565 test_low_degree::<GoldilocksField, _, 4>(ComparisonGate::<_, 4>::new(num_bits, num_chunks))
566 }
567
568 #[test]
569 fn eval_fns() -> Result<()> {
570 let num_bits = 40;
571 let num_chunks = 5;
572 const D: usize = 2;
573 type C = PoseidonGoldilocksConfig;
574 type F = <C as GenericConfig<D>>::F;
575
576 test_eval_fns::<F, C, _, D>(ComparisonGate::<_, 2>::new(num_bits, num_chunks))
577 }
578
579 #[test]
580 fn test_gate_constraint() {
581 const D: usize = 2;
582 type C = PoseidonGoldilocksConfig;
583 type F = <C as GenericConfig<D>>::F;
584 type FF = <C as GenericConfig<D>>::FE;
585
586 let num_bits = 40;
587 let num_chunks = 5;
588 let chunk_bits = num_bits / num_chunks;
589
590 // Returns the local wires for a comparison gate given the two inputs.
591 let get_wires = |first_input: F, second_input: F| -> Vec<FF> {
592 let mut v = Vec::new();
593
594 let first_input_u64 = first_input.to_canonical_u64();
595 let second_input_u64 = second_input.to_canonical_u64();
596
597 let result_bool = F::from_bool(first_input_u64 <= second_input_u64);
598
599 let chunk_size = 1 << chunk_bits;
600 let mut first_input_chunks: Vec<F> = (0..num_chunks)
601 .scan(first_input_u64, |acc, _| {
602 let tmp = *acc % chunk_size;
603 *acc /= chunk_size;
604 Some(F::from_canonical_u64(tmp))
605 })
606 .collect();
607 let mut second_input_chunks: Vec<F> = (0..num_chunks)
608 .scan(second_input_u64, |acc, _| {
609 let tmp = *acc % chunk_size;
610 *acc /= chunk_size;
611 Some(F::from_canonical_u64(tmp))
612 })
613 .collect();
614
615 let mut chunks_equal: Vec<F> = (0..num_chunks)
616 .map(|i| F::from_bool(first_input_chunks[i] == second_input_chunks[i]))
617 .collect();
618 let mut equality_dummies: Vec<F> = first_input_chunks
619 .iter()
620 .zip(second_input_chunks.iter())
621 .map(|(&f, &s)| if f == s { F::ONE } else { F::ONE / (s - f) })
622 .collect();
623
624 let mut most_significant_diff_so_far = F::ZERO;
625 let mut intermediate_values = Vec::new();
626 for i in 0..num_chunks {
627 if first_input_chunks[i] != second_input_chunks[i] {
628 most_significant_diff_so_far = second_input_chunks[i] - first_input_chunks[i];
629 intermediate_values.push(F::ZERO);
630 } else {
631 intermediate_values.push(most_significant_diff_so_far);
632 }
633 }
634 let most_significant_diff = most_significant_diff_so_far;
635
636 let two_n_plus_msd =
637 (1 << chunk_bits) as u64 + most_significant_diff.to_canonical_u64();
638 let mut msd_bits: Vec<F> = (0..chunk_bits + 1)
639 .scan(two_n_plus_msd, |acc, _| {
640 let tmp = *acc % 2;
641 *acc /= 2;
642 Some(F::from_canonical_u64(tmp))
643 })
644 .collect();
645
646 v.push(first_input);
647 v.push(second_input);
648 v.push(result_bool);
649 v.push(most_significant_diff);
650 v.append(&mut first_input_chunks);
651 v.append(&mut second_input_chunks);
652 v.append(&mut equality_dummies);
653 v.append(&mut chunks_equal);
654 v.append(&mut intermediate_values);
655 v.append(&mut msd_bits);
656
657 v.iter().map(|&x| x.into()).collect()
658 };
659
660 let mut rng = OsRng;
661 let max: u64 = 1 << (num_bits - 1);
662 let first_input_u64 = rng.gen_range(0..max);
663 let second_input_u64 = {
664 let mut val = rng.gen_range(0..max);
665 while val < first_input_u64 {
666 val = rng.gen_range(0..max);
667 }
668 val
669 };
670
671 let first_input = F::from_canonical_u64(first_input_u64);
672 let second_input = F::from_canonical_u64(second_input_u64);
673
674 let less_than_gate = ComparisonGate::<F, D> {
675 num_bits,
676 num_chunks,
677 _phantom: PhantomData,
678 };
679 let less_than_vars = EvaluationVars {
680 local_constants: &[],
681 local_wires: &get_wires(first_input, second_input),
682 public_inputs_hash: &HashOut::rand(),
683 };
684 assert!(
685 less_than_gate
686 .eval_unfiltered(less_than_vars)
687 .iter()
688 .all(|x| x.is_zero()),
689 "Gate constraints are not satisfied."
690 );
691
692 let equal_gate = ComparisonGate::<F, D> {
693 num_bits,
694 num_chunks,
695 _phantom: PhantomData,
696 };
697 let equal_vars = EvaluationVars {
698 local_constants: &[],
699 local_wires: &get_wires(first_input, first_input),
700 public_inputs_hash: &HashOut::rand(),
701 };
702 assert!(
703 equal_gate
704 .eval_unfiltered(equal_vars)
705 .iter()
706 .all(|x| x.is_zero()),
707 "Gate constraints are not satisfied."
708 );
709 }
710}