BatchZK: A Fully Pipelined GPU-Accelerated System for Batch Generation of Zero-Knowledge Proofs

Paper: BatchZK: A Fully Pipelined GPU-Accelerated System for Batch Generation of Zero-Knowledge Proofs
Review Form: The Guardian

---

Summary

This paper presents BatchZK, a GPU-accelerated system designed to optimize the throughput of batch zero-knowledge proof (ZKP) generation. The authors correctly identify a gap in existing research, which has largely focused on reducing the latency of single proof generation. Their approach is to construct a deep pipeline where individual computational modules of modern ZKP protocols (sum-check, Merkle tree, linear-time encoder) are broken into stages, with each stage mapped to dedicated GPU resources. The system is evaluated on several GPUs and demonstrated in a verifiable machine learning context.

While the engineering effort is commendable and the raw throughput numbers appear impressive, my assessment is that the paper’s core claims are built on a foundation of questionable and potentially misleading comparisons. The experimental methodology conflates architectural improvements with algorithmic ones, the system's design appears brittle and manually tuned, and the significant negative impact on latency is not adequately addressed.

---

Strengths

1. Relevant Problem Formulation: The paper's focus on throughput for batch ZKP generation is highly relevant for many practical applications, such as large-scale verifiable computation services or blockchain rollups, where aggregating and proving many transactions or computations is the primary goal. This is a valuable shift from the common focus on single-proof latency.
2. Focus on Modern Protocols: The system is designed around the computational primitives of recent, efficient ZKP systems (e.g., those based on the sum-check protocol), rather than the more heavily studied NTT/MSM-based protocols. This aligns the work with the current trajectory of ZKP research.
3. Demonstrated High Throughput: The results, on their face, show a system capable of generating a high volume of proofs per second, particularly in the verifiable machine learning application (Section 6.3, page 13), where sub-second proof generation is achieved.

---

Weaknesses

1. Fundamentally Flawed Performance Comparisons: The paper’s headline claims of massive speedups are predicated on an apples-to-oranges comparison. The abstract claims ">259.5x higher throughput compared to state-of-the-art GPU-accelerated systems." This figure is derived from Table 8 (page 13), which compares BatchZK (implementing modern, cost-effective protocols) against Bellperson (implementing older, more computationally expensive R1CS-based protocols using MSM/NTT). A significant, and likely dominant, portion of this speedup comes from the choice of ZKP protocol, not the authors' proposed pipelined architecture. The authors briefly acknowledge this in their "breakdown" analysis (Section 6.3, page 12), but this admission is buried, while the misleading top-line numbers are highlighted in the abstract and introduction. A rigorous evaluation would compare the proposed pipelined system against a non-pipelined, batched baseline that implements the exact same ZKP protocol. Without this, the true contribution of the pipeline architecture is impossible to quantify.

2. Brittle, Manually-Tuned Resource Allocation: The core of the pipeline's efficiency relies on balancing the stages. The authors state, "we manually allocate resources to different modules to keep their throughput consistent" (Section 4, page 9), providing a hard-coded ratio of 35:12:113 for a V100 GPU. This raises serious concerns about the system's generality and robustness:

   • Architecture Dependence: How does this optimal ratio change for different GPU architectures with varying numbers of SMs, memory bandwidth, and core designs (e.g., A100, H100)? The paper provides no analysis.
   • Problem Size Dependence: How does the ratio change for different problem sizes (e.g., circuit scale S, Merkle tree depth)? A system that requires expert manual re-tuning for every new hardware target or problem class is not a general-purpose solution but a highly specialized proof-of-concept.

3. Insufficient Analysis of the Latency-Throughput Trade-off: The paper's own results in Table 6 (page 11) show that the pipelined approach leads to a substantial increase in per-proof latency compared to non-pipelined baselines (e.g., Merkle tree latency is 2.5x worse than Simon, Sumcheck is 3x worse than Icicle). The authors frame this simply as a trade-off. However, this is a critical limitation that is not explored. Many high-throughput scenarios, such as blockchain transaction sequencing, still have latency constraints. The paper fails to define the application space where such a severe latency penalty is acceptable, weakening the argument for the system's practical impact.

