How Can Bitcoin Resist Quantum Computers? A Comparison of Three Lattice-Based Signature Schemes

Original author: Blockstream Team

Original compilation: Saoirse, Foresight News

Blockstream Research has released a comprehensive research report on lattice-based signatures for Bitcoin. This article summarizes the research content, key findings, and related recommendations. The full report can be accessed here.

Digital signatures are the core mechanism for authorizing Bitcoin transactions, and the Schnorr and ECDSA signatures currently used for this purpose are extremely low-cost. In 1994, Shor proved that a sufficiently powerful quantum computer could break both types of signatures. While there is ongoing debate about when such machines will become available, we need to develop a viable post-quantum signature deployment plan before the problem actually arrives.

Lattice-based signature schemes are a popular candidate to replace existing signatures. Lattice cryptography has a research history of over a century, and its cryptographic applications have been developed for nearly three decades. In post-quantum cryptography, lattice-based signatures offer several advantages: the total size of public keys and signatures can be as low as under 1.6 kilobytes, and their algebraic structure holds promise for supporting multisignatures, threshold signatures, and succinct proofs in the future.

This report studies three schemes: Dilithium, Falcon, and Hawk. For readers unfamiliar with lattice cryptography, we explain the design rationale of each scheme, provide a complete description of the algorithm flow, and analyze them from dimensions such as security, performance, and practical deployment (e.g., wallet key derivation). Among the three, which schemes can actually be deployed on the Bitcoin blockchain?

Evaluation Criteria

Bitcoin has its own constraints on signature scheme selection, and this evaluation focuses on four core criteria:

• On-chain cost: One of the most important metrics is the total size of public keys and signatures. When an output is spent, both the public key and signature are recorded on-chain, and full nodes need to download and store every byte. Verification overhead is equally critical: every signature is verified by all nodes in the network, and slow verification would burden the entire network.
• Implementation complexity: Whether the scheme can be implemented securely is crucial. If the design requires floating-point arithmetic or delicate Gaussian sampling, an implementation error or a side-channel attack such as timing analysis could leak the key. To achieve a smooth migration, implementation complexity is a factor that cannot be ignored.
• Deployment risk: When actually integrating into Bitcoin, there are various practical obstacles: the choice of hash function at the consensus level (most candidates use SHAKE, while Bitcoin uses SHA-256), the reproducibility of signature results across platforms, and whether the signing procedure fits the memory constraints of hardware wallets.
• Development potential: The vast majority of Bitcoin wallets use the BIP-32 hierarchical deterministic mechanism: from a single master public key, an infinite number of child public keys can be derived without access to the private key. Currently, no standardized post-quantum signature scheme natively supports this feature, so we study the cost of adding this capability; we also examine various non-standard scheme variants that might offer additional benefits.

What Security Level Should Be Chosen?

Before comparing sizes, we must first determine the target security level, and this choice is not as straightforward as it seems. NIST classifies security levels from 1 to 5; higher levels provide stronger security but also larger key and signature sizes.

We believe Bitcoin should adopt at least security level 3. Bitcoin outputs may remain unspent for decades, and if advances in cryptanalysis reduce the actual security level of the scheme, assets would be locked by weakened keys and exposed to long-term risk. Lattice-based assumptions have already withstood nearly three decades of public cryptanalysis, longer than the research foundation when Bitcoin adopted elliptic curves. However, the complex algebraic structure of lattice cryptography still leaves many avenues for future attacks, and we should not bet all our long-term security on it.

Major mainstream products have made the same judgment. Apple's iMessage PQ3 protocol directly discards level 1 lattice parameters and uses level 3 and level 5 parameters throughout; Cloudflare uses ML-KEM-768 (level 3) in its post-quantum TLS deployment, stating that while level 1 currently appears secure, it is necessary to reserve a security margin for decades of future cryptanalysis. Bitcoin's security time horizon is even longer than both.

Raising the security level comes at a cost. For example, moving Dilithium from level 2 to level 3 increases the total size by about 1.5 kilobytes. The report compares parameter sets at all security levels, allowing readers to weigh the trade-offs themselves. The case of Hawk proves that conservative security considerations are not merely theoretical.

Detailed Analysis of Candidate Schemes

Dilithium: A Simple Design

Dilithium, standardized by NIST as ML-DSA in FIPS 204, migrates the commitment-challenge-response paradigm of Schnorr signatures to module lattice arithmetic.

