Score:1

Prod Check Gadget in PLONK - any polynomial which satisfies the prod check seems to be the trivial polynomial

et flag

In Dan Boneh's PLONK Video - https://www.youtube.com/watch?v=vxyoPM2m7Yg he refers to the Prod Check Gadget

$\omega \in F_p$ is a primitive $k$-th root of unity ($\omega^{k-1} = 1$)

$H = \{1, \omega, \omega^2, ..., \omega^{k-1}\} \subseteq F_p$

Prod Check Gadget is used to prove that $\prod_{a \in H} f(a) = c$

I was trying to construct a polynomial $f(x)$ which there is true.

I used $p=17$ i.e $f \in F_{17}$

$\omega = 4$ is the primitive $4$th root of unity in $F_{17}$.

So $H = \{1, 4, 16, 13\}$

Let $c = 5$

Now, I try to find a polynomial $f$ such that $f(a) = 5$ for all $a \in H$ using Lagrange Polynomial Interpolation.

sage: F17 = GF(17)
sage: R17.<x> = PolynomialRing(F17)
sage: w = F17(4)
sage: c = F17(5)
sage: points = [(w^0, c), (w, c), (w^2, c), (w^3, c)]
sage: R17.lagrange_polynomial(points)
5

So Lagrange Interpolation gives returns $f$ as the trivial polynomial $f(x) = 5$

Any value of $c$ returns the polynomial as $f(x) = c$

So I am unable figure what is the point of this gadget?

Or am I doing something wrong in my toy example?

Score:1
sd flag

ProdCheck gadget is used for checking the product of values of the polynomial over a multiplicative subgroup of the field is equal to some constant or not.

In your toy example, you want to find a polynomial $f$ such that $f(a)=5$ for all $a\in H$. But Prodcheck gadget is for checking $\prod\limits_{a\in H}f(a)=c$ or not.

For the Lagrange polynomial computation over $F_{17}$ , sage outputs $5$ because I think it will be the constant polynomial $f(x)=5$

et flag
You are right. Brain fade moment for me! However, Is there a way, I can create a polynomial where $\prod\limits_{a\in H}f(a)=c$ in $F_{17}$ with $w$ as the primitive 4th root of unity
Manas Jana avatar
sd flag
You can construct a polynomial $f$ like this: choose $c_0,c_1,c_2,c_3$ such that $c=c_0c_1c_2c_3$ and construct $f$ using Lagrange interpolation such that $f(w^i)=c_i.$
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.