This prize focused on maximizing throughput/minimizing latency of these operations on client-type devices and blockchain-based VMs, specifically the WebAssembly (WASM) runtime. Both elliptic curve operations and finite field arithmetic fall under the purview of Multi-Scalar multiplication (MSM) operations. MSM is one of the core operations used in ZK-SNARK proving systems and is very compute intensive, with most of the run-time spent doing finite field arithmetic. With regards to blockchain-based virtual machines(VMs), in particular, improved elliptic curve operations and finite field arithmetic leads to better overall performance on just about every level. The competition focused on improvements for the BLS-12-381 curve. For Poseidon hash, BLS12-381 is more efficient than BLS12-377, to make Poseidon hash secure, BLS12-377 needs around 66% more computation and latency than BLS12-381. The performance of Poseidon hash is critical and widely used in many industry products such as Filecoin and Zcash.
Overall, work with accelerating these types of operations leads to more efficient algorithms in any context where MSM operations related to elliptic curves and finite field arithmetic are employed. Cryptographic protocols(non-blockchain), communication protocols, identity and access management protocols, and blockchain protocols benefit from all strides made in this field through improvements in speed, efficiency, scalability, and security.
Yrrid Software, which placed as the winning team for this category, has truly deep experience in the niche focuses of this particular prize. Dr. Niall Emmart has 20 published papers in the field, while Sougata Bhattacharya and Antony Suresh each have over 20 years experience building scalable, high-performance web and back-end applications directly dependent upon efficient elliptic curve operations and finite field arithmetic. Yrrid Software says “The ZPrize has been an excellent opportunity to showcase Yrrid's skill and expertise at optimizing the core operations of ZK-SNARK systems. Yrrid's medium and long term interests are to provide consulting services to the community.” Sougata and Antony's expertise building web applications were key benefits for this competition. By the end of the competition, Yrrid had improved MSM performance by 5.41x (over the provided baseline) for WASM.
Gregor, who came in 2nd place, recognized that performance of finite field multiplication could be the main decider. Midway through the competition time, he realized the smaller limb size trick (which decided the competition), and had a pretty fast version based on Montgomery multiplication. Gregor points out that he and Yrrid implemented all the low-level algorithms from scratch rather than using existing libraries which were not optimized for Wasm; he believes this made the difference. This approach came with its own challenges, due to the very manual, raw Wasm approach, there were a lot of bugs with accessing the wrong memory, not zeroing memory, etc, Gregor noted these were hard to debug and could've been completely avoided by using a high level language and compiling that. Gregor provides a detailed write up of his ZPrize experience here, github README.
As a result of the challenges experienced relating to Wasm, Gregor used his work to launch wasmati, a Typescript library to write Wasm at the instruction level, which he talks about in his blog post here.
The track of this particular prize focused on accelerating elliptic curve operations and finite field arithmetic, which is essential to improving the speed and efficiency of devices such as clients and blockchain-based VMs, particularly those focusing on the WebAssembly (WASM) runtime. The WebAssembly runtime was chosen due to its relative ease of use compared to other similar formats and such devices were selected because of their proven reputation for being optimal for parallel processing. Participants aimed to achieve the lowest combined latency of MSM over a range of input vector lengths in WASM runtimes. As Gregor says, “the whole goal is to make something for the web / JS ecosystem.”
Accelerating elliptic curve operations and finite field arithmetic leads to better performance of cryptographic algorithms that are based on elliptic curve cryptography and leads to higher security of systems dependent upon said algorithms, along with scaling the impact of cryptographic applications such as decentralized identity management and decentralized communications services.
All in all, the more impact is made in this field, the more new business opportunities will arise for organizations looking to leverage tech tied to elliptic curve cryptography. ZPrize and similar open-source efforts will continue to help to bring about this future and more powerful, more easily usable ZK. Participation in the ZPrize competition continues to create opportunities for academic and industry collaboration across the greater area 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.
