Consider the commitments to polynomials . Let's say that and were queried at the point , while and were queried at both points and . (Here, is the primitive root of unity in the multiplicative subgroup over which we constructed the polynomials).
To open these commitments, we could create a polynomial for each point that we queried at (corresponding to each relative rotation used in the circuit). But this would not be efficient in the circuit; for example, would appear in multiple polynomials.
Instead, we can group the commitments by the sets of points at which they were queried:
For each of these groups, we combine them into a polynomial set, and create a single for that set, which we open at each rotation.
The multipoint opening optimization takes as input:
- A random sampled by the verifier, at which we evaluate .
- Evaluations of each polynomial at each point of interest, provided by the prover:
These are the outputs of the vanishing argument.
The multipoint opening optimization proceeds as such:
Sample random , to keep linearly independent.
Accumulate polynomials and their corresponding evaluations according to the point set at which they were queried:
[ [a(x) + x_1 b(x)], [ c(x) + x_1 d(x), c(\omega x) + x_1 d(\omega x) ] ]
q_eval_setsis a vector of sets of evaluations, where the outer vector corresponds to the point sets, which in this example are and , and the inner vector corresponds to the points in each set.
Interpolate each set of values in
f_polyswhich check the correctness of
If , then should be a polynomial. If and then should be a polynomial.
Sample random to keep the
Sample random , at which we evaluate :
Sample random to keep and
final_poly, which is the polynomial we commit to in the inner product argument.