Let's construct a simple zero knowledge range proof from a hiding polynomial commitment scheme (PCS).
Let be a prime, where for some . We want a commitment scheme for elements in that allows a prover to efficiently convince a verifier that a committed quantity is in the range .
We show that for a committed , the prover can provide an HVZK proof to convince the verifier that by committing to two polynomials of degree , and running the polynomial evaluation protocol three times. Therefore:
In what follows we use to denote polynomials in of degree less than . We assume that divides so that there is an element of order . Let .
Suppose that we have available a hiding and binding PCS for polynomials in . Moreover, we assume that the polynomial evaluation protocol is HVZK.
To commit to an element , choose an arbitrary polynomial such that . Taking as the constant polynomial is sufficient. The commitment to is the polynomial commitment to .
If the PCS is additive, then the commitment scheme is additively homomorphic: given commitments to and in , anyone can construct a commitment to .
Let be a commitment to so that , as above. Let be the binary digits of , so that .
Now, given , the prover proves that , by constructing a degree- polynomial such that Observe that . Now the prover needs to prove three things:
Condition (1) proves that ; Conditions (2) and (3) prove that are all in and are the binary digital of . Together, these conditions prove that , as required.
To prove Conditions (1)-(3), the prover sends to the verifier a polynomial commitment to . It then proves to the verifier that the following polynomials evaluate to zero for all : This can be done efficiently using a batch opening technique described in this paper. The verifier sends a radom to the prover, and the prover computes the quotient polynomial The prover sends a polynomial commitment to to the verifier, and then proves that the polynomial is the zero polynomial. To do so, the verifier sends a random to the prover, and together they run the evaluation protocol three times: once for , once for , and once for evaluating , where . This is a linear combination of and , and therefore the verifier can construct a commitment to using the additiving property of the PCS. The three evaluations, , , and , along with and , are sufficient to evaluate and confirm that the result is zero. This proves, with high probability, that is the zero polynomial.
There is one remaining issue, which is that revealing , , and is not zero-knowledge. The fix is simple: the prover constructs as a degree polynomial by interpolating to a random value at two more points outside . That is, is defined in exactly the same way on all points in , but and for random and . Since has the same values over all points in , this has no effect on the relations checked above. This is zero-knowledge because and can now be simulated as independent random values in . Moreover, the value of is completely determined by the fact that , and can therefore also be simulated. Note that we need to restrict the choice of to to ensure that the simulation is valid.
This entire process makes two polynomial commitments, to and , and uses the polynomial evaluation protocol three times to evaluate , , and . We note that, if needed, it is possible to reduce the degree of by writing in a base greater than 2.
The Bulletproofs paper (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.
This scheme initially appeared as a component of Turbo Plonk by Ariel Gabizon and Zac Williamson