🚀 Accelerated libiop by Optimizing Additive FFT Algorithms
This repository is a fork of libiop focusing on optimizing additive Fast Fourier Transform (FFT) algorithms used in the original repository.
This library uses the Cantor additive FFT implemented in the additive-fft library and demonstrates notable performance gains in the current Aurora [BCRSVW] implementation over the Gao–Mateer (GM) algorithm provided in libiop across all input sizes, and over the LCH algorithm re-implemented in additive-fft for smaller circuits, which are prevalent in many zkSNARK applications.
We achieved about ~40% performance improvement on the Aurora while maintaining correctness and interface compatibility with upstream libiop.
WARNING: This is an academic proof-of-concept prototype, and in particular has not received careful code review.
This implementation is NOT ready for production use.
Please follow the installation instructions.
| Prover: GM | Prover: Cantor | Prover: LCH | Verifier: GM | Verifier: Cantor | Verifier: LCH | ||
|---|---|---|---|---|---|---|---|
| 9 | 16 | 0.44 | 0.33 | 0.35 | 0.04 | 0.04 | 0.04 |
| 10 | 17 | 0.90 | 0.67 | 0.71 | 0.05 | 0.05 | 0.05 |
| 11 | 18 | 1.87 | 1.36 | 1.44 | 0.07 | 0.06 | 0.07 |
| 12 | 19 | 3.99 | 2.91 | 2.93 | 0.10 | 0.09 | 0.10 |
| 13 | 20 | 8.53 | 6.02 | 5.95 | 0.17 | 0.15 | 0.16 |
| 14 | 21 | 19.47 | 12.01 | 12.44 | 0.29 | 0.26 | 0.28 |
| 15 | 22 | 41.05 | 25.27 | 25.41 | 0.54 | 0.48 | 0.52 |
| 16 | 23 | 84.26 | 50.83 | 50.63 | 1.02 | 0.93 | 1.00 |
| 17 | 24 | 176.67 | 104.26 | 102.95 | 1.98 | 1.79 | 1.93 |
| 18 | 25 | 373.83 | 216.00 | 213.61 | 3.88 | 3.51 | 3.78 |
| 19 | 26 | 771.42 | 443.88 | 441.51 | 7.78 | 6.91 | 7.44 |
All measurements were taken with Google Benchmark, with a minimum 10-second warm-up period, on:
- CPU: AMD Ryzen 9 9950X @ 5.7 GHz
- RAM: 64 GB DDR5
- OS: Debian 12 with kernel 6.12.12
The codeword length is set to
This library is licensed under the MIT License.
This work was supported by BTQ Technologies Corp. and Mitacs.