--- 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\}$, &nbsp; and 3. $\ \ g(X) - 2 g(X \omega) \in \{0,1\}$ &nbsp; 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