Range check solution 2 (interactive)

(Solution by Alex Ozdemir)

If we allow prover and verifier to interact, we can do this range check in just 48 quadratic constraints plus one additional round of interaction.

This protocol requires a challenge from the verifier. In other words: The prover will commit to some witnesses; the verifier will send a randomly-chosen challenge; and then the prover will produce more witnesses and finish the proof.

As usual, this protocol can be made non-interactive using the Fiat-Shamir heuristic.

The idea is to do the original fixed-size range check using a lookup argument. So suppose you have an $x$, and you just want to check that $0 \leq x < 2^{64}$. Our original binary-expansion protocol checks this with 64 quadratic constraints; this lookup argument will reduce it to 32 quadratic constraints.

We can check $0 \leq x < y$ by performing two fixed-size range checks: one on $x$ and one on $y-x$. The cost of multiple lookup arguments can be amortized. While one fixed-size range check requires 32 constraints, we will be able to do two of them in just 48 constraints.

The idea is simple: to prove that $x$ lies in range, we will expand $x$ in base $16$ as

$$x = a_0 + 16 a_1 + 16^2 a_2 + \cdots + 16^{15} a_{15},$$

where each $a_i$ lies in

$$a_i \in \{ 0, 1, \ldots, 15 \}.$$

OK, so now the problem is: How do we check that each $a_i$ lies between 0 and 16? This is a classic example of a lookup argument.

We’re going to do it using what’s called the “logarithmic derivative trick”; the same trick is used in the cq paper, for instance. (The name “logarithmic derivative” is a little strange, since it involves neither logarithms nor derivatives.)

Remember where we are: The prover has 16 witnesses $a_0, \ldots, a_{15}$, each of which must be one of the 16 values $0, \ldots, 15$.

The prover is going to compute another 16 values $c_0, c_1, \ldots, c_{15}$. The letter $c$ stands for “count”: $c_j$ is the number of $a$’s that are equal to $j$, for each $i$.

Now, for any $T$, the equality

$$\sum_{i=0}^{15} \frac{1}{T - a_i} = \sum_{j=0}^{15} \frac{c_j}{T - j}$$

must hold, because both sides have the same terms. And conversely, if constants $a_i$ and $c_j$ are such that the equality holds for randomly chosen $T$, then both sides must be the same rational function of $T$. We won’t give a full algebraic proof here, but if the two sides are the same rational function, then each $a_i$ must be equal to some $j$.

So, here’s the full protocol.

• Prover commits to the constants $a_i$ and $c_j$.
• Verifier sends a random challenge $T$.
• Prover commits to additional constants $$b_i = \frac{1}{T - a_i}$$ and $$d_j = \frac{c_j}{T - j}.$$
• Prover proves the following constraints (of which 32 are quadratic): $$\begin{aligned} \sum_{i=0}^{15} {16}^i a_i &= x \\ \sum_{i=0}^{15} b_i &= \sum_{i=0}^{15} d_j \\ b_i (T - a_i) &= 1 \\ d_j (T - j) &= c_j. \end{aligned}$$

This proves that each $a_i$ lies in the list $0, \ldots, 15$, so $0 \leq x < 16^{16} = 2^{64}$, using just 32 constraints.

Returning to the original problem, if you want to prove that $0 \leq x < y$, you could just perform range checks on both $x$ and $y-x$, for a total of 64 constraints.

But in fact we can cut it down to 48 constraints by amortizing the lookups. Suppose we write

$$\begin{aligned} x &= a_0 + 16 a_1 + 16^2 a_2 + \cdots + 16^{15} a_{15} \\ y &= a'_0 + 16 a'_1 + 16^2 a'_2 + \cdots + 16^{15} a'_{15}. \end{aligned}$$

We need to show that all the variables $a_i$ and $a'_i$ are in the set $\{0, 1, \ldots, 15\}$. To do this, let $c_j$ be the number of $a_i$’s and $a'_i$’s combined that are equal to $j$.

So now there are 32 witnesses $a_i$ and $a'_i$, but there are still only 16 witnesses $c_j$ for both range checks combined.

Now the equality we want to prove is

$$\sum_{i=0}^{15} \frac{1}{T - a_i} + \sum_{i=0}^{15} \frac{1}{T - a'_i} = \sum_{j=0}^{15} \frac{c_j}{T - j}.$$

We’ll use the same trick as before: Since you can’t do a division in-circuit, the prover will commit to the value of each fraction. So each fraction above translates to one multiplicative constraint to be verified. Since there are 48 fractions in total, we end up with 48 constraints.

Here’s the full protocol.

• Prover commits to the constants $a_i$, $a'_i$, and $c_j$.
• Verifier sends a random challenge $T$.
• Prover commits to additional constants $$\begin{aligned} b_i &= \frac{1}{T - a_i} \\ b'_i &= \frac{1}{T - a_i} \\ d_j &= \frac{c_j}{T - j}. \end{aligned}$$
• Prover proves the following constraints (of which 48 are quadratic): $$\begin{aligned} \sum_{i=0}^{15} {16}^i a_i &= x \\ \sum_{i=0}^{15} b_i + \sum_{i=0}^{15} b'_i &= \sum_{i=0}^{15} d_j \\ b_i (T - a_i) &= 1 \\ b'_i (T - a'_i) &= 1 \\ d_j (T - j) &= c_j. \end{aligned}$$