ark-r1cs-std/r1cs-std/src/bits/boolean.rs
r1cs-std/src/bits/boolean.rsRaw
1use algebra::{BitIterator, Field, PrimeField};
2
3use crate::{prelude::*, Assignment, Vec};
4use core::borrow::Borrow;
5use r1cs_core::{ConstraintSystem, ConstraintVar, LinearCombination, SynthesisError, Variable};
6
7/// Represents a variable in the constraint system which is guaranteed
8/// to be either zero or one.
9#[derive(Copy, Clone, Debug)]
10pub struct AllocatedBit {
11 variable: Variable,
12 value: Option<bool>,
13}
14
15impl AllocatedBit {
16 pub fn get_value(&self) -> Option<bool> {
17 self.value
18 }
19
20 pub fn get_variable(&self) -> Variable {
21 self.variable
22 }
23
24 /// Performs an XOR operation over the two operands, returning
25 /// an `AllocatedBit`.
26 pub fn xor<ConstraintF, CS>(mut cs: CS, a: &Self, b: &Self) -> Result<Self, SynthesisError>
27 where
28 ConstraintF: Field,
29 CS: ConstraintSystem<ConstraintF>,
30 {
31 let mut result_value = None;
32
33 let result_var = cs.alloc(
34 || "xor result",
35 || {
36 if a.value.get()? ^ b.value.get()? {
37 result_value = Some(true);
38
39 Ok(ConstraintF::one())
40 } else {
41 result_value = Some(false);
42
43 Ok(ConstraintF::zero())
44 }
45 },
46 )?;
47
48 // Constrain (a + a) * (b) = (a + b - c)
49 // Given that a and b are boolean constrained, if they
50 // are equal, the only solution for c is 0, and if they
51 // are different, the only solution for c is 1.
52 //
53 // ¬(a ∧ b) ∧ ¬(¬a ∧ ¬b) = c
54 // (1 - (a * b)) * (1 - ((1 - a) * (1 - b))) = c
55 // (1 - ab) * (1 - (1 - a - b + ab)) = c
56 // (1 - ab) * (a + b - ab) = c
57 // a + b - ab - (a^2)b - (b^2)a + (a^2)(b^2) = c
58 // a + b - ab - ab - ab + ab = c
59 // a + b - 2ab = c
60 // -2a * b = c - a - b
61 // 2a * b = a + b - c
62 // (a + a) * b = a + b - c
63 cs.enforce(
64 || "xor constraint",
65 |lc| lc + a.variable + a.variable,
66 |lc| lc + b.variable,
67 |lc| lc + a.variable + b.variable - result_var,
68 );
69
70 Ok(AllocatedBit {
71 variable: result_var,
72 value: result_value,
73 })
74 }
75
76 /// Performs an AND operation over the two operands, returning
77 /// an `AllocatedBit`.
78 pub fn and<ConstraintF, CS>(mut cs: CS, a: &Self, b: &Self) -> Result<Self, SynthesisError>
79 where
80 ConstraintF: Field,
81 CS: ConstraintSystem<ConstraintF>,
82 {
83 let mut result_value = None;
84
85 let result_var = cs.alloc(
86 || "and result",
87 || {
88 if a.value.get()? & b.value.get()? {
89 result_value = Some(true);
90
91 Ok(ConstraintF::one())
92 } else {
93 result_value = Some(false);
94
95 Ok(ConstraintF::zero())
96 }
97 },
98 )?;
99
100 // Constrain (a) * (b) = (c), ensuring c is 1 iff
101 // a AND b are both 1.
102 cs.enforce(
103 || "and constraint",
104 |lc| lc + a.variable,
105 |lc| lc + b.variable,
106 |lc| lc + result_var,
107 );
108
109 Ok(AllocatedBit {
110 variable: result_var,
111 value: result_value,
112 })
113 }
114
115 /// Performs an OR operation over the two operands, returning
116 /// an `AllocatedBit`.
117 pub fn or<ConstraintF, CS>(mut cs: CS, a: &Self, b: &Self) -> Result<Self, SynthesisError>
118 where
119 ConstraintF: Field,
120 CS: ConstraintSystem<ConstraintF>,
121 {
122 let mut result_value = None;
123
124 let result_var = cs.alloc(
125 || "or result",
126 || {
127 if a.value.get()? | b.value.get()? {
128 result_value = Some(true);
129 Ok(ConstraintF::one())
130 } else {
131 result_value = Some(false);
132 Ok(ConstraintF::zero())
133 }
134 },
135 )?;
136
137 // Constrain (1 - a) * (1 - b) = (c), ensuring c is 1 iff
138 // a and b are both false, and otherwise c is 0.
139 cs.enforce(
140 || "nor constraint",
141 |lc| lc + CS::one() - a.variable,
142 |lc| lc + CS::one() - b.variable,
143 |lc| lc + CS::one() - result_var,
144 );
145
146 Ok(AllocatedBit {
147 variable: result_var,
148 value: result_value,
149 })
150 }
151
152 /// Calculates `a AND (NOT b)`.
153 pub fn and_not<ConstraintF, CS>(mut cs: CS, a: &Self, b: &Self) -> Result<Self, SynthesisError>
154 where
155 ConstraintF: Field,
156 CS: ConstraintSystem<ConstraintF>,
157 {
158 let mut result_value = None;
159
160 let result_var = cs.alloc(
161 || "and not result",
162 || {
163 if a.value.get()? & !b.value.get()? {
164 result_value = Some(true);
165
166 Ok(ConstraintF::one())
167 } else {
168 result_value = Some(false);
169
170 Ok(ConstraintF::zero())
171 }
172 },
173 )?;
174
175 // Constrain (a) * (1 - b) = (c), ensuring c is 1 iff
176 // a is true and b is false, and otherwise c is 0.
177 cs.enforce(
178 || "and not constraint",
179 |lc| lc + a.variable,
180 |lc| lc + CS::one() - b.variable,
181 |lc| lc + result_var,
182 );
183
184 Ok(AllocatedBit {
185 variable: result_var,
186 value: result_value,
187 })
188 }
189
190 /// Calculates `(NOT a) AND (NOT b)`.
191 pub fn nor<ConstraintF, CS>(mut cs: CS, a: &Self, b: &Self) -> Result<Self, SynthesisError>
192 where
193 ConstraintF: Field,
194 CS: ConstraintSystem<ConstraintF>,
195 {
196 let mut result_value = None;
197
198 let result_var = cs.alloc(
199 || "nor result",
200 || {
201 if !a.value.get()? & !b.value.get()? {
202 result_value = Some(true);
203
204 Ok(ConstraintF::one())
205 } else {
206 result_value = Some(false);
207
208 Ok(ConstraintF::zero())
209 }
210 },
211 )?;
212
213 // Constrain (1 - a) * (1 - b) = (c), ensuring c is 1 iff
214 // a and b are both false, and otherwise c is 0.
215 cs.enforce(
216 || "nor constraint",
217 |lc| lc + CS::one() - a.variable,
218 |lc| lc + CS::one() - b.variable,
219 |lc| lc + result_var,
220 );
221
222 Ok(AllocatedBit {
223 variable: result_var,
224 value: result_value,
225 })
226 }
227}
228
229impl PartialEq for AllocatedBit {
230 fn eq(&self, other: &Self) -> bool {
231 self.value.is_some() && other.value.is_some() && self.value == other.value
232 }
233}
234
235impl Eq for AllocatedBit {}
236
237impl<ConstraintF: Field> AllocGadget<bool, ConstraintF> for AllocatedBit {
238 fn alloc_constant<T, CS: ConstraintSystem<ConstraintF>>(
239 _cs: CS,
240 _t: T,
241 ) -> Result<Self, SynthesisError>
242 where
243 T: Borrow<bool>,
244 {
245 unimplemented!();
246 }
247
248 fn alloc<F, T, CS: ConstraintSystem<ConstraintF>>(
249 mut cs: CS,
250 value_gen: F,
251 ) -> Result<Self, SynthesisError>
252 where
253 F: FnOnce() -> Result<T, SynthesisError>,
254 T: Borrow<bool>,
255 {
256 let mut value = None;
257 let var = cs.alloc(
258 || "boolean",
259 || {
260 value = Some(*value_gen()?.borrow());
261 if value.get()? {
262 Ok(ConstraintF::one())
263 } else {
264 Ok(ConstraintF::zero())
265 }
266 },
267 )?;
268
269 // Constrain: (1 - a) * a = 0
270 // This constrains a to be either 0 or 1.
271 cs.enforce(
272 || "boolean constraint",
273 |lc| lc + CS::one() - var,
274 |lc| lc + var,
275 |lc| lc,
276 );
277
278 Ok(AllocatedBit {
279 variable: var,
280 value,
281 })
282 }
283
284 fn alloc_input<F, T, CS: ConstraintSystem<ConstraintF>>(
285 mut cs: CS,
286 value_gen: F,
287 ) -> Result<Self, SynthesisError>
288 where
289 F: FnOnce() -> Result<T, SynthesisError>,
290 T: Borrow<bool>,
291 {
292 let mut value = None;
293 let var = cs.alloc_input(
294 || "boolean",
295 || {
296 value = Some(*value_gen()?.borrow());
297 if value.get()? {
298 Ok(ConstraintF::one())
299 } else {
300 Ok(ConstraintF::zero())
301 }
302 },
303 )?;
304
305 // Constrain: (1 - a) * a = 0
306 // This constrains a to be either 0 or 1.
307 cs.enforce(
308 || "boolean constraint",
309 |lc| lc + CS::one() - var,
310 |lc| lc + var,
311 |lc| lc,
312 );
313
314 Ok(AllocatedBit {
315 variable: var,
316 value,
317 })
318 }
319}
320
321impl<ConstraintF: PrimeField> CondSelectGadget<ConstraintF> for AllocatedBit {
322 fn conditionally_select<CS: ConstraintSystem<ConstraintF>>(
323 cs: CS,
324 cond: &Boolean,
325 true_value: &Self,
326 false_value: &Self,
327 ) -> Result<Self, SynthesisError> {
328 cond_select_helper(
329 cs,
330 cond,
331 (true_value.value, true_value.variable),
332 (false_value.value, false_value.variable),
333 )
334 }
335
336 fn cost() -> usize {
337 1
338 }
339}
340
341fn cond_select_helper<F: PrimeField, CS: ConstraintSystem<F>>(
342 mut cs: CS,
343 cond: &Boolean,
344 first: (Option<bool>, impl Into<ConstraintVar<F>>),
345 second: (Option<bool>, impl Into<ConstraintVar<F>>),
346) -> Result<AllocatedBit, SynthesisError> {
347 let mut result_val = None;
348 let result_var = cs.alloc(
349 || "cond_select_result",
350 || {
351 result_val = cond
352 .get_value()
353 .and_then(|c| if c { first.0 } else { second.0 });
354 result_val.get().map(|v| F::from(v as u8))
355 },
356 )?;
357
358 let first_var = first.1.into();
359 let second_var = second.1.into();
360
361 // a = self; b = other; c = cond;
362 //
363 // r = c * a + (1 - c) * b
364 // r = b + c * (a - b)
365 // c * (a - b) = r - b
366 let one = CS::one();
367 cs.enforce(
368 || "conditionally_select",
369 |_| cond.lc(one, F::one()),
370 |lc| (&first_var - &second_var) + lc,
371 |lc| ConstraintVar::from(result_var) - &second_var + lc,
372 );
373
374 Ok(AllocatedBit {
375 value: result_val,
376 variable: result_var,
377 })
378}
379
380/// This is a boolean value which may be either a constant or
381/// an interpretation of an `AllocatedBit`.
382#[derive(Copy, Clone, Debug)]
383pub enum Boolean {
384 /// Existential view of the boolean variable
385 Is(AllocatedBit),
386 /// Negated view of the boolean variable
387 Not(AllocatedBit),
388 /// Constant (not an allocated variable)
389 Constant(bool),
390}
391
392impl Boolean {
393 pub fn get_value(&self) -> Option<bool> {
394 match *self {
395 Boolean::Constant(c) => Some(c),
396 Boolean::Is(ref v) => v.get_value(),
397 Boolean::Not(ref v) => v.get_value().map(|b| !b),
398 }
399 }
400
401 pub fn lc<ConstraintF: Field>(
402 &self,
403 one: Variable,
404 coeff: ConstraintF,
405 ) -> LinearCombination<ConstraintF> {
406 match *self {
407 Boolean::Constant(c) => {
408 if c {
409 (coeff, one).into()
410 } else {
411 LinearCombination::<ConstraintF>::zero()
412 }
413 }
414 Boolean::Is(ref v) => (coeff, v.get_variable()).into(),
415 Boolean::Not(ref v) => {
416 LinearCombination::<ConstraintF>::zero() + (coeff, one) - (coeff, v.get_variable())
417 }
418 }
419 }
420
421 /// Construct a boolean vector from a vector of u8
422 pub fn constant_u8_vec<ConstraintF: Field, CS: ConstraintSystem<ConstraintF>>(
423 cs: &mut CS,
424 values: &[u8],
425 ) -> Vec<Self> {
426 let mut input_bits = vec![];
427 for (byte_i, input_byte) in values.iter().enumerate() {
428 for bit_i in (0..8).rev() {
429 let cs = cs.ns(|| format!("input_bit_gadget {} {}", byte_i, bit_i));
430 input_bits.push(
431 AllocatedBit::alloc(cs, || Ok((input_byte >> bit_i) & 1u8 == 1u8))
432 .unwrap()
433 .into(),
434 );
435 }
436 }
437 input_bits
438 }
439
440 /// Construct a boolean from a known constant
441 pub fn constant(b: bool) -> Self {
442 Boolean::Constant(b)
443 }
444
445 /// Return a negated interpretation of this boolean.
446 pub fn not(&self) -> Self {
447 match *self {
448 Boolean::Constant(c) => Boolean::Constant(!c),
449 Boolean::Is(ref v) => Boolean::Not(*v),
450 Boolean::Not(ref v) => Boolean::Is(*v),
451 }
452 }
453
454 /// Perform XOR over two boolean operands
455 pub fn xor<'a, ConstraintF, CS>(
456 cs: CS,
457 a: &'a Self,
458 b: &'a Self,
459 ) -> Result<Self, SynthesisError>
460 where
461 ConstraintF: Field,
462 CS: ConstraintSystem<ConstraintF>,
463 {
464 match (a, b) {
465 (&Boolean::Constant(false), x) | (x, &Boolean::Constant(false)) => Ok(*x),
466 (&Boolean::Constant(true), x) | (x, &Boolean::Constant(true)) => Ok(x.not()),
467 // a XOR (NOT b) = NOT(a XOR b)
468 (is @ &Boolean::Is(_), not @ &Boolean::Not(_))
469 | (not @ &Boolean::Not(_), is @ &Boolean::Is(_)) => {
470 Ok(Boolean::xor(cs, is, ¬.not())?.not())
471 }
472 // a XOR b = (NOT a) XOR (NOT b)
473 (&Boolean::Is(ref a), &Boolean::Is(ref b))
474 | (&Boolean::Not(ref a), &Boolean::Not(ref b)) => {
475 Ok(Boolean::Is(AllocatedBit::xor(cs, a, b)?))
476 }
477 }
478 }
479
480 /// Perform OR over two boolean operands
481 pub fn or<'a, ConstraintF, CS>(cs: CS, a: &'a Self, b: &'a Self) -> Result<Self, SynthesisError>
482 where
483 ConstraintF: Field,
484 CS: ConstraintSystem<ConstraintF>,
485 {
486 match (a, b) {
487 (&Boolean::Constant(false), x) | (x, &Boolean::Constant(false)) => Ok(*x),
488 (&Boolean::Constant(true), _) | (_, &Boolean::Constant(true)) => {
489 Ok(Boolean::Constant(true))
490 }
491 // a OR b = NOT ((NOT a) AND b)
492 (a @ &Boolean::Is(_), b @ &Boolean::Not(_))
493 | (b @ &Boolean::Not(_), a @ &Boolean::Is(_))
494 | (b @ &Boolean::Not(_), a @ &Boolean::Not(_)) => {
495 Ok(Boolean::and(cs, &a.not(), &b.not())?.not())
496 }
497 (&Boolean::Is(ref a), &Boolean::Is(ref b)) => {
498 AllocatedBit::or(cs, a, b).map(Boolean::from)
499 }
500 }
501 }
502
503 /// Perform AND over two boolean operands
504 pub fn and<'a, ConstraintF, CS>(
505 cs: CS,
506 a: &'a Self,
507 b: &'a Self,
508 ) -> Result<Self, SynthesisError>
509 where
510 ConstraintF: Field,
511 CS: ConstraintSystem<ConstraintF>,
512 {
513 match (a, b) {
514 // false AND x is always false
515 (&Boolean::Constant(false), _) | (_, &Boolean::Constant(false)) => {
516 Ok(Boolean::Constant(false))
517 }
518 // true AND x is always x
519 (&Boolean::Constant(true), x) | (x, &Boolean::Constant(true)) => Ok(*x),
520 // a AND (NOT b)
521 (&Boolean::Is(ref is), &Boolean::Not(ref not))
522 | (&Boolean::Not(ref not), &Boolean::Is(ref is)) => {
523 Ok(Boolean::Is(AllocatedBit::and_not(cs, is, not)?))
524 }
525 // (NOT a) AND (NOT b) = a NOR b
526 (&Boolean::Not(ref a), &Boolean::Not(ref b)) => {
527 Ok(Boolean::Is(AllocatedBit::nor(cs, a, b)?))
528 }
529 // a AND b
530 (&Boolean::Is(ref a), &Boolean::Is(ref b)) => {
531 Ok(Boolean::Is(AllocatedBit::and(cs, a, b)?))
532 }
533 }
534 }
535
536 pub fn kary_and<ConstraintF, CS>(mut cs: CS, bits: &[Self]) -> Result<Self, SynthesisError>
537 where
538 ConstraintF: Field,
539 CS: ConstraintSystem<ConstraintF>,
540 {
541 assert!(!bits.is_empty());
542 let mut bits = bits.iter();
543
544 let mut cur: Self = *bits.next().unwrap();
545 for (i, next) in bits.enumerate() {
546 cur = Boolean::and(cs.ns(|| format!("AND {}", i)), &cur, next)?;
547 }
548
549 Ok(cur)
550 }
551
552 pub fn kary_or<ConstraintF, CS>(mut cs: CS, bits: &[Self]) -> Result<Self, SynthesisError>
553 where
554 ConstraintF: Field,
555 CS: ConstraintSystem<ConstraintF>,
556 {
557 assert!(!bits.is_empty());
558 let mut bits = bits.iter();
559
560 let mut cur: Self = *bits.next().unwrap();
561 for (i, next) in bits.enumerate() {
562 cur = Boolean::or(cs.ns(|| format!("OR {}", i)), &cur, next)?;
563 }
564
565 Ok(cur)
566 }
567
568 /// Asserts that at least one operand is false.
569 pub fn enforce_nand<ConstraintF, CS>(mut cs: CS, bits: &[Self]) -> Result<(), SynthesisError>
570 where
571 ConstraintF: Field,
572 CS: ConstraintSystem<ConstraintF>,
573 {
574 let res = Self::kary_and(&mut cs, bits)?;
575
576 match res {
577 Boolean::Constant(false) => Ok(()),
578 Boolean::Constant(true) => Err(SynthesisError::AssignmentMissing),
579 Boolean::Is(ref res) => {
580 cs.enforce(
581 || "enforce nand",
582 |lc| lc,
583 |lc| lc,
584 |lc| lc + res.get_variable(),
585 );
586
587 Ok(())
588 }
589 Boolean::Not(ref res) => {
590 cs.enforce(
591 || "enforce nand",
592 |lc| lc,
593 |lc| lc,
594 |lc| lc + CS::one() - res.get_variable(),
595 );
596
597 Ok(())
598 }
599 }
600 }
601
602 /// Asserts that this bit_gadget representation is "in
603 /// the field" when interpreted in big endian.
604 pub fn enforce_in_field<ConstraintF, CS, F: PrimeField>(
605 cs: CS,
606 bits: &[Self],
607 ) -> Result<(), SynthesisError>
608 where
609 ConstraintF: Field,
610 CS: ConstraintSystem<ConstraintF>,
611 {
612 // b = char() - 1
613 let mut b = F::characteristic().to_vec();
614 assert_eq!(b[0] % 2, 1);
615 b[0] -= 1;
616 let run = Self::enforce_smaller_or_equal_than::<_, _, F, _>(cs, bits, b)?;
617
618 // We should always end in a "run" of zeros, because
619 // the characteristic is an odd prime. So, this should
620 // be empty.
621 assert!(run.is_empty());
622
623 Ok(())
624 }
625
626 /// Asserts that this bit_gadget representation is smaller
627 /// or equal than the provided element
628 pub fn enforce_smaller_or_equal_than<ConstraintF, CS, F: PrimeField, E: AsRef<[u64]>>(
629 mut cs: CS,
630 bits: &[Self],
631 element: E,
632 ) -> Result<Vec<Boolean>, SynthesisError>
633 where
634 ConstraintF: Field,
635 CS: ConstraintSystem<ConstraintF>,
636 {
637 let mut bits_iter = bits.iter();
638 let b: &[u64] = element.as_ref();
639
640 // Runs of ones in r
641 let mut last_run = Boolean::constant(true);
642 let mut current_run = vec![];
643
644 let mut found_one = false;
645 let mut run_i = 0;
646 let mut nand_i = 0;
647
648 let char_num_bits = {
649 let mut leading_zeros = 0;
650 let mut total_bits = 0;
651 let mut found_one = false;
652 for b in BitIterator::new(b.clone()) {
653 total_bits += 1;
654 if !b && !found_one {
655 leading_zeros += 1
656 }
657 if b {
658 found_one = true;
659 }
660 }
661
662 total_bits - leading_zeros
663 };
664
665 if bits.len() > char_num_bits {
666 let num_extra_bits = bits.len() - char_num_bits;
667 let mut or_result = Boolean::constant(false);
668 for (i, should_be_zero) in bits[0..num_extra_bits].iter().enumerate() {
669 or_result = Boolean::or(
670 &mut cs.ns(|| format!("Check {}-th or", i)),
671 &or_result,
672 should_be_zero,
673 )?;
674 let _ = bits_iter.next().unwrap();
675 }
676 or_result.enforce_equal(
677 &mut cs.ns(|| "Check that or of extra bits is zero"),
678 &Boolean::constant(false),
679 )?;
680 }
681
682 for b in BitIterator::new(b) {
683 // Skip over unset bits at the beginning
684 found_one |= b;
685 if !found_one {
686 continue;
687 }
688
689 let a = bits_iter.next().unwrap();
690
691 if b {
692 // This is part of a run of ones.
693 current_run.push(a.clone());
694 } else {
695 if !current_run.is_empty() {
696 // This is the start of a run of zeros, but we need
697 // to k-ary AND against `last_run` first.
698
699 current_run.push(last_run);
700 last_run = Self::kary_and(cs.ns(|| format!("run {}", run_i)), ¤t_run)?;
701 run_i += 1;
702 current_run.truncate(0);
703 }
704
705 // If `last_run` is true, `a` must be false, or it would
706 // not be in the field.
707 //
708 // If `last_run` is false, `a` can be true or false.
709 //
710 // Ergo, at least one of `last_run` and `a` must be false.
711 Self::enforce_nand(cs.ns(|| format!("nand {}", nand_i)), &[last_run, *a])?;
712 nand_i += 1;
713 }
714 }
715 assert!(bits_iter.next().is_none());
716
717 Ok(current_run)
718 }
719}
720
721impl PartialEq for Boolean {
722 fn eq(&self, other: &Self) -> bool {
723 use self::Boolean::*;
724
725 match (*self, *other) {
726 (Is(a), Is(b)) | (Not(a), Not(b)) => a == b,
727 (Is(a), Not(b)) | (Not(a), Is(b)) => a != b,
728 (Is(a), Constant(b)) | (Constant(b), Is(a)) => a.value.unwrap() == b,
729 (Not(a), Constant(b)) | (Constant(b), Not(a)) => a.value.unwrap() != b,
730 (Constant(a), Constant(b)) => a == b,
731 }
732 }
733}
734
735impl Eq for Boolean {}
736
737impl From<AllocatedBit> for Boolean {
738 fn from(b: AllocatedBit) -> Boolean {
739 Boolean::Is(b)
740 }
741}
742
743impl<ConstraintF: Field> AllocGadget<bool, ConstraintF> for Boolean {
744 fn alloc_constant<T, CS: ConstraintSystem<ConstraintF>>(
745 _cs: CS,
746 t: T,
747 ) -> Result<Self, SynthesisError>
748 where
749 T: Borrow<bool>,
750 {
751 Ok(Boolean::constant(*t.borrow()))
752 }
753
754 fn alloc<F, T, CS: ConstraintSystem<ConstraintF>>(
755 cs: CS,
756 value_gen: F,
757 ) -> Result<Self, SynthesisError>
758 where
759 F: FnOnce() -> Result<T, SynthesisError>,
760 T: Borrow<bool>,
761 {
762 AllocatedBit::alloc(cs, value_gen).map(Boolean::from)
763 }
764
765 fn alloc_input<F, T, CS: ConstraintSystem<ConstraintF>>(
766 cs: CS,
767 value_gen: F,
768 ) -> Result<Self, SynthesisError>
769 where
770 F: FnOnce() -> Result<T, SynthesisError>,
771 T: Borrow<bool>,
772 {
773 AllocatedBit::alloc_input(cs, value_gen).map(Boolean::from)
774 }
775}
776
777impl<ConstraintF: Field> EqGadget<ConstraintF> for Boolean {}
778
779impl<ConstraintF: Field> ConditionalEqGadget<ConstraintF> for Boolean {
780 fn conditional_enforce_equal<CS>(
781 &self,
782 mut cs: CS,
783 other: &Self,
784 condition: &Boolean,
785 ) -> Result<(), SynthesisError>
786 where
787 CS: ConstraintSystem<ConstraintF>,
788 {
789 use self::Boolean::*;
790 let one = CS::one();
791 let difference: LinearCombination<ConstraintF> = match (self, other) {
792 // 1 - 1 = 0 - 0 = 0
793 (Constant(true), Constant(true)) | (Constant(false), Constant(false)) => return Ok(()),
794 // false != true
795 (Constant(_), Constant(_)) => return Err(SynthesisError::AssignmentMissing),
796 // 1 - a
797 (Constant(true), Is(a)) | (Is(a), Constant(true)) => {
798 LinearCombination::zero() + one - a.get_variable()
799 }
800 // a - 0 = a
801 (Constant(false), Is(a)) | (Is(a), Constant(false)) => {
802 LinearCombination::zero() + a.get_variable()
803 }
804 // 1 - !a = 1 - (1 - a) = a
805 (Constant(true), Not(a)) | (Not(a), Constant(true)) => {
806 LinearCombination::zero() + a.get_variable()
807 }
808 // !a - 0 = !a = 1 - a
809 (Constant(false), Not(a)) | (Not(a), Constant(false)) => {
810 LinearCombination::zero() + one - a.get_variable()
811 }
812 // b - a,
813 (Is(a), Is(b)) => LinearCombination::zero() + b.get_variable() - a.get_variable(),
814 // !b - a = (1 - b) - a
815 (Is(a), Not(b)) | (Not(b), Is(a)) => {
816 LinearCombination::zero() + one - b.get_variable() - a.get_variable()
817 }
818 // !b - !a = (1 - b) - (1 - a) = a - b,
819 (Not(a), Not(b)) => LinearCombination::zero() + a.get_variable() - b.get_variable(),
820 };
821
822 if let Constant(false) = condition {
823 Ok(())
824 } else {
825 cs.enforce(
826 || "conditional_equals",
827 |lc| difference + &lc,
828 |lc| condition.lc(one, ConstraintF::one()) + &lc,
829 |lc| lc,
830 );
831 Ok(())
832 }
833 }
834
835 fn cost() -> usize {
836 1
837 }
838}
839
840impl<ConstraintF: Field> ToBytesGadget<ConstraintF> for Boolean {
841 /// Outputs `1u8` if `self` is true, and `0u8` otherwise.
842 fn to_bytes<CS: ConstraintSystem<ConstraintF>>(
843 &self,
844 _cs: CS,
845 ) -> Result<Vec<UInt8>, SynthesisError> {
846 let mut bits = vec![Boolean::constant(false); 7];
847 bits.push(*self);
848 bits.reverse();
849 let value = self.get_value().map(|val| val as u8);
850 let byte = UInt8 { bits, value };
851 Ok(vec![byte])
852 }
853}
854
855impl<ConstraintF: PrimeField> ToConstraintFieldGadget<ConstraintF> for Boolean {
856 fn to_constraint_field<CS: ConstraintSystem<ConstraintF>>(
857 &self,
858 mut cs: CS,
859 ) -> Result<Vec<FpGadget<ConstraintF>>, SynthesisError> {
860 let gadget = match self {
861 Boolean::Constant(cond) => {
862 if *cond {
863 FpGadget::one(&mut cs.ns(|| "one"))?
864 } else {
865 FpGadget::zero(&mut cs.ns(|| "zero"))?
866 }
867 }
868 Boolean::Is(allocated_bit) => {
869 let value = match self.get_value() {
870 None => None,
871 Some(bool) => {
872 if bool {
873 Some(ConstraintF::one())
874 } else {
875 Some(ConstraintF::zero())
876 }
877 }
878 };
879
880 FpGadget::<ConstraintF> {
881 value,
882 variable: ConstraintVar::Var(allocated_bit.get_variable()),
883 }
884 }
885 Boolean::Not(allocated_bit) => {
886 let value = match self.get_value() {
887 None => None,
888 Some(bool) => {
889 if bool {
890 Some(ConstraintF::zero())
891 } else {
892 Some(ConstraintF::one())
893 }
894 }
895 };
896
897 let mut lc = LinearCombination::<ConstraintF>::zero();
898 lc += (ConstraintF::one(), CS::one());
899 lc += (-ConstraintF::one(), allocated_bit.get_variable());
900
901 FpGadget::<ConstraintF> {
902 value,
903 variable: ConstraintVar::LC(lc),
904 }
905 }
906 };
907
908 Ok(vec![gadget])
909 }
910}
911
912impl<ConstraintF: PrimeField> CondSelectGadget<ConstraintF> for Boolean {
913 fn conditionally_select<CS>(
914 mut cs: CS,
915 cond: &Self,
916 true_value: &Self,
917 false_value: &Self,
918 ) -> Result<Self, SynthesisError>
919 where
920 CS: ConstraintSystem<ConstraintF>,
921 {
922 match cond {
923 Boolean::Constant(true) => Ok(true_value.clone()),
924 Boolean::Constant(false) => Ok(false_value.clone()),
925 cond @ Boolean::Not(_) => {
926 Self::conditionally_select(cs, &cond.not(), false_value, true_value)
927 }
928 cond @ Boolean::Is(_) => match (true_value, false_value) {
929 (x, &Boolean::Constant(false)) => Boolean::and(cs.ns(|| "and"), cond, x).into(),
930 (&Boolean::Constant(false), x) => Boolean::and(cs.ns(|| "and"), &cond.not(), x),
931 (&Boolean::Constant(true), x) => Boolean::or(cs.ns(|| "or"), cond, x).into(),
932 (x, &Boolean::Constant(true)) => Boolean::or(cs.ns(|| "or"), &cond.not(), x),
933 (a @ Boolean::Is(_), b @ Boolean::Is(_))
934 | (a @ Boolean::Not(_), b @ Boolean::Not(_))
935 | (a @ Boolean::Is(_), b @ Boolean::Not(_))
936 | (a @ Boolean::Not(_), b @ Boolean::Is(_)) => {
937 let a_lc = a.lc(CS::one(), ConstraintF::one());
938 let b_lc = b.lc(CS::one(), ConstraintF::one());
939 Ok(
940 cond_select_helper(cs, cond, (a.get_value(), a_lc), (b.get_value(), b_lc))?
941 .into(),
942 )
943 }
944 },
945 }
946 }
947
948 fn cost() -> usize {
949 1
950 }
951}
952
953#[cfg(test)]
954mod test {
955 use super::{AllocatedBit, Boolean};
956 use crate::{prelude::*, test_constraint_system::TestConstraintSystem};
957 use algebra::{bls12_381::Fr, BitIterator, Field, One, PrimeField, UniformRand, Zero};
958 use core::str::FromStr;
959 use r1cs_core::ConstraintSystem;
960 use rand::SeedableRng;
961 use rand_xorshift::XorShiftRng;
962
963 #[test]
964 fn test_boolean_to_byte() {
965 for val in [true, false].iter() {
966 let mut cs = TestConstraintSystem::<Fr>::new();
967 let a: Boolean = AllocatedBit::alloc(&mut cs, || Ok(*val)).unwrap().into();
968 let bytes = a.to_bytes(&mut cs.ns(|| "ToBytes")).unwrap();
969 assert_eq!(bytes.len(), 1);
970 let byte = &bytes[0];
971 assert_eq!(byte.value.unwrap(), *val as u8);
972
973 for (i, bit_gadget) in byte.bits.iter().enumerate() {
974 assert_eq!(
975 bit_gadget.get_value().unwrap(),
976 (byte.value.unwrap() >> i) & 1 == 1
977 );
978 }
979 }
980 }
981
982 #[test]
983 fn test_allocated_bit() {
984 let mut cs = TestConstraintSystem::<Fr>::new();
985
986 AllocatedBit::alloc(&mut cs, || Ok(true)).unwrap();
987 assert!(cs.get("boolean") == Fr::one());
988 assert!(cs.is_satisfied());
989 cs.set("boolean", Fr::zero());
990 assert!(cs.is_satisfied());
991 cs.set("boolean", Fr::from_str("2").unwrap());
992 assert!(!cs.is_satisfied());
993 assert!(cs.which_is_unsatisfied() == Some("boolean constraint"));
994 }
995
996 #[test]
997 fn test_xor() {
998 for a_val in [false, true].iter() {
999 for b_val in [false, true].iter() {
1000 let mut cs = TestConstraintSystem::<Fr>::new();
1001 let a = AllocatedBit::alloc(cs.ns(|| "a"), || Ok(*a_val)).unwrap();
1002 let b = AllocatedBit::alloc(cs.ns(|| "b"), || Ok(*b_val)).unwrap();
1003 let c = AllocatedBit::xor(&mut cs, &a, &b).unwrap();
1004 assert_eq!(c.value.unwrap(), *a_val ^ *b_val);
1005
1006 assert!(cs.is_satisfied());
1007 }
1008 }
1009 }
1010
1011 #[test]
1012 fn test_or() {
1013 for a_val in [false, true].iter() {
1014 for b_val in [false, true].iter() {
1015 let mut cs = TestConstraintSystem::<Fr>::new();
1016 let a = AllocatedBit::alloc(cs.ns(|| "a"), || Ok(*a_val)).unwrap();
1017 let b = AllocatedBit::alloc(cs.ns(|| "b"), || Ok(*b_val)).unwrap();
1018 let c = AllocatedBit::or(&mut cs, &a, &b).unwrap();
1019 assert_eq!(c.value.unwrap(), *a_val | *b_val);
1020
1021 assert!(cs.is_satisfied());
1022 assert!(cs.get("a/boolean") == if *a_val { Fr::one() } else { Fr::zero() });
1023 assert!(cs.get("b/boolean") == if *b_val { Fr::one() } else { Fr::zero() });
1024 }
1025 }
1026 }
1027
1028 #[test]
1029 fn test_and() {
1030 for a_val in [false, true].iter() {
1031 for b_val in [false, true].iter() {
1032 let mut cs = TestConstraintSystem::<Fr>::new();
1033 let a = AllocatedBit::alloc(cs.ns(|| "a"), || Ok(*a_val)).unwrap();
1034 let b = AllocatedBit::alloc(cs.ns(|| "b"), || Ok(*b_val)).unwrap();
1035 let c = AllocatedBit::and(&mut cs, &a, &b).unwrap();
1036 assert_eq!(c.value.unwrap(), *a_val & *b_val);
1037
1038 assert!(cs.is_satisfied());
1039 assert!(cs.get("a/boolean") == if *a_val { Fr::one() } else { Fr::zero() });
1040 assert!(cs.get("b/boolean") == if *b_val { Fr::one() } else { Fr::zero() });
1041 assert!(
1042 cs.get("and result")
1043 == if *a_val & *b_val {
1044 Fr::one()
1045 } else {
1046 Fr::zero()
1047 }
1048 );
1049
1050 // Invert the result and check if the constraint system is still satisfied
1051 cs.set(
1052 "and result",
1053 if *a_val & *b_val {
1054 Fr::zero()
1055 } else {
1056 Fr::one()
1057 },
1058 );
1059 assert!(!cs.is_satisfied());
1060 }
1061 }
1062 }
1063
1064 #[test]
1065 fn test_and_not() {
1066 for a_val in [false, true].iter() {
1067 for b_val in [false, true].iter() {
1068 let mut cs = TestConstraintSystem::<Fr>::new();
1069 let a = AllocatedBit::alloc(cs.ns(|| "a"), || Ok(*a_val)).unwrap();
1070 let b = AllocatedBit::alloc(cs.ns(|| "b"), || Ok(*b_val)).unwrap();
1071 let c = AllocatedBit::and_not(&mut cs, &a, &b).unwrap();
1072 assert_eq!(c.value.unwrap(), *a_val & !*b_val);
1073
1074 assert!(cs.is_satisfied());
1075 assert!(cs.get("a/boolean") == if *a_val { Fr::one() } else { Fr::zero() });
1076 assert!(cs.get("b/boolean") == if *b_val { Fr::one() } else { Fr::zero() });
1077 assert!(
1078 cs.get("and not result")
1079 == if *a_val & !*b_val {
1080 Fr::one()
1081 } else {
1082 Fr::zero()
1083 }
1084 );
1085
1086 // Invert the result and check if the constraint system is still satisfied
1087 cs.set(
1088 "and not result",
1089 if *a_val & !*b_val {
1090 Fr::zero()
1091 } else {
1092 Fr::one()
1093 },
1094 );
1095 assert!(!cs.is_satisfied());
1096 }
1097 }
1098 }
1099
1100 #[test]
1101 fn test_nor() {
1102 for a_val in [false, true].iter() {
1103 for b_val in [false, true].iter() {
1104 let mut cs = TestConstraintSystem::<Fr>::new();
1105 let a = AllocatedBit::alloc(cs.ns(|| "a"), || Ok(*a_val)).unwrap();
1106 let b = AllocatedBit::alloc(cs.ns(|| "b"), || Ok(*b_val)).unwrap();
1107 let c = AllocatedBit::nor(&mut cs, &a, &b).unwrap();
1108 assert_eq!(c.value.unwrap(), !*a_val & !*b_val);
1109
1110 assert!(cs.is_satisfied());
1111 assert!(cs.get("a/boolean") == if *a_val { Fr::one() } else { Fr::zero() });
1112 assert!(cs.get("b/boolean") == if *b_val { Fr::one() } else { Fr::zero() });
1113 assert!(
1114 cs.get("nor result")
1115 == if !*a_val & !*b_val {
1116 Fr::one()
1117 } else {
1118 Fr::zero()
1119 }
1120 );
1121
1122 // Invert the result and check if the constraint system is still satisfied
1123 cs.set(
1124 "nor result",
1125 if !*a_val & !*b_val {
1126 Fr::zero()
1127 } else {
1128 Fr::one()
1129 },
1130 );
1131 assert!(!cs.is_satisfied());
1132 }
1133 }
1134 }
1135
1136 #[test]
1137 fn test_enforce_equal() {
1138 for a_bool in [false, true].iter().cloned() {
1139 for b_bool in [false, true].iter().cloned() {
1140 for a_neg in [false, true].iter().cloned() {
1141 for b_neg in [false, true].iter().cloned() {
1142 let mut cs = TestConstraintSystem::<Fr>::new();
1143
1144 let mut a: Boolean = AllocatedBit::alloc(cs.ns(|| "a"), || Ok(a_bool))
1145 .unwrap()
1146 .into();
1147 let mut b: Boolean = AllocatedBit::alloc(cs.ns(|| "b"), || Ok(b_bool))
1148 .unwrap()
1149 .into();
1150
1151 if a_neg {
1152 a = a.not();
1153 }
1154 if b_neg {
1155 b = b.not();
1156 }
1157
1158 a.enforce_equal(&mut cs, &b).unwrap();
1159
1160 assert_eq!(cs.is_satisfied(), (a_bool ^ a_neg) == (b_bool ^ b_neg));
1161 }
1162 }
1163 }
1164 }
1165 }
1166
1167 #[test]
1168 fn test_conditional_enforce_equal() {
1169 for a_bool in [false, true].iter().cloned() {
1170 for b_bool in [false, true].iter().cloned() {
1171 for a_neg in [false, true].iter().cloned() {
1172 for b_neg in [false, true].iter().cloned() {
1173 let mut cs = TestConstraintSystem::<Fr>::new();
1174
1175 // First test if constraint system is satisfied
1176 // when we do want to enforce the condition.
1177 let mut a: Boolean = AllocatedBit::alloc(cs.ns(|| "a"), || Ok(a_bool))
1178 .unwrap()
1179 .into();
1180 let mut b: Boolean = AllocatedBit::alloc(cs.ns(|| "b"), || Ok(b_bool))
1181 .unwrap()
1182 .into();
1183
1184 if a_neg {
1185 a = a.not();
1186 }
1187 if b_neg {
1188 b = b.not();
1189 }
1190
1191 a.conditional_enforce_equal(&mut cs, &b, &Boolean::constant(true))
1192 .unwrap();
1193
1194 assert_eq!(cs.is_satisfied(), (a_bool ^ a_neg) == (b_bool ^ b_neg));
1195
1196 // Now test if constraint system is satisfied even
1197 // when we don't want to enforce the condition.
1198 let mut cs = TestConstraintSystem::<Fr>::new();
1199
1200 let mut a: Boolean = AllocatedBit::alloc(cs.ns(|| "a"), || Ok(a_bool))
1201 .unwrap()
1202 .into();
1203 let mut b: Boolean = AllocatedBit::alloc(cs.ns(|| "b"), || Ok(b_bool))
1204 .unwrap()
1205 .into();
1206
1207 if a_neg {
1208 a = a.not();
1209 }
1210 if b_neg {
1211 b = b.not();
1212 }
1213
1214 let false_cond = AllocatedBit::alloc(cs.ns(|| "cond"), || Ok(false))
1215 .unwrap()
1216 .into();
1217 a.conditional_enforce_equal(&mut cs, &b, &false_cond)
1218 .unwrap();
1219
1220 assert!(cs.is_satisfied());
1221 }
1222 }
1223 }
1224 }
1225 }
1226
1227 #[test]
1228 fn test_boolean_negation() {
1229 let mut cs = TestConstraintSystem::<Fr>::new();
1230
1231 let mut b = Boolean::from(AllocatedBit::alloc(&mut cs, || Ok(true)).unwrap());
1232
1233 match b {
1234 Boolean::Is(_) => {}
1235 _ => panic!("unexpected value"),
1236 }
1237
1238 b = b.not();
1239
1240 match b {
1241 Boolean::Not(_) => {}
1242 _ => panic!("unexpected value"),
1243 }
1244
1245 b = b.not();
1246
1247 match b {
1248 Boolean::Is(_) => {}
1249 _ => panic!("unexpected value"),
1250 }
1251
1252 b = Boolean::constant(true);
1253
1254 match b {
1255 Boolean::Constant(true) => {}
1256 _ => panic!("unexpected value"),
1257 }
1258
1259 b = b.not();
1260
1261 match b {
1262 Boolean::Constant(false) => {}
1263 _ => panic!("unexpected value"),
1264 }
1265
1266 b = b.not();
1267
1268 match b {
1269 Boolean::Constant(true) => {}
1270 _ => panic!("unexpected value"),
1271 }
1272 }
1273
1274 #[derive(Copy, Clone, Debug)]
1275 enum OperandType {
1276 True,
1277 False,
1278 AllocatedTrue,
1279 AllocatedFalse,
1280 NegatedAllocatedTrue,
1281 NegatedAllocatedFalse,
1282 }
1283
1284 #[test]
1285 fn test_boolean_xor() {
1286 let variants = [
1287 OperandType::True,
1288 OperandType::False,
1289 OperandType::AllocatedTrue,
1290 OperandType::AllocatedFalse,
1291 OperandType::NegatedAllocatedTrue,
1292 OperandType::NegatedAllocatedFalse,
1293 ];
1294
1295 for first_operand in variants.iter().cloned() {
1296 for second_operand in variants.iter().cloned() {
1297 let mut cs = TestConstraintSystem::<Fr>::new();
1298
1299 let a;
1300 let b;
1301
1302 {
1303 let mut dyn_construct = |operand, name| {
1304 let cs = cs.ns(|| name);
1305
1306 match operand {
1307 OperandType::True => Boolean::constant(true),
1308 OperandType::False => Boolean::constant(false),
1309 OperandType::AllocatedTrue => {
1310 Boolean::from(AllocatedBit::alloc(cs, || Ok(true)).unwrap())
1311 }
1312 OperandType::AllocatedFalse => {
1313 Boolean::from(AllocatedBit::alloc(cs, || Ok(false)).unwrap())
1314 }
1315 OperandType::NegatedAllocatedTrue => {
1316 Boolean::from(AllocatedBit::alloc(cs, || Ok(true)).unwrap()).not()
1317 }
1318 OperandType::NegatedAllocatedFalse => {
1319 Boolean::from(AllocatedBit::alloc(cs, || Ok(false)).unwrap()).not()
1320 }
1321 }
1322 };
1323
1324 a = dyn_construct(first_operand, "a");
1325 b = dyn_construct(second_operand, "b");
1326 }
1327
1328 let c = Boolean::xor(&mut cs, &a, &b).unwrap();
1329
1330 assert!(cs.is_satisfied());
1331
1332 match (first_operand, second_operand, c) {
1333 (OperandType::True, OperandType::True, Boolean::Constant(false)) => {}
1334 (OperandType::True, OperandType::False, Boolean::Constant(true)) => {}
1335 (OperandType::True, OperandType::AllocatedTrue, Boolean::Not(_)) => {}
1336 (OperandType::True, OperandType::AllocatedFalse, Boolean::Not(_)) => {}
1337 (OperandType::True, OperandType::NegatedAllocatedTrue, Boolean::Is(_)) => {}
1338 (OperandType::True, OperandType::NegatedAllocatedFalse, Boolean::Is(_)) => {}
1339
1340 (OperandType::False, OperandType::True, Boolean::Constant(true)) => {}
1341 (OperandType::False, OperandType::False, Boolean::Constant(false)) => {}
1342 (OperandType::False, OperandType::AllocatedTrue, Boolean::Is(_)) => {}
1343 (OperandType::False, OperandType::AllocatedFalse, Boolean::Is(_)) => {}
1344 (OperandType::False, OperandType::NegatedAllocatedTrue, Boolean::Not(_)) => {}
1345 (OperandType::False, OperandType::NegatedAllocatedFalse, Boolean::Not(_)) => {}
1346
1347 (OperandType::AllocatedTrue, OperandType::True, Boolean::Not(_)) => {}
1348 (OperandType::AllocatedTrue, OperandType::False, Boolean::Is(_)) => {}
1349 (
1350 OperandType::AllocatedTrue,
1351 OperandType::AllocatedTrue,
1352 Boolean::Is(ref v),
1353 ) => {
1354 assert!(cs.get("xor result") == Fr::zero());
1355 assert_eq!(v.value, Some(false));
1356 }
1357 (
1358 OperandType::AllocatedTrue,
1359 OperandType::AllocatedFalse,
1360 Boolean::Is(ref v),
1361 ) => {
1362 assert!(cs.get("xor result") == Fr::one());
1363 assert_eq!(v.value, Some(true));
1364 }
1365 (
1366 OperandType::AllocatedTrue,
1367 OperandType::NegatedAllocatedTrue,
1368 Boolean::Not(ref v),
1369 ) => {
1370 assert!(cs.get("xor result") == Fr::zero());
1371 assert_eq!(v.value, Some(false));
1372 }
1373 (
1374 OperandType::AllocatedTrue,
1375 OperandType::NegatedAllocatedFalse,
1376 Boolean::Not(ref v),
1377 ) => {
1378 assert!(cs.get("xor result") == Fr::one());
1379 assert_eq!(v.value, Some(true));
1380 }
1381
1382 (OperandType::AllocatedFalse, OperandType::True, Boolean::Not(_)) => {}
1383 (OperandType::AllocatedFalse, OperandType::False, Boolean::Is(_)) => {}
1384 (
1385 OperandType::AllocatedFalse,
1386 OperandType::AllocatedTrue,
1387 Boolean::Is(ref v),
1388 ) => {
1389 assert!(cs.get("xor result") == Fr::one());
1390 assert_eq!(v.value, Some(true));
1391 }
1392 (
1393 OperandType::AllocatedFalse,
1394 OperandType::AllocatedFalse,
1395 Boolean::Is(ref v),
1396 ) => {
1397 assert!(cs.get("xor result") == Fr::zero());
1398 assert_eq!(v.value, Some(false));
1399 }
1400 (
1401 OperandType::AllocatedFalse,
1402 OperandType::NegatedAllocatedTrue,
1403 Boolean::Not(ref v),
1404 ) => {
1405 assert!(cs.get("xor result") == Fr::one());
1406 assert_eq!(v.value, Some(true));
1407 }
1408 (
1409 OperandType::AllocatedFalse,
1410 OperandType::NegatedAllocatedFalse,
1411 Boolean::Not(ref v),
1412 ) => {
1413 assert!(cs.get("xor result") == Fr::zero());
1414 assert_eq!(v.value, Some(false));
1415 }
1416
1417 (OperandType::NegatedAllocatedTrue, OperandType::True, Boolean::Is(_)) => {}
1418 (OperandType::NegatedAllocatedTrue, OperandType::False, Boolean::Not(_)) => {}
1419 (
1420 OperandType::NegatedAllocatedTrue,
1421 OperandType::AllocatedTrue,
1422 Boolean::Not(ref v),
1423 ) => {
1424 assert!(cs.get("xor result") == Fr::zero());
1425 assert_eq!(v.value, Some(false));
1426 }
1427 (
1428 OperandType::NegatedAllocatedTrue,
1429 OperandType::AllocatedFalse,
1430 Boolean::Not(ref v),
1431 ) => {
1432 assert!(cs.get("xor result") == Fr::one());
1433 assert_eq!(v.value, Some(true));
1434 }
1435 (
1436 OperandType::NegatedAllocatedTrue,
1437 OperandType::NegatedAllocatedTrue,
1438 Boolean::Is(ref v),
1439 ) => {
1440 assert!(cs.get("xor result") == Fr::zero());
1441 assert_eq!(v.value, Some(false));
1442 }
1443 (
1444 OperandType::NegatedAllocatedTrue,
1445 OperandType::NegatedAllocatedFalse,
1446 Boolean::Is(ref v),
1447 ) => {
1448 assert!(cs.get("xor result") == Fr::one());
1449 assert_eq!(v.value, Some(true));
1450 }
1451
1452 (OperandType::NegatedAllocatedFalse, OperandType::True, Boolean::Is(_)) => {}
1453 (OperandType::NegatedAllocatedFalse, OperandType::False, Boolean::Not(_)) => {}
1454 (
1455 OperandType::NegatedAllocatedFalse,
1456 OperandType::AllocatedTrue,
1457 Boolean::Not(ref v),
1458 ) => {
1459 assert!(cs.get("xor result") == Fr::one());
1460 assert_eq!(v.value, Some(true));
1461 }
1462 (
1463 OperandType::NegatedAllocatedFalse,
1464 OperandType::AllocatedFalse,
1465 Boolean::Not(ref v),
1466 ) => {
1467 assert!(cs.get("xor result") == Fr::zero());
1468 assert_eq!(v.value, Some(false));
1469 }
1470 (
1471 OperandType::NegatedAllocatedFalse,
1472 OperandType::NegatedAllocatedTrue,
1473 Boolean::Is(ref v),
1474 ) => {
1475 assert!(cs.get("xor result") == Fr::one());
1476 assert_eq!(v.value, Some(true));
1477 }
1478 (
1479 OperandType::NegatedAllocatedFalse,
1480 OperandType::NegatedAllocatedFalse,
1481 Boolean::Is(ref v),
1482 ) => {
1483 assert!(cs.get("xor result") == Fr::zero());
1484 assert_eq!(v.value, Some(false));
1485 }
1486
1487 _ => panic!("this should never be encountered"),
1488 }
1489 }
1490 }
1491 }
1492
1493 #[test]
1494 fn test_boolean_cond_select() {
1495 let variants = [
1496 OperandType::True,
1497 OperandType::False,
1498 OperandType::AllocatedTrue,
1499 OperandType::AllocatedFalse,
1500 OperandType::NegatedAllocatedTrue,
1501 OperandType::NegatedAllocatedFalse,
1502 ];
1503
1504 for condition in variants.iter().cloned() {
1505 for first_operand in variants.iter().cloned() {
1506 for second_operand in variants.iter().cloned() {
1507 let mut cs = TestConstraintSystem::<Fr>::new();
1508
1509 let cond;
1510 let a;
1511 let b;
1512
1513 {
1514 let mut dyn_construct = |operand, name| {
1515 let cs = cs.ns(|| name);
1516
1517 match operand {
1518 OperandType::True => Boolean::constant(true),
1519 OperandType::False => Boolean::constant(false),
1520 OperandType::AllocatedTrue => {
1521 Boolean::from(AllocatedBit::alloc(cs, || Ok(true)).unwrap())
1522 }
1523 OperandType::AllocatedFalse => {
1524 Boolean::from(AllocatedBit::alloc(cs, || Ok(false)).unwrap())
1525 }
1526 OperandType::NegatedAllocatedTrue => {
1527 Boolean::from(AllocatedBit::alloc(cs, || Ok(true)).unwrap())
1528 .not()
1529 }
1530 OperandType::NegatedAllocatedFalse => {
1531 Boolean::from(AllocatedBit::alloc(cs, || Ok(false)).unwrap())
1532 .not()
1533 }
1534 }
1535 };
1536
1537 cond = dyn_construct(condition, "cond");
1538 a = dyn_construct(first_operand, "a");
1539 b = dyn_construct(second_operand, "b");
1540 }
1541
1542 let before = cs.num_constraints();
1543 let c = Boolean::conditionally_select(&mut cs, &cond, &a, &b).unwrap();
1544 let after = cs.num_constraints();
1545
1546 assert!(
1547 cs.is_satisfied(),
1548 "failed with operands: cond: {:?}, a: {:?}, b: {:?}",
1549 condition,
1550 first_operand,
1551 second_operand,
1552 );
1553 assert_eq!(
1554 c.get_value(),
1555 if cond.get_value().unwrap() {
1556 a.get_value()
1557 } else {
1558 b.get_value()
1559 }
1560 );
1561 assert!(<Boolean as CondSelectGadget<Fr>>::cost() >= after - before);
1562 }
1563 }
1564 }
1565 }
1566
1567 #[test]
1568 fn test_boolean_or() {
1569 let variants = [
1570 OperandType::True,
1571 OperandType::False,
1572 OperandType::AllocatedTrue,
1573 OperandType::AllocatedFalse,
1574 OperandType::NegatedAllocatedTrue,
1575 OperandType::NegatedAllocatedFalse,
1576 ];
1577
1578 for first_operand in variants.iter().cloned() {
1579 for second_operand in variants.iter().cloned() {
1580 let mut cs = TestConstraintSystem::<Fr>::new();
1581
1582 let a;
1583 let b;
1584
1585 {
1586 let mut dyn_construct = |operand, name| {
1587 let cs = cs.ns(|| name);
1588
1589 match operand {
1590 OperandType::True => Boolean::constant(true),
1591 OperandType::False => Boolean::constant(false),
1592 OperandType::AllocatedTrue => {
1593 Boolean::from(AllocatedBit::alloc(cs, || Ok(true)).unwrap())
1594 }
1595 OperandType::AllocatedFalse => {
1596 Boolean::from(AllocatedBit::alloc(cs, || Ok(false)).unwrap())
1597 }
1598 OperandType::NegatedAllocatedTrue => {
1599 Boolean::from(AllocatedBit::alloc(cs, || Ok(true)).unwrap()).not()
1600 }
1601 OperandType::NegatedAllocatedFalse => {
1602 Boolean::from(AllocatedBit::alloc(cs, || Ok(false)).unwrap()).not()
1603 }
1604 }
1605 };
1606
1607 a = dyn_construct(first_operand, "a");
1608 b = dyn_construct(second_operand, "b");
1609 }
1610
1611 let c = Boolean::or(&mut cs, &a, &b).unwrap();
1612
1613 assert!(cs.is_satisfied());
1614
1615 match (first_operand, second_operand, c) {
1616 (OperandType::True, OperandType::True, Boolean::Constant(true)) => {}
1617 (OperandType::True, OperandType::False, Boolean::Constant(true)) => {}
1618 (OperandType::True, OperandType::AllocatedTrue, Boolean::Constant(true)) => {}
1619 (OperandType::True, OperandType::AllocatedFalse, Boolean::Constant(true)) => {}
1620 (
1621 OperandType::True,
1622 OperandType::NegatedAllocatedTrue,
1623 Boolean::Constant(true),
1624 ) => {}
1625 (
1626 OperandType::True,
1627 OperandType::NegatedAllocatedFalse,
1628 Boolean::Constant(true),
1629 ) => {}
1630
1631 (OperandType::False, OperandType::True, Boolean::Constant(true)) => {}
1632 (OperandType::False, OperandType::False, Boolean::Constant(false)) => {}
1633 (OperandType::False, OperandType::AllocatedTrue, Boolean::Is(_)) => {}
1634 (OperandType::False, OperandType::AllocatedFalse, Boolean::Is(_)) => {}
1635 (OperandType::False, OperandType::NegatedAllocatedTrue, Boolean::Not(_)) => {}
1636 (OperandType::False, OperandType::NegatedAllocatedFalse, Boolean::Not(_)) => {}
1637
1638 (OperandType::AllocatedTrue, OperandType::True, Boolean::Constant(true)) => {}
1639 (OperandType::AllocatedTrue, OperandType::False, Boolean::Is(_)) => {}
1640 (
1641 OperandType::AllocatedTrue,
1642 OperandType::AllocatedTrue,
1643 Boolean::Is(ref v),
1644 ) => {
1645 assert_eq!(v.value, Some(true));
1646 }
1647 (
1648 OperandType::AllocatedTrue,
1649 OperandType::AllocatedFalse,
1650 Boolean::Is(ref v),
1651 ) => {
1652 assert_eq!(v.value, Some(true));
1653 }
1654 (
1655 OperandType::AllocatedTrue,
1656 OperandType::NegatedAllocatedTrue,
1657 Boolean::Not(ref v),
1658 ) => {
1659 assert_eq!(v.value, Some(false));
1660 }
1661 (
1662 OperandType::AllocatedTrue,
1663 OperandType::NegatedAllocatedFalse,
1664 Boolean::Not(ref v),
1665 ) => {
1666 assert_eq!(v.value, Some(false));
1667 }
1668
1669 (OperandType::AllocatedFalse, OperandType::True, Boolean::Constant(true)) => {}
1670 (OperandType::AllocatedFalse, OperandType::False, Boolean::Is(_)) => {}
1671 (
1672 OperandType::AllocatedFalse,
1673 OperandType::AllocatedTrue,
1674 Boolean::Is(ref v),
1675 ) => {
1676 assert_eq!(v.value, Some(true));
1677 }
1678 (
1679 OperandType::AllocatedFalse,
1680 OperandType::AllocatedFalse,
1681 Boolean::Is(ref v),
1682 ) => {
1683 assert_eq!(v.value, Some(false));
1684 }
1685 (
1686 OperandType::AllocatedFalse,
1687 OperandType::NegatedAllocatedTrue,
1688 Boolean::Not(ref v),
1689 ) => {
1690 assert_eq!(v.value, Some(true));
1691 }
1692 (
1693 OperandType::AllocatedFalse,
1694 OperandType::NegatedAllocatedFalse,
1695 Boolean::Not(ref v),
1696 ) => {
1697 assert_eq!(v.value, Some(false));
1698 }
1699
1700 (
1701 OperandType::NegatedAllocatedTrue,
1702 OperandType::True,
1703 Boolean::Constant(true),
1704 ) => {}
1705 (OperandType::NegatedAllocatedTrue, OperandType::False, Boolean::Not(_)) => {}
1706 (
1707 OperandType::NegatedAllocatedTrue,
1708 OperandType::AllocatedTrue,
1709 Boolean::Not(ref v),
1710 ) => {
1711 assert_eq!(v.value, Some(false));
1712 }
1713 (
1714 OperandType::NegatedAllocatedTrue,
1715 OperandType::AllocatedFalse,
1716 Boolean::Not(ref v),
1717 ) => {
1718 assert_eq!(v.value, Some(true));
1719 }
1720 (
1721 OperandType::NegatedAllocatedTrue,
1722 OperandType::NegatedAllocatedTrue,
1723 Boolean::Not(ref v),
1724 ) => {
1725 assert_eq!(v.value, Some(true));
1726 }
1727 (
1728 OperandType::NegatedAllocatedTrue,
1729 OperandType::NegatedAllocatedFalse,
1730 Boolean::Not(ref v),
1731 ) => {
1732 assert_eq!(v.value, Some(false));
1733 }
1734
1735 (
1736 OperandType::NegatedAllocatedFalse,
1737 OperandType::True,
1738 Boolean::Constant(true),
1739 ) => {}
1740 (OperandType::NegatedAllocatedFalse, OperandType::False, Boolean::Not(_)) => {}
1741 (
1742 OperandType::NegatedAllocatedFalse,
1743 OperandType::AllocatedTrue,
1744 Boolean::Not(ref v),
1745 ) => {
1746 assert_eq!(v.value, Some(false));
1747 }
1748 (
1749 OperandType::NegatedAllocatedFalse,
1750 OperandType::AllocatedFalse,
1751 Boolean::Not(ref v),
1752 ) => {
1753 assert_eq!(v.value, Some(false));
1754 }
1755 (
1756 OperandType::NegatedAllocatedFalse,
1757 OperandType::NegatedAllocatedTrue,
1758 Boolean::Not(ref v),
1759 ) => {
1760 assert_eq!(v.value, Some(false));
1761 }
1762 (
1763 OperandType::NegatedAllocatedFalse,
1764 OperandType::NegatedAllocatedFalse,
1765 Boolean::Not(ref v),
1766 ) => {
1767 assert_eq!(v.value, Some(false));
1768 }
1769
1770 _ => panic!(
1771 "this should never be encountered, in case: (a = {:?}, b = {:?}, c = {:?})",
1772 a, b, c
1773 ),
1774 }
1775 }
1776 }
1777 }
1778
1779 #[test]
1780 fn test_boolean_and() {
1781 let variants = [
1782 OperandType::True,
1783 OperandType::False,
1784 OperandType::AllocatedTrue,
1785 OperandType::AllocatedFalse,
1786 OperandType::NegatedAllocatedTrue,
1787 OperandType::NegatedAllocatedFalse,
1788 ];
1789
1790 for first_operand in variants.iter().cloned() {
1791 for second_operand in variants.iter().cloned() {
1792 let mut cs = TestConstraintSystem::<Fr>::new();
1793
1794 let a;
1795 let b;
1796
1797 {
1798 let mut dyn_construct = |operand, name| {
1799 let cs = cs.ns(|| name);
1800
1801 match operand {
1802 OperandType::True => Boolean::constant(true),
1803 OperandType::False => Boolean::constant(false),
1804 OperandType::AllocatedTrue => {
1805 Boolean::from(AllocatedBit::alloc(cs, || Ok(true)).unwrap())
1806 }
1807 OperandType::AllocatedFalse => {
1808 Boolean::from(AllocatedBit::alloc(cs, || Ok(false)).unwrap())
1809 }
1810 OperandType::NegatedAllocatedTrue => {
1811 Boolean::from(AllocatedBit::alloc(cs, || Ok(true)).unwrap()).not()
1812 }
1813 OperandType::NegatedAllocatedFalse => {
1814 Boolean::from(AllocatedBit::alloc(cs, || Ok(false)).unwrap()).not()
1815 }
1816 }
1817 };
1818
1819 a = dyn_construct(first_operand, "a");
1820 b = dyn_construct(second_operand, "b");
1821 }
1822
1823 let c = Boolean::and(&mut cs, &a, &b).unwrap();
1824
1825 assert!(cs.is_satisfied());
1826
1827 match (first_operand, second_operand, c) {
1828 (OperandType::True, OperandType::True, Boolean::Constant(true)) => {}
1829 (OperandType::True, OperandType::False, Boolean::Constant(false)) => {}
1830 (OperandType::True, OperandType::AllocatedTrue, Boolean::Is(_)) => {}
1831 (OperandType::True, OperandType::AllocatedFalse, Boolean::Is(_)) => {}
1832 (OperandType::True, OperandType::NegatedAllocatedTrue, Boolean::Not(_)) => {}
1833 (OperandType::True, OperandType::NegatedAllocatedFalse, Boolean::Not(_)) => {}
1834
1835 (OperandType::False, OperandType::True, Boolean::Constant(false)) => {}
1836 (OperandType::False, OperandType::False, Boolean::Constant(false)) => {}
1837 (OperandType::False, OperandType::AllocatedTrue, Boolean::Constant(false)) => {}
1838 (OperandType::False, OperandType::AllocatedFalse, Boolean::Constant(false)) => {
1839 }
1840 (
1841 OperandType::False,
1842 OperandType::NegatedAllocatedTrue,
1843 Boolean::Constant(false),
1844 ) => {}
1845 (
1846 OperandType::False,
1847 OperandType::NegatedAllocatedFalse,
1848 Boolean::Constant(false),
1849 ) => {}
1850
1851 (OperandType::AllocatedTrue, OperandType::True, Boolean::Is(_)) => {}
1852 (OperandType::AllocatedTrue, OperandType::False, Boolean::Constant(false)) => {}
1853 (
1854 OperandType::AllocatedTrue,
1855 OperandType::AllocatedTrue,
1856 Boolean::Is(ref v),
1857 ) => {
1858 assert!(cs.get("and result") == Fr::one());
1859 assert_eq!(v.value, Some(true));
1860 }
1861 (
1862 OperandType::AllocatedTrue,
1863 OperandType::AllocatedFalse,
1864 Boolean::Is(ref v),
1865 ) => {
1866 assert!(cs.get("and result") == Fr::zero());
1867 assert_eq!(v.value, Some(false));
1868 }
1869 (
1870 OperandType::AllocatedTrue,
1871 OperandType::NegatedAllocatedTrue,
1872 Boolean::Is(ref v),
1873 ) => {
1874 assert!(cs.get("and not result") == Fr::zero());
1875 assert_eq!(v.value, Some(false));
1876 }
1877 (
1878 OperandType::AllocatedTrue,
1879 OperandType::NegatedAllocatedFalse,
1880 Boolean::Is(ref v),
1881 ) => {
1882 assert!(cs.get("and not result") == Fr::one());
1883 assert_eq!(v.value, Some(true));
1884 }
1885
1886 (OperandType::AllocatedFalse, OperandType::True, Boolean::Is(_)) => {}
1887 (OperandType::AllocatedFalse, OperandType::False, Boolean::Constant(false)) => {
1888 }
1889 (
1890 OperandType::AllocatedFalse,
1891 OperandType::AllocatedTrue,
1892 Boolean::Is(ref v),
1893 ) => {
1894 assert!(cs.get("and result") == Fr::zero());
1895 assert_eq!(v.value, Some(false));
1896 }
1897 (
1898 OperandType::AllocatedFalse,
1899 OperandType::AllocatedFalse,
1900 Boolean::Is(ref v),
1901 ) => {
1902 assert!(cs.get("and result") == Fr::zero());
1903 assert_eq!(v.value, Some(false));
1904 }
1905 (
1906 OperandType::AllocatedFalse,
1907 OperandType::NegatedAllocatedTrue,
1908 Boolean::Is(ref v),
1909 ) => {
1910 assert!(cs.get("and not result") == Fr::zero());
1911 assert_eq!(v.value, Some(false));
1912 }
1913 (
1914 OperandType::AllocatedFalse,
1915 OperandType::NegatedAllocatedFalse,
1916 Boolean::Is(ref v),
1917 ) => {
1918 assert!(cs.get("and not result") == Fr::zero());
1919 assert_eq!(v.value, Some(false));
1920 }
1921
1922 (OperandType::NegatedAllocatedTrue, OperandType::True, Boolean::Not(_)) => {}
1923 (
1924 OperandType::NegatedAllocatedTrue,
1925 OperandType::False,
1926 Boolean::Constant(false),
1927 ) => {}
1928 (
1929 OperandType::NegatedAllocatedTrue,
1930 OperandType::AllocatedTrue,
1931 Boolean::Is(ref v),
1932 ) => {
1933 assert!(cs.get("and not result") == Fr::zero());
1934 assert_eq!(v.value, Some(false));
1935 }
1936 (
1937 OperandType::NegatedAllocatedTrue,
1938 OperandType::AllocatedFalse,
1939 Boolean::Is(ref v),
1940 ) => {
1941 assert!(cs.get("and not result") == Fr::zero());
1942 assert_eq!(v.value, Some(false));
1943 }
1944 (
1945 OperandType::NegatedAllocatedTrue,
1946 OperandType::NegatedAllocatedTrue,
1947 Boolean::Is(ref v),
1948 ) => {
1949 assert!(cs.get("nor result") == Fr::zero());
1950 assert_eq!(v.value, Some(false));
1951 }
1952 (
1953 OperandType::NegatedAllocatedTrue,
1954 OperandType::NegatedAllocatedFalse,
1955 Boolean::Is(ref v),
1956 ) => {
1957 assert!(cs.get("nor result") == Fr::zero());
1958 assert_eq!(v.value, Some(false));
1959 }
1960
1961 (OperandType::NegatedAllocatedFalse, OperandType::True, Boolean::Not(_)) => {}
1962 (
1963 OperandType::NegatedAllocatedFalse,
1964 OperandType::False,
1965 Boolean::Constant(false),
1966 ) => {}
1967 (
1968 OperandType::NegatedAllocatedFalse,
1969 OperandType::AllocatedTrue,
1970 Boolean::Is(ref v),
1971 ) => {
1972 assert!(cs.get("and not result") == Fr::one());
1973 assert_eq!(v.value, Some(true));
1974 }
1975 (
1976 OperandType::NegatedAllocatedFalse,
1977 OperandType::AllocatedFalse,
1978 Boolean::Is(ref v),
1979 ) => {
1980 assert!(cs.get("and not result") == Fr::zero());
1981 assert_eq!(v.value, Some(false));
1982 }
1983 (
1984 OperandType::NegatedAllocatedFalse,
1985 OperandType::NegatedAllocatedTrue,
1986 Boolean::Is(ref v),
1987 ) => {
1988 assert!(cs.get("nor result") == Fr::zero());
1989 assert_eq!(v.value, Some(false));
1990 }
1991 (
1992 OperandType::NegatedAllocatedFalse,
1993 OperandType::NegatedAllocatedFalse,
1994 Boolean::Is(ref v),
1995 ) => {
1996 assert!(cs.get("nor result") == Fr::one());
1997 assert_eq!(v.value, Some(true));
1998 }
1999
2000 _ => {
2001 panic!(
2002 "unexpected behavior at {:?} AND {:?}",
2003 first_operand, second_operand
2004 );
2005 }
2006 }
2007 }
2008 }
2009 }
2010
2011 #[test]
2012 fn test_enforce_in_field() {
2013 {
2014 let mut cs = TestConstraintSystem::<Fr>::new();
2015
2016 let mut bits = vec![];
2017 for (i, b) in BitIterator::new(Fr::characteristic()).skip(1).enumerate() {
2018 bits.push(Boolean::from(
2019 AllocatedBit::alloc(cs.ns(|| format!("bit_gadget {}", i)), || Ok(b)).unwrap(),
2020 ));
2021 }
2022
2023 Boolean::enforce_in_field::<_, _, Fr>(&mut cs, &bits).unwrap();
2024
2025 assert!(!cs.is_satisfied());
2026 }
2027
2028 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
2029
2030 for _ in 0..1000 {
2031 let r = Fr::rand(&mut rng);
2032 let mut cs = TestConstraintSystem::<Fr>::new();
2033
2034 let mut bits = vec![];
2035 for (i, b) in BitIterator::new(r.into_repr()).skip(1).enumerate() {
2036 bits.push(Boolean::from(
2037 AllocatedBit::alloc(cs.ns(|| format!("bit_gadget {}", i)), || Ok(b)).unwrap(),
2038 ));
2039 }
2040
2041 Boolean::enforce_in_field::<_, _, Fr>(&mut cs, &bits).unwrap();
2042
2043 assert!(cs.is_satisfied());
2044 }
2045 }
2046
2047 #[test]
2048 fn test_enforce_nand() {
2049 {
2050 let mut cs = TestConstraintSystem::<Fr>::new();
2051
2052 assert!(Boolean::enforce_nand(&mut cs, &[Boolean::constant(false)]).is_ok());
2053 assert!(Boolean::enforce_nand(&mut cs, &[Boolean::constant(true)]).is_err());
2054 }
2055
2056 for i in 1..5 {
2057 // with every possible assignment for them
2058 for mut b in 0..(1 << i) {
2059 // with every possible negation
2060 for mut n in 0..(1 << i) {
2061 let mut cs = TestConstraintSystem::<Fr>::new();
2062
2063 let mut expected = true;
2064
2065 let mut bits = vec![];
2066 for j in 0..i {
2067 expected &= b & 1 == 1;
2068
2069 if n & 1 == 1 {
2070 bits.push(Boolean::from(
2071 AllocatedBit::alloc(cs.ns(|| format!("bit_gadget {}", j)), || {
2072 Ok(b & 1 == 1)
2073 })
2074 .unwrap(),
2075 ));
2076 } else {
2077 bits.push(
2078 Boolean::from(
2079 AllocatedBit::alloc(
2080 cs.ns(|| format!("bit_gadget {}", j)),
2081 || Ok(b & 1 == 0),
2082 )
2083 .unwrap(),
2084 )
2085 .not(),
2086 );
2087 }
2088
2089 b >>= 1;
2090 n >>= 1;
2091 }
2092
2093 let expected = !expected;
2094
2095 Boolean::enforce_nand(&mut cs, &bits).unwrap();
2096
2097 if expected {
2098 assert!(cs.is_satisfied());
2099 } else {
2100 assert!(!cs.is_satisfied());
2101 }
2102 }
2103 }
2104 }
2105 }
2106
2107 #[test]
2108 fn test_kary_and() {
2109 // test different numbers of operands
2110 for i in 1..15 {
2111 // with every possible assignment for them
2112 for mut b in 0..(1 << i) {
2113 let mut cs = TestConstraintSystem::<Fr>::new();
2114
2115 let mut expected = true;
2116
2117 let mut bits = vec![];
2118 for j in 0..i {
2119 expected &= b & 1 == 1;
2120
2121 bits.push(Boolean::from(
2122 AllocatedBit::alloc(cs.ns(|| format!("bit_gadget {}", j)), || {
2123 Ok(b & 1 == 1)
2124 })
2125 .unwrap(),
2126 ));
2127 b >>= 1;
2128 }
2129
2130 let r = Boolean::kary_and(&mut cs, &bits).unwrap();
2131
2132 assert!(cs.is_satisfied());
2133
2134 match r {
2135 Boolean::Is(ref r) => {
2136 assert_eq!(r.value.unwrap(), expected);
2137 }
2138 _ => unreachable!(),
2139 }
2140 }
2141 }
2142 }
2143}