# 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.