Range check solution 1 (public $y$ with verifier precompute)

Suppose $y$ is a public value, known to both prover and verifier. In this setting, it’s okay to ask the verifier to verify an out-of-circuit computation.

So here’s the solution. Both prover and verifier compute the largest power of 2 less than $y$; call it $2^r$. They also compute $c = y - 2^r$, which will satisfy $0 < c \leq 2^r$.

The main idea is a slight generalization of the “range check by binary expansion” trick. The integer $x$ lies in the interval $[0, y)$ if and only if we can decompose

$$x = x_0 + x_1 + \cdots + x_{63},$$

where:

$$x_i = 0 \text{ or } 2^i$$

for $i < r$,

$$x_r = 0 \text{ or } c,$$

and

$$x_j = 0$$

for $j > r$.

Let $a_i = 2^i$ for $i < r$, $a_r = c$, and $a_i = 0$ for $i > r$. These $a_i$’s, for $0 \leq i < 64$, will be public inputs to the circuit; both prover and verifier will compute them from $y$.

Additionally, the prover will produce private witnesses $x_0, \ldots, x_{63}$. These witnesses are required to satisfy:

$$\begin{aligned} x &= x_0 + x_1 + \cdots + x_{63} \\ x_0^2 &= x_0 a_0 \\ x_1^2 &= x_1 a_1 \\ & \vdots \\ x_{63}^2 &= x_{63} a_{63}. \\ \end{aligned}$$

(Notice that $x_i^2 = x_i a_i$ is satisfied if and only if $x_i$ is either $0$ or $a_i$.) This solves the problem with only 64 quadratic constraints.