Accelerating Multi-Scalar Multiplication for Efficient Zero Knowledge Proofs with Multi-GPU Systems

A zero-knowledge proof lets one computer prove to another that a statement is true while revealing nothing else about it — the basis of private digital currency and of verifiably outsourcing work to a machine you do not trust — but the cost is brutally lopsided, because CHECKING a proof is fast while CREATING one can take minutes even on a graphics processor, which is what keeps the technique out of everyday use; almost all of that time goes into a single mathematical operation called MULTI-SCALAR MULTIPLICATION, which the paper reports at about 78.2 percent of the work, so speeding it up is nearly the whole problem; this paper (Shandong University) presents DistMSM, which spreads that operation across SEVERAL graphics processors — adapting the classic bucket-based algorithm to a multi-processor setting and dealing with the bottlenecks that appear as you add more processors — and separately rewrites the elliptic-curve arithmetic that runs on each processor, cutting the demand for registers with two techniques and pressing the tensor cores (units built for machine learning) into service for certain very large integer multiplications; the reported result is an average speedup of 6.39 times over the best previous implementations, turning a task that took seconds on one processor into tens of milliseconds.

Why this problem is worth solving

The value of this technique is entirely real, and so is the reason almost nobody uses it casually — so it is worth understanding both the promise and where the cost sits.

That one operation is where all the engineering effort goes.

What people did before, and where it broke

• The direct method. Compute each scalar times its point separately using repeated doubling and adding, then sum everything. Correct and simple, but it pays the full expensive procedure once per point, which is hopeless when there are hundreds of millions of them.
• Pippenger’s bucket algorithm. The classic improvement, and still the foundation of every serious implementation. It converts the bulk of the work into ordinary point additions, so the expensive doublings are performed a fixed number of times overall rather than once per point.
• Single graphics processor implementations. Bucket accumulation is enormously parallel, so running it on a graphics processor with thousands of arithmetic units is a natural fit, and existing systems do this. But even so the paper notes proof generation can still take minutes.
• Custom hardware for the operation. Separate lines of work build dedicated accelerators for multi-scalar multiplication. These can be very fast, but require building and deploying new hardware rather than using the graphics processors organisations already own.
• The gap. The obvious next step is more graphics processors, but adding processors does not automatically add speed. The bucket algorithm contains work whose cost is set by the window size rather than by the number of inputs, so it does not shrink as processors are added, and distributing the work introduces communication that a single processor never paid. Separately, the arithmetic kernel on each processor is limited by how many registers the wide-integer values consume. That is the two-level gap DistMSM addresses.

How multi-scalar multiplication is computed, and where DistMSM intervenes

The idea

Amortize the expensive operation across every input at once. The insight at the heart of the bucket algorithm, which everything else builds on, is a reorganization. Multiplying a scalar by a point requires many DOUBLINGS, which are expensive, and doing that separately for every one of hundreds of millions of points is unaffordable. Pippenger’s method restructures the computation so that the doublings happen a fixed number of times for the whole problem, while each individual point contributes only a single cheap ADDITION into a bucket. The expensive resource is paid for once and shared by everyone. Restructuring work so a costly fixed step is amortized across a whole batch, rather than repeated per item, is the same batching-and-amortization discipline covered elsewhere on this site, where a system waits to accumulate enough work to justify a fixed transfer cost, and where a per-item overhead is hoisted out of a loop and paid once.

Watch the part that does not shrink. The reason more processors do not straightforwardly mean more speed is structural. In the bucket algorithm, the accumulation phase is proportional to the number of points, so splitting the points across processors genuinely divides that work. But the bucket-weighting phase is governed by the window size, so its cost stays the same no matter how many points there are or how many processors you employ. Anything that stays constant while everything around it shrinks eventually becomes the whole cost, and distributing the problem also introduces communication that a single processor never had to pay. The paper states that DistMSM identifies and addresses the bottlenecks that emerge during this scaling. Recognising that the component which refuses to shrink governs the limit is the same find-and-attack-the-bottleneck discipline covered elsewhere on this site, where speedups stall not because the parallel part is slow but because a fixed serial or reduction cost was left untouched.

