Performance Bottlenecks in Computing ZK Proofs on a GPU

arXiv:2611.09569v1 [cs.CR] 6 Nov 2026

Performance Bottlenecks in Computing ZK Proofs on a GPU Victor Carolino∗

Caleb Geren∗

Michael Kaufman∗

victor.carolino@proton.me Lehigh University Redwood Shores, CA, USA

c.geren@utah.edu University of Utah Salt Lake City, UT, USA

kaufmanmp03@gmail.com Lehigh University Burlington, MA, USA

Maximilian Nussbaum

William Scott

Henry F. Korth

nussbaummax88@gmail.com Lehigh University Bethlehem, PA, USA

wis226@lehigh.edu Lehigh University Bethlehem, PA, USA

hfk2@lehigh.edu Lehigh University Bethlehem, PA, USA

Abstract Zero-knowledge proofs allow one party to prove the correctness of a statement or execution of a computation while revealing no more than the statement of correctness itself. Recent use cases, such as AI datasets[20], suggest the need for faster proof generation over increasingly large constraint sets. This paper explores efforts in optimizing zero-knowledge proof generation, specifically PlonK, using GPUs, for applications that are not amenable to solution via incrementally verifiable computing (IVC). Our intention with this work is to improve ZK performance by introducing fundamental changes in the low-level architectural structure of proof generation. These changes affect performance curves for most current proof generation algorithms. In particular, this paper explores the trade-offs between increased parallelization on GPUs and the resultant memory management problems that occur due to this parallelization. We implement a parallelized PlonK in order to analyze these trade-offs and make arguments concerning the nature of data flows within the proving protocol. Our results lead us to consider multi-GPU environments to maximize performance for large circuit sizes. Such environments introduce issues of communication, efficient hardware management, data partition, and data transfers. This paper further discusses the use cases that motivate multi-GPU implementations, their cost models, and the use of remote direct memory access (RDMA) for data transfer among GPUs.

CCS Concepts • Security and privacy → Database activity monitoring; Information flow control; Cryptography;

Keywords zero-knowledge, blockchain, performance, PlonK, GPU

1

Introduction

Zero-knowledge succinct arguments of knowledge, or zk-SNARKs, are cryptographic primitives through which a prover 𝜌 may efficiently convince a verifier 𝑣 of the correctness of some computation 𝜆. This is achieved by providing a succinct argument of 𝜆’s validity 𝜋, revealing no further information about 𝜆 [4]. Such constructions are extremely beneficial in various application domains. These range from privacy applications, as discussed, e.g., in [6], to cases ∗ Work done while these authors were at Lehigh University

where zk-SNARKs are used for their succinctness and thus easy correctness checking, as in zk-rollups. Because of the computational complexity of proof generation, significant attention has been paid to proof-generation efficiency by subdividing tasks. These include incrementally verifiable computing [10, 21], and the aggregation of proofs to distribute easily segmented subtasks [21, 34]. In this paper, we focus on zk-SNARKs, specifically PlonK[16], applied to use cases that are sub-dividable into small proofs. We elaborate on these and other application domains in Section 2, in Table 1. The widespread adoption of zk-SNARKs and other argumentof-knowledge technologies is limited by these performance barriers. Particularly, these challenges lie in the balancing of three key metrics: verification time, proof-generation time, and proof size. Various approaches to constructing arithmetization schemes and implementing underlying cryptographic primitives (i.e. hashing and elliptic curves) provide different balances of these three aforementioned metrics [33]. Scaling zero-knowledge is a prominent issue within the cryptographic space. Various solutions center either around decreasing algorithmic complexity in ZK systems [11, 21] or efficiently implementing existing systems [22, 23, 38]. The latter approach has seen significant advances in the past several years, due to competitions that focus on engineering scalable ZK proving systems, such as ZPrize1 . Many solutions focus on common computations shared among proving systems including multi-scalar multiplication (MSM), the number theoretic transform (NTT), and other hard computations. These serve as large bottlenecks in the proof generation process and increasing efficiency in them would have an extreme impact on the power of ZK systems [37]. While this paper holistically considers the entirety of the proving process, it focuses on computation time for proof generation as a key metric in our GPU optimizations. Within the proof-generation process, we focus on multi-scalar multiplication (MSM), which is at the core of many zero-knowledge proving systems and is highly suitable for parallelization. The application domains we cite necessitate the creation of ZK proofs over hundreds millions of constraints (> 228 ). Constraint sets of this magnitude lead to extremely high computational complexity and demand for large amounts of memory. In this paper, we describe out implementation of the PlonK protocol into an NVIDIA A10 and V100 environment using the CUDA

1 https://www.zprize.io/

,,

Carolino, et al.

platform and Thrust library. Through this process, we observe bottlenecks in memory management stemming from difficulties in optimizing within a heterogeneous CPU-GPU computing architecture [36]. The memory challenge is shown to be sufficiently serious that a well-configured CPU system can outperform our GPU-based implementation despite PlonK being highly parallelizable. Our work demonstrates the importance of carefully considering not only parallelism but also memory management when choosing an execution strategy for ZK-proof implementations. We also provide a foundation for further research efforts into parallelizing larger ZK-proof constructions, not only within a GPU, but also across multiple GPUs (and CPUs). Such a system would require a cost model and partitioning algorithm to determine the most efficient partitioning and strategic delivery of data at runtime. Such a ZK-proof implementation would leverage data transfer between processors using remote direct memory access (RDMA), a method of data transfer that does not interrupt the remote processor across a network of machines. We further expand upon this in Section 7. The general outline of the rest of the paper is as follows. Section 2 provides the necessary background to zk-SNARKs, specifically the PlonK constructions and relevant research that motivates our contributions. Section 3 describes our implementation process and highlights critical development decisions. Section 4 details results from our proving system, and Section 5 analyzes these results and connects them to particularly notable areas of improvement within the MSM. Section 6 explores challenges in optimization of heterogeneous computing, our motivation for pursuing non-IVC based proofs, and brings to light several potential promising improvements in proof generation. Section 7 describes future work motivated by Section 5, concluding our paper.

