# $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))$$