Locus: A Framework for Exploring and Optimizing Point Addition Hardware for Zero-Knowledge Proofs

• MSM dominates ZKP accelerator cost: prior profiling finds it uses 60–90% of proving time and more than half of compute area, with millions of PADDs in practical workloads.In zkSpeed, MSMs incur 4 billion field multiplications.Source: §1 · p. 1
• Prior PADD hardware targets a few specific curves, leaving no unified method to explore microarchitectural trade-offs across curves and hardware targets.Asymptotic cost alone does not capture factors such as pipeline depth, area, and on-chip memory.Source: §1 · p. 2
• Locus systematically characterizes PADD designs and generates synthesizable RTL for ASIC and FPGA backends.The study explores over 1,000 design points and integrates PADDs into MSM pipelines and a prior end-to-end ZKP accelerator.Source: §1 · p. 2
• 2.71× geomean speedup and 3.11× geomean area reduction over prior ASICs, 34.67× geomean speedup over CPU, and 3.15× geomean speedup in end-to-end proof generation at iso-area.Source: §1 · p. 2

2.1 Elliptic Curves

• Elliptic curves are finite-field point sets defined by nonsingular equations; Locus supports Short Weierstrass and Twisted Edwards forms and can be extended to others.The evaluation focuses on standardized named curves spanning both forms.Source: §2.1 · p. 2

2.2 Multi-Scalar Multiplication

• MSMs combine scalars and elliptic-curve points, using repeated point additions to perform point multiplications on scalars and coordinates of 256–753 bits.Pippenger’s Algorithm [27] partitions scalar multiplications into parallel windows and combines reduction steps.Source: §2.2 · p. 2

2.3 Point Addition

• Affine point addition requires costly modular inversion, so Locus uses Jacobian coordinates for Short Weierstrass curves and Extended Projective coordinates for Twisted Edwards curves.Most ZKP protocols use Short Weierstrass formulas that distinguish addition from doubling; Twisted Edwards often supports unified addition, and BLS12-377* denotes BLS12-377 expressed in that form.Source: §2.3 · p. 2

2.4 Related Work

• Prior accelerators use curve-specific PADD configurations, leaving alternative latency, area, and throughput trade-offs and their impact on MSM efficiency uncharacterized.Examples include FPGA designs using Karatsuba and constant multipliers and ASIC designs synthesized or hand-tuned for selected curves [1, 7–9, 18, 28, 29, 39, 40].Source: §2.4 · p. 2

3 The Locus Framework

• Locus parameterizes optimized cryptographic primitives in HLS and automates PADD design generation across curve forms and parameters.Its modular structure supports extension to additional equation forms.Source: §3 · p. 3

3.1 Addressing the Multiplier Bottleneck

• Modular multiplication dominates PADD area and latency, so Locus offers Montgomery and Barrett reduction as alternative kernels with modulus-dependent trade-offs.Montgomery uses precomputed q′ and Montgomery-domain operands; Barrett uses μ and a multiplier twice the Modmul operand width.Source: §3.1 · p. 3, §3 · p. 3

3.1.1 Decomposed Multipliers.

• Locus exposes multiplier decomposition depth and base width, using recursive Karatsuba, then Schoolbook, then baseline multipliers as operands shrink.It also adds optimized squaring primitives; approximately one-third of operations in Short Weierstrass PADD formulas are modular squarings.Source: §3.1.1 · p. 3, Figure 3 · p. 3

3.1.2 Constant Multipliers.

• Locus makes constant fixing a curve-dependent design choice because constant Hamming weight affects multiplier area and latency.Reduction constants q′ and μ, modulus q, and curve coefficients a, d, and k can each be fixed or left variable.Source: §3.1.2 · pp. 3–4

3.1.3 HLS Optimizations.

• Carry Save Adder clustering replaces regular adders in adder trees and yields up to 1.5× PADD speedup.The passage attributes this to lower, bitwidth-independent CSA latency at moderate area cost.Source: §3.1.3 · p. 4

3.2 Multi-Precision

• Multi-precision arithmetic uses smaller shared word-width units for larger operations, saving area at the cost of latency and throughput.Locus implements textbook multi-precision modular primitives for comparison.Source: §3.2 · p. 4

3.3 The Point Addition Unit