2

Background

Since the introduction of the Groth16 protocol [17], zk-SNARK protocols have rapidly increased in number. In all of these protocols, certain commonalities arise including the MSM operation on which we focus in this paper. More generally, three broad stages represent the life-cycle of any SNARK construction: • Setup: the process in which parties engage in a multi-party computation (MPC) to create a cryptographic reference that secures all future computations. There exist zk-SNARKs with trusted [16, 17] and also untrusted setups [8]. PlonK uses a trusted setup. A key advanage of PlonK is its required use of only a single, universal setup, compared to Groth16 which requires a separate setup for each execution being proved. • Proof Generation: the process of generating an argument of knowledge for subsequent verification. • Verification: the process of verifying the argument of knowledge. While this paper focuses on the proof-generation process, we briefly discuss the trusted setup and verification processes as tradeoffs made during proof generation. During the trusted setup, parties collaborate in an MPC setting to generate a reference string, often referred to as a common reference string (CRS) or structured reference string (SRS). This reference string is used to hide universal commitments, which create the structure for the cryptographic guarantees provided later in

the proof generation process. Creating a reference string is either circuit-specific (i.e. program specific) or universal. Circuit-specific constructions, like Groth-16, require a new trusted setup for each specific computation to be proved. While this is impractical for typical large-scale ZK applications, Groth16 provides the benefit of a comparatively smaller proof size and shorter prover computation time. Most widely-adopted ZK systems have universal trusted setups, which allow for the creation of a single SRS that can be used for all proofs thereafter. The verification stage must be efficient because, in most applications, a proof is verified by multiple parties. For PlonK and Groth16, the proofs are succinct and can be verified in constant time. Setup-free proof systems, based on zk-STARKs[5], have the obvious benefit of no setup phase, but suffer from asymptotically worse verification time (linear or logarithmic). Looking ahead, STARKs, being hash-based, offer quantum safety.

2.1

PlonK

PlonK [16] introduced the construction of a prover with a universal SRS via the arithmetization scheme Plonkish. PlonK and its variants have since become a standard in zk-SNARK-based constructions; and it reasonably approximates the state of zero-knowledge SNARK technology. Central to PlonK and important to the efficiency of the PlonK system is its arithmetization scheme: Plonkish. For our purposes, Plonkish can be described as a protocol acting upon polynomial constraints over a finite field. These polynomial constraints restrict our circuit to specific input/output requirements. Each gate represents one instruction in a computation, and its associated polynomial must evaluate to zero for the gate condition to be satisfied. We can represent these polynomials with a sparse matrix that eventually transforms into a polynomial of degree 3𝑛 + 5 for a circuit with 𝑛 gates. To get a sense of how large even relatively simple circuits can be, we note that a circuit that demonstrates that a prover knows three terms in a Pythagorean triple contains about 12 constraints, resulting in an MSM with at least 41 summations of elliptic curve points[15]. More circuit sizes are detailed in Table 1. These summations are difficult to compute because, while each coefficient in this polynomial is a scalar, each term associated with a coefficient is a point within a finite field. This field is instantiated over an elliptic curve, with points often above 200 bits in size. The MSM can be described as follows: 𝑛−1 ∑︁ 𝑀𝑆𝑀 = 𝐺𝑖 ∗ 𝑥𝑖 (1) 𝑖=0

where each elliptic curve point, an element of our field, is represented by 𝐺𝑖 and our scalars are represented by 𝑥𝑖 . The scalars 𝑥𝑖 are too large to be processed as hardware-level integers, so they must be split into smaller limbs, denoted as 𝑥𝑖,𝑗 . The number of bits, 𝑐, in a limb is called the window size. The result is that for a 𝑏-bit scalar, we have 𝐾 = 𝑏/𝑐 windows, and within each window there are 2𝑐 possible scalar values. Thus, we write the MSM as a sum over each of the 𝐾 windows: 𝑛−1 −1 ∑︁ 𝐾∑︁ 𝑀𝑆𝑀 = 𝐺𝑖 ∗ 𝑥𝑖,𝑗 ∗ 2𝑐 𝑗 (2) 𝑖=0 𝑗=0

Performance Bottlenecks in Computing ZK Proofs on a GPU

,,

where the 2𝑐 𝑗 term comes from the need to adjust each partial result based on the position of each limb in the full scalar.

𝛴xG→

Table 1: Examples of ZK Applications and Relative Constraint-Set Sizes Example

Description

Size

ZKRollups2

ZK-Rollups are a substantive application of ZK technology, and are virtually limitless in size.

> 227

Private Transactions3

ZK powered private transaction systems provide a solution to transacting privately on a public ledger.

> 226

Trustworthy

AI accountability in the realms of data provenance and distribution can be approached readily from a ZK perspective.

> 223

ZK solutions offer fair-trade guarantees about consumer goods via traceability and authenticity.

> 223

Anonymous voting systems are realizable through ZK systems which protect user identities.

