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