Its greatest feature is simplicity. All operations in Dilithium are integer operations: ring operations, matrix-vector multiplication, hashing, and rounding. There is no floating-point arithmetic and no discrete Gaussian sampling. It is easier to write secure, constant-time implementations. It is also the most widely deployed candidate, already integrated into OpenSSL, BoringSSL, AWS-LC, and Apple CryptoKit.

The trade-off is larger size. At security level 3, ML-DSA-65 has a public key of 1952 bytes and a signature of 3309 bytes, totaling 5261 bytes, about 55 times the total size of Bitcoin's native public/private key plus signature, making it the largest of the three schemes at the same security level.

For Bitcoin, the most valuable aspect of Dilithium is that it is the only one of the three that comes close to implementing BIP-32-style key derivation. The re-randomizable key construction DilithiumRK can generate child keys from parent keys using only public information. The report analyzes three variants, including our proposed DilithiumRKS, where the derivation logic is entirely within wallet software and the chain only requires a standard verifier to process ordinary ML-DSA signatures. However, none of the three are ready for production: two variants require modifications to the verifier, and DilithiumRKS itself lacks a complete unforgeability proof; all schemes rely on a network-wide shared matrix, which is formally secure under the Module-LWE assumption but binds the security of all keys to a single instance. We believe that public key derivation based on Dilithium is currently only a proof of concept and cannot be deployed in practice.

Falcon: A Compact Scheme

Falcon, selected by NIST and standardized as FN-DSA, is the most compact of the three. At security level 1, Falcon-512 has a combined public key and signature size of 1563 bytes; at level 5, Falcon-1024 totals 3073 bytes. Falcon-1024, with a higher security margin, is even smaller than level 3 Dilithium.

Falcon takes a different approach from Dilithium: a hash-and-sign paradigm based on NTRU lattices. The signer's private key is a short basis of the lattice; the message is hashed to a point in space, and the signer uses the short basis to find a lattice vector close to that point. The point and the nearby vector together form the signature; verification only checks that the vector belongs to the lattice and is sufficiently close. The implementation challenge is to find the vector without leaking information about the basis. Early schemes GGH and NTRUSign directly selected nearby lattice points, leaking some geometric information with each signature. Falcon adopts the GPV framework, sampling nearby vectors from a Gaussian distribution, which provably makes the sampled output independent of the basis, eliminating the leakage risk, but the implementation difficulty of the sampler increases significantly.

The sampler is the engineering weakness of Falcon. It operates in the complex Fourier domain and requires floating-point computation. Different processors, compilers, and compilation optimization options can cause inconsistent floating-point results. This is not just a compatibility issue but also a security concern: the GPV security proof requires that the signer never outputs two different short vectors for the same digest; if the signature becomes deterministic, platform-induced floating-point rounding differences would violate this condition. There is a viable solution: deterministic Falcon can replace hardware floating-point with integer emulation, producing identical signatures on all platforms. The cost is a roughly 15-fold slowdown in signing speed and about a 2-fold slowdown in key generation.

Importantly, verification is unaffected: Falcon verification is entirely integer-based, deterministic, and also the fastest among the candidates. This asymmetric property is very friendly to Bitcoin: signing is performed once by the wallet when spending a transaction, while every signature is verified by all full nodes in the network. A 15-fold slowdown in signing is a low-frequency cost, and in exchange we get cross-platform reproducibility and integer arithmetic, which we consider a reasonable trade-off. Therefore, the floating-point issue is an obstacle that can be solved through engineering means, not a fatal flaw.

Two points to note: due to structural constraints, Falcon has no level 3 parameters; one must choose either level 1 or level 5. Based on security margin considerations, we recommend Falcon-1024. Second, signing consumes a large amount of memory: the sampler for the 1024 parameter set relies on a precomputed tree, occupying about 90 kilobytes of memory. Hardware wallets can dynamically rebuild the tree branch by branch, reducing memory usage to 16 kilobytes, but signing time doubles. Slower signing on hardware devices is a real cost, but still acceptable.

Hawk: A Failed Scheme

Hawk aimed to combine the advantages of the other two schemes: Hawk-512 signatures are only 555 bytes, smaller than Falcon; signing is entirely integer-based, with a minimum memory footprint of only 6 kilobytes. It was also the only lattice-based candidate remaining in the third round of NIST's additional signature competition, and the report devotes considerable space to this scheme.

The trade-off lies in the security assumptions. It does not rely on the NTRU or SIS problems that have been subjected to decades of cryptanalysis, but on the lattice isomorphism problem and the one-more-SVP assumption, both of which have a relatively short research history.