> 220

Voting 6 Health AI Model Verification[19]

Proof that a specific health diagnosis used a specific approved AI diagnostic model

> 230

AI 4

Supply Chain 5 Anonymous

2.2

MSM Acceleration Techniques

The existence of applications with large circuit sizes and the difficulty of performing operations in elliptic-curve groups over large finite fields has led to a variety of algorithms and techniques to speed up computation. In this section, we detail algorithms and techniques that are widely adopted among virtually all proving systems due to their efficiency in facilitating the MSM. First, and most notably, is Pippenger’s bucket algorithm [7]. The primary focus of this algorithm is to eliminate the large scalar multiplications associated with each point and replace them with many smaller point additions and multiplications. The algorithm directly addresses this change through the introduction of windowing. During the bucket accumulation step, the scalars of the computation are split bitwise into windows of arbitrary size chosen by the developer. Each window-sized scalar is then associated with a specific bucket based on its value, as shown in Figure 1. Points are then assigned to buckets based on the scalar by which the point is to be multiplied. After the values are assigned, the sum of the points in each bucket is computed, and each of those sums is multiplied by total by the 3 https://research.protocol.ai/sites/snarks/ 4 https://research.protocol.ai/sites/snarks/ 5 https://www.certik.com/resources/blog/advanced-formal-verification-of-ZK-proofverifying-a-zk-instruction 6 https://www.gate.com/learn/articles/succinct-perfecting-the-infrastructure-for-zkproof-supply-chains/2325

i,j

i

0

1

2

3

Gk . . .

Gl . . .

Gq . . .

Gp . . .

00

01

10

11

𝛴

𝛴

𝛴

𝛴

0

1

2

Bucket Index

Bucket Contents

Bucket Window 3

Figure 1: Bucket Accumulation in Pippenger’s Bucket Method

scalar associated with that bucket. After that, for each window, the bucket sums are themselves summed. The window-sums are then scaled via a bit shift to correspond to the size of the original scalars. Finally, the totals of the scaled window-sums are accumulated to obtain the final result. Although the main goal of this algorithm is to break up large scalars into smaller values to avoid costly large point multiplication, the implementation comes with an extremely parallelizable approach. This parallelism is shown through the steps of breaking up the scalars into buckets within windows and through the accumulation of those buckets and windows. Each of these processes can be done at once without having the complication of collisions between threads on a CPU or GPU. The difficulty comes with how to adjust these operations accordingly for the most efficient method to balance compute times with data transfer. More recently, compelling work has suggested assigning GPU cores to buckets, with threads still being assigned to windows [18]. Stemming from Pippenger’s bucket method, and another common avenue for accelerating MSM dominated SNARK proofs, is memory interleaving [22]. Memory interleaving takes advantage of the multistreaming technique to simultaneously transfer data loads from host to device while performing computation on device, as depicted in Figure 2. This is a very common approach to achieving runtime speedups within the MSM, and is critical to understanding this paper’s implementation.

3

Methodology

The parallelization work was performed within the NVIDIA ecosystem on A10 and V100 GPUs using the CUDA platform and Thrust library. Our work further builds upon Aztec’s Barretenberg library, which implements the PlonK protocol. Detailed in previous works [13, 14], the issue of this parallelization work concerning the PlonK proving system is highly non-trivial. The proving system’s various computational bottlenecks and the existence of several sequential computations within those methods [2, 39] give rise to problems in achieving full parallelization. In particular, critical problems exist in the realm of host-device data transfer. In this section, we detail our approach to developing an initial parallel implementation of the PlonK proving system aimed at providing a platform for measuring memory requirements and motivating our decision to use Thrust. We describe the steps needed for a full implementation in Section 6.

,,

Carolino, et al.

Host

Device Non-MSM computation Data Transfer MSM Idle

Figure 2: Diagrammatic representation of memory interleaving data transfers in between respective host and device transfers/computations.

assembly’s support for extended-precision integer arithmetic with carry propagation. These changes allow us to use the Thrust library in our bucket accumulation stage of the MSM by delegating the prefix sum code to the Thrust abstractions, improving both performance and simplicity. Thrust’s implementation, backed in turn by CUDA Unbound (CUB) as part of the CUDA C++ core libraries, uses a highly optimized algorithm incorporating decoupled lookback to calculate efficiently the prefix sum over a very large number of inputs[31]. The result is a highly optimized and adaptable implementation that scales efficiently to higher input sizes, never needing to spawn a kernel manually. The dimensions of the execution grid are no longer tied to the bucket size, as the new algorithm simply processes all points and then scatters the output to the correct locations as necessary.

3.2 3.1

CUDA Kernels and Modularization

