Zero-knowledge proofs validate statements without revealing any information, pivotal for applications such as verifiable outsourcing and digital currencies. However, their broad adoption is limited by the prolonged proof generation times, mainly due to two operations: Multi-Scalar Multiplication (MSM) and Number Theoretic Transform (NTT). While MSM has been efficiently accelerated using multi-GPU systems, NTT has not, due to the high inter-GPU communication overhead incurred by its permutation data access pattern.
Zero-knowledge proof (ZKP) is an important cryptographic tool that sees wide applications in real-world scenarios where privacy must be protected, including privacy-preserving blockchains and zero-knowledge machine learning. Existing ZKP acceleration approaches using GPUs, FPGAs, and ASICs focus only on classic protocols that rely on expensive elliptic curve arithmetics. Emerging ZKP protocols based on hash functions can greatly reduce the algorithmic complexity, but they also introduce much more diverse computation kernels that cannot be efficiently handled by a single accelerator chip if dedicated units for each kernel are used. Our approach is to leverage a unified hardware architecture that is able to efficiently support the common primitives in ZKP, and then use smart mapping strategies to flexibly map various kernels to such hardware while ensuring high resource utilization. We design UniZK as such a ZKP accelerator, with a systolic-array-based hardware architecture enhanced with extra local links and a new vector processing mode. We propose novel mapping strategies to support diverse kernels including number theoretic transforms, hash functions, and general polynomial computations. UniZK provides 97x and 46x speedups on average compared to the CPU and GPU implementations of the same protocols, and is also 840x faster than previous ZKP accelerators using different protocols.
Machine learning is an important technology that can be applied to various services, such as medical diagnosis and sales data analysis. However, the machine learning often involves personal information in the data used for training, and data encryption is essential to prove the learning process without losing data privacy. Garg et al. proposed a method using zero-knowledge proofs to verify whether data owned by the prover has been correctly utilized for the training on a machine learning model. They applied their method to federated learning, in which multiple users learn a model from their data. On the other hand, their method requires each prover to share data using Multi-Party Computation (MPC), which results in significant computational overhead for each user. Furthermore, their method does not provide a solution for the case where a malicious prover proves the data that he/she has not actually used for the training. We propose a method to prove the correctness of the procedure that one's own data was used for training without using MPC by sharing models instead of sharing the data. In our scheme, each prover's model can only be accessed by two users: the verifier and the next prover, thus reducing the computational effort required for model sharing. The data and the model used for training can be applied to zero-knowledge proofs, and the verifier can verify only the model to prove that it has been trained without disclosing the data. We prove how we can identify the malicious prover when he/she sends different models to the verification phase.
This survey provides a comprehensive examination of verifiable computing, tracing its evolution from foundational complexity theory to modern zero-knowledge succinct non-interactive arguments of knowledge (ZK-SNARKs). We explore key developments in interactive proof systems, knowledge complexity, and the application of low-degree polynomials in error detection and verification protocols. The survey delves into essential mathematical frameworks such as the Cook-Levin Theorem, the sum-check protocol, and the GKR protocol, highlighting their roles in enhancing verification efficiency and soundness. By systematically addressing the limitations of traditional NP-based proof systems and then introducing advanced interactive proof mechanisms to overcome them, this work offers an accessible step-by-step introduction for newcomers while providing detailed mathematical analyses for researchers. Ultimately, we synthesize these concepts to elucidate the GKR protocol, which serves as a foundation for contemporary verifiable computing models. This survey not only reviews the historical and theoretical advancements in verifiable computing over the past three decades but also lays the groundwork for understanding recent innovations in the field.
Zero-knowledge proofs allow verification of computations without revealing private information. However, existing systems require memory proportional to the computation size, which has historically limited use in large-scale applications and on mobile and edge devices. We solve this fundamental bottleneck by developing, to our knowledge, the first proof system with sublinear memory requirements for mainstream cryptographic constructions. Our approach processes computations in blocks using a space-efficient tree algorithm, reducing memory from linear scaling to square-root scaling--from $Θ(T)$ to $O(\sqrt{T} + \log T \log\log T)$ for computation size $T$--while maintaining the same proof generation time through a constant number of streaming passes. For widely-used linear polynomial commitment schemes (KZG/IPA), our method produces identical proofs and verification when using the same parameters and hashing only aggregate commitments into the challenge generation, preserving proof size and security. Hash-based systems also achieve square-root memory scaling though with slightly different proof structures. This advance enables zero-knowledge proofs on everyday devices and makes previously infeasible large computations verifiable, fundamentally democratizing access to privacy-preserving computation. Space-efficient zero knowledge proof systems create opportunities to reshape how trust is established in digital systems--from enabling widespread participation in decentralized networks to making verifiable scientific computing practical at unprecedented scales.
In order to enable more types of machine learning models to use zero-knowledge proofs to enhance their computational verifiability, this study proposes a zero-knowledge machine learning conversion method based on the Taylor series. Firstly, a polynomial expansion of structures with transcendental functions in ordinary machine learning models is performed using Taylor's formula. The corresponding arithmetic circuit descriptions are written in ZKP based on the converted model structures. Finally, the proof body is generated, which allows the verifier to verify the correctness of the results quickly. The basic experimental idea is also given, and the scheme's feasibility is verified, which can be done to provide a verification path for the model without seriously affecting its accuracy.
Shahzad Ahmad Butt, Benjamin Reynolds, V. Ramamurthy, Xiao Xiao · 8 authors
Zero-Knowledge Proofs (ZKPs) have emerged as an important cryptographic technique allowing one party (prover) to prove the correctness of a statement to some other party (verifier) and nothing else. ZKPs give rise to user's privacy in many applications such as blockchains, digital voting, and machine learning. Traditionally, ZKPs suffered from poor scalability but recently, a sub-class of ZKPs known as Zero-knowledge Succinct Non-interactive ARgument of Knowledges (zk-SNARKs) have addressed this challenge. They are getting significant attention and are being implemented by many public libraries. In this paper, we present a novel scalable architecture that is suitable for accelerating the zk-SNARK prover compute on FPGAs. We focus on the multi-scalar multiplication (MSM) that accounts for the majority of computation time spent in zk-SNARK systems. The MSM calculations extensive rely on modular arithmetic so highly optimized Intel IP Libraries for modular arithmetic are used. The proposed architecture exploits the parallelism inherent to MSM and is implemented using the Intel OneAPI framework for FPGAs. Our implementation runs 110x-150x faster compared to reference software library, uses a generic curve form in Jacobian coordinates and is the first to report FPGA hardware acceleration results for BLS12-381 and BN128 family of elliptic curves.
Nikola Samardzic, Simon Langowski, Srinivas Devadas, Daniel Sánchez
Zero-Knowledge Proofs (ZKPs) are a cryptographic tool that enables one party (a prover) to prove to another (a verifier) that a statement is true, without requiring the prover to disclose any data to the verifier. ZKPs have many use cases, such as letting clients delegate computation to servers with cryptographic correctness guarantees, while enabling the server to use secret data in these computations. ZKP applications span verifiable machine learning (ML) and databases, online auctions, electronic voting, and blockchains. While ZKPs are already widely used in blockchains, the prohibitive costs of proof generation limit them to proving very simple computations. We present a novel accelerator, NoCap, that leverages hardware-algorithm co-design to achieve transformative speedups. NoCap generates proofs 586× faster than a 32-core CPU, and 41× faster than PipeZK, a state-of-the-art ZKP accelerator. We leverage recent algorithmic developments to achieve these speedups: we identify and combine two recent hash-based ZKP algorithms, Orion and Spartan, which have similar performance on CPUs to the ZKPs targeted by prior accelerators, but are much more amenable to hardware acceleration. Though these algorithms result in larger proofs, we show that the end-to-end speedups (including prover time, proof transmission, and verification time) more than justify this size increase. We contribute a novel hardware organization to exploit these acceleration opportunities: NoCap is a programmable vector processor with functional units tailored to the needs of hash-based ZKPs. We also contribute a co-designed implementation of the Spartan+Orion ZKP tailored to accelerators, with optimizations that improve parallelism and reduce memory traffic. As a result, NoCap achieves speedups that enable new use cases for ZKP.
Hao Zhou, Changxu Liu, Lan Yang, Li Shang · 5 authors
Zero-knowledge proof (ZKP) plays a significant role in privacy protection technology. However, the proof generation phase requires considerable time and hardware resources. In this phase, Number Theoretic Transform or Inverse Number Theoretic Transform (NTT/INTT) in polynomial computation, as well as Multiple Scalar Multiplication (MSM), are bottlenecks that dominate the execution time. In this paper, we propose a highly reconfigurable accelerator ReZK to accelerate ZKP proof generation phase, focusing on NTT/INTT and MSM. According to the configurations, ReZK can be configured as NTT, INTT, and MSM with variable sizes and bit-widths by adjusting the data path between on-chip memories and arithmetic cores. As the basic unit of arithmetic cores, the reconfigurable processing element (PE) in ReZK is composed of pipelined modular multipliers and modular adders that support variable bit-widths. It can perform butterfly or arithmetic operations. Based on the reconfigurable PEs, the ReZK core can implement NTT/INTT with different sizes and bit-widths, or a fully pipelined point adder (PADD). Additionally, we propose a modularized MSM scheduling architecture to support various bit-widths. The on-chip memories are also well organized for reuse. In NTT/INTT mode, 4-way 256-bit or 2-way 384-bit NTT/INTT can be computed in parallel. In MSM mode, for different elliptic curves, ReZK is capable of processing 4-way 256-bit or 2-way 384-bit MSM in parallel.
Data privacy has become a severe concern due to the substantial growth in data gathering and processing, driven by the widespread adoption of cloud computing and cryptocurrency. Zero-Knowledge Proof (ZKP) has emerged as a promising cryptographic protocol for ensuring data privacy. However, ZKP suffers from high computational costs, making it excessively slow when implemented in software. To identify performance bottlenecks in the ZKP protocol, existing research has focused on CPU performance evaluation at the architecture level, considering factors such as execution time and memory consumption. Nevertheless, ZKP protocols have distinct memory and computing needs at each stage, these studies lack detailed CPU performance analyses necessary to improve ZKP performance and promote wider adoption.In this paper, we provide a comprehensive performance analysis of widely used ZKP libraries on CPUs. We perform four different analyses to characterize the CPU microarchitecture, memory, code, and scalability performance of the ZKP protocol on different CPUs. Our analysis reveals that the ZKP protocol performs differently on different CPUs, emphasizing the need for microarchitecture-specific analysis and optimizations. We evaluate loads and stores, last level cache (LLC) misses per kilo instructions (MPKI), and maximum memory bandwidth utilization of ZKP. We observe the proving stage consumes the highest memory bandwidth (25Gbps). We identify the functions that consume the most CPU time in each stage of the ZKP protocol and categorize each stage as compute, control-flow, or data-flow intensive. Also, we identify the proving stage as the most scalable with the potential to be sped up by parallel computation. These findings provide valuable insights for designing future ZKP accelerators, leading to more efficient and scalable ZKP implementations.
Zero Knowledge Proofs (ZKPs) are cryptographic security techniques that allow secure data exchange without revealing secret information. This research study investigates and analyzes efficiency factors, robustness features, applicability, and uses, along with challenges for the implementation of these techniques, which are most important to achieving higher security. We categorize ZKPs techniques into three types: interactive, non-interactive, and succinct non-interactive arguments of knowledge (SNARKs). Different authors have examined prominent models such as zkSNARK, Ligero, Bulletproofs, Hyrax, Aurora, and Libra. Libra stands out for its outstanding efficiency, requiring a one-time trusted setup depending on the input size. The study explores various challenges in ZKPs to enhance their robustness. To solve problems like the trusted setup dilemma and quantum computing attacks, the research suggests making progress by integrating different models, improving efficiency, looking into new mathematical problems, creating more advanced cryptographic tools, and studying lattice-based cryptography for better security. The results highlight the need to overcome constraints and improve ZKPs security and effectiveness in practical setups to enhance their efficiency, and they will direct future research for privacy, security, and integrity in a variety of applications.
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$3.9\boldsymbol{\times}$. Experimental results also show that Falic achieves a throughput speedup of up to$1.62\boldsymbol{\times}$and saves as much as$8.5\boldsymbol{\times}$energy compared to an RTX 2080Ti GPU.
Ryan Lavin, Xuekai Liu, Hardhik Mohanty, L. E. J. Norman · 6 authors
Zero-knowledge proofs (ZKPs) enable computational integrity and privacy by allowing one party to prove the truth of a statement without revealing underlying data. Compared with alternatives such as homomorphic encryption and secure multiparty computation, ZKPs offer distinct advantages in universality and minimal trust assumptions, with applications spanning blockchain systems and confidential verification of computational tasks. This survey provides a technical overview of ZKPs with a focus on an increasingly relevant subset called zkSNARKs. Unlike prior surveys emphasizing algorithmic and theoretical aspects, we take a broader view of practical deployments and recent use cases across multiple domains including blockchain privacy, scaling, storage, and interoperability, as well as non-blockchain applications such as voting, authentication, timelocks, and machine learning. To support consistent comparison, we provide (i) a taxonomy of application areas, (ii) evaluation criteria including proof size, prover and verifier time, memory, and setup assumptions, and (iii) comparative tables summarizing key tradeoffs and representative systems. The survey also covers supporting infrastructure, including zero-knowledge virtual machines, domain-specific languages, libraries, and frameworks. While emphasizing zkSNARKs for their prevalence in deployed systems, we compare them with zkSTARKs and Bulletproofs to clarify transparency and performance tradeoffs. We conclude with future research and application directions.
Multi-scalar multiplication (MSM) is the most computation-intensive part in proof generation of Zero-knowledge proof (ZKP). In this paper, we propose MSMAC, an FPGA accelerator for large-scale MSM. MSMAC adopts a specially designed Instruction Set Architecture (ISA) for MSM and optimizes pipelined Point Addition Unit (PAU) with hybrid Karatsuba multiplier. Moreover, a runtime system is proposed to split MSM tasks with the optimal sub-task size and orchestrate execution of Processing Elements (PEs). Experimental results show that MSMAC achieves up to 328X and 1.96X speedups compared to the state-of-the-art implementation on CPU (one core) and GPU, respectively, outperforming the state-of-the-art ASIC accelerator by 1.79X. On 4 FPGAs, MSMAC performs 1,261X faster than a single CPU core.
Vladlen D. Afonin, Sergey Zapechnikov, Igor A. Prostov
Zero-knowledge proofs are being increasingly applied to a wide range of tasks in modern distributed information systems. Of particular interest are such areas of activity as digital asset management systems, anonymous electronic voting systems, and anonymous credentials. Nevertheless, within the framework of the desire of Russian developers to localize the developed products, there is a question of compliance of the used algorithms with the legislative framework of the Russian Federation, which obliges developers to use local cryptographic standards. As our analysis shows, insufficient attention has been paid in the literature to the applicability of these standards to the scenario of use in zero-knowledge proof systems. In particular, the complexity of proof generation, parameters of arithmetic schemes are not analyzed, there is no comparison of computational complexity and cryptographic properties with foreign alternatives. In this paper we consider in detail the peculiarities of implementation of the arithmetic scheme for the function of GOST 34.11-2018 in the most widespread language for arithmetic circuit programming Circom. The developed program code is open and available for use and modification. The characteristics of the scheme, compilation and generation times are analyzed. The obtained results were compared with other popular hash functions: the cryptographic hash function SHA256 included in the standard language library, and the hash function Poseidon, specialized and optimized for use in zero-knowledge proof systems. The results show that while the use of the Russian hash function is possible, it is not desirable in applications that do not require the use of local cryptographic standards, due to the greater time complexity of witness generation and consequently proof generation. Recommendations on usage scenarios are given and further research directions are suggested.
Zero-knowledge proof (ZKP) systems have surged attention and held a fundamental role in contemporary cryptography. Zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) protocols dominate the ZKP usage, implemented through arithmetic circuit programming paradigm. However, underconstrained or overconstrained circuits may lead to bugs. The former refers to circuits that lack the necessary constraints, resulting in unexpected solutions and causing the verifier to accept a bogus witness, and the latter refers to circuits that are constrained excessively, resulting in lacking necessary solutions and causing the verifier to accept no witness. This article introduces a novel approach for pinpointing two distinct types of bugs in ZKP circuits. The method involves encoding the arithmetic circuit constraints to polynomial equation systems and solving them over finite fields by the computer algebra system . The classification of verification results is refined, greatly enhancing the expressive power of the system. A tool, AC 4 , is proposed to represent the implementation of the method. Experiments show that AC 4 demonstrates an increase in the solved rate, showing a 36.7% improvement over Picus and CIVER, and a slight improvement over halo2-analyzer, a checker for halo2 circuits. Within a solvable range, the checking time has also exhibited noticeable improvement, demonstrating a magnitude increase compared to previous efforts.
Zero-Knowledge Proofs (ZKPs) ensure privacy in sensitive applications, including blockchains, anonymous verifiable voting, and secure auctions. In recent years, a number of ZKP implementations have been presented. The diversity of available solutions raises the need to compare the implementations to discover their strengths and weaknesses. Unfortunately, the collection of ZKP implementations is highly heterogeneous, aggravating a just comparison between different implementations. Hence, there is a strong need for a benchmarking solution to measure and collect metrics to compare different ZKP implementations. Therefore, we design and implement a benchmarking solution for ZKPs. The proposed solution allows users to gather performance metrics of different ZKP implementations and aids the decision-making process of selecting the right implementation for a specific use case. The system is highly configurable and allows the integration of novel ZKP systems. Further, we demonstrate the solution’ s applicability by benchmarking two popular ZKP implementations.
We study the problem of constructing succinct zero knowledge proof systems for floating point computations. The standard approach to handle floating point computations requires conversion to binary circuits, following the IEEE-754 floating point standard. This approach incurs a poly(w) overhead in prover efficiency for computations with w-bit precision, resulting in very high prover runtimes -- already the key bottleneck in the design of succinct arguments. We make the following contributions: -We propose a new model for verifying floating point computations that guarantees approximate correctness w.r.t. a relative error bound. This model is inspired by numerical analysis, and is very meaningful for applications such as machine learning and scientific computing. -Using this model, we present a general method for constructing succinct zero-knowledge proofs for floating point computations starting from existing public-coin "commit-and-prove'' systems. For computations with w-bit precision, our approach incurs only a log(w) overhead in prover running time. Our compiler nearly preserves (up to a factor of 2) the communication complexity of the underlying protocol, and requires sub-linear verification time. The resulting proof can be made non-interactive in the random oracle model. Concretely, our scheme is ~57x faster than the method following IEEE standard exactly [35] for 32-bit floating point computations. Central to our main result, and of independent interest, is a new batch range proof system in standard prime order groups that does not rely on bit decomposition.
We propose a new doubly efficient interactive proof protocol for general arithmetic circuits. The protocol generalizes the interactive proof for layered circuits proposed by Goldwasser, Kalai and Rothblum to arbitrary circuits, while preserving the optimal prover complexity that is strictly linear to the size of the circuits. The proof size remains succinct for low depth circuits and the verifier time is sublinear for structured circuits. We then construct a new zero knowledge argument scheme for general arithmetic circuits using our new interactive proof protocol together with polynomial commitments. Our key technique is a new sumcheck equation that reduces a claim about the output of one layer to claims about its input only, instead of claims about all the layers above which inevitably incurs an overhead proportional to the depth of the circuit. We developed efficient algorithms for the prover to run this sumcheck protocol and to combine multiple claims back into one in linear time in the size of the circuit. Not only does our new protocol achieve optimal prover complexity asymptotically, but it is also efficient in practice. Our experiments show that it only takes 0.3 seconds to generate the proof for a circuit with more than 600,000 gates, which is 13 times faster than the original interactive proof protocol on the corresponding layered circuit. The proof size is 208 kilobytes and the verifier time is 66 milliseconds. Our implementation can take general arithmetic circuits directly, without transforming them to layered circuits with a high overhead on the size of the circuit.