2
$\begingroup$

I am going through Dan Boneh's video on PLONK - https://www.youtube.com/watch?v=LbpPCN-f_XA&t=952s

At around 19 minutes, he gets to the Prod Check Gadget.

Background:

$\omega \in \mathbb F_p$ is the primitive $k$th root of unity (i.e. $\omega^{k} = 1$)

$\Omega = \{1, \omega, \omega^{2}, ..., \omega^{k-1}\}$

Let $t(1) = f(1)$ and $t(\omega^s) = \prod_{i=0}^s f(\omega^i)$ for $s = 1, ..., k-1$.

Prover has to prove that:

$\prod_{a \in \Omega} f(a) = 1$

Boneh says that Prover can prove the above by proving 2 things

1) $t(\omega^{k-1}) = 1$

and

2) $t(\omega\cdot x) - t(x)\cdot f(\omega \cdot x) = 0$ for all $x \in \Omega$

I understand the 2nd check but I don't understand why it's required. Boneh says it's to make sure $t$ was constructed correctly.

How exactly could the first check be true without the 2nd check also being true. How exactly can a malicious Prover do something malicious if only the first check had to be proved?


UPDATE:

I am wondering if the reason is this -

Normally, commitment openings are evaluated at a random point sent by the verifier. However, here the commitment openings are going to be evaluated at known values from $\Omega$. So it would be easy for the prover to cheat. He can create a polynomial which evaluates to whatever value he wants & commits to it rather than the actual $t(x)$. I think the 2nd check may be to prevent that.

$\endgroup$
2
  • $\begingroup$ Your second equation is wrong. You need a minus instead of the first equal sign. $\endgroup$
    – kodlu
    Mar 29, 2023 at 12:19
  • $\begingroup$ @kodlu - yes, edited. Thank you $\endgroup$
    – user93353
    Mar 29, 2023 at 12:21

1 Answer 1

3
+50
$\begingroup$

The correct checks are

1) $t(\omega^{k-1}) = 1$

and

2) $t(\omega\cdot x) - t(x)\cdot f(\omega \cdot x) = 0$ for all $x \in \Omega$

The prover is supplying values in a black box way. The second relation is a "differential" relation specifying $t(w \cdot x)$ in terms of $t(x)$ and $f(\omega \cdot x)$ so it can hold without the first equation holding. Simply write the recurrence for $f(w^{k-1})=c\neq 1,$ going backwards.

All the verifier sees are values, so a specific value (here $f(w^{k-1})$ needs to be fixed and verified for the answer to be correct.

Edit: Indeed, due to the fact that the set $\Omega$ is a priori known, the second check prevents the prover setting an arbitrary polynomial $t(x)$ and then verify it if the first check was the only check used.

$\endgroup$
2
  • 1
    $\begingroup$ If I understand you correctly, you are saying that that "Condition 1" makes sure that the answer is correct. And "Condition 2" makes sure it's calculated using the right procedure. i.e $\prod_{a \in \Omega} f(a) = 1$ is an incremental/recursive calculation. And condition 2 proves every intermediate step in the calculation. So if the final answer is correct, then it proves that the final answer can be correct only if each previous step in calculation is correct. Am I correct? $\endgroup$
    – user93353
    Mar 30, 2023 at 7:07
  • $\begingroup$ Also, I am wondering if there is another reason. Unlike normal commitment openings, this is not going to be evaluated at a random point, but at known values from $\Omega$. So it's easy for the prover to cheat. He can create a polynomial which evaluates to whatever value he wants & commits to it rather than the actual $t(x)$. I think the 2nd check is to prevent that. What do you think? $\endgroup$
    – user93353
    Mar 30, 2023 at 9:58

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.