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.