ETHFALCON

ETHFALCON gather experimentations around FALCON adaptations for the ETHEREUM ecosystem. Falcon signature scheme is a post-quantum digital signature algorithm. This repo provides:

• on-chain contracts for verification
• python signers and verification for testing (offchain and on-chain wrapping cast).
• c signers and verification for testing (based on the NIST reference implementation, with added functionalities).

This is an experimental work, not audited: DO NOT USE IN PRODUCTION, LOSS OF FUND WILL OCCUR.

SPECIFICATION

The repo implements several versions of FALCON:

• FALCON is the legacy NIST round3 compliant (tested against official KATS, just here).

• ETHFALCON is an EVM friendly version, security equivalent replacing SHAKE by keccak to reduce costs.

• EPERVIER is a 'FALCON with recovery' EVM version, enabling to mimic the ecrecover functionning (recover address from signature).

Detailed specification is provided in the EIP 8052 and here.

I/O Description

This section describes the mathematical encodings used in ZKNOX implementation and NIST.

Polynomials representations:

Expanded polynomials

Expanded polynomials are arrays sorted from lowest to highest degree, thus a polynomial $P=a_0+a_1X+...+a_{511}X^{511}$ is encoded as the array $$A=[a0, ..., a_{511}]$$

Compacted polynomials

Polynomials in FALCON512 are polynomial of degree 511 defined over $F_{12289}$. As such they are represented by packing 16 coefficients of 16 bits by word, thus a polynomial $P=a_0+a_1X+...+a_{511}X^{511}$ is encoded as the uin256 array $$A=[a0+2^{16}a_1+ ...+2^{16\times 15}a_{15}, ..., a_{240}+ ...+2^{16\times 15}a_{511}]$$

Conversion from and to compact/expanded polynomials are performed by _ZKNOX_NTT_Expand and _ZKNOX_NTT_Compact. On chain external functions use compacted representation to reduce call data cost.

NTT and standard representation

The NTT (frequency) domain is used to speed up polynomial multiplication. Switching to and from the NTT domain is performed using _ZKNOX_NTTFW and _ZKNOX_NTTINV. Those operation are the most expensive, thus the verification functions takes the public key in its NTT representation.

Compressed polynomials

Compressed polynomials uses a custom RLE encoding defined in Algorithm 17 of FALCON specification. Decompression of polynomials is performed by _ZKNOX_NTT_Decompress.

NIST KATS

NIST KAT are made of

 * the encoded public key:0x09+ public key compressed value
 * the signature bundled with the message. Format is:
 *   signature length     slen encoded on 2 bytes, big-endian
 *   nonce                40 bytes
 *   message              mlen bytes
 *   signature            slen bytes

Conversion from NIST KATS to ZKNOX encodings are performed by decompress_KAT.

INSTALLATION

The repo contains a solidity verifier and a python signer.

• Installation:

  make install

  (or make install_signer or make install_verifier)

• Tests:

  make test

  (or make test_signer or make test_verifier)

BENCHMARKS

The following benchmarks can be reproduced using

make bench

Function	Description	gas cost	Tests Status
ZKNOX_falcon.verify	NIST	3.9M	✅
ZKNOX_ethfalcon.verify	EVM Friendly	1.5 M	✅
ZKNOX_epervier.verify	Recover EVM friendly	1.6 M	✅

Experimental (branch exp/pq-verifier-gas, not on main)

Not reproducible with make bench on this branch — check out exp/pq-verifier-gas first. The branch also changes the build profile (solc 0.8.30, via-IR, optimizer_runs = 1000000), so its bytecode differs from main's for every contract.

Function	Description	gas cost	Tests Status
ZKNOX_falcon_fast.verify	NIST, SHAKE256 via an external Keccak-f[1600] helper	1.98M	✅
ZKNOX_falcon_turbo.verify	NIST, the above + a packed-SWAR NTT core	1.32M	✅
ZKNOX_falcon_fused.verify	NIST, the above + fused radix-8 NTT, Yul hash-to-point sampler, SWAR norms	0.73M	✅
ZKNOX_falcon8.verify	NIST, eight 32-bit lanes with Montgomery R = 2^16, norm folded into hash-to-point, resident SHAKE lanes, own Keccak-f[1600] helper	0.65M	✅

