Join Log in
Score:1
avatar Crypto

Question about the PLONK permutation check

et flag
user93353

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?

84
1 + 0
Score:2
Wilson avatar Crypto
se flag
Wilson

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$."

+ 2
et flag
user93353
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?
0
Reply
Wilson avatar
se flag
Wilson
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.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

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.