EPF Week 7 Update 8 & 9

After going through Dankrad's IPA note with Pedersen and then going through a few more resources on IPA. 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:

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

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}+\dots +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, 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)]\ast$,

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