Boolean vectors AND gate

1

Hi,

I was curious how does one implement an AND gate between two boolean vectors ? Here what I mean is suppose one has
(0110,1110) and (1111,0000) = (0110,0000)
Any idea as to how I can do that?

Thanks in advance!

2

It's the & operator - same as in many other languages like for example C++. The trait for it is called BitAnd, if you'd need to use it in generic context.

So I think you'd use that operator on integers and implement it on your boolean vectors - unsure what exactly they will be - using that.

3

You can do this using the bitwise & operator. For example, if your bits are stored in integer types, you can use it like this:

let a = 0b0110_1110;
let b = 0b1111_0000;

let c = a & b;
assert_eq!(c, 0b0110_0000);

If your boolean or integer values are stored in vectors or arrays, you can iterate over them and apply the & operator to each element:

fn and(a: &[bool], b: &[bool]) -> Vec<bool> {
    // This simple implementation assumes both inputs have the same length.
    assert_eq!(a.len(), b.len());
    a.iter().zip(b).map(|(x, y)| x & y).collect()
}

Crates like bitvec provide compact boolean vectors that implement BitAnd, so you can use the & operator on them directly.

1 Like
4

Thanks that helps!

5

I have used the exact line as you had said.

    mut cs: CS,
    a: &[Boolean], r: &[Boolean]
) -> Result<Vec<Boolean>, SynthesisError> {
    // Flip endianness of each input byte
    let input_1: Vec<_> = a
        .chunks(8)
        .map(|c| c.iter().rev())
        .flatten()
        .cloned()
        .collect();
    let input_2: Vec<_> = r
        .chunks(8)
        .map(|c| c.iter().rev())
        .flatten()
        .cloned()
        .collect();

    let mid = input_1.iter().zip(input_2).map(|(x, y)| x & y).collect();

    // Flip endianness of each output byte
    
      Ok(mid
        .chunks(8)
        .map(|c| c.iter().rev())
        .flatten()
        .cloned()
        .collect())
}

But I still get the error,

error[E0369]: no implementation for `&Boolean & Boolean`
  --> src/main.rs:62:58
   |
62 |     let mid = input_1.iter().zip(input_2).map(|(x, y)| x & y).collect();
   |                                                        - ^ - Boolean
   |                                                        |
   |                                                        &Boolean

error: aborting due to previous error; 1 warning emitted

For more information about this error, try `rustc --explain E0369`.
error: could not compile `multiply`

I don't understand how exactly can I fix it. Please let me know.
Thanks!

6

Where is the type Boolean defined?

7

So Boolean is part of Bellman library,

bellman::gadgets::boolean::Boolean
8

From the bellman docs we can see that Boolean does not implement the standard BitAnd trait, but it does have its own and() method. Instead of (x & y), you can write:

Boolean::and(cs, x, y).unwrap()

If you want to propagate the error instead of unwrapping, something like this should work:

let mid = input_1.iter().zip(input_2).map(|(x, y)| {
    Boolean::and(cs, x, y)
}).collect::<Result<Vec<Boolean>, SynthesisError>>()?;
9

Avoid the unwrap by writing

.map(|(x, y)| Boolean::and(cs, x, y)).collect()?;

actually, you probably need to write

.map(|(x, y)| Boolean::and(&mut cs, x, y)).collect()?;
1 Like
10

Alright I am trying these options, I first wrote Boolean::and but now that I see the syntax you have written, think I was wrong, I will get back in a bit

11

So below is the piece of code that has stopped giving the error but now I have another problem here.

   .collect();

    let mid = input_1.iter().zip(input_2).map(|(x, y)| Boolean::and(&mut cs, &x, &y)).collect()?;

The error I get is


error[E0282]: type annotations needed
  --> src/main.rs:67:10
   |
62 |     let mid = input_1.iter().zip(input_2).map(|(x, y)| Boolean::and(&mut cs, &x, &y)).collect()?;
   |         --- consider giving `mid` a type
...
67 |       Ok(mid
   |          ^^^ cannot infer type
   |
   = note: type must be known at this point

But for this code I am referring to bellman - Rust . But I don't see them here giving a data type, am I missing something ? Please let me know.

Thanks!

12

Try annotating the .collect() call like this:

let mid = input_1.iter().zip(input_2)
    .map(|(x, y)| Boolean::and(&mut cs, &x, &y))
    .collect::<Result<Vec<Boolean>, SynthesisError>>()?;
13

Thanks a lot, that works perfectly now, the way I wanted. Just curious as to I still don't understand how is the error fixed ?

14

Iterator::collect is a generic function defined as:

pub fn collect<B>(self) -> B
where
    B: FromIterator<Self::Item>,

which returns B by calling:

B::from_iter(self)

but since FromIterator can be implemented for various different types, (such as Vec<T> and String) if rust can't infer the return type, it doesn't know which type from_iter is called on, and so you must declare the type yourself.

// this also works because rust now knows that `B` in `collect::<B>()` == `Result<Vec<Boolean>, SynthesisError>`
let mid: Result<Vec<Boolean>, SynthesisError> = input_1.iter().zip(input_2)
    .map(|(x, y)| Boolean::and(&mut cs, &x, &y))
    .collect()?;
15

Thanks I understand

16

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.