# PLONK Prod Check Proof - why does it have to be proven upto the last element of the set? It should be enough to prove it upto last but one element

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$$ (including at $$x = \omega^{k-1})$$

My question is about the including in the 2nd proof.

I think it needs to be proved only up to $$x= \omega^{k-2}$$ & the last element $$\omega^{k-1}$$can be ignored.

If we take $$x= \omega^{k-1}$$, then 2nd equation

$$t(\omega\cdot x) - t(x)\cdot f(\omega \cdot x) \stackrel {?}{=} 0$$

becomes

$$t(\omega \cdot \omega^{k-1}) - t(\omega^{k-1})\cdot f(\omega \cdot \omega^{k-1}) \stackrel {?}{=} 0$$

i.e.

$$t(\omega^k) - t(\omega^{k-1})\cdot f(\omega^k) \stackrel {?}{=} 0$$

I don't think it's needed to prove this at all, since the final equality we want to prove is $$t(\omega^{k-1}) = 1$$ - we never have to go beyond the $$x = k-2$$th power of $$\omega$$ (i.e. $$x = \omega^{k-2}$$)

Using $$x = \omega^{k-2}$$ proves

$$t(\omega^{k-1}) - t(\omega^{k-2})\cdot f(\omega^{k-1}) = 0$$

& we have already proved $$\omega^{k-1} = 1$$

So there is no need for $$x = \omega^{k-1}$$.

So why is Boneh very particularly saying (including at $$x = \omega^{k-1})$$?

What am I missing?

• Notice that 1) checks that the "last" value of $t$ is correct and 2) check that $t$ is well constructed for every element of $\Omega$. If you exclude the check at $\omega^{k-1}$, then you are missing the check that $t(1)=f(1)$, so a dishonest prover could set anything for $t(1) \neq f(1)$. Apr 2, 2023 at 18:04

At $$x=\omega^{k-1}$$ the 2nd equation is $$t(\omega^k) = t(\omega^{k-1}) \cdot f(\omega^k)$$ which, knowing that $$\omega^k = 1$$ and assuming 1) is satisfied, i.e. $$t(\omega^{k-1})=1$$, it converts to $$t(1) = f(1)$$ which is a necessary check to ensure the correctness of the "Prod Check Gadget". Otherwise, the prover could lie to the verifier by setting $$t(1) = \tilde{t} \neq f(1)$$ with $$\tilde{t} \in \mathbb{F}$$ and still satisfying both 1) and 2) for $$x \in \Omega \backslash \{\omega^{k-1}\}$$ (I'll let you think about a specific example).
• Your answer makes a lot of sense, but I have a question. Let's consider, the prover instead has to prove $\prod_{a \in \Omega} f(a) = m$ where $m$ is some value. In this, all other steps work similarly but he won't be able to prove the final step that $t(1) = f(1)$. Instead when we substitutes $x= \omega^{k-1}$, we will end up with $t(1) = m.f(1)$. So in this case, how will the proof proceed? How will the proof gadget have to change to prove $\prod_{a \in \Omega} f(a) = m$ Apr 3, 2023 at 9:51
• Idk if this is the best solution, but my idea is to use the $(k-1)$-th Lagrange polynomial $L_{k-1}(x)$ such that $L_{k-1}(x) = 1$ if $x=\omega^{k-1}$ and $L_{k-1}(x)=0$ if $x \in \Omega \backslash \{\omega^{k-1}\}$. Then, 1) needs to be $t(\omega^{k-1})=m$ and 2) turns to be $t(\omega \cdot x) - t(x) \cdot f(\omega \cdot x) + L_{k-1}(x)(m f(\omega \cdot x) - f(\omega \cdot x)) = 0$. I let you check that these new constraints are correct for your variant. Apr 3, 2023 at 13:55
• What exactly is $(k-1)$th Lagrange Polynomial? Boneh doesn't cover any such thing in his video. I googled for it but can only find Lagrange interpolation which I know about but doesn't sound like what you are referring to. Apr 4, 2023 at 12:04
• The $(k-1)$-th Lagrange polynomial is obtained by interpolating the set of points $(1,0),(\omega,0),(\omega^2,0),\dots,(\omega^{k-2},0),(\omega^{k-1},1)$, so, the unique polynomial of degree $k-1$ such that is $1$ at $\omega^{k-1}$ and $0$ everywhere else of $\Omega$ Apr 5, 2023 at 7:08
• Thank you for your answer. My original question is fully answered for $\prod_{a \in \Omega} f(a) = 1$. I think I will post a separate question for $\prod_{a \in \Omega} f(a) = m$ to see there is a simple solution like for the $1$ case. Apr 5, 2023 at 9:02