Our experiments focused directly on MSM computation with the limbs input directly as a large array. This array contained a series of big-ints represented as four 64-bit limbs, that is, each element of the array was allotted four indices to fit the size of the 254-bit scalars and field elements used in the MSM. The array also contained preallocated and unoccupied indices, reserved to allow for an easierto-use indexing scheme. The indexing scheme is used in the bucket value reduction computations. The experiment’s data were loaded in this manner to avoid the need for multiple host-to-device data transfers before and throughout the on-device computations. For the parallel execution of our implementation, we used CUDA, a general purpose API library and extension of C++ made by NVIDIA for working with GPUs. CUDA abstracts the underlying GPU via the PTX virtual-machine architecture. Within the CUDA extension of C++, kernels can be made that are functions compiled to run specifically on the GPU to utilize the thousands of threads a GPU can support. Several of these kernels are used in our implementation of the MSM. For these kernels, we chose a sequential implementation of individually highly parallel CUDA launches relying upon the CUDA-Thrust framework. This is done to perform the multitude of sum-reductions, a parallel computing computation critical to the overall performance of Pippenger’s algorithm [7] for computing the MSM. For our work, we chose the BN-254 curve[3], though other curves are also used in practice. Our BN-254 curve is employed using coefficients modulo a prime close to the size of 2254 , requiring us to perform arithmetic operations on integers of at least 254 bits in length (“field elements”). We used 4 extended-precision 64-bit “add” instructions in the PTX assembly, plus a small cost to check if we overflowed the modulus (+4 instructions to correct any overflow). Given a statically known prime, an efficient solution is to use a technique known as Montgomery multiplication[9]. In our case, this allows computing multiplication modulo of the aforementioned prime using only 64-bit multiplications and bit shifts. Having no direct step of modulo a 254-bit prime eliminates the need to track higher-order bits or implement a bignum modulus. Our implementation uses 32 multiply-adds, 16 additions, and one check for overflow correction. This is almost entirely implemented directly using PTX

Hardware and Testing

In order to analyze systems with circuit counts ranging from 215 to 225 , careful selection of GPU hardware was important. We focused on finding units that we expected would lend themselves well to proof generation. We remind the reader that these constraint-set sizes are entirely reasonable in terms of applications and are less than the scale of the largest applications that could benefit from ZK technology, as discussed in Section 2. Workloads consisted of a series of benchmarks using this GPU implementation as well as previous related works[12] using the Volta Tesla V100 GPU and the Ampere A10 GPU. The main differences between these chips are how they handle memory transfers. The Tesla V100 is a chip has been developed for high-performance computing applications while the A10 is a chip has been developed for efficiency in AI applications. Note that the A10 GPU has roughly 1.8x more CUDA cores available than the V100. Another difference is how these GPU implementations handle memory and bandwidth. Specifically, the Volta architecture we used has 16 gigabytes of memory7 with 900 gigabytes per second of bandwidth [27]. The Ampere A10 architecture supplies 24 gigabytes of memory with 600 gigabytes per second of bandwidth [30]. These specifications show a 1.5x improvement in memory and a 0.66x decrease in bandwidth for the Ampere A10 architecture in comparison to the Volta architecture. Both chips were chosen to be benchmarked as they both provide different computing capabilities that may prove optimal for the subproblems of the ZK proof computation. Specifically, an increased number of CUDA cores in the A10 allows for more streaming multiprocessors(SM). The V100 allows for better allocation per streaming multiprocessor, memory bandwidth, and more capable SM scheduling due to Volta’s redesigned memory hierarchy. We chose these two architectures because they both have unique advantages that lend themselves well to proof generation. Furthermore, they handle memory transfers differently [27, 28], and studying how they react to high memory loads is of acute interest to future work in this space, discussed in Section 7.

4

Results

We present our examination of the parallelized proving system in the following section. Special care was placed on the study of 7 The V100 offers a 32GB VRAM configuration, but that was not available for this work.

Performance Bottlenecks in Computing ZK Proofs on a GPU

Execution Time (Sec)

Volta Tesla 100 GPU

Ampere 10 GPU

Intel Xeon(R) Platinum 8358

40

30

20

10

0 2^15

2^16

2^17

2^18

2^19

2^20

2^21

2^22

2^23

2^24

2^25

Constraint Size

Figure 3: Execution Size Vs. Constraint-Set Size and Processor

Volta Tesla 100 GPU

Ampere 10 GPU

25

Memory Utilization

GPU memory utilization and the role of data transfers between host (CPU) and device (GPU) as a bottleneck, especially in how the computation’s GPU parallelism utilization is bound by memory rather than by compute capability. Ultimately, our results show that the performance bottleneck lies in memory congestion and data transfer. Figure 3 shows that execution time as a function of the size of the constraint set grows at a dramatic rate once GPU memory limits are hit. Figure 4 shows that, for each GPU system, the performance barrier is hit when memory utilization approaches 100%. In contrast, running on a CPU-only platform shows significantly better performance. That is, our ability to exploit the full degree of GPU parallelism was limited by memory issues. These metrics formulate the basis of our approach to the problem of expanding this work to multiple GPUs, further detailed in Section 7. Note that validation of the MSM result is of utmost importance in verifying that the PlonK system ran correctly and is a non-trivial problem. In our implementation, correctness was achieved by using result references of operations done previously on the elliptic curve and associated points that we used. These references were received directly from Aztec, the developer of the native PlonK proving system within their Barretenberg library. We analyze the performance of the PlonK system on an instantiated bare-metal NVIDIA V100 and A10 Tensor Core units. We consider the performance based upon (1) scaling with respect to constraint-set sizes and (2) overall memory utilization. Focusing on constraint-set size is natural in this analysis, as the computation size directly influences the number of constraints in the system [35]. Generally, within the implementation, we see Ampere units receiving a slightly larger memory utilization throughout proof generation compared to Volta units. We observe that Ampere 10 finishes execution in slightly less than 20 seconds up to 224 constraints, where the Volta Tesla 100 finishes its computation in slightly less than 30 seconds up to the same constraint-set size. The Ampere and Volta architectures saw nearly identical and near-constant memory utilization up until 221 constraints, where exponential growth begins. This growth is insurmountable on these platforms, and past 224 constraints, the Volta architecture failed to finish the computation. While the Ampere GPU was able to outperform the Volta architecture, it too failed at 225 constraints. We observe similar failures to the Ampere results for 225 constraints on the Volta hardware, detecting VRAM utilization of 20 GB. We note similar, yet not equal, memory requirements in the two architectures despite disparities in the compute time for large constraint-set sizes. These results are consistent with the improved hardware capabilities that the Ampere architecture has compared to Volta, namely in memory. Specifically, Ampere architecture A10 has a 1.5x improvement in memory compared to the Volta architecture, indicated in the hardware specifications, resulting in a huge difference in the hardware demand with increasing numbers of constraints. This heightened load on the hardware past the point of 221 constraints is observed in compute time measurements. Notably, this corresponds to a markedly low performance compared to the CPU implementation, where memory was not a limiting factor. In Section 5, we consider why the GPU implementations failed to outperform the CPU implementation regardless of the number of constraints.

