Falic: An FPGA-Based Multi-Scalar Multiplication Accelerator for Zero-Knowledge Proof

In this paper, we propose Falic, a novel FPGA-based accelerator to accelerate multi-scalar multiplication (MSM), the most time-consuming phase of zk-SNARK proof generation. Falic innovates three techniques. First, it leverages globally asynchronous locally synchronous (GALS) strategy to build multiple small and lightweight MSM cores to parallelize the independent inner product computation on different portions of the scalar vector and point vector. Second, each MSM core contains just one large-integer modular multiplier (LIMM) that is multiplexed to perform the point additions (PADDs) generated during MSM. We strike a balance between the throughput and hardware cost by batching the appropriate number of PADDs and selecting the computation graph of PADD with proper parallelism degree. Finally, the performance is further improved by a simple cache structure that enables the computation reuse. We implement Falic on two different FPGAs with different hardware resources, i.e., the Xilinx U200 and Xilinx U250. Compared to the prior FPGA-based accelerator, Falic improves the MSM throughput by <inline-formula><tex-math notation="LaTeX">$3.9\boldsymbol{\times}$</tex-math><alternatives><mml:math><mml:mn>3.9</mml:mn><mml:mo mathvariant="bold">&#x000D7;</mml:mo></mml:math><inline-graphic xlink:href="yang-ieq1-3449121.gif"/></alternatives></inline-formula>. Experimental results also show that Falic achieves a throughput speedup of up to <inline-formula><tex-math notation="LaTeX">$1.62\boldsymbol{\times}$</tex-math><alternatives><mml:math><mml:mn>1.62</mml:mn><mml:mo mathvariant="bold">&#x000D7;</mml:mo></mml:math><inline-graphic xlink:href="yang-ieq2-3449121.gif"/></alternatives></inline-formula> and saves as much as <inline-formula><tex-math notation="LaTeX">$8.5\boldsymbol{\times}$</tex-math><alternatives><mml:math><mml:mn>8.5</mml:mn><mml:mo mathvariant="bold">&#x000D7;</mml:mo></mml:math><inline-graphic xlink:href="yang-ieq3-3449121.gif"/></alternatives></inline-formula> energy compared to an RTX 2080Ti GPU.