Try   HackMD

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
    [π0,π1,...,πi,...,πn]
    for a
    n
    opening pairs
    [f(y0)=z0,f(y1)=z1,...,f(yi)=zi,...,f(yn)=zn]

    The requirement here is that the
    n
    opening proofs are generated from the same polynomial
    f
  • Multiopening KZG Proof means generating a single proof
    π
    for two or more openings
    [f(y1)=z1,f(y2)=z2]
    .

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],[s2],...,[sd]

Commitment

Generating KZG commitment for polynomial

f of degree
d

Cf=0idfi[si]

Proof

Say we want to prove that

f(y)=z. This is equivalent to prove the existance of the quotient polynomial
Ty(X)=f(X)zXy
. Note that the quotient polynomial has degree
d1
given the division between two polynomials.

The (opening) proof

π is therefore equal to generate a KZG commitment for the quotient polynomial

π[f(y)=z]=CTy

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

CTy first requires to compute the coefficients
ti
of the quotient polynomial
Ty(X)
. These can be computed using the following formula:

  • td1=fd
  • tj=fj+1+ytj+1

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

td1 of the quotient polynomial is equal to the highest degree coefficient (leading term) of the polynomial
f
, namely
fd
. 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
fd
, while the leading term of the divisor is
1
. Therefore the leading term of the quotient is equal to
fd
.

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)=2X33X2+X5
f(2)=1

Ty(X)=f(X)1X2=2X33X2+X6X2

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

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

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

To generalize the definition of the quotient polynomial for a polynomial

f(X)=a3X3+a2X2+a1X+a0 and a pair
f(y)=z

Ty(X)=a3X2+(a2+ya3)X+a1+ya2+y2a3

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.

π[f(b)=c]

The quotient polynomial will be

Tb(X)=a3X2+(a2+ba3)X+a1+ba2+b2a3

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

π would look like in the two different cases.

π[f(y)=z]=CTy=a3[s2]+(a2+ya3)[s1]+a1+ya2+y2a3

π[f(b)=c]=CTy=a3[s2]+(a2+ba3)[s1]+a1+ba2+b2a3

We can group the first proof by

y and the second proof by
b

π[f(y)=z]=CTy=a3y2+(a3[s1]+a2)y+a3[s2]+a2[s1]+a1

π[f(b)=a]=CTb=a3b2+(a3[s1]+a2)b+a3[s2]+a2[s1]+a1

We can see this as a polynomial

h in
X

h(X)=a3X2+(a3[s1]+a2)X+a3[s2]+a2[s1]+a1

Note that the coefficients of

h are only dependent of the coefficients
ai
of the initial polynomial
f
and on the values
[si]
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:

π[f(y)=z]=CTy=h(y)=a3y2+(a3[s1]+a2)y+a3[s2]+a2[s1]+a1

π[f(b)=a]=CTy=h(y)=a3b2+(a3[s1]+a2)b+a3[s2]+a2[s1]+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

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

  • Requires evaluations to be at the roots of unity
  • Direct FFT: go from coefficients to evaluations
    O(dlogd)
    .
  • Inverse FFT (interpolation): go from evaluations to coefficients
    O(dlogd)

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(dlogd)

  1. 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(nlogn)

TO DO

  • Comparative cost analysis