# Bitwise operations

In this note we describe how to compute bitwise AND, OR, and XOR operations on 32-bit values. It assumes some familiarity with [permutation checks](https://hackmd.io/@arielg/ByFgSDA7D).

Assume that $x$ and $y$ are field elements in a 64-bit prime field. Assume also that $x$ and $y$ are known to contain values smaller than $2^{32}$. We want to compute $x \oplus y \rightarrow z$, where $\oplus$ is either bitwise AND, OR, or XOR, and $z$ is a field element containing the result of the corresponding bitwise operation.

First, observe that we can compute AND, OR, and XOR relations for **single bit values** as follows:

$$
and(x, y) = x \cdot y
$$

$$
or(x, y) = x + y - x \cdot y
$$

$$
xor(x, y) = x + y - 2 \cdot x \cdot y
$$

To compute bitwise operations for multi-bit values, we will decompose the values into individual bits, apply the operations to single bits, and then aggregate the bitwsie results into the final result.

To perform this operation we will use a table with 13 columns, and computing a single AND, OR, or XOR operation will require 8 table rows. We will also rely on two periodic columns as shown below.


In the above, the columns have the following meanings:

* Periodic columns $k_0$ and $k_1$. These columns contain values needed to switch various constraint on or off. $k_0$ contains a repeating sequence of a single one, followed by seven zeros. $k_1$ contains a repeating sequence of seven ones, followed by a single zero.
* Row address column $r$. Values in this column are incremented with every row. We will use this column to bind inputs and outputs for a single operation - i.e., the inputs and outputs will be exactly 7 rows apart.
* Input columns $x$ and $y$. On the first row of each 8-row cycle, the prover will set values in these columns to the values to which a bitwise operation is to be applied. For all subsequent rows, we will remove 4 lower bits from each value.
* Columns $x_0$, $x_1$, $x_2$, $x_3$, $y_0$, $y_1$, $y_2$, $y_3$ will contain lower 4 bits of their corresponding values.
* Output column $z$. This column will be used to aggregate the results of bitwise operations performed over columns $x_0$, $x_1$, $x_2$, $x_3$, $y_0$, $y_1$, $y_2$, $y_3$. By the time we get to the last row in each 8-row cycle, this column will contain the final result.
* Column $p$ will contain increasing powers of $16$ and will aid in aggregation of bitwise results into column $z$.

## Example
Let's illustrate the above table on a concrete example. For simplicity, we'll use 16-bit values, and thus, we'll only need 4 rows to complete the operation (rather than 8 for 32-bit values). Let's say $x = 41851$ (`b1010_0011_0111_1011`) and $y = 40426$ (`b1001_1101_1110_1010`), then $and(x, y) = 33130$ (`b1000_0001_0110_1010`). The table for this computation looks like so:

| r | x | y | x0 | x1 | x2 | x3 | y0 | y1 | y2 | y3 | z | p |
| :-: | :---: | :----: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :---: | :--: |
| 0 | 41851 | 40426 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 10 | 1 |
| 1 | 2615 | 2526 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 106 | 16 |
| 2 | 163 | 157 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 362 | 256 |
| 3 | 10 | 9 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 33130 | 4096 |

Here, in the first row, we set $x$ and $y$ columns to their corresponding values. The bit columns ($a_0 .. a_3$ and $b_0 .. b_3$) in the first row contain the lower 4 bits of their corresponding values (`b1101` and `b1010`). Column $z$ contains the result of bitwise AND for the lower 4 bits (`b1010`).

With every subsequent row, we inject the next 4 bits of each value into the bit columns, reduce the $x$ and $y$ columns accordingly, and aggregate the result of bitwise AND into the $z$ column. By the time we get to the last row, $z$ column contains the result of bitwise AND, while columns $x$ and $y$ contain the 4 most significant bits of their original values.

## Constraints
AIR constraints needed to ensure the correctness of the above table are described below.

### Row address
As mentioned above, row address values should be simply incremented by one with each row. Denoting $r$ as the value of column $r$ in the current row, and $r'$ as the value in column $r$ in the next row, we can enforces this constraint as follows:

$$
r' - (r + 1) = 0
$$

### Input decomposition
We need to make sure that inputs $x$ and $y$ are decomposed correctly into their individual bits. To do this, first, we need to make sure that columns $x_0$, $x_1$, $x_2$, $x_3$, $y_0$, $y_1$, $y_2$, $y_3$, can contain only binary values ($0$ or $1$). This can be accomplished with the following constraints (for $i$ ranging between $0$ and $3$):

$$
x_i^2 - x_i = 0
$$

$$
y_i^2 - y_i = 0
$$

Then, we need to make sure that for all rows in an 8-row cycle except for the last one, the values in $x$ and $y$ columns are reduced by the values contained in the individual bit columns $x_i$ and $y_i$. Denoting $x$ as the value of column $x$ in the current row, and $x'$ as the value of column $x$ in the next row, we can enforce these conditions as follows:

$$
k_1 \cdot \left(x' \cdot 16 - \left(x - \sum_{i=0}^3(2^i \cdot x_i)\right)\right) = 0
$$

$$
k_1 \cdot \left(y' \cdot 16 - \left(y - \sum_{i=0}^3(2^i \cdot y_i)\right)\right) = 0
$$

The above constraints enforce that when $k_1 = 1$ , $x' = \frac{1}{16} \cdot \left(x - \sum_{i=0}^3(2^i \cdot x_i)\right)$ and $y' = \frac{1}{16} \cdot \left(y - \sum_{i=0}^3(2^i \cdot y_i)\right)$.

Lastly, we need to make sure that on the last row of every 8-row cycle, the values remaining in the columns $x$ and $y$ are exactly equal to the aggregation of binary values contained in the individual bit columns $x_i$, and $y_i$. This can be enforced with the following constraints:

$$
(1 - k_1) \cdot \left(x - \sum_{i=0}^3(2^i \cdot x_i)\right) = 0
$$

$$
(1 - k_1) \cdot \left(y - \sum_{i=0}^3(2^i \cdot y_i)\right) = 0
$$

The above constraints enforce that when $k_1 = 0$, $x = \sum_{i=0}^3(2^i \cdot x_i)$ and $y = \sum_{i=0}^3(2^i \cdot y_i)$.

### Output aggregation
To ensure correct aggregation of operations over individual bits, first, we need to make sure that column $p$ contains increasing powers of $16$ reset every 8th row. This can be enforced with the following constraints:

$$
k_0 \cdot (p - 1) = 0
$$

$$
k_1 \cdot (p' - p \cdot 16 ) = 0
$$

Then, we need to ensure that in the first row of every 8-row cycle, value in column $z$ is exactly equal to the aggregated values of a bitwise operation applied to columns $x_0$, $x_1$, $x_2$, $x_3$, $y_0$, $y_1$, $y_2$, $y_3$. For an AND operation, constraint enforcing this would look as follows:

$$
k_0 \cdot \left(z - \sum_{i=0}^3(2^i \cdot x_i \cdot y_i)\right) = 0
$$

Lastly, we need to ensure that for all other rows, value in the $z$ column is computed by adding the value from the previous row of the column to the bitwise operation applied to the next set of bits of $x$ and $y$. This can be enforced with the following constraint:

$$
k_1 \cdot \left(z' - z + p' \cdot \sum_0^3(2^i \cdot x'_i \cdot y'_i)\right) = 0
$$

The above constraint enforces that when $k_1 = 1$, $z' = z + p' \cdot \sum_{i=0}^3(2^i \cdot x'_i \cdot y'_i)$

## Permutation product
For the permutation product, we want to include values of $x$ and $y$ at the first row of every 8-row cycle, and value of $z$ at the last row of the cycle. Denoting the random value received from the verifier as $\alpha$, this can be achieved using the following:

$$
v_i = k_0 \cdot (\alpha \cdot r + \alpha^2 \cdot x + \alpha^3 \cdot y) + (1-k_1) \cdot (\alpha \cdot r + \alpha^2 \cdot z)
$$

Thus, when $k_0 = 1$, $(\alpha \cdot r + \alpha^2 \cdot x + \alpha^3 \cdot y)$ is included into the product, and when $k_1 = 0$, $(\alpha \cdot r + \alpha^2 \cdot z)$ gets included into the product.

Then, denoting another random value sent by the verifier as $\beta$, and setting $m = k_0 + (1 - k_1)$, we can compute the permutation product as follows:

$$
\prod_{i=0}^n ((\beta + v_i) \cdot m_i + 1 - m_i)
$$

The above ensures that when $k_0 + (1 - k_1) = 0$ (which is true for all rows in the 8-row cycle except for the first and the last one), the product does not change. Otherwise, $(\beta + v_i)$ gets included into the product.

## Table lookups
To perform a lookup into this table, we need to know values of $r$, $x$, $y$, $z$ (which the prover will provide non-deterministically). The lookup can then be performed by including the following into the lookup product:

$$
\left(\beta + (\alpha \cdot r + \alpha^2 \cdot x + \alpha^3 \cdot y)\right) \cdot \left(\beta + (\alpha \cdot (r + 7) + \alpha^2 \cdot z)\right)
$$

## Reducing the number of rows
It is possible to reduce the number of rows in the table from 8 to 4 by performing bitwise operations on 2-bit values (rather than on single bits). This would require some changes to the constraints, most important of which are listed below.

### Limit column values to 2 bits
We'll need to make sure that $x_0 .. x_3$ and $y_0 .. y_3$ columns contain 2-bit values. This can be accomplished with the following constraints:

$$
x_i \cdot (x_i - 1) \cdot (x_i - 2) \cdot (x_i - 3) = 0
$$

$$
y_i \cdot (y_i - 1) \cdot (y_i - 2) \cdot (y_i - 3) = 0
$$

### Bitwise operations on 2-bit limbs
Instead of simple formulas for single-bit bitwise operations, we'll need to compute results of bitwsie operations over 2-bit values using a sum of degree 6 polynomials.

For example, assuming $x$ and $y$ are 2-bit values, their bitwise AND can be computed as a sum of the following polynomials:

$$
\frac{1}{4} \cdot x \cdot (x - 2) \cdot (x - 3) \cdot y \cdot (y - 2) \cdot (y - 3)
$$

$$
\frac{1}{12} \cdot x \cdot (x - 2) \cdot (x - 3) \cdot y \cdot (y - 1) \cdot (y - 2)
$$

$$
\frac{1}{2} \cdot x \cdot (x - 1) \cdot (x - 3) \cdot y \cdot (y - 1) \cdot (y - 3)
$$

$$
-\frac{1}{6} \cdot x \cdot (x - 1) \cdot (x - 3) \cdot y \cdot (y - 1) \cdot (y - 2)
$$

$$
\frac{1}{12} \cdot x \cdot (x - 1) \cdot (x - 2) \cdot y \cdot (y - 2) \cdot (y - 3)
$$

$$
-\frac{1}{6} \cdot x \cdot (x - 1) \cdot (x - 2) \cdot y \cdot (y - 1) \cdot (y - 3)
$$

$$
\frac{1}{12} \cdot x \cdot (x - 1) \cdot (x - 2) \cdot y \cdot (y - 1) \cdot (y - 2)
$$

We can compute 2-bit results for OR and XOR operations in a similar manner. The general idea here is that we need to list polynomials which evaluate to $1$ for a given set of input values, and then multiply each polynomial by an expected result of a bitwise operation.

For example, to compute a bitwise OR of $3$ and $3$, we first need to come up with a polynomial which evaluates to $1$ for $x = 3$ and $y = 3$, and to $0$ for all other inputs. This polynomial is:

$$
\frac{1}{36} \cdot x \cdot (x - 1) \cdot (x - 2) \cdot y \cdot (y - 1) \cdot (y - 2)
$$

And then, since $or(3, 3) = 3$, we need to multiply this polynomial by $3$, obtaining:

$$
\frac{1}{12} \cdot x \cdot (x - 1) \cdot (x - 2) \cdot y \cdot (y - 1) \cdot (y - 2)
$$

We then repeat this process for all $x$ and $y$ where $or(x, y) \ne 0$ to obtain all required polynomials.