Exact figures on the NIST KAT vector (forge nightly c808c4cd, solc 0.8.30, via-IR, optimizer_runs = 1000000, evm cancun, helper cold): 1,975,365 / 1,315,117 / 726,912 / 650,345 gas, i.e. 5.99x from ZKNOX_falcon (3,910,833 on main). All four verifiers keep the verify(h, salt, s2, ntth) API of ZKNOX_falcon and are asserted against it (KAT, differential fuzz on both sides of the signature bound; 153 tests on the branch).

On ZKNOX_falcon8 the ten Keccak-f[1600] permutations of the hash-to-point are ~400k of the 650k: the arithmetic is at its floor (the eight-lane transform chain, forward + key product + inverse, is 160k; the Keccak-f body is at the minimum operation count of the permutation), so the next step is a precompile, not more Solidity.

The three NIST verifiers of the branch delegate the Keccak-f[1600] permutation to a helper contract bound by EXTCODEHASH, deployed once per chain (~4.3M gas) and shared. ZKNOX_falcon_fast, _turbo and _fused use the Fireblocks helper (MIT, vendored from fireblocks-labs/evm-ml-dsa-verifier, test/f1600_170.hex); ZKNOX_falcon8 uses our own (test/f1600_zknox.hex, generated by pythonref/gen_keccak_helper.py, 39,974 gas per permutation against 40,448, checked against the Fireblocks helper on both of its interfaces and against a Python reference on a gas-counting mini-EVM). See DECISIONS.md (ADR-001 to ADR-006) and VERSION.md on the branch for the measurements, the bounds and what was tried and rejected. ZKNOX_falcon8 runs at 18,807 bytes of runtime.

More benchmark details for both solidity code and python available here. Those are measured on compacted polynomial representation. For decompressed/kats, add 900K to benchmarks.

EXAMPLE

Use the following commands to generate, sign a message and verify it with the onchain contract

# generate public and private keys using 'falcon', 'ethfalcon' or 'epervier'
./sign_cli.py genkeys --version='falcon'
# generate a signature
./sign_cli.py sign --privkey='private_key.pem' --data=546869732069732061207472616e73616374696f6e
# verify onchain the  signature using address of contract specified below (ensure --version is compliant with address)
./sign_cli.py verifyonchain --pubkey='public_key.pem' --data=546869732069732061207472616e73616374696f6e --signature='sig' --contractaddress='0xD088Ede58BD1736477d66d114D842bDE279A41Fa' --rpc='https://sepolia.optimism.io'w

The contract address refers to the contract implementing FALCON in Solidity. This should output:

0x0000000000000000000000000000000000000000000000000000000000000001

More details here.

https://ethresear.ch/t/lattice-based-signature-aggregation/22282 leanEthereum/leanSpec#9 https://github.com/leanEthereum/leanMultisig/tree/main/crates/leanVm

DEPLOYMENTS

Contract deployments are provided in kohaku project.

7702 DELEGATION

Before Native Account Abstraction is pushed, a demonstration of how to integrate FALCON in a 7702 delegation is provided in ZKNOX_IVerifierDelegate_7702.t.sol.

One of Kohaku goals is to integrate these contracts in a 4337 account.

CONCLUSION

This repo provides a highly optimized version of FALCON. Order of magnitudes were gained compared to other implementations. In our search, we also devise a way to implement falcon with recovery without requiring the inverse NTT transformation (only forward). Despite those efforts, it does not seem plausible to reach operational (below 1M) verification cost. Nevertheless, the provided code allow Account Abtraction using 7702 or 4337 from today. The architecture also demonstrates that providing NTT would allow an acceptable cost, and provide more genericity and agility in the PQ signature candidate of Ethereum. For this reason NTT-EIP is submitted.

REFERENCES

• [EXTCODE COPY TRICK] section 3.3
• [FALCON] Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU
• [NTT-EIP] NTT-EIP as a building block for FALCON, DILITHIUM and Stark verifiers
• [Tetration] Falcon solidity.