# Thoughts on Plookup implementation of Sha256 and Keccak

One of neat tricks used in [Barretenberg](https://github.com/AztecProtocol/barretenberg/blob/f8d91ed11f9bd6fa07b7c789498f0b93277223f2/barretenberg/src/aztec/stdlib/hash/sha256/sha256_plookup.cpp) implementation of Sha256 table-based constraint system is the special algorithm for handling majority and choose functions:
\begin{eqnarray}
maj(x, y, z) &=& (x∧y)⊕(x∧z)⊕(y∧z) \\ ch(x, y, z) &=& (x∧y)⊕(¬x∧z).
\end{eqnarray}

Instead of introducing many separate tables for each type of primitive boolean function (^, ⊕, ¬) and then applying them repeatedly in the right order, we may take the more efficient approach.

Consider the following tables:
| x | y | z | maj(x, y, z) | x + y + z |
|---|---|---|:------------:|:-----------:|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 2 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 2 |
| 1 | 1 | 0 | 1 | 2 |
| 1 | 1 | 1 | 0 | 3 |

| x | y | z | choose(x, y, z) | x + 2y + 3z |
|---|---|---|:---------------:|:-----------:|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 3 |
| 0 | 1 | 0 | 0 | 2 |
| 0 | 1 | 1 | 1 | 5 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 4 |
| 1 | 1 | 0 | 1 | 3 |
| 1 | 1 | 1 | 1 | 6 |

In these tables, third column is our logical function *log(x,y z)*, and the last column is the corresponding algebraic encoding *alg(x,y,z)*, chosen so that the transformation $f$ from *alg* $\to$ *log* is well-defined. Note that in the last table, the value 3 appears twice on two different rows but the corresponding value in the third column on those rows is the same (0).

This observations suggest introducing the following algorithm for handling complex logical operatiosn (such as **maj** and **ch**:

1) for all arguments c in (x, y, z) do:
*convertion* $c = \sum c_i 2^i$ (binary representation) to $c_{sparse} = \sum c_i b^i$ (sparse representation), where base $b$ is chosen in a way that prevents overflowing to the nearby chunk in algebraic encoding (b = 4 for **maj** and b = 7 for **ch**).
In practice this can be achieved via spliting $c$ into chunks of appropriate size, mapping each chunk to sparse representation separately (via table query), and taking linear combination of transformed chunks.
2) instead of doing logical operations on (x, y, z) apply *algebraic operations* on their sparse encodings ($x_{sparse}, y_{sparse}, z_{sparse}$). For **maj** and **ch** these algebraic operations are simply linear combinations and fit into a single PLONK gate!
3) *normalization*: convert the result back from sparse form into binary, where each chunk $[0; b-1]$ is mapped to $\{0, 1\}$ via one-to-one function $f$ discussed above.

This trick leads to more compact constrain systems in two ways:
1) it reduces the total number of tables used - instead of separate tables for each basic logic operations, we require only two: the one which converts number to sparse from, and another converting it back.
2) it reduces the total number of gates used.

However we have simplified things a little.The actual Sha256 hash mixes complex logical operations with circular rotations. Our sparse representation is friendly to the first (by design), but not to the second. Barretenberg authors solve this problem by introducing several different tables which do rotation *and* convertion to sparse form in one fell swoop. This strategy is fine to Sha256 (though not ideal) where the number of different rotation moduli is rather small, but carries serious obstacles for Keccak, where each of 25 lanes is shifted by unique modulus.

Let's see, if we could do better here. Assume, that our sparse algebraic encoding for x in base $b$ is
$$ x = \sum_i^nx_i b^i,$$ where each $x_i$ is $\in [0, c-1]$ . In fact, the only actual restriction for the choice of base $b$ is that all separate chunks $x_i$ should be uniqely decodable and retrived from $x$, or in other words:

The map $([0, c-1] \times n) \to \mathbb{F}: (x_0, \dots, x_{n}) \to \sum_i^nx_i b^i$ is injective.

The most simplest and natural choice is $b = c$, and we may also take $b = c+1$ or $b=2c$, or any larger base $b$ as long as $x = \sum_i^nx_i b^i$ doesn't wrap around modulus p of field $\mathbb{F}$. In this case, injectivity is trivial.

However, there is a special choice of base $b$ which forces x to *wrap around* $p$, but super friendly to rotations. Take $b=g$ - root of unity of order n: $$g^{n} = 1, g^i \neq 1, \forall i <= n.$$

If we still posess *injectivity* property for such choice of $b=g$, then both goals are achieved: logical operations are encoded as algebraic relations and are done on chunk-to-chunk basis and numbers are rotated by multiplication by corresponding powers of $g$. Using this, we may pack both rotations and arithmetic in the same Plonk gates.

In practice, we are mostly interested for the following special cases of this injectivity problem:
1) $c = 8, n = 32$ - for efficient implementation of Sha256 gadget.
2) $c = 8$(or at least $c=4$), $n = 64$ - for Keccak.

Note that, for Sha256 with $c = 8, n = 32$ the total number of all possible linear combinations $\sum_i x_ig^i$ is $8^{32} = 2^{3 \cdot 32} = 2^{96}$, so that injectivity cannot be checked by brute-force. If there exists rigorous *positive* solution to this injectivity problem, it will help to further reduce the number of gates and tables in Sha256 and Keccak Plookup implementations.