Abstract
Include a precompiled signature verification function using Falcon-512. Falcon-512 is a candidate for standardization by the National Institute of Standards and Technology (NIST) and is quantum resistant with security level I.
Motivation
The advent of quantum computing threatens blockchain protocols and networks because they utilize non-quantum resistant cryptographic algorithms. When quantum computers become robust enough to run Shor’s algorithm (a quantum algorithm to find the prime factors of an integer) on a large scale, the most used asymmetric algorithms, utilized for digital signatures and message encryption, such as RSA, (EC)DSA, and (EC)DH, will be no longer secure. Quantum computers will be able to break them within a short period of time. Today, there are hundreds of billions of dollars denominated in cryptocurrencies and other digital assets that rely on blockchain ledgers as well as thousands of blockchain-based applications storing value in blockchain networks. Cryptocurrencies and blockchain-based applications require solutions that guarantee quantum resistance in order to preserve the integrity of data and assets in these public and immutable ledgers. Most proposals for quantum-resistant blockchain networks are theoretical, require large QKD (quantum key distribution, a secure communication method that implements a cryptographic protocol involving components of quantum mechanics) networks, or propose new quantum-resistant blockchain protocols to be built from scratch. This EIP is pioneer in proposing a solution compatible with current EVM blockchain protocols. It presents a simple mechanism to add a NIST-compliant post-quantum signature to blockchain transactions, making them quantum-resistant even when ECC (elliptic curve cryptography) cryptography becomes vulnerable against attacks by quantum computers. We have developed a Solidity implementation for the on-chain verification of this signatures, which does not scale due to the required high amount of gas. This is why this EIP is proposing a pre-compiled smart contract that allows to verify post-quantum signatures in a scalable manner.
Specification
A clean implementation for Falcon-512 algorithm was brought from the PQClean project.
The precompiled signature verification function runs at address 0x65. The required inputs are:
public key - Falcon Public key of 897 bytessignature - 666 bytes (max size)message - an arbitrary number of bytes representing the message that was signed
Those inputs are encoded according to:
[pubkey:897 bytes][signature:666 bytes][message: remainder]
Output is:
result -
A successful signature verification returns 0000000000000000000000000000000000000000000000000000000000000001, otherwise 0000000000000000000000000000000000000000000000000000000000000000 indicating all other failure cases where sufficient gas has been provided.
The precompile will only revert in the case where insufficient gas has been provided. Data format errors, size errors, and invalid signatures will not cause the precompile to revert.
{
Input: "",
Gas: 10,
ExpectedError: "out of gas",
Name: "empty input, too little gas",
},
{
Input: "111111110000000000000000000000000000000000000000000000000000000000000060000000000000000000000000000000000000000000000000000000000000032000000000000000000000000000000000000000000000000000000000000006e0",
Gas: 1000000,
Result: "000000000000000000000000000000000000000000000000000000000000000000000000",
Name: "garbled input",
}
Example Usage in Solidity
The precompile can be wrapped in Solidity to provide a more development-friendly interface to Falcon-512 signature verification.
function verify(
bytes calldata publicKey,
bytes calldata signature,
bytes calldata message
) public returns (bool isValid) {
(bool success, bytes memory verifies) = address(0x0000000000000000000000000000000000000065)
.staticcall(
abi.encodePacked(
publicKey,
signature,
message
)
);
require(success && verifies.length == 32, "Invalid signature");
return verifies[31] == 1;
}
Gas costs
Since data size is variable, each operation to execute the precompiled call will require:
- 1465 base units of gas for each operation.
- 6 units of gas for each word contained in the payload.
These values are based on results presented at the benchmarks section.
Rationale
Falcon-512 is a good candidate for a new signature implementation. Key sizes in Falcon-512 are relatively small compared to other post-quantum signature algorithms.
The following table shows a summary of the typical values for keys and the approximate amount of time taken per second to execute signature verifications as specified by the authors of Falcon algorithm:
| variant |
verify/s |
pub size(bytes) |
sig size(bytes) |
| Falcon512 |
27933.0 |
897 |
666 |
Falcon uses shake256 under the hood, an implementation made in solidity showed it is not viable to implement this algorithm at that layer, on the other hand the implementation of falcon-512 by using precompiles turned to be the best approach since the gas cost (as shown in the previous section) is relatively low.
Implementing just the signature verification is sufficiently enough to open a wide range of use cases at the smart contract level. To give an example, this method can perfectly work with the Account Abstraction concept, where the authentication process would rely on Falcon and the account is a smart contract.
benchmarks
Assuming ecRecover precompile is perfectly priced, a set of benchmarks were executed comparing Falcon-512 signature verification function precompile with ecRecover precompile. For benchmarks, it was used 2.6 GHz Intel Core i7 64-bit machine.
$ cat /proc/cpuinfo | grep "model name"
Intel(R) Core(TM) i7-10750H CPU @ 2.60GHz
5 seconds benchmark
Based on 100 test vectors with valid signatures a benchmark of 5 seconds, for each test vector, was performed, considering the following:
- the average time per operation (ns/op),
- each vector size increases in 33 bytes
- Ecrecover is well tested
Benchmark results here
Then the 100 BenchmarkPrecompiledFalcon512 results were approximated to a linear equation dependent on the number of bytes in each test vector. From the approximation it was concluded that 1465 units of gas is the base requirement for any falcon-512 signature validation and 6 gas per word is additionally required.
Backwards Compatibility
There is very little risk of breaking backwards-compatibility with this EIP, the sole issue being if someone were to build a contract relying on the address at 0x65 being empty. The likelihood of this is low, and should specific instances arise, the address could be chosen to be any arbitrary value with negligible risk of collision.
Test Cases
A set of test vectors, with valid signatures, for benchmarking on new implementations is located in a separate file
A set of test vectors, with invalid data, to verify some invalid signature cases is located in a separate file
Security Considerations
Since the scope of this proposal is encapsulated at the contract level for verifying signatures it doesn't represent issues in regards to security.
Copyright
Copyright and related rights waived via CC0.
