CycloneNTT: An NTT/FFT Architecture Using Quasi-Streaming of Large Datasets on DDR- and HBM-based FPGA Platforms

Kaveh Aasaraai; Emanuele Cesena; Rahul Maganti; Nicolas Stalder; Javier Varela; Kevin Bowers

Paper 2022/1657

CycloneNTT: An NTT/FFT Architecture Using Quasi-Streaming of Large Datasets on DDR- and HBM-based FPGA Platforms

Kaveh Aasaraai

, Jump Trading

Emanuele Cesena

, Jump Crypto

Rahul Maganti

, Jump Crypto

Nicolas Stalder

, Jump Crypto

Javier Varela, Jump Trading

Kevin Bowers, Jump Trading

Abstract

Number-Theoretic-Transform (NTT) is a variation of Fast-Fourier-Transform (FFT) on finite fields. NTT is being increasingly used in blockchain and zero-knowledge proof applications. Although FFT and NTT are widely studied for FPGA implementation, we believe CycloneNTT is the first to solve this problem for large data sets (, 64-bit numbers) that would not fit in the on-chip RAM. CycloneNTT uses a state-of-the-art butterfly network and maps the dataflow to hybrid FIFOs composed of on-chip SRAM and external memory. This manifests into a quasi-streaming data access pattern minimizing external memory access latency and maximizing throughput. We implement two variants of CycloneNTT optimized for DDR and HBM external memories. Although historically this problem has been shown to be memory-bound, CycloneNTT's quasi-streaming access pattern is optimized to the point that when using HBM (Xilinx C1100), the architecture becomes compute-bound. On the DDR-based platform (AWS F1), the latency of the application is equal to the streaming of the entire dataset times to/from external memory. Moreover, exploiting HBM's larger number of channels, and following a series of additional optimizations, CycloneNTT only requires passes.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint.
Keywords: NTT FPGA FFT Number Theoretic Transform Goldilocks field Quasi-Streaming
Contact author(s): kaasaraai @ jumptrading com
ecesena @ jumpcrypto com
rmaganti @ jumpcrypto com
nicolas @ jumpcrypto com
jvarela @ jumptrading com
kbowers @ jumptrading com
History: 2022-11-28: approved; 2022-11-28: received; See all versions
Short URL: https://ia.cr/2022/1657
License: CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2022/1657,
      author = {Kaveh Aasaraai and Emanuele Cesena and Rahul Maganti and Nicolas Stalder and Javier Varela and Kevin Bowers},
      title = {{CycloneNTT}: An {NTT}/{FFT} Architecture Using Quasi-Streaming of Large Datasets on {DDR}- and {HBM}-based {FPGA} Platforms},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1657},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1657}
}