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

Every GPU system built for zero-knowledge proofs so far has raced to finish one proof as fast as possible, which sounds right until you look at what the hardware is doing — a Merkle tree halves its work at every level, so the threads that were busy at the leaves sit idle for most of the run; BatchZK (Zhejiang and NUS) rebuilds the three computational modules that the newer hash-based protocols actually use as pipelines, so a thread that finishes one proof's stage immediately picks up the next proof's, and reports 259.5x the throughput of the leading GPU system plus 9.52 proofs per second for verifiable neural network inference — while being honest that individual proofs now take several times longer.

Why this problem is worth solving

The economics of this technology are throughput economics, and the research had been optimising something else.

The second half of the setup is a shift in the cryptography itself.

What people did before, and where it broke

• Accelerate a single proof on a GPU. Several published systems do this for the older protocols, spreading one proof across the device to minimise its latency. Where it broke. A single proof cannot occupy tens of thousands of cores for long. The Merkle tree phase alone halves its parallelism at every level and cannot be reordered, so utilisation collapses partway through and the remaining cores wait. Optimising latency actively spends the device on one item that cannot use it.
• Rely on GPU implementations that exist for the new modules. Industrial libraries do provide GPU implementations of Merkle trees and the sum-check protocol. Where it broke. The paper’s objection is that they use the intuitive parallel algorithm — one kernel, one instance, threads going idle as the work shrinks. Its measurements show one of them losing throughput on small trees specifically because the size falls below what the cores could absorb.
• Just launch many independent proofs at once. The obvious way to get throughput without redesigning anything: run many single-proof kernels concurrently. Where it broke. Every concurrent proof needs its full working set resident, so device memory becomes the limit long before the cores do, and each kernel still has the same idle tail — you have multiplied the waste rather than removed it.
• Port the existing accelerator work to the new protocols. Tempting, since the engineering is mature. Where it broke. The kernels have nothing in common. Transforms and curve multiplications are compute-heavy with regular structure; the sum-check protocol reduces to a few additions and multiplications per element, which makes it memory-bound instead, and the encoder multiplies vectors by sparse matrices whose entries are 256 to 768 bits wide rather than the 32 or 64 that sparse-matrix libraries assume.
• The gap. The two problems compound. Nobody had built a GPU system for the modules the new protocols actually use, and nobody had built any GPU proof system around throughput — so the natural question, what does a proof factory look like rather than a proof sprinter, had not been asked.

How BatchZK keeps the cores busy

The idea

Stop asking how fast one proof finishes and start asking how many finish per second. The reframing is the paper, and the evidence for it is a utilisation curve. Building a Merkle tree over a large input needs a thread per leaf at the bottom and half as many at each level up, so a kernel that begins fully occupied ends almost empty, and the layers are strictly sequential so nothing can be moved to fill the gap. Every prior GPU proof system has this shape and reports the latency it achieved anyway. Turning each layer into a pipeline stage and letting different proofs occupy different stages means the threads released as one tree narrows are immediately claimed by the wide base of the proof behind it, and the paper’s measurements show utilisation staying high across the whole run rather than falling off a cliff. Building for the number of items completed rather than the time of any one item is the inversion of what the GPU proof-acceleration work covered elsewhere on this site set out to do, and the paper is explicit that it is choosing the other side of that trade.

The protocols changed underneath, and the old accelerator work does not transfer. This is the second, independent argument, and it is why the modules had to be built from scratch rather than adapted. The older schemes are dominated by number theoretic transforms and multi-scalar multiplication over elliptic curve points; the newer ones deliberately avoid both, using a sum-check protocol, Merkle trees and a linear-time encoder instead. Those are not just cheaper versions of the same thing — they have a different character. The sum-check work per element is a couple of additions and a multiplication, which shifts the bottleneck from computation to memory access, so the optimisation that matters is arranging the table updates to avoid races without extra global traffic. The encoder multiplies vectors by sparse matrices, but the entries are field elements 256 to 768 bits wide, which is outside what any sparse-matrix library was built for. Recognising that a shift in cryptographic fashion invalidates a decade of accelerator design is the same observation made from the custom-silicon side by the unified zero-knowledge accelerator covered elsewhere on this site.

The payoff shows up in an application that could not previously be served at all. The concrete deployment is machine learning as a service, where a provider proves that a prediction really came from the model it committed to, without revealing the weights. Here the pipeline shape fits the problem exactly, because customer requests arrive as a stream rather than a batch you assemble. The system reports 9.52 proofs per second for VGG-16 inference on CIFAR-10, which the authors describe as the first sub-second proof generation in the field — a claim about amortised cost rather than about how long any single customer waits, since the end-to-end latency for one proof is 15.2 seconds. Against the neural network proving system it compares to, covered elsewhere on this site, the improvement is 458 times, though the two are running different models rather than the identical circuit.

Walking a batch of Merkle trees through the pipeline

This is the measurement that motivates everything else. The paper plots core utilisation and shows it collapsing for the non-pipelined schemes while staying flat for the pipelined ones. It also notes that one industrial GPU library actually loses throughput on small trees, precisely because the tree size drops below what the available cores could absorb.

Why it works

