AD - Quantum Resistance - On-Chain Verification of Post-Quantum Signatures

On-Chain Verification of Post-Quantum Signatures

When a writer node adds a post quantum signature to the meta-transaction and broadcasts it to the network, there must be a mechanism for the signature to be verified. In the regular Ethereum protocol, there is not explicit verification for any signature. In the Ethereum protocol, for a given ECDSA signature, an address is derived and used as the identity of the person willing to execute and pay for a blockchain operation. For the LACChain Besu Network, we have decided to implement a verification protocol based on the Onchain Permissioning feature, which is based on smart contracts. This feature enables each node to intercept every transaction and run different validations before incorporating them into their transaction pool and replicate them
to their peers.

Particularly, according to our protocol, nodes use the post quantum signature to verify the authenticity and integrity of the transaction. As the name of the feature implies, this is resolved by making a local call to a smart contract existing in the network, which receives several parameters (sender address, target address, transaction value, gas price, gas limit, payload). To our purpose, nodes check the “target address” and dissect the “payload”, as described below.

As previously discussed, we use a meta-transaction model for executing user requests. This means that there is a single-entry point for our network, which is the address of the Relay Hub contract where the meta-transaction is directed. Therefore, the first Permissioning check consists of verifying that the target address is the Relay Hub contract. Otherwise, nodes will reject the transaction.

Once the Relay Hub smart contract has been verified as the target of the transaction, each node extracts the original payload transaction, the writer node’s DID, and the Falcon-512 signature from the original transaction in order to verify the signature.

Additionally, a call to the DID Registry allows for retrieval of the public keys associated with it, including the post-quantum public key that should match the post-quantum signature. With this information, each node receiving a transaction from a peer takes the original transaction, the public key, and the signature, and verifies their consistency. If it is not consistent, they reject the transaction (i.e., they do not add it to their transaction pool, nor propagate it to other peers).

To summarize, the protocol we have designed consists of three steps:

Every node that receives a meta-transaction -from the node that created it or from another node that replicated it- checks the sender. This involves obtaining the DID from the meta-transaction and locally querying the DID Registry in order to resolve (i.e., obtain) its Ethereum keys (ECDSA). They then verify that the public key derived from the ECDSA signature of the meta-transaction has control over the node’s DID that generated it.
If Step 1 is successful, the node calls the DID Registry again and now resolves the post-quantum public key associated with the DID as well as the Ethereum public key verified in Step 1.
With the post-quantum public key resolved from the DID Registry in Step 2, the post-quantum signature, and the original transaction, each node then verifies the post-quantum algorithm. If the three previous steps are successfully completed, nodes add the meta-transaction to their transaction pool and replicate them onto other nodes so that the validators will receive them and add them into the next block.

As previously stated, we have chosen Falcon-512 as our post-quantum algorithm. There is not yet an ideal way of implementing the Falcon-512 verification required to accomplish the Step 3 of this verification process nor any other postquantum algorithm, in Ethereum-based networks. We have developed three alternative mechanisms and analyzed their pros and cons.

These three mechanisms are:

Implementing the verification code in Solidity.
Implementing solidity instruction in the Solc compiler and corresponding EVM opcode, written in Java (Besu is written in Java), that performs a call through JNI to a NIST-compliant and high performance native Liboqs library outside of the EVM virtualized environment.
Refactoring the EVM opcode Java from the EVM virtual machine into a pre-compiled contract (a EVM Java-code native smart contract) that performs the call through JNI to the NIST compliant, high performance native Liboqs library outside of the EVM virtualized environment.

We hope that in the not-so-distant future, we can use this effort in alignment with the upcoming protocol changes in the form ofthe Accounts Abstractions, which will allow us to replace ECC cryptography with new algorithms, including post-quantum.

Verification Code in Solidity

The natural execution environment for the blockchain is the Ethereum Virtual Machine; thus, in our first attempt, we implemented the verification code entirely in the Solidity language. We dissect the reference implementation in the following modules and discuss the implementation of the highlighted functions one by one.

Implementing the highlighted portions of Fig. 8 in Solidity allowed for on-chain signature verification. Upon the completion of the development process, we faced two major problems. The first problem was the code size. It exceeded the 24kb limit that Ethereum mainnet imposes. This limit could have been exceeded in LACChain because LACChain has different boundaries, but such large code sizes are not ideal. The second and more major problem was the execution cost. In Fig. 9, we present a chart with the execution cost of the verification of the known answer tests provided by the Falcon implementation. If we compare the average 500 million gas units for a single Falcon signature verification, with the current block limit of 12 million gas units in the Ethereum mainnet, we can conclude that this approach is completely impractical at this point.

