EIP-7885 NTT operation precompiles (Precompile for NTT operations)

No call decision · EVM & execution · EIP status Draft · created 2025-02-12

Adds four precompiles: NTT (Number Theoretic Transform) and its inverse, which speed up polynomial multiplication, plus vector modular multiplication and addition. The goal is to substantially lower the cost of quantum-resistant signature verification and STARK verification.

Why it is needed

Regular accounts on Ethereum today use a signature scheme called ECDSA. This scheme can be broken once a sufficiently powerful quantum computer appears. The quantum-resistant signature algorithms meant to replace it (FALCON, DILITHIUM, etc.) rely on polynomial multiplication as their core operation, but implementing this directly in the EVM today is prohibitively expensive in gas. By the source text's measurement, a single FALCON signature verification costs about 1.8 million gas, which can only be experimented with on low-fee L2s and is impractical to use on L1. This EIP lowers that cost substantially by providing the NTT transform, a common building block of polynomial multiplication, as a precompile (a fast operation built into the client in advance). Because it embeds a general-purpose operation rather than one specific algorithm, it can be used to implement either DILITHIUM or FALCON at low cost, and the same operation also accelerates STARK verifiers, helping both scalability and preparedness against the quantum threat.

What changes

Today

After EIP-7885

Who is affected

In depth

Composition of the four precompiles

This adds four precompiles: NTT_FW (forward NTT, negative wrap convolution), NTT_INV (inverse NTT), NTT_VECMULMOD (vector modular multiplication), and NTT_VECADDMOD (vector modular addition). In the Specification's constants table, the addresses are still TBD, while the reference implementation (op-geth) uses 0x12, 0x13, 0x14, and 0x15. The Specification body sets the gas cost of NTT_FW and NTT_INV at 600 each, and defines the two vector operations with separate formulas.

Mathematical foundation: cyclotomic rings and field parameters

The operations are defined over the cyclotomic ring R = F_q[X]/(Xⁿ+1). n is the degree, a power of two, and q is a prime satisfying q ≡ 1 mod 2n. ω is an n-th root of unity in F_q, and ψ is a 2n-th root of unity. Elements of R are polynomials of degree at most n-1, represented as coefficient vectors of length n. NTT only works for primes satisfying this condition (q ≡ 1 mod 2n), so the test cases also include checks that reject moduli violating this condition.

The NTT_FW and NTT_INV algorithms

NTT_FW takes a vector a in standard order as input and converts it to bit-reversed output using a precomputed table Ψrev that stores powers of ψ in bit-reversed order. Conversely, NTT_INV restores bit-reversed input to standard order using the Ψ⁻¹rev table and finally multiplies all coefficients by n⁻¹. Both algorithms are described as a triple loop in a butterfly structure, and the functional tests verify the round trip INTT(NTT(x)) = x. The Rationale states that multiplication is completed as f×g = NTT_INV(NTT_VECMULMOD(NTT_FW(a), NTT_FW(b))), and that the complexity is n·log₂n instead of n².

Vector operations and two gas models

NTT_VECMULMOD performs componentwise multiplication of two vectors mod q, and NTT_VECADDMOD performs componentwise addition mod q. The Specification defines, letting k be the smallest power of two greater than log₂(q), the multiplication gas as k·log₂(n)/8 and the addition gas as k·log₂(n)/32. Meanwhile, the gas analysis in the Rationale presents a different model: NTT has a fixed cost per scheme (on a nocgo basis, Falcon-512 790, Falcon-1024 1,750, ML-DSA NTT_FW 220 and NTT_INV 270; on a cgo basis, 500, 1,080, 256, and 340 respectively), while the vector operations are linear in length N: VECMULMOD ceil(0.32×N), VECADDMOD ceil(0.3×N). The target throughput is about 50 to 55 mgas/s, the same level as ECRECOVER. Both models appear together in the document, so the figures are not yet finalized.

Supported fields: covering both quantum-resistant cryptography and STARKs

The fields to which the design applies are listed as NIST-selected quantum-resistant schemes such as FALCON (q=3·2¹²+1), DILITHIUM (q=2²³-2¹³+1), and KYBER (q=13·2⁸+1), along with Babybear (q=15·2²⁷+1, Risc0), Goldilocks (q=2⁶⁴-2³²+1, Polygon Plonky2), M31 (q=2³¹-1, Circle STARKs, STwo, Plonky3), and StarkCurve (q=2²⁵¹+17·2¹⁹²+1). The choice to embed a general-purpose NTT rather than one dedicated to a specific algorithm is the basis for flexibility spanning both signature schemes and STARK proof systems.

Benchmarks: savings compared to Solidity

In a pure Yul-optimized Solidity implementation, Falcon (q=12289, n=512) costs 1.8M gas for one NTT, with an estimated 3.6M gas overall, and Dilithium is estimated at about 2.3M gas overall. The source text states that adopting this EIP can reduce Falcon signature verification to 1,500 gas, and that adopting a hash function as a separate EIP would enable 2,000 gas verification. In op-geth integration tests (OP-Stack testnet), ETHFALCON verification dropped from 1,800,000 gas to 479,341 gas, a 73.4% reduction, and ETHDILITHIUM saved more than 2.1M gas per verification. The liboqs (cgo) implementation has 36 to 38% lower NTT gas than pure Go.

Input format and tests

The reference implementation's input format is ring_degree (4 bytes) + modulus (8 bytes) + coefficients (uint16×N for FALCON, int32×N for ML-DSA). The tests include rejection of abnormal inputs such as an invalid opcode, a ring degree that is not a power of two or is less than 16, a modulus that does not satisfy q ≡ 1 mod 2N, coefficients exceeding the modulus, and mismatched input length, as well as functional verification using a ring degree of 16 and modulus of 97, and benchmarks for Falcon-512 (n=512, q=12289), Kyber-128 (n=256, q=3329), and Dilithium-256 (n=256, q=8380417). Reference implementations are provided in Python, Solidity, and op-geth (nocgo and cgo).

Still at the Draft stage

This EIP's status is Draft, so its content may change. The precompile addresses are listed as TBD in the constants table, the gas models in the Specification and the Rationale are written differently from each other, and the Security Considerations section is left empty as 'needs discussion'. There is no record of a fork-inclusion decision at a core developer call.

Original EIP · ← EIPs