,,

20 15 10 5 0 2^15

2^16

2^17

2^18

2^19

2^20

2^21

2^22

2^23

2^24

2^25

Constraint Sizes

Figure 4: Memory Utilization Vs. Constraint-Set Size

5

Analysis

The results in previous section show a clear problem with our initial focus on parallelism, since GPU memory usage and data transfer between host and device memory are the bottlenecks in the computation, overwhelming the benefits of parallelism. GPU memory usage becomes a significant limiting factor with a large number of constraints due to the mapped bucket indexing used in the implementation, and the need to allocate room for each possibly filled bucket before the first kernel launch. This implementation choice optimizes inter-kernel performance using existing Thrust reduction methods to achieve the greatest possible parallelism on a per-kernel basis. A more GPU-architecture amicable implementation could exploit host-device memory transfer interleaved with computation and shared memory transfer (as opposed to global memory transfer). Memory interleaving is only beneficial as long as we have VRAM space. Consequently, we propose that despite improvements from shared memory implementations, larger constraint-set sizes will necessitate the exploration of optimizations beyond interleaving. Data transfer from host to device and vice versa proved to be a large execution time bottleneck. We opted for a chosen bucket indexing scheme which requires an initial transfer to GPU for sum reduction. While this results in decreased efficiency, more complicated indexing schemes typically result in larger memory overhead. [22].

,,

Carolino, et al.

The option of implementing a less complicated indexing scheme is a reasonable alternative that was beyond the scope of this work. It is worth noting that in future implementations with regard to large amounts of MSM-input constraints, multiple data streams from host hardware to device hardware could potentially reduce the bottleneck [22]. Nevertheless, as described in section 6, these may require RDMA operations. Mentioned earlier in section 3, the use of Thrust both capitalizes on an easily optimized bucket running sum technique but also delays the generation process due to the necessity of converting between host types (i.e. primitive arrays) and Thrust types such as Thrust vectors. Also worthy of considerations are the problems that a Thrustreliant implementation introduces. Thrust is particularly well suited for optimizing running sums at runtime and is a natural choice for highly intensive running-sum loads. One particular issue of our Thrust implementation is the lack of ability for the Thrust interpreter to handle large memory transfers between device (the GPU) and host (the CPU), which are required for every Thrust call. It is important to note that this memory congestion is not a Thrust-specific issue. While memory bottlenecks may be slightly exacerbated with a Thrust implementation, the scale of the MSM is still the primary hurdle for any host-device transfer process that may not be completely amenable to multi-streaming techniques. The conversion of host arrays and primitive storage types necessitates their adaptation into thrust-readable vector conversions. In the MSM, we see primitive array of sizes 4 ∗ 226 or greater [1]. The existence of types as large as 712 bits requires the deconstruction of elliptic curve points into multiple segments. As a result, despite optimal parallelism within kernels, parallel PlonK fundamentally suffers from overly congested memory traffic, especially within the MSM computation. In Section 4, we see complications from massive conversions of the order of > 226 size arrays that are frequently converted from host-to-device and device-to-host. Because of these reasons, we see that Thrust is likely not an optimal choice for implementing running sums with large workloads, such as the one found in the computation of the MSM. These particular data structures, necessitated by the MSM and used throughout the various kernels and host processes, greatly affected the final computation. We discuss this further in Section 7 and in [26].

6

Alternative Techniques

Before moving forward, it is important to note that our utilization of Thrust in the implementation of Aztec’s Barretenberg (PlonK) does not affect the algorithmic structure of PlonK. It also does not utilize multiple I/O streams to interleave MSM computations on the GPU with memory transfer as seen in other implementations, such as cuZK[22]. Our parallel implementation paired with this work primarily aims to bring attention to the true bottleneck in tackling the problem of parallelizing the multi-scalar multiplication of points in large finite fields. In looking forward to improving upon our implementation, attention must be paid to sufficiently leveraging the parallelism on the GPU through increasing the pressure placed on I/O streams. This will then cause a greater number of streaming multiprocessors than what is currently used. With this in mind, we discuss several optimizations that may dramatically improve the scaling potential of zk-SNARKs. Primarily,

