%20.png)
The Accelerating MSM Operations Competition focused on improving multi-scalar multiplication (MSM) for the BLS 12-377 G1 curve by increasing its speed and efficiency. Participants needed to develop the lowest-latency MSM technique using either a GPU or an FPGA. This competition is important because computing MSM operations is a major bottleneck for zero-knowledge proving. zk-SNARKs.
Multiscalar multiplication refers to an operation that involves performing multiple scalar multiplications simultaneously on different points of an elliptic curve and then adding the results together. This operation is a common building block for many cryptographic primitives, including zero-knowledge proofs and protocols.
MSM is crucial in both proof generation and verification processes within a zk-SNARK. Provers and verifiers work with points on an elliptic curve and a set of numbers (scalars) from a unique range called the scalar field. The BLS 12-377 G1 curve is one such curve over which zkSNARKs are defined. .
MSM involves calculating polynomial commitments, a vital part of the proof, by performing mathematical operations with these points and scalars. Similarly, during proof verification, the verifier carries out MSM operations on the curve to establish the proof's correctness without revealing the secret information.
Efficient multiscalar multiplication algorithms can help minimize the proof sizes, verification times, and overall computational costs of these zero-knowledge systems. Optimizing MSM for the BLS 12-377 G1 curve enhances the efficiency and performance of zk-SNARKs that utilize this curve, leading to faster proof generation and verification processes. This optimization enables more practical, scalable, and efficient privacy-preserving applications.
The most common approach to computing MSMs is called Pippenger's algorithm takes advantage of the sparsity of the scalar representation and the efficient use of buckets to speed up the multiscalar multiplication process. The choice of the window size w is crucial for performance, as it determines the trade-off between the number of point additions and point doublings. In general, larger window sizes lead to fewer point additions at the cost of more point doublings, while smaller window sizes lead to the opposite. The optimal window size depends on the specific use case, the number of points involved, and the hardware or platform being used.
The Open Division Prize 1a category required participants to create the most efficient MSM technique using a GPU. Matter Labs tied with Yrrid Software for first place in this category, both achieving a speedup well above 2x over the baseline implementation.
This challenge required participants to efficiently adapt the algorithm to the GPU architecture, manage memory bandwidth and latency, and minimize divergent execution paths for optimal performance.
For the Matter Labs team, which was composed of Robert Remen and Michael Carilli, participation in the competition was a natural fit. Before joining Matter Labs at large in October 2021, Robert collected a masters degree in applied informatics and worked for six years on designing and implementing machine learning algorithms that were run on GPUs and applied in the training of algorithmic trading models. Michael, prior to joining Matter Labs full time in June 2022, was employed at NVidia, mainly working on Pytorch - a Python-based machine learning framework.
Since the Matter Labs team already used MSM in their current proof system this formed the basis for their ZPrize submission. Naturally, the changes and improvements developed for the submission were then backported to their MSM that they currently use in their proof system in production.
The Yrrid Software team was composed of three members: Niall Emmart, Sougata Bhattacharya, and Antony Suresh. Sougata and Antony each have over 20 years experience building scalable, high-performance web and back-end applications, which made a perfect counterpoint for Nial’s extensive knowledge of finite field arithmetic and GPU experience. Together this was an excellent opportunity to showcase Yrrid's skill and expertise at optimizing the core operations of ZK-SNARK systems.
The Open Division Prize 1b competition, on the other hand, required participants to create the most efficient MSM technique using an FPGA. Jane Street engineers Ben Devlin, Rahul Yesantharao, Andy Ray, and Fu Yong Quah comprised the winning team, HardCaml, in this category. When looking at ZPrize categories the group was immediately drawn to big data problems with pre-existing benchmarks to compete against as well as to the idea of specialized compute accelerators and moving computation off general-purpose CPUs. Despite the complexity of the MSM problem, they were able to create an efficient and optimized MSM technique using FPGAs.
Their team’s technique was to fundamentally re-optimize every underlying component, from the mathematical algorithms to the heuristics and physical hardware layout, in the context of the overall MSM computation. This synergistic, ground-up approach made their final architecture as fast as possible. The competition raised visibility and generated interest in HardCaml, the hardware design language used at Jane Street, providing opportunities for new partnerships and collaborations.
The challenge of improving MSM is particularly significant because of the limited resources of FPGAs and GPUs. Efficient use of resources and algorithm design that takes advantage of parallelism is critical. Participants in the competition faced the challenge of beating an already-strong baseline implementation of Pippenger’s algorithm. The winning teams broke down the problem into its underlying components and fundamentally re-optimized every component to squeeze out as much efficiency as possible.
By developing more efficient MSM techniques for zk-SNARK schemes, we can improve the speed and scalability of privacy-preserving applications. The ZPrize competition provides an opportunity for participants to showcase their skills in cryptography and contribute to the advancement of zero-knowledge proof technology. Through their participation, winners gain valuable experience and recognition while contributing to the wider crypto community. ZPrize is an important step towards building a more secure and efficient digital world, where privacy and security are paramount.
Interested in being a part of ZPrize 2023? Head to our Discord to get involved.
