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 /// Asserts that at least one operand is false.
553 pub fn enforce_nand<ConstraintF, CS>(mut cs: CS, bits: &[Self]) -> Result<(), SynthesisError>
554 where
555 ConstraintF: Field,
556 CS: ConstraintSystem<ConstraintF>,
557 {
558 let res = Self::kary_and(&mut cs, bits)?;
559
560 match res {
561 Boolean::Constant(false) => Ok(()),
562 Boolean::Constant(true) => Err(SynthesisError::AssignmentMissing),
563 Boolean::Is(ref res) => {
564 cs.enforce(
565 || "enforce nand",
566 |lc| lc,
567 |lc| lc,
568 |lc| lc + res.get_variable(),
569 );
570
571 Ok(())
572 }
573 Boolean::Not(ref res) => {
574 cs.enforce(
575 || "enforce nand",
576 |lc| lc,
577 |lc| lc,
578 |lc| lc + CS::one() - res.get_variable(),
579 );
580
581 Ok(())
582 }
583 }
584 }
585
586 /// Asserts that this bit_gadget representation is "in
587 /// the field" when interpreted in big endian.
588 pub fn enforce_in_field<ConstraintF, CS, F: PrimeField>(
589 cs: CS,
590 bits: &[Self],
591 ) -> Result<(), SynthesisError>
592 where
593 ConstraintF: Field,
594 CS: ConstraintSystem<ConstraintF>,
595 {
596 // b = char() - 1
597 let mut b = F::characteristic().to_vec();
598 assert_eq!(b[0] % 2, 1);
599 b[0] -= 1;
600 let run = Self::enforce_smaller_or_equal_than::<_, _, F, _>(cs, bits, b)?;
601
602 // We should always end in a "run" of zeros, because
603 // the characteristic is an odd prime. So, this should
604 // be empty.
605 assert!(run.is_empty());
606
607 Ok(())
608 }
609
610 /// Asserts that this bit_gadget representation is smaller
611 /// or equal than the provided element
612 pub fn enforce_smaller_or_equal_than<ConstraintF, CS, F: PrimeField, E: AsRef<[u64]>>(
613 mut cs: CS,
614 bits: &[Self],
615 element: E,
616 ) -> Result<Vec<Boolean>, SynthesisError>
617 where
618 ConstraintF: Field,
619 CS: ConstraintSystem<ConstraintF>,
620 {
621 let mut bits_iter = bits.iter();
622 let b: &[u64] = element.as_ref();
623
624 // Runs of ones in r
625 let mut last_run = Boolean::constant(true);
626 let mut current_run = vec![];
627
628 let mut found_one = false;
629 let mut run_i = 0;
630 let mut nand_i = 0;
631
632 let char_num_bits = {
633 let mut leading_zeros = 0;
634 let mut total_bits = 0;
635 let mut found_one = false;
636 for b in BitIterator::new(b.clone()) {
637 total_bits += 1;
638 if !b && !found_one {
639 leading_zeros += 1
640 }
641 if b {
642 found_one = true;
643 }
644 }
645
646 total_bits - leading_zeros
647 };
648
649 if bits.len() > char_num_bits {
650 let num_extra_bits = bits.len() - char_num_bits;
651 let mut or_result = Boolean::constant(false);
652 for (i, should_be_zero) in bits[0..num_extra_bits].iter().enumerate() {
653 or_result = Boolean::or(
654 &mut cs.ns(|| format!("Check {}-th or", i)),
655 &or_result,
656 should_be_zero,
657 )?;
658 let _ = bits_iter.next().unwrap();
659 }
660 or_result.enforce_equal(
661 &mut cs.ns(|| "Check that or of extra bits is zero"),
662 &Boolean::constant(false),
663 )?;
664 }
665
666 for b in BitIterator::new(b) {
667 // Skip over unset bits at the beginning
668 found_one |= b;
669 if !found_one {
670 continue;
671 }
672
673 let a = bits_iter.next().unwrap();
674
675 if b {
676 // This is part of a run of ones.
677 current_run.push(a.clone());
678 } else {
679 if !current_run.is_empty() {
680 // This is the start of a run of zeros, but we need
681 // to k-ary AND against `last_run` first.
682
683 current_run.push(last_run);
684 last_run = Self::kary_and(cs.ns(|| format!("run {}", run_i)), ¤t_run)?;
685 run_i += 1;
686 current_run.truncate(0);
687 }
688
689 // If `last_run` is true, `a` must be false, or it would
690 // not be in the field.
691 //
692 // If `last_run` is false, `a` can be true or false.
693 //
694 // Ergo, at least one of `last_run` and `a` must be false.
695 Self::enforce_nand(cs.ns(|| format!("nand {}", nand_i)), &[last_run, *a])?;
696 nand_i += 1;
697 }
698 }
699 assert!(bits_iter.next().is_none());
700
701 Ok(current_run)
702 }
703}
704
705impl PartialEq for Boolean {
706 fn eq(&self, other: &Self) -> bool {
707 use self::Boolean::*;
708
709 match (*self, *other) {
710 (Is(a), Is(b)) | (Not(a), Not(b)) => a == b,
711 (Is(a), Not(b)) | (Not(a), Is(b)) => a != b,
712 (Is(a), Constant(b)) | (Constant(b), Is(a)) => a.value.unwrap() == b,
713 (Not(a), Constant(b)) | (Constant(b), Not(a)) => a.value.unwrap() != b,
714 (Constant(a), Constant(b)) => a == b,
715 }
716 }
717}
718
719impl Eq for Boolean {}
720
721impl From<AllocatedBit> for Boolean {
722 fn from(b: AllocatedBit) -> Boolean {
723 Boolean::Is(b)
724 }
725}
726
727impl<ConstraintF: Field> AllocGadget<bool, ConstraintF> for Boolean {
728 fn alloc_constant<T, CS: ConstraintSystem<ConstraintF>>(
729 _cs: CS,
730 t: T,
731 ) -> Result<Self, SynthesisError>
732 where
733 T: Borrow<bool>,
734 {
735 Ok(Boolean::constant(*t.borrow()))
736 }
737
738 fn alloc<F, T, CS: ConstraintSystem<ConstraintF>>(
739 cs: CS,
740 value_gen: F,
741 ) -> Result<Self, SynthesisError>
742 where
743 F: FnOnce() -> Result<T, SynthesisError>,
744 T: Borrow<bool>,
745 {
746 AllocatedBit::alloc(cs, value_gen).map(Boolean::from)
747 }
748
749 fn alloc_input<F, T, CS: ConstraintSystem<ConstraintF>>(
750 cs: CS,
751 value_gen: F,
752 ) -> Result<Self, SynthesisError>
753 where
754 F: FnOnce() -> Result<T, SynthesisError>,
755 T: Borrow<bool>,
756 {
757 AllocatedBit::alloc_input(cs, value_gen).map(Boolean::from)
758 }
759}
760
761impl<ConstraintF: Field> EqGadget<ConstraintF> for Boolean {}
762
763impl<ConstraintF: Field> ConditionalEqGadget<ConstraintF> for Boolean {
764 fn conditional_enforce_equal<CS>(
765 &self,
766 mut cs: CS,
767 other: &Self,
768 condition: &Boolean,
769 ) -> Result<(), SynthesisError>
770 where
771 CS: ConstraintSystem<ConstraintF>,
772 {
773 use self::Boolean::*;
774 let one = CS::one();
775 let difference: LinearCombination<ConstraintF> = match (self, other) {
776 // 1 - 1 = 0 - 0 = 0
777 (Constant(true), Constant(true)) | (Constant(false), Constant(false)) => return Ok(()),
778 // false != true
779 (Constant(_), Constant(_)) => return Err(SynthesisError::AssignmentMissing),
780 // 1 - a
781 (Constant(true), Is(a)) | (Is(a), Constant(true)) => {
782 LinearCombination::zero() + one - a.get_variable()
783 }
784 // a - 0 = a
785 (Constant(false), Is(a)) | (Is(a), Constant(false)) => {
786 LinearCombination::zero() + a.get_variable()
787 }
788 // 1 - !a = 1 - (1 - a) = a
789 (Constant(true), Not(a)) | (Not(a), Constant(true)) => {
790 LinearCombination::zero() + a.get_variable()
791 }
792 // !a - 0 = !a = 1 - a
793 (Constant(false), Not(a)) | (Not(a), Constant(false)) => {
794 LinearCombination::zero() + one - a.get_variable()
795 }
796 // b - a,
797 (Is(a), Is(b)) => LinearCombination::zero() + b.get_variable() - a.get_variable(),
798 // !b - a = (1 - b) - a
799 (Is(a), Not(b)) | (Not(b), Is(a)) => {
800 LinearCombination::zero() + one - b.get_variable() - a.get_variable()
801 }
802 // !b - !a = (1 - b) - (1 - a) = a - b,
803 (Not(a), Not(b)) => LinearCombination::zero() + a.get_variable() - b.get_variable(),
804 };
805
806 if let Constant(false) = condition {
807 Ok(())
808 } else {
809 cs.enforce(
810 || "conditional_equals",
811 |lc| difference + &lc,
812 |lc| condition.lc(one, ConstraintF::one()) + &lc,
813 |lc| lc,
814 );
815 Ok(())
816 }
817 }
818
819 fn cost() -> usize {
820 1
821 }
822}
823
824impl<ConstraintF: Field> ToBytesGadget<ConstraintF> for Boolean {
825 /// Outputs `1u8` if `self` is true, and `0u8` otherwise.
826 fn to_bytes<CS: ConstraintSystem<ConstraintF>>(
827 &self,
828 _cs: CS,
829 ) -> Result<Vec<UInt8>, SynthesisError> {
830 let mut bits = vec![Boolean::constant(false); 7];
831 bits.push(*self);
832 bits.reverse();
833 let value = self.get_value().map(|val| val as u8);
834 let byte = UInt8 { bits, value };
835 Ok(vec![byte])
836 }
837}
838
839impl<ConstraintF: PrimeField> CondSelectGadget<ConstraintF> for Boolean {
840 fn conditionally_select<CS>(
841 mut cs: CS,
842 cond: &Self,
843 true_value: &Self,
844 false_value: &Self,
845 ) -> Result<Self, SynthesisError>
846 where
847 CS: ConstraintSystem<ConstraintF>,
848 {
849 match cond {
850 Boolean::Constant(true) => Ok(true_value.clone()),
851 Boolean::Constant(false) => Ok(false_value.clone()),
852 cond @ Boolean::Not(_) => {
853 Self::conditionally_select(cs, &cond.not(), false_value, true_value)
854 }
855 cond @ Boolean::Is(_) => match (true_value, false_value) {
856 (x, &Boolean::Constant(false)) => Boolean::and(cs.ns(|| "and"), cond, x).into(),
857 (&Boolean::Constant(false), x) => Boolean::and(cs.ns(|| "and"), &cond.not(), x),
858 (&Boolean::Constant(true), x) => Boolean::or(cs.ns(|| "or"), cond, x).into(),
859 (x, &Boolean::Constant(true)) => Boolean::or(cs.ns(|| "or"), &cond.not(), x),
860 (a @ Boolean::Is(_), b @ Boolean::Is(_))
861 | (a @ Boolean::Not(_), b @ Boolean::Not(_))
862 | (a @ Boolean::Is(_), b @ Boolean::Not(_))
863 | (a @ Boolean::Not(_), b @ Boolean::Is(_)) => {
864 let a_lc = a.lc(CS::one(), ConstraintF::one());
865 let b_lc = b.lc(CS::one(), ConstraintF::one());
866 Ok(
867 cond_select_helper(cs, cond, (a.get_value(), a_lc), (b.get_value(), b_lc))?
868 .into(),
869 )
870 }
871 },
872 }
873 }
874
875 fn cost() -> usize {
876 1
877 }
878}
879
880#[cfg(test)]
881mod test {
882 use super::{AllocatedBit, Boolean};
883 use crate::{prelude::*, test_constraint_system::TestConstraintSystem};
884 use algebra::{bls12_381::Fr, BitIterator, Field, One, PrimeField, UniformRand, Zero};
885 use core::str::FromStr;
886 use r1cs_core::ConstraintSystem;
887 use rand::SeedableRng;
888 use rand_xorshift::XorShiftRng;
889
890 #[test]
891 fn test_boolean_to_byte() {
892 for val in [true, false].iter() {
893 let mut cs = TestConstraintSystem::<Fr>::new();
894 let a: Boolean = AllocatedBit::alloc(&mut cs, || Ok(*val)).unwrap().into();
895 let bytes = a.to_bytes(&mut cs.ns(|| "ToBytes")).unwrap();
896 assert_eq!(bytes.len(), 1);
897 let byte = &bytes[0];
898 assert_eq!(byte.value.unwrap(), *val as u8);
899
900 for (i, bit_gadget) in byte.bits.iter().enumerate() {
901 assert_eq!(
902 bit_gadget.get_value().unwrap(),
903 (byte.value.unwrap() >> i) & 1 == 1
904 );
905 }
906 }
907 }
908
909 #[test]
910 fn test_allocated_bit() {
911 let mut cs = TestConstraintSystem::<Fr>::new();
912
913 AllocatedBit::alloc(&mut cs, || Ok(true)).unwrap();
914 assert!(cs.get("boolean") == Fr::one());
915 assert!(cs.is_satisfied());
916 cs.set("boolean", Fr::zero());
917 assert!(cs.is_satisfied());
918 cs.set("boolean", Fr::from_str("2").unwrap());
919 assert!(!cs.is_satisfied());
920 assert!(cs.which_is_unsatisfied() == Some("boolean constraint"));
921 }
922
923 #[test]
924 fn test_xor() {
925 for a_val in [false, true].iter() {
926 for b_val in [false, true].iter() {
927 let mut cs = TestConstraintSystem::<Fr>::new();
928 let a = AllocatedBit::alloc(cs.ns(|| "a"), || Ok(*a_val)).unwrap();
929 let b = AllocatedBit::alloc(cs.ns(|| "b"), || Ok(*b_val)).unwrap();
930 let c = AllocatedBit::xor(&mut cs, &a, &b).unwrap();
931 assert_eq!(c.value.unwrap(), *a_val ^ *b_val);
932
933 assert!(cs.is_satisfied());
934 }
935 }
936 }
937
938 #[test]
939 fn test_or() {
940 for a_val in [false, true].iter() {
941 for b_val in [false, true].iter() {
942 let mut cs = TestConstraintSystem::<Fr>::new();
943 let a = AllocatedBit::alloc(cs.ns(|| "a"), || Ok(*a_val)).unwrap();
944 let b = AllocatedBit::alloc(cs.ns(|| "b"), || Ok(*b_val)).unwrap();
945 let c = AllocatedBit::or(&mut cs, &a, &b).unwrap();
946 assert_eq!(c.value.unwrap(), *a_val | *b_val);
947
948 assert!(cs.is_satisfied());
949 assert!(cs.get("a/boolean") == if *a_val { Fr::one() } else { Fr::zero() });
950 assert!(cs.get("b/boolean") == if *b_val { Fr::one() } else { Fr::zero() });
951 }
952 }
953 }
954
955 #[test]
956 fn test_and() {
957 for a_val in [false, true].iter() {
958 for b_val in [false, true].iter() {
959 let mut cs = TestConstraintSystem::<Fr>::new();
960 let a = AllocatedBit::alloc(cs.ns(|| "a"), || Ok(*a_val)).unwrap();
961 let b = AllocatedBit::alloc(cs.ns(|| "b"), || Ok(*b_val)).unwrap();
962 let c = AllocatedBit::and(&mut cs, &a, &b).unwrap();
963 assert_eq!(c.value.unwrap(), *a_val & *b_val);
964
965 assert!(cs.is_satisfied());
966 assert!(cs.get("a/boolean") == if *a_val { Fr::one() } else { Fr::zero() });
967 assert!(cs.get("b/boolean") == if *b_val { Fr::one() } else { Fr::zero() });
968 assert!(
969 cs.get("and result")
970 == if *a_val & *b_val {
971 Fr::one()
972 } else {
973 Fr::zero()
974 }
975 );
976
977 // Invert the result and check if the constraint system is still satisfied
978 cs.set(
979 "and result",
980 if *a_val & *b_val {
981 Fr::zero()
982 } else {
983 Fr::one()
984 },
985 );
986 assert!(!cs.is_satisfied());
987 }
988 }
989 }
990
991 #[test]
992 fn test_and_not() {
993 for a_val in [false, true].iter() {
994 for b_val in [false, true].iter() {
995 let mut cs = TestConstraintSystem::<Fr>::new();
996 let a = AllocatedBit::alloc(cs.ns(|| "a"), || Ok(*a_val)).unwrap();
997 let b = AllocatedBit::alloc(cs.ns(|| "b"), || Ok(*b_val)).unwrap();
998 let c = AllocatedBit::and_not(&mut cs, &a, &b).unwrap();
999 assert_eq!(c.value.unwrap(), *a_val & !*b_val);
1000
1001 assert!(cs.is_satisfied());
1002 assert!(cs.get("a/boolean") == if *a_val { Fr::one() } else { Fr::zero() });
1003 assert!(cs.get("b/boolean") == if *b_val { Fr::one() } else { Fr::zero() });
1004 assert!(
1005 cs.get("and not result")
1006 == if *a_val & !*b_val {
1007 Fr::one()
1008 } else {
1009 Fr::zero()
1010 }
1011 );
1012
1013 // Invert the result and check if the constraint system is still satisfied
1014 cs.set(
1015 "and not result",
1016 if *a_val & !*b_val {
1017 Fr::zero()
1018 } else {
1019 Fr::one()
1020 },
1021 );
1022 assert!(!cs.is_satisfied());
1023 }
1024 }
1025 }
1026
1027 #[test]
1028 fn test_nor() {
1029 for a_val in [false, true].iter() {
1030 for b_val in [false, true].iter() {
1031 let mut cs = TestConstraintSystem::<Fr>::new();
1032 let a = AllocatedBit::alloc(cs.ns(|| "a"), || Ok(*a_val)).unwrap();
1033 let b = AllocatedBit::alloc(cs.ns(|| "b"), || Ok(*b_val)).unwrap();
1034 let c = AllocatedBit::nor(&mut cs, &a, &b).unwrap();
1035 assert_eq!(c.value.unwrap(), !*a_val & !*b_val);
1036
1037 assert!(cs.is_satisfied());
1038 assert!(cs.get("a/boolean") == if *a_val { Fr::one() } else { Fr::zero() });
1039 assert!(cs.get("b/boolean") == if *b_val { Fr::one() } else { Fr::zero() });
1040 assert!(
1041 cs.get("nor result")
1042 == if !*a_val & !*b_val {
1043 Fr::one()
1044 } else {
1045 Fr::zero()
1046 }
1047 );
1048
1049 // Invert the result and check if the constraint system is still satisfied
1050 cs.set(
1051 "nor result",
1052 if !*a_val & !*b_val {
1053 Fr::zero()
1054 } else {
1055 Fr::one()
1056 },
1057 );
1058 assert!(!cs.is_satisfied());
1059 }
1060 }
1061 }
1062
1063 #[test]
1064 fn test_enforce_equal() {
1065 for a_bool in [false, true].iter().cloned() {
1066 for b_bool in [false, true].iter().cloned() {
1067 for a_neg in [false, true].iter().cloned() {
1068 for b_neg in [false, true].iter().cloned() {
1069 let mut cs = TestConstraintSystem::<Fr>::new();
1070
1071 let mut a: Boolean = AllocatedBit::alloc(cs.ns(|| "a"), || Ok(a_bool))
1072 .unwrap()
1073 .into();
1074 let mut b: Boolean = AllocatedBit::alloc(cs.ns(|| "b"), || Ok(b_bool))
1075 .unwrap()
1076 .into();
1077
1078 if a_neg {
1079 a = a.not();
1080 }
1081 if b_neg {
1082 b = b.not();
1083 }
1084
1085 a.enforce_equal(&mut cs, &b).unwrap();
1086
1087 assert_eq!(cs.is_satisfied(), (a_bool ^ a_neg) == (b_bool ^ b_neg));
1088 }
1089 }
1090 }
1091 }
1092 }
1093
1094 #[test]
1095 fn test_conditional_enforce_equal() {
1096 for a_bool in [false, true].iter().cloned() {
1097 for b_bool in [false, true].iter().cloned() {
1098 for a_neg in [false, true].iter().cloned() {
1099 for b_neg in [false, true].iter().cloned() {
1100 let mut cs = TestConstraintSystem::<Fr>::new();
1101
1102 // First test if constraint system is satisfied
1103 // when we do want to enforce the condition.
1104 let mut a: Boolean = AllocatedBit::alloc(cs.ns(|| "a"), || Ok(a_bool))
1105 .unwrap()
1106 .into();
1107 let mut b: Boolean = AllocatedBit::alloc(cs.ns(|| "b"), || Ok(b_bool))
1108 .unwrap()
1109 .into();
1110
1111 if a_neg {
1112 a = a.not();
1113 }
1114 if b_neg {
1115 b = b.not();
1116 }
1117
1118 a.conditional_enforce_equal(&mut cs, &b, &Boolean::constant(true))
1119 .unwrap();
1120
1121 assert_eq!(cs.is_satisfied(), (a_bool ^ a_neg) == (b_bool ^ b_neg));
1122
1123 // Now test if constraint system is satisfied even
1124 // when we don't want to enforce the condition.
1125 let mut cs = TestConstraintSystem::<Fr>::new();
1126
1127 let mut a: Boolean = AllocatedBit::alloc(cs.ns(|| "a"), || Ok(a_bool))
1128 .unwrap()
1129 .into();
1130 let mut b: Boolean = AllocatedBit::alloc(cs.ns(|| "b"), || Ok(b_bool))
1131 .unwrap()
1132 .into();
1133
1134 if a_neg {
1135 a = a.not();
1136 }
1137 if b_neg {
1138 b = b.not();
1139 }
1140
1141 let false_cond = AllocatedBit::alloc(cs.ns(|| "cond"), || Ok(false))
1142 .unwrap()
1143 .into();
1144 a.conditional_enforce_equal(&mut cs, &b, &false_cond)
1145 .unwrap();
1146
1147 assert!(cs.is_satisfied());
1148 }
1149 }
1150 }
1151 }
1152 }
1153
1154 #[test]
1155 fn test_boolean_negation() {
1156 let mut cs = TestConstraintSystem::<Fr>::new();
1157
1158 let mut b = Boolean::from(AllocatedBit::alloc(&mut cs, || Ok(true)).unwrap());
1159
1160 match b {
1161 Boolean::Is(_) => {}
1162 _ => panic!("unexpected value"),
1163 }
1164
1165 b = b.not();
1166
1167 match b {
1168 Boolean::Not(_) => {}
1169 _ => panic!("unexpected value"),
1170 }
1171
1172 b = b.not();
1173
1174 match b {
1175 Boolean::Is(_) => {}
1176 _ => panic!("unexpected value"),
1177 }
1178
1179 b = Boolean::constant(true);
1180
1181 match b {
1182 Boolean::Constant(true) => {}
1183 _ => panic!("unexpected value"),
1184 }
1185
1186 b = b.not();
1187
1188 match b {
1189 Boolean::Constant(false) => {}
1190 _ => panic!("unexpected value"),
1191 }
1192
1193 b = b.not();
1194
1195 match b {
1196 Boolean::Constant(true) => {}
1197 _ => panic!("unexpected value"),
1198 }
1199 }
1200
1201 #[derive(Copy, Clone, Debug)]
1202 enum OperandType {
1203 True,
1204 False,
1205 AllocatedTrue,
1206 AllocatedFalse,
1207 NegatedAllocatedTrue,
1208 NegatedAllocatedFalse,
1209 }
1210
1211 #[test]
1212 fn test_boolean_xor() {
1213 let variants = [
1214 OperandType::True,
1215 OperandType::False,
1216 OperandType::AllocatedTrue,
1217 OperandType::AllocatedFalse,
1218 OperandType::NegatedAllocatedTrue,
1219 OperandType::NegatedAllocatedFalse,
1220 ];
1221
1222 for first_operand in variants.iter().cloned() {
1223 for second_operand in variants.iter().cloned() {
1224 let mut cs = TestConstraintSystem::<Fr>::new();
1225
1226 let a;
1227 let b;
1228
1229 {
1230 let mut dyn_construct = |operand, name| {
1231 let cs = cs.ns(|| name);
1232
1233 match operand {
1234 OperandType::True => Boolean::constant(true),
1235 OperandType::False => Boolean::constant(false),
1236 OperandType::AllocatedTrue => {
1237 Boolean::from(AllocatedBit::alloc(cs, || Ok(true)).unwrap())
1238 }
1239 OperandType::AllocatedFalse => {
1240 Boolean::from(AllocatedBit::alloc(cs, || Ok(false)).unwrap())
1241 }
1242 OperandType::NegatedAllocatedTrue => {
1243 Boolean::from(AllocatedBit::alloc(cs, || Ok(true)).unwrap()).not()
1244 }
1245 OperandType::NegatedAllocatedFalse => {
1246 Boolean::from(AllocatedBit::alloc(cs, || Ok(false)).unwrap()).not()
1247 }
1248 }
1249 };
1250
1251 a = dyn_construct(first_operand, "a");
1252 b = dyn_construct(second_operand, "b");
1253 }
1254
1255 let c = Boolean::xor(&mut cs, &a, &b).unwrap();
1256
1257 assert!(cs.is_satisfied());
1258
1259 match (first_operand, second_operand, c) {
1260 (OperandType::True, OperandType::True, Boolean::Constant(false)) => {}
1261 (OperandType::True, OperandType::False, Boolean::Constant(true)) => {}
1262 (OperandType::True, OperandType::AllocatedTrue, Boolean::Not(_)) => {}
1263 (OperandType::True, OperandType::AllocatedFalse, Boolean::Not(_)) => {}
1264 (OperandType::True, OperandType::NegatedAllocatedTrue, Boolean::Is(_)) => {}
1265 (OperandType::True, OperandType::NegatedAllocatedFalse, Boolean::Is(_)) => {}
1266
1267 (OperandType::False, OperandType::True, Boolean::Constant(true)) => {}
1268 (OperandType::False, OperandType::False, Boolean::Constant(false)) => {}
1269 (OperandType::False, OperandType::AllocatedTrue, Boolean::Is(_)) => {}
1270 (OperandType::False, OperandType::AllocatedFalse, Boolean::Is(_)) => {}
1271 (OperandType::False, OperandType::NegatedAllocatedTrue, Boolean::Not(_)) => {}
1272 (OperandType::False, OperandType::NegatedAllocatedFalse, Boolean::Not(_)) => {}
1273
1274 (OperandType::AllocatedTrue, OperandType::True, Boolean::Not(_)) => {}
1275 (OperandType::AllocatedTrue, OperandType::False, Boolean::Is(_)) => {}
1276 (
1277 OperandType::AllocatedTrue,
1278 OperandType::AllocatedTrue,
1279 Boolean::Is(ref v),
1280 ) => {
1281 assert!(cs.get("xor result") == Fr::zero());
1282 assert_eq!(v.value, Some(false));
1283 }
1284 (
1285 OperandType::AllocatedTrue,
1286 OperandType::AllocatedFalse,
1287 Boolean::Is(ref v),
1288 ) => {
1289 assert!(cs.get("xor result") == Fr::one());
1290 assert_eq!(v.value, Some(true));
1291 }
1292 (
1293 OperandType::AllocatedTrue,
1294 OperandType::NegatedAllocatedTrue,
1295 Boolean::Not(ref v),
1296 ) => {
1297 assert!(cs.get("xor result") == Fr::zero());
1298 assert_eq!(v.value, Some(false));
1299 }
1300 (
1301 OperandType::AllocatedTrue,
1302 OperandType::NegatedAllocatedFalse,
1303 Boolean::Not(ref v),
1304 ) => {
1305 assert!(cs.get("xor result") == Fr::one());
1306 assert_eq!(v.value, Some(true));
1307 }
1308
1309 (OperandType::AllocatedFalse, OperandType::True, Boolean::Not(_)) => {}
1310 (OperandType::AllocatedFalse, OperandType::False, Boolean::Is(_)) => {}
1311 (
1312 OperandType::AllocatedFalse,
1313 OperandType::AllocatedTrue,
1314 Boolean::Is(ref v),
1315 ) => {
1316 assert!(cs.get("xor result") == Fr::one());
1317 assert_eq!(v.value, Some(true));
1318 }
1319 (
1320 OperandType::AllocatedFalse,
1321 OperandType::AllocatedFalse,
1322 Boolean::Is(ref v),
1323 ) => {
1324 assert!(cs.get("xor result") == Fr::zero());
1325 assert_eq!(v.value, Some(false));
1326 }
1327 (
1328 OperandType::AllocatedFalse,
1329 OperandType::NegatedAllocatedTrue,
1330 Boolean::Not(ref v),
1331 ) => {
1332 assert!(cs.get("xor result") == Fr::one());
1333 assert_eq!(v.value, Some(true));
1334 }
1335 (
1336 OperandType::AllocatedFalse,
1337 OperandType::NegatedAllocatedFalse,
1338 Boolean::Not(ref v),
1339 ) => {
1340 assert!(cs.get("xor result") == Fr::zero());
1341 assert_eq!(v.value, Some(false));
1342 }
1343
1344 (OperandType::NegatedAllocatedTrue, OperandType::True, Boolean::Is(_)) => {}
1345 (OperandType::NegatedAllocatedTrue, OperandType::False, Boolean::Not(_)) => {}
1346 (
1347 OperandType::NegatedAllocatedTrue,
1348 OperandType::AllocatedTrue,
1349 Boolean::Not(ref v),
1350 ) => {
1351 assert!(cs.get("xor result") == Fr::zero());
1352 assert_eq!(v.value, Some(false));
1353 }
1354 (
1355 OperandType::NegatedAllocatedTrue,
1356 OperandType::AllocatedFalse,
1357 Boolean::Not(ref v),
1358 ) => {
1359 assert!(cs.get("xor result") == Fr::one());
1360 assert_eq!(v.value, Some(true));
1361 }
1362 (
1363 OperandType::NegatedAllocatedTrue,
1364 OperandType::NegatedAllocatedTrue,
1365 Boolean::Is(ref v),
1366 ) => {
1367 assert!(cs.get("xor result") == Fr::zero());
1368 assert_eq!(v.value, Some(false));
1369 }
1370 (
1371 OperandType::NegatedAllocatedTrue,
1372 OperandType::NegatedAllocatedFalse,
1373 Boolean::Is(ref v),
1374 ) => {
1375 assert!(cs.get("xor result") == Fr::one());
1376 assert_eq!(v.value, Some(true));
1377 }
1378
1379 (OperandType::NegatedAllocatedFalse, OperandType::True, Boolean::Is(_)) => {}
1380 (OperandType::NegatedAllocatedFalse, OperandType::False, Boolean::Not(_)) => {}
1381 (
1382 OperandType::NegatedAllocatedFalse,
1383 OperandType::AllocatedTrue,
1384 Boolean::Not(ref v),
1385 ) => {
1386 assert!(cs.get("xor result") == Fr::one());
1387 assert_eq!(v.value, Some(true));
1388 }
1389 (
1390 OperandType::NegatedAllocatedFalse,
1391 OperandType::AllocatedFalse,
1392 Boolean::Not(ref v),
1393 ) => {
1394 assert!(cs.get("xor result") == Fr::zero());
1395 assert_eq!(v.value, Some(false));
1396 }
1397 (
1398 OperandType::NegatedAllocatedFalse,
1399 OperandType::NegatedAllocatedTrue,
1400 Boolean::Is(ref v),
1401 ) => {
1402 assert!(cs.get("xor result") == Fr::one());
1403 assert_eq!(v.value, Some(true));
1404 }
1405 (
1406 OperandType::NegatedAllocatedFalse,
1407 OperandType::NegatedAllocatedFalse,
1408 Boolean::Is(ref v),
1409 ) => {
1410 assert!(cs.get("xor result") == Fr::zero());
1411 assert_eq!(v.value, Some(false));
1412 }
1413
1414 _ => panic!("this should never be encountered"),
1415 }
1416 }
1417 }
1418 }
1419
1420 #[test]
1421 fn test_boolean_cond_select() {
1422 let variants = [
1423 OperandType::True,
1424 OperandType::False,
1425 OperandType::AllocatedTrue,
1426 OperandType::AllocatedFalse,
1427 OperandType::NegatedAllocatedTrue,
1428 OperandType::NegatedAllocatedFalse,
1429 ];
1430
1431 for condition in variants.iter().cloned() {
1432 for first_operand in variants.iter().cloned() {
1433 for second_operand in variants.iter().cloned() {
1434 let mut cs = TestConstraintSystem::<Fr>::new();
1435
1436 let cond;
1437 let a;
1438 let b;
1439
1440 {
1441 let mut dyn_construct = |operand, name| {
1442 let cs = cs.ns(|| name);
1443
1444 match operand {
1445 OperandType::True => Boolean::constant(true),
1446 OperandType::False => Boolean::constant(false),
1447 OperandType::AllocatedTrue => {
1448 Boolean::from(AllocatedBit::alloc(cs, || Ok(true)).unwrap())
1449 }
1450 OperandType::AllocatedFalse => {
1451 Boolean::from(AllocatedBit::alloc(cs, || Ok(false)).unwrap())
1452 }
1453 OperandType::NegatedAllocatedTrue => {
1454 Boolean::from(AllocatedBit::alloc(cs, || Ok(true)).unwrap())
1455 .not()
1456 }
1457 OperandType::NegatedAllocatedFalse => {
1458 Boolean::from(AllocatedBit::alloc(cs, || Ok(false)).unwrap())
1459 .not()
1460 }
1461 }
1462 };
1463
1464 cond = dyn_construct(condition, "cond");
1465 a = dyn_construct(first_operand, "a");
1466 b = dyn_construct(second_operand, "b");
1467 }
1468
1469 let before = cs.num_constraints();
1470 let c = Boolean::conditionally_select(&mut cs, &cond, &a, &b).unwrap();
1471 let after = cs.num_constraints();
1472
1473 assert!(
1474 cs.is_satisfied(),
1475 "failed with operands: cond: {:?}, a: {:?}, b: {:?}",
1476 condition,
1477 first_operand,
1478 second_operand,
1479 );
1480 assert_eq!(
1481 c.get_value(),
1482 if cond.get_value().unwrap() {
1483 a.get_value()
1484 } else {
1485 b.get_value()
1486 }
1487 );
1488 assert!(<Boolean as CondSelectGadget<Fr>>::cost() >= after - before);
1489 }
1490 }
1491 }
1492 }
1493
1494 #[test]
1495 fn test_boolean_or() {
1496 let variants = [
1497 OperandType::True,
1498 OperandType::False,
1499 OperandType::AllocatedTrue,
1500 OperandType::AllocatedFalse,
1501 OperandType::NegatedAllocatedTrue,
1502 OperandType::NegatedAllocatedFalse,
1503 ];
1504
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 a;
1510 let b;
1511
1512 {
1513 let mut dyn_construct = |operand, name| {
1514 let cs = cs.ns(|| name);
1515
1516 match operand {
1517 OperandType::True => Boolean::constant(true),
1518 OperandType::False => Boolean::constant(false),
1519 OperandType::AllocatedTrue => {
1520 Boolean::from(AllocatedBit::alloc(cs, || Ok(true)).unwrap())
1521 }
1522 OperandType::AllocatedFalse => {
1523 Boolean::from(AllocatedBit::alloc(cs, || Ok(false)).unwrap())
1524 }
1525 OperandType::NegatedAllocatedTrue => {
1526 Boolean::from(AllocatedBit::alloc(cs, || Ok(true)).unwrap()).not()
1527 }
1528 OperandType::NegatedAllocatedFalse => {
1529 Boolean::from(AllocatedBit::alloc(cs, || Ok(false)).unwrap()).not()
1530 }
1531 }
1532 };
1533
1534 a = dyn_construct(first_operand, "a");
1535 b = dyn_construct(second_operand, "b");
1536 }
1537
1538 let c = Boolean::or(&mut cs, &a, &b).unwrap();
1539
1540 assert!(cs.is_satisfied());
1541
1542 match (first_operand, second_operand, c) {
1543 (OperandType::True, OperandType::True, Boolean::Constant(true)) => {}
1544 (OperandType::True, OperandType::False, Boolean::Constant(true)) => {}
1545 (OperandType::True, OperandType::AllocatedTrue, Boolean::Constant(true)) => {}
1546 (OperandType::True, OperandType::AllocatedFalse, Boolean::Constant(true)) => {}
1547 (
1548 OperandType::True,
1549 OperandType::NegatedAllocatedTrue,
1550 Boolean::Constant(true),
1551 ) => {}
1552 (
1553 OperandType::True,
1554 OperandType::NegatedAllocatedFalse,
1555 Boolean::Constant(true),
1556 ) => {}
1557
1558 (OperandType::False, OperandType::True, Boolean::Constant(true)) => {}
1559 (OperandType::False, OperandType::False, Boolean::Constant(false)) => {}
1560 (OperandType::False, OperandType::AllocatedTrue, Boolean::Is(_)) => {}
1561 (OperandType::False, OperandType::AllocatedFalse, Boolean::Is(_)) => {}
1562 (OperandType::False, OperandType::NegatedAllocatedTrue, Boolean::Not(_)) => {}
1563 (OperandType::False, OperandType::NegatedAllocatedFalse, Boolean::Not(_)) => {}
1564
1565 (OperandType::AllocatedTrue, OperandType::True, Boolean::Constant(true)) => {}
1566 (OperandType::AllocatedTrue, OperandType::False, Boolean::Is(_)) => {}
1567 (
1568 OperandType::AllocatedTrue,
1569 OperandType::AllocatedTrue,
1570 Boolean::Is(ref v),
1571 ) => {
1572 assert_eq!(v.value, Some(true));
1573 }
1574 (
1575 OperandType::AllocatedTrue,
1576 OperandType::AllocatedFalse,
1577 Boolean::Is(ref v),
1578 ) => {
1579 assert_eq!(v.value, Some(true));
1580 }
1581 (
1582 OperandType::AllocatedTrue,
1583 OperandType::NegatedAllocatedTrue,
1584 Boolean::Not(ref v),
1585 ) => {
1586 assert_eq!(v.value, Some(false));
1587 }
1588 (
1589 OperandType::AllocatedTrue,
1590 OperandType::NegatedAllocatedFalse,
1591 Boolean::Not(ref v),
1592 ) => {
1593 assert_eq!(v.value, Some(false));
1594 }
1595
1596 (OperandType::AllocatedFalse, OperandType::True, Boolean::Constant(true)) => {}
1597 (OperandType::AllocatedFalse, OperandType::False, Boolean::Is(_)) => {}
1598 (
1599 OperandType::AllocatedFalse,
1600 OperandType::AllocatedTrue,
1601 Boolean::Is(ref v),
1602 ) => {
1603 assert_eq!(v.value, Some(true));
1604 }
1605 (
1606 OperandType::AllocatedFalse,
1607 OperandType::AllocatedFalse,
1608 Boolean::Is(ref v),
1609 ) => {
1610 assert_eq!(v.value, Some(false));
1611 }
1612 (
1613 OperandType::AllocatedFalse,
1614 OperandType::NegatedAllocatedTrue,
1615 Boolean::Not(ref v),
1616 ) => {
1617 assert_eq!(v.value, Some(true));
1618 }
1619 (
1620 OperandType::AllocatedFalse,
1621 OperandType::NegatedAllocatedFalse,
1622 Boolean::Not(ref v),
1623 ) => {
1624 assert_eq!(v.value, Some(false));
1625 }
1626
1627 (
1628 OperandType::NegatedAllocatedTrue,
1629 OperandType::True,
1630 Boolean::Constant(true),
1631 ) => {}
1632 (OperandType::NegatedAllocatedTrue, OperandType::False, Boolean::Not(_)) => {}
1633 (
1634 OperandType::NegatedAllocatedTrue,
1635 OperandType::AllocatedTrue,
1636 Boolean::Not(ref v),
1637 ) => {
1638 assert_eq!(v.value, Some(false));
1639 }
1640 (
1641 OperandType::NegatedAllocatedTrue,
1642 OperandType::AllocatedFalse,
1643 Boolean::Not(ref v),
1644 ) => {
1645 assert_eq!(v.value, Some(true));
1646 }
1647 (
1648 OperandType::NegatedAllocatedTrue,
1649 OperandType::NegatedAllocatedTrue,
1650 Boolean::Not(ref v),
1651 ) => {
1652 assert_eq!(v.value, Some(true));
1653 }
1654 (
1655 OperandType::NegatedAllocatedTrue,
1656 OperandType::NegatedAllocatedFalse,
1657 Boolean::Not(ref v),
1658 ) => {
1659 assert_eq!(v.value, Some(false));
1660 }
1661
1662 (
1663 OperandType::NegatedAllocatedFalse,
1664 OperandType::True,
1665 Boolean::Constant(true),
1666 ) => {}
1667 (OperandType::NegatedAllocatedFalse, OperandType::False, Boolean::Not(_)) => {}
1668 (
1669 OperandType::NegatedAllocatedFalse,
1670 OperandType::AllocatedTrue,
1671 Boolean::Not(ref v),
1672 ) => {
1673 assert_eq!(v.value, Some(false));
1674 }
1675 (
1676 OperandType::NegatedAllocatedFalse,
1677 OperandType::AllocatedFalse,
1678 Boolean::Not(ref v),
1679 ) => {
1680 assert_eq!(v.value, Some(false));
1681 }
1682 (
1683 OperandType::NegatedAllocatedFalse,
1684 OperandType::NegatedAllocatedTrue,
1685 Boolean::Not(ref v),
1686 ) => {
1687 assert_eq!(v.value, Some(false));
1688 }
1689 (
1690 OperandType::NegatedAllocatedFalse,
1691 OperandType::NegatedAllocatedFalse,
1692 Boolean::Not(ref v),
1693 ) => {
1694 assert_eq!(v.value, Some(false));
1695 }
1696
1697 _ => panic!(
1698 "this should never be encountered, in case: (a = {:?}, b = {:?}, c = {:?})",
1699 a, b, c
1700 ),
1701 }
1702 }
1703 }
1704 }
1705
1706 #[test]
1707 fn test_boolean_and() {
1708 let variants = [
1709 OperandType::True,
1710 OperandType::False,
1711 OperandType::AllocatedTrue,
1712 OperandType::AllocatedFalse,
1713 OperandType::NegatedAllocatedTrue,
1714 OperandType::NegatedAllocatedFalse,
1715 ];
1716
1717 for first_operand in variants.iter().cloned() {
1718 for second_operand in variants.iter().cloned() {
1719 let mut cs = TestConstraintSystem::<Fr>::new();
1720
1721 let a;
1722 let b;
1723
1724 {
1725 let mut dyn_construct = |operand, name| {
1726 let cs = cs.ns(|| name);
1727
1728 match operand {
1729 OperandType::True => Boolean::constant(true),
1730 OperandType::False => Boolean::constant(false),
1731 OperandType::AllocatedTrue => {
1732 Boolean::from(AllocatedBit::alloc(cs, || Ok(true)).unwrap())
1733 }
1734 OperandType::AllocatedFalse => {
1735 Boolean::from(AllocatedBit::alloc(cs, || Ok(false)).unwrap())
1736 }
1737 OperandType::NegatedAllocatedTrue => {
1738 Boolean::from(AllocatedBit::alloc(cs, || Ok(true)).unwrap()).not()
1739 }
1740 OperandType::NegatedAllocatedFalse => {
1741 Boolean::from(AllocatedBit::alloc(cs, || Ok(false)).unwrap()).not()
1742 }
1743 }
1744 };
1745
1746 a = dyn_construct(first_operand, "a");
1747 b = dyn_construct(second_operand, "b");
1748 }
1749
1750 let c = Boolean::and(&mut cs, &a, &b).unwrap();
1751
1752 assert!(cs.is_satisfied());
1753
1754 match (first_operand, second_operand, c) {
1755 (OperandType::True, OperandType::True, Boolean::Constant(true)) => {}
1756 (OperandType::True, OperandType::False, Boolean::Constant(false)) => {}
1757 (OperandType::True, OperandType::AllocatedTrue, Boolean::Is(_)) => {}
1758 (OperandType::True, OperandType::AllocatedFalse, Boolean::Is(_)) => {}
1759 (OperandType::True, OperandType::NegatedAllocatedTrue, Boolean::Not(_)) => {}
1760 (OperandType::True, OperandType::NegatedAllocatedFalse, Boolean::Not(_)) => {}
1761
1762 (OperandType::False, OperandType::True, Boolean::Constant(false)) => {}
1763 (OperandType::False, OperandType::False, Boolean::Constant(false)) => {}
1764 (OperandType::False, OperandType::AllocatedTrue, Boolean::Constant(false)) => {}
1765 (OperandType::False, OperandType::AllocatedFalse, Boolean::Constant(false)) => {
1766 }
1767 (
1768 OperandType::False,
1769 OperandType::NegatedAllocatedTrue,
1770 Boolean::Constant(false),
1771 ) => {}
1772 (
1773 OperandType::False,
1774 OperandType::NegatedAllocatedFalse,
1775 Boolean::Constant(false),
1776 ) => {}
1777
1778 (OperandType::AllocatedTrue, OperandType::True, Boolean::Is(_)) => {}
1779 (OperandType::AllocatedTrue, OperandType::False, Boolean::Constant(false)) => {}
1780 (
1781 OperandType::AllocatedTrue,
1782 OperandType::AllocatedTrue,
1783 Boolean::Is(ref v),
1784 ) => {
1785 assert!(cs.get("and result") == Fr::one());
1786 assert_eq!(v.value, Some(true));
1787 }
1788 (
1789 OperandType::AllocatedTrue,
1790 OperandType::AllocatedFalse,
1791 Boolean::Is(ref v),
1792 ) => {
1793 assert!(cs.get("and result") == Fr::zero());
1794 assert_eq!(v.value, Some(false));
1795 }
1796 (
1797 OperandType::AllocatedTrue,
1798 OperandType::NegatedAllocatedTrue,
1799 Boolean::Is(ref v),
1800 ) => {
1801 assert!(cs.get("and not result") == Fr::zero());
1802 assert_eq!(v.value, Some(false));
1803 }
1804 (
1805 OperandType::AllocatedTrue,
1806 OperandType::NegatedAllocatedFalse,
1807 Boolean::Is(ref v),
1808 ) => {
1809 assert!(cs.get("and not result") == Fr::one());
1810 assert_eq!(v.value, Some(true));
1811 }
1812
1813 (OperandType::AllocatedFalse, OperandType::True, Boolean::Is(_)) => {}
1814 (OperandType::AllocatedFalse, OperandType::False, Boolean::Constant(false)) => {
1815 }
1816 (
1817 OperandType::AllocatedFalse,
1818 OperandType::AllocatedTrue,
1819 Boolean::Is(ref v),
1820 ) => {
1821 assert!(cs.get("and result") == Fr::zero());
1822 assert_eq!(v.value, Some(false));
1823 }
1824 (
1825 OperandType::AllocatedFalse,
1826 OperandType::AllocatedFalse,
1827 Boolean::Is(ref v),
1828 ) => {
1829 assert!(cs.get("and result") == Fr::zero());
1830 assert_eq!(v.value, Some(false));
1831 }
1832 (
1833 OperandType::AllocatedFalse,
1834 OperandType::NegatedAllocatedTrue,
1835 Boolean::Is(ref v),
1836 ) => {
1837 assert!(cs.get("and not result") == Fr::zero());
1838 assert_eq!(v.value, Some(false));
1839 }
1840 (
1841 OperandType::AllocatedFalse,
1842 OperandType::NegatedAllocatedFalse,
1843 Boolean::Is(ref v),
1844 ) => {
1845 assert!(cs.get("and not result") == Fr::zero());
1846 assert_eq!(v.value, Some(false));
1847 }
1848
1849 (OperandType::NegatedAllocatedTrue, OperandType::True, Boolean::Not(_)) => {}
1850 (
1851 OperandType::NegatedAllocatedTrue,
1852 OperandType::False,
1853 Boolean::Constant(false),
1854 ) => {}
1855 (
1856 OperandType::NegatedAllocatedTrue,
1857 OperandType::AllocatedTrue,
1858 Boolean::Is(ref v),
1859 ) => {
1860 assert!(cs.get("and not result") == Fr::zero());
1861 assert_eq!(v.value, Some(false));
1862 }
1863 (
1864 OperandType::NegatedAllocatedTrue,
1865 OperandType::AllocatedFalse,
1866 Boolean::Is(ref v),
1867 ) => {
1868 assert!(cs.get("and not result") == Fr::zero());
1869 assert_eq!(v.value, Some(false));
1870 }
1871 (
1872 OperandType::NegatedAllocatedTrue,
1873 OperandType::NegatedAllocatedTrue,
1874 Boolean::Is(ref v),
1875 ) => {
1876 assert!(cs.get("nor result") == Fr::zero());
1877 assert_eq!(v.value, Some(false));
1878 }
1879 (
1880 OperandType::NegatedAllocatedTrue,
1881 OperandType::NegatedAllocatedFalse,
1882 Boolean::Is(ref v),
1883 ) => {
1884 assert!(cs.get("nor result") == Fr::zero());
1885 assert_eq!(v.value, Some(false));
1886 }
1887
1888 (OperandType::NegatedAllocatedFalse, OperandType::True, Boolean::Not(_)) => {}
1889 (
1890 OperandType::NegatedAllocatedFalse,
1891 OperandType::False,
1892 Boolean::Constant(false),
1893 ) => {}
1894 (
1895 OperandType::NegatedAllocatedFalse,
1896 OperandType::AllocatedTrue,
1897 Boolean::Is(ref v),
1898 ) => {
1899 assert!(cs.get("and not result") == Fr::one());
1900 assert_eq!(v.value, Some(true));
1901 }
1902 (
1903 OperandType::NegatedAllocatedFalse,
1904 OperandType::AllocatedFalse,
1905 Boolean::Is(ref v),
1906 ) => {
1907 assert!(cs.get("and not result") == Fr::zero());
1908 assert_eq!(v.value, Some(false));
1909 }
1910 (
1911 OperandType::NegatedAllocatedFalse,
1912 OperandType::NegatedAllocatedTrue,
1913 Boolean::Is(ref v),
1914 ) => {
1915 assert!(cs.get("nor result") == Fr::zero());
1916 assert_eq!(v.value, Some(false));
1917 }
1918 (
1919 OperandType::NegatedAllocatedFalse,
1920 OperandType::NegatedAllocatedFalse,
1921 Boolean::Is(ref v),
1922 ) => {
1923 assert!(cs.get("nor result") == Fr::one());
1924 assert_eq!(v.value, Some(true));
1925 }
1926
1927 _ => {
1928 panic!(
1929 "unexpected behavior at {:?} AND {:?}",
1930 first_operand, second_operand
1931 );
1932 }
1933 }
1934 }
1935 }
1936 }
1937
1938 #[test]
1939 fn test_enforce_in_field() {
1940 {
1941 let mut cs = TestConstraintSystem::<Fr>::new();
1942
1943 let mut bits = vec![];
1944 for (i, b) in BitIterator::new(Fr::characteristic()).skip(1).enumerate() {
1945 bits.push(Boolean::from(
1946 AllocatedBit::alloc(cs.ns(|| format!("bit_gadget {}", i)), || Ok(b)).unwrap(),
1947 ));
1948 }
1949
1950 Boolean::enforce_in_field::<_, _, Fr>(&mut cs, &bits).unwrap();
1951
1952 assert!(!cs.is_satisfied());
1953 }
1954
1955 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
1956
1957 for _ in 0..1000 {
1958 let r = Fr::rand(&mut rng);
1959 let mut cs = TestConstraintSystem::<Fr>::new();
1960
1961 let mut bits = vec![];
1962 for (i, b) in BitIterator::new(r.into_repr()).skip(1).enumerate() {
1963 bits.push(Boolean::from(
1964 AllocatedBit::alloc(cs.ns(|| format!("bit_gadget {}", i)), || Ok(b)).unwrap(),
1965 ));
1966 }
1967
1968 Boolean::enforce_in_field::<_, _, Fr>(&mut cs, &bits).unwrap();
1969
1970 assert!(cs.is_satisfied());
1971 }
1972
1973 // for _ in 0..1000 {
1974 // // Sample a random element not in the field
1975 // let r = loop {
1976 // let mut a = Fr::rand(&mut rng).into_repr();
1977 // let b = Fr::rand(&mut rng).into_repr();
1978
1979 // a.add_nocarry(&b);
1980 // // we're shaving off the high bit_gadget later
1981 // a.as_mut()[3] &= 0x7fffffffffffffff;
1982 // if Fr::from_repr(a).is_err() {
1983 // break a;
1984 // }
1985 // };
1986
1987 // let mut cs = TestConstraintSystem::<Fr>::new();
1988
1989 // let mut bits = vec![];
1990 // for (i, b) in BitIterator::new(r).skip(1).enumerate() {
1991 // bits.push(Boolean::from(
1992 // AllocatedBit::alloc(cs.ns(|| format!("bit_gadget {}",
1993 // i)), Some(b)) .unwrap(),
1994 // ));
1995 // }
1996
1997 // Boolean::enforce_in_field::<_, _, Fr>(&mut cs, &bits).unwrap();
1998
1999 // assert!(!cs.is_satisfied());
2000 // }
2001 }
2002
2003 #[test]
2004 fn test_enforce_nand() {
2005 {
2006 let mut cs = TestConstraintSystem::<Fr>::new();
2007
2008 assert!(Boolean::enforce_nand(&mut cs, &[Boolean::constant(false)]).is_ok());
2009 assert!(Boolean::enforce_nand(&mut cs, &[Boolean::constant(true)]).is_err());
2010 }
2011
2012 for i in 1..5 {
2013 // with every possible assignment for them
2014 for mut b in 0..(1 << i) {
2015 // with every possible negation
2016 for mut n in 0..(1 << i) {
2017 let mut cs = TestConstraintSystem::<Fr>::new();
2018
2019 let mut expected = true;
2020
2021 let mut bits = vec![];
2022 for j in 0..i {
2023 expected &= b & 1 == 1;
2024
2025 if n & 1 == 1 {
2026 bits.push(Boolean::from(
2027 AllocatedBit::alloc(cs.ns(|| format!("bit_gadget {}", j)), || {
2028 Ok(b & 1 == 1)
2029 })
2030 .unwrap(),
2031 ));
2032 } else {
2033 bits.push(
2034 Boolean::from(
2035 AllocatedBit::alloc(
2036 cs.ns(|| format!("bit_gadget {}", j)),
2037 || Ok(b & 1 == 0),
2038 )
2039 .unwrap(),
2040 )
2041 .not(),
2042 );
2043 }
2044
2045 b >>= 1;
2046 n >>= 1;
2047 }
2048
2049 let expected = !expected;
2050
2051 Boolean::enforce_nand(&mut cs, &bits).unwrap();
2052
2053 if expected {
2054 assert!(cs.is_satisfied());
2055 } else {
2056 assert!(!cs.is_satisfied());
2057 }
2058 }
2059 }
2060 }
2061 }
2062
2063 #[test]
2064 fn test_kary_and() {
2065 // test different numbers of operands
2066 for i in 1..15 {
2067 // with every possible assignment for them
2068 for mut b in 0..(1 << i) {
2069 let mut cs = TestConstraintSystem::<Fr>::new();
2070
2071 let mut expected = true;
2072
2073 let mut bits = vec![];
2074 for j in 0..i {
2075 expected &= b & 1 == 1;
2076
2077 bits.push(Boolean::from(
2078 AllocatedBit::alloc(cs.ns(|| format!("bit_gadget {}", j)), || {
2079 Ok(b & 1 == 1)
2080 })
2081 .unwrap(),
2082 ));
2083 b >>= 1;
2084 }
2085
2086 let r = Boolean::kary_and(&mut cs, &bits).unwrap();
2087
2088 assert!(cs.is_satisfied());
2089
2090 match r {
2091 Boolean::Is(ref r) => {
2092 assert_eq!(r.value.unwrap(), expected);
2093 }
2094 _ => unreachable!(),
2095 }
2096 }
2097 }
2098 }
2099}