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 goes over the point sets, and the inner vector goes over 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.