0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
+50
$\begingroup$

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.

$\endgroup$

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.