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