Fast amortized KZG proofs

Background

Based on Fast amortized KZG proofs.

Multiple KZG Proofs Generation is different from Multiopening KZG Proof:

• Multiple KZG Proofs Generation means generating
  $n$ KZG proofs
  
  $$[{\pi }_0,{\pi }_1,...,{\pi }_i,...,{\pi }_n]$$ for a
  $n$ opening pairs
  $$[f(y_0)=z_0,f(y_1)=z_1,...,f(y_i)=z_i,...,f(y_n)=z_n]$$
  The requirement here is that the
  $n$ opening proofs are generated from the same polynomial
  $f$
• Multiopening KZG Proof means generating a single proof
  $\pi$ for two or more openings
  $[f(y_1)=z_1,f(y_2)=z_2]$.

In the case of Summa, we are interesting in the former when generating the user inclusion opening proofs. As of today, each proof is generated running the same routine via the create_proof function.

The goal is to explore optimization techniques that come when the multiple opening (KZG) proofs are generated starting from the same polynomial

$f(x)$.

KZG Commitment

Setup

$$[s],[s^2],...,[s^d]$$

Commitment

Generating KZG commitment for polynomial

$f$ of degree

$d$

$$C_f=\sum _{0\le i\le d}{f}_i[s^i]$$

Proof

Say we want to prove that

$f(y)=z$. This is equivalent to prove the existance of the quotient polynomial

$T_y(X)=\frac{f(X)-z}{X-y}$. Note that the quotient polynomial has degree

$d-1$ given the division between two polynomials.

The (opening) proof

$\pi$ is therefore equal to generate a KZG commitment for the quotient polynomial

$$\pi [f(y)=z]=C_{T_y}$$

For the scope of Summa, we want to generate many of these proofs. As many as the number of users of the Custodian.

Generating the commitment

$C_{T_y}$ first requires to compute the coefficients

$t_i$ of the quotient polynomial

$T_y(X)$. These can be computed using the following formula:

• $t_{d-1}=f_d$
• $t_j=f_{j+1}+y\cdot t_{j+1}$

Let's understand why is that the case. The first expression states that the highest degree coefficient (leading term)

$t_{d-1}$ of the quotient polynomial is equal to the highest degree coefficient (leading term) of the polynomial

$f$, namely

$f_d$. The reason of that is rooted in the nature of polynomial division. The leading term of the quotient polynomial is obtained by dividing the leading term of the dividend by the leading term of the divisor. In this case, the leading term of the dividend is

$f_d$, while the leading term of the divisor is

$1$. Therefore the leading term of the quotient is equal to

$f_d$.

The second formula is a way to recursively calculate the next coefficient of the quotient polynomial starting from the new leading coefficient of the dividend. This is rooted in the nature of polynomial long division as you can see from the following example that considers a polynomial

$f$ of degree 3.

$f(X)=2X^3-3X^2+X-5$

$f(2)=1$

$T_y(X)=\frac{f(X)-1}{X-2}=\frac{2X^3-3X^2+X-6}{X-2}$

You can see how the coefficients of the quotient polynomial match the definition above.

To generalize the definition of the quotient polynomial for a polynomial

$f(X)=a_3{X}^3+a_2{X}^2+a_{1}X+a_0$ and a pair

$f(y)=z$

$$T_y(X)=a_3{X}^2+(a_2+y\cdot a_3)X+a1+y\cdot a2+y^2\cdot a3$$

Let's now consider the case in which we need to generate an opening proof for the same polynomial

$f$ but for a different pair of points.

$$\pi [f(b)=c]$$

The quotient polynomial will be

$$T_b(X)=a_3{X}^2+(a_2+b\cdot a_3)X+a1+b\cdot a2+b^2\cdot a3$$

Using this expression, you can tell that, apart from the leading coefficient, all the other coefficients of the quotient polynomials are opening-proof dependent. Namely, the value

$b$ or

$y$ at which we are opening the proof appears inside the coefficient. Also you can note that the value of

$z$ (or

$c$ in the second polynomial) doesn't appear in the quotient polynomial

Now let's see how the actual KZG proof

$\pi$ would look like in the two different cases.

$$\pi [f(y)=z]=C_{T_y}=a_3[s^2]+(a_2+y\cdot a_3)[s^1]+a1+y\cdot a2+y^2\cdot a3$$

$$\pi [f(b)=c]=C_{T_y}=a_3[s^2]+(a_2+b\cdot a_3)[s^1]+a1+b\cdot a2+b^2\cdot a3$$

We can group the first proof by

$y$ and the second proof by

$b$

$$\pi [f(y)=z]=C_{T_y}=a_3\cdot y^2+(a_3\cdot [s^1]+a_2)\cdot y+a_3\cdot [s^2]+a^2\cdot [s^1]+a1$$

$$\pi [f(b)=a]=C_{T_b}=a_3\cdot b^2+(a_3\cdot [s^1]+a_2)\cdot b+a_3\cdot [s^2]+a^2\cdot [s^1]+a1$$

We can see this as a polynomial

$h$ in

$X$

$$h(X)=a_3\cdot X^2+(a_3\cdot [s^1]+a_2)\cdot X+a_3\cdot [s^2]+a^2\cdot [s^1]+a1$$

Note that the coefficients of

$h$ are only dependent of the coefficients

$a_i$ of the initial polynomial

$f$ and on the values

$[s_i]$ of the trusted setup.

The opening proof for whatever point

$y$ or

$b$ can be seen as an evaluation of

$h(X)$ at that point:

$$\pi [f(y)=z]=C_{T_y}=h(y)=a_3\cdot y^2+(a_3\cdot [s^1]+a_2)\cdot y+a_3\cdot [s^2]+a^2\cdot [s^1]+a1$$

$$\pi [f(b)=a]=C_{T_y}=h(y)=a_3\cdot b^2+(a_3\cdot [s^1]+a_2)\cdot b+a_3\cdot [s^2]+a^2\cdot [s^1]+a1$$

So let's say that we have a polynomial

$f$ of degree

$d$ and we want to generate

$n$ KZG opening proofs out of it. The steps needed are:

1. Calculate the coefficients of
   $h$.
2. Perform
   $n$ evaluations of
   $h(X)$

The main takeaway here is that we remove the need to calculate a new quotient polynomial for each of the

$n$ opening proofs. Instead the coefficients of

$h$ needs to be calculated only once and then can be reused to generate the different proofs of inclusion.

FFT

• Requires evaluations to be at the roots of unity
• Direct FFT: go from coefficients to evaluations
  $O(d\cdot logd)$.
• Inverse FFT (interpolation): go from evaluations to coefficients
  $O(d\cdot logd)$

More on that within the paper.

Application

• Requires evaluations to be at the roots of unity for efficiency reasons.

In order to generate

$n$ KZG proofs, it is required to:

1. Calculate the coefficients of
   $h$

Check paragraph 2.2 of the Paper. his operation is

$O(d\cdot logd)$

2. Calculate the
   $n$ evaluations of the polynomial
   $h$ at the roots of unity that corresponds to the KZG proofs.

It turns out that we can use FTT to efficiently calculate the evaluations of

$h$ at the roots of unity starting from its coefficients. This operation is

$O(n\cdot logn)$

TO DO

• Comparative cost analysis