Candidate: Guiwen Luo
Title: On the Computation of Multi-Scalar Multiplication Towards Efficient zkSNARKs
Date: June 20, 2023
Time: 10:00 AM
Place: EIT 3142
Supervisor(s): Gong, Guang
Abstract:
The operation of computing multiple scalar multiplications in an elliptic curve group and then adding them together is called multi-scalar multiplication. Multi-scalar multiplication is the essential operation for proof generation and verification in pairing-based trusted setup zero-knowledge succinct non-interactive argument of knowledge (zkSNARK) protocols, which empower the privacy-preserving features in blockchain applications. Pairing-based trusted setup zkSNARKs usually follow a common paradigm. A public string composed of a list of fixed points in an elliptic curve group called common reference string (CRS) is generated in a trusted manner and all parties have access to it. The prover generates the zkSNARK proof by computing multi-scalar multiplications over the points in CRS. The verifier verifies the proof by computing multi-scalar multiplications and elliptic curve bilinear pairings.
Multi-scalar multiplication in pairing-based trusted setup zkSNARKs has two characteristics. First, all the points are fixed once CRS is generated. Second, the number of points is large. In this paper, we target at $n = 2^c\ (10 \le c \le 21)$, which covers the majority of zkSNARK applications. Our goal in this thesis is to propose and implement efficient algorithms for computing multi-scalar multiplications towards efficient zkSNARKs.
This thesis mainly consists of the following three parts. Firstly, the background knowledge and the existing popular algorithms are introduced. Secondly, two frameworks for computing multi-scalar multiplications over fixed points and five corresponding auxiliary set constructions are proposed. Lastly, the theoretical analysis and software implementation on the instantiations of the proposed frameworks are presented.