these areas concern the promising sectors of ZK research surrounding folding and incremental verifiable computation (IVC) in general. This scheme presents a recursive approach to proof generation of computations. It is also worth noting that at times IVC protocols avoid SNARKs, and even arguments of knowledge in general. These eliminate the need for a trusted setup or an FFT, and recent works show smallest known prover times and verifier overheads [21, 24]. While this incremental approach is promising, we see three unique reasons to believe non-recursive SNARKs still signify an important aspect of verifiable computation: (1) It is difficult to parallelize IVCs due to their linear nature. Consequently, computations that are generally approached from a parallel computing lens suffer when verified incrementally. There exist tree-based implementations of IVC that allow certain degrees of parallelism through the use of treebased recursive protocols, but fully exploiting the nature of certain embarrassingly parallel computations will always be inherently limited in IVC-based schemes. (2) The folding schemes of Mangrove [24], and Sangria [25] both rely upon Plonkish arithmetization schemes to perform commitments to the verifier. We want to highlight Sangria, which utilizes a zkSNARK - PlonK - to provide stronger arguments for succinctness and zero-knowledgeness in their incremental computation. ‘ (3) The problem of the MSM still presents itself in nearly every IVC scheme in the literature [6, 21, 21, 24, 25, 32], especially those which utilize folding. As described in Section 1, the MSM dominates prover time in SNARKs like PlonK. As a result, improvements in SNARKs via reductions in MSM compute time and efficient memory sharing also stand to benefit in the space of folding schemes. Beyond the above the reasons listed above, the dominant consideration is that folding schemes and recursive proof constructions are, in general, not applicable to problems that have a large volume of input data. More specifically, there exist problems that require verification not only of a statement of the latest computation over the latest subset of data but also verification of a statement over the latest subset of data along with previous subsets of data. Large proofs that fall into this category are of particular interest in the application domain of privacy-preserving healthcare software applications, such as the analysis of healthcare images, such as MRIs [19] with varying file sizes for different health-related images ranging from 131 KB to 30 MB. Other examples of large ZK-proof applications that do not meet the input requirements of folding schemes or recursive construction include: (1) Financial Data Analysis with an interest in financial structuring for the purposes of evasion. (2) Verification of an outsourced computation’s integrity, especially in cases where the computation is built upon a blackbox model. These examples highlight the problem set for which every additional proof may require data that have already been verified via IVC. If parallelization of folding schemes can be applied to IVC as a whole, and especially in the context of optimizing zkSNARKs found in certain folding schemes, then very promising offers of scalability

Performance Bottlenecks in Computing ZK Proofs on a GPU

arise. These scalability directions are even more beneficial in the context of parallelizable IVC’s, such as Mangrove [24]. While IVC is a promising domain, aforementioned downfalls indicate it is not a silver bullet, and we still must explore other realms for ZK acceleration.

7

Future Work

As applications with increasingly large numbers of constraints emerge, it becomes imperative that proof-generation techniques continue to advance to meet demand. In this section, we introduce several areas of future work, motivated by the results and observations we have presented in this paper and by emerging proving technologies that may be consequential for zk-SNARK generation schemes. First, the absolute need for GPU memory suggests a multi-GPU approach, even if all resulting parallelism cannot be exploited. The goal is to run the MSM computation at GPU speed to optimize proofgeneration latency. While a multi-GPU system seems straightforward, it introduces various other issues. Specifically, data-transfer bottlenecks would be even more prevalent than what we faced in our implementation for this paper. While we needed to move data between CPU and GPU, any partitioning of computations among GPU systems requires even more movement of memory. Recent developments, such as Dist-MSM[18], have further laid the foundation for multi-GPU implementations. Dist-MSM tackles these issues by limiting how often points and scalars are transferred, performing heavy computations locally, and aggregating partial results in a master node. Although our implementation reached maximum constraints of 225 , there are applications with a greater number of constraints, approaching a billion (230 ). Furthermore, potential use cases extend beyond those referenced, and the need for large constraint-set sizes is poised to grow. This presents the need for a multi-GPU approach and, more specifically, a cost model for data-transfer that accounts for all transfers among computers in a parallel computing cluster. Beyond data transfers, the nonuniformity of the MSM must also be considered as partitioning data requires attention. Seeing as the ultimate goal is scalability and latency, it is critical that, for each computation, the data arrive in a timely manner to optimize the full computing platform. Additionally, it is advantageous to allocate total memory usage in an efficient manner among multiple GPUs. For the MSM, this suggests that we must seek parallelization that is consistent with efficient data movement. Note that folding is absent from this list of future work. For the aforementioned reasons, we chose to overlook IVC schemes for the time being in favor of bolstering memory issues through the above techniques in the short term. However, we still support the idea that IVC schemes will be a leading solution in accelerating zero-knowledge for proof tasks that are segmentable into subtasks. That being said, within the scope of multiple GPUs, we clearly see an issue arise in memory sharing, which already exists between host and device on a single GPU. Thus, we again emphasize the value of developing a cost model for the size of the input constraintset size to the hardware requirement. It is consequential that this model consider the cost of memory transfers, any trade-offs, and the ideal partitioning of data among a multi-GPU system. This will

,,

be dampened by the potential use of RDMA within memory transfers, a promising new route of development for memory intensive programs [29]. We see a compelling and emerging direction for scaling zeroknowledge proofs. Specifically, the eventual implementation of a multi-GPU model[26] in conjunction with the use of RDMA to handle particular proofs of correctness that cannot be incrementally verifiable.

Acknowledgments This work is supported by Oracle Cloud and related resources provided by the Oracle for Research program, and by gifts from Steel Perlot and Google. A Lehigh CORE grant also provided support. We thank dePaul Miller, our colleague in the SSS Lab at Lehigh, for providing his GPU expertise. Finally, we acknowledge our colleagues in the Scalable Systems and Software Research group (sss.cse.lehigh.edu) and in Lehigh Blockchain (blockchain.cse.lehigh.edu).

