Falcon Post-Quantum Signature Scheme Proposal

[Giulio Golinelli]

Hi everyone,

I am to share a technical demonstration and benchmarking project that integrates the Falcon post-quantum signature scheme (Falcon-512) into Bitcoin Core, implemented as a soft-fork within the classic P2WPKH mode. This work aims to provide a practical reference for possible future Falcon adoption, especially as it approaches FIPS standardization.
You can find details at this fork.

Why Falcon?

Falcon is a lattice-based, post-quantum digital signature scheme designed to be secure against quantum attacks. Unlike other PQC candidates such as SPHINCS+ and ML-DSA, Falcon offers significantly smaller signature and public key sizes, as well as efficient signing and verification times. It is implemented in pure C and does not require external dependencies.

Benchmarking & Results
Aspect                           Falcon    ECDSA
Public Key Size (B) 897         33
Signature Size (B) 655         71
Verification Time (μs) 57         120

Verification time is more critical than signature creation time in Bitcoin, since signature creation is performed by clients (wallets), while nodes focus on verification.

Integration

• Falcon was included into the codebase from the original GitHub repository.
• The build system (CMakeLists.txt) was updated to support Falcon.
• Falcon verification has been soft-fork enabled via a new script verification flag.

Next Steps & Reference
This project serves as a practical demonstration of Falcon’s promising performance, highlighting its advantages over currently selected post-quantum signature algorithms such as SPHINCS+ and ML-DSA, which face significant time and space limitations. As Falcon approaches FIPS standardization, this work aims to provide a reference for future adoption and integration in Bitcoin.

Let me know what you think and if this could be of interest for which case I can complement the project by integrating Falcon into all the other spending paths. I also look forward to development/integration corrections.

Best regards,
Giulio

[waxwing/ AdamISZ]

Thanks for the report!

Forgive the rather ignorant question here, but:

Given the obvious that we have a problem with size on-chain (and I'm aware you've focused here specifically on the most plausible scheme that has the least ridiculously large size, and yet it's still 20x larger), has there been comparison of the possibility of batched signing (not batched *verification*, but signing) in different PQ schemes, with a view to a CISA like approach to transactions in a future with much larger keys and sigs? A nice side effect might be a pure economic motivation for much better fungibility (coinjoin becoming much more desirable for the base layer, albeit I think it's in higher layers where we are/will be get(ting) most privacy).

A cursory search tells me that Falcon specifically can't support any kind of batched signing, but I have no idea whether that's correct.

Cheers,

AdamISZ/waxwing

[conduition]

Falcon (FN-DSA) relies on discrete gaussian sampling using constant-time floating point arithmetic for signers, which is very hard to implement quickly and in constant time (securely). Despite being significantly harder to implement than ML-DSA, it only provides a mild (factor of two or so) improvement in signature + pubkey size. This is why we're probably not including FN-DSA in our PQ signature opcode BIP following BIP360.

https://blog.cloudflare.com/nist-post-quantum-surprise/#floating-points-falcons-achilles

While I wouldn't rule out Falcon permanently, I personally feel more research is needed to explore Falcon, its weaknesses, and how flexibly it can be adapted to schemes like CISA, BIP32, and multisignatures. Let it bake a little longer.

If small signatures are your goal, then I'd look into SQIsign, which uses isogeny-based cryptography to produce very small sigs (148b) and pubkeys (65b) using some convoluted mathematical tricks. However, much like Falcon, it is still immature and needs more researchers to optimize its verification, explore its strengths, and attack its weaknesses. 

If you want a PQC scheme that's ready today and also provides small signatures, I'll point you to XMSS, and Jonas Nick's SHRINCS proposal. You can configure an unbalanced XMSS tree to get 272 byte signatures, potentially smaller if you crank up the parameters. The catch is a dependence on statefulness. 

regards,

conduition

--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/16e01530-e9dd-481f-8c7f-ca9ccafcfcden%40googlegroups.com.

[Giulio Golinelli]

Hi Adam,

thanks a lot for the thoughtful question — it’s definitely not ignorant at all, and it touches one of the core reasons Schnorr ended up being such a good fit for Bitcoin.