Spend the scarce on-chip resource wisely, and repurpose the unit built for something else. At the kernel level the constraint is registers. A graphics processor gives each of its many concurrent threads a share of a fixed register file, so a thread that needs many registers means fewer threads can run at once, and fewer threads means less of the hardware’s latency-hiding parallelism is available. Elliptic-curve arithmetic is unusually greedy here, because a single value hundreds of bits wide occupies many registers and its intermediate products are wider still. DistMSM reports two techniques for reducing that pressure. It also reaches for the tensor cores, units placed on the chip to accelerate machine learning, and uses them for certain large integer multiplications. Treating a fixed on-chip budget as the thing to optimize, and repurposing a specialized unit for work its designers did not intend, are both patterns covered elsewhere on this site — in the pages where a finite hardware resource sets a hard ceiling that the software must be shaped around, and in the pages that press an existing hardware primitive into service for an unrelated purpose because it happens to have exactly the right shape.

Computing a multi-scalar multiplication with buckets

points on these curves have coordinates that are integers hundreds of bits wide, so even one point addition becomes many wide-integer operations
the answer is a single point, so all the intermediate results are eventually summed together

Why it works

• Multiplying each scalar by its point separately repeats the expensive doublings once per point → the bucket algorithm reduces each point to a single addition and performs the doublings a fixed number of times for the whole problem → the dominant cost stops growing with the scalar width times the number of points.
• Bucket accumulation is a huge number of independent additions → a graphics processor has thousands of arithmetic units for exactly that shape of work → the largest phase maps naturally onto the hardware.
• The bucket-weighting phase is governed by window size rather than input count → it does not shrink when the points are divided across more processors → it, together with newly introduced communication, is what limits multi- processor scaling, and the paper reports identifying and addressing these bottlenecks.
• Wide-integer values consume many registers, and registers are a fixed per-processor budget shared by all concurrent threads → reducing register demand allows more threads to run at once → more of the hardware’s latency-hiding parallelism is actually used.
• Tensor cores sit idle during ordinary integer work but are built to multiply small matrices very fast → certain large integer multiplications can be routed to them → a unit already present on the chip contributes to a workload it was never intended for.

What it costs (trade-offs and scope)

• It requires several graphics processors. The entire contribution assumes a distributed multi-processor system. Organisations with a single processor gain only the kernel-level improvements, and the headline speedup is reported across various processor counts rather than for any single configuration.
• Tensor cores are hardware-specific. Using matrix units for integer multiplication ties the kernel to processor generations that provide suitable tensor cores with suitable numeric formats, so the optimization does not transfer to hardware lacking them.
• The window size remains a tuning parameter. Bucket-based methods trade the cost of accumulation against the cost of bucket weighting through the window width, and the right choice depends on the input size, the curve and the machine — a knob that must be set rather than a property that holds automatically.
• It accelerates one operation, not proving as a whole. Multi-scalar multiplication is reported at about 78.2 percent of proof generation, which bounds the end-to-end benefit — even making it instantaneous would leave the remaining fifth of the work untouched.
• This page is written without the full text. The paper is not open access and no preprint or author copy could be located, so the mechanisms behind the two register techniques, the exact tensor-core mapping, the specific scaling bottleneck identified, the baselines, the hardware used and the per-curve results are not described here. The background above is standard, verifiable material about zero-knowledge proving and Pippenger’s algorithm; the claims about DistMSM come from the abstract.

The evaluation

The abstract reports an average speedup of 6.39 times over state-of-the-art multi-scalar multiplication implementations, measured across various elliptic curves and various numbers of graphics processors, and states that a task which previously took seconds on a single processor completes in tens of milliseconds. The specific hardware, the baseline systems, the curves tested, the processor counts and any breakdown showing how much each contribution supplied are not available in the material accessible for this page, so no such details are reproduced.

Check yourself

Sources

• Accelerating Multi-Scalar Multiplication for Efficient Zero Knowledge Proofs with Multi-GPU Systems (ACM DL, DOI 10.1145/3620666.3651364) — ASPLOS 2024, pages 57 to 70. Not open access; the abstract is the source for all DistMSM claims on this page.
• dblp record — bibliographic entry and authors (Zhuoran Ji, Zhiyuan Zhang, Jiming Xu, Lei Ju).
• Semantic Scholar entry — confirms the paper is closed access with no open-access copy available.