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) -> Option<ConstraintSystemRef<F>> {
236 match self {
237 Self::Is(a) | Self::Not(a) => Some(a.cs.clone()),
238 _ => 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(_) => r.cs().unwrap().enforce_constraint(
602 r.lc(),
603 lc!() + Variable::One,
604 lc!() + Variable::One,
605 ),
606 }
607 }
608
609 /// Enforces that `bits`, when interpreted as a integer, is less than `F::characteristic()`,
610 /// That is, interpret bits as a little-endian integer, and enforce that this integer
611 /// is "in the field Z_p", where `p = F::characteristic()` .
612 #[tracing::instrument(target = "r1cs")]
613 pub fn enforce_in_field_le(bits: &[Self]) -> Result<(), SynthesisError> {
614 // `bits` < F::characteristic() <==> `bits` <= F::characteristic() -1
615 let mut b = F::characteristic().to_vec();
616 assert_eq!(b[0] % 2, 1);
617 b[0] -= 1; // This works, because the LSB is one, so there's no borrows.
618 let run = Self::enforce_smaller_or_equal_than_le(bits, b)?;
619
620 // We should always end in a "run" of zeros, because
621 // the characteristic is an odd prime. So, this should
622 // be empty.
623 assert!(run.is_empty());
624
625 Ok(())
626 }
627
628 /// Enforces that `bits` is less than or equal to `element`,
629 /// when both are interpreted as (little-endian) integers.
630 #[tracing::instrument(target = "r1cs", skip(element))]
631 pub fn enforce_smaller_or_equal_than_le<'a>(
632 bits: &[Self],
633 element: impl AsRef<[u64]>,
634 ) -> Result<Vec<Self>, SynthesisError> {
635 let b: &[u64] = element.as_ref();
636
637 let mut bits_iter = bits.iter().rev(); // Iterate in big-endian
638
639 // Runs of ones in r
640 let mut last_run = Boolean::constant(true);
641 let mut current_run = vec![];
642
643 let mut element_num_bits = 0;
644 for _ in BitIteratorBE::without_leading_zeros(b) {
645 element_num_bits += 1;
646 }
647
648 if bits.len() > element_num_bits {
649 let mut or_result = Boolean::constant(false);
650 for should_be_zero in &bits[element_num_bits..] {
651 or_result = or_result.or(should_be_zero)?;
652 let _ = bits_iter.next().unwrap();
653 }
654 or_result.enforce_equal(&Boolean::constant(false))?;
655 }
656
657 for (b, a) in BitIteratorBE::without_leading_zeros(b).zip(bits_iter.by_ref()) {
658 if b {
659 // This is part of a run of ones.
660 current_run.push(a.clone());
661 } else {
662 if !current_run.is_empty() {
663 // This is the start of a run of zeros, but we need
664 // to k-ary AND against `last_run` first.
665
666 current_run.push(last_run.clone());
667 last_run = Self::kary_and(¤t_run)?;
668 current_run.truncate(0);
669 }
670
671 // If `last_run` is true, `a` must be false, or it would
672 // not be in the field.
673 //
674 // If `last_run` is false, `a` can be true or false.
675 //
676 // Ergo, at least one of `last_run` and `a` must be false.
677 Self::enforce_kary_nand(&[last_run.clone(), a.clone()])?;
678 }
679 }
680 assert!(bits_iter.next().is_none());
681
682 Ok(current_run)
683 }
684
685 /// Conditionally selects one of `first` and `second` based on the value of `self`:
686 ///
687 /// If `self.is_eq(&Boolean::TRUE)`, this outputs `first`; else, it outputs `second`.
688 /// ```
689 /// # fn main() -> Result<(), r1cs_core::SynthesisError> {
690 /// // We'll use the BLS12-381 scalar field for our constraints.
691 /// use algebra::bls12_381::Fr;
692 /// use r1cs_core::*;
693 /// use r1cs_std::prelude::*;
694 ///
695 /// let cs = ConstraintSystem::<Fr>::new_ref();
696 ///
697 /// let a = Boolean::new_witness(cs.clone(), || Ok(true))?;
698 /// let b = Boolean::new_witness(cs.clone(), || Ok(false))?;
699 ///
700 /// let cond = Boolean::new_witness(cs.clone(), || Ok(true))?;
701 ///
702 /// cond.select(&a, &b)?.enforce_equal(&Boolean::TRUE)?;
703 /// cond.select(&b, &a)?.enforce_equal(&Boolean::FALSE)?;
704 ///
705 /// assert!(cs.is_satisfied().unwrap());
706 /// # Ok(())
707 /// # }
708 /// ```
709 #[tracing::instrument(target = "r1cs", skip(first, second))]
710 pub fn select<T: CondSelectGadget<F>>(
711 &self,
712 first: &T,
713 second: &T,
714 ) -> Result<T, SynthesisError> {
715 T::conditionally_select(&self, first, second)
716 }
717}
718
719impl<F: Field> From<AllocatedBit<F>> for Boolean<F> {
720 fn from(b: AllocatedBit<F>) -> Self {
721 Boolean::Is(b)
722 }
723}
724
725impl<F: Field> AllocVar<bool, F> for Boolean<F> {
726 fn new_variable<T: Borrow<bool>>(
727 cs: impl Into<Namespace<F>>,
728 f: impl FnOnce() -> Result<T, SynthesisError>,
729 mode: AllocationMode,
730 ) -> Result<Self, SynthesisError> {
731 if mode == AllocationMode::Constant {
732 Ok(Boolean::Constant(*f()?.borrow()))
733 } else {
734 AllocatedBit::new_variable(cs, f, mode).map(Boolean::from)
735 }
736 }
737}
738
739impl<F: Field> EqGadget<F> for Boolean<F> {
740 #[tracing::instrument(target = "r1cs")]
741 fn is_eq(&self, other: &Self) -> Result<Boolean<F>, SynthesisError> {
742 // self | other | XNOR(self, other) | self == other
743 // -----|-------|-------------------|--------------
744 // 0 | 0 | 1 | 1
745 // 0 | 1 | 0 | 0
746 // 1 | 0 | 0 | 0
747 // 1 | 1 | 1 | 1
748 Ok(self.xor(other)?.not())
749 }
750
751 #[tracing::instrument(target = "r1cs")]
752 fn conditional_enforce_equal(
753 &self,
754 other: &Self,
755 condition: &Boolean<F>,
756 ) -> Result<(), SynthesisError> {
757 use Boolean::*;
758 let one = Variable::One;
759 let difference = match (self, other) {
760 // 1 == 1; 0 == 0
761 (Constant(true), Constant(true)) | (Constant(false), Constant(false)) => return Ok(()),
762 // false != true
763 (Constant(_), Constant(_)) => return Err(SynthesisError::AssignmentMissing),
764 // 1 - a
765 (Constant(true), Is(a)) | (Is(a), Constant(true)) => lc!() + one - a.variable(),
766 // a - 0 = a
767 (Constant(false), Is(a)) | (Is(a), Constant(false)) => lc!() + a.variable(),
768 // 1 - !a = 1 - (1 - a) = a
769 (Constant(true), Not(a)) | (Not(a), Constant(true)) => lc!() + a.variable(),
770 // !a - 0 = !a = 1 - a
771 (Constant(false), Not(a)) | (Not(a), Constant(false)) => lc!() + one - a.variable(),
772 // b - a,
773 (Is(a), Is(b)) => lc!() + b.variable() - a.variable(),
774 // !b - a = (1 - b) - a
775 (Is(a), Not(b)) | (Not(b), Is(a)) => lc!() + one - b.variable() - a.variable(),
776 // !b - !a = (1 - b) - (1 - a) = a - b,
777 (Not(a), Not(b)) => lc!() + a.variable() - b.variable(),
778 };
779
780 if condition != &Constant(false) {
781 let cs = self.cs().or(other.cs()).or(condition.cs()).unwrap();
782 cs.enforce_constraint(lc!() + difference, condition.lc(), lc!())?;
783 }
784 Ok(())
785 }
786
787 #[tracing::instrument(target = "r1cs")]
788 fn conditional_enforce_not_equal(
789 &self,
790 other: &Self,
791 should_enforce: &Boolean<F>,
792 ) -> Result<(), SynthesisError> {
793 use Boolean::*;
794 let one = Variable::One;
795 let difference = match (self, other) {
796 // 1 != 0; 0 != 1
797 (Constant(true), Constant(false)) | (Constant(false), Constant(true)) => return Ok(()),
798 // false == false and true == true
799 (Constant(_), Constant(_)) => return Err(SynthesisError::AssignmentMissing),
800 // 1 - a
801 (Constant(true), Is(a)) | (Is(a), Constant(true)) => lc!() + one - a.variable(),
802 // a - 0 = a
803 (Constant(false), Is(a)) | (Is(a), Constant(false)) => lc!() + a.variable(),
804 // 1 - !a = 1 - (1 - a) = a
805 (Constant(true), Not(a)) | (Not(a), Constant(true)) => lc!() + a.variable(),
806 // !a - 0 = !a = 1 - a
807 (Constant(false), Not(a)) | (Not(a), Constant(false)) => lc!() + one - a.variable(),
808 // b - a,
809 (Is(a), Is(b)) => lc!() + b.variable() - a.variable(),
810 // !b - a = (1 - b) - a
811 (Is(a), Not(b)) | (Not(b), Is(a)) => lc!() + one - b.variable() - a.variable(),
812 // !b - !a = (1 - b) - (1 - a) = a - b,
813 (Not(a), Not(b)) => lc!() + a.variable() - b.variable(),
814 };
815
816 if should_enforce != &Constant(false) {
817 let cs = self
818 .cs()
819 .or(other.cs())
820 .or(should_enforce.cs())
821 .ok_or(SynthesisError::UnconstrainedVariable)?;
822 cs.enforce_constraint(difference, should_enforce.lc(), should_enforce.lc())?;
823 }
824 Ok(())
825 }
826}
827
828impl<F: Field> ToBytesGadget<F> for Boolean<F> {
829 /// Outputs `1u8` if `self` is true, and `0u8` otherwise.
830 #[tracing::instrument(target = "r1cs")]
831 fn to_bytes(&self) -> Result<Vec<UInt8<F>>, SynthesisError> {
832 let mut bits = vec![self.clone()];
833 bits.extend(vec![Boolean::constant(false); 7]);
834 let value = self.value().map(u8::from).ok();
835 let byte = UInt8 { bits, value };
836 Ok(vec![byte])
837 }
838}
839
840impl<F: PrimeField> ToConstraintFieldGadget<F> for Boolean<F> {
841 #[tracing::instrument(target = "r1cs")]
842 fn to_constraint_field(&self) -> Result<Vec<FpVar<F>>, SynthesisError> {
843 let var = From::from(self.clone());
844 Ok(vec![var])
845 }
846}
847
848impl<F: Field> CondSelectGadget<F> for Boolean<F> {
849 #[tracing::instrument(target = "r1cs")]
850 fn conditionally_select(
851 cond: &Boolean<F>,
852 true_val: &Self,
853 false_val: &Self,
854 ) -> Result<Self, SynthesisError> {
855 use Boolean::*;
856 match cond {
857 Constant(true) => Ok(true_val.clone()),
858 Constant(false) => Ok(false_val.clone()),
859 cond @ Not(_) => Self::conditionally_select(&cond.not(), false_val, true_val),
860 cond @ Is(_) => match (true_val, false_val) {
861 (x, &Constant(false)) => cond.and(x),
862 (&Constant(false), x) => cond.not().and(x),
863 (&Constant(true), x) => cond.or(x),
864 (x, &Constant(true)) => cond.not().or(x),
865 (a, b) => {
866 let cs = cond.cs().unwrap();
867 let result: Boolean<F> =
868 AllocatedBit::new_witness_without_booleanity_check(cs.clone(), || {
869 let cond = cond.value()?;
870 Ok(if cond { a.value()? } else { b.value()? })
871 })?
872 .into();
873 //
874 // a = self; b = other; c = cond;
875 //
876 // r = c * a + (1 - c) * b
877 // r = b + c * (a - b)
878 // c * (a - b) = r - b
879 //
880 // If a, b, cond are all boolean, so is r.
881 //
882 // self | other | cond | result
883 // -----|-------|----------------
884 // 0 | 0 | 1 | 0
885 // 0 | 1 | 1 | 0
886 // 1 | 0 | 1 | 1
887 // 1 | 1 | 1 | 1
888 // 0 | 0 | 0 | 0
889 // 0 | 1 | 0 | 1
890 // 1 | 0 | 0 | 0
891 // 1 | 1 | 0 | 1
892 cs.enforce_constraint(
893 cond.lc(),
894 lc!() + a.lc() - b.lc(),
895 lc!() + result.lc() - b.lc(),
896 )?;
897
898 Ok(result)
899 }
900 },
901 }
902 }
903}
904
905#[cfg(test)]
906mod test {
907 use super::{AllocatedBit, Boolean};
908 use crate::prelude::*;
909 use algebra::{
910 bls12_381::Fr, BitIteratorBE, BitIteratorLE, Field, One, PrimeField, UniformRand, Zero,
911 };
912 use r1cs_core::{ConstraintSystem, Namespace, SynthesisError};
913 use rand::SeedableRng;
914 use rand_xorshift::XorShiftRng;
915
916 #[test]
917 fn test_boolean_to_byte() -> Result<(), SynthesisError> {
918 for val in [true, false].iter() {
919 let cs = ConstraintSystem::<Fr>::new_ref();
920 let a = Boolean::new_witness(cs.clone(), || Ok(*val))?;
921 let bytes = a.to_bytes()?;
922 assert_eq!(bytes.len(), 1);
923 let byte = &bytes[0];
924 assert_eq!(byte.value()?, *val as u8);
925
926 for (i, bit) in byte.bits.iter().enumerate() {
927 assert_eq!(bit.value()?, (byte.value()? >> i) & 1 == 1);
928 }
929 }
930 Ok(())
931 }
932
933 #[test]
934 fn test_xor() -> Result<(), SynthesisError> {
935 for a_val in [false, true].iter().copied() {
936 for b_val in [false, true].iter().copied() {
937 let cs = ConstraintSystem::<Fr>::new_ref();
938 let a = AllocatedBit::new_witness(cs.clone(), || Ok(a_val))?;
939 let b = AllocatedBit::new_witness(cs.clone(), || Ok(b_val))?;
940 let c = AllocatedBit::xor(&a, &b)?;
941 assert_eq!(c.value()?, a_val ^ b_val);
942
943 assert!(cs.is_satisfied().unwrap());
944 assert_eq!(a.value()?, (a_val));
945 assert_eq!(b.value()?, (b_val));
946 assert_eq!(c.value()?, (a_val ^ b_val));
947 }
948 }
949 Ok(())
950 }
951
952 #[test]
953 fn test_or() -> Result<(), SynthesisError> {
954 for a_val in [false, true].iter().copied() {
955 for b_val in [false, true].iter().copied() {
956 let cs = ConstraintSystem::<Fr>::new_ref();
957 let a = AllocatedBit::new_witness(cs.clone(), || Ok(a_val))?;
958 let b = AllocatedBit::new_witness(cs.clone(), || Ok(b_val))?;
959 let c = AllocatedBit::or(&a, &b)?;
960 assert_eq!(c.value()?, a_val | b_val);
961
962 assert!(cs.is_satisfied().unwrap());
963 assert_eq!(a.value()?, (a_val));
964 assert_eq!(b.value()?, (b_val));
965 assert_eq!(c.value()?, (a_val | b_val));
966 }
967 }
968 Ok(())
969 }
970
971 #[test]
972 fn test_and() -> Result<(), SynthesisError> {
973 for a_val in [false, true].iter().copied() {
974 for b_val in [false, true].iter().copied() {
975 let cs = ConstraintSystem::<Fr>::new_ref();
976 let a = AllocatedBit::new_witness(cs.clone(), || Ok(a_val))?;
977 let b = AllocatedBit::new_witness(cs.clone(), || Ok(b_val))?;
978 let c = AllocatedBit::and(&a, &b)?;
979 assert_eq!(c.value()?, a_val & b_val);
980
981 assert!(cs.is_satisfied().unwrap());
982 assert_eq!(a.value()?, (a_val));
983 assert_eq!(b.value()?, (b_val));
984 assert_eq!(c.value()?, (a_val & b_val));
985 }
986 }
987 Ok(())
988 }
989
990 #[test]
991 fn test_and_not() -> Result<(), SynthesisError> {
992 for a_val in [false, true].iter().copied() {
993 for b_val in [false, true].iter().copied() {
994 let cs = ConstraintSystem::<Fr>::new_ref();
995 let a = AllocatedBit::new_witness(cs.clone(), || Ok(a_val))?;
996 let b = AllocatedBit::new_witness(cs.clone(), || Ok(b_val))?;
997 let c = AllocatedBit::and_not(&a, &b)?;
998 assert_eq!(c.value()?, a_val & !b_val);
999
1000 assert!(cs.is_satisfied().unwrap());
1001 assert_eq!(a.value()?, (a_val));
1002 assert_eq!(b.value()?, (b_val));
1003 assert_eq!(c.value()?, (a_val & !b_val));
1004 }
1005 }
1006 Ok(())
1007 }
1008
1009 #[test]
1010 fn test_nor() -> Result<(), SynthesisError> {
1011 for a_val in [false, true].iter().copied() {
1012 for b_val in [false, true].iter().copied() {
1013 let cs = ConstraintSystem::<Fr>::new_ref();
1014 let a = AllocatedBit::new_witness(cs.clone(), || Ok(a_val))?;
1015 let b = AllocatedBit::new_witness(cs.clone(), || Ok(b_val))?;
1016 let c = AllocatedBit::nor(&a, &b)?;
1017 assert_eq!(c.value()?, !a_val & !b_val);
1018
1019 assert!(cs.is_satisfied().unwrap());
1020 assert_eq!(a.value()?, (a_val));
1021 assert_eq!(b.value()?, (b_val));
1022 assert_eq!(c.value()?, (!a_val & !b_val));
1023 }
1024 }
1025 Ok(())
1026 }
1027
1028 #[test]
1029 fn test_enforce_equal() -> Result<(), SynthesisError> {
1030 for a_bool in [false, true].iter().cloned() {
1031 for b_bool in [false, true].iter().cloned() {
1032 for a_neg in [false, true].iter().cloned() {
1033 for b_neg in [false, true].iter().cloned() {
1034 let cs = ConstraintSystem::<Fr>::new_ref();
1035
1036 let mut a = Boolean::new_witness(cs.clone(), || Ok(a_bool))?;
1037 let mut b = Boolean::new_witness(cs.clone(), || Ok(b_bool))?;
1038
1039 if a_neg {
1040 a = a.not();
1041 }
1042 if b_neg {
1043 b = b.not();
1044 }
1045
1046 a.enforce_equal(&b)?;
1047
1048 assert_eq!(
1049 cs.is_satisfied().unwrap(),
1050 (a_bool ^ a_neg) == (b_bool ^ b_neg)
1051 );
1052 }
1053 }
1054 }
1055 }
1056 Ok(())
1057 }
1058
1059 #[test]
1060 fn test_conditional_enforce_equal() -> Result<(), SynthesisError> {
1061 for a_bool in [false, true].iter().cloned() {
1062 for b_bool in [false, true].iter().cloned() {
1063 for a_neg in [false, true].iter().cloned() {
1064 for b_neg in [false, true].iter().cloned() {
1065 let cs = ConstraintSystem::<Fr>::new_ref();
1066
1067 // First test if constraint system is satisfied
1068 // when we do want to enforce the condition.
1069 let mut a = Boolean::new_witness(cs.clone(), || Ok(a_bool))?;
1070 let mut b = Boolean::new_witness(cs.clone(), || Ok(b_bool))?;
1071
1072 if a_neg {
1073 a = a.not();
1074 }
1075 if b_neg {
1076 b = b.not();
1077 }
1078
1079 a.conditional_enforce_equal(&b, &Boolean::constant(true))?;
1080
1081 assert_eq!(
1082 cs.is_satisfied().unwrap(),
1083 (a_bool ^ a_neg) == (b_bool ^ b_neg)
1084 );
1085
1086 // Now test if constraint system is satisfied even
1087 // when we don't want to enforce the condition.
1088 let cs = ConstraintSystem::<Fr>::new_ref();
1089
1090 let mut a = Boolean::new_witness(cs.clone(), || Ok(a_bool))?;
1091 let mut b = Boolean::new_witness(cs.clone(), || Ok(b_bool))?;
1092
1093 if a_neg {
1094 a = a.not();
1095 }
1096 if b_neg {
1097 b = b.not();
1098 }
1099
1100 let false_cond =
1101 Boolean::new_witness(r1cs_core::ns!(cs, "cond"), || Ok(false))?;
1102 a.conditional_enforce_equal(&b, &false_cond)?;
1103
1104 assert!(cs.is_satisfied().unwrap());
1105 }
1106 }
1107 }
1108 }
1109 Ok(())
1110 }
1111
1112 #[test]
1113 fn test_boolean_negation() -> Result<(), SynthesisError> {
1114 let cs = ConstraintSystem::<Fr>::new_ref();
1115
1116 let mut b = Boolean::new_witness(cs.clone(), || Ok(true))?;
1117 assert!(matches!(b, Boolean::Is(_)));
1118
1119 b = b.not();
1120 assert!(matches!(b, Boolean::Not(_)));
1121
1122 b = b.not();
1123 assert!(matches!(b, Boolean::Is(_)));
1124
1125 b = Boolean::Constant(true);
1126 assert!(matches!(b, Boolean::Constant(true)));
1127
1128 b = b.not();
1129 assert!(matches!(b, Boolean::Constant(false)));
1130
1131 b = b.not();
1132 assert!(matches!(b, Boolean::Constant(true)));
1133 Ok(())
1134 }
1135
1136 #[derive(Eq, PartialEq, Copy, Clone, Debug)]
1137 enum OpType {
1138 True,
1139 False,
1140 AllocatedTrue,
1141 AllocatedFalse,
1142 NegatedAllocatedTrue,
1143 NegatedAllocatedFalse,
1144 }
1145
1146 const VARIANTS: [OpType; 6] = [
1147 OpType::True,
1148 OpType::False,
1149 OpType::AllocatedTrue,
1150 OpType::AllocatedFalse,
1151 OpType::NegatedAllocatedTrue,
1152 OpType::NegatedAllocatedFalse,
1153 ];
1154
1155 fn construct<F: Field>(
1156 ns: Namespace<F>,
1157 operand: OpType,
1158 ) -> Result<Boolean<F>, SynthesisError> {
1159 let cs = ns.cs();
1160
1161 let b = match operand {
1162 OpType::True => Boolean::constant(true),
1163 OpType::False => Boolean::constant(false),
1164 OpType::AllocatedTrue => Boolean::new_witness(cs, || Ok(true))?,
1165 OpType::AllocatedFalse => Boolean::new_witness(cs, || Ok(false))?,
1166 OpType::NegatedAllocatedTrue => Boolean::new_witness(cs, || Ok(true))?.not(),
1167 OpType::NegatedAllocatedFalse => Boolean::new_witness(cs, || Ok(false))?.not(),
1168 };
1169 Ok(b)
1170 }
1171
1172 #[test]
1173 fn test_boolean_xor() -> Result<(), SynthesisError> {
1174 for first_operand in VARIANTS.iter().cloned() {
1175 for second_operand in VARIANTS.iter().cloned() {
1176 let cs = ConstraintSystem::<Fr>::new_ref();
1177
1178 let a = construct(r1cs_core::ns!(cs, "a"), first_operand)?;
1179 let b = construct(r1cs_core::ns!(cs, "b"), second_operand)?;
1180 let c = Boolean::xor(&a, &b)?;
1181
1182 assert!(cs.is_satisfied().unwrap());
1183
1184 match (first_operand, second_operand, c) {
1185 (OpType::True, OpType::True, Boolean::Constant(false)) => (),
1186 (OpType::True, OpType::False, Boolean::Constant(true)) => (),
1187 (OpType::True, OpType::AllocatedTrue, Boolean::Not(_)) => (),
1188 (OpType::True, OpType::AllocatedFalse, Boolean::Not(_)) => (),
1189 (OpType::True, OpType::NegatedAllocatedTrue, Boolean::Is(_)) => (),
1190 (OpType::True, OpType::NegatedAllocatedFalse, Boolean::Is(_)) => (),
1191
1192 (OpType::False, OpType::True, Boolean::Constant(true)) => (),
1193 (OpType::False, OpType::False, Boolean::Constant(false)) => (),
1194 (OpType::False, OpType::AllocatedTrue, Boolean::Is(_)) => (),
1195 (OpType::False, OpType::AllocatedFalse, Boolean::Is(_)) => (),
1196 (OpType::False, OpType::NegatedAllocatedTrue, Boolean::Not(_)) => (),
1197 (OpType::False, OpType::NegatedAllocatedFalse, Boolean::Not(_)) => (),
1198
1199 (OpType::AllocatedTrue, OpType::True, Boolean::Not(_)) => (),
1200 (OpType::AllocatedTrue, OpType::False, Boolean::Is(_)) => (),
1201 (OpType::AllocatedTrue, OpType::AllocatedTrue, Boolean::Is(ref v)) => {
1202 assert_eq!(v.value(), Ok(false));
1203 }
1204 (OpType::AllocatedTrue, OpType::AllocatedFalse, Boolean::Is(ref v)) => {
1205 assert_eq!(v.value(), Ok(true));
1206 }
1207 (OpType::AllocatedTrue, OpType::NegatedAllocatedTrue, Boolean::Not(ref v)) => {
1208 assert_eq!(v.value(), Ok(false));
1209 }
1210 (OpType::AllocatedTrue, OpType::NegatedAllocatedFalse, Boolean::Not(ref v)) => {
1211 assert_eq!(v.value(), Ok(true));
1212 }
1213 (OpType::AllocatedFalse, OpType::True, Boolean::Not(_)) => (),
1214 (OpType::AllocatedFalse, OpType::False, Boolean::Is(_)) => (),
1215 (OpType::AllocatedFalse, OpType::AllocatedTrue, Boolean::Is(ref v)) => {
1216 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::one());
1217 assert_eq!(v.value(), Ok(true));
1218 }
1219 (OpType::AllocatedFalse, OpType::AllocatedFalse, Boolean::Is(ref v)) => {
1220 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1221 assert_eq!(v.value(), Ok(false));
1222 }
1223 (OpType::AllocatedFalse, OpType::NegatedAllocatedTrue, Boolean::Not(ref v)) => {
1224 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::one());
1225 assert_eq!(v.value(), Ok(true));
1226 }
1227 (
1228 OpType::AllocatedFalse,
1229 OpType::NegatedAllocatedFalse,
1230 Boolean::Not(ref v),
1231 ) => {
1232 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1233 assert_eq!(v.value(), Ok(false));
1234 }
1235
1236 (OpType::NegatedAllocatedTrue, OpType::True, Boolean::Is(_)) => (),
1237 (OpType::NegatedAllocatedTrue, OpType::False, Boolean::Not(_)) => (),
1238 (OpType::NegatedAllocatedTrue, OpType::AllocatedTrue, Boolean::Not(ref v)) => {
1239 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1240 assert_eq!(v.value(), Ok(false));
1241 }
1242 (OpType::NegatedAllocatedTrue, OpType::AllocatedFalse, Boolean::Not(ref v)) => {
1243 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::one());
1244 assert_eq!(v.value(), Ok(true));
1245 }
1246 (
1247 OpType::NegatedAllocatedTrue,
1248 OpType::NegatedAllocatedTrue,
1249 Boolean::Is(ref v),
1250 ) => {
1251 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1252 assert_eq!(v.value(), Ok(false));
1253 }
1254 (
1255 OpType::NegatedAllocatedTrue,
1256 OpType::NegatedAllocatedFalse,
1257 Boolean::Is(ref v),
1258 ) => {
1259 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::one());
1260 assert_eq!(v.value(), Ok(true));
1261 }
1262
1263 (OpType::NegatedAllocatedFalse, OpType::True, Boolean::Is(_)) => (),
1264 (OpType::NegatedAllocatedFalse, OpType::False, Boolean::Not(_)) => (),
1265 (OpType::NegatedAllocatedFalse, OpType::AllocatedTrue, Boolean::Not(ref v)) => {
1266 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::one());
1267 assert_eq!(v.value(), Ok(true));
1268 }
1269 (
1270 OpType::NegatedAllocatedFalse,
1271 OpType::AllocatedFalse,
1272 Boolean::Not(ref v),
1273 ) => {
1274 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1275 assert_eq!(v.value(), Ok(false));
1276 }
1277 (
1278 OpType::NegatedAllocatedFalse,
1279 OpType::NegatedAllocatedTrue,
1280 Boolean::Is(ref v),
1281 ) => {
1282 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::one());
1283 assert_eq!(v.value(), Ok(true));
1284 }
1285 (
1286 OpType::NegatedAllocatedFalse,
1287 OpType::NegatedAllocatedFalse,
1288 Boolean::Is(ref v),
1289 ) => {
1290 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1291 assert_eq!(v.value(), Ok(false));
1292 }
1293
1294 _ => unreachable!(),
1295 }
1296 }
1297 }
1298 Ok(())
1299 }
1300
1301 #[test]
1302 fn test_boolean_cond_select() -> Result<(), SynthesisError> {
1303 for condition in VARIANTS.iter().cloned() {
1304 for first_operand in VARIANTS.iter().cloned() {
1305 for second_operand in VARIANTS.iter().cloned() {
1306 let cs = ConstraintSystem::<Fr>::new_ref();
1307
1308 let cond = construct(r1cs_core::ns!(cs, "cond"), condition)?;
1309 let a = construct(r1cs_core::ns!(cs, "a"), first_operand)?;
1310 let b = construct(r1cs_core::ns!(cs, "b"), second_operand)?;
1311 let c = cond.select(&a, &b)?;
1312
1313 assert!(
1314 cs.is_satisfied().unwrap(),
1315 "failed with operands: cond: {:?}, a: {:?}, b: {:?}",
1316 condition,
1317 first_operand,
1318 second_operand,
1319 );
1320 assert_eq!(
1321 c.value()?,
1322 if cond.value()? {
1323 a.value()?
1324 } else {
1325 b.value()?
1326 }
1327 );
1328 }
1329 }
1330 }
1331 Ok(())
1332 }
1333
1334 #[test]
1335 fn test_boolean_or() -> Result<(), SynthesisError> {
1336 for first_operand in VARIANTS.iter().cloned() {
1337 for second_operand in VARIANTS.iter().cloned() {
1338 let cs = ConstraintSystem::<Fr>::new_ref();
1339
1340 let a = construct(r1cs_core::ns!(cs, "a"), first_operand)?;
1341 let b = construct(r1cs_core::ns!(cs, "b"), second_operand)?;
1342 let c = a.or(&b)?;
1343
1344 assert!(cs.is_satisfied().unwrap());
1345
1346 match (first_operand, second_operand, c.clone()) {
1347 (OpType::True, OpType::True, Boolean::Constant(true)) => (),
1348 (OpType::True, OpType::False, Boolean::Constant(true)) => (),
1349 (OpType::True, OpType::AllocatedTrue, Boolean::Constant(true)) => (),
1350 (OpType::True, OpType::AllocatedFalse, Boolean::Constant(true)) => (),
1351 (OpType::True, OpType::NegatedAllocatedTrue, Boolean::Constant(true)) => (),
1352 (OpType::True, OpType::NegatedAllocatedFalse, Boolean::Constant(true)) => (),
1353
1354 (OpType::False, OpType::True, Boolean::Constant(true)) => (),
1355 (OpType::False, OpType::False, Boolean::Constant(false)) => (),
1356 (OpType::False, OpType::AllocatedTrue, Boolean::Is(_)) => (),
1357 (OpType::False, OpType::AllocatedFalse, Boolean::Is(_)) => (),
1358 (OpType::False, OpType::NegatedAllocatedTrue, Boolean::Not(_)) => (),
1359 (OpType::False, OpType::NegatedAllocatedFalse, Boolean::Not(_)) => (),
1360
1361 (OpType::AllocatedTrue, OpType::True, Boolean::Constant(true)) => (),
1362 (OpType::AllocatedTrue, OpType::False, Boolean::Is(_)) => (),
1363 (OpType::AllocatedTrue, OpType::AllocatedTrue, Boolean::Is(ref v)) => {
1364 assert_eq!(v.value(), Ok(true));
1365 }
1366 (OpType::AllocatedTrue, OpType::AllocatedFalse, Boolean::Is(ref v)) => {
1367 assert_eq!(v.value(), Ok(true));
1368 }
1369 (OpType::AllocatedTrue, OpType::NegatedAllocatedTrue, Boolean::Not(ref v)) => {
1370 assert_eq!(v.value(), Ok(false));
1371 }
1372 (OpType::AllocatedTrue, OpType::NegatedAllocatedFalse, Boolean::Not(ref v)) => {
1373 assert_eq!(v.value(), Ok(false));
1374 }
1375
1376 (OpType::AllocatedFalse, OpType::True, Boolean::Constant(true)) => (),
1377 (OpType::AllocatedFalse, OpType::False, Boolean::Is(_)) => (),
1378 (OpType::AllocatedFalse, OpType::AllocatedTrue, Boolean::Is(ref v)) => {
1379 assert_eq!(v.value(), Ok(true));
1380 }
1381 (OpType::AllocatedFalse, OpType::AllocatedFalse, Boolean::Is(ref v)) => {
1382 assert_eq!(v.value(), Ok(false));
1383 }
1384 (OpType::AllocatedFalse, OpType::NegatedAllocatedTrue, Boolean::Not(ref v)) => {
1385 assert_eq!(v.value(), Ok(true));
1386 }
1387 (
1388 OpType::AllocatedFalse,
1389 OpType::NegatedAllocatedFalse,
1390 Boolean::Not(ref v),
1391 ) => {
1392 assert_eq!(v.value(), Ok(false));
1393 }
1394
1395 (OpType::NegatedAllocatedTrue, OpType::True, Boolean::Constant(true)) => (),
1396 (OpType::NegatedAllocatedTrue, OpType::False, Boolean::Not(_)) => (),
1397 (OpType::NegatedAllocatedTrue, OpType::AllocatedTrue, Boolean::Not(ref v)) => {
1398 assert_eq!(v.value(), Ok(false));
1399 }
1400 (OpType::NegatedAllocatedTrue, OpType::AllocatedFalse, Boolean::Not(ref v)) => {
1401 assert_eq!(v.value(), Ok(true));
1402 }
1403 (
1404 OpType::NegatedAllocatedTrue,
1405 OpType::NegatedAllocatedTrue,
1406 Boolean::Not(ref v),
1407 ) => {
1408 assert_eq!(v.value(), Ok(true));
1409 }
1410 (
1411 OpType::NegatedAllocatedTrue,
1412 OpType::NegatedAllocatedFalse,
1413 Boolean::Not(ref v),
1414 ) => {
1415 assert_eq!(v.value(), Ok(false));
1416 }
1417
1418 (OpType::NegatedAllocatedFalse, OpType::True, Boolean::Constant(true)) => (),
1419 (OpType::NegatedAllocatedFalse, OpType::False, Boolean::Not(_)) => (),
1420 (OpType::NegatedAllocatedFalse, OpType::AllocatedTrue, Boolean::Not(ref v)) => {
1421 assert_eq!(v.value(), Ok(false));
1422 }
1423 (
1424 OpType::NegatedAllocatedFalse,
1425 OpType::AllocatedFalse,
1426 Boolean::Not(ref v),
1427 ) => {
1428 assert_eq!(v.value(), Ok(false));
1429 }
1430 (
1431 OpType::NegatedAllocatedFalse,
1432 OpType::NegatedAllocatedTrue,
1433 Boolean::Not(ref v),
1434 ) => {
1435 assert_eq!(v.value(), Ok(false));
1436 }
1437 (
1438 OpType::NegatedAllocatedFalse,
1439 OpType::NegatedAllocatedFalse,
1440 Boolean::Not(ref v),
1441 ) => {
1442 assert_eq!(v.value(), Ok(false));
1443 }
1444
1445 _ => panic!(
1446 "this should never be encountered, in case: (a = {:?}, b = {:?}, c = {:?})",
1447 a, b, c
1448 ),
1449 }
1450 }
1451 }
1452 Ok(())
1453 }
1454
1455 #[test]
1456 fn test_boolean_and() -> Result<(), SynthesisError> {
1457 for first_operand in VARIANTS.iter().cloned() {
1458 for second_operand in VARIANTS.iter().cloned() {
1459 let cs = ConstraintSystem::<Fr>::new_ref();
1460
1461 let a = construct(r1cs_core::ns!(cs, "a"), first_operand)?;
1462 let b = construct(r1cs_core::ns!(cs, "b"), second_operand)?;
1463 let c = a.and(&b)?;
1464
1465 assert!(cs.is_satisfied().unwrap());
1466
1467 match (first_operand, second_operand, c) {
1468 (OpType::True, OpType::True, Boolean::Constant(true)) => (),
1469 (OpType::True, OpType::False, Boolean::Constant(false)) => (),
1470 (OpType::True, OpType::AllocatedTrue, Boolean::Is(_)) => (),
1471 (OpType::True, OpType::AllocatedFalse, Boolean::Is(_)) => (),
1472 (OpType::True, OpType::NegatedAllocatedTrue, Boolean::Not(_)) => (),
1473 (OpType::True, OpType::NegatedAllocatedFalse, Boolean::Not(_)) => (),
1474
1475 (OpType::False, OpType::True, Boolean::Constant(false)) => (),
1476 (OpType::False, OpType::False, Boolean::Constant(false)) => (),
1477 (OpType::False, OpType::AllocatedTrue, Boolean::Constant(false)) => (),
1478 (OpType::False, OpType::AllocatedFalse, Boolean::Constant(false)) => (),
1479 (OpType::False, OpType::NegatedAllocatedTrue, Boolean::Constant(false)) => (),
1480 (OpType::False, OpType::NegatedAllocatedFalse, Boolean::Constant(false)) => (),
1481
1482 (OpType::AllocatedTrue, OpType::True, Boolean::Is(_)) => (),
1483 (OpType::AllocatedTrue, OpType::False, Boolean::Constant(false)) => (),
1484 (OpType::AllocatedTrue, OpType::AllocatedTrue, Boolean::Is(ref v)) => {
1485 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::one());
1486 assert_eq!(v.value(), Ok(true));
1487 }
1488 (OpType::AllocatedTrue, OpType::AllocatedFalse, Boolean::Is(ref v)) => {
1489 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1490 assert_eq!(v.value(), Ok(false));
1491 }
1492 (OpType::AllocatedTrue, OpType::NegatedAllocatedTrue, Boolean::Is(ref v)) => {
1493 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1494 assert_eq!(v.value(), Ok(false));
1495 }
1496 (OpType::AllocatedTrue, OpType::NegatedAllocatedFalse, Boolean::Is(ref v)) => {
1497 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::one());
1498 assert_eq!(v.value(), Ok(true));
1499 }
1500
1501 (OpType::AllocatedFalse, OpType::True, Boolean::Is(_)) => (),
1502 (OpType::AllocatedFalse, OpType::False, Boolean::Constant(false)) => (),
1503 (OpType::AllocatedFalse, OpType::AllocatedTrue, Boolean::Is(ref v)) => {
1504 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1505 assert_eq!(v.value(), Ok(false));
1506 }
1507 (OpType::AllocatedFalse, OpType::AllocatedFalse, Boolean::Is(ref v)) => {
1508 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1509 assert_eq!(v.value(), Ok(false));
1510 }
1511 (OpType::AllocatedFalse, OpType::NegatedAllocatedTrue, Boolean::Is(ref v)) => {
1512 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1513 assert_eq!(v.value(), Ok(false));
1514 }
1515 (OpType::AllocatedFalse, OpType::NegatedAllocatedFalse, Boolean::Is(ref v)) => {
1516 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1517 assert_eq!(v.value(), Ok(false));
1518 }
1519
1520 (OpType::NegatedAllocatedTrue, OpType::True, Boolean::Not(_)) => (),
1521 (OpType::NegatedAllocatedTrue, OpType::False, Boolean::Constant(false)) => (),
1522 (OpType::NegatedAllocatedTrue, OpType::AllocatedTrue, Boolean::Is(ref v)) => {
1523 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1524 assert_eq!(v.value(), Ok(false));
1525 }
1526 (OpType::NegatedAllocatedTrue, OpType::AllocatedFalse, Boolean::Is(ref v)) => {
1527 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1528 assert_eq!(v.value(), Ok(false));
1529 }
1530 (
1531 OpType::NegatedAllocatedTrue,
1532 OpType::NegatedAllocatedTrue,
1533 Boolean::Is(ref v),
1534 ) => {
1535 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1536 assert_eq!(v.value(), Ok(false));
1537 }
1538 (
1539 OpType::NegatedAllocatedTrue,
1540 OpType::NegatedAllocatedFalse,
1541 Boolean::Is(ref v),
1542 ) => {
1543 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1544 assert_eq!(v.value(), Ok(false));
1545 }
1546
1547 (OpType::NegatedAllocatedFalse, OpType::True, Boolean::Not(_)) => (),
1548 (OpType::NegatedAllocatedFalse, OpType::False, Boolean::Constant(false)) => (),
1549 (OpType::NegatedAllocatedFalse, OpType::AllocatedTrue, Boolean::Is(ref v)) => {
1550 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::one());
1551 assert_eq!(v.value(), Ok(true));
1552 }
1553 (OpType::NegatedAllocatedFalse, OpType::AllocatedFalse, Boolean::Is(ref v)) => {
1554 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1555 assert_eq!(v.value(), Ok(false));
1556 }
1557 (
1558 OpType::NegatedAllocatedFalse,
1559 OpType::NegatedAllocatedTrue,
1560 Boolean::Is(ref v),
1561 ) => {
1562 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::zero());
1563 assert_eq!(v.value(), Ok(false));
1564 }
1565 (
1566 OpType::NegatedAllocatedFalse,
1567 OpType::NegatedAllocatedFalse,
1568 Boolean::Is(ref v),
1569 ) => {
1570 assert_eq!(cs.assigned_value(v.variable()).unwrap(), Fr::one());
1571 assert_eq!(v.value(), Ok(true));
1572 }
1573
1574 _ => {
1575 panic!(
1576 "unexpected behavior at {:?} AND {:?}",
1577 first_operand, second_operand
1578 );
1579 }
1580 }
1581 }
1582 }
1583 Ok(())
1584 }
1585
1586 #[test]
1587 fn test_smaller_than_or_equal_to() -> Result<(), SynthesisError> {
1588 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
1589 for _ in 0..1000 {
1590 let mut r = Fr::rand(&mut rng);
1591 let mut s = Fr::rand(&mut rng);
1592 if r > s {
1593 core::mem::swap(&mut r, &mut s)
1594 }
1595
1596 let cs = ConstraintSystem::<Fr>::new_ref();
1597
1598 let native_bits: Vec<_> = BitIteratorLE::new(r.into_repr()).collect();
1599 let bits = Vec::new_witness(cs.clone(), || Ok(native_bits))?;
1600 Boolean::enforce_smaller_or_equal_than_le(&bits, s.into_repr())?;
1601
1602 assert!(cs.is_satisfied().unwrap());
1603 }
1604
1605 for _ in 0..1000 {
1606 let r = Fr::rand(&mut rng);
1607 if r == -Fr::one() {
1608 continue;
1609 }
1610 let s = r + Fr::one();
1611 let s2 = r.double();
1612 let cs = ConstraintSystem::<Fr>::new_ref();
1613
1614 let native_bits: Vec<_> = BitIteratorLE::new(r.into_repr()).collect();
1615 let bits = Vec::new_witness(cs.clone(), || Ok(native_bits))?;
1616 Boolean::enforce_smaller_or_equal_than_le(&bits, s.into_repr())?;
1617 if r < s2 {
1618 Boolean::enforce_smaller_or_equal_than_le(&bits, s2.into_repr())?;
1619 }
1620
1621 assert!(cs.is_satisfied().unwrap());
1622 }
1623 Ok(())
1624 }
1625
1626 #[test]
1627 fn test_enforce_in_field() -> Result<(), SynthesisError> {
1628 {
1629 let cs = ConstraintSystem::<Fr>::new_ref();
1630
1631 let mut bits = vec![];
1632 for b in BitIteratorBE::new(Fr::characteristic()).skip(1) {
1633 bits.push(Boolean::new_witness(cs.clone(), || Ok(b))?);
1634 }
1635 bits.reverse();
1636
1637 Boolean::enforce_in_field_le(&bits)?;
1638
1639 assert!(!cs.is_satisfied().unwrap());
1640 }
1641
1642 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
1643
1644 for _ in 0..1000 {
1645 let r = Fr::rand(&mut rng);
1646 let cs = ConstraintSystem::<Fr>::new_ref();
1647
1648 let mut bits = vec![];
1649 for b in BitIteratorBE::new(r.into_repr()).skip(1) {
1650 bits.push(Boolean::new_witness(cs.clone(), || Ok(b))?);
1651 }
1652 bits.reverse();
1653
1654 Boolean::enforce_in_field_le(&bits)?;
1655
1656 assert!(cs.is_satisfied().unwrap());
1657 }
1658 Ok(())
1659 }
1660
1661 #[test]
1662 fn test_enforce_nand() -> Result<(), SynthesisError> {
1663 {
1664 let cs = ConstraintSystem::<Fr>::new_ref();
1665
1666 assert!(
1667 Boolean::enforce_kary_nand(&[Boolean::new_constant(cs.clone(), false)?]).is_ok()
1668 );
1669 assert!(
1670 Boolean::enforce_kary_nand(&[Boolean::new_constant(cs.clone(), true)?]).is_err()
1671 );
1672 }
1673
1674 for i in 1..5 {
1675 // with every possible assignment for them
1676 for mut b in 0..(1 << i) {
1677 // with every possible negation
1678 for mut n in 0..(1 << i) {
1679 let cs = ConstraintSystem::<Fr>::new_ref();
1680
1681 let mut expected = true;
1682
1683 let mut bits = vec![];
1684 for _ in 0..i {
1685 expected &= b & 1 == 1;
1686
1687 let bit = if n & 1 == 1 {
1688 Boolean::new_witness(cs.clone(), || Ok(b & 1 == 1))?
1689 } else {
1690 Boolean::new_witness(cs.clone(), || Ok(b & 1 == 0))?.not()
1691 };
1692 bits.push(bit);
1693
1694 b >>= 1;
1695 n >>= 1;
1696 }
1697
1698 let expected = !expected;
1699
1700 Boolean::enforce_kary_nand(&bits)?;
1701
1702 if expected {
1703 assert!(cs.is_satisfied().unwrap());
1704 } else {
1705 assert!(!cs.is_satisfied().unwrap());
1706 }
1707 }
1708 }
1709 }
1710 Ok(())
1711 }
1712
1713 #[test]
1714 fn test_kary_and() -> Result<(), SynthesisError> {
1715 // test different numbers of operands
1716 for i in 1..15 {
1717 // with every possible assignment for them
1718 for mut b in 0..(1 << i) {
1719 let cs = ConstraintSystem::<Fr>::new_ref();
1720
1721 let mut expected = true;
1722
1723 let mut bits = vec![];
1724 for _ in 0..i {
1725 expected &= b & 1 == 1;
1726 bits.push(Boolean::new_witness(cs.clone(), || Ok(b & 1 == 1))?);
1727 b >>= 1;
1728 }
1729
1730 let r = Boolean::kary_and(&bits)?;
1731
1732 assert!(cs.is_satisfied().unwrap());
1733
1734 if let Boolean::Is(ref r) = r {
1735 assert_eq!(r.value()?, expected);
1736 }
1737 }
1738 }
1739 Ok(())
1740 }
1741}