ark-r1cs-std/r1cs-std/src/bits/boolean.rs
r1cs-std/src/bits/boolean.rsRaw
1use algebra::{BitIterator, Field};
2
3use crate::{prelude::*, Assignment, Vec};
4use core::borrow::Borrow;
5use r1cs_core::{lc, ConstraintSystemRef, LinearCombination, Namespace, SynthesisError, Variable};
6
7/// Represents a variable in the constraint system which is guaranteed
8/// to be either zero or one.
9#[derive(Clone, Debug, Eq, PartialEq)]
10pub struct AllocatedBit<F: Field> {
11 variable: Variable,
12 cs: ConstraintSystemRef<F>,
13}
14
15pub(crate) fn bool_to_field<F: Field>(val: impl Borrow<bool>) -> F {
16 if *val.borrow() {
17 F::one()
18 } else {
19 F::zero()
20 }
21}
22
23impl<F: Field> AllocatedBit<F> {
24 /// Get the assigned value for `self`.
25 pub fn value(&self) -> Result<bool, SynthesisError> {
26 let value = self.cs.assigned_value(self.variable).get()?;
27 if value.is_zero() {
28 Ok(false)
29 } else if value.is_one() {
30 Ok(true)
31 } else {
32 unreachable!("Incorrect value assigned: {:?}", value);
33 }
34 }
35
36 /// Get the R1CS variable for `self`.
37 pub fn variable(&self) -> Variable {
38 self.variable
39 }
40
41 /// Allocate a witness variable without a booleanity check.
42 fn new_witness_without_booleanity_check<T: Borrow<bool>>(
43 cs: ConstraintSystemRef<F>,
44 f: impl FnOnce() -> Result<T, SynthesisError>,
45 ) -> Result<Self, SynthesisError> {
46 let variable = cs.new_witness_variable(|| f().map(bool_to_field))?;
47 Ok(Self { variable, cs })
48 }
49
50 /// Performs an XOR operation over the two operands, returning
51 /// an `AllocatedBit`.
52 pub fn xor(&self, b: &Self) -> Result<Self, SynthesisError> {
53 let result = Self::new_witness_without_booleanity_check(self.cs.clone(), || {
54 Ok(self.value()? ^ b.value()?)
55 })?;
56
57 // Constrain (a + a) * (b) = (a + b - c)
58 // Given that a and b are boolean constrained, if they
59 // are equal, the only solution for c is 0, and if they
60 // are different, the only solution for c is 1.
61 //
62 // ¬(a ∧ b) ∧ ¬(¬a ∧ ¬b) = c
63 // (1 - (a * b)) * (1 - ((1 - a) * (1 - b))) = c
64 // (1 - ab) * (1 - (1 - a - b + ab)) = c
65 // (1 - ab) * (a + b - ab) = c
66 // a + b - ab - (a^2)b - (b^2)a + (a^2)(b^2) = c
67 // a + b - ab - ab - ab + ab = c
68 // a + b - 2ab = c
69 // -2a * b = c - a - b
70 // 2a * b = a + b - c
71 // (a + a) * b = a + b - c
72 self.cs.enforce_constraint(
73 lc!() + self.variable + self.variable,
74 lc!() + b.variable,
75 lc!() + self.variable + b.variable - result.variable,
76 )?;
77
78 Ok(result)
79 }
80
81 /// Performs an AND operation over the two operands, returning
82 /// an `AllocatedBit`.
83 pub fn and(&self, b: &Self) -> Result<Self, SynthesisError> {
84 let result = Self::new_witness_without_booleanity_check(self.cs.clone(), || {
85 Ok(self.value()? & b.value()?)
86 })?;
87
88 // Constrain (a) * (b) = (c), ensuring c is 1 iff
89 // a AND b are both 1.
90 self.cs.enforce_constraint(
91 lc!() + self.variable,
92 lc!() + b.variable,
93 lc!() + result.variable,
94 )?;
95
96 Ok(result)
97 }
98
99 /// Performs an OR operation over the two operands, returning
100 /// an `AllocatedBit`.
101 pub fn or(&self, b: &Self) -> Result<Self, SynthesisError> {
102 let result = Self::new_witness_without_booleanity_check(self.cs.clone(), || {
103 Ok(self.value()? | b.value()?)
104 })?;
105
106 // Constrain (1 - a) * (1 - b) = (c), ensuring c is 1 iff
107 // a and b are both false, and otherwise c is 0.
108 self.cs.enforce_constraint(
109 lc!() + Variable::One - self.variable,
110 lc!() + Variable::One - b.variable,
111 lc!() + Variable::One - result.variable,
112 )?;
113
114 Ok(result)
115 }
116
117 /// Calculates `a AND (NOT b)`.
118 pub fn and_not(&self, b: &Self) -> Result<Self, SynthesisError> {
119 let result = Self::new_witness_without_booleanity_check(self.cs.clone(), || {
120 Ok(self.value()? & !b.value()?)
121 })?;
122
123 // Constrain (a) * (1 - b) = (c), ensuring c is 1 iff
124 // a is true and b is false, and otherwise c is 0.
125 self.cs.enforce_constraint(
126 lc!() + self.variable,
127 lc!() + Variable::One - b.variable,
128 lc!() + result.variable,
129 )?;
130
131 Ok(result)
132 }
133
134 /// Calculates `(NOT a) AND (NOT b)`.
135 pub fn nor(&self, b: &Self) -> Result<Self, SynthesisError> {
136 let result = Self::new_witness_without_booleanity_check(self.cs.clone(), || {
137 Ok(!(self.value()? | b.value()?))
138 })?;
139
140 // Constrain (1 - a) * (1 - b) = (c), ensuring c is 1 iff
141 // a and b are both false, and otherwise c is 0.
142 self.cs.enforce_constraint(
143 lc!() + Variable::One - self.variable,
144 lc!() + Variable::One - b.variable,
145 lc!() + result.variable,
146 )?;
147
148 Ok(result)
149 }
150}
151
152impl<F: Field> AllocVar<bool, F> for AllocatedBit<F> {
153 /// If `self.mode` == `AllocationMode::Constant`, this method simply outputs
154 /// a `Boolean::Constant`.
155 ///
156 /// Otherwise, it produces a new variable of the appropriate type
157 /// (instance or witness), with a booleanity check.
158 ///
159 /// N.B.: we could omit the booleanity check when allocating `self`
160 /// as a new public input, but that places an additional burden on
161 /// protocol designers. Better safe than sorry!
162 fn new_variable<T: Borrow<bool>>(
163 cs: impl Into<Namespace<F>>,
164 f: impl FnOnce() -> Result<T, SynthesisError>,
165 mode: AllocationMode,
166 ) -> Result<Self, SynthesisError> {
167 let ns = cs.into();
168 let cs = ns.cs();
169 if mode == AllocationMode::Constant {
170 let variable = if *f()?.borrow() {
171 Variable::One
172 } else {
173 Variable::Zero
174 };
175 Ok(Self { variable, cs })
176 } else {
177 let variable = if mode == AllocationMode::Input {
178 cs.new_input_variable(|| f().map(bool_to_field))?
179 } else {
180 cs.new_witness_variable(|| f().map(bool_to_field))?
181 };
182
183 // Constrain: (1 - a) * a = 0
184 // This constrains a to be either 0 or 1.
185
186 cs.enforce_named_constraint(
187 "Booleanity check",
188 lc!() + Variable::One - variable,
189 lc!() + variable,
190 lc!(),
191 )?;
192
193 Ok(Self { variable, cs })
194 }
195 }
196}
197
198impl<F: Field> CondSelectGadget<F> for AllocatedBit<F> {
199 fn conditionally_select(
200 cond: &Boolean<F>,
201 true_val: &Self,
202 false_val: &Self,
203 ) -> Result<Self, SynthesisError> {
204 let res = Boolean::conditionally_select(
205 cond,
206 &true_val.clone().into(),
207 &false_val.clone().into(),
208 )?;
209 match res {
210 Boolean::Is(a) => Ok(a),
211 _ => unreachable!("Impossible"),
212 }
213 }
214}
215
216/// This is a boolean value which may be either a constant or
217/// an interpretation of an `AllocatedBit`.
218#[derive(Clone, Debug, Eq, PartialEq)]
219pub enum Boolean<F: Field> {
220 /// Existential view of the boolean variable
221 Is(AllocatedBit<F>),
222 /// Negated view of the boolean variable
223 Not(AllocatedBit<F>),
224 /// Constant (not an allocated variable)
225 Constant(bool),
226}
227
228impl<F: Field> R1CSVar<F> for Boolean<F> {
229 type Value = bool;
230
231 fn cs(&self) -> Option<ConstraintSystemRef<F>> {
232 match self {
233 Self::Is(a) | Self::Not(a) => Some(a.cs.clone()),
234 _ => None,
235 }
236 }
237
238 fn value(&self) -> Result<Self::Value, SynthesisError> {
239 match self {
240 Boolean::Constant(c) => Ok(*c),
241 Boolean::Is(ref v) => v.value(),
242 Boolean::Not(ref v) => v.value().map(|b| !b),
243 }
244 }
245}
246
247impl<F: Field> Boolean<F> {
248 pub fn lc(&self) -> LinearCombination<F> {
249 match self {
250 Boolean::Constant(false) => lc!(),
251 Boolean::Constant(true) => lc!() + Variable::One,
252 Boolean::Is(v) => v.variable().into(),
253 Boolean::Not(v) => lc!() + Variable::One - v.variable(),
254 }
255 }
256
257 /// Construct a boolean vector from a vector of u8
258 pub fn constant_vec_from_bytes(values: &[u8]) -> Vec<Self> {
259 let mut input_bits = vec![];
260 for input_byte in values {
261 for bit_i in (0..8).rev() {
262 input_bits.push(Self::Constant(((input_byte >> bit_i) & 1u8) == 1u8));
263 }
264 }
265 input_bits
266 }
267
268 /// Construct a boolean from a known constant
269 pub fn constant(b: bool) -> Self {
270 Boolean::Constant(b)
271 }
272
273 /// Return a negated interpretation of this boolean.
274 pub fn not(&self) -> Self {
275 match *self {
276 Boolean::Constant(c) => Boolean::Constant(!c),
277 Boolean::Is(ref v) => Boolean::Not(v.clone()),
278 Boolean::Not(ref v) => Boolean::Is(v.clone()),
279 }
280 }
281}
282impl<F: Field> Boolean<F> {
283 /// Perform XOR over two boolean operands
284 pub fn xor<'a>(&'a self, b: &'a Self) -> Result<Self, SynthesisError> {
285 use Boolean::*;
286 match (self, b) {
287 (&Constant(false), x) | (x, &Constant(false)) => Ok(x.clone()),
288 (&Constant(true), x) | (x, &Constant(true)) => Ok(x.not()),
289 // a XOR (NOT b) = NOT(a XOR b)
290 (is @ &Is(_), not @ &Not(_)) | (not @ &Not(_), is @ &Is(_)) => {
291 Ok(is.xor(¬.not())?.not())
292 }
293 // a XOR b = (NOT a) XOR (NOT b)
294 (&Is(ref a), &Is(ref b)) | (&Not(ref a), &Not(ref b)) => Ok(Is(a.xor(b)?)),
295 }
296 }
297
298 /// Perform OR over two boolean operands
299 pub fn or<'a>(&'a self, b: &'a Self) -> Result<Self, SynthesisError> {
300 use Boolean::*;
301 match (self, b) {
302 (&Constant(false), x) | (x, &Constant(false)) => Ok(x.clone()),
303 (&Constant(true), _) | (_, &Constant(true)) => Ok(Constant(true)),
304 // a OR b = NOT ((NOT a) AND b)
305 (a @ &Is(_), b @ &Not(_)) | (b @ &Not(_), a @ &Is(_)) | (b @ &Not(_), a @ &Not(_)) => {
306 Ok(a.not().and(&b.not())?.not())
307 }
308 (&Is(ref a), &Is(ref b)) => a.or(b).map(From::from),
309 }
310 }
311
312 /// Perform AND over two boolean operands
313 pub fn and<'a>(&'a self, b: &'a Self) -> Result<Self, SynthesisError> {
314 use Boolean::*;
315 match (self, b) {
316 // false AND x is always false
317 (&Constant(false), _) | (_, &Constant(false)) => Ok(Constant(false)),
318 // true AND x is always x
319 (&Constant(true), x) | (x, &Constant(true)) => Ok(x.clone()),
320 // a AND (NOT b)
321 (&Is(ref is), &Not(ref not)) | (&Not(ref not), &Is(ref is)) => Ok(Is(is.and_not(not)?)),
322 // (NOT a) AND (NOT b) = a NOR b
323 (&Not(ref a), &Not(ref b)) => Ok(Is(a.nor(b)?)),
324 // a AND b
325 (&Is(ref a), &Is(ref b)) => Ok(Is(a.and(b)?)),
326 }
327 }
328
329 pub fn kary_and(bits: &[Self]) -> Result<Self, SynthesisError> {
330 assert!(!bits.is_empty());
331 let mut cur: Option<Self> = None;
332 for next in bits {
333 cur = if let Some(b) = cur {
334 Some(b.and(next)?)
335 } else {
336 Some(next.clone())
337 };
338 }
339
340 Ok(cur.expect("should not be 0"))
341 }
342
343 pub fn kary_or(bits: &[Self]) -> Result<Self, SynthesisError> {
344 assert!(!bits.is_empty());
345 let mut cur: Option<Self> = None;
346 for next in bits {
347 cur = if let Some(b) = cur {
348 Some(b.or(next)?)
349 } else {
350 Some(next.clone())
351 };
352 }
353
354 Ok(cur.expect("should not be 0"))
355 }
356
357 pub fn kary_nand(bits: &[Self]) -> Result<Self, SynthesisError> {
358 Ok(Self::kary_and(bits)?.not())
359 }
360
361 /// Assert that at least one input is false.
362 fn enforce_kary_nand(bits: &[Self]) -> Result<(), SynthesisError> {
363 use Boolean::*;
364 let r = Self::kary_nand(bits)?;
365 match r {
366 Constant(true) => Ok(()),
367 Constant(false) => Err(SynthesisError::AssignmentMissing),
368 Is(_) | Not(_) => r.cs().unwrap().enforce_constraint(
369 r.lc(),
370 lc!() + Variable::One,
371 lc!() + Variable::One,
372 ),
373 }
374 }
375
376 /// Asserts that this bit_gadget representation is "in
377 /// the field" when interpreted in big endian.
378 pub fn enforce_in_field(bits: &[Self]) -> Result<(), SynthesisError> {
379 // b = char() - 1
380 let mut b = F::characteristic().to_vec();
381 assert_eq!(b[0] % 2, 1);
382 b[0] -= 1;
383 let run = Self::enforce_smaller_or_equal_than(bits, b)?;
384
385 // We should always end in a "run" of zeros, because
386 // the characteristic is an odd prime. So, this should
387 // be empty.
388 assert!(run.is_empty());
389
390 Ok(())
391 }
392
393 /// Asserts that this bit_gadget representation is smaller
394 /// or equal than the provided element
395 pub fn enforce_smaller_or_equal_than(
396 bits: &[Self],
397 element: impl AsRef<[u64]>,
398 ) -> Result<Vec<Self>, SynthesisError> {
399 let mut bits_iter = bits.iter();
400 let b: &[u64] = element.as_ref();
401
402 // Runs of ones in r
403 let mut last_run = Boolean::constant(true);
404 let mut current_run = vec![];
405
406 let mut found_one = false;
407
408 let char_num_bits = {
409 let mut leading_zeros = 0;
410 let mut total_bits = 0;
411 let mut found_one = false;
412 for b in BitIterator::new(b.clone()) {
413 total_bits += 1;
414 if !b && !found_one {
415 leading_zeros += 1
416 }
417 if b {
418 found_one = true;
419 }
420 }
421
422 total_bits - leading_zeros
423 };
424
425 if bits.len() > char_num_bits {
426 let num_extra_bits = bits.len() - char_num_bits;
427 let mut or_result = Boolean::constant(false);
428 for should_be_zero in &bits[0..num_extra_bits] {
429 or_result = or_result.or(should_be_zero)?;
430 let _ = bits_iter.next().unwrap();
431 }
432 or_result.enforce_equal(&Boolean::constant(false))?;
433 }
434
435 for b in BitIterator::new(b) {
436 // Skip over unset bits at the beginning
437 found_one |= b;
438 if !found_one {
439 continue;
440 }
441
442 let a = bits_iter.next().unwrap();
443
444 if b {
445 // This is part of a run of ones.
446 current_run.push(a.clone());
447 } else {
448 if !current_run.is_empty() {
449 // This is the start of a run of zeros, but we need
450 // to k-ary AND against `last_run` first.
451
452 current_run.push(last_run.clone());
453 last_run = Self::kary_and(¤t_run)?;
454 current_run.truncate(0);
455 }
456
457 // If `last_run` is true, `a` must be false, or it would
458 // not be in the field.
459 //
460 // If `last_run` is false, `a` can be true or false.
461 //
462 // Ergo, at least one of `last_run` and `a` must be false.
463 Self::enforce_kary_nand(&[last_run.clone(), a.clone()])?;
464 }
465 }
466 assert!(bits_iter.next().is_none());
467
468 Ok(current_run)
469 }
470
471 pub fn select<T: CondSelectGadget<F>>(
472 &self,
473 first: &T,
474 second: &T,
475 ) -> Result<T, SynthesisError> {
476 T::conditionally_select(&self, first, second)
477 }
478}
479
480impl<F: Field> From<AllocatedBit<F>> for Boolean<F> {
481 fn from(b: AllocatedBit<F>) -> Self {
482 Boolean::Is(b)
483 }
484}
485
486impl<F: Field> AllocVar<bool, F> for Boolean<F> {
487 fn new_variable<T: Borrow<bool>>(
488 cs: impl Into<Namespace<F>>,
489 f: impl FnOnce() -> Result<T, SynthesisError>,
490 mode: AllocationMode,
491 ) -> Result<Self, SynthesisError> {
492 if mode == AllocationMode::Constant {
493 Ok(Boolean::Constant(*f()?.borrow()))
494 } else {
495 AllocatedBit::new_variable(cs, f, mode).map(Boolean::from)
496 }
497 }
498}
499
500impl<F: Field> EqGadget<F> for Boolean<F> {
501 fn is_eq(&self, other: &Self) -> Result<Boolean<F>, SynthesisError> {
502 // self | other | XNOR(self, other) | self == other
503 // -----|-------|-------------------|--------------
504 // 0 | 0 | 1 | 1
505 // 0 | 1 | 0 | 0
506 // 1 | 0 | 0 | 0
507 // 1 | 1 | 1 | 1
508 Ok(self.xor(other)?.not())
509 }
510
511 fn conditional_enforce_equal(
512 &self,
513 other: &Self,
514 condition: &Boolean<F>,
515 ) -> Result<(), SynthesisError> {
516 use Boolean::*;
517 let one = Variable::One;
518 let difference = match (self, other) {
519 // 1 == 1; 0 == 0
520 (Constant(true), Constant(true)) | (Constant(false), Constant(false)) => return Ok(()),
521 // false != true
522 (Constant(_), Constant(_)) => return Err(SynthesisError::AssignmentMissing),
523 // 1 - a
524 (Constant(true), Is(a)) | (Is(a), Constant(true)) => lc!() + one - a.variable(),
525 // a - 0 = a
526 (Constant(false), Is(a)) | (Is(a), Constant(false)) => lc!() + a.variable(),
527 // 1 - !a = 1 - (1 - a) = a
528 (Constant(true), Not(a)) | (Not(a), Constant(true)) => lc!() + a.variable(),
529 // !a - 0 = !a = 1 - a
530 (Constant(false), Not(a)) | (Not(a), Constant(false)) => lc!() + one - a.variable(),
531 // b - a,
532 (Is(a), Is(b)) => lc!() + b.variable() - a.variable(),
533 // !b - a = (1 - b) - a
534 (Is(a), Not(b)) | (Not(b), Is(a)) => lc!() + one - b.variable() - a.variable(),
535 // !b - !a = (1 - b) - (1 - a) = a - b,
536 (Not(a), Not(b)) => lc!() + a.variable() - b.variable(),
537 };
538
539 if condition != &Constant(false) {
540 let cs = self.cs().or(other.cs()).or(condition.cs()).unwrap();
541 cs.enforce_constraint(lc!() + difference, condition.lc(), lc!())?;
542 }
543 Ok(())
544 }
545
546 fn conditional_enforce_not_equal(
547 &self,
548 other: &Self,
549 should_enforce: &Boolean<F>,
550 ) -> Result<(), SynthesisError> {
551 use Boolean::*;
552 let one = Variable::One;
553 let difference = match (self, other) {
554 // 1 != 0; 0 != 1
555 (Constant(true), Constant(false)) | (Constant(false), Constant(true)) => return Ok(()),
556 // false == false and true == true
557 (Constant(_), Constant(_)) => return Err(SynthesisError::AssignmentMissing),
558 // 1 - a
559 (Constant(true), Is(a)) | (Is(a), Constant(true)) => lc!() + one - a.variable(),
560 // a - 0 = a
561 (Constant(false), Is(a)) | (Is(a), Constant(false)) => lc!() + a.variable(),
562 // 1 - !a = 1 - (1 - a) = a
563 (Constant(true), Not(a)) | (Not(a), Constant(true)) => lc!() + a.variable(),
564 // !a - 0 = !a = 1 - a
565 (Constant(false), Not(a)) | (Not(a), Constant(false)) => lc!() + one - a.variable(),
566 // b - a,
567 (Is(a), Is(b)) => lc!() + b.variable() - a.variable(),
568 // !b - a = (1 - b) - a
569 (Is(a), Not(b)) | (Not(b), Is(a)) => lc!() + one - b.variable() - a.variable(),
570 // !b - !a = (1 - b) - (1 - a) = a - b,
571 (Not(a), Not(b)) => lc!() + a.variable() - b.variable(),
572 };
573
574 if should_enforce != &Constant(false) {
575 let cs = self
576 .cs()
577 .or(other.cs())
578 .or(should_enforce.cs())
579 .ok_or(SynthesisError::UnconstrainedVariable)?;
580 cs.enforce_constraint(difference, should_enforce.lc(), should_enforce.lc())?;
581 }
582 Ok(())
583 }
584}
585
586impl<F: Field> ToBytesGadget<F> for Boolean<F> {
587 /// Outputs `1u8` if `self` is true, and `0u8` otherwise.
588 fn to_bytes(&self) -> Result<Vec<UInt8<F>>, SynthesisError> {
589 let mut bits = vec![Boolean::constant(false); 7];
590 bits.push(self.clone());
591 bits.reverse();
592 let value = self.value().map(|val| val as u8).ok();
593 let byte = UInt8 { bits, value };
594 Ok(vec![byte])
595 }
596}
597
598impl<F: Field> CondSelectGadget<F> for Boolean<F> {
599 fn conditionally_select(
600 cond: &Boolean<F>,
601 true_val: &Self,
602 false_val: &Self,
603 ) -> Result<Self, SynthesisError> {
604 use Boolean::*;
605 match cond {
606 Constant(true) => Ok(true_val.clone()),
607 Constant(false) => Ok(false_val.clone()),
608 cond @ Not(_) => Self::conditionally_select(&cond.not(), false_val, true_val),
609 cond @ Is(_) => match (true_val, false_val) {
610 (x, &Constant(false)) => cond.and(x),
611 (&Constant(false), x) => cond.not().and(x),
612 (&Constant(true), x) => cond.or(x),
613 (x, &Constant(true)) => cond.not().or(x),
614 (a, b) => {
615 let cs = cond.cs().unwrap();
616 let result: Boolean<F> =
617 AllocatedBit::new_witness_without_booleanity_check(cs.clone(), || {
618 let cond = cond.value()?;
619 Ok(if cond { a.value()? } else { b.value()? })
620 })?
621 .into();
622 //
623 // a = self; b = other; c = cond;
624 //
625 // r = c * a + (1 - c) * b
626 // r = b + c * (a - b)
627 // c * (a - b) = r - b
628 //
629 // If a, b, cond are all boolean, so is r.
630 //
631 // self | other | cond | result
632 // -----|-------|----------------
633 // 0 | 0 | 1 | 0
634 // 0 | 1 | 1 | 0
635 // 1 | 0 | 1 | 1
636 // 1 | 1 | 1 | 1
637 // 0 | 0 | 0 | 0
638 // 0 | 1 | 0 | 1
639 // 1 | 0 | 0 | 0
640 // 1 | 1 | 0 | 1
641 cs.enforce_constraint(
642 cond.lc(),
643 lc!() + a.lc() - b.lc(),
644 lc!() + result.lc() - b.lc(),
645 )?;
646
647 Ok(result)
648 }
649 },
650 }
651 }
652}
653
654#[cfg(test)]
655mod test {
656 use super::{AllocatedBit, Boolean};
657 use crate::prelude::*;
658 use algebra::{bls12_381::Fr, BitIterator, Field, One, PrimeField, UniformRand, Zero};
659 use r1cs_core::{ConstraintSystem, Namespace, SynthesisError};
660 use rand::SeedableRng;
661 use rand_xorshift::XorShiftRng;
662
663 #[test]
664 fn test_boolean_to_byte() -> Result<(), SynthesisError> {
665 for val in [true, false].iter() {
666 let cs = ConstraintSystem::<Fr>::new_ref();
667 let a = Boolean::new_witness(cs.clone(), || Ok(*val))?;
668 let bytes = a.to_bytes()?;
669 assert_eq!(bytes.len(), 1);
670 let byte = &bytes[0];
671 assert_eq!(byte.value()?, *val as u8);
672
673 for (i, bit) in byte.bits.iter().enumerate() {
674 assert_eq!(bit.value()?, (byte.value()? >> i) & 1 == 1);
675 }
676 }
677 Ok(())
678 }
679
680 #[test]
681 fn test_xor() -> Result<(), SynthesisError> {
682 for a_val in [false, true].iter().copied() {
683 for b_val in [false, true].iter().copied() {
684 let cs = ConstraintSystem::<Fr>::new_ref();
685 let a = AllocatedBit::new_witness(cs.ns("a"), || Ok(a_val))?;
686 let b = AllocatedBit::new_witness(cs.ns("b"), || Ok(b_val))?;
687 let c = AllocatedBit::xor(&a, &b)?;
688 assert_eq!(c.value()?, a_val ^ b_val);
689
690 assert!(cs.is_satisfied().unwrap());
691 assert_eq!(a.value()?, (a_val));
692 assert_eq!(b.value()?, (b_val));
693 assert_eq!(c.value()?, (a_val ^ b_val));
694 }
695 }
696 Ok(())
697 }
698
699 #[test]
700 fn test_or() -> Result<(), SynthesisError> {
701 for a_val in [false, true].iter().copied() {
702 for b_val in [false, true].iter().copied() {
703 let cs = ConstraintSystem::<Fr>::new_ref();
704 let a = AllocatedBit::new_witness(cs.ns("a"), || Ok(a_val))?;
705 let b = AllocatedBit::new_witness(cs.ns("b"), || Ok(b_val))?;
706 let c = AllocatedBit::or(&a, &b)?;
707 assert_eq!(c.value()?, a_val | b_val);
708
709 assert!(cs.is_satisfied().unwrap());
710 assert_eq!(a.value()?, (a_val));
711 assert_eq!(b.value()?, (b_val));
712 assert_eq!(c.value()?, (a_val | b_val));
713 }
714 }
715 Ok(())
716 }
717
718 #[test]
719 fn test_and() -> Result<(), SynthesisError> {
720 for a_val in [false, true].iter().copied() {
721 for b_val in [false, true].iter().copied() {
722 let cs = ConstraintSystem::<Fr>::new_ref();
723 let a = AllocatedBit::new_witness(cs.ns("a"), || Ok(a_val))?;
724 let b = AllocatedBit::new_witness(cs.ns("b"), || Ok(b_val))?;
725 let c = AllocatedBit::and(&a, &b)?;
726 assert_eq!(c.value()?, a_val & b_val);
727
728 assert!(cs.is_satisfied().unwrap());
729 assert_eq!(a.value()?, (a_val));
730 assert_eq!(b.value()?, (b_val));
731 assert_eq!(c.value()?, (a_val & b_val));
732 }
733 }
734 Ok(())
735 }
736
737 #[test]
738 fn test_and_not() -> Result<(), SynthesisError> {
739 for a_val in [false, true].iter().copied() {
740 for b_val in [false, true].iter().copied() {
741 let cs = ConstraintSystem::<Fr>::new_ref();
742 let a = AllocatedBit::new_witness(cs.ns("a"), || Ok(a_val))?;
743 let b = AllocatedBit::new_witness(cs.ns("b"), || Ok(b_val))?;
744 let c = AllocatedBit::and_not(&a, &b)?;
745 assert_eq!(c.value()?, a_val & !b_val);
746
747 assert!(cs.is_satisfied().unwrap());
748 assert_eq!(a.value()?, (a_val));
749 assert_eq!(b.value()?, (b_val));
750 assert_eq!(c.value()?, (a_val & !b_val));
751 }
752 }
753 Ok(())
754 }
755
756 #[test]
757 fn test_nor() -> Result<(), SynthesisError> {
758 for a_val in [false, true].iter().copied() {
759 for b_val in [false, true].iter().copied() {
760 let cs = ConstraintSystem::<Fr>::new_ref();
761 let a = AllocatedBit::new_witness(cs.ns("a"), || Ok(a_val))?;
762 let b = AllocatedBit::new_witness(cs.ns("b"), || Ok(b_val))?;
763 let c = AllocatedBit::nor(&a, &b)?;
764 assert_eq!(c.value()?, !a_val & !b_val);
765
766 assert!(cs.is_satisfied().unwrap());
767 assert_eq!(a.value()?, (a_val));
768 assert_eq!(b.value()?, (b_val));
769 assert_eq!(c.value()?, (!a_val & !b_val));
770 }
771 }
772 Ok(())
773 }
774
775 #[test]
776 fn test_enforce_equal() -> Result<(), SynthesisError> {
777 for a_bool in [false, true].iter().cloned() {
778 for b_bool in [false, true].iter().cloned() {
779 for a_neg in [false, true].iter().cloned() {
780 for b_neg in [false, true].iter().cloned() {
781 let cs = ConstraintSystem::<Fr>::new_ref();
782
783 let mut a = Boolean::new_witness(cs.ns("a"), || Ok(a_bool))?;
784 let mut b = Boolean::new_witness(cs.ns("b"), || Ok(b_bool))?;
785
786 if a_neg {
787 a = a.not();
788 }
789 if b_neg {
790 b = b.not();
791 }
792
793 a.enforce_equal(&b)?;
794
795 assert_eq!(
796 cs.is_satisfied().unwrap(),
797 (a_bool ^ a_neg) == (b_bool ^ b_neg)
798 );
799 }
800 }
801 }
802 }
803 Ok(())
804 }
805
806 #[test]
807 fn test_conditional_enforce_equal() -> Result<(), SynthesisError> {
808 for a_bool in [false, true].iter().cloned() {
809 for b_bool in [false, true].iter().cloned() {
810 for a_neg in [false, true].iter().cloned() {
811 for b_neg in [false, true].iter().cloned() {
812 let cs = ConstraintSystem::<Fr>::new_ref();
813
814 // First test if constraint system is satisfied
815 // when we do want to enforce the condition.
816 let mut a = Boolean::new_witness(cs.clone(), || Ok(a_bool))?;
817 let mut b = Boolean::new_witness(cs.clone(), || Ok(b_bool))?;
818
819 if a_neg {
820 a = a.not();
821 }
822 if b_neg {
823 b = b.not();
824 }
825
826 a.conditional_enforce_equal(&b, &Boolean::constant(true))?;
827
828 assert_eq!(
829 cs.is_satisfied().unwrap(),
830 (a_bool ^ a_neg) == (b_bool ^ b_neg)
831 );
832
833 // Now test if constraint system is satisfied even
834 // when we don't want to enforce the condition.
835 let cs = ConstraintSystem::<Fr>::new_ref();
836
837 let mut a = Boolean::new_witness(cs.ns("a"), || Ok(a_bool))?;
838 let mut b = Boolean::new_witness(cs.ns("b"), || Ok(b_bool))?;
839
840 if a_neg {
841 a = a.not();
842 }
843 if b_neg {
844 b = b.not();
845 }
846
847 let false_cond = Boolean::new_witness(cs.ns("cond"), || Ok(false))?;
848 a.conditional_enforce_equal(&b, &false_cond)?;
849
850 assert!(cs.is_satisfied().unwrap());
851 }
852 }
853 }
854 }
855 Ok(())
856 }
857
858 #[test]
859 fn test_boolean_negation() -> Result<(), SynthesisError> {
860 let cs = ConstraintSystem::<Fr>::new_ref();
861
862 let mut b = Boolean::new_witness(cs.clone(), || Ok(true))?;
863 assert!(matches!(b, Boolean::Is(_)));
864
865 b = b.not();
866 assert!(matches!(b, Boolean::Not(_)));
867
868 b = b.not();
869 assert!(matches!(b, Boolean::Is(_)));
870
871 b = Boolean::Constant(true);
872 assert!(matches!(b, Boolean::Constant(true)));
873
874 b = b.not();
875 assert!(matches!(b, Boolean::Constant(false)));
876
877 b = b.not();
878 assert!(matches!(b, Boolean::Constant(true)));
879 Ok(())
880 }
881
882 #[derive(Eq, PartialEq, Copy, Clone, Debug)]
883 enum OpType {
884 True,
885 False,
886 AllocatedTrue,
887 AllocatedFalse,
888 NegatedAllocatedTrue,
889 NegatedAllocatedFalse,
890 }
891
892 const VARIANTS: [OpType; 6] = [
893 OpType::True,
894 OpType::False,
895 OpType::AllocatedTrue,
896 OpType::AllocatedFalse,
897 OpType::NegatedAllocatedTrue,
898 OpType::NegatedAllocatedFalse,
899 ];
900
901 fn construct<F: Field>(
902 cs: impl Into<Namespace<F>>,
903 operand: OpType,
904 name: &'static str,
905 ) -> Result<Boolean<F>, SynthesisError> {
906 let ns = cs.into();
907 let cs = ns.cs().ns(name);
908
909 let b = match operand {
910 OpType::True => Boolean::constant(true),
911 OpType::False => Boolean::constant(false),
912 OpType::AllocatedTrue => Boolean::new_witness(cs, || Ok(true))?,
913 OpType::AllocatedFalse => Boolean::new_witness(cs, || Ok(false))?,
914 OpType::NegatedAllocatedTrue => Boolean::new_witness(cs, || Ok(true))?.not(),
915 OpType::NegatedAllocatedFalse => Boolean::new_witness(cs, || Ok(false))?.not(),
916 };
917 Ok(b)
918 }
919
920 #[test]
921 fn test_boolean_xor() -> Result<(), SynthesisError> {
922 for first_operand in VARIANTS.iter().cloned() {
923 for second_operand in VARIANTS.iter().cloned() {
924 let cs = ConstraintSystem::<Fr>::new_ref();
925
926 let a = construct(cs.clone(), first_operand, "a")?;
927 let b = construct(cs.clone(), second_operand, "b")?;
928 let c = Boolean::xor(&a, &b)?;
929
930 assert!(cs.is_satisfied().unwrap());
931
932 match (first_operand, second_operand, c) {
933 (OpType::True, OpType::True, Boolean::Constant(false)) => (),
934 (OpType::True, OpType::False, Boolean::Constant(true)) => (),
935 (OpType::True, OpType::AllocatedTrue, Boolean::Not(_)) => (),
936 (OpType::True, OpType::AllocatedFalse, Boolean::Not(_)) => (),
937 (OpType::True, OpType::NegatedAllocatedTrue, Boolean::Is(_)) => (),
938 (OpType::True, OpType::NegatedAllocatedFalse, Boolean::Is(_)) => (),
939
940 (OpType::False, OpType::True, Boolean::Constant(true)) => (),
941 (OpType::False, OpType::False, Boolean::Constant(false)) => (),
942 (OpType::False, OpType::AllocatedTrue, Boolean::Is(_)) => (),
943 (OpType::False, OpType::AllocatedFalse, Boolean::Is(_)) => (),
944 (OpType::False, OpType::NegatedAllocatedTrue, Boolean::Not(_)) => (),
945 (OpType::False, OpType::NegatedAllocatedFalse, Boolean::Not(_)) => (),
946
947 (OpType::AllocatedTrue, OpType::True, Boolean::Not(_)) => (),
948 (OpType::AllocatedTrue, OpType::False, Boolean::Is(_)) => (),
949 (OpType::AllocatedTrue, OpType::AllocatedTrue, Boolean::Is(ref v)) => {
950 assert_eq!(v.value(), Ok(false));
951 }
952 (OpType::AllocatedTrue, OpType::AllocatedFalse, Boolean::Is(ref v)) => {
953 assert_eq!(v.value(), Ok(true));
954 }
955 (OpType::AllocatedTrue, OpType::NegatedAllocatedTrue, Boolean::Not(ref v)) => {
956 assert_eq!(v.value(), Ok(false));
957 }
958 (OpType::AllocatedTrue, OpType::NegatedAllocatedFalse, Boolean::Not(ref v)) => {
959 assert_eq!(v.value(), Ok(true));
960 }
961 (OpType::AllocatedFalse, OpType::True, Boolean::Not(_)) => (),
962 (OpType::AllocatedFalse, OpType::False, Boolean::Is(_)) => (),
963 (OpType::AllocatedFalse, OpType::AllocatedTrue, Boolean::Is(ref v)) => {
964 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::one());
965 assert_eq!(v.value(), Ok(true));
966 }
967 (OpType::AllocatedFalse, OpType::AllocatedFalse, Boolean::Is(ref v)) => {
968 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
969 assert_eq!(v.value(), Ok(false));
970 }
971 (OpType::AllocatedFalse, OpType::NegatedAllocatedTrue, Boolean::Not(ref v)) => {
972 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::one());
973 assert_eq!(v.value(), Ok(true));
974 }
975 (
976 OpType::AllocatedFalse,
977 OpType::NegatedAllocatedFalse,
978 Boolean::Not(ref v),
979 ) => {
980 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
981 assert_eq!(v.value(), Ok(false));
982 }
983
984 (OpType::NegatedAllocatedTrue, OpType::True, Boolean::Is(_)) => (),
985 (OpType::NegatedAllocatedTrue, OpType::False, Boolean::Not(_)) => (),
986 (OpType::NegatedAllocatedTrue, OpType::AllocatedTrue, Boolean::Not(ref v)) => {
987 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
988 assert_eq!(v.value(), Ok(false));
989 }
990 (OpType::NegatedAllocatedTrue, OpType::AllocatedFalse, Boolean::Not(ref v)) => {
991 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::one());
992 assert_eq!(v.value(), Ok(true));
993 }
994 (
995 OpType::NegatedAllocatedTrue,
996 OpType::NegatedAllocatedTrue,
997 Boolean::Is(ref v),
998 ) => {
999 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1000 assert_eq!(v.value(), Ok(false));
1001 }
1002 (
1003 OpType::NegatedAllocatedTrue,
1004 OpType::NegatedAllocatedFalse,
1005 Boolean::Is(ref v),
1006 ) => {
1007 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::one());
1008 assert_eq!(v.value(), Ok(true));
1009 }
1010
1011 (OpType::NegatedAllocatedFalse, OpType::True, Boolean::Is(_)) => (),
1012 (OpType::NegatedAllocatedFalse, OpType::False, Boolean::Not(_)) => (),
1013 (OpType::NegatedAllocatedFalse, OpType::AllocatedTrue, Boolean::Not(ref v)) => {
1014 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::one());
1015 assert_eq!(v.value(), Ok(true));
1016 }
1017 (
1018 OpType::NegatedAllocatedFalse,
1019 OpType::AllocatedFalse,
1020 Boolean::Not(ref v),
1021 ) => {
1022 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1023 assert_eq!(v.value(), Ok(false));
1024 }
1025 (
1026 OpType::NegatedAllocatedFalse,
1027 OpType::NegatedAllocatedTrue,
1028 Boolean::Is(ref v),
1029 ) => {
1030 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::one());
1031 assert_eq!(v.value(), Ok(true));
1032 }
1033 (
1034 OpType::NegatedAllocatedFalse,
1035 OpType::NegatedAllocatedFalse,
1036 Boolean::Is(ref v),
1037 ) => {
1038 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1039 assert_eq!(v.value(), Ok(false));
1040 }
1041
1042 _ => unreachable!(),
1043 }
1044 }
1045 }
1046 Ok(())
1047 }
1048
1049 #[test]
1050 fn test_boolean_cond_select() -> Result<(), SynthesisError> {
1051 for condition in VARIANTS.iter().cloned() {
1052 for first_operand in VARIANTS.iter().cloned() {
1053 for second_operand in VARIANTS.iter().cloned() {
1054 let cs = ConstraintSystem::<Fr>::new_ref();
1055
1056 let cond = construct(cs.clone(), condition, "cond")?;
1057 let a = construct(cs.clone(), first_operand, "a")?;
1058 let b = construct(cs.clone(), second_operand, "b")?;
1059 let c = cond.select(&a, &b)?;
1060
1061 assert!(
1062 cs.is_satisfied().unwrap(),
1063 "failed with operands: cond: {:?}, a: {:?}, b: {:?}",
1064 condition,
1065 first_operand,
1066 second_operand,
1067 );
1068 assert_eq!(
1069 c.value()?,
1070 if cond.value()? {
1071 a.value()?
1072 } else {
1073 b.value()?
1074 }
1075 );
1076 }
1077 }
1078 }
1079 Ok(())
1080 }
1081
1082 #[test]
1083 fn test_boolean_or() -> Result<(), SynthesisError> {
1084 for first_operand in VARIANTS.iter().cloned() {
1085 for second_operand in VARIANTS.iter().cloned() {
1086 let cs = ConstraintSystem::<Fr>::new_ref();
1087
1088 let a = construct(cs.clone(), first_operand, "a")?;
1089 let b = construct(cs.clone(), second_operand, "b")?;
1090 let c = a.or(&b)?;
1091
1092 assert!(cs.is_satisfied().unwrap());
1093
1094 match (first_operand, second_operand, c.clone()) {
1095 (OpType::True, OpType::True, Boolean::Constant(true)) => (),
1096 (OpType::True, OpType::False, Boolean::Constant(true)) => (),
1097 (OpType::True, OpType::AllocatedTrue, Boolean::Constant(true)) => (),
1098 (OpType::True, OpType::AllocatedFalse, Boolean::Constant(true)) => (),
1099 (OpType::True, OpType::NegatedAllocatedTrue, Boolean::Constant(true)) => (),
1100 (OpType::True, OpType::NegatedAllocatedFalse, Boolean::Constant(true)) => (),
1101
1102 (OpType::False, OpType::True, Boolean::Constant(true)) => (),
1103 (OpType::False, OpType::False, Boolean::Constant(false)) => (),
1104 (OpType::False, OpType::AllocatedTrue, Boolean::Is(_)) => (),
1105 (OpType::False, OpType::AllocatedFalse, Boolean::Is(_)) => (),
1106 (OpType::False, OpType::NegatedAllocatedTrue, Boolean::Not(_)) => (),
1107 (OpType::False, OpType::NegatedAllocatedFalse, Boolean::Not(_)) => (),
1108
1109 (OpType::AllocatedTrue, OpType::True, Boolean::Constant(true)) => (),
1110 (OpType::AllocatedTrue, OpType::False, Boolean::Is(_)) => (),
1111 (OpType::AllocatedTrue, OpType::AllocatedTrue, Boolean::Is(ref v)) => {
1112 assert_eq!(v.value(), Ok(true));
1113 }
1114 (OpType::AllocatedTrue, OpType::AllocatedFalse, Boolean::Is(ref v)) => {
1115 assert_eq!(v.value(), Ok(true));
1116 }
1117 (OpType::AllocatedTrue, OpType::NegatedAllocatedTrue, Boolean::Not(ref v)) => {
1118 assert_eq!(v.value(), Ok(false));
1119 }
1120 (OpType::AllocatedTrue, OpType::NegatedAllocatedFalse, Boolean::Not(ref v)) => {
1121 assert_eq!(v.value(), Ok(false));
1122 }
1123
1124 (OpType::AllocatedFalse, OpType::True, Boolean::Constant(true)) => (),
1125 (OpType::AllocatedFalse, OpType::False, Boolean::Is(_)) => (),
1126 (OpType::AllocatedFalse, OpType::AllocatedTrue, Boolean::Is(ref v)) => {
1127 assert_eq!(v.value(), Ok(true));
1128 }
1129 (OpType::AllocatedFalse, OpType::AllocatedFalse, Boolean::Is(ref v)) => {
1130 assert_eq!(v.value(), Ok(false));
1131 }
1132 (OpType::AllocatedFalse, OpType::NegatedAllocatedTrue, Boolean::Not(ref v)) => {
1133 assert_eq!(v.value(), Ok(true));
1134 }
1135 (
1136 OpType::AllocatedFalse,
1137 OpType::NegatedAllocatedFalse,
1138 Boolean::Not(ref v),
1139 ) => {
1140 assert_eq!(v.value(), Ok(false));
1141 }
1142
1143 (OpType::NegatedAllocatedTrue, OpType::True, Boolean::Constant(true)) => (),
1144 (OpType::NegatedAllocatedTrue, OpType::False, Boolean::Not(_)) => (),
1145 (OpType::NegatedAllocatedTrue, OpType::AllocatedTrue, Boolean::Not(ref v)) => {
1146 assert_eq!(v.value(), Ok(false));
1147 }
1148 (OpType::NegatedAllocatedTrue, OpType::AllocatedFalse, Boolean::Not(ref v)) => {
1149 assert_eq!(v.value(), Ok(true));
1150 }
1151 (
1152 OpType::NegatedAllocatedTrue,
1153 OpType::NegatedAllocatedTrue,
1154 Boolean::Not(ref v),
1155 ) => {
1156 assert_eq!(v.value(), Ok(true));
1157 }
1158 (
1159 OpType::NegatedAllocatedTrue,
1160 OpType::NegatedAllocatedFalse,
1161 Boolean::Not(ref v),
1162 ) => {
1163 assert_eq!(v.value(), Ok(false));
1164 }
1165
1166 (OpType::NegatedAllocatedFalse, OpType::True, Boolean::Constant(true)) => (),
1167 (OpType::NegatedAllocatedFalse, OpType::False, Boolean::Not(_)) => (),
1168 (OpType::NegatedAllocatedFalse, OpType::AllocatedTrue, Boolean::Not(ref v)) => {
1169 assert_eq!(v.value(), Ok(false));
1170 }
1171 (
1172 OpType::NegatedAllocatedFalse,
1173 OpType::AllocatedFalse,
1174 Boolean::Not(ref v),
1175 ) => {
1176 assert_eq!(v.value(), Ok(false));
1177 }
1178 (
1179 OpType::NegatedAllocatedFalse,
1180 OpType::NegatedAllocatedTrue,
1181 Boolean::Not(ref v),
1182 ) => {
1183 assert_eq!(v.value(), Ok(false));
1184 }
1185 (
1186 OpType::NegatedAllocatedFalse,
1187 OpType::NegatedAllocatedFalse,
1188 Boolean::Not(ref v),
1189 ) => {
1190 assert_eq!(v.value(), Ok(false));
1191 }
1192
1193 _ => panic!(
1194 "this should never be encountered, in case: (a = {:?}, b = {:?}, c = {:?})",
1195 a, b, c
1196 ),
1197 }
1198 }
1199 }
1200 Ok(())
1201 }
1202
1203 #[test]
1204 fn test_boolean_and() -> Result<(), SynthesisError> {
1205 for first_operand in VARIANTS.iter().cloned() {
1206 for second_operand in VARIANTS.iter().cloned() {
1207 let cs = ConstraintSystem::<Fr>::new_ref();
1208
1209 let a = construct(cs.clone(), first_operand, "a")?;
1210 let b = construct(cs.clone(), second_operand, "b")?;
1211 let c = a.and(&b)?;
1212
1213 assert!(cs.is_satisfied().unwrap());
1214
1215 match (first_operand, second_operand, c) {
1216 (OpType::True, OpType::True, Boolean::Constant(true)) => (),
1217 (OpType::True, OpType::False, Boolean::Constant(false)) => (),
1218 (OpType::True, OpType::AllocatedTrue, Boolean::Is(_)) => (),
1219 (OpType::True, OpType::AllocatedFalse, Boolean::Is(_)) => (),
1220 (OpType::True, OpType::NegatedAllocatedTrue, Boolean::Not(_)) => (),
1221 (OpType::True, OpType::NegatedAllocatedFalse, Boolean::Not(_)) => (),
1222
1223 (OpType::False, OpType::True, Boolean::Constant(false)) => (),
1224 (OpType::False, OpType::False, Boolean::Constant(false)) => (),
1225 (OpType::False, OpType::AllocatedTrue, Boolean::Constant(false)) => (),
1226 (OpType::False, OpType::AllocatedFalse, Boolean::Constant(false)) => (),
1227 (OpType::False, OpType::NegatedAllocatedTrue, Boolean::Constant(false)) => (),
1228 (OpType::False, OpType::NegatedAllocatedFalse, Boolean::Constant(false)) => (),
1229
1230 (OpType::AllocatedTrue, OpType::True, Boolean::Is(_)) => (),
1231 (OpType::AllocatedTrue, OpType::False, Boolean::Constant(false)) => (),
1232 (OpType::AllocatedTrue, OpType::AllocatedTrue, Boolean::Is(ref v)) => {
1233 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::one());
1234 assert_eq!(v.value(), Ok(true));
1235 }
1236 (OpType::AllocatedTrue, OpType::AllocatedFalse, Boolean::Is(ref v)) => {
1237 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1238 assert_eq!(v.value(), Ok(false));
1239 }
1240 (OpType::AllocatedTrue, OpType::NegatedAllocatedTrue, Boolean::Is(ref v)) => {
1241 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1242 assert_eq!(v.value(), Ok(false));
1243 }
1244 (OpType::AllocatedTrue, OpType::NegatedAllocatedFalse, Boolean::Is(ref v)) => {
1245 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::one());
1246 assert_eq!(v.value(), Ok(true));
1247 }
1248
1249 (OpType::AllocatedFalse, OpType::True, Boolean::Is(_)) => (),
1250 (OpType::AllocatedFalse, OpType::False, Boolean::Constant(false)) => (),
1251 (OpType::AllocatedFalse, OpType::AllocatedTrue, Boolean::Is(ref v)) => {
1252 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1253 assert_eq!(v.value(), Ok(false));
1254 }
1255 (OpType::AllocatedFalse, OpType::AllocatedFalse, Boolean::Is(ref v)) => {
1256 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1257 assert_eq!(v.value(), Ok(false));
1258 }
1259 (OpType::AllocatedFalse, OpType::NegatedAllocatedTrue, Boolean::Is(ref v)) => {
1260 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1261 assert_eq!(v.value(), Ok(false));
1262 }
1263 (OpType::AllocatedFalse, OpType::NegatedAllocatedFalse, Boolean::Is(ref v)) => {
1264 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1265 assert_eq!(v.value(), Ok(false));
1266 }
1267
1268 (OpType::NegatedAllocatedTrue, OpType::True, Boolean::Not(_)) => (),
1269 (OpType::NegatedAllocatedTrue, OpType::False, Boolean::Constant(false)) => (),
1270 (OpType::NegatedAllocatedTrue, OpType::AllocatedTrue, Boolean::Is(ref v)) => {
1271 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1272 assert_eq!(v.value(), Ok(false));
1273 }
1274 (OpType::NegatedAllocatedTrue, OpType::AllocatedFalse, Boolean::Is(ref v)) => {
1275 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1276 assert_eq!(v.value(), Ok(false));
1277 }
1278 (
1279 OpType::NegatedAllocatedTrue,
1280 OpType::NegatedAllocatedTrue,
1281 Boolean::Is(ref v),
1282 ) => {
1283 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1284 assert_eq!(v.value(), Ok(false));
1285 }
1286 (
1287 OpType::NegatedAllocatedTrue,
1288 OpType::NegatedAllocatedFalse,
1289 Boolean::Is(ref v),
1290 ) => {
1291 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1292 assert_eq!(v.value(), Ok(false));
1293 }
1294
1295 (OpType::NegatedAllocatedFalse, OpType::True, Boolean::Not(_)) => (),
1296 (OpType::NegatedAllocatedFalse, OpType::False, Boolean::Constant(false)) => (),
1297 (OpType::NegatedAllocatedFalse, OpType::AllocatedTrue, Boolean::Is(ref v)) => {
1298 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::one());
1299 assert_eq!(v.value(), Ok(true));
1300 }
1301 (OpType::NegatedAllocatedFalse, OpType::AllocatedFalse, Boolean::Is(ref v)) => {
1302 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1303 assert_eq!(v.value(), Ok(false));
1304 }
1305 (
1306 OpType::NegatedAllocatedFalse,
1307 OpType::NegatedAllocatedTrue,
1308 Boolean::Is(ref v),
1309 ) => {
1310 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1311 assert_eq!(v.value(), Ok(false));
1312 }
1313 (
1314 OpType::NegatedAllocatedFalse,
1315 OpType::NegatedAllocatedFalse,
1316 Boolean::Is(ref v),
1317 ) => {
1318 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::one());
1319 assert_eq!(v.value(), Ok(true));
1320 }
1321
1322 _ => {
1323 panic!(
1324 "unexpected behavior at {:?} AND {:?}",
1325 first_operand, second_operand
1326 );
1327 }
1328 }
1329 }
1330 }
1331 Ok(())
1332 }
1333
1334 #[test]
1335 fn test_enforce_in_field() -> Result<(), SynthesisError> {
1336 {
1337 let cs = ConstraintSystem::<Fr>::new_ref();
1338
1339 let mut bits = vec![];
1340 for b in BitIterator::new(Fr::characteristic()).skip(1) {
1341 bits.push(Boolean::new_witness(cs.clone(), || Ok(b))?);
1342 }
1343
1344 Boolean::enforce_in_field(&bits)?;
1345
1346 assert!(!cs.is_satisfied().unwrap());
1347 }
1348
1349 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
1350
1351 for _ in 0..1000 {
1352 let r = Fr::rand(&mut rng);
1353 let cs = ConstraintSystem::<Fr>::new_ref();
1354
1355 let mut bits = vec![];
1356 for b in BitIterator::new(r.into_repr()).skip(1) {
1357 bits.push(Boolean::new_witness(cs.clone(), || Ok(b))?);
1358 }
1359
1360 Boolean::enforce_in_field(&bits)?;
1361
1362 assert!(cs.is_satisfied().unwrap());
1363 }
1364 Ok(())
1365 }
1366
1367 #[test]
1368 fn test_enforce_nand() -> Result<(), SynthesisError> {
1369 {
1370 let cs = ConstraintSystem::<Fr>::new_ref();
1371
1372 assert!(
1373 Boolean::enforce_kary_nand(&[Boolean::new_constant(cs.clone(), false)?]).is_ok()
1374 );
1375 assert!(
1376 Boolean::enforce_kary_nand(&[Boolean::new_constant(cs.clone(), true)?]).is_err()
1377 );
1378 }
1379
1380 for i in 1..5 {
1381 // with every possible assignment for them
1382 for mut b in 0..(1 << i) {
1383 // with every possible negation
1384 for mut n in 0..(1 << i) {
1385 let cs = ConstraintSystem::<Fr>::new_ref();
1386
1387 let mut expected = true;
1388
1389 let mut bits = vec![];
1390 for _ in 0..i {
1391 expected &= b & 1 == 1;
1392
1393 let bit = if n & 1 == 1 {
1394 Boolean::new_witness(cs.clone(), || Ok(b & 1 == 1))?
1395 } else {
1396 Boolean::new_witness(cs.clone(), || Ok(b & 1 == 0))?.not()
1397 };
1398 bits.push(bit);
1399
1400 b >>= 1;
1401 n >>= 1;
1402 }
1403
1404 let expected = !expected;
1405
1406 Boolean::enforce_kary_nand(&bits)?;
1407
1408 if expected {
1409 assert!(cs.is_satisfied().unwrap());
1410 } else {
1411 assert!(!cs.is_satisfied().unwrap());
1412 }
1413 }
1414 }
1415 }
1416 Ok(())
1417 }
1418
1419 #[test]
1420 fn test_kary_and() -> Result<(), SynthesisError> {
1421 // test different numbers of operands
1422 for i in 1..15 {
1423 // with every possible assignment for them
1424 for mut b in 0..(1 << i) {
1425 let cs = ConstraintSystem::<Fr>::new_ref();
1426
1427 let mut expected = true;
1428
1429 let mut bits = vec![];
1430 for _ in 0..i {
1431 expected &= b & 1 == 1;
1432 bits.push(Boolean::new_witness(cs.clone(), || Ok(b & 1 == 1))?);
1433 b >>= 1;
1434 }
1435
1436 let r = Boolean::kary_and(&bits)?;
1437
1438 assert!(cs.is_satisfied().unwrap());
1439
1440 if let Boolean::Is(ref r) = r {
1441 assert_eq!(r.value()?, expected);
1442 }
1443 }
1444 }
1445 Ok(())
1446 }
1447}