# Proving multiple evaluations on multiple polynomials using IPAs

This is a slightly-rewritten version of the original post from [here](https://hackmd.io/@6iQDuIePQjyYBqDChYw_jg/SJeZNp6au).
$$
\def\Gr{\mathbb{G}}
$$

## 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 $\Gr$ 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\Gr$ are generators of $\Gr$ 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:

$$
f_0(z_0) = y_0 \\\vdots \\f_{m-1}(z_{m-1}) = y_{m-1}
$$

## 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} + \ldots +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(X) = \sum_{i=0}^{m-1} r^i \frac{f_i(X)}{t-z_i}$$

Note that $g'_1(t) = g_1(t)$, so proving an evaluation proof for $g'_1(t)$ is equivalent to proving $g_1(t)$.
Crucially, the verifier is able to compute the commitment for $g'_1(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$