Accelerating Number Theoretic Transform with Multi-GPU Systems for Efficient Zero Knowledge Proof

Generating a zero-knowledge proof takes minutes and rests on two heavy computations — one of which parallelises across many graphics processors easily and one of which does not, because its access pattern reshuffles the whole dataset at every stage; UniNTT (Shandong University and Quan Cheng Laboratory) makes the awkward one work across eight processors, and the reason it pays off is counterintuitive, since spreading it out makes that step slower in isolation while making the whole proof faster.

Why this problem is worth solving

The asymmetry is what makes the technique both valuable and impractical.

The specific computation being accelerated has an access pattern that fights parallelism.

What people did before, and where it broke

• Run the transform on one device and everything else on many. The pragmatic answer, and what every prior system does. Where it broke. It looks correct if you time the transform alone, but its output feeds the other computation, which is already spread across devices — so the output must be distributed regardless. From one device that distribution is a single link to the host and then out again, leaving the other links idle.
• Give each device its own independent transform. If a protocol needs several, hand one to each device and the links stay busy. Where it broke. Real protocols do not have enough. The workflow of a leading proof system contains groups of one, three, four and five transforms, and on an eight-device machine the measured link utilisation is 0.31.
• Use the classical four-step decomposition. Arrange the data as a matrix, transform the columns, transpose, transform the rows. This is the standard way to split a large transform and is used across distributed systems, custom silicon and programmable logic. Where it broke. It requires multiplying every element by a correction table between the two halves. That is tolerable once, but reaching from a whole multi-device system down to a warp needs four decompositions, and the paper computes the resulting arithmetic overhead at 16.7 percent for a representative size — prohibitive when each multiplication is over a 256-bit integer.
• Optimise each level of the hierarchy separately. Thread-level, block-level and device-level transforms each get their own tuned implementation. Where it broke. They are different algorithms at each level, so every optimisation has to be conceived and implemented several times, and an idea that works at one level is never tried at the others.
• Accelerate the transform on other hardware. Custom silicon, programmable logic, and processor clusters have all been targeted, mostly using the four-step decomposition. Where it broke. Nothing, but those designs assume sequential processors or fixed pipelines. The correction table is cheap when the small transforms share a core and can share one table; on a graphics processor the pieces run on separate units with separate memory, so sharing the table means replicating it.
• The gap. Nobody had asked whether the correction step was necessary, or noticed that removing it would let the same algorithm run unchanged at four different scales — which is what turns a pile of level-specific tricks into one set of optimisations applied four times.

How a transform gets spread across a machine

The idea

Making the transform slower in isolation makes the proof faster overall. This is the observation the paper opens with and it inverts the usual reasoning. Timing the transform by itself, moving it onto many devices is a clear loss — communication appears where there was none, and the measurements show every implementation, including this one, getting worse from one device to two. But the transform’s output is the input to the other heavy computation, which already runs across all the devices, so that output has to be distributed whatever happens. Done from a single device it is a one-to-many pattern through the host, using one link while the rest idle; done from all devices it happens concurrently on every link. The volume is fixed and the number of links goes up. The measured consequence is stark: the other computation is 65.2 percent of the arithmetic and the transform only 20.9, yet accelerating the transform delivers a 3.84 times end-to-end improvement, because once the arithmetic is fast enough the bottleneck has moved to the interconnect. That this whole situation exists is a direct consequence of the multi-device multi-scalar multiplication work covered elsewhere on this site having already succeeded — solving one half of the pipeline is what made the other half’s placement matter.

The standard decomposition carries an assumption that is wrong on this hardware. The classical four-step method transforms columns, transposes, transforms rows, and multiplies everything by a correction table in between. That table exists so all the small transforms can use the same root of unity, which is a sensible trade on a sequential processor where those transforms share a core and therefore share one table in cache. On a graphics processor the pieces run on physically separate units with separate memory, so sharing the root would mean replicating the table anyway — the optimisation buys nothing and the correction step is pure cost. Giving each row a different root instead removes the multiplication entirely, making the split exactly equivalent to the original computation. The size of the win is in what it unlocks rather than what it saves directly: four nested decompositions under the classical scheme would cost 16.7 percent extra arithmetic on 256-bit integers, which is why nobody decomposed that aggressively before. Finding that a textbook parallelisation encodes assumptions that do not hold at these bit widths is precisely the observation the earlier GPU proof system covered elsewhere on this site was built on.

Free decomposition turns four hierarchy levels into one problem. Once splitting costs nothing, the same transform can be run at every scale, and the machine stops looking like four different things. The paper abstracts each level to the same two components — units that execute transforms, and a memory they exchange through — and designs five optimisations against that abstraction rather than against any level. Each is then tailored: root caching works in the column stage where all units share a root and is replaced by prefetching in the row stage where they do not; data layout means choosing which transform variant matches the current ordering at device level and transposing big integers to kill an eight-way bank conflict at warp level. The interesting result is that optimisations assumed to belong to one level generalise. Pipelining was invented to hide inter-device transfers and turns out to be worth 7.4 percent within a device and 3.5 percent inside a thread block; and letting a warp own a transform, previously thought too fine, converts shared-memory exchanges into register shuffles. An enabling change whose value lies in making previously inexpressible optimisations possible is the same shape as the non-blocking automata work covered elsewhere on this site, where the headline idea is a slowdown alone and everything comes from what it permits.

Following one transform down the hierarchy

