What we propose?
In this topic we bring a proposal to introduce a precompile to verify a generic postquantum Falcon-512 signature.
Why Falcon Signatures?
Falcon algorithm is a good postquantum candidate algorithm for ethereum because of the short size of the produced signature (~667 bytes) and public key (897 bytes).
The way we propose it allows to handle such signatures at a contract level so encapsulating the feature at the execution layer.
Additionally the benchmarks we performed (results are presented in the proposed EIP) shows the low consumption of gas (around 1465 as a base cost plus 6 gas per word in the message to sign. For instance to verify a message of 33 bytes the cost of verification in the precompile would cost 1663 units of gas).
The method doesnât replace secp256k1 elliptic curve but instead it is an option that can work together with such algorithm. For example a transaction is still signed following the ecdsa-secp256k1 signature algorithm while also embedding a falcon signature in a contract call for an additional authentication.
Falcon-512 could be a good fit with account abstractions (EIP-4337)
Why a precompiled contract for Falcon is a good option?
We implemented the falcon signature algorithm directly in solidity, which proved to be unfeasible due to the high consumption of gas (Implementation in solidity here)
Implementing the same feature in two clients Hyperledger Besu and Geth turned to be way cheaper, even less than ecrecover.
Additional References:
One of our initiatives using the proposed Falcon-512 precompiled Link
Hi @abcoathup the difference relies in the message size. Our proposed precompile doesnât limit the size of the message (in the other proposal the message is limited to 256 bits). For our proposal, a particular case is just setting a message of 32 bytes (e.g. a digest) but in other cases it is up to the contract layer decide the size of the message, for example a digest of 384 bits. Since message is dynamic the gas cost is dynamic as well. It was calculated by using a geth implementation and summarized results here that the base cost of executing a generic verification of a falcon signature is 1465 units of gas plus 6 units of gas per word of message.
Hi, this implementation is a straightforward translation of a C code, which doesnât exploit at all the finite field operations avalaible in solidity. As such it cannot be concluded at all that it shows the infeasibility of FALCON in solidity.
For instance :
function mq_add(uint32 x, uint32 y)
can trivially be replaced by a single addmod instruction, it is an emulation over a 32 bit architecture of a modular addition, same for sub
the use of a montgomery representation is totally useless as mulmod is only 3 gas cost, here it is several hundreds of gas per modular multiplication. Which is the critical part of the code (more than 90% is the computation overt the lattice).
Lattice computations require larger amount of space, but are faster than elliptic curve operations. (Look at bench here and there, falcon is faster than ECDSA). So it should be feasible to have implementation in the order of magnitude of emulated non native ecc (ed25519, secp256r1).
That being said, having a PQ precompile would be a good idea. We should wait for available implementations in devices (smartphones and PC), cause the process of standardization is still very wet.