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