.png)
Number-theoretic transformations (NTT) are essential building blocks for most zero-knowledge proof protocols but especially for those based on error-correcting codes, such as STARK and Plonky2. Also sometimes referred to as Fast Fourier Transforms, NTT is a technique that can enable more efficient polynomial calculations by changing how the polynomial is represented. Since all modern zero-knowledge proof systems are built on polynomial commitment schemes, NTT ends up being a major bottleneck in the proof-generation process.
A Field-Programmable Gate Array (FPGA) is an integrated circuit designed to be configured by a developer after manufacturing, making it "field-programmable". It contains an array of programmable logic blocks and a hierarchy of reconfigurable interconnects that allow the blocks to be wired together to perform complex computational tasks. FPGAs are often compared to ASICs (Application-Specific Integrated Circuits) and in fact are often used when designing ASICs for specific applications.
By leveraging the performance of an FPGA to perform faster NTT computations, we can more easily multiply large sets of numbers quicker, improving the efficiency of the underlying cryptography methods and polynomial arithmetic. For protocols based on FRI-commitment schemes (such as STARKs), the proving time (in terms of computation) is almost exclusively based on the latency of the NTT operations. As a result, this greatly reduces the computational bottlenecks for SNARK-based systems.
Supranational, the winning team for this category, has a history of working on hardware acceleration of cryptography and open source cryptography, with a particular focus on zero-knowledge proof acceleration. The team worked at Intel and was involved in projects like the Intel SHA extensions. Other team members have been long-time contributors to open source cryptography libraries like OpenSSL which power the modern web. Supranational developed sppark, a library used as the baseline in the zPrize MSM competition, and incorporated into zero-knowledge protocols like Aleo. Suprational says, “ZPrize was a great opportunity for us to continue to contribute to advancing the state of the art for open source cryptography. We are super excited about this industry initiative and it has done a great job at raising awareness of the importance of high performance open source cryptography.”
The HardCaml team, who came in 2nd place was composed of Andy Ray, Rahul Yesantharao, Fu Yong Quah, Benjamin Devlin, all co-workers from the Jane Street FPGA team. This team decided to attack both the MSM and NTT ZPrize FPGA categories since they both imposed big data problems with impressive published GPU and FPGA solutions; the team was eager to see how they would stack up against the challenges. Ben says “Even though we did the competition in our spare time, ZPrize has had a really positive impact at work by raising visibility and getting more people interested in Hardcaml (the hardware design language we use at Jane Street).”
The COSIC research group of the Electrical Engineering Department at KU Leuven in Belgium came in third place. The team had wide-ranging expertise on secure embedded systems and hardware, with special knowledge in implementing cryptographic algorithms on various platforms. The team also included Michiel Van Beirendonck, whose research revolves around lattice-based cryptography, side-channel attacks, and hardware acceleration of fully homomorphic encryption schemes, and Jonas Bertels, who specializes in implementing cryptographic primitives such as the Number Theoretic Transform and modular arithmetic. Additionally, Furkan Turan, a postdoctoral researcher, specializes in FPGA acceleration of cryptographic algorithms and homomorphic computing at a datacenter scale. The COSIC team says, “Thanks to the appealing parameters of the ZPRIZE project, we could explore highly optimized NTT arithmetic. As a result, faster FHE implementations utilizing improved NTT hardware will be possible.”
The Jump Crypto team led by Rahul Maganti and iCAS Lab headed by Ramtin Zand placed 4th and 5th respectively. iCAS Lab was composed of four graduate students from the intelligent circuits, architectures, and systems (iCAS) lab who participated in the ZPrize competition under the supervision of Dr. Ramtin Zand, the principal investigator. Mohammad Elbtity took charge of hardware development, while Joseph Lindsay oversaw algorithm-level contributions. Peyton Chandarana and Mohammadreza Mohammadi provided additional support roles. On ZPrize, the iCas Lab team says, “as an academic lab, participation in the ZPrize competition opened up opportunities for collaboration with industry which can potentially lead to forming partnerships in the future for accelerating zero-knowledge cryptography. Such collaborations are critical for the advancement of the field.”
The track of this particular prize focused on accelerating Number Theoretic Transforms (NTTs), an essential building block for Zero-Knowledge Proof (ZKP) protocols, on an FPGA platform. “The large size of the data and the underlying finite field arithmetic made this an especially difficult challenge”, says Dr. Ramtin Zand of iCAS Lab. “NTT computation operates on over one million coefficients, which creates a huge memory size and memory traffic problem. It must efficiently be stored and loaded from off-chip memory. Secondarily, the track focused on NTTs over a particular finite field: Polygon Zero’s Goldilocks field.” The COSIC team from KU Leuven found a unique approach to surmounting hurdles related to memory through an HBM-friendly four-step NTT process with specific reorder operations to support the NTT butterflies. Additionally, they were the only team to exploit the Goldilocks root-of-unity trick for the second problem, to create an efficient finite-field arithmetic implementation which requires no multipliers.
The winner of the category, the Supranational team found their key challenge to be the number of skill sets needed for the FPGA competition. Through reliance on their core competencies in hardware design, algorithm design, hardware implementation, and memory optimization, and careful management of data movement, they were able to propel themselves to success.
When dealing with the PoSW competition, Supranational determined the need to employ ZK algorithm optimization and implementation across both CPU and GPU platforms to be the main obstacles. Through careful management of data movement, they were able to surmount them.
Sitting at the intersection of hardware acceleration of ZKP and blockchain technologies, the ZPrize competition is opening exciting new doors for future research into hardware acceleration of FHE using highly optimized NTT arithmetic. In the coming months and years, even faster FHE implementations utilizing improved NTT hardware will be possible due to the open source nature of competition results. Furthermore, participation in the ZPrize competition continues to open up opportunities for academic and industry collaboration. Such collaborations are critical for the advancement in the acceleration 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.