• The idle threads and the waiting proofs are the same resource mismatch. A shrinking computation releases threads it cannot reuse while other proofs wait to start → putting stages of different proofs side by side matches one to the other → utilisation stays high across the whole run instead of collapsing partway.
• Nothing about the arithmetic changes, only the scheduling. The same hashes and the same rounds are computed in the same order for each individual proof → the pipeline is a question of what a thread does next, not of what it computes → so the modules can be reused across several different protocols that share these building blocks.
• Dynamic loading is what makes many proofs in flight affordable. Running proofs concurrently the naive way needs every working set resident simultaneously → fetching each segment when its stage comes due means an in-flight proof holds only its current stage data → device memory stops being the limit on pipeline depth.
• Each module is optimised where its own bottleneck sits. Hashing is compute-bound and its 32-bit chunks match register width exactly, so they go in registers → the sum-check work is a couple of arithmetic operations per element and is therefore memory-bound, so two alternating buffers remove races without adding traffic → one design does not get applied uniformly to computations with opposite characters.
• A streaming application is the natural customer. Machine learning as a service receives requests one at a time rather than as an assembled batch → a pipeline consumes exactly that shape of input → the deployment fits the mechanism rather than being retrofitted to it.

What it costs (trade-offs and scope)

• Latency gets substantially worse, and the paper says so directly. Compared against non-pipelined implementations of the same modules, the pipelined versions reach as little as 0.161 of the benchmark latency for Merkle trees and 0.130 for sum-check at the larger size — that is, roughly six and eight times slower per item. The authors name recovering some of that as important future work.
• The latency penalty grows with problem size. At the smaller size the ratios are 0.388, 0.325 and 0.678 for the three modules; at the larger they fall to 0.161, 0.130 and 0.396. The deeper the pipeline has to be, the longer any individual item spends in it.
• The sub-second claim is about amortised cost, not waiting time. The verifiable machine learning deployment produces 9.52 proofs per second, but a single proof takes 15.2 seconds end to end — meaning roughly 145 proofs are in flight at once. It is a real and useful number for a service proving everything it serves; it is not what a single customer experiences.
• Most of the headline speedup comes from the protocol, not the pipeline. The authors provide this decomposition themselves, which is to their credit. At one circuit scale, switching protocols accounts for 24.34 times and the pipeline design for 14.70 times of the roughly 357 times total against the GPU baseline. The comparison is therefore against systems running older protocols as much as against systems lacking a pipeline.
• The 259.5 times abstract figure is the oldest GPU in the sweep. It is measured on a V100. Across the range of cards tested the margin narrows considerably, and the same table shows the newest card giving a much smaller ratio.
• The verifiable machine learning comparison uses different models. The authors trained their own VGG-16 reaching 93.93% accuracy against baselines at 90.30%, 90.37% and 84.19%. A stronger model is arguably a harder thing to prove, so this does not flatter them, but it does mean the circuits are not identical.
• Some comparisons are against CPU implementations. The sum-check speedup of over 3040 times is against a CPU library; against the industrial GPU implementation it is over 1.51 times, reaching 5.85 times at best. The two numbers describe very different things and only the second isolates the contribution.
• The main results run on a Grace Hopper superchip. Portability to older cards is demonstrated, but the headline configuration is high-end hardware with a fast host-to-device path, and the design leans on overlapping transfers with computation.

The evaluation

Check yourself

Sources

The paper is “BatchZK: A Fully Pipelined GPU-Accelerated System for Batch Generation of Zero-Knowledge Proofs” by Tao Lu, Yuxun Chen, Zonghui Wang, Xiaohang Wang, Wenzhi Chen and Jiaheng Zhang, published at ASPLOS 2025 Volume 1, pages 100-115, DOI 10.1145/3669940.3707270. The authors are at Zhejiang University and the National University of Singapore, with the first author having done the work as a visiting scholar at NUS.

This explainer is written from the full text, read from the authors’ preprint on the IACR Cryptology ePrint Archive (2024/1862). Everything above comes from the paper’s own sections 1 through 7: the table of which computational modules each generation of protocol depends on; the analysis of why one kernel per Merkle tree leaves threads idle as layers narrow, with the accompanying core-utilisation measurements; the pipelined Merkle tree design with its SHA-256 chunks forced into 32-bit registers and its multi-stream overlap of transfers with hashing; the pipelined sum-check design with its diagnosis that the bottleneck is memory rather than computation and its two alternating recyclable buffers avoiding write races, plus the tree-based reduction for the summation step; the pipelined encoder with its two interconnected pipelines, its sparse matrices derived from bipartite graphs, and the note that field elements of 256 to 768 bits fall outside standard sparse-matrix optimisations; the dynamic data loading scheme and its effect on amortised device memory; the machine-learning-as-a-service deployment with its commitment of model parameters via a Merkle root; the module evaluations against Orion, Simon, Icicle and Arkworks, including the sum-check figures of over 3040 times against CPU and over 1.51 times against the industrial GPU implementation; the latency table showing ratios of 0.388, 0.325 and 0.678 at the smaller size falling to 0.161, 0.130 and 0.396 at the larger; the full-system results against Libsnark, Bellperson and the Orion plus Arkworks combination; the explicit decomposition attributing 24.34 times to the protocol change and 14.70 times to the pipeline; the cross-GPU table giving 259.5 times on the V100; and the verifiable neural network results with 9.52 proofs per second, 15.2 seconds of latency, 93.93% model accuracy and speedups of 458 and 5601 times.