2
$\begingroup$

From the PLONK paper.

On Page 31, Point 6

Compute the Lagrange Polynomial Evaluation $L_1(\zeta) = \frac{\omega(\zeta^n - 1)} {n(\zeta- \omega)}$

I don't think this formula is correct.

We have $n$ gates from $H=\lbrace 1, \omega, \omega^2, \omega^3, ..., \omega^{n-1}\rbrace$.

So the formula for computing $L_1(X)$ should be

$L_1(X) = \frac {(X-\omega)(X-\omega^2)(X-\omega^3)...(X-\omega^{n-1})}{(1-\omega)(1-\omega^2)(1-\omega^3)...(1-\omega^{n-1})}$

To get the $X^n-1$ term in the numerator, I multiply numerator & denominator by $(X-1)$

$L_1(X) = \frac {(X-1)(X-\omega)(X-\omega^2)(X-\omega^3)...(X-\omega^{n-1})}{(X-1)(1-\omega)(1-\omega^2)(1-\omega^3)...(1-\omega^{n-1})}$

It can be shown that $X^n-1 = (X-1)(X-\omega)(X-\omega^2)(X-\omega^3)...(X-\omega^{n-1})$

So

$L_1(X) = \frac {X^n-1}{(X-1)(1-\omega)(1-\omega^2)(1-\omega^3)...(1-\omega^{n-1})}$

So $L_1(\zeta) = \frac {\zeta^n-1}{(\zeta-1)(1-\omega)(1-\omega^2)(1-\omega^3)...(1-\omega^{n-1})}$

The above doesn't match with the formula in the paper i.e. $L_1(\zeta) = \frac{\omega(\zeta^n - 1)} {n(\zeta- \omega)}$

I tested with sample values also. Let's say we are in $\mathbb F_{17}$ & $\omega = 4$ which is the 4th root of unity in $\mathbb F_{17}$.

So $H=\lbrace 1, \omega, \omega^2, \omega^3 \rbrace$.

Let $\zeta = 5$

Using the paper's formula.

$L_1(5) = \frac {4(5^4 -1)}{4(5-4)}$

$L_1(5) = 12$

And if I use my formula

$L_1(5) = \frac {5^4-1}{(5-1)(1-4)(1-4^2)(1-4^3)}$

$L_1(5) = 5$

$\endgroup$
5
  • $\begingroup$ How do you conclude that the paper is wrong? Numerical comparison with examples should also be done more carefully. It would better to compare the paper’s result to that of a vanilla Lagrange output rather than the intermediate formula in question which hasn’t been proven equivalent to the Lagrange polynomial. $\endgroup$ Aug 21, 2023 at 21:11
  • $\begingroup$ @MarcIlunga I concluded it's wrong not on the basis of the numerical example but based on the formula for calculation of Lagrange bases. I have shown what I think is the right way to calculate $L_1(\zeta)$ in my question - that's how Lagrange bases are calculated . The numerical example isn't to show that it's wrong but to show that my way & their way aren't equivalent. $\endgroup$
    – user93353
    Aug 21, 2023 at 23:58
  • $\begingroup$ The issue is that youut $L_1$ does not compute the right polynomial. Recall that $L_i$ should be one only for $\omega^i$. In your case you are computing $L_0$ instead. $\endgroup$ Aug 22, 2023 at 5:40
  • $\begingroup$ @MarcIlunga $L_1$ here is the first lagrange base - they are indexing from $1$ & not from $0$. If you check the formula in Round 2, it uses $L_1$ at the beginning & then $L_2$ to $L_n$ inside the $\sum$. Since there are only $n$ gates, there are $n$ Lagrange bases. If there was an $L_0$ also, you will end up with $n+1$ Langrange Bases which would be wrong. $\endgroup$
    – user93353
    Aug 22, 2023 at 5:54
  • $\begingroup$ We are working in a subgroup of order $n$ so $L_n$ is effectively $L_0$. Stated differently, you are computing $L_n$ instead of $L_1$. Please review the definition of $L_i$ and recompute it for $i = 1$, meaning $\omega^1$. $\endgroup$ Aug 22, 2023 at 6:12

