Why does the permutation polynomial have the First Lagrange base added to it in PLONK?

user93353

8/4/24, 8:13 AM

From the PLONK paper.

On page 19 & ahead, the permutation check is described. In particular, on page 20, the protocol is described.

Step 5 of the check is described as

Verifier checks if for all $a \in H$

a) $L_1(a) (Z(a) -1) = 0$

b) $Z(a) f'(a) = g'(a) Z(a\cdot g)$

However, in the actual Round where (I think) this check is implemented (Round 2 on Page 28), this is how the polynomial is created

$z(X) = (b_7X2 + b_8X + b_9)Z_H(X ) + L_1(X) + \prod_{i=1}^{n−1}L_{i+1}(X)\prod_{j=1}^{i} \frac {(\omega_j +\beta \omega^j +\gamma)(\omega_{n+j} +\beta k_1 \omega^j +\gamma)(\omega_{2n+j} +\beta k_2 \omega^j +\gamma)}{(\omega_j +\sigma^*(j)\beta \omega^j +\gamma)(\omega_{n+j} +\sigma^*(n+j)\beta k_1 \omega^j +\gamma)(\omega_{2n+j} +\sigma^*(2n+j)\beta k_2 \omega^j +\gamma)}$

I understand the $b_7, b_8$ etc term multiplied with $Z_H$ so I will remove it for simplification. Also, again for simplification I will denote the numerator polynomial as $f'$ & the denominator as $g'$. So this is the permutation polynomial

$z(X) = \textbf{L_1(X)} + \prod_{i=1}^{n−1}L_{i+1}(X)\prod_{j=1}^{i} \frac {f'}{g'}$

I don't understand the leading $L_1(X)$ which is added at the beginning? Why is the first Lagrange Base added to $z(X)$? Can someone who understood this explain this? As per section 5, shouldn't $L_1(X)$ be multiplied?

1 + 0

zero-knowledge-proofs

snarks

Score:1

Crypto

Dani Vilardell

8/11/24, 4:29 AM

I think you made a mistake when reading the paper, since the different elements of the Lagrange base are added, not multiplied, giving the following definition of permutation polynomial:

$$z(X) = L_1(X) + \sum_{i=1}^{n-1}L_{i+1}(X)\prod_{j=1}^i\frac{f'(a^j)}{g'(a^j)}$$

I removed the $(b_7X^2+b_8X+b_9)Z_H(X)$ from $z(X)$ since it's only use is to provide the zero knowledge property to the protocol and is irrelevant to your question.

Now that we have the correct equation, we can understand the reason we are adding all this different constraints together. The main goal of the protocol is to prove that $$ \prod_{i=1}^{n}\frac{f'(a^i)}{g'(a^i)} = 1 $$

since this would imply that the permutation check passed, and therefore the circuit "wiring" is correct.

What the protocol will do to prove this is a Zero test which will check that $$L_1(x)(z(x)-1) = 0 \quad \text{and} \quad z(x)f'(x) = z(ax)g'(x) \quad \forall x \in H$$$H$ being the set of $n$-roots of unity.

It is easy to see that the previously defined $z(X)$ fulfils this two equations as long as $$ z(a) = 1 \quad \text{and} \quad z(a^{n})f'(a^{n}) = z(a^{n+1})g'(a^{n}) = z(a)g'(a^{n}) = g'(a^{n}) $$ which would imply $$ z(a^{n})\frac{f'(a^{n})}{g'(a^{n})} = \prod_{i=1}^{n} \frac{f'(a^{i})}{g'(a^{i})} = 1 $$

This is exactly what we wanted to prove to the verifier.

+ 0

Elon Musk

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

EN: Why does the permutation polynomial have the First Lagrange base added to it in 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.