EIP-7619 Falcon-512 post-quantum signature verification precompile (Precompile Falcon512 generic verifier)

No call decision · Security & privacy · EIP status Draft · created 2023-07-03

Adds signature verification for the post-quantum signature algorithm Falcon-512 as a precompile (a built-in contract) at address 0x65. This makes post-quantum signature verification affordable, where it had previously been unusable in Solidity due to excessive gas cost.

Why it is needed

Today, Ethereum and most other blockchains use signatures based on elliptic curve cryptography (ECC). Once a sufficiently powerful quantum computer can run Shor's algorithm (a quantum algorithm that quickly finds the prime factors of an integer), widely used asymmetric cryptosystems such as RSA, (EC)DSA, and (EC)DH can be broken in a short amount of time. Blockchain ledgers carry hundreds of billions of dollars in cryptocurrency and digital assets along with thousands of applications, so a way to guarantee quantum resistance is needed. However, most existing proposals for quantum-resistant blockchains are either theoretical, require a large-scale quantum key distribution (QKD) network, or propose building an entirely new protocol from scratch. This proposal instead chose an approach compatible with today's EVM blockchains. The authors implemented Falcon-512 verification in Solidity, but it required too much gas to be scalable. This EIP therefore proposes adding it as a precompile.

What changes

Today

After EIP-7619

Who is affected

In depth

Precompile address and input encoding

The precompile operates at address 0x65 and uses a Falcon-512 implementation taken from the PQClean project. There are three inputs. public key is an 897-byte Falcon public key, signature is at most 666 bytes, and message is the arbitrary-length byte string that was signed. The encoding simply concatenates them in the order [pubkey:897 bytes][signature:666 bytes][message: remainder]. In Solidity this can be wrapped in a helper function that concatenates the three values with abi.encodePacked and makes a staticcall.

Output rule: revert occurs only on insufficient gas

If verification succeeds, it returns 0000000000000000000000000000000000000000000000000000000000000001; every other failure returns 0000000000000000000000000000000000000000000000000000000000000000. The only case in which the precompile reverts is insufficient gas. Malformed input data, wrong size, and invalid signatures are all handled by returning 0 rather than reverting. The original test examples illustrate this rule. Supplying empty input with 10 gas produces an out-of-gas error, and supplying garbled input with 1000000 gas returns 0.

Gas cost: base 1465, plus 6 per word

Since the input data size is variable, gas consists of two parts: a base of 1465 gas per call plus 6 gas per word in the payload. These values come from benchmarking. Assuming the ecRecover precompile's gas is priced correctly, the authors ran 5-second benchmarks on a 2.6GHz Intel Core i7-10750H 64-bit machine against 100 valid-signature test vectors (each vector 33 bytes larger than the last) and measured the average time per operation (ns/op). Fitting the 100 results to a linear equation over byte count yielded the conclusion of a base cost of 1465 gas plus 6 gas per word.

Why Falcon-512

Falcon-512 is a NIST (US National Institute of Standards and Technology) standardization candidate with security level I post-quantum resistance. Compared with other post-quantum signature algorithms, its relatively small key size was the reason for choosing it. Per the figures stated by the algorithm's authors: 897-byte public key, 666-byte signature, and 27933.0 verifications per second. Falcon uses shake256 internally, and running this algorithm at that layer in a Solidity implementation was impractical, making the precompile approach the best option given its relatively low gas cost. The original text notes that implementing signature verification alone already opens up broad use cases at the smart contract level, citing as an example combining Falcon-based authentication with account abstraction, where the account itself remains a smart contract.

Backwards compatibility and test vectors

The risk of breaking backwards compatibility is very small. It would only matter for contracts that rely on address 0x65 being empty, which is unlikely, and if a concrete case emerges, any other arbitrary address with negligible collision risk could be chosen instead. For test data, separate files provide a collection of valid-signature test vectors for benchmarking the new implementation and a collection of test vectors for verifying invalid-signature cases. On the security side, the original text states that because this proposal's scope is limited to the contract-level feature of signature verification, it does not introduce security issues.

Current status: Draft

This EIP was created on July 3, 2023 and its status is Draft. The specification, including the address, gas values, and input format, may change during discussion. There is no record of a core developer call that decided on fork inclusion.

Original EIP · ← EIPs