# Verify all proofs Suppose you have a polynomial $P$, and the sample proofs $Q_i = \lfloor \frac{P}{X^{16} - \omega^{i * 16}} \rfloor$. Goal: verify all proofs. Note that for all $i$, $Q_i * (X^{16} - \omega^{i * 16}) = P - I_i$, where $I_i$ is the $deg < 16$ interpolant of the i'th subgroup. We can combine all of these equations with a random linear combination: $\sum Q_i * (X^{16} - \omega^{i * 16}) * r_i = \sum (P - I_i) * r_i$ Now let us play with this equation: $\sum (Q_i * r_i)* X^{16} - \sum (Q_i * w^{i * 16} * r_i) = P * \sum r_i - \sum (I_i * r_i)$ We now convert this into a pairing equation: $e(\sum (Q_i * r_i), [X^{16}]) \div e(\sum (Q_i * w^{i * 16} * r_i), [1]) = e(P * \sum r_i - \sum (I_i * r_i), [1])$ Let us go through this term-by-term. * $\sum (Q_i * r_i)$ is a simple size $\frac{N}{16}$ fast linear combination. * $\sum Q_i * w^{i * 16} * r_i$ is a simple size $\frac{N}{16}$ fast linear combination. * $P * \sum r_i$ is a multiplication after N field operations * $\sum (I_i * r_i)$ involves the calculation of $\frac{N}{16}$ size-16 interpolants; with Lagrange interpolation this can be done in $\approx 16 * N$ field operations; FFTs may speed this up but at these small scales only slightly. Adding up the interpolants and converting the result into a point is trivial.