# On the cost of lookups in SHA

[TOC]

## In short
We want to understand:
> *How many lookups (and of which size) are there in SHA256?*

Once we know that we can assess how much it would cost to have that implemented through a lookup argument such as Baloo or Caulk.

Before asking this question more precisely we establish some notation through examples. (or just jump to a [more precise version of the question](https://hackmd.io/GHOhPwE6RVG7Nq8y3IuLJA?both#Back-to-the-original-question) if you are in a hurry and you know the stuff).

## An example circuit using lookups
**NB:** Please note the following is just an example---there are probably better ways to perform the same computation.

Consider the following circuit with two witnesses of size $n$:
- $w = (w_1, \dots, w_n)$
- $w' = (w'_1, \dots, w'_n)$

The computation requires this:
- all of the $w_i$-s are bytes
- the second witness is a XOR of the first and second half of the first one. That is, for each $i$, $w'_i = w_{\uparrow,i} \oplus w_{\downarrow,i}$
where the upward and downward arrow indicate respectively the left-most and right-most 4-bits of the byte $w_i$ (Example: if $w_i = 01001100$ then $w_{\uparrow,i} = 0100$)

### How to implement this with lookup arguments

Recall what a lookup does: given a table $T$ it allows us to look up values in it. The function (four-bit) XOR, for example, can be implemented as a lookup table $T_{XOR}$ storing:

| a | b | a XOR b |
| -------- | -------- | -------- |
| 0000 | 0000 | 0000 |
| ... | ... | ... |
| 0100 | 0110 | 0010 |
| ... | ... | ... |

This table has $2^4 = 16$ rows.

Using the table above the prover can provide a commitment to the $w_{\uparrow,i}$-s and $w_{\downarrow,i}$-s and show
$(w_{\uparrow,i}, w_{\downarrow,i}, w'_i) \in T_{XOR}$ through a lookup argument. (other assumptions we are making: 1) the w and w'-s are also committed somewhere; 2) we also---in some other way (ignore it for the sake of this note)---need to show that $w_i = 2^4\cdot w_{\uparrow,i} + w_{\downarrow,i}$)

Another table we can use is the one for checking that w_i-s are bytes. This table $T_{byte}$ would just consist of a single column like this one:

| a |
| -------- |
| 00000000 |
| 00000001 |
| ... |
| 10010110 |
| ... |
| 11111111 |

This table has $2^8 =256$ rows.

## Cost of lookups

The *main* cost in lookup arguments for proving time often hinges on
how many lookups we are carrying out. (In the examples above, we are doing $n$ lookups per table, the length of $w$ and $w'$). Call this number $m$.

The number of rows in a table (in our examples above, 16 and 256) affect the complexity of the preprocessing stage. Call this value $N$.

The number of column plays a role, but it tends to be minor: all columns in a table can be "compressed" into one and everything reduces to a single-column lookup (if this does not make sense, ignore it, but trust that it is simple).

For example the cost in Baloo is the following:

What if we have many tables, say $k$ of them? There are two ways there.
- We can perform one lookup argument per table (possibly in parallel)
- somewhat further "compress" all lookups.

The extent to which we can use the second option depends a lot on the specific setting. Therefore for sake of simplicity we just consider the naive case for now, that is we perform $k$ lookup arguments.

## Back to the original question
Now that we established some notation, we can return to our question rephrasing it as such:

> *What are $N,m,k$ in SHA256?*

## An additional question
Lookups may not be sufficient on their own in a computation (see, e.g. $w = 2^4\cdot w_{\uparrow,i} + w_{\downarrow,i}$ in the previous computation(ignore one could do a lookup there too), or imagine that we needed to perform some other consistency checks among wires)
So another question is
> What other checks does one need to perform besides lookups in SHA?

## For more resources on SHA with lookups and lookups in hashing

https://hackmd.io/@7dpNYqjKQGeYC7wMlPxHtQ/BJpNmNW0L#4SHA-256

https://anoma.net/blog/hash-functions-in-plonkup/