• Locus composes optimized modular primitives into complete PADD and PDBL units and reports area and latency for each curve and configuration.Both single- and multi-precision designs are supported.Source: §3.3 · p. 4

3.4 Optimizing MSM Performance

• Locus’s analytical MSM model prunes over 10,000 configurations in under 10 seconds and stays within 5% of cycle-accurate simulation for evaluated SZKP-style configurations.The model assumes uniform scalars and serial bucket accumulation; selected Pareto candidates are validated by simulation and synthesis.Source: §3.4 · p. 4

ASIC design space

• The ASIC sweep focuses on fully pipelined II = 1 single-precision designs, with baseline PADDs using Catapult multipliers and variable constants.The baseline matches prior work [9].Source: §4 · p. 4

ASIC implementation

• ASIC designs use Catapult HLS with a GF 12nm library and a 1 GHz target, except baseline multipliers at ≥512 bits, which target 667 MHz.Design Compiler estimates area and power; the MSM model and GF12 SRAM estimates guide sweeps, with selected latency estimates validated within 5% of simulation.Source: §4 · p. 4

FPGA implementation

• FPGA RTL is synthesized with Vivado at varying clock speeds on Versal HBM VH1782 and UltraScale+ VU9P platforms.The platforms represent state-of-the-art capability and comparison with established literature benchmarks, respectively.Source: §4 · pp. 4–5

Testing and verification

• All evaluated designs are validated against software references using 1,000 random and edge-case samples through the automated pipeline.The pipeline checks both C++ HLS sources and generated RTL.Source: §4 · p. 5

5 Evaluation Results

• The evaluation quantifies PADD optimizations with ablations and isolated design-knob analyses.It also compares against prior ASIC, FPGA, and CPU implementations.Source: §5 · p. 5
• The evaluation includes a case study on MSM performance.Source: §5 · p. 5
• The evaluation tests Locus PADDs in an end-to-end ZKP accelerator.Source: §5 · p. 5

5.1 Pareto Space Analysis

• Montgomery designs are fastest across evaluated curves and smaller in 5 of 8 cases, while Barrett designs are roughly 30% smaller for Ed25519 and Secp256k1.The smaller Barrett designs are associated with lower NAF Hamming weight for μ than for Montgomery’s q′.Source: §5.1 · p. 5
• For BLS12-377 and BLS12-381 Montgomery designs, the fastest options gain 42% and 58% speedup for 10% and 20% area increases; MNT4753 favors the smallest design.Source: §5.1 · p. 5
• Figure 4 maps the PADD design space across named curves and highlights Pareto-optimal points, analyzed separately for Montgomery and Barrett Modmul types.Source: Figure 4 · p. 5, §5.1 · p. 5
• Optimal settings vary by curve and reduction method: the fastest designs use low-to-mid Karatsuba depth, while the smallest use the deepest available depth.For Barrett, fixed reduction constants always yield the fastest designs in the reported analysis.Source: §5.1 · p. 5, Table 2 · p. 5

5.2.1 Ablation Study.

• Optimized multipliers provide roughly 2× speedup and area reduction alone; constant-fixing adds approximately 20% latency and 30% area reduction, varying by curve.For special-form primes, constant-fixing yields 40–60% additional area reduction for the smallest PADDs, versus 6–13% for other curves; Ed448 reaches up to 3.4× speedup and nearly 8× area reduction over baseline.Source: §5.2.1 · pp. 5–6, Figure 5 · p. 5

5.2.2 Impact of Karatsuba Depth.

• Multiplier designs achieve 4–8× better ADP than baseline across evaluated bitwidths, with intermediate Karatsuba depths typically minimizing ADP.The best depth varies at non-power-of-two widths: Montgomery 768-bit designs favor kar = 2, while 753-bit designs favor kar = 3; Barrett performs worse than Montgomery.Source: §5.2.2 · p. 6, Figure 6 · p. 6

5.2.3 Impact of Fixing Constants.

• Constant-fixing combinations have curve-dependent effects: fixing all constants minimizes area, but the lowest-latency configuration varies by curve.BN254 favors fixed q and variable q′, MNT4753 the reverse, and BLS12-377 favors fixing all constants; fixing curve coefficients usually has minimal impact, with a slight latency degradation for Ed448.Source: §5.2.3 · p. 6, Figure 7 · p. 6

