# notes on range check $RC$ custom gate

Let $RC_{d,e}$ be a range check custom gate to check that $d \leq x \leq e$ where $d, e, x \in \mathbb{F}_{n}$ and $d<e$ and $e-d < n$.

Let $t_{d,e}$ be the plookup table used by $RC_{d,e}$ to prove that a witness value exist in this table. With this setup, for every $RC_{d,e}$ with different d and e parameters, a new $t_{d,e}$ should be added to the system.

Suppose we wish to use a unique custom gate. We split the check equation $d \leq x \leq e$ in two different equations: $d \leq x$ and $x \leq e$. If we arrange this equations to $x-d \ge 0$ and $e-x \ge 0$ we can reduce to unique range check gate $RC_{0,n}$, from now on $RC$, to check both equations. Thus, we reduce also to a unique plookup table $t_{0,n}$, from now on $t_{RC}$.

The new range check gate has three inputs $d , e \text{ and } x$, where $d$ is the range check lower bound, $e$ is the range check upper bound and $x$ is the value we want to check. The gate has no outputs.

## Range check custom gate on CIRCOM

customGate RangeCheck() {
    signal input lower_bound;
    signal input upper_bound;
    signal input to_check;
    
    assert(lower_bound <= to_check
           && to_check <= upper_bound);

}

...

pragma customGates;

template Foo() {
    signal input lower_bound;
    signal input upper_bound;
    signal input toCheck;

    custom_component rangeCheck = RangeCheck();

    rangeCheck.lower_bound <== lower_bound;
    rangeCheck.upper_bound <== upper_bound;
    rangeCheck.to_check    <== to_check;

    ...
}

## Adapting PlonK to use range check custom gate
In terms of PlonK, we have to its equation to:

$$q_{L_i}a_i + q_{R_i}b_i + q_{O_i}c_i + q_{M_i}a_ib_i + q_{C_i} + q_{K_i}(-q_{L_i}a_i - q_{R_i}b_i) = 0$$

For each range check gate $RC$ we generate two PlonK gates, corresponding to equations $x-d \ge 0$ and $e-x \ge 0$, as following:

$$
x-d \ge 0 \quad
\begin{cases}
q_L = 1 \\
q_R=-d,\: b=1 \\
q_O=q_M=q_C=0 \\
q_{K}=1 \\
\end{cases}
$$

$$
e-x \ge 0 \quad
\begin{cases}
q_L = -1 \\
q_R=e,\: b=1 \\
q_O=q_M=q_C=0 \\
q_{K}=1 \\
\end{cases}
$$

Note with this setup we use only a plookup table for all range check gates on the circuit. On the other hand for each range check gate we generate two PlonK gates.