## Lookup tables

Let
- $comp(x,y,z) = 2^{21}·x + 2^{10}·y + z$, where $(x,y,z) \in [2^{11}] \times [2^{11}] \times [2^{10}]$.
- $w^{\rightarrow n}$ be a right bitwise rotation by n positions of the word w
- $w^{\Rightarrow n}$ be a right bitwise shift by n positions of the word w

We define:

1. $T_{maj} := \{(x,y,z; w): w = \text{bitwise majority of } x, y, z\}$, where $x,y,z,w \in [2^{11}]$
2. $T_{ch} := \{(x,y,z; w): w = \text{bitwise choose of } x, y, z\}$, where $x,y,z,w \in [2^{11}]$
3. $T_{rot0} := \{(x,y,z; w): w = \sigma^{\rightarrow 2} \oplus \sigma^{\rightarrow 13} \oplus \sigma^{\rightarrow 22}\}$, where $(x,y,z) \in [2^{11}] \times [2^{11}] \times [2^{10}], w \in [2^{32}], \sigma = comp(x,y,z)$
4. $T_{rot1} := \{(x,y,z; w): w = \sigma^{\rightarrow 6} \oplus \sigma^{\rightarrow 11} \oplus \sigma^{\rightarrow 25}\}$, where $(x,y,z) \in [2^{11}] \times [2^{11}] \times [2^{10}], w \in [2^{32}], \sigma = comp(x,y,z)$
5. $T_{dec} := \{(w; x,y,z): comp(x,y,z) = w \mod 2^{32}\}$, where $(x,y,z) \in [2^{11}] \times [2^{11}] \times [2^{10}], w \in [7 · 2^{32}]$
6. $T_{w1} := \{(w; w'): w' = w^{\rightarrow 7} \oplus w^{\rightarrow 18} \oplus w^{\Rightarrow 3}\}$, where $w, w' \in [2^{32}]$
7. $T_{w2} := \{(w; w'): w' = w^{\rightarrow 17} \oplus w^{\rightarrow 19} \oplus w^{\Rightarrow 10}\}$, where $w, w' \in [2^{32}]$
8. $T_{mod} := \{(w; w'): w' = w \mod 2^{32}\}$, where $w \in [4 · 2^{32}], w \in [2^{32}]$

Sizes: 1 table of size $7 · 2^{32}$, 1 table of size $2^{34}$, 2 tables of size $2^{33}$, 4 tables of size $2^{32}$.

## Gates equations

Let $R$ be the number of rows per round (currently it is $4$). Let $A_i$ be the $i$th advice column. Let $I$ be the public input (instance) column. Let $F$ be the fixed column.

### Summary

1. $13$ lookups per round plus $8$ at the end
2. max degree (excluding lookups): $n$
3. offsets (excluding lookups): $\{0, g, g^3, g^{-1}, g^{-2}, g^{-3R}, g^{-2R + 2}, g^{-7R}, g^{-15R + 2}, g^{-16R}\}$ ($10$ different offsets)
4. offsets in lookups: $\{0, g, g^2, g^3, g^{-R}, g^{-2R}\}$ ($6$ different offsets)

### Lookup gate

- [rot0(a)] $(A_0(X), A_1(X), A_2(X); A_0(g·X))\in T_{rot0}$
- [rot1(e)] $(A_3(X), A_4(X), A_5(X); A_4(g·X))\in T_{rot1}$
- [maj_x] $(A_0(X), A_0(g^{-R}·X), A_0(g^{-2R}·X); A_1(g·X))\in T_{maj}$
- [maj_y] $(A_1(X), A_1(g^{-R}·X), A_1(g^{-2R}·X); A_2(g·X))\in T_{maj}$
- [maj_z] $(A_2(X), A_2(g^{-R}·X), A_2(g^{-2R}·X); A_3(g·X))\in T_{maj}$
- [ch_x] $(A_3(X), A_3(g^{-R}·X), A_3(g^{-2R}·X); A_5(g·X))\in T_{ch}$
- [ch_y] $(A_4(X), A_4(g^{-R}·X), A_4(g^{-2R}·X); A_6(g·X))\in T_{ch}$
- [ch_z] $(A_5(X), A_5(g^{-R}·X), A_5(g^{-2R}·X); A_7(g·X))\in T_{ch}$
- [message schedule] $(A_6(g^2·X); A_6(X)) \in T_{w1}$
- [message schedule] $(A_7(g^2·X); A_6(X)) \in T_{w2}$

Max degree (excluding lookup): $0$
Offsets (excluding lookup): $\{\}$

### Composition gate

- [majority] $A_0(g·X) = 2^{21} · A_1(X) + 2^{10} · A_2(X) + A_3(X)$
- [choose] $A_1(g·X) = 2^{21} · A_5(X) + 2^{10} · A_6(X) + A_7(X)$
- [hash word d] $A_2(g·X) = 2^{21} · A_0(g^{-3R}·X) + 2^{10} · A_1(g^{-3R}·X) + A_2(g^{-3R}·X)$
- [hash word h] $A_3(g·X) = 2^{21} · A_3(g^{-3R}·X) + 2^{10} · A_4(g^{-3R}·X) + A_5(g^{-3R}·X)$

Max degree (excluding lookup): $n$
Offsets (excluding lookup): $\{0, g, g^{-3R}\}$

### Addition gate

- [A] $A_0(g·X) = F(X) + A_0(X) + A_1(X) + A_3(X) + A_0(g^{-1}·X) + A_4(g^{-1}·X) + A_6(g^{-2}·X)$
- [E] $A_1(g·X) = F(X) + A_1(X) + A_2(X) + A_3(X) + A_4(g^{-1}·X) + A_6(g^{-2}·X)$

Max degree (excluding lookup): $n$
Offsets (excluding lookup): $\{0, g, g^{-1}, g^{-2}\}$

### Decomposition gate

- [hash word a] $(A_0(X); A_0(g·X), A_1(g·X), A_2(g·X)) \in T_{dec}$
- [hash word e] $(A_1(X); A_3(g·X), A_4(g·X), A_5(g·X)) \in T_{dec}$

Max degree (excluding lookup): $0$
Offsets (excluding lookup): $\{\}$

### Witness computation gate

- [summation in field] $A_7(X) = A_7(g^{-2R + 2}·X) + A_6(g^{-7R}·X) + A_6(g^{-15R + 2}·X) + A_6(g^{-16R}·X)$
- [truncation] $(A_7(X); A_6(X)) \in T_{mod}$

Max degree (excluding lookup): $n$
Offsets (excluding lookup): $\{0, g^{-2R + 2}, g^{-7R}, g^{-15R + 2}, g^{-16R}\}$

### Result verification gate

- [lower hash word] $A_{0}(X) · 2^{21} + A_{1}(X) · 2^{10} + A_{2}(X) + F(X) = A_2(g^3·X)$
- [second hash word] $A_{3}(X) · 2^{21} + A_{4}(X) · 2^{10} + A_{5}(X) + F(g·X) = A_3(g^3·X)$
- $(A_2(g^3·X), I(X)) \in T_{mod}$
- $(A_3(g^3·X), I(g·X)) \in T_{mod}$

Max degree (excluding lookup): $n$
Offsets (excluding lookup): $\{0, g, g^3\}$