Decomposition

Given a field element $\alpha$, these gadgets decompose it into $W$ $K$-bit windows $$\alpha =k_0+2^K\cdot k_1+2^{2K}\cdot k_2+\cdots +2^{(W-1)K}\cdot k_{W-1}$$ where each $k_i$ a $K$-bit value.

This is done using a running sum $z_i,i\in [\mathrm{0..}W).$ We initialize the running sum $z_0=\alpha ,$ and compute subsequent terms $z_{i+1}=\frac{z_i-k_i}{2^K}.$ This gives us:

$$\begin{array}{rl}{z}_0& =\alpha \\ & =k_0+2^K\cdot k_1+2^{2K}\cdot k_2+2^{3K}\cdot k_3+\cdots ,\\ z_1& =(z_0-k_0)/2^K\\ & =k_1+2^K\cdot k_2+2^{2K}\cdot k_3+\cdots ,\\ z_2& =(z_1-k_1)/2^K\\ & =k_2+2^K\cdot k_3+\cdots ,\\ & ⋮\\ \downarrow & \text{ (in strict mode)}\\ z_W& =(z_{W-1}-k_{W-1})/2^K\\ & =0\text{ (because }{z}_{W-1}=k_{W-1}\text{)}\end{array}$$

Strict mode

Strict mode constrains the running sum output $z_W$ to be zero, thus range-constraining the field element to be within $W\cdot K$ bits.

In strict mode, we are also assured that $z_{W-1}=k_{W-1}$ gives us the last window in the decomposition.

Lookup decomposition

This gadget makes use of a $K$-bit lookup table to decompose a field element $\alpha$ into $K$-bit words. Each $K$-bit word $k_i=z_i-2^K\cdot z_{i+1}$ is range-constrained by a lookup in the $K$-bit table.

The region layout for the lookup decomposition uses a single advice column $z$, and two selectors $q_{lookup}$ and $q_{running}.$ $$\begin{array}{ccc}z& q_{lookup}& q_{running}\\ z_0& 1& 1\\ z_1& 1& 1\\ ⋮& ⋮& ⋮\\ z_{n-1}& 1& 1\\ z_n& 0& 0\end{array}$$

Short range check

Using two $K$-bit lookups, we can range-constrain a field element $\alpha$ to be $n$ bits, where $n\le K.$ To do this:

1. Constrain $0\le \alpha <2^K$ to be within $K$ bits using a $K$-bit lookup.
2. Constrain $0\le \alpha \cdot 2^{K-n}<2^K$ to be within $K$ bits using a $K$-bit lookup.

The short variant of the lookup decomposition introduces a $q_{bitshift}$ selector. The same advice column $z$ has here been renamed to $\text{word}$ for clarity: $$\begin{array}{cccc}\text{word}& q_{lookup}& q_{running}& q_{bitshift}\\ \alpha & 1& 0& 0\\ {\alpha }^{\prime }& 1& 0& 1\\ 2^{K-n}& 0& 0& 0\end{array}$$

where ${\alpha }^{\prime }=\alpha \cdot 2^{K-n}.$ Note that $2^{K-n}$ is assigned to a fixed column at keygen, and copied in at proving time. This is used in the gate enabled by the $q_{bitshift}$ selector to check that $\alpha$ was shifted correctly: $$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 2& q_{bitshift}\cdot ((\alpha \cdot 2^{K-n})-{\alpha }^{\prime })\end{array}$$

Combined lookup expression

Since the lookup decomposition and its short variant both make use of the same lookup table, we combine their lookup input expressions into a single one:

$$q_{lookup}\cdot \left(q_{running}\cdot (z_i-2^K\cdot z_{i+1})+(1-q_{running})\cdot \text{word}\right)$$

where $z_i$ and $\text{word}$ are the same cell (but distinguished here for clarity of usage).

Short range decomposition

For a short range (for instance, $[0,\text{range})$ where $\text{range}\le 8$), we can range-constrain each word using a degree-$\text{range}$ polynomial constraint instead of a lookup: $$\text{range\_check}(word,range)=\text{word}\cdot (1-\text{word})\cdots (\text{range}-1-\text{word}).$$