---
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

or

By clicking below, you agree to our terms of service.

Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet

Wallet
(
)

Connect another wallet
New to HackMD? Sign up