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