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
- Ethereum signatures are based on elliptic curve cryptography and are not secure against a powerful quantum computer
- Implementing Falcon-512 verification in Solidity costs too much gas to be practically usable
- Most quantum-resistant blockchain proposals are either theoretical or assume an entirely new chain
After EIP-7619
- Calling the precompile at address 0x65 allows Falcon-512 signatures to be verified at low gas cost
- Can be used by applications where a smart contract authenticates with a post-quantum signature, for example in authenticating an account-abstraction account
- Adds post-quantum resistance based on a NIST standardization candidate algorithm without changing existing EVM chains
Who is affected
- Wallet & app developers: Contracts will be able to call Falcon-512 signature verification. The original cites, as an example use case, combining this with the account abstraction concept to let a smart contract account's authentication rely on Falcon.
- Client teams: A new precompile must be implemented at address 0x65. The original's implementation is adapted from the PQClean project's Falcon-512 implementation.
- Users: This provides a signature scheme option that can protect assets and data even if elliptic curve cryptography becomes vulnerable to quantum computers.
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.