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