# $2^n$-bit arithmetic in ZK without range checks
<style>
.ui-infobar, #doc.markdown-body { max-width: 1050px; }
</style>
*Dmitry Khovratovich*

**Problem**: whenever we implement an algorithm that works over $Z_{N}$, with $N=2^{16}$ or $N=2^{32}$, we need
to reduce all computations modulo $N$ and range-check all variables against $N$. These operations are expensive. We suggest a new scheme that implements the mod-$N$ arithmetic without range checks.

## 1. State of the art: Simplified Plonk

Notation: $N =2^n$.

First recall (and simplify) how Plonk arranges its witness.

| Index | Witness poly $f_1$ | $f_2$ | $f_3$ |
| ------------ | ------------------ | -------- | -------- |
| $\omega$ | | |
| $\omega^2$ | | | |
| | | | |
| $x$ | $f_1(x)$ | $f_2(x)$ | $f_3(x)$ |
| | | | |
| $\omega^N=1$ | | | |

### Identities
* Addition gate:
$$
f_3(x) = f_1(x)+f_2(x)
$$

* Multiplication gate:
$$
f_3(x) = f_1(x)\cdot f_2(x)
$$

## 2. New scheme

### Idea

* **Make all witness values to be roots of unity $V_N$.**
* **Represent $i<N$ as $\omega^i$.**
* **For each witness value $f(x)= \omega^j$ store $\omega^{\frac{j(j+1)}{2}}$ in a cell nearby as value of $f^{exp}(x)$.**
* **Ensure that the same permutation $\sigma$ maps $\{\omega,\omega^2,\ldots, \omega^N\}$ to $\{f(x)\}$ and $\{\omega,\omega^3,\omega^6,\ldots, \omega^{\frac{N(N+1)}{2}}\}$ to $\{f^{exp}(x)\}$**

### Witness table
| Index | Witness poly $f_1$ | $f_1^{exp}$ | $f_2$ | $f_2^{exp}$ | $f_3$ | $f_3^{exp}$ | $f_4$ | Value poly $g_1$ | $g_2$ |
| ------------ | --------------------- | -------------------------------------------- | -------- | -------------- | -------- | -------------- | -------- | ---------------- | --------------------------- |
| | | | | | | | | | |
| $\omega$ | | | | | | | | $\omega$ | $\omega$ |
| $\omega^2$ | | | | | | | | $\omega^2$ | $\omega^3$ |
| $\omega^3$ | | | | | | | | $\omega^3$ | $\omega^6$ |
| | | | | | | | | | |
| $x=\omega^i$ | $f_1(x)=\omega^{j_i}$ | $f_1^{exp}(x)=\omega^{\frac{j_i(j_i+1)}{2}}$ | $f_2(x)$ | $f_2^{exp}(x)$ | $f_3(x)$ | $f_3^{exp}(x)$ | $f_4(x)$ | $\omega^{i}$ | $\omega^{\frac{i(i+1)}{2}}$ |
| | | | | | | | | | |
| $\omega^N=1$ | | | | | | | | $\omega^N=1$ | $\omega^{\frac{N(N+1)}{2}}$ |

### Identities
* Consistency equations:
\begin{align}
\sigma_1:&\quad \{g_1(x)\}\rightarrow \{f_1(x)\}\\
\sigma_1:&\quad \{g_2(x)\}\rightarrow \{f_1^{exp}(x)\}\\
\sigma_2:&\quad \{g_1(x)\}\rightarrow \{f_2(x)\}\\
\sigma_2:&\quad \{g_2(x)\}\rightarrow \{f_2^{exp}(x)\}\\
\sigma_3:&\quad \{g_1(x)\}\rightarrow \{f_3(x)\}\\
\sigma_3:&\quad \{g_2(x)\}\rightarrow \{f_3^{exp}(x)\}
\end{align}

* Addition gate $(\omega^i,\omega^j)\rightarrow \omega^{i+j}$ or $f_3 = f_1 + f_2 \pmod{N}$ (in the exponent):
$$
f_3(x) = f_1(x)\cdot f_2(x)
$$

* Multiplication gate $(\omega^i,\omega^j)\rightarrow \omega^{ij}$ or $f_4 = f_1 \cdot f_2 \pmod{N}$ (in the exponent):
$$
\begin{cases}
f_3(x) = f_1(x)\cdot f_2(x);\quad \text{auxiliary variable $\omega^{i+j}$}\\
f_3^{exp}(x) = f_1^{exp}(x)\cdot f_2^{exp}(x)\cdot f_4 (x) ;\quad \text{exploit equation } \omega^{\frac{(i+j)(i+j+1)}{2}} = \omega^{\frac{i(i+1)}{2}}\cdot \omega^{\frac{j(j+1)}{2}}\cdot \omega^{ij}
\end{cases}
$$

The gates can be combined as mult gate computes addition along the way.

#### How to prove consistency equations

##### Via a lookup prover

Let $T$ be the $N$-size table consisting of $(g_1(\omega^i),g_2(\omega^i))$ pairs.

Then we prove:
$$
(f_i(X), f_i^{exp}(X))\in T\text{ for }X\in V_N.
$$
with Baloo or Caulk(+).

##### Directly

1. Commit to $f_i, f_i^{exp}$
2. Generate challenge $\alpha$.
3. Compute and prove aggregated polynomial
$$
h(X)=\prod_{1\leq i \leq N}(X-f_1(\omega^i)-\alpha f_1^{exp}(\omega^i))(X-f_2(\omega^i)-\alpha f_2^{exp}(\omega^i))(X-f_3(\omega^i)-\alpha f_3^{exp}(\omega^i))
$$
4. Compute and prove reduced poly
$$
\widehat{h}(X) = \frac{h(X)}{GCD(h(X),h'(X))}
$$

5. Prove that $\widehat{h}(X)$ divides $\psi(X)$ where
$$
\psi(X) =\prod_{1\leq i \leq N}(X-g_1(\omega^i)-\alpha g_2(\omega^i))
$$