---
breaks: false
---
$$
\def\Fp{\mathbb{F}_p}
\def\FF{\Fp^{\scriptscriptstyle{(<n)}}[X]}
\def\com{\mathbf{com}}
\def\range#1{[{#1}]}
$$
# A Simple Range Proof From Polynomial Commitments
### Dan Boneh, Ben Fisch, Ariel Gabizon, and Zac Williamson
---
Let's construct a simple zero knowledge range proof from a
hiding polynomial commitment scheme (PCS).
### The setup
Let $p$ be a prime, where $p > 2^n$ for some $n$. We want a commitment scheme for elements in $\Fp$ that allows a prover to efficiently convince a verifier that a committed quantity $z \in \Fp$ is in the range $0 \leq z < 2^n$.
We show that for a committed $z \in \Fp$, the prover can provide an HVZK proof to convince the verifier
that $0 \leq z < 2^n$ by committing to **two** polynomials of degree $(n+1)$, and running the polynomial evaluation protocol **three** times. Therefore:
- For the pairing-based polynomial commitment scheme of Kate, Zaverucha and Goldberg, this gives a range proof of length $O_\lambda(1)$ that can be verified in time $O_\lambda(1)$, with a trusted setup and an updatable SRS of size $O_\lambda(n)$.
- For the DARK polynomial commitment scheme of Bünz, Fisch, and Szepieniec, this gives a range proof of length $O_\lambda(\log n)$ that can be verified in time $O_\lambda(\log n)$, with no trusted setup.
- For comparison, recall that Bulletproofs give a range proof with no trusted setup of length $O_\lambda(\log n)$ that can be verified in time $O_\lambda(n)$.
In what follows we use $\FF$ to denote polynomials in $\Fp[X]$ of degree less than $n$. We assume that $n$ divides $p-1$ so that there is an element $\omega \in \Fp$ of order $n$. Let $H = \{1,\omega,\omega^2,\ldots,\omega^{n-1}\}$.
### The commitment scheme
Suppose that we have available a hiding and binding PCS for polynomials in $\FF$. Moreover, we assume that the polynomial evaluation protocol is HVZK.
To commit to an element $z \in \Fp$, choose an arbitrary polynomial $f \in \FF$ such that $f(1) = z$. Taking $f$ as the constant polynomial $f(X) = z$ is sufficient. The commitment to $z$ is the polynomial commitment $\com_f$ to $f$.
If the PCS is additive,
then the commitment scheme is additively homomorphic:
given commitments to $z_1$ and $z_2$ in $\Fp$,
anyone can construct a commitment to $z_1+z_2$.
### Range proof for the range $[0,2^n)$
Let $\com_f$ be a commitment to $z \in \Fp$
so that $f(1) = z$, as above.
Let $z_0, \ldots, z_{n-1} \in \{0,1\}$ be the binary digits of $z$, so that $z = \sum_{i=0}^{n-1} 2^{i} \cdot z_i$.
Now, given $\com_f$, the prover proves that $0 \leq z < 2^n$,
by constructing a degree-$(n-1)$ polynomial $g \in \FF$ such that
$$ g(\omega^{n-1}) = z_{n-1} \quad\text{and}\quad
\text{$g(\omega^{i}) = 2 g(\omega^{i+1}) + z_{i}\ $ for all $i=n-2,\ldots,0$.} $$
Observe that $g(1) = g(\omega^0) = \sum_{i=0}^{n-1} 2^{i} \cdot z_i = z$.
Now the prover needs to prove three things:
1. $\ \ g(1) = f(1)$,
2. $\ \ g(\omega^{n-1}) \in \{0,1\}$, and
3. $\ \ g(X) - 2 g(X \omega) \in \{0,1\}$
for all $x \in H \setminus \{\omega^{n-1}\}$.
Condition (1) proves that $g(1) = z$;
Conditions (2) and (3) prove that $z_0, \ldots, z_{n-1}$ are all in $\{0,1\}$ and are the binary digital of $z$.
Together, these conditions prove that $0 \leq z < 2^n$, as required.
To prove Conditions (1)-(3), the prover sends to the verifier
a polynomial commitment to $g$.
It then proves to the verifier that the following polynomials evaluate to zero for all $x \in H$:
$$ \begin{align*}
w_1(X) & = (g - f) \cdot \textstyle{\left(\frac{X^{n}-1}{X-1}\right)} , \\[2mm]
w_2(X) & = g \cdot (1 - g) \cdot \textstyle{\left(\frac{X^{n}-1}{X-\omega^{n-1}}\right)} , \quad\text{and} \\[2mm]
w_3(X) & = \big[g(X) - 2 g(X \omega)\big] \cdot \big[1 - g(X) + 2 g(X \omega)\big] \cdot (X - \omega^{n-1}).
\end{align*}
$$
This can be done efficiently using a
batch opening technique described in [this paper](https://eprint.iacr.org/2020/081).
The verifier sends a radom $\tau \in \Fp$ to the prover,
and the prover computes the quotient polynomial
$$q(X) = (w_1 + \tau w_2 + \tau^2 w_3) / (X^{n}-1).$$
The prover sends a polynomial commitment to $q$ to the verifier,
and then proves that the polynomial
$$ w(X) = w_1 + \tau w_2 + \tau^2 w_3 - q \cdot (X^{n}-1) $$
is the zero polynomial.
To do so, the verifier sends a random $\rho \in \Fp$ to the prover,
and together they run the evaluation protocol three times:
once for $g(\rho)$,
once for $g(\rho \omega)$, and
once for evaluating $\hat{w}(\rho)$, where $\hat{w}(X) = f(X) \cdot \left(\frac{\rho^n - 1}{\rho-1}\right) + q(X) \cdot (\rho^n-1)$.
This $\hat{w}$ is a linear combination of $f$ and $q$,
and therefore the verifier can construct a commitment to $\hat{w}$ using the additiving property of the PCS. The three evaluations, $g(\rho)$, $\hat{w}(\rho)$, and $g(\rho \omega)$, along with $\rho$ and $\tau$, are sufficient to evaluate $w(\rho)$ and confirm that the result is zero.
This proves, with high probability, that $w$ is the zero polynomial.
There is one remaining issue, which is that revealing
$g(\rho)$, $\hat{w}(\rho)$, and $g(\rho \omega)$ is not zero-knowledge.
The fix is simple: the prover constructs $g$ as a degree $n+1$
polynomial by interpolating $g$ to a random value at two more points
$\omega', \omega''$ outside $H$.
That is, $g$ is defined in exactly
the same way on all points in $H$,
but $g(\omega') = \alpha$ and $g(\omega'') = \beta$
for random $\alpha, \beta \in \Fp$ and $\omega, \omega' \not \in H$.
Since $g$ has the same values over all points in $H$,
this has no effect on the relations checked above.
This is zero-knowledge because $g(\rho)$ and $g(\rho \omega)$
can now be simulated as independent random values in $\Fp$.
Moreover, the value of $\hat{w}(\rho)$ is completely determined
by the fact that $w(\rho) = 0$, and can therefore also be simulated.
Note that we need to restrict the choice of $\rho$ to $(\Fp \setminus H)$ to ensure that the simulation is valid.
This entire process makes two polynomial commitments, to $g$ and $q$,
and uses the polynomial evaluation protocol three times to
evaluate $g(\rho)$, $\hat{w}(\rho)$, and $g(\rho \omega)$.
We note that, if needed, it is possible to reduce the degree of $g$ by writing $z$ in a base greater than 2.
### Other constructions
The [Bulletproofs paper](https://eprint.iacr.org/2017/1066.pdf) (Section 4.1) shows how to implement a range proof using an inner-product argument. The DARK paper shows how to implemement an inner-product argument using a polynomial commitment scheme. Combining the two gives another way to construct a range proof from a polynomial commitment scheme with similar properties as the range proof described above. Interestingly, the resulting protocol is quite different.
### Implementation/related work
This scheme initially appeared as a component of [Turbo Plonk](https://github.com/AztecProtocol/barretenberg/blob/master/src/barretenberg/waffle/proof_system/widgets/turbo_range_widget.cpp) by Ariel Gabizon and Zac Williamson