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