1 Answer 1

3
+50
$\begingroup$

Given the subgroup $H=\lbrace 1, \omega, \omega^2, \omega^3, ..., \omega^{n-1}\rbrace$ of order $n$, the Lagrange basis of this subgroup is given by the set of polynomials $\lbrace L_i \rbrace_{i=1}^n$ such that $L_i(w^k) = 1$ if and only if $i=k$ and $0$ otherwise.

The well-known interpolation methods gives $L_i(x) = \frac{\prod_{k \neq i}(x - \omega^k)}{\prod_{k \neq i}(\omega^i - \omega^k)}$.

As per the definitions of the basis, the $L_1$ expression in the question $$L_1(X) = \frac {(X-\omega)(X-\omega^2)(X-\omega^3)...(X-\omega^{n-1})}{(1-\omega)(1-\omega^2)(1-\omega^3)...(1-\omega^{n-1})}$$ does not compute the correct value and is instead computing $L_n$ ($L_0$ given that $\omega^n = \omega^0 = 1)$.

$L_1(x)$ should instead be $$L_1(X) = \frac {(X-1)(X-\omega^2)(X-\omega^3)...(X-\omega^{n-1})}{(\omega-1)(\omega-\omega^2)(\omega-\omega^3)...(\omega-\omega^{n-1})}.$$

Using the numerical example, it can be verified that $L_1(5) = 12$, which corresponds to $L_1(5) = \frac {4(5^4 -1)}{4(5-4)}$.

This can also be verified using the sagemath snippet below

F = GF(17)
w = F(4)
s = 5
idxs = lambda i: [k for k in range(4) if i != k]
li = lambda i,x: prod([x - w^k for k in idxs(i)])/prod([w^i - w^k for k in idxs(i)])
# Sanity check
[[li(j,w^i) for i in range(4)] for j in range(4)]
# L_i(s)
print([li(i,s) for i in range(4)])

The output is [5, 12, 8, 10]. Which also shows that $5$ the result of $L_n(5)$.

Now, what about the connection between the "normal" Lagrange polynomial and the one defined in the paper? The paper "Fractal: Post-Quantum and Transparent Recursive Proofs from Holography" explained this. At a high level, the vanishing polynomial $Z_H(x)$ for $H$ and the polynomials $L_i$ are quite related.

Indeed, $Z_H$ is almost the same as $Z_H(x)/(x-\omega^i)$. But, not quite, since the latter polynomial does not evaluate to $i$ in $\omega^i$, so we need some normalization.

Consider the derivative of $Z_H(x)$, when evaluated at $w^i$ we get $$Z_H'(w^i) = 1\times\prod_{k \neq i}(\omega^i - \omega^k) + (w^i-w^i)\times\text{stuff} = \prod_{k \neq i}(\omega^i - \omega^k).$$ Consequently, we can see that $$L_i(x) = \frac{1}{Z_H'(\omega^i)} \frac{Z_H(x)}{(x-w^i)}.$$

And $$L_1(x) = \frac{1}{n\omega^{-1}} \frac{x^n - 1}{(x-w)}.$$

$\endgroup$
3
  • 1
    $\begingroup$ thanks for getting to this, nice answer, I guessed the derivative had to be involved but had no time to go through the steps $\endgroup$
    – kodlu
    Aug 22, 2023 at 16:18
  • $\begingroup$ @kodlu, it was a nice excuse to look deeper into PLONK : ) $\endgroup$ Oct 5, 2023 at 10:30
  • $\begingroup$ Is there any intuition to this another expression of Lagrange polynomial? $\endgroup$
    – Paul Yu
    Jan 13 at 15:40

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.