4. Oversimplified Memory Analysis: The claim of reduced memory usage is, again, based on a flawed comparison with Bellperson (Table 10, page 13), whose memory footprint is dominated by its underlying cryptographic operations. The true comparison should be against a naive batching of the same protocols BatchZK uses. While the dynamic loading approach is sensible, the paper provides no analysis of the pipeline's own memory overhead, such as the memory required for buffering intermediate data between the numerous pipeline stages.

5. Missing Experimental Details for Reproducibility: The verifiable machine learning application results (Table 11, page 13) are presented without a key piece of information: the size of the resulting arithmetic circuit (e.g., number of multiplication gates) for the VGG-16 inference. Without this parameter, the reported throughput of 9.52 proofs/second is not comparable to other works and the result is not reproducible.

---

Questions to Address In Rebuttal

1. Regarding the headline performance claims (>259.5x speedup): Can the authors provide a revised evaluation that compares BatchZK against a non-pipelined (but still batched and GPU-accelerated) version of the same sum-check-based protocol? This is the only way to isolate and accurately measure the performance contribution of the proposed pipelining architecture itself.

2. Regarding resource allocation: Please provide a sensitivity analysis for the manual 35:12:113 thread allocation ratio. How does performance degrade when this ratio is applied to different GPUs (e.g., the A100 or H100 from your tests) or to different circuit sizes? Does your system provide any mechanism for automatically determining these ratios?

3. Regarding latency: Please provide a more detailed discussion of the application scenarios for which the observed 2.5-3x degradation in single-proof latency is acceptable. Conversely, are there high-throughput applications (e.g., time-sensitive financial transaction batching) for which BatchZK would be fundamentally unsuitable due to this latency penalty?

4. Regarding the verifiable machine learning evaluation: To ensure reproducibility and fair comparison, please state the exact number of constraints and multiplication gates in the arithmetic circuit generated for the VGG-16 model used in your evaluation in Table 11.

Reviewer: The Synthesizer (Contextual Analyst)

---

Summary

The paper presents BatchZK, a GPU-accelerated system designed for high-throughput batch generation of zero-knowledge proofs (ZKPs). The authors identify a crucial shift in the ZKP landscape: a move away from protocols reliant on expensive primitives like NTT and MSM, towards newer, more efficient protocols built on cost-effective modules like sum-check, Merkle trees, and linear-time encoders. The core contribution is a fully pipelined architecture that decomposes these modern ZKP modules into sequential stages, with each stage mapped to dedicated GPU kernels. This design maximizes GPU utilization for batch processing, directly targeting throughput rather than the single-proof latency optimized by prior works. The authors demonstrate the system's effectiveness with impressive results, including a >259x throughput improvement over prior GPU-accelerated systems and, most notably, achieving sub-second proof generation for a VGG-16 model in a verifiable machine learning application.

---

Strengths

This is an excellent and timely systems paper that makes a significant contribution to the practical application of zero-knowledge proofs.

1. Clear and Insightful Problem Framing: The authors have done a masterful job of contextualizing their work. The distinction they draw between the "first category" (NTT/MSM-based) and "second category" (sum-check/Merkle-based) of ZKP protocols is lucid and compelling (Figure 1, page 3). This framing immediately establishes a clear research gap: hardware acceleration has historically focused on the former, leaving the increasingly popular latter category underserved. This paper squarely addresses that gap.

2. Elegant and Well-Motivated Technical Approach: The core idea of creating a deep pipeline by breaking down ZKP primitives into their constituent computational layers (e.g., layers of a Merkle tree, rounds of a sum-check) is a classic systems optimization applied brilliantly in a new domain. As illustrated in Figure 4 (page 5), this approach directly tackles the GPU underutilization problem inherent in naive parallelization of these "reducing" workloads. It represents a fundamental shift from optimizing for latency to optimizing for throughput, which is the correct metric for many real-world ZKP applications like blockchain rollups and Machine-Learning-as-a-Service (MLaaS).

