GZKP: A GPU Accelerated Zero-Knowledge Proof System

A zero-knowledge proof verifies in milliseconds but takes half a minute to GENERATE, because proving means millions of operations on 256–753-bit integers — GZKP rebuilds both prover stages for the GPU (an NTT that never shuffles global memory, an MSM that merges every window into one bucket set, and a big-integer library running in double-precision floats) for an order-of-magnitude speedup over the best prior GPU provers.

Why this problem is worth solving

A

But the cost didn’t vanish — it moved to the prover. Every private Zcash transaction requires its sender to generate a proof, and that takes over 30 seconds of CPU time. Filecoin’s storage proofs, private smart contracts, verifiable databases, even proofs about machine-learning predictions all sit behind the same bottleneck. The arithmetic is brutal by construction: zkSNARK security rests on

What people did before, and where it broke

Proof generation has exactly two expensive stages. The POLY stage runs a series of

Both kernels have decades of parallel-computing literature behind them, and the existing GPU provers imported it directly. That is where things broke:

• NTT: the shuffle that ate the kernel. A GPU wants the 32 threads of a
  the GPU’s scheduling unit — 32 threads that execute in lockstep and achieve full memory bandwidth only when they access consecutive addresses (a “coalesced” access)
  to read consecutive addresses, but the NTT’s butterfly pattern reads elements a large stride apart. The classical fix — physically shuffle the array between iteration batches so the next batch reads contiguously — is nearly free for 8-byte floats. With 381-bit or 753-bit elements (48–96 bytes each), the shuffle is itself a giant data movement: measured in bellperson, shuffle steps consume 42–81% of each batch’s time. Skipping the shuffle is no better — the strided accesses it prevents grow from 13% to 53% of runtime between consecutive batches at scale 2²⁴.
• MSM: a serial tail and unbalanced buckets. Every fast MSM uses
  the classic trick for computing Σ sᵢ⊗Pᵢ — slice each scalar into windows of k bits, and within each window throw points into 2ᵏ−1 “buckets” by their k-bit digit. Sum each bucket, weight buckets by their digit (bucket-reduction), then combine window results with repeated doubling (window-reduction). It replaces per-scalar doubling chains with mostly plain point additions
  . On a GPU the point-merging phase parallelizes well, but the final window-reduction is a dependency chain that must run serially — bellperson ships it back to the CPU. Worse, real proof workloads have sparse scalar vectors (mostly zeros and ones, an artifact of how circuits encode bound checks), so bucket sizes vary wildly: the heaviest bucket holds 2.85× the average, and every warp waits for the slowest one. This is why MINA’s GPU barely improved on libsnark’s CPU end to end.
• Big-integer arithmetic itself. GPUs provision far more floating-point than integer multiply throughput, yet every prior prover ran its field arithmetic on the integer units, with each 753-bit number spread across 24 thirty-two-bit words.

How GZKP generates a proof

The idea

Don’t move the data — move the work assignment. The NTT insight is that shuffling exists only to make thread accesses contiguous, and contiguity can be manufactured without touching global memory. Later NTT batches consist of many small independent groups; GZKP assigns several of them (G ≥ 4) to one thread block, which loads G strided slices and transposes them in shared memory — 48 KB per SM, free to permute. The global array is written back in the SAME order it was read. What the classic algorithm did with a full-array pass through global memory, GZKP does with an on-chip transpose whose cost is invisible. A column-major layout for the big integers finishes the job: limb j of 32 consecutive elements sits at 32 consecutive addresses, so every warp access coalesces — worth 2× by itself at 753 bits.

Spend cheap preprocessing to delete the serial step. Pippenger’s window-reduction exists because bucket b in window t represents b·2^(t·k)⊗P — different windows carry different weights, so their results must be combined by a doubling chain at the end. GZKP’s move: bake the weight into the POINT instead. If the table already holds 2^(t·k)⊗Pᵢ, then window t’s digit can be added directly into a single, window-agnostic bucket set. All windows merge; the doubling chain vanishes; and point-merging — already 90% of the work — becomes a single uniform phase that saturates the GPU. The naive table is too big (over 5 GB at Zcash’s scale), so GZKP stores weighted points only at checkpoints every M windows and pays at most (M−1)·k extra additions to reach intermediate windows — a knob that adapts the same code to a 32 GB V100 or an 11 GB GTX 1080Ti.

