In Protocol 4.1, Figure 2, would the following modification still be valid?
Define \hat{z}_i(X) := \prod_{\omega \in \Omega_i} (X-\omega) and replace g(X), C_g with
- g'(X) := \sum_{i=1}^k \rho^{i-1} \frac{1}{\hat{z}_i(r)}\cdot f_i(X) - q'(X) \big( \equiv\frac{1}{z(r)} \cdot g(X) \big)
- C_{g'} := C_{q'} - \sum_{i=1}^k \rho^{i-1} \frac{1}{\hat{z}_i(r)}\cdot C_i \big( \equiv\frac{1}{z(r)} \cdot C_g \big)
Alternatively, we can also write q(X) := \sum_{i=1}^k \rho^{i-1} \frac{f_i(X)}{\hat{z}_i(X)} in a way that emphasizes that we are dividing f_i(X) by all of its roots, in a similar way to classic KZG.
Intuitively, this would not change the execution of the protocol since we are simply multiplying q(X) by a value known by the verifier.
This modification makes the implementation a lot more straight forward especially for a circuit version of the verifier.
Indeed, since we no longer need to compute the set \Omega = \cup_{i=1}^k \Omega_i or its vanishing polynomial z(X), we can simply iterate over the list \{(C_i, \Omega_i)\}_{i=1}^k without having to check if \Omega_i \cap \Omega_j \neq \emptyset.
Note that the same modification should apply to generalized protocol in A.7 Figure 5.