Cloud-MSM: The first FPGA MSM library for ZKP
Open-source available for AWS F1
The Problem with MSM
Zero Knowledge Proofs (ZKPs) are computationally intensive algorithms. Their performance requires an immense amount of processing time as measured in microseconds and power consumption as measured in watts. A major reason for these expenses is Multi-Scalar Multiplication (MSM), a key component in many kinds of Zero Knowledge Proofs.
Multi-Scalar Multiplication is a fundamental mathematical computation required in many forms of Elliptic Curve Cryptography (ECC), an umbrella term under which Zero Knowledge Proofs lie. MSM is a major computational bottleneck due to the large number of Elliptic Curve additions it requires. This results in a time-consuming and energy intensive step for ZK proof generation, which consists of large-size polynomial computations.
Hardware optimizations for ZKP often take the form of parallelization, which means running a number of computations at the same time, in order to cut down on the computation time of calculation.
Interest in optimizing MSMs by decreasing their computational time and energy requirements was recently prompted by their application to ZK-SNARKs, where they often turn out to be a major computational bottleneck. ZK-SNARKs, which stands for Zero Knowledge, Succinct Non-Interactive Argument of Knowledge, are one of two types of Zero Knowledge Proof schemes.
Until now, the majority of hardware experimentation with accelerating MSM has been done with Graphics Processing Units (GPUs). Ingonyama Research brings functioning and operational MSM for the first time to FPGAs, or Field Programmable Gate Arrays, which we believe to be a superior approach for accelerating MSM computation on the way to developing Zero Knowledge for Application Specific Integrated Circuits (ASICs).
We believe that the energy efficiency in FPGAs is more suitable for MSM, due to their function specific design as compared to GPU’s narrower flexibility. With FPGAs at the base, we take a holistic approach to MSM optimization, with designs based on a novel algorithmic approach and hardware specific optimizations. At the core, we rely on a modular multiplication technique, which we also deem to be of independent interest from this research.
Delving deeper, we use the Parallel Bucket Method and low latency Complete Elliptic Curve addition formulae along with Domb-Barret Reduction to produce results with improved energy efficiency and speeds comparative to GPUs.
We implemented and tested our design on FPGA, and in our research paper highlight the promise of optimized hardware over state-of-the-art GPU-based MSM solvers, in terms of both speed and energy expenditure.
Cloud MSM Library
In line with Ingonyama values of transparency and collaboration, we are releasing our FPGA Cloud MSM Library to the public on the AWS F1 environment.
This allows programmers or researchers working on Zero Knowledge projects that require MSM computation to use our library in any way they see fit. Developers can take our code and implement it, either on FPGAs in their possession, or in a cloud environment by renting an FPGA configuration via AWS.
Cloud MSM is especially beneficial for mobile based applications, because it allows programs to outsource computationally intensive ZKP to the cloud. This results in Zero Knowledge accessibility, from any device.
We will continue to add to the cloud MSM library as our research continues, with our goal of making MSM computation faster still. We believe it is possible to make MSM computation 2 to 4 times faster than its current version, on the same FPGA hardware.
Finally, it is our hope that releasing the cloud MSM library encourages community experts to review and improve upon our designs, as we work to decrease the computational strain of ZKP.
Follow our Journey:
Twitter: https://twitter.com/Ingo_zk
Github: https://github.com/ingonyama-zk
Latest work: https://github.com/ingonyama-zk/cloud-ZK
Join us: https://www.ingonyama.com/careers