Our implementation of post-quantum signatures using Solidity code is the first one that has been developed to our knowledge. The open-source code can be found here.

EVM virtual machine-based signature validation support

An EVM based approach requires modification of both the Solidity compiler (solc) and the Ethereum Virtual Machine (EVM) that underpins the Besu Hyperledger technology used by LACChain.

These changes are applicable across all Ethereum-based networks but require all participating nodes within the blockchain to utilize the updated solidity compiler and EVM. The Java Native Interface (JNI) is also required in addition to ensuring that compatible OpenQuantum Safe (an open-source venture) Liboqs libraries are installed. Performance is therefore limited only by the native liboqs library and the native node processing power.

The solidity modification is minor, and only requires adding an instruction token to the existing instruction list. The modification to the EVM is similarly minor and only requires adding a Java class to a Falcon Verify operation and registering the class with the operations available for that version of the EVM virtual machine. This implementation provides a simple Gas cost of 1. However, an extended example could be made to utilize the memory-block size cost calculation performed by SHA3.

The approach only uses one opcode from the 6000 opcodes limit call within the standard configuration of Ethereum. The real-world performance of the signature verification is as fast as the hardware can perform – aligning with the performance observed by the OpenQuantum Safe teams.

The utilization of the OpenQuantum Safe liboqs library ensures minimal operational delay or risk in maintaining updated quantum algorithms in line with NIST and the OpenSource Safe current standards. The Java class implemented for the EVM can also be extended beyond Falcon-512 and to allow Falcon-1024 or other signatures.

The EVM stack word width is 256bits, which naturally fits with the existing 256-bit hashes used in the classical encryption. However, post-quantum signatures with larger memory requirements will become less optimal unless the stack word width is increased at the cost of compatibility with previously operational blockchains. Finally, the POC EVM implementation utilizes Falcon-512, which minimizes this impact while also providing a security level that is in alignment with classical AES-256. Fig. 10 summarizes the interactions described in this subsection.

EVM pre-compiled-based signature validation support

The pre-compiled approach transplants the EVM falcon verify operation Java class into a EVM precompiled smart contract (a native Java compiled smart contract). This approach has two benefits that reduce operational impact:

No change to the Solidity compiler.
No change to the underlying EVM virtual machine.

This facilitates the distribution of the quantum signature verification separate from the compiler and EVM releases. The approach therefore brings all the benefits of the EVM opcode implementation but with less operational work. The JNI and Liboqs libraries are used identically, offering speed and ease of maintenance. It is also worth mentioning that given this verification is meant to be executed before a node joins the blockchain, it could easily be replaced in the future without affecting the consensus. It will only be necessary to modify the deployment scripts.

Implementing this solution in the LACChain Hyperledger Besu Network would require changes in the protocol with respect to other Ethereum networks, including the mainnet. This would be against our goal to preserve compatibility with the Ethereum community. Therefore, the ideal way to proceed with this third approach for the verification of Falcon signatures is submitting an EIP for the community to evaluate the incorporation of a pre-compiled smart contract into the Ethereum protocol, being this either the full Falcon verification algorithm or same detected bottlenecks from a gas consumption perspective.

Fig. 11 shows some advantages and disadvantages of Pure Solidity, EVM Opcode and precompiled contract.

Comparison between different solutions for verification of post-quantum signatures

The three alternatives that were designed and tested for the verification of post-quantum signatures are successful for verification but not ideal for a productive implementation if the Ethereum-based network implementing them is intended to remain fully compatible with the Ethereum mainnet. The Solidity native implementation is not scalable due to the amount of gas required for the execution of the code, although it does not require a modification of Besu or Ethereum. The modification of the Solidity compiler and the EVM, as well as the pre-compiled smart contract are computationally scalable. However, they require undesired modifications unless otherwise agreed upon by the entire Ethereum community, which is the goal we aim at to pursue in the next step of this pilot.

Additionally, the second and third solutionsuse the Java Virtual machine. However, unlike the Solidity native implementation, these two techniques are not impacted by EVM or JavaVM mathematical computational problems maintaining validity and security between releases. Instead, the pure C native method of Liboqs implements its own mathematical validity tests as part of the C build system. The result is that regardless of Java or EVM release, the verifying
Liboqs library remains mathematically valid (assuming no optimizations or changes that invalidate tests). This approach allows organizations to separate security requirements, offering more precise maintenance and governance. However, this approach would require extra security protocols with the additional overhead.

Check our terms and conditions, privacy policies, and cookies policy.