# Multipoint opening argument

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.

## Optimization steps

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:

1. Sample random , to keep linearly independent.

2. Accumulate polynomials and their corresponding evaluations according to the point set at which they were queried: q_polys: q_eval_sets:

        [
[a(x) + x_1 b(x)],
[
c(x) + x_1 d(x),
c(\omega x) + x_1 d(\omega x)
]
]


NB: q_eval_sets is 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.

3. Interpolate each set of values in q_eval_sets: r_polys:

4. Construct f_polys which check the correctness of q_polys: f_polys

If , then should be a polynomial. If and then should be a polynomial.

5. Sample random to keep the f_polys linearly independent.

6. Construct .

7. Sample random , at which we evaluate :

8. Sample random to keep and q_polys linearly independent.

9. Construct final_poly, which is the polynomial we commit to in the inner product argument.