Exa: A Unified Architecture for Multi-Scalar Multiplication and Polynomial Computation in Zero-Knowledge Proof

Abstract

Zero-knowledge proof (ZKP) is a cryptographic protocol that allows a prover to convince verifiers that a computation is correctly executed without disclosing the prover’s secret. ZKP has been deployed in various privacy-preserving applications. However, the proof generation is notably inefficient on general-purpose processors. Multi-scalar multiplication (MSM) and polynomial computation (POLY), including number theoretic transform (NTT), are two of the most computation-intensive parts in proof generation. Recently, separate accelerators for MSM and POLY (mostly NTT) have been proposed. Unfortunately, separate accelerators may have poor resource utilization since MSM and POLY cannot be performed concurrently. To address this challenge, we propose Exa, a unified hardware architecture for MSM and POLY. It enables MSM and POLY to share computational resources and memory resources through decoupling dataflow control, computation, and memory. We design a novel unified functional unit (FU) array that can support both POLY operation and point addition (PADD) for MSM. In addition, we propose a 3-D NTT implementation and an adaptive MSM implementation on the FU array using a domain-specific instruction set architecture (ISA). Exa is scalable and can be efficiently orchestrated by our proposed runtime system. Compared with the separate accelerators for MSM and NTT, Exa occupies 47% less chip area. Compared to state-of-the-art accelerator PipeZK, Exa achieves up to$20.68 \times $and$4.58 \times $improvement for NTT and MSM, respectively, while occupying a chip area that is$2.6 \times $smaller. For end-to-end applications, Exa can achieve a speedup of$6.5 \times $on average than software implementation.