Technical Summary: ZK-Flex

Problem Statement

Zero-Knowledge Proofs (ZKPs), particularly the widely adopted Groth16 protocol, enable privacy-preserving verification of computational correctness. However, proof generation is computationally intensive, dominated by two stages: Polynomial (POLY) computation (involving Number-Theoretic Transforms, NTT) and Elliptic-Curve (EC) computation (involving Multi-Scalar Multiplication, MSM). Together, these account for approximately 95% of the total proving time.

Hardware acceleration for ZKPs faces two primary challenges:

1. Large-Precision Modular Multiplication: ZKP protocols operate over large finite fields (e.g., 256, 384, or 768 bits) that cannot easily exploit Residue Number System (RNS) parallelism due to non-decomposable prime moduli. Standard schoolbook multiplication is inefficient, and existing reconfigurable accelerators often struggle to support these varying precisions efficiently.
2. Dynamic Workload Shifting: The balance between POLY and EC workloads shifts dynamically based on the problem size (e.g., the number of constraints). Prior accelerators with separate engines for NTT and MSM often suffer from poor resource utilization, where one engine remains idle while the other is the bottleneck. Furthermore, existing solutions like ReZK and LegoZK are limited in precision scalability (ReZK up to 384-bit) or area efficiency (LegoZK), and they rely on fixed algorithmic mappings that prevent the exploitation of more efficient variants.

Methodology

The authors propose ZK-Flex, a flexible and scalable software–hardware co-designed framework. The system integrates a host-side software optimizer with a specialized ASIC accelerator.

Software Layer Optimizations

The software layer analyzes the workload and generates optimized instructions for the hardware:

• Next Smooth Composite (NSC) Padding: Conventional systems pad polynomial lengths to the next power of two (NP2), which can drastically increase the number of points in the subsequent MSM stage. ZK-Flex introduces an NSC strategy that pads to the next "smooth composite" number (formed by small prime factors like 2, 3, 5, 7). This reduces the MSM workload significantly when constraints are not near a power of two.
• Mixed-Radix NTT: To support NSC padding, the framework employs a mixed-radix NTT engine supporting radices 2, 3, 4, 5, 7, and 8. The software includes estimators to balance the trade-off between the overhead of mixed-radix NTT and the savings in MSM cost, selecting the optimal strategy (NP2 vs. NSC) for each specific workload.
• Adaptive MSM Configuration: The EC optimizer automatically determines the optimal window size and tiling strategy for the Pippenger bucket-based MSM algorithm based on available memory capacity and parallelism. It utilizes signed-digit representation and mixed point addition (MPADD) to reduce modular multiplications.

Hardware Architecture

The hardware accelerator is built around a reconfigurable core called TCore (Toom–Cook Core):

• TCore Design: TCore is a hierarchical architecture based on the Toom–Cook algorithm, which generalizes Karatsuba multiplication. It supports 256-bit, 384-bit, and 768-bit precisions using a hybrid Toom-2/Toom-3 scheme that minimizes area overhead. The core consists of Processing Elements (PEs) organized into groups for evaluation, integer multiplication, and interpolation stages.
• Scalable Composition: Multiple TCore units are interconnected via a Ruche-based Network-on-Chip (NoC). This allows the composition of higher-level kernels, such as NTT butterflies of various radices and various elliptic curve point operations (PADD, PDBL, etc.), enabling the hardware to adapt to different cryptographic parameters.
• Linked-List Memory Management: To address memory constraints during MSM accumulation, ZK-Flex introduces a linked-list memory mechanism. Instead of assigning dedicated bucket memory to every parallel engine (which scales poorly), this technique clusters points within buckets using pointers. This allows multiple MPADD engines to share a unified bucket memory with conflict-free access, significantly improving parallelism under limited on-chip memory capacity.

Key Contributions

1. Unified SW-HW Co-Design: ZK-Flex is the first framework to jointly optimize algorithmic choices (NSC padding, mixed-radix NTT) and hardware architecture (Toom–Cook cores, linked-list memory) to address the specific bottlenecks of ZKP generation.
2. Flexible Multi-Precision Core: The introduction of the TCore, which supports 256, 384, and 768-bit operations with minimal area overhead through a hybrid Toom-2/3 approach, overcoming the precision limitations of prior reconfigurable accelerators.
3. Efficient Memory Management: The linked-list memory mechanism enables high parallelism in MSM operations without the superlinear growth of bucket memory requirements, solving a key utilization bottleneck in prior designs.
4. Comprehensive Evaluation: The framework is evaluated across diverse ZKP workloads, including cryptographic primitives, blockchain applications (Groth16), and machine learning models (Lenet, VGG16).

Results

The authors synthesized ZK-Flex using a 28 nm process node and evaluated it against state-of-the-art accelerators (PipeZK, GZKP, and LegoZK) and CPU baselines.

• Performance Speedup: ZK-Flex achieves a 5–11× speedup in proof generation latency compared to the best prior reconfigurable accelerator (LegoZK). In specific cases (e.g., VGG16), the speedup reaches up to 11.5×.
• Area Efficiency: The framework demonstrates up to 3.8× higher area efficiency (proofs/s/mm²) compared to prior works.
• Component Performance:
  • NTT: Achieves 1.48× to 1.84× speedup over LegoZK.
  • MSM: Achieves 2.69× to 4.16× speedup over LegoZK.
• Software Impact: Ablation studies show that the software optimizations (POLY and EC optimizers) contribute an average 2.4× speedup over a baseline without these optimizations, with gains reaching up to 4.2× in specific scenarios.

Significance and Claims

The paper claims that ZK-Flex establishes a new foundation for high-performance, reconfigurable ZKP acceleration. By addressing the dual challenges of large-precision arithmetic efficiency and dynamic workload utilization, ZK-Flex overcomes the limitations of previous hardware-only or partially optimized approaches. The authors position the framework as a state-of-the-art solution capable of scaling across diverse cryptographic parameters and application domains, from blockchain rollups to machine learning verification, while maintaining high resource utilization and area efficiency.