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