Score:3

PLONK: Why is the quotient polynomial multiplied by different powers of a challenge?

et flag

From the PLONK paper.

Page 29, Round 3

enter image description here

The paper doesn't explain the need or the use of the quotient challenge $\alpha$.

I understand why each of the polynomials is multiplied by $\frac {1}{Z_H}$ but don't understand why the second is also multiplied by $\alpha$ & the last by $\alpha^2$ - what purpose does the quotient challenge serve & why are different powers used? I can't find this discussed anywhere in the paper.

Score:3
se flag

The quotient challenge is necessary for soundness. In particular, if the prover wants to show that there exists quotients $q_1=f_1/z_H$, $q_2=f_2/z_H$, and $q_3=f_3/z_H$. To do so, it can instead send $q = (f_1+\alpha f_2+\alpha^2 f_3)/z_H$, where $\alpha$ is a verifier challenge (or the output of Fiat-Shamir). Then, the verifier can query at a random $\beta$ to check the identity $(f_1(\beta)+\alpha f_2(\beta)+\alpha^2 f_3(\beta))-z_H(\beta)q(\beta) = 0$.

Here's a sketch of the proof of soundness. We want to show that $f_1, f_2, f_3$ are zero over $H$. Let's consider the polynomial $$F(X,Y)=f_1(X)+Yf_2(X)+Y^2f_3(X)$$ I will argue that $F(X,Y)$ vanishes for all $x=h\in H$ if and only if $f_1, f_2, f_3$ vanish over $H$. Consider an arbitrary element $h\in H$, $$F(h, Y)=f_1(h)+Yf_2(h)+Y^2f_3(h)=0$$ if and only if $f_1(h)=f_2(h)=f_3(h)=0$. This is because the $Y$ powers are linearly independent.

The verifier can perform a randomized test to check if $F(X,Y)$ vanishes over $H$. First it sends a challenge $Y=\alpha$. Then, the honest prover sends back $q(X)=F(X,\alpha)/z_H$ to prove that the resulting polynomial vanishes on $H$.

Let's consider the probability for which a malicious prover gets caught. There must be at least one element $h'\in H$ such that $f_1(h')+Yf_2(h')+Y^2f_3(h')\neq 0$. Since we queried at a random $\alpha$, by Schwartz-Zippel lemma, $f_1(h')+\alpha f_2(h')+\alpha^2f_3(h')=0$ occurs with probability less than $\frac{2}{|\mathbb{F}|}$. Thus, with high probability, there cannot exist a quotient $q(X)$ such that $F(X, \alpha)=z_H(X)q(X)$. Hence, the $q(X)$ that the malicious prover sent cannot be a valid quotient.

Now the verifier has to check that $q(X)$ is a valid quotient, which requires another randomized check to $X=\beta$ to check $F(\beta, \alpha)=z_H(\beta)q(\beta)$.

Wilson avatar
se flag
Hi @user93353, I've edited the answer with a more fleshed out analysis. Does it help you with understanding the soundness analysis more?
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.