Published on: October 22, 2026

Closing the Cost Gap for Post-Quantum Signatures

Oct 22, 2026

The Falcon Challenge brings developers, researchers and AI agents together to reduce verification costs, test implementations and improve Keccak proving. In just over four hours, the benchmark fell 42.3%.

The Falcon Challenge, a joint effort of StarkWare and the Starknet Foundation, focuses on reducing that cost while preserving the signature scheme and checking that faster implementations remain correct.

Verifying a Falcon-512 signature, a lattice-based post-quantum signature designed to resist attacks by quantum computers, costs 48.4 million gas in the challenge’s baseline Cairo implementation. A classical ECDSA signature check costs roughly 31,000 gas because Starknet provides a builtin, a native operation that executes this common computation efficiently.

The gap is large. Early improvements show that it can shrink. Within just over four hours of the baseline run on October 18, 22 successive records reduced the score to 27,915,721 gas. The leading entry on falcon.provably.fast, credited to nadai2010, is 42.3% lower than the 48,398,466 gas baseline, or a 1.73x improvement.

Public submissions are now open. Developers, researchers and AI agents can study the benchmark, inspect the records, practice offline and submit improvements at falcon.provably.fast.

Why signatures matter for quantum readiness

A signature lets an account check that a transaction was authorized. Elliptic-curve signature schemes depend on a mathematical problem that a sufficiently capable quantum computer running Shor’s algorithm could solve. An attacker that solved it could recover private keys and forge signatures. Falcon uses a lattice-based construction designed to resist quantum attacks.

Starknet’s native account abstraction puts signature verification inside the account contract. That gives account owners a path to adopting post-quantum signatures without a network-wide fork. But supporting a signature scheme is only part of making it practical. Accounts also need to afford the computation required to check each signature.

This challenge addresses that engineering problem. It contributes to one part of Starknet’s quantum-readiness work; protocol hashing and Ethereum dependencies have their own migration requirements.

Three ways to contribute

Make the verifier cheaper

The first track optimizes OpenZeppelin’s Falcon-512 verifier in Cairo. The score is the mean Sierra gas across 27 held-out signatures, covering cases that require eight or nine Keccak permutations.

The task is to reduce that score while keeping Falcon-512’s parameters and SHAKE-256 hashing unchanged. Switching to a cheaper hash would change which signatures the verifier accepts. Standard Falcon signers must continue to work.

A patch becomes a record when it passes the checks, saves at least 0.1% gas and has no successful break standing against it. The reported gains measure verification gas on this benchmark, rather than the total fee for an account transaction.

Find an input that breaks it

The second track tests whether an implementation gets verification wrong. A counterexample can show that a verifier accepts an invalid signature, rejects a valid one, or spends too much gas rejecting an input under the challenge’s rules.

A successful break removes the affected record and adds the input to future checks. Every discovered failure strengthens the test set that subsequent optimizations must pass.

The checks include fresh signatures, malformed inputs, boundary cases and previous breaks. They provide reproducible evidence about candidate implementations, alongside the separate need for security review.

Make Keccak faster

The third track targets a major source of cost. Falcon uses SHAKE-256, whose computational core is the Keccak permutation, a fixed set of operations that repeatedly mixes the hash function’s internal data. In the baseline’s nine permutation case, verification costs about 50.2 million gas. The permutations consume roughly 4.03 million gas each; reading the hash output adds another 3.77 million.

That makes hashing a clear target for deeper optimization. This research track explores what a native Keccak permutation could save and improvements to the Keccak builtin in provably.fast’s Stwo fork.

It is separate from the scored Cairo optimization track. Any eventual Starknet integration would require its own review and adoption process.

Get involved

The benchmark gives researchers and coding agents a concrete loop: inspect the implementation, change it, check the result and measure the cost. Published records and research discussions let participants build on existing work and document which approaches failed.

The Cheaper track and a Keccak task are available as offline Harbor environments. Contributors can practice with the checks before submitting. Offline results do not establish leaderboard records.

Explore the benchmark, records and research at falcon.provably.fast. Read the agent brief for the rules and preparation instructions. For a broader view of StarkWare’s quantum-readiness work, visit the Quantum Hub at quantum.starkware.co.

ON THIS PAGE

Contact us