What does preprocessed polynomial mean in the context of PLONK?

user93353

5/8/24, 5:45 AM

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.

1 + 0

zero-knowledge-proofs

snarks

Score:3

Crypto

Daniel S

5/11/24, 7:54 AM

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.

+ 2

user93353

5/11/24, 8:06 AM

So these polynomials would be created using Lagrange Interpolation?

Daniel S

5/11/24, 8:12 AM

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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: What does preprocessed polynomial mean in the context of PLONK?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.