3. Transformative Performance and Impact: The results are not merely incremental; they are transformative. The ability to generate 9.52 proofs per second for a VGG-16 inference (Table 11, page 13) is a landmark achievement. It moves verifiable machine learning from a theoretical curiosity with multi-minute or multi-second proof times into the realm of practical, sub-second viability for real-time services. This result alone could significantly accelerate the adoption of verifiable AI. The broader system speedups (>259x over Bellperson on a V100 GPU) further underscore the power of their pipelined approach.

4. Bridging Theory and Practice: This work serves as a vital bridge between the fast-moving frontier of ZKP theory and the practical needs of system deployers. By building a high-performance engine for the primitives used in modern protocols like HyperPlonk, Orion, and Virgo, the authors are providing the tooling necessary to unlock the potential of this recent cryptographic research. The paper is an exemplar of how systems and architecture research can act as a force multiplier for advances in other fields.

---

Weaknesses

The weaknesses of the paper are minor and relate more to exploring the boundaries of the proposed approach rather than any fundamental flaws in it.

1. Limited Discussion on Generalizability and Adaptability: The paper demonstrates a highly effective system, but the pipeline appears to be carefully hand-tuned. The resource allocation section (Section 4, page 9) mentions manually balancing threads based on an empirically derived execution time ratio (35:12:113). This raises questions about the engineering effort required to adapt BatchZK to new ZKP protocols or even variations of existing ones. A discussion on the principles of this pipeline construction and the potential for a more automated or adaptable framework would strengthen the paper's contribution from a methodological standpoint.

2. Insufficient Exploration of the Latency-Throughput Trade-off: The authors correctly identify that their system prioritizes throughput over latency and provide some latency numbers in Table 6 (page 11). However, this critical trade-off could be explored more deeply. For many interactive applications, even within a batch-processing paradigm, the "time to first proof" or the end-to-end latency for a given task remains important. A characterization of how latency behaves as batch size and pipeline depth increase would provide a more complete picture of the system's performance envelope and help practitioners better understand its suitability for different use cases.

---

Questions to Address In Rebuttal

1. Regarding the manual resource allocation mentioned on page 9: How sensitive is the system's performance to the precise thread allocation ratios between the different modules (linear-time encoder, Merkle tree, sum-check)? Could the authors elaborate on the process or methodology for tuning these parameters when targeting a new ZKP protocol or a different GPU architecture?

2. The paper's primary contribution is a dramatic improvement in throughput, at the cost of some latency for individual proofs. Could the authors provide more insight into this trade-off? For example, what is the effective end-to-end latency for a proof that enters the pipeline when it is already full (i.e., the steady-state latency)? How does this compare to the latency of a single-proof, non-pipelined execution of the same primitives on the GPU? This would help clarify the exact nature of the performance trade-off.

Paper Title: BatchZK: A Fully Pipelined GPU-Accelerated System for Batch Generation of Zero-Knowledge Proofs
Review Form: The Innovator

---

Summary

The authors propose BatchZK, a GPU-accelerated system designed to maximize the throughput of batch zero-knowledge proof (ZKP) generation. The core thesis is that prior GPU work on ZKPs has incorrectly focused on latency reduction for single proofs using older, computationally expensive primitives (NTT, MSM). This paper pivots to address throughput for batches of proofs using modern, cost-effective primitives: the sum-check protocol, Merkle trees, and linear-time encoders. The claimed novelty is the system's "fully pipelined" architecture, where each ZKP primitive is decomposed into a series of dedicated GPU kernels, allowing batches of proofs to be streamed through the system, maximizing hardware utilization.

---

Strengths

The primary strength of this work lies in identifying a gap in the state-of-the-art and proposing a novel system architecture to fill it. While the constituent ideas (pipelining, GPU acceleration) are not new in isolation, their synthesis and application in this specific context represent a genuine contribution.

