3
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Hi @user93353, I've edited the answer with a more fleshed out analysis. Does it help you with understanding the soundness analysis more? $\endgroup$
    – Wilson
    May 11, 2023 at 14:53

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.