Proving multiple evaluations on multiple polynomials using IPAs

This is a slightly-rewritten version of the original post from here.

$$$$

Introduction

This document explains how to open different polynomials at different points.
The opening proof consists of one inner-product argument (IPA) proof, one commitment and one scalar.

The key application here is computing a slim Verkle proof fast!

Notation

Let

$\mathbb{G}$ be a group of order

$p$ whose group operation is denoted additively.

Let

$c=[f(X)]$ denote a polynomial commitment to

$f(X)$, typically done as:

$$c=\prod _{i=0}^n{g}_i^{f_i}$$
where

$g_i\in \mathbb{G}$ are generators of

$\mathbb{G}$ and

$f=[f_0,\dots ,f_n]$ are the coefficients of the degree-

$n$ polynomial

$f$.

Statement

Given

$m$ IPA commitments

$C_0=[f_0(X)]...C_{m-1}=[f_{m-1}(X)]$, we want to prove evaluations:

$$\begin{gathered} f_0(z_0)=y_0 \\ ⋮ \\ {f}_{m-1}(z_{m-1})=y_{m-1} \end{gathered}$$

Batch proof using two IPA proofs

1. Let
   $r\leftarrow H(C_0,...C_{m-1};z_0,...,z_{m-1};y_0,...,y_{m-1})$

$$g(X)=r^0\frac{f_0(X)-y_0}{X-z_0}+r^1\frac{f_1(X)-y_1}{X-z_1}+\dots +r^{m-1}\frac{f_{m-1}(X)-y_{m-1}}{X-z_{m-1}}$$

The prover starts off by committing to

$g(X)$, we denote this by

$C=[g(X)]$.

The prover's job is to now convince the verifier that

$C$ is a commitment to

$g(X)$. We do this by evaluating

$g(X)$ at some random point

$t$

We split the evaluation into two parts

$g_1(t)$ and

$g_2(t)$.

$g_2(t)$ can be computed by the verifier.

However,

$g_1(t)$ cannot be computed by the verifier since it involves random evaluations of the polynomials

$f_i(X)$. Instead, the prover will compute

$g_1(t)$ and send a proof of it's correctness.

$$g_1(t)=\sum _{i=0}^{m-1}{r}^i\frac{f_i(t)}{t-z_i}$$

$$g_2(t)=\sum _{i=0}^{m-1}{r}^i\frac{y_i}{t-z_i}$$

2. Let
   $t\leftarrow H(r,C)$

We note that

$g_1(X)=\sum _{i=0}^{m-1}{r}^i\frac{f_i(X)}{X-z_i}$.
However, the verifier will work with:

$$g_1^{\prime }(X)=\sum _{i=0}^{m-1}{r}^i\frac{f_i(X)}{t-z_i}$$

Note that

$g_1^{\prime }(t)=g_1(t)$, so proving an evaluation proof for

$g_1^{\prime }(t)$ is equivalent to proving

$g_1(t)$.
Crucially, the verifier is able to compute the commitment for

$g_1^{\prime }(X)$, which it could not do for

$g_1(X)$ due to the

$X-z_i$'s in the denominator.

Now we form two IPA proofs:

• One for
  $g_1(X)$ at
  $t$. We call this
  ${\pi }_1$
• One for
  $g(X)$ at
  $t$. We call this
  $\pi$

The prover now computes

$y=g_1(t)$

The proof consists of

$C,({\pi }_1,y),\pi$

In this non-aggregated variation, the prover does not need to add

$[g_1(X)]$ to the transcript.

Verification

The Verifier ultimately wants to verify that

$C$ is the commitment to the polynomial

$g(x)$.

The verifier computes

$r$ and

$t$.

The verifier also computes

$g_2(t)$, we mentioned above that they can do this by themselves.

Computing

$g(t)$

The verifier now needs to compute

$g(t)$:

$g(t)=g_1(t)-g_2(t)$

• We know that
  $g_1(t)$ was supplied in the proof as
  $y$.
• $g_2(t)$ can be computed by the verifier.

Hence the verifier can compute

$g(t)$.

Note, however, that they cannot be sure that

$g_1(t)$ is the correct computation by the prover. They need to build

$[g_1(X)]$ themselves and verify it against

$g_1(t)$

Computing

$[g_1(X)]$

This is

$g_1(X)$:

$$g_1(X)=\sum _{i=0}^{m-1}{r}^i\frac{f_i(X)}{t-z_i}$$

Hence

$[g_1(X)]$ is:

$$[g_1(X)]=\sum _{i=0}^{m-1}\frac{r_i}{t-z_i}{C}_i$$

The verifier is able to compute this themselves, and so is able to verify the proof

${\pi }_1$ for

$g_1(t)$ against

$[g_1(X)]$.

Is

$g(t)$ correct?

Note now that since

$g_1(t)$ was verified to be correct and

$g_2(t)$ was computed by the verifier, we can be sure that

$g(t)$ is correct.

Verify

$g(x)$ at

$t$

We can now verify

$g(t)$ against

$C=[g(X)]$ using the proof

$\pi$.

Complexity

The communication complexity of this protocol is two IPA proofs, 1 scalar and 1 commitment. We can get a better protocol by aggregating things together!

More efficient batch proof using one IPA proof

We now present a protocol to aggregate the two IPA proofs together, only requiring one IPA proof.

Prover

2. Let
   $q\leftarrow H(t,[g_1(X)])$

The prover no longer computes an IPA proof for

$g_1(X)$ and

$g(X)$.
Instead, the prover combines them using

$q$.

Let:

$$g_3(X)=g_1(X)+q\cdot g(X)$$

Now, we form an IPA proof

${\pi }_3$ for

$g_3(X)$ at

$t$.

The prover still computes

$y=g_1(t)$

The smaller proof now consists of

$(C=[g(X)],{\pi }_3,y)$

Verifier

In the previous step, the verifier checked

$g_1(t)$'s proof

${\pi }_1$ against

$[g_1(X)]$.
We delay this verification and instead compute:

• $[g_3(X)]=[g_1(X)]+q\cdot [g(X)]$
• $g_3(t)=g_1(t)+q\cdot g(t)$

The verifier now checks

$g_3(t)$'s proof

${\pi }_3$ against

$[g_3(X)]$.

With overwhelming probability over

$q$ this will only return true iff

$[g_1(X)]$ and

$[g(X)]$ opened at

$t$ are

$g_1(t)$ and

$g(t)$ respectively, from the equation.

Complexity

The communication complexity of the protocol is one IPA Proof, one commitment and one scalar.

Do we need to add

$[g_1(X)]$ to the transcript?

In the KZG document, this is

$h(X)$

If we were able to avoid this, then we could save a lot on prover time, as they could evaluate each

$f_i$ at

$t$, then do

$\frac{r^i\cdot f_i(t)}{t-z_i}$ instead of needing to first compute

$\frac{r^i\cdot f_i(X)}{t-z_i}$. (In the non-batched version)

However, we do need to do this because the challenge

$q$ is aggregating

$[g_1(X)]$ and

$[g(X)]$, we need to bind

$[g_1(X)]$ to the challenge

$q$.

There may be an argument to say that since

$g_1(X)$ uses

$t$ and simply using

$q=H(t)$ is enough to bind

$g_1(X)$ to

$q$. We can restate this problem as:

Given two polynomials :

$f(X,Y)$ and

$g(X)$

I generate a completely random variable

$t$.

If I want to add together

$f(X,t)$ and

$g(x)$

Is it enough to generate randomness based on

$g(X)$ and

$t$ alone?

The answer is no because the prover has free reign over

$X$ and can change it without affecting

$q$