Zero-knowledge proofs on mobile devices have the power to revolutionize applications like private transactions, self-sovereign identity, and scalable computation, making them a game-changer in the field. Multi-scalar multiplication (MSM) is a core operation for producing zkSNARKs, and it is the primary bottleneck and barrier for deployment of proving on mobile.
This prize focused on minimizing latency of computing MSM in native mobile applications, which is a large barrier to mass adoption. Competitors had to adapt their skills to a mobile platform with a unique CPU architecture and various resource limitations.
The importance of enhancing the performance of Multiscalar Multiplication (MSM) on mobile devices grows in tandem with the expanding role and capabilities of these devices in our daily lives. By making these operations more efficient, we can offer mobile experiences that reduce latency linked to performance and bolster data security.
ConsenSys Gnark, the winning team for this particular category, was composed of Youssef El Housni and Gautam Botrel. Youssef completed his PhD in Mathematics and Computer Science at Ecole Polytechnique, while Gautam has a background in scientific computing, on the software engineering side.
They utilized their knowledge and experience working with elliptic-curve-based SNARK proof systems to attack the challenge using the Go language, along two CPU architectures, x86 and arm64. In the end, they found that their particular approach yielded “a 40-47% speedup over the state-of-the-art implementation, which was implemented in Rust.” The team plans to use their work in at least two real-world applications: Linea zkEVM by ConsenSys and the Celo network. ConsenSys Gnark penned a detailed research paper on their experience, which can be accessed here.
Nick Stathas, an individual competitor, is a 2021 MIT graduate with a Master of Engineering in Electrical Engineering and Computer Science, with a focus on the intersection between AI and computer systems/software performance engineering. In the past, he spent two years as a software engineer at Jump trading and he recently began a position as a research engineer at OpenAI.
Of ZPrize, Stathas says, “my participation in ZPrize shattered some of my misconceptions regarding software performance engineering, particularly regarding programming languages and the capability of compilers. It was pretty exciting learning a new field and discovering that the best known algorithm for multi-scalar multiplication is quite simple and beautiful. I learned that the state-of-the-art relies on getting the fine-details right, including picking the right data representation and minimizing individual arithmetic operations.”
This challenge was focused on accelerating the execution of MSM on mobile devices. This enhancement could considerably improve the performance of zero-knowledge protocols, leading to a better user experience with mobile applications that are based on zero-knowledge systems. The focus here was on reducing the latency of computing MSM in native mobile applications.
All the contestants used the same benchmark: the Arkworks MSM implementation over BLS12-377 G1. The goal for each participant was to exceed this baseline by at least 10%.
Nick Stathas had this to say about the experience, "Running ZK proofs on mobile devices is impractical today and I felt like this category would have immediate impact on a real problem inhibiting mass adoption of ZK cryptography.” Nick also commented on the complexities of existing systems. "Existing libraries for big number arithmetic and finite field math are quite layered and complex which makes them difficult to optimize end-to-end."
Gautam explained,
"This category (accelerate MSM on Mobile) was the only one targeting common CPUs, albeit on a mobile device.
Accelerating zk primitives for this type of target is important since it is the end-user-facing one. Reaching good performance using CPU only gives zk-tech a greater reach.."
The Gnark team who won the competition, not only optimized the arithmetic of finite fields but also proposed a new coordinate system for twisted Edwards curves suited for the Pippenger MSM algorithm.
Accelerating MSM operations leads to a wide array of improvements for mobile devices. This helps us create more powerful, easy-to-use, and secure experiences with zero-knowledge systems.
Gautam from the Consensys Gnark team put it well when he said, "Since we are building an open source library, having a community wide recognition for our work is great; I think it gives confidence to project looking to use gnark or gnark-crypto that the performances are state of the art and the team is strong." ZPrize and other open-source efforts drive innovation. These platforms provide exciting and impactful opportunities for collaboration between academia and industry, fostering further development and pushing the boundaries of zero-knowledge cryptography.
ZPrize 2023 is currently in the works and we want you to get involved! Head to our Discord to find out more.
