NTT-EIP as a building block for FALCON, DILITHIUM and Stark verifiers
With the release of Willow cheap, the concern for quantum threat against Ethereum seems to accelerate. Posts by Asanso and PMiller summarize those stakes and possible solutions. Those solutions include use of lattice based signatures such as Dillithium or FALCON (the latter being more optimized for onchain constraints), STARKs and FHE. There is a consensus in the cryptographic research community around lattices as the future of asymmetric protocols, and STARKs won the race for ZKEVMs implementation (as used by Scroll, Starknet and ZKsync).
Those protocols have in common to require fast polynomial multiplication over prime fields, and use NTT (a special FFT adapted to prime fields). While in the past Montgomery multipliers over elliptic curve fields were the critical target of optimizations (both hardware and software), NTT optimization is the key to a performant PQ implementation.
Discussion
In the past Ethereum chose specificity by picking secp256k1 as its sole candidate for signature. Later, after dedicated hardware and proving systems working on other hardwares were realeased, a zoo of EIP flourished to propose alternative curves. There where attempts to have higher level EIPs to enable all of those at once, such as EWASM, SIMD, EVMMAX, or RIP7696 (by decreasing order of genericity and complexity).
Picking NTT as EIP instead of a given scheme would provide massive gas cost reduction for all schemes relying on it.
- pros : massive reduction to all cited protocols, more agility for evolutions.
- cons: requires to be wrapped into implementations, not optimal for a given target compared to dedicated EIP, not stateless.
Implementation results
ZKNOX performed an optimized implementation of NTT, using top notch algorithm, Yul and memory hacks to reach a 1.9M NTT polynomial multiplication, 3.6M for a whole EVM-friendly falcon verification (shake being replaced by keccak). While this numbers provide a massive gains compared to previous implementation, it is still expensive. This is why pushing this primitive into nodes as a precompile is now proposed as EIP-9374.
Link
Acknowledgements
We are grateful to Antonio Sanso for its valuable insights and discussions.