What does preprocessed polynomial mean in the context of PLONK?

Question

The PLONK paper uses the term preprocessed polynomial a lot of times.

• For e.g. page 14

The protocol definition includes a set of preprocessed polynomials $g1, . . . , g_l \in F<d[X]$

• Page 20

Preprocessed polynomials: The polynomial $S_{ID} \in F<n[X]$ defined by $S_{ID}(\mathbf g^i) = i$ for each $i \in [n]$ and $S_\sigma \in F<n[X]$ defined by $S\sigma (\mathbf g^i) = \sigma(i)$ for each $i \in [n]$.

And several more.

However, I can't find exactly what preprocessing means in this context.

Can someone please explain.

Answer 1

Pre-processing means part of the one-time initial set up computation of the system prior to the generation of any proofs. This set-up phase is allowed to use considerably more resources.

If we look to the footnote on page 2 we read:

We use the term SNARK in this paper for what is sometimes called a “SNARK with preprocessing”(see e.g. [GGPR13]) where one allows a one-time verifier computation that is polynomial rather than polylogarithmic in the circuit size.

Thus the $g_i$ are created as part of the set-up and may use greater computarion in their creation than is permitted for a proof.