1
$\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$ (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?

$\endgroup$
1
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – Bean Guy
    Apr 2, 2023 at 18:04

1 Answer 1

3
+50
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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$ $\endgroup$
    – user93353
    Apr 3, 2023 at 9:51
  • $\begingroup$ 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. $\endgroup$
    – Bean Guy
    Apr 3, 2023 at 13:55
  • $\begingroup$ 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. $\endgroup$
    – user93353
    Apr 4, 2023 at 12:04
  • $\begingroup$ 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$ $\endgroup$
    – Bean Guy
    Apr 5, 2023 at 7:08
  • $\begingroup$ 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. $\endgroup$
    – user93353
    Apr 5, 2023 at 9:02

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.