What you’re referring to is technically called signature aggregation, which is distinct from batch verification. Signature aggregation relies on a linear homomorphic algebraic structure that is inherent to Schnorr signatures, and it’s precisely this property that enables constructions like MuSig. Unfortunately, this kind of structure is not something we get across the post-quantum signature landscape (whether standardized or exotic schemes).

L2 ZK rollups can mitigate this by verifying many user signatures off-chain and proving the resulting state transition with a single succinct proof, effectively collapsing many verifications into one on L1. In a post-quantum setting, LaBRADOR ([https://eprint.iacr.org/2022/1341.pdf](https://eprint.iacr.org/2022/1341.pdf)), a lattice-based SNARK could be adopted. Bitcoin-oriented ZK rollups along these lines, such as Citrea, already explore this approach.

My current view is that L2 ZK constructions may be a key part of the toolbox to mitigate the absence of aggregation and efficient batching — at least until we discover a PQ signature scheme with Schnorr-like advantages. Considering it took roughly 30 years from RSA to reach Schnorr, we should expect that fully realizing such a post-quantum analogue will likely take several years of research and development.

Very happy to hear your thoughts on this, and thanks again for raising the point. I’m still relatively new to Bitcoin, so if I’ve made any incorrect assumptions here, please feel free to correct me.

Best regards,

Giulio

--
You received this message because you are subscribed to a topic in the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/bitcoindev/PsClmK4Em1E/unsubscribe.
To unsubscribe from this group and all its topics, send an email to bitcoindev+...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/e7977710-22ca-477c-b8cd-0933f41ff398n%40googlegroups.com.

[Giulio Golinelli]

Falcon (FN-DSA) relies on discrete gaussian sampling using constant-time floating point arithmetic for signers, which is very hard to implement quickly and in constant time (securely).

This is true for the first Falcon version published (randomized mode of operation). This implementation uses the author-recommended deterministic Falcon mode (see author’s notes) which uses software floating-point emulation . This eliminates side-channel risks associated with non-constant-time hardware FPUs. It is also SNARK-friendly and overcomes portability limitation. While this sacrifices the performance optimizations of true FPUs, signing speed is not critical in Bitcoin, where verification dominates node activity.

If small signatures are your goal, then I'd look into SQIsign

This would be good like many other PQ exotic schemes but all of these are far from being standardized soon.

If you want a PQC scheme that's ready today and also provides small signatures, I'll point you to XMSS, and Jonas Nick's SHRINCS proposal. You can configure an unbalanced XMSS tree to get 272 byte signatures, potentially smaller if you crank up the parameters. The catch is a dependence on statefulness. 

SPHINCS+ cannot be considered a valid fallback as it introduces large signature overhead (it's not meant for bitcoin-like use-cases). Any TPM-based state management would reduce performance and compatibility across architectures. The hash-based nature of SHRINCS is highly SNARK-unfriendly, making them incompatible with emerging L2 ZK rollup constructions. Moreover in high-throughput L2 environments, state management, limits on the number of signatures and performance degradation proportional to published signatures are critical bottlenecks.

[Mikhail Kudinov]

Hi everyone,
I am happy that the discussion on the PQ topic is active. I wanted to add my view on the raised issues. 

For the fallback in SHRINCS, one option is to use SPHINCS+ as a fallback with a limited number of signatures. By setting an upper bound as large as 2^30 or 2^40, the signature size can be significantly reduced, and the scheme would only be invoked in exceptional circumstances. In most realistic scenarios, the fallback would consist of generating a single signature to move assets to a new address. As for the statefulness problems, I agree that this is an important drawback that we should keep in mind.

The SHA-based SPHINCS+ is indeed not particularly efficient in SNARK settings. But one could replace the hash functions with SNARK-friendly alternatives (for example, Poseidon) in the future, which will make it much, much more efficient.

It is also a question: how much weight should we put on adopting an explicitly SNARK-friendly signature scheme? While such compatibility is clearly advantageous, it does not seem to me to be a decisive point on its own. What would you say?
I am also unsure to what extent Falcon can be considered SNARK-friendly. Has there been any research in this direction, or are there benchmarks evaluating its performance in SNARK environments?

Finally, regarding SQIsign: although the signature sizes are remarkable, I agree that we need more time for the scheme to mature before considering adoption.

Best,
Mike

--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/2e4abb5a847ab9d78857aee2fded500a234f68a6.camel%40gmail.com.