There’s a number of useful stuff that we can do on top of a bootleproof-style polynomial commitment. I’ll briefly list them here.
Imagine that you want to enforce a maximum degree on a committed polynomial. You can do that by asking the prover to shift the coefficients of the polynomial to the right, so much that it becomes impossible to fit them if the polynomial were to be more than the maximum degree we wanted to enforce. This is equivalent to the following:
When the verifier verifies the opening, they will have to right shift the received evaluation in the same way.
Note that this kind of aggregation forces us to provide all combinations of evaluations, some of which might not be needed (for example, ).
If a polynomial is too large to fit in one SRS, you can split it in chuncks of size at most
That is useful in HALO. Problem statement: given a commitment , and a polynomial , prove to me that the . The proof is simple:
- generate a random point
- evaluate at ,
- ask for an evaluation proof of on . If it evaluates to as well then is a commitment to with overwhelming probability