Verify all proofs

Suppose you have a polynomial

$P$, and the sample proofs

$Q_i=\lfloor \frac{P}{X^{16}-{\omega }^{i\ast 16}}\rfloor$.

Goal: verify all proofs.

Note that for all

$i$,

$Q_i\ast (X^{16}-{\omega }^{i\ast 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\ast (X^{16}-{\omega }^{i\ast 16})\ast r_i=\sum (P-I_i)\ast r_i$

Now let us play with this equation:

$\sum (Q_i\ast r_i)\ast X^{16}-\sum (Q_i\ast w^{i\ast 16}\ast r_i)=P\ast \sum r_i-\sum (I_i\ast r_i)$

We now convert this into a pairing equation:

$e(\sum (Q_i\ast r_i),[X^{16}])÷e(\sum (Q_i\ast w^{i\ast 16}\ast r_i),[1])=e(P\ast \sum r_i-\sum (I_i\ast r_i),[1])$

Let us go through this term-by-term.

• $\sum (Q_i\ast r_i)$ is a simple size
  $\frac{N}{16}$ fast linear combination.
• $\sum Q_i\ast w^{i\ast 16}\ast r_i$ is a simple size
  $\frac{N}{16}$ fast linear combination.
• $P\ast \sum r_i$ is a multiplication after N field operations
• $\sum (I_i\ast r_i)$ involves the calculation of
  $\frac{N}{16}$ size-16 interpolants; with Lagrange interpolation this can be done in
  $\approx 16\ast 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.