Score:3

Why is Lagrange interpolation required in Batch Opening case of KZG/Kate PCS?

et flag

From here - Batch Opening of KZG PCS


One can prove multiple evaluations $(\phi(e_i) = y_i)_{i\in I}$,for arbitrary points $e_i$ using a constant-sized KZG batch proof, $\pi_I = g^{q_I(\tau)}$, where

\begin{align} \label{eq:batch-proof-rel} q_I(X) &=\frac{\phi(X)-R_I(X)}{A_I(X)}\\ A_I(X) &=\prod_{i\in I} (X - e_i)\\ R_I(e_i) &= y_i,\forall i\in I\\ \end{align}

$R_I(X)$ can be interpolated via Lagrange interpolation in $O(\vert I\vert\log^2{\vert I\vert})$ time as:

\begin{align} R_I(X)=\sum_{i\in I} y_i \prod_{j\in I,j\ne i}\frac{X - e_j}{e_i - e_j} \end{align}


My question here is as to why Lagrange interpolation is needed for finding $R_I(X)$?

All the $e_i$'s are known, so $A_I(X)$ is a known polynomial. If you use long division to divide $\phi(X)$ by $A_I(X)$, you will get $q_I(X)$ with $R_I(X)$ as the reminder. So why Lagrange Interpolation is needed here?

Down below, the page also says that $A_I(X)$ is also interpolated. Again why?

Score:2
ru flag

It's computational efficiency rather than mathematical necessity.

Using interpolation means that the computation can be done with complexity independent of the degree of $\phi(X)$. For $\phi(X)$ of large degree relative to the size of $|I|$, interpolation will be much quicker than polynomial division.

The reference to interpolating $A_I(X)$ simply refers to constructing $A_I(X)$ using the product tree described (here interpolation just means the construction of a polynomial satisfying constraints rather than specifically Lagrange interpolation).

et flag
Hey, one more question on the same thing. The original Kate Paper says $R(x)$ is handed by the Prover to the verifier. However other documents like the one I linked to in my question say that the verifier also figures out $R(x)$ by Lagrange's Interpolation. I understand how the verifier can do this, but I wondering about the inconsistency. Is this an optimisation - i.e. to reduce the size of communication between prover & verifier. Also, it's a trade-off since the verifier would need to spend time doing the interpolation.
Daniel S avatar
ru flag
As well as the trade off, with interpolation, the verifier has the choice to only verify a subset or to amalgamate proofs. I could see how this might lead to more efficiency.
et flag
Thank you .....
I sit in a Tesla and translated this thread with Ai:

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.