A significant stride has been taken towards making Ethereum quantum-safe as we integrate the first successful STARK-based verification of post-quantum digital signatures on Starknet, a zero-knowledge layer-2 scaling solution on Ethereum. This achievement marks the first step in supporting NIST standardized post-quantum digital signature algorithms on Ethereum and replacing vulnerable cryptographic primitives with quantum-safe algorithms.

This achievement comes at the same time as major US government organizations releasing resources for the migration to post-quantum cryptography. Last week, the Cybersecurity and Infrastructure Security Agency (CISA), the National Security Agency (NSA), and the National Institute of Standards and Technology (NIST) jointly developed a factsheet on the implications of quantum capabilities. ISA, NSA, and NIST are advising organizations to start developing quantum-readiness roadmaps, with an urgency coming from the potential of cyber threats targeting current data that may need long-term protection, such as a "harvest now, break later" strategy by attackers. Cryptographic algorithms used in Ethereum today such as ECDSA, will have to be updated or replaced with quantum-resistant algorithms to combat this anticipated threat.

One replacement for ECDSA in Ethereum is Falcon, or Fast-Fourier Lattice-based Compact Signatures over NTRU. Falcon is a digital signature algorithm based on the NTRU assumption, which relies on the hardness of the Learning with Errors (LWE) problem and is understood to offer protection against quantum attacks. It is one of the algorithms NIST announced it will standardize in 2024. Beyond its security advantages, Falcon signatures stand out for their efficiency, boasting a signature size that is competitive with other standardized post-quantum signature schemes. Furthermore, Falcon emphasizes compactness, offering a notably succinct public key that facilitates easy transmission and verification.

In the world of Ethereum, it's become clear that blockspace is precious. Even the more compact ECDSA signatures, which occupy a footprint nearly ten times smaller than Falcon signatures, are being optimized further by layer-2 solutions to enhance transaction speeds and reduce associated gas fees. This motivated us to develop a STARK for Falcon signature verification, allowing us to benefit from Falcon's security features while maintaining the efficiency that Ethereum demands. By using a STARK, we can roll up the verification of several thousands of Falcon signatures in a proof and post the results on-chain. This STARK implementation is based on our prior work on quantum-safe signature aggregation using PQScale, one of our core technologies at BTQ. PQScale aggregates Falcon signatures using the quantum-resistant AURORA proving system, achieving a space savings of 12.5x. This brings the per-signature cost of Falcon to below the cost of ECDSA.

Looking ahead there are several key areas that capture our interest. First, we'd like to use a recursive proving scheme that maintains proof size within a comparable range to single signature verification. This will ensure that aggregating a high volume of signatures doesn't lead to substantial increases in proof size. Additionally, we're looking to leverage signature abstraction through the account abstraction model proposed in EIP-4337. Through account abstraction, smart contract accounts can be designated to sign and verify Falcon signatures in place of ECDSA within the account's contract code. This makes it easier for applications and users to start using Falcon, or other post-quantum signature schemes, without waiting for the entire Ethereum network to adopt a new signature. Starkware natively supports account abstraction, wherein all accounts are realized as smart contracts. Relevant documentation for the account contract interface can be found here.

We'd like to thank Eli and the Starkware team for helping us realize this milestone. We're extremely exited to advance further on our roadmap, especially as we delve into the recursive proving scheme and the nuances of account abstraction. Together, we can continue to push the boundaries and shape the future of Ethereum. We'd also like to thank feltroid prime for his contributions to the Cairo development and consultation throughout the project.