Based on Fast amortized KZG proofs.
Multiple KZG Proofs Generation is different from Multiopening KZG Proof:
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 .
Generating KZG commitment for polynomial of degree
Say we want to prove that . This is equivalent to prove the existance of the quotient polynomial . Note that the quotient polynomial has degree given the division between two polynomials.
The (opening) proof is therefore equal to generate a KZG commitment for the quotient polynomial
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 first requires to compute the coefficients of the quotient polynomial . These can be computed using the following formula:
Let's understand why is that the case. The first expression states that the highest degree coefficient (leading term) of the quotient polynomial is equal to the highest degree coefficient (leading term) of the polynomial , namely . 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 , while the leading term of the divisor is . Therefore the leading term of the quotient is equal to .
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 of degree 3.
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 and a pair
Let's now consider the case in which we need to generate an opening proof for the same polynomial but for a different pair of points.
The quotient polynomial will be
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 or at which we are opening the proof appears inside the coefficient. Also you can note that the value of (or 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.
We can group the first proof by and the second proof by
We can see this as a polynomial in
Note that the coefficients of are only dependent of the coefficients of the initial polynomial and on the values of the trusted setup.
The opening proof for whatever point or can be seen as an evaluation of at that point:
So let's say that we have a polynomial of degree and we want to generate KZG opening proofs out of it. The steps needed are:
The main takeaway here is that we remove the need to calculate a new quotient polynomial for each of the opening proofs. Instead the coefficients of needs to be calculated only once and then can be reused to generate the different proofs of inclusion.
More on that within the paper.
In order to generate KZG proofs, it is required to:
Check paragraph 2.2 of the Paper. his operation is
It turns out that we can use FTT to efficiently calculate the evaluations of at the roots of unity starting from its coefficients. This operation is