1
$\begingroup$

From the PLONK paper.

On pages 19 & 20, the paper describes the prescribed permutation check in PLONK.

enter image description here

In the last step of the proof, these are the checks

a) $L_1(a)(Z(a) - 1) = 0$
b) $Z(a)f'(a) = g'(a)Z(a \cdot g)$

In (a), I think checking $Z(a) - 1 = 0$ & doing the (b) check as written is enough. What purpose does multiplying this by the first Lagrange Polynomial ($L_1(a)$) serve?

Can someone explain?

$\endgroup$

1 Answer 1

2
$\begingroup$

The checks a) and b) are done over every element $a\in H$ (Notice the statement "for all $a\in H$"). The product check requires that the verifier check that $Z(g)=1$ (the inductive base case). Since $L_1$ only evaluates to $1$ (otherwise $0$) at $g$, checking $L_1(a)(Z(a)-1)=0$ over all $a\in H$ is exactly the same as checking $Z(g)-1=0\implies Z(g)=1$. If we were to check $Z(a)-1=0$ for all $a\in H$ instead, that check would translate to "does Z(X) evaluate to only 1 over every element of $H$."

$\endgroup$
2
  • $\begingroup$ There are 2 sets here. First is $[n]$ which is $[1,2,...,n]$ & the 2nd is $H = \{g, g^2, g^3, ..., 1\}$ - last element is $1$ because $g^n = 1$ because order of $g$ is $1$. I think the subscript of $L_1$ is the $1$ taken from $[n]$. However since the first element of $H$ is $g$ wouldn't $Z(a)$ be $Z(g)$ rather than $Z(1)$? it's $Z(last element of H)$ which will be $Z(1)$ - i.e we have to prove $Z(g) = 1$ & not $Z(1) = 1$, right? Or am i mistaken? $\endgroup$
    – user93353
    May 4, 2023 at 11:01
  • $\begingroup$ Ah, yes, it depends on how you do indexing. I was originally referring to the multiplicative identity $1$ of the group $H$. Normally, people use $0$ indexing, which is what led to me using $g^0=1$. I'll edit the answer to match the plonk indexing. $\endgroup$
    – Wilson
    May 4, 2023 at 15:40

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.