References [1] Aztec. 2025. Barretenberg GIT Repository. https://github.com/AztecProtocol/barretenberg. [2] Suyash Bagad, Quang Dao, Yuval Domb, and Justin Thaler. 2025. Speeding Up Sum-Check Proving. Cryptology ePrint Archive, Paper 2025/1117. https: //eprint.iacr.org/2025/1117 [3] Paulo S. L. M. Barreto and Michael Naehrig. 2006. Pairing-Friendly Elliptic Curves of Prime Order. In Selected Areas in Cryptography, Bart Preneel and Stafford Tavares (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 319–331. [4] Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan Håstad, Joe Kilian, Silvio Micali, and Phillip Rogaway. 1988. Everything Provable is Provable in Zero-Knowledge. In Advances in Cryptology — CRYPTO’ 88., Shafi Goldwasser (Ed.). Springer. [5] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. 2018. Scalable, transparent, and post-quantum secure computational integrity. IACR Cryptol. ePrint Arch. (2018), 46. http://eprint.iacr.org/2018/046 [6] Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. 2014. Zerocash: Decentralized Anonymous Payments from Bitcoin. In 2014 IEEE Symposium on Security and Privacy. 459–474. doi:10.1109/SP.2014.36 [7] Daniel J. Bernstein. 2002. Pippenger’s Exponentiation Algorithm. Manuscript, University of Illinois at Chicago. https://cr.yp.to/papers/pippenger-20020118retypeset20220327.pdf. [8] Alexander R. Block, Justin Holmgren, Alon Rosen, Ron D. Rothblum, and Pratik Soni. 2021. Time- and Space-Efficient Arguments from Groups of Unknown Order. In Advances in Cryptology – CRYPTO 2021, Tal Malkin and Chris Peikert (Eds.). Springer International Publishing, Cham, 123–152. [9] Yu Chen, Seunghwan Kim, Yuzhe Song, and Xiao Wang. 2022. EdMSM: MultiScalar Multiplication for SNARKs and Faster Montgomery Multiplication. Cryptology ePrint Archive, Report 2022/1400. https://eprint.iacr.org/2022/1400. [10] Brad Cohn, Evan Shapiro, and Emre Tekişalp. 2020. Mina: Economics and Monetary Policy. https://minaprotocol.com/wp-content/uploads/ economicsWhitepaper.pdf. [11] Sai Deng and Bo Du. 2023. zkTree: A Zero-Knowledge Recursion Tree with ZKP Membership Proofs. Cryptology ePrint Archive, Paper 2023/208. https: //eprint.iacr.org/2023/208 [12] Tal Derei. 2023. Accelerating the PlonK zkSNARK Proving System using GPU Architectures. Technical Report. Master’s Thesis, Lehigh University. [13] Tal Derei, Benjamin Aulenbach, Victor Carolino, Caleb Geren, Michael Kaufman, Jonathan Klein, Rishad Islam Shanto, and Henry F. Korth. 2023. Scaling ZeroKnowledge to Verifiable Databases. In VDBS ’23: Proceedings of the 1st Workshop on Verifiable Database Systems. Association for Computing Machinery, New York, NY, USA. doi:10.1145/3595647.3595648 [14] Tal Derei, Caleb Geren, Michael Kaufman, Jon Klein, and Rishad Islam Shantho. 2023. Benchmarking PlonK, TurboPlonk, and UltraPlonk Proving Systems. Technical Report. Lehigh University. https://github.com/TalDerei/MastersResearch/blob/main/Benchmarking%20Plonk%2C%20TurboPlonk%2C%20and% 20UltraPlonk%20Proving%20Systems.pdf. [15] Joshua Fitzgerald. 2020. PLONK by Hand. https://medium.com/@MetastateTeam/plonk-by-hand-part-1-setup79347dc0a32/.

,,

