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