# EPF Week 7 Update 8 & 9
After going through [Dankrad's IPA note with Pedersen](https://dankradfeist.de/ethereum/2021/07/27/inner-product-arguments.html) and then going through a few more [resources on IPA](https://www.youtube.com/watch?v=RaEs5mnXIhY&t=1582s&pp=ygUXaW5uZXIgcHJvZHVjdCBhcmd1bWVudHM%3D). I finally realised how IPA multipoint really worked!

### Intro
Here I'll talk about how we can open multiple polynomials at different points.
Finally aggregating to 1 proof, 1 commitment and 1 scalar.

### Definition

Given $m$ IPA commitments $C_0 = [f_0(X)] ... C_{m-1} = [f_{m-1}(X)]$, prove evaluations:

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

where $z_i \in \{0,...,d-1\}$

### Prover

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 initially commits to $g(X)$, we denote this by $D$ or $[g(X)]$.

Now the prover has to convince the verifier that $D$ is a commitment to $g(X)$. We do this by evaluating $g(X)$ at some random point $t$.

We can split the evaluation into $g_1(t)$ and $g_2(t)$, $g_2(t)$. These two can be computed by the verifier, while $g_1(t)$ cannot, because it involves random evaluations at the polynomials $f_i(X)$.

Hence the verifier is able to compute $g_2(t)$, and the prover will compute $g_1(t)$ and send a proof of it's correctness.

The expressions are as following:

$$
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,D)$

We note that $g_1(X) = \sum_{i=0}^{m-1} r^i \frac{f_i(X)}{X-z_i}$. However, we specify it as $\sum_{i=0}^{m-1} r^i \frac{f_i(X)}{t-z_i}$ because $g_1(t)$ is also able to prove for an opening, hence the verifier is able to compute the commitment for it.

Thereby, we finally boil down to 2 IPA proofs. One for $g_1(X)$ at $t$. We call this $\pi$. And the other one for $g(X)$ at $t$. We call this $\rho$.

Hence, the prover now computes $y = g_1(t)$, and the proof consists of $D, (\pi, y), \rho$.

However, this is still the variant where we haven't yet *aggregated* the proofs.

### Verifier

The Verifier ultimately wants to verify that $D$ is the commitment to the polynomial $g(x)$, hence he computes $r$ and $t$.

Then the verifier also computes $g_2(t)$, by themselves.

However, the verifier cannot assert to the fact that $g_1(t)$ is the correct computation by the prover. The verifier has to separately build $[g_1(X)]$ and then re-check it with $g_1(t)$.

The verifier proceeds with computing $[g_1(X)]$. The verifier as I said, is able to compute this by themselves, to cross check it with $g_1(t)$ using the `ipa_verify()` function, the reference Go [implementation](https://github.com/crate-crypto/go-ipa/blob/master/ipa/verifier.go#L14-#L93), using ($[g_1(X)]$,$g_1(t)$,$\pi$) params.

As $g(t) = g_1(t) - g_2(t)$, 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.

#### Verifying $g(x)$ at $t$

We now call `ipa_verify()` passing ($D = [g(X)]*$,$g(t)$,$\rho$) as params.

Now we have 2 IPA proofs, 1 commitment and 1 scalar.

Now we are left with `aggregation` to 1 final IPA proof.

### Aggregating...

#### Prover's side

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

The prover no longer computes an IPA proof for $g_1(X)$ and $g(X)$ instead they combine them using $q$.

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

Now we form an IPA Proof for $g_3(X)$ at $t$. Lets call this $\sigma$.

The prover still computes $y = g_1(t)$

The proof consists of $D, \sigma, y$

#### Verifier's side

In the previous step, the verifier called $[g_1(X)]$ ,$g_1(t)$ with $\pi$, 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)$

We now call `ipa_verify()` using ($[g_3(X)]$,$g_3(t)$,$\sigma$).

This strategy finally boils down the proof to 1 IPA proof, 1 commitment and 1 scalar.