1. Novel Application of a Classic Architecture: The core idea—decomposing a complex computation into a deep, multi-kernel pipeline for streaming workloads on a GPU—is a novel application in the ZKP domain. Prior GPU-ZKP work like GZKP [38] focused on optimizing monolithic kernels for latency. BatchZK's contribution is to correctly identify that the batch generation problem is a throughput problem, for which a pipeline is the appropriate architectural pattern.

2. Novel Primitive-Specific Decompositions: The novelty is most evident in how the authors adapt each primitive to the pipeline model:

   • Merkle Tree (Section 3.1, page 5): The proposed method of dedicating kernels to specific layers of the tree and streaming multiple trees through this pipeline (Figure 4b) is a clear and novel departure from the "intuitive" single-kernel-per-tree approach used in prior work like Simon [51].
   • Linear-time Encoder (Section 3.3, page 7): The authors state that no prior GPU implementation exists, making their implementation the first. More significantly, their method for handling the inherent recursion by splitting the process into two separate, interconnected pipelines (Figure 6) is a novel and clever transformation that makes the algorithm amenable to a streaming architecture. This is a non-trivial contribution.

3. Clear Distinction from Prior Pipelined ZKP Work: The authors correctly cite PipeZK [64], which applied pipelining to ZKPs on ASICs. However, the delta is significant and clear: PipeZK targeted the older NTT/MSM primitives on a fundamentally different hardware architecture. BatchZK's contribution is a novel pipeline design for the different computational patterns of sum-check, Merkle trees, and linear-time encoders on GPUs. This distinction is well-defined and defended.

---

Weaknesses

The paper's claims of novelty are generally strong, but could be tempered with more precise language regarding which components are truly new versus which are standard high-performance computing (HPC) engineering practices.

1. Overstated Novelty of Standard Optimizations: The paper presents certain techniques as integral parts of its contribution without sufficiently acknowledging them as standard practice. For instance, the use of multi-stream technology to overlap data transfers with computation (Section 4, page 9) is a canonical GPU optimization pattern. Similarly, the double-buffering memory access pattern for the sum-check protocol (Figure 5, page 6) is a well-known technique to avoid memory hazards in streaming algorithms. While their application is necessary for the system to function, these are not novel ideas in themselves. The paper would be stronger if it framed these as "applying standard techniques" rather than implying they are part of the core novel design.

2. Novelty is Architectural, Not Algorithmic: To be clear, this work does not introduce a new ZKP protocol or a new fundamental algorithm for any of the computational modules. Its novelty is purely at the systems and architecture level—it presents a new way to execute existing algorithms. This is a valuable contribution for a systems conference like ASPLOS, but the paper should maintain this clarity throughout. The contribution is in the "how," not the "what."

---

Questions to Address In Rebuttal

1. On the Novelty of the Sum-check Pipeline: The authors contrast their pipelined sum-check module with the implementation in Icicle [28]. The paper's argument rests on the assumption that Icicle uses a monolithic kernel that leads to thread idling. Can the authors provide more concrete evidence for this? A comparative profile of GPU core utilization between their single-proof, non-pipelined sum-check kernel and the Icicle implementation would substantially bolster the claim that their pipelined decomposition is a fundamentally new and superior approach.

2. Generalizability of the Pipeline Transformation: The transformation of the recursive linear-time encoder into a dual-pipeline structure is the most technically novel part of the paper. Is this a bespoke solution tailored exclusively to the Spielman encoder, or is it a generalizable pattern for mapping a certain class of recursive algorithms onto streaming hardware? If the latter, discussing this pattern's characteristics would elevate the significance of this contribution beyond the immediate ZKP context.

3. On the Dynamic Loading Method: The paper claims a "dynamic loading method" as a feature (Abstract, page 1). From the description, this appears to be a direct consequence of the pipelined design (i.e., only data for the current proof-in-flight needs to be loaded). Is there any novel mechanism in the loading method itself, or is the memory reduction simply an inherent benefit of a streaming architecture over a naive parallel approach that would load all m proofs' data at once? Please clarify the precise novelty here.