Balance the load you can no longer hide. With one giant merged bucket set, the sparse-scalar imbalance that crippled MINA would be fatal — so GZKP treats bucket sizes as a scheduling input. Buckets are grouped into tasks of similar total load, the heaviest tasks launch first, warps are allocated proportional to load, and individual point-additions are internally parallelized across threads via cooperative groups so even one monster bucket spreads across the machine.

Feed it all with floating-point arithmetic. Field elements are represented as 52-bit limbs stored in FP64 mantissas; Dekker’s method splits each multiplication so products are exact. The GPU’s double-precision units — mostly idle in integer-based provers — do the heavy lifting. This library is orthogonal to the algorithms: the paper shows it accelerates even the baseline’s own design by 1.6×.

Walking through one Zcash proof

vector size: 2,097,151
bellperson: 0.69 s POLY + 2.24 s MSM

Why it works

• Shuffling was pure overhead that scaled with bit-width → keeping data stationary and transposing small tiles in 48 KB shared memory buys contiguity without global traffic → NTT time drops up to 2.1× from this alone, and total NTT runtime becomes linear in N (the baseline’s wasn’t, because its fixed one-group-per-block division left 30 of 32 threads idle in late batches).
• Window-reduction was serial because windows carried different weights → precomputing the weights into the points makes every window’s contribution commensurable → all additions land in one bucket set, the GPU runs one giant uniform accumulation, and the CPU round-trip for the serial tail disappears.
• The preprocessing table depends only on the circuit’s fixed base points, not the scalars → it is computed once and amortized over every proof the circuit ever generates → the online path pays only the (M−1)·k extra additions, tunable against available memory.
• Load imbalance is measurable before launch (bucket sizes are known after digit-counting) → scheduling can be explicit — similar-load groups, heaviest-first, warps proportional to load → sparse real-world scalars no longer serialize the machine, which is precisely where MINA lost its GPU advantage.
• FP64 units on a V100 vastly outnumber integer-multiply throughput → 52-bit limbs in double mantissas with Dekker’s exact products move field arithmetic onto the abundant resource → 1.6× on the baseline’s own design, compounding with the algorithmic wins.

What it costs

• Preprocessing memory, deliberately spent. The checkpointed weighted-point table makes GZKP’s BLS12-381 memory footprint larger than bellperson’s (though it plateaus past scale 2²² and stays within a V100’s 32 GB). The paper’s framing: bellperson under-uses GPU memory; GZKP converts that headroom into speed.
• Offline preprocessing per circuit. The weighted-point table must be built before the first proof. It is reusable across all proofs of that circuit — the standard zkSNARK setting — but a workload with constantly changing base points would not amortize it.
• Extra additions at checkpoints. Skipping intermediate windows costs up to (M−1)·k point-additions per element — the explicit price of fitting the table into smaller GPUs.
• Per-curve tuning. The window size k comes from profiling each curve/scale combination, and the finite-field library needs limb-count configuration per bit-width (15 limbs at 753 bits).
• Engineering depth. Custom CUDA with cooperative groups, a hand-built floating-point field library, and layout changes (column-major limbs) that permeate every kernel — this is a ground-up prover, not a patch to bellperson.

The evaluation

Experiments run on NVIDIA V100 GPUs (with a GTX 1080Ti repeat to check the results aren’t V100-specific), against the strongest available system per curve: libsnark and bellman on CPU, MINA and bellperson on GPU. Real workloads come from xJsnark applications (AES, SHA-256, RSA operations, Merkle trees, an auction) and the Zcash transaction tool — both produce the sparse scalars that stress load balancing — while module microbenchmarks use dense synthetic data, so the sparse-workload wins are not an artifact of cherry-picked inputs. Honest accounting note: the ablations attribute the gains — in the MSM at scale 2²², bucket partitioning alone gives 3.25×, the floating-point library adds 33%, and load balancing brings the total to 5.6×; in the NTT, the library gives 1.6× and the shuffle-less design another 1.5× on top.

Check yourself

Sources

• ACM DL (open access): GZKP: A GPU Accelerated Zero-Knowledge Proof System — ASPLOS 2023