5.2.4 Single-precision vs Multi-precision.

• Multi-precision designs perform worse than the single-precision baseline on ADP × II across evaluated bitwidths, despite using less area through resource sharing.Their latency penalty and inability to fully pipeline make them less suitable for high-throughput ZKP accelerators, though they may remain relevant under heavy resource constraints.Source: §5.2.4 · p. 6, Figure 8 · p. 6

5.3.1 ASIC.

• Locus’s fastest ASIC designs achieve 2.71× geomean speedup, and its smallest designs achieve 3.11× geomean area reduction over prior works.The comparison uses Locus-generated PADDs that follow prior approaches with baseline multipliers and constant-fixing disabled.Source: §5.3.1 · p. 6, Table 3 · p. 6

5.3.2 FPGA.

• On the VU9P, Locus achieves 2–5× speedup with 1.3–1.9× fewer cycles than CycloneMSM, and 3–5× fewer cycles than HardcamlMSM and BSTMSM.On VH1782, its min-DSP variant uses 1,512 DSPs, the lowest among implementations with reported DSP counts; Locus also spans resource–performance trade-offs rather than targeting one implementation.Source: §5.3.2 · p. 7, Table 4 · p. 7

5.3.3 Speedup over CPU.

• Against a single-threaded AMD EPYC 7502 CPU, Locus FPGA designs achieve 1.21–1.83× speedups, while ASIC designs achieve 19–70× speedups.MNT4753 designs are too large to fit on the evaluated FPGAs.Source: §5.3.3 · p. 7, Table 5 · p. 7

5.3.4 Rapid Algorithm Exploration.

• For BLS12-377*, the CycloneMSM PADD formula achieves 3.10× speedup and 2.98× area reduction versus standard Short Weierstrass, with 10 ns latency.Locus generates this ASIC design to assess the hardware impact of an algorithmic optimization that eliminates a key Modmul bottleneck.Source: §5.3.4 · p. 7, Figure 9 · p. 7

5.4 Locus MSMs vs. Prior Work

• The study constructs MSM Pareto curves by sweeping configurations for each curve’s Pareto-optimal PADDs under a 50 mm2 area budget, then validates predicted latency with cycle-accurate simulation.The comparison implements prior zkSpeed and SZKP PADDs at the same technology node.Source: §5.4 · pp. 7–8
• At iso-area, Locus MSM designs achieve 2.72× geomean speedup; at iso-latency, the fastest baseline MSMs are 2–3× larger than equivalent Locus designs.Locus also achieves roughly 2–4× improvement in performance per area across curves; gains are more pronounced at higher bitwidths, where Locus designs can clock at 1 GHz.Source: §5.4 · p. 8

5.5 End-to-End ZKP Evaluation

• With Locus optimizations at isofrequency, Design B reduces PADD depth from Design A’s 113 stages to 34, improving utilization and reducing runtime.At w = 5 there are 31 buckets, fewer than the 113 pipeline stages in Design A; Design C raises frequency to 1 GHz and achieves 3.19× geomean speedup over Design A.Source: §5.5 · p. 8
• Design G achieves 3.15× geomean speedup over Design D with less area by using Locus’s area-saving optimizations to include a second PADD.Increasing the window size to w = 7 provides 127 buckets, improving utilization when the PADD pipeline is deep.Source: §5.5 · p. 8
• SZKP’s simple scheduling schemes rely on pipeline depth being short relative to bucket count; deeper pipelines at higher frequencies and bitwidths can degrade utilization.Locus PADDs reduce pipeline depth at 1 GHz, preserving simple scheduling without requiring more complex schedulers.Source: §5.5 · p. 8

6 Conclusion

• Locus explores more than 1,000 PADD designs across curves used in ZKPs, blockchains, and digital signatures, exposing architectural trade-offs.The exploration spans performance- and area-targeted implementations across ASICs and FPGAs.Source: §6 · p. 8
• Locus rapidly generates and evaluates PADD implementations tailored to performance and area targets across ASICs and FPGAs.Source: §6 · p. 8
• Locus integrates optimized PADDs into an MSM and a full ZKP accelerator, demonstrating gains at both the MSM and proof-generation levels.Source: §6 · p. 8
• Locus’s optimized modular-arithmetic units provide a basis for extending the framework to other cryptographic modules.Source: §6 · p. 8