batch open multiple `q`

[kunxian-xia]

Motivation

In our zkvm, we have two sets of matrices to commit:

1. preprocessed trace matrices: we commit it in the setup phase.
2. witness trace matrices: they vary from instance to instance (only known at proving time)

Therefore we need to open two giga mles ($q_f$, $q_w$). Assume the preprocessed set has $K_f$ polynomials, the witness set has $K_w$ polynomials.

prover

1. sample $c_f \in E^{k_f}$, $v_f = \sum_i \textrm{eq}(c_f, i) * C_i^f * f_i(z_r[..s])$;
2. sample $c_w \in E^{k_w}$, $v_w = \sum_i \textrm{eq}(c_w, i) * C_i^w * w_i(z_r[..s])$;
3. run jagged sumcheck for $v_f, q_f$ to get proof $\pi_f^1$ and then run jagged assist sumcheck to get proof $\pi_f^2$.
4. run jagged sumcheck for $v_w, q_w$ to get proof $\pi_w^1$ and then run jagged assist sumcheck to get proof $\pi_w^2$.
5. invoke inner PCS to batch open $q_f(z_f)$ and $q_w(z_w)$ to get a inner PCS opening proof $\pi$.

verifier

1. sample $c_f \in E^{k_f}$, $v_f = \sum_i \textrm{eq}(c_f, i) * C_i^f * f_i(z_r[..s])$;
2. sample $c_w \in E^{k_w}$, $v_w = \sum_i \textrm{eq}(c_w, i) * C_i^w * w_i(z_r[..s])$;
3. verify jagged sumcheck proof $\pi_f^1$ and jagged assist sumcheck proof $\pi_f^2$;
4. verify jagged sumcheck proof $\pi_w^1$ and jagged assist sumcheck proof $\pi_w^2$;
5. verify inner PCS opening proof $\pi$.