3
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
+50
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ So these polynomials would be created using Lagrange Interpolation? $\endgroup$
    – user93353
    May 11, 2023 at 8:06
  • $\begingroup$ They could be created using Lagrange interpolation, or depending on the properties being proven other generation methods might be appropriate. The framework is quite general. $\endgroup$
    – Daniel S
    May 11, 2023 at 8:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.