# Simple R1CS range check and truncation

*Dmitry Khovratovich, 2022*

Here is a method to make a range check in R1CS against an $n$-bit constant $X\in[2^{n-1};2^n)$ with exactly $n$ multiplicative constraints.

## Range Check

### Integer form
For this we note that $a<X$ if and only if $a=(X-2^{n-1})b + c$ where $b\in\{0,1\}$ and $c<2^{n-1}$. Therefore the range check is equivalent to the system of $n$ multiplicative and 1 additive constraints
$$
\begin{cases}
a = (X-2^{n-1})a_{n-1} + \sum_{0\leq i \leq n-2} a_i 2^{i};\\
(a_i-1)a_i=0;\quad 0\leq i \leq n-1.
\end{cases}
$$
Note that the resulting decomposition is not unique but for a number of applications it is not a problem.

**Example**:
$$
a<47\;\Leftrightarrow\;
\begin{cases}
a = 15a_{5} + 16a_4 +8a_3 + 4a_2+2a_1 + a_0;\\
(a_i-1)a_i=0;\quad 0\leq i \leq 5.
\end{cases}
$$

### Binary form

If $a$ is given in the binary representation ($b_s b_{s-1}\ldots b_1 b_0$)it is almost as simple. Let $p$ be the field size.
* If $\log_2 p>n$ then we simply check that higher bits up to $b_{n}$ inclusive are 0 and then use $a=\sum_{i<n}2^ib_i$ in the constraints above.
* If $\log_2 p <n$:
* If $b_{n-1}=0$ then accept the check.
* Else make a range check $\sum_{i<n-1}2^ib_i < X-2^{n-1}$ as above

## Truncation

Truncating some bits off a binary representation of a number $A$ is not straightforward if $A$ is given as a field element. We show how to keep only $d$ least significant bits in $\lceil \log p \rceil +3$ multiplicative constraints for any number of bits.

Let us decompose the field size as $p=p_12^d+p_2$. We suggest asserting that
* $A_1\leq p_1$ with the method above using $\lceil \log p \rceil - d$ constraints.
* $A-A_2 = 2^d A_1$
* ($A_2<2^d$ if $A_1\neq p_1$) OR ($A_2<p_2$ if $A_1=p_1$).
This condition can be expressed with $d+3$ constraints:
\begin{align}
(A_1-p_1)y=z;\\
z(z-1)=0;\\
(A_1-p_1-y)(z-1)=0;\text{ (optional)}\\
A_2 = (p_2-2^{d-1}+z(2^{d}-p_2))a_{d-1} + \sum_{0\leq i \leq d-2} a_i 2^{i};\\
a_i(a_i-1)=0
\end{align}

Then $A-2^dA_1$ is the truncation of $A$ to the lowest $d$ bits.

### Truncating 1 bit

Requires only $d+2=\lceil \log p \rceil +1$ constraints

* $(A_1-1)A_1=0$
* $A- A_2 = 2^dA_1$
* $A_2 = (2^{d-1}-(2^{d}-p_2)A_1)a_{d-1}+ \sum_{0\leq i \leq d-2} a_i 2^{i};$
* $a_i(a_i-1)=0$