Score:1

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

et flag

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?

Bean Guy avatar
in flag
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)$.
Score:3
in flag

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

et flag
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$
Bean Guy avatar
in flag
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.
et flag
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.
Bean Guy avatar
in flag
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$
et flag
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.
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.