The variant of the algorithm is chosen to match how the data already sits in memory, so no transpose is needed on the way in. The output ordering does not matter, since what consumes it is indifferent to layout.

Why it works

• The volume is fixed but the number of links is not. The output has to reach every device whether or not the transform ran on all of them → doing it from one device serialises through a single link while the others idle → doing it from all devices puts every link to work at once, so the transfer time falls roughly in proportion to the device count.
• Sharing a root of unity is only worth something when the pieces share memory. The correction table exists so small transforms can reuse one root table → on hardware where the pieces run on separate units with separate memory, that table gets replicated rather than shared → so giving each piece a different root costs nothing in practice and removes the correction multiplication entirely.
• Zero-cost splitting is what permits splitting four times. A decomposition that costs 4 percent extra arithmetic each time is fine once and adds 16.7 percent when nested four deep → at 256 bits per integer that is decisive, since modular multiplication grows with the square of the word count → removing the cost is what makes it reasonable to reach all the way from a multi-device system down to a warp.
• One algorithm at every scale means one set of optimisations. When each level runs a different formulation, every idea must be reinvented per level and cross-level transfer never gets tried → when they all run the same computation, the hardware can be described uniformly and an optimisation written once → which is how pipelining, designed for the slowest level, was found to be worth 7.4 and 3.5 percent at two much faster ones.
• Exchanging data once per level frees the fast memory for something else. Conventional implementations use shared memory for the data exchange in every round → aggressive decomposition reduces that to one exchange per level → leaving shared memory available to cache roots of unity, which prior implementations could not do at the thread-block level at all.

What it costs (trade-offs and scope)

• The speedup depends heavily on how many independent transforms the protocol has. Against the best prior implementation it is 7.88 times for a single transform and 1.89 times for eight. The advertised 4.26 times is an average across that range. The authors argue one is typical in real protocols and the workflow they show supports it, but the endpoints differ by a factor of four.
• The baselines cannot use the hardware, by construction. No other implementation supports splitting a transform across devices, so they were extended by giving each device an independent transform. When the protocol has fewer transforms than the machine has devices, they simply idle. That is a genuine limitation of those systems and it is also not a comparison between two multi-device algorithms, because there is only one.
• Spreading the transform out makes the transform slower. Every implementation including this one degrades going from one device to two. The win exists only in end-to-end context, which the paper states plainly and shows in its own figures.
• The motivation is specific to one interconnect topology. The whole argument rests on independent link bandwidths and a one-to-many pattern through host memory. Adaptation to a faster direct interconnect is asserted to be straightforward and is not evaluated.
• Memory assumptions are large. The roots of unity occupy four gigabytes in host memory, held for the entire application lifetime, plus half a gigabyte per device for the row stage — which the authors note some devices may have to reallocate between operations.
• Several optimisations barely matter at several levels, which the paper reports. Skipping multiplications by one affects 0.024 percent of operations at the top level and is applied only in the first round at thread-block level, because distinguishing the two kinds of operation costs more than it saves on hardware without branch prediction. Its cumulative contribution is 7.8 percent.
• The breakdown is measured against an unoptimised kernel. The per-level percentages are relative to a weak baseline, and how they compose across levels is not obvious from the presentation.
• Constants are hand-chosen for this configuration. The block-level transform size, the number of pipeline groups, and how many transforms a block-level pipeline holds are all set empirically for the machine used.
• Main results are one curve on one set of consumer devices. The study across four processor models and four curves is single-device only, so it says nothing about how the multi-device behaviour varies.
• The big-integer arithmetic is borrowed. It comes directly from one of the baseline libraries, which sharpens the comparison against that library but means the absolute numbers inherit whatever it does.

The evaluation

Check yourself

Sources

The paper is “Accelerating Number Theoretic Transform with Multi-GPU Systems for Efficient Zero Knowledge Proof” by Zhuoran Ji, Jianyu Zhao, Peimin Gao, Xiangkai Yin and Lei Ju, published at ASPLOS 2025, pages 1-14, DOI 10.1145/3669940.3707241. The authors are at Shandong University and Quan Cheng Laboratory.

This explainer is written from the full 14-page text. Everything above comes from the paper’s own sections: the background on proof systems, the stages of proof generation and the workflow of the protocol family used as the running example, the definition of the transform and the butterfly structure of the two classical fast algorithms with their differing strides; the motivation section arguing that multi-device support reduces end-to-end communication time, with the comparison of one-to-many and concurrent distribution patterns and the measured interconnect utilisation figure for assigning one transform per device; the decomposition section covering the matrix formulation, the worked 16-point and 64-point examples, recursive application, the mixing of conventional rounds with decomposition, the pseudocode, and the comparison against the classical four-step method including the computed arithmetic overhead for four nested decompositions and the argument about why sharing roots does not help on this hardware; the abstract hardware model and the five optimisations of root reuse and prefetching, input data layout, multiplication elimination with its pseudocode, and shortest-path pipelining; the systematic deployment across the multi-device system, single device, thread block and warp levels, with the per-level workload sizes, root memory requirements, layout decisions, and the reasoning about where each optimisation does and does not pay; and the evaluation covering the hardware and baselines, transform performance across differing numbers of concurrent transforms, end-to-end results on three workloads with their proof sizes and verification times, scalability for both the transform alone and end-to-end proof generation, performance across four processor models and four elliptic curves including the analysis of why the widest curve underperforms its theoretical arithmetic cost, and the per-level breakdown of every optimisation.