This section contains various ideas and snippets that you might find useful while writing halo2 circuits.
A common constraint used in R1CS circuits is the boolean constraint: . This constraint can only be satisfied by or .
In halo2 circuits, you can similarly constrain a cell to have one of a small set of values. For example, to constrain to the range , you would create a gate of the form:
while to constrain to be either 7 or 13, you would use:
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 ). 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 will constrain to be equal to one of where the latter can be arbitrary polynomials, as long as the whole expression stays within the maximum degree bound.
We can use Lagrange interpolation to create a polynomial constraint that maps for small sets of .
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:
Then, we construct the Lagrange basis polynomial for each point using the identity: where is the number of data points. ( in our example above.)
Recall that the Lagrange basis polynomial evaluates to at and at all other
Continuing our example, we get four Lagrange basis polynomials:
Our polynomial constraint is then