[16] Ariel Gabizon, Zachary J. Williamson, and Oana-Madalina Ciobotaru. 2019. PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. IACR Cryptol. ePrint Arch. 2019 (2019), 953. [17] J. Groth. 2016. On the Size of Pairing-based Non-interactive Arguments. https: //doi.org/10.1007/978-3-662-49896-5_11. [18] Zhuoran Ji, Zhiyuan Zhang, Jiming Xu, and Lei Ju. 2024. Accelerating Multi-Scalar Multiplication for Efficient Zero Knowledge Proofs with Multi-GPU Systems. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3 (La Jolla, CA, USA) (ASPLOS ’24). Association for Computing Machinery, New York, NY, USA, 57–70. doi:10.1145/3620666.3651364 [19] Pooyan Kazemian, Hank Korth, and Manoj Malhotra. 2025. Verifiable Artificial Intelligence for Medical Decision Making: Application to Skin Cancer Diagnosis. In Proc. INFORMS Annual Meeting. [20] Pooyan Kazemian and Manoj Malhotra. 2024. Advancing Healthcare Delivery and Diagnostics Through Verifiable Artificial Intelligence and Blockchain. In POMS International Conference,. [21] Abhiram Kothapalli, Srinath Setty, and Ioanna Tzialla. 2022. Nova: Recursive Zero-Knowledge Arguments from Folding Schemes. In Advances in Cryptology – CRYPTO 2022, Yevgeniy Dodis and Thomas Shrimpton (Eds.). Springer Nature Switzerland, Cham, 359–388. [22] Tao Lu, Chengkun Wei, Ruijing Yu, Yi Chen, Li Wang, Chaochao Chen, Zeke Wang, and Wenzhi Chen. 2022. cuZK: Accelerating Zero-Knowledge Proof with A Faster Parallel Multi-Scalar Multiplication Algorithm on GPUs. Cryptology ePrint Archive, Paper 2022/1321. https://eprint.iacr.org/2022/1321 https://eprint. iacr.org/2022/1321. [23] Weiliang Ma, Qian Xiong, Xuanhua Shi, Xiaosong Ma, Hai Jin, Haozhao Kuang, Mingyu Gao, Ye Zhang, Haichen Shen, and Weifang Hu. 2023. GZKP: A GPU Accelerated Zero-Knowledge Proof System. In Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 (Vancouver, BC, Canada) (ASPLOS 2023). Association for Computing Machinery, New York, NY, USA, 340–353. doi:10.1145/3575693.3575711 [24] Wilson Nguyen, Trisha Datta, Binyi Chen, Nirvan Tyagi, and Dan Boneh. 2024. Mangrove: A Scalable Framework for Folding-based SNARKs. Cryptology ePrint Archive, Paper 2024/416. https://eprint.iacr.org/2024/416.pdf [25] Nicolas Mohnblatt. 2024. Sangria: a Folding Scheme for PLONK. Web document. https://geometry.xyz/notebook/sangria-a-folding-scheme-for-plonk. [26] Syeda Ajbina Nusrat. 2026. Cost Model for Multi-scalar multiplication of Zero Knowledge Proof. Technical Report. Master’s Thesis, Lehigh University, in preparation (May 2026). [27] NVIDIA. 2017. NVIDIA Tesla V100 GPU Architecture. Web document. https://images.nvidia.com/content/volta-architecture/pdf/voltaarchitecture-whitepaper.pdf. [28] NVIDIA. 2021. NVIDIA A100 TENSOR CORE GPU. https://www.nvidia. com/content/dam/en-zz/Solutions/Data-Center/a100/pdf/a100-80gb-datasheetupdate-nvidia-us-1521051-r2-web.pdf [29] NVIDIA. 2022. GPUDirect RDMA. https://docs.nvidia.com/cuda/gpudirectrdma/index.html [30] NVIDIA. 2022. NVIDIA A10 Datasheet. Web document. https://www.nvidia. com/content/dam/en-zz/Solutions/Data-Center/a10/pdf/datasheet-new/nvidiaa10-datasheet.pdf. [31] Muhammad Osama, Duane Merrill, Cris Cecka, Michael Garland, and John D. Owens. 2023. Stream-K: Work-Centric Parallel Decomposition for Dense MatrixMatrix Multiplication on the GPU. In Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (Montreal, QC, Canada) (PPoPP ’23). Association for Computing Machinery, New York, NY, USA, 429–431. doi:10.1145/3572848.3577479 [32] Srinath Setty. 2019. Spartan: Efficient and general-purpose zkSNARKs without trusted setup. Cryptology ePrint Archive, Paper 2019/550. https://eprint.iacr. org/2019/550 [33] Justin Thaler. 2023. Proofs, Arguments, and Zero-Knowledge. Now Foundation and Trends. [34] A. Tzionis. 2023. A “literature review” on Rollups and Validium. Web document. https://ethresear.ch/t/a-literature-review-on-rollups-and-validium/16370/1. [35] Maxim A. Vezenov. 2022. Accelerating zkSNARKs on Modern Architectures. Technical Report. Master’s Thesis, Lehigh University. [36] Samuel Williams, Andrew Waterman, and David Patterson. 2009. Roofline: an insightful visual performance model for multicore architectures. Commun. ACM 52, 4 (April 2009), 65–76. doi:10.1145/1498765.1498785 [37] Charles. F. Xavier. 2022. PipeMSM: Hardware Acceleration for Multi-Scalar Multiplication. Cryptology ePrint Archive, Paper 2022/999. https://eprint.iacr. org/2022/999 https://eprint.iacr.org/2022/999. [38] Ye Zhang, Shuo Wang, Xian Zhang, Jiangbin Dong, Xingzhong Mao, Fan Long, Cong Wang, Dong Zhou, Mingyu Gao, and Guangyu Sun. 2021. PipeZK: Accelerating Zero-Knowledge Proof with a Pipelined Architecture. In 48th ACM/IEEE Annual International Symposium on Computer Architecture, ISCA 2021, Valencia, Spain, June 14-18, 2021. IEEE, 416–428. doi:10.1109/ISCA52012.2021.00040

Carolino, et al.

[39] Zhiyuan Zhang, Yanxin Cai, Wenhao Yin, Xueyu Wu, Yi Wang, Lei Ju, and Zhuoran Ji. 2026. Pipelonk: Accelerating End-to-End Zero-Knowledge Proof Generation on GPUs for PLONK-Based Protocols. In Proceedings of the 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (Sydney, NSW, Australia) (PPoPP ’26). Association for Computing Machinery, New York, NY, USA, 439–451. doi:10.1145/3774934.3786448

Related documents

• FASTAR: FRI Accelerator for Scalable Transparent ARguments of Knowledge#1061173
• FASTAR: FRI Accelerator for Scalable Transparent ARguments of Knowledge#1043035
• AlchemQ: Proof-Carrying Quantum Circuit Optimization with Per-Result Equivalence Certificates#1013761
• Growing an Agent/Prover Interface: Evolutionary Tool Design for Cost-Efficient Theorem Proving in Rocq and Lean#1144511
• zkPHIRE: A Programmable Accelerator for ZKPs over HIgh-degRee, Expressive Gates#1144728