Join Log in
Score:2
avatar Crypto

PLONK Product Check Proof. Why is the 2nd condition required?

et flag
user93353

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.

90
1 + 2
kodlu avatar
sa flag
kodlu
Your second equation is *wrong*. You need a minus instead of the first equal sign.
0
Reply
et flag
user93353
@kodlu - yes, edited. Thank you
0
Reply
Score:3
kodlu avatar Crypto
sa flag
kodlu

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.

+ 2
et flag
user93353
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?
1
Reply
et flag
user93353
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?
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.