# Tips and tricks

This section contains various ideas and snippets that you might find useful while writing halo2 circuits.

## Small range constraints

A common constraint used in R1CS circuits is the boolean constraint: $b∗(1−b)=0$. This constraint can only be satisfied by $b=0$ or $b=1$.

In halo2 circuits, you can similarly constrain a cell to have one of a small set of values. For example, to constrain $a$ to the range $[0..5]$, you would create a gate of the form:

$a⋅(1−a)⋅(2−a)⋅(3−a)⋅(4−a)=0$

while to constraint $c$ to be either 7 or 13, you would use:

$(7−c)⋅(13−c)=0$

The underlying principle here is that we create a polynomial constraint with roots at each value in the set of possible values we want to allow. In R1CS circuits, the maximum supported polynomial degree is 2 (due to all constraints being of the form $a∗b=c$). In halo2 circuits, you can use arbitrary-degree polynomials - with the proviso that higher-degree constraints are more expensive to use.

Note that the roots don't have to be constants; for example $(a−x)⋅(a−y)⋅(a−z)=0$ will constrain $a$ to be equal to one of ${x,y,z}$ where the latter can be arbitrary polynomials, as long as the whole expression stays within the maximum degree bound.

## Small set interpolation

We can use Lagrange interpolation to create a polynomial constraint that maps $f(X)=Y$ for small sets of $X∈{x_{i}},Y∈{y_{i}}$.

For instance, say we want to map a 2-bit value to a "spread" version interleaved with zeros. We first precompute the evaluations at each point:

$00→000001→000110→010011→0101 ⟹⟹⟹⟹ 0→01→12→43→5 $

Then, we construct the Lagrange basis polynomial for each point using the identity: $l_{j}(X)=0≤m<k,m=j∏ x_{j}−x_{m}x−x_{m} ,$ where $k$ is the number of data points. ($k=4$ in our example above.)

Recall that the Lagrange basis polynomial $l_{j}(X)$ evaluates to $1$ at $X=x_{j}$ and $0$ at all other $x_{i},j=i.$

Continuing our example, we get four Lagrange basis polynomials:

$l_{0}(X)l_{1}(X)l_{2}(X)l_{3}(X) ==== (−3)(−2)(−1)(X−3)(X−2)(X−1) (−2)(−1)(1)(X−3)(X−2)(X) (−1)(1)(2)(X−3)(X−1)(X) (1)(2)(3)(X−2)(X−1)(X) $

Our polynomial constraint is then

$⟹ f(0)⋅l_{0}(X)0⋅l_{0}(X) ++ f(1)⋅l_{1}(X)1⋅l_{1}(X) ++ f(2)⋅l_{2}(X)4⋅l_{2}(X) ++ f(3)⋅l_{3}(X)5⋅l_{3}(X) −− f(X)f(X) == 00. $