This repository contains the EIP for NTT transform, along with a python reference code, and a solidity implementation.

With the release of Willow cheap, the concern for quantum threat against Ethereum seems to accelerate. Post by [Asanso](https://ethresear.ch/t/so-you-wanna-post-quantum-ethereum-transaction-signature/21291) and [PMiller](https://ethresear.ch/t/tidbits-of-post-quantum-eth/21296) 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 asymetric 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](https://vitalik.eth.limo/general/2019/05/12/fft.html) 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.

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 attempt 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.

The NTT operates on sequences of numbers (often coefficients of polynomials) in a modular arithmetic system. It maps these sequences into a different domain where convolution operations (e.g., polynomial multiplication) become simpler and faster, akin to how FFT simplifies signal convolution. Compared to FFT which uses root of unity in complex plane, NTT uses roots of unity in a finite field or ring.

The NTT is based on the Discrete Fourier Transform (DFT), defined as:

Where:

- $x[j]$: Input sequence of length N.

- $X[k]$: Transformed sequence,

- $q$: A prime modulus,

- $\omega$: A primitive N-th root of unity modulo $q$, with

$\omega^N \equiv 1 \mod q \quad \text{and} \quad \omega^k \not\equiv 1 \mod q \; \forall \; 0 < k < N$

NTT computation uses the a similar approach as Cooley-Tukey algorithm to provide a O(N log N) complexity. The NTT algorithm transforms a sequence $(x[j])$ to $(X[k])$ using modular arithmetic. It is invertible, allowing reconstruction of the original sequence via the Inverse NTT (INTT). The inverse process is similar but requires dividing by \(N\) (mod \(q\)) and using $(\omega^{-1}$) (the modular inverse of $\omega$). The following algorithm is extracted from

[[LN16]](https://eprint.iacr.org/2016/504.pdf), and describe how to compute the NTT when $R_q= \mathbb{Z}_q[X]/X^n+1$ (Negative Wrap Convolution).


The Inverse NTT is computed through the following algorithm:


| Field | $n$ | Recursive NTT (Tetration) | Iterative NTT (ZKNox) | Iterative InvNTT (ZKNox)|

|-|-|-|-|-|

|Falcon | 512 | 761 μs | 528 μs | 561 μs |

|Falcon | 1024 | 1642 μs | 1076 μs | 1199 μs |

|Dilithium| 128 | 165 μs | 114 μs | 113 μs |

|Dilithium| 256 | 371 μs | 258 μs | 260 μs |

|BabyBear | 256 | 531 μs | 389 μs | 404 μs |

The recursive inverse NTT is very costly because of the required inversions. For Falcon, the field is small enough so that field inversions can be precomputed, but the cost is still higher than the iterative inverse NTT.

The field arithmetic has not been optimized. In the case of BabyBear, this becomes significant and so the comparison is not really significant.

| Function | Description | gas cost | Tests Status |

|------------------------|---------------------|---------------------|---------------------|

| NTT recursive | original gas cost from [falcon-solidity](https://github.com/Tetration-Lab/falcon-solidity/blob/main/src/Falcon.sol) | 6.9M | OK|

| InvNTT recursive | original gas cost from [falcon-solidity](https://github.com/Tetration-Lab/falcon-solidity/blob/main/src/Falcon.sol) | 7.8M | OK|

| Full Falcon verification | original gas cost from [falcon-solidity](https://github.com/Tetration-Lab/falcon-solidity/blob/main/src/Falcon.sol) | 24 M| OK|

| NTT iterative | ZKNOX | 4M | OK|

| InvNTT iterative | ZKNOX | 4.2M | OK|

| Full Falcon verification | ZKNOX | 8.5 M| OK|

Further optimizations are reached by using Yul for critical sections and using the CODECOPY and EXTCODECOPY trick detailed in of [[RD23]](https://eprint.iacr.org/2023/939.pdf) (section 3.3, "Hacking EVM memory access cost").

| Function | Description | gas cost | Tests Status |

|------------------------|---------------------|---------------------|---------------------|

| ntt.NTTFW | ZKNOX_NTTFW, iterative yuled | 1.9M | OK|

| falcon.verify_opt | Full falcon verification with precomputated pubkey | 3.6M | OK|

ZKNOX is planning a client implementation for node of the considered EIP.

We provided an optimized version of FALCON, using an optimized version of NTT. This code can be used to speed up Stark verification as well as other lattices primitives (Dilithium, Kyber, etc.). While it seems achievable to use FALCON as a progressive precompile, the cost remains very high. Using a client implementation with NTT-EIP (in a Geth fork for example), ETHEREUM could become from a PQ-Friendly and ZK-Friendly chain. This work is supported by the Ethereum Foundation.

- [[LN16]](https://eprint.iacr.org/2016/504.pdf) Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography. Patrick Longa, Michael Naehrig.

- [[EIP616]](https://eips.ethereum.org/EIPS/eip-616) EIP-616: SIMD Operations for the EVM. Greg Colvin.

- [[RD23]](https://eprint.iacr.org/2023/939.pdf) Speeding up elliptic computations for Ethereum Account Abstraction. Renaud Dubois.

- [[DILITHIUM]](https://eprint.iacr.org/2017/633.pdf) CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme. Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler and Damien Stehlé.

Fork of `op-geth` with precompiled contracts for Number Theoretic Transform (NTT) operations using open-quantum-safe liboqs via CGO bindings, enabling efficient on-chain post-quantum cryptographic operations.

| Address | Name | Description |

| ------- | --------- | ---------------------------------------------------------------------- |

| `0x12` | NTT_FW | Forward NTT using liboqs (Falcon-512/1024, ML-DSA) |

| `0x13` | NTT_INV | Inverse NTT using liboqs (same schemes as NTT_FW) |

| `0x14` | VECMULMOD | Element-wise modular multiplication: `result[i] = (a[i] * b[i]) mod q` |

| `0x15` | VECADDMOD | Element-wise modular addition: `result[i] = (a[i] + b[i]) mod q` |

| Scheme | Ring Degree | Modulus | Element Size |

| ----------- | ----------- | ------- | ---------------- |

| Falcon-512 | 512 | 12289 | uint16 (2 bytes) |

| Falcon-1024 | 1024 | 12289 | uint16 (2 bytes) |

| ML-DSA | 256 | 8380417 | int32 (4 bytes) |

git clone -b feature/ntt-cgo-bindings https://github.com/yhl125/liboqs.git

sudo apt install astyle cmake gcc ninja-build libssl-dev python3-pytest python3-pytest-xdist unzip xsltproc doxygen graphviz python3-yaml valgrind pkg-config

cd liboqs/bindings/go

make all

export PKG_CONFIG_PATH=/path/to/liboqs/bindings/go/.config:$PKG_CONFIG_PATH

export DYLD_LIBRARY_PATH=/path/to/liboqs/build/lib:$DYLD_LIBRARY_PATH # macOS

export LD_LIBRARY_PATH=/path/to/liboqs/build/lib:$LD_LIBRARY_PATH # Linux

make geth

Transforms coefficients into NTT domain using liboqs.

**Input:**

**Output:** NTT-transformed coefficients (same format as input)

**Gas Cost:**

- Falcon-512: 500 gas (~9.4μs, 53 mgas/s)

- Falcon-1024: 1,080 gas (~20.4μs, 53 mgas/s)

- ML-DSA: 256 gas (~4.8μs, 53 mgas/s)

Transforms NTT domain coefficients back to standard representation.

**Input:** Same as NTT_FW (coefficients in NTT domain)

**Output:** Coefficients in standard representation

**Gas Cost:**

- Falcon-512: 500 gas (~9.4μs, 53 mgas/s)

- Falcon-1024: 1,080 gas (~20.3μs, 53 mgas/s)

- ML-DSA: 340 gas (~6.4μs, 53 mgas/s)

Element-wise modular multiplication in NTT domain.

**Input:**

**Output:** Element-wise product `(a[i] * b[i]) mod q`

**Gas Cost:** `ceil(0.32 × n)`

- Falcon-512: 164 gas (~2.9μs, 56 mgas/s)

- Falcon-1024: 328 gas (~6.0μs, 55 mgas/s)

- ML-DSA: 82 gas (~2.0μs, 42 mgas/s)

Element-wise modular addition.

**Input:** Same as VECMULMOD

**Output:** Element-wise sum `(a[i] + b[i]) mod q`

**Gas Cost:** `ceil(0.3 × n)`

- Falcon-512: 154 gas (~2.8μs, 55 mgas/s)

- Falcon-1024: 308 gas (~5.8μs, 53 mgas/s)

- ML-DSA: 77 gas (~1.6μs, 47 mgas/s)

cd core/vm

go test -v -run TestPrecompiled.*NTT

go test -v -run TestPrecompiledNTT_FW

go test -v -run TestPrecompiledNTT_VECMULMOD

go test -bench=BenchmarkPrecompiledNTT -benchtime=5s

**Test Coverage:**

- Scheme detection (Falcon-512/1024, ML-DSA)

- Input validation (malformed inputs, invalid parameters)

- Round-trip verification (`INTT(NTT(x)) = x`)

- Cross-scheme isolation

- Performance benchmarks with crypto standards

Benchmarks were run on an Intel(R) Xeon(R) CPU @ 2.20GHz. For detailed results, please see the files below:

- [Ecrecover Benchmark Test Results](./benchmark_results/BenchmarkPrecompiledEcrecover)

- [NTT & NTT Vector Operations Benchmark Test Results](./benchmark_results/BenchmarkPrecompiledNTT)

goos: linux

goarch: amd64

pkg: github.com/ethereum/go-ethereum/core/vm

cpu: Intel(R) Xeon(R) CPU @ 2.20GHz

BenchmarkPrecompiledEcrecover/-Gas=3000-4 65388 57182 ns/op 3000 gas/op 52.46 mgas/s 352 B/op 6 allocs/op

BenchmarkPrecompiledEcrecover/-Gas=3000-4 64994 55950 ns/op 3000 gas/op 53.61 mgas/s 352 B/op 6 allocs/op

BenchmarkPrecompiledEcrecover/-Gas=3000-4 61538 56411 ns/op 3000 gas/op 53.18 mgas/s 352 B/op 6 allocs/op

BenchmarkPrecompiledEcrecover/-Gas=3000-4 66052 55283 ns/op 3000 gas/op 54.26 mgas/s 352 B/op 6 allocs/op

BenchmarkPrecompiledEcrecover/-Gas=3000-4 65418 56104 ns/op 3000 gas/op 53.47 mgas/s 352 B/op 6 allocs/op

PASS

ok github.com/ethereum/go-ethereum/core/vm 21.021s