Just before the report was finalized, Straznickas and Weis from Anthropic discovered a structural flaw in Hawk's lattice construction: the dimension of the SVP problem that actually needs to be solved for key recovery is only half of what the designers intended. The key recovery security bits of the candidate parameter sets were significantly weakened. The researchers completed a full end-to-end key recovery attack on the challenge parameter HAWK-256 used for cryptanalysis; even under attack, the formally proposed HAWK-512 and HAWK-1024 remain practically unbreakable. The Hawk team confirmed the attack's validity and withdrew the scheme from the NIST process; the team stated that if the vulnerability were fixed by doubling parameters, Hawk's original size advantage would completely disappear.

The report retains the Hawk section because the attack targets algebraic properties of a specific number field and does not entirely negate the design paradigm. Whether a redesign can avoid the vulnerability remains an open question. The Hawk incident also intuitively validates our insistence on conservative security margins: a scheme with excellent size and speed, having gone through multiple rounds of standardization, can have its estimated security level drastically reduced by a single paper.

Comparison Table of Schemes

All schemes in the table above (including SPHINCS+) are stateless signatures: the signer does not need to record past signatures. Stateful hash-based signatures like XMSS can achieve smaller signature sizes but require maintaining signature state; see the hash-based signature special report for comparison.

Many Obstacles Remain for Deployment

Falcon lacks a usable key derivation scheme. The only publicly available BIP-32-style Falcon derivation scheme re-randomizes the private key basis, causing the signature norm upper bound to be drastically increased, and on-chain signatures balloon to about 23.7 kilobytes. Moreover, the scheme's parameters do not meet its own security conditions, and fixing this issue would further increase the size. There is currently no viable Falcon public key derivation implementation, which is also the most valuable open problem identified in the report.

The Falcon standard is not yet finalized. Although NIST has selected Falcon, the FN-DSA draft has not been officially released. Only after standardization is complete will we have audited implementations, test vectors, and hardware-level support. Widespread adoption can reduce the risk and difficulty of integrating into Bitcoin's consensus layer. We recommend waiting for the official release of FN-DSA; until then, Falcon remains in a state of flux.

Falcon-WS variant: This variant relaxes internal parameters and relies on rejection sampling for compensation, compressing the total size to 1114 bytes at level 1 and 2387 bytes at level 5, further reducing size compared to the original Falcon. This direction has research value but will not be included in the official standard and requires more cryptanalytic validation. Existing research has found flaws in the strong unforgeability proofs of its derived schemes (ordinary unforgeability is unaffected).

Will better schemes emerge in the future? Apart from the above schemes, the Fiat-Shamir family dates back to BLISS in 2013. The latest result by Gärtner at CRYPTO 2025, based on mature assumptions, has paper sizes comparable to Falcon. The root cause of the difficulty in engineering this family lies in implementation security: BLISS was broken by side-channel attacks due to non-constant-time Gaussian sampling; subsequent schemes have not completely resolved this issue, and the latest result also suggests that protecting the sampling step is even more difficult. Until the problem is solved, such schemes are only theoretically attractive and not suitable for deployment.

Lattice-based and hash-based signatures can complement each other. Lattice-based signatures can serve as components of hybrid schemes. For example, in SHRINCS, the stateless recovery path currently uses SPHINCS+ signatures of several kilobytes; replacing them with Falcon (or Falcon-WS) signatures would be smaller and faster to verify, significantly reducing the overhead of the infrequent recovery path without affecting the everyday use path.

Research Conclusions

The ranking of lattice-based candidates is clear: Hawk withdrew from competition after the attack by the Anthropic team; Dilithium has the lowest implementation difficulty and is the only scheme with a research foundation for key derivation, but its size is not friendly to Bitcoin's on-chain costs; Falcon combines compact size, fast verification, and mature security assumptions; its main weakness—floating-point arithmetic on the signing side—already has a viable engineering solution. If we had to choose a lattice-based signature scheme for Bitcoin today, we would choose Falcon-1024.

For now, our view is consistent with the hash-based signature report: the conservative short-term route remains hash-based signatures, with the most mature security assumptions and lowest risk, suitable as a transitional scheme. Once FN-DSA is officially finalized, with stable specifications, audited codebases, and hardware wallet support, Falcon will bring significant improvements over pure hash-based signatures; a hybrid deployment can also be adopted, allowing the two signature systems to complement each other.