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?


1 Answer 1


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

  • $\begingroup$ 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. $\endgroup$
    – user93353
    Jan 23, 2023 at 12:03
  • $\begingroup$ 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. $\endgroup$
    – Daniel S
    Jan 24, 2023 at 10:12
  • $\begingroup$ Thank you ..... $\endgroup$
    – user93353
    Jan 24, 2023 at 12:10

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.