Trusted Setup in zkSNARKs— Powers of Tau vs Lagrange basis
In the spirit of unraveling the mystery of the black box known as “zero-knowledge proofs”, this article seeks to address some aspects of the trusted setup and to explore its impact on the performance of the prover. When we delve into the zkSNARK setup, it is divided into three components: the Prover, Verifier, and Trusted Setup. From a performance perspective, the verifier must be light and swift to validate proofs. Conversely, the prover bears a hefty burden, undertaking extensive and exhausting computations to generate the proof. Sometimes, selecting the appropriate form of trusted setup can help alleviate this burden.
Polynomials serve as one of the foundational pillars of zero-knowledge proofs, critically consuming approximately 80% of computational time due to operations like polynomial multiplication, evaluations, and multi-scaler multiplications. These operations, notably, become performance bottlenecks. Significantly, the polynomials dealt with are of high order, often equal to or exceeding 2²⁰.
Let’s explore an example involving polynomial commitment in a cryptographic setting. Polynomial commitment is a technique that allows a prover to commit to a particular polynomial in a way that is verifiable yet reveals no additional information about the polynomial itself.
To elaborate, consider two polynomials, A and B, each of degree n=2¹⁸−1. The prover seeks to multiply these two polynomials, obtaining a resulting polynomial, P. Multiplying two polynomials of degree n will produce a polynomial of degree 2n. In this instance, after the multiplication, the degree of P would be 2×(2¹⁸−1). Subsequently, P must be evaluated at a random value, denoted as τ (tau), without revealing the coefficients of P to a verifier.
This process forms a commitment to polynomials A and B because the prover demonstrates the ability to evaluate P at τ without revealing A, B, or P explicitly. Verifiability is achieved through the use of cryptographic techniques to assure the verifier that P(τ) is computed correctly without conveying any additional information about P, A, or B.
In addition, the value of tau is obscured by the properties of elliptic curves. When any value (a scalar) is multiplied by a point on the elliptic curve, the result is also a point on the elliptic curve. Thanks to the discrete logarithm problem, it is difficult to deduce what the original value was. All of these Powers of Tau are generated during the trusted setup. The setup agent selects a random value for tau and calculates all powers up to 2n-1, then multiplies them by a point on the elliptic curve G — often referred to as a generator point. This setup is frequently referred to as a Structured Reference String (SRS).
From our schooling, we are familiar with how to multiply polynomials: we simply multiply each term from polynomial A with each term in polynomial B. The algorithmic complexity of this conventional approach is O(n²). In our instance, where n=2¹⁸, this means we need to perform 68,719,476,736 multiplications. If we assume that each multiplication takes 1 millisecond to complete, this operation would take approximately 795 days to finish. Fortunately, there are more efficient methods available. We can convert polynomials into points using evaluation methods and perform element-wise multiplication, which has a linear time complexity of O(n). The most expedient way to evaluate polynomials is to utilize Fast Fourier Transformations (FFT).
Note: In order to multiply polynomials A and B, they must be padded with zero coefficients to ensure that no results are lost. The code will be implemented to accommodate this requirement.
The final step requires converting the evaluated form of P back to a polynomial, so we can apply our Powers of Tau from the trusted setup to obtain the commitment. For this, we can utilize the Inverse Fast Fourier Transformation.
While at first glance obtaining a polynomial commitment in this manner may seem like a significant overhead, in reality, the algorithmic complexity of such an approach is O(n log n), which is less than O(n²).
But what if we could use the evaluated form of P to compute the commitment, thereby removing the last IFFT operation from the routine? In this scenario, the setup agent would have to perform extra work: take the generated SRS and convert it into Lagrange basis. This additional action is entirely justified since the setup agent only has to do it once, whereas the prover must go through the routine each time a proof is generated.
Adding one extra step to the trusted setup essentially eliminates the necessity of converting P back to polynomial form. Thus, the prover simply has to compute the commitment:
The code to this article I’ve submitted here.
For this test I used BLS12–381 elliptic curve, and entire example is written in rust, here are some of the results:
*******************************
* *
* Powers of Tau vs Lagrange *
* *
*******************************
Options:
1. Run commitment with pre-generated SRS
2. Generate new SRS
3. Exit
> 1
------------ Setup ------------
Loading powers of tau ...
Loading powers of tau - Elapsed: 99.25125ms
Loading powers of tau in Lagrange basis ...
Loading powers of tau in Lagrange basis - Elapsed: 65.753583ms
Polynomial Generation ...
Polynomial Generation - Elapsed: 2.853042ms
------------ Prover ------------
Witness Generation ...
Witness Generation - Elapsed: 2.573541ms
Commitment Calculation (Powers of Tau) ...
Commitment Calculation (Powers of Tau) - Elapsed: 1.000773667s
Commitment Calculation (Lagrange) ...
Commitment Calculation (Lagrange) - Elapsed: 943.58275ms
------------ Result ------------
Commitment[t] G1: (0x967dbd96321619d880a2faa30118ce2466362e14d850ea45151479da9deecb9dfe42451ff1f7a6324fb3ad6a89fe026, 0x14f969cd42ed59a9b911849e90bbe8542c6555f9682860d2920b1a5e29e5ee1387ead3e7c0b58778219539d31ca33b67)
Commitment[l] G1: (0x967dbd96321619d880a2faa30118ce2466362e14d850ea45151479da9deecb9dfe42451ff1f7a6324fb3ad6a89fe026, 0x14f969cd42ed59a9b911849e90bbe8542c6555f9682860d2920b1a5e29e5ee1387ead3e7c0b58778219539d31ca33b67)This article was partially inspired by a post from Figment Capital about accelerating Zero-Knowledge Proofs, wherein they explore additional techniques to enhance the Prover’s performance.
References:
