Falcon, Dilithium, and the Fall of Hawk: Evaluating Lattice-Based Signatures for Bitcoin

Blockstream Research has printed a full report on lattice-based signatures for Bitcoin. This submit summarizes what we examined, what we discovered, and what we suggest. The report itself is obtainable on ePrint.

Digital signatures are the core mechanism in Bitcoin that authorizes transactions, and the Schnorr and ECDSA signatures doing that job immediately are remarkably low-cost. Shor confirmed in 1994 {that a} sufficiently massive quantum pc breaks them. When such a machine will exist stays an energetic matter of dialogue, however a reputable deployment plan for post-quantum signatures is required properly earlier than the reply issues.

Lattice-based signature schemes are amongst the strongest candidates to exchange them. Lattices have been studied for over a century, their cryptographic functions for practically three a long time, and amongst the post-quantum households they promise mixed signature and public key sizes beginning beneath 1.6 kB, plus an algebraic construction which will finally help multisignatures, threshold signing, and succinct proofs.

Our report research the three schemes: Dilithium, Falcon, and Hawk. For every, we current the instinct behind the design, give an entire description of the algorithms, and analyze safety, efficiency, and deployment points resembling pockets key derivation, assuming no prior publicity to lattice cryptography.

This submit condenses the findings: which of the three, if any, may really go on-chain?

What We’re Grading On

Bitcoin locations its personal restrictions on the alternative of a signature scheme. Four standards drive our analysis:

On-chain price. One of the most vital metrics is the mixed measurement of the public key and the signature, as a result of each are recorded on-chain when an output is spent, and each byte is downloaded and saved by each full node. Verification price issues for the identical cause: every signature is verified by each node, so gradual verification burdens the complete community.

Implementation complexity. An vital query is how onerous it’s to implement the scheme securely. A design that wants floating-point arithmetic or delicate Gaussian sampling is a design that may leak its secret key by way of an implementation mistake or a facet channel resembling timing evaluation. We need to purpose for a easy migration, and implementation complexity is a severe issue.

Deployment pitfalls. We must also contemplate the frictions an actual Bitcoin integration would face: the consensus-critical alternative of hash perform (the candidates use SHAKE, Bitcoin makes use of SHA-256), reproducibility of signing throughout platforms, and whether or not the signer suits in the RAM finances of a {hardware} pockets.

Potential. Most Bitcoin wallets are hierarchical and deterministic (BIP 32): from a single grasp public key, a pockets derives an unbounded provide of little one public keys with out ever touching the secret key. None of the standardized post-quantum schemes helps this out of the field, so we look at what it will price so as to add. We additionally have a look at modifications of the schemes, which aren’t standardized however may convey extra advantages.

Which Security Level?

Before evaluating sizes, we’ve got to repair the goal safety stage, and this alternative is much less apparent than it sounds. NIST defines safety classes 1 by way of 5; greater classes present stronger safety, which in flip requires bigger keys and signatures.

We argue that Bitcoin ought to purpose for at the least class 3. Outputs could stay unspent for a long time, and if cryptanalytic progress pushes a scheme beneath its supposed stage, cash could also be locked below weakened keys and keep weak indefinitely. Lattice assumptions usually are not new (they’ve been below public cryptanalysis for shut to 3 a long time, longer than elliptic curves had accrued when Bitcoin adopted them), however their wealthy algebraic construction leaves extra floor for future assaults than we wish to guess the far future on.

Major deployers have reached the identical conclusion. Apple omits Category 1 lattice parameters fully from its iMessage PQ3 protocol, utilizing Category 3 and 5 parameters all through. Cloudflare deploys ML-KEM-768 (Category 3) in its post-quantum TLS rollout, noting that whereas Category 1 appears advantageous immediately, they like a margin towards a long time of future cryptanalysis. Bitcoin’s horizon is longer than both.

The margin has its personal worth. For instance, shifting Dilithium from Category 2 to Category 3 provides about 1.5 kB to the mixed measurement. Our report compares the parameter units in any respect out there safety classes, so readers can assess the trade-offs themselves. Recent occasions, as we are going to see with Hawk, suggest the warning isn’t theoretical.

The Candidates

Dilithium: The Straightforward One

Dilithium (standardized by NIST as ML-DSA in FIPS 204) follows the identical dedication–problem–response template as Schnorr, translated into module-lattice arithmetic.

Its core function is simplicity. Dilithium’s operations are fully integer-based: ring arithmetic, matrix-vector merchandise, hashing, and rounding. There is not any floating level and no discrete Gaussian sampling, which makes a safe, constant-time implementation a lot simpler to get proper. It can also be the most generally adopted candidate, already transport in OpenSSL, BoringSSL, AWS-LC, and Apple CryptoKit.

The worth is measurement. At Category 3 (ML-DSA-65), the public secret’s 1,952 bytes and the signature 3,309 bytes (5,261 bytes mixed), roughly 55 instances Bitcoin’s mixed public key and signature measurement and the largest of the three candidates at each stage.

Dilithium’s most attention-grabbing function for Bitcoin is that it’s the solely candidate with a near-practical strategy to BIP 32-style key derivation. The rerandomizable-key building DilithiumRK turns a father or mother key into a baby key utilizing public info solely. The report analyzes three variants, together with DilithiumRKS, a variant we suggest during which the derivation logic lives fully in pockets software program and the chain sees plain ML-DSA signatures below the inventory verifier. None of the three is able to deploy: two require a verifier that deviates from the normal, our DilithiumRKS nonetheless lacks a accomplished unforgeability proof, and all relaxation on a network-wide shared matrix, a conference that’s formally sound below Module-LWE however concentrates the safety of each key on a single occasion. We argue that at this stage public-key derivation options based mostly on Dilithium are a proof of idea slightly than a deployable possibility.

Falcon: The Compact One

Falcon, chosen by NIST for standardization as FN-DSA, is the most compact of the three. At Category 1, Falcon-512 wants 1,563 bytes for public key and signature mixed; at Category 5, Falcon-1024 wants 3,073 bytes. Falcon-1024, with a big safety margin, continues to be smaller than Dilithium at Category 3.

Falcon takes a distinct route than Dilithium: hash-and-sign over NTRU lattices. The signer’s secret is a brief foundation of a lattice; the message hashes to a degree in area, and the signer makes use of the brief foundation to discover a lattice vector near that time. The pair (level, close by vector) is the signature; verification solely checks that the vector lies on the lattice and is shut sufficient. The delicate half is discovering that vector with out leaking the foundation: earlier schemes (GGH, NTRUSign) merely rounded to a close-by lattice level, and each signature leaked a bit of its geometry. Falcon as a substitute follows the GPV framework and samples the close by vector from a Gaussian distribution whose output is provably unbiased of the foundation, closing the leak at the worth of a way more delicate sampler.

That sampler is Falcon’s weak level in follow. It works in the Fourier area over the advanced numbers, which implies floating-point arithmetic. Floating-point outcomes can differ between processors, compilers, and even optimization flags. This is not only a portability nuisance but additionally a safety downside: the GPV proof requires {that a} signer by no means launch two totally different brief vectors for the identical digest, and platform-dependent rounding can violate precisely that after signing is derandomized. There is an answer: a deterministic Falcon implementation replaces {hardware} floating level with integer emulation, producing bit-identical signatures on each platform. Signing slows down by roughly 15×, and key era by 2×.

Importantly, verification is untouched, as a result of Falcon verification makes use of no floating level in any respect. Falcon’s verification is integer-only, deterministic, and the quickest of all the candidates. This asymmetry is favorable for Bitcoin: an output is signed as soon as, by one pockets, at spending time, whereas its signature is verified by each full node. A 15× penalty on the rare signing, in change for making it reproducible and integer-only, is in our view the proper trade-off. We subsequently regard the floating-point requirement as a manageable engineering concern slightly than a blocker.

Two caveats. Due to structural necessities, Falcon doesn’t have a Category 3 parameter set. The alternative is just between Category 1 and Category 5. By the security-margin argument, we suggest Falcon-1024. The second caveat is that signing requires a major quantity of reminiscence: the sampler is pushed by a precomputed tree that occupies roughly 90 kB of RAM at the 1024 stage. A {hardware} pockets can as a substitute rebuild the tree branch-by-branch inside about 16 kB, at the price of roughly doubling signing time. Slower signing on a small gadget is an actual price, however arguably manageable.

Hawk: The Failed One

Hawk aimed to mix the benefits of the different two candidates: signatures even smaller than Falcon’s (555 bytes at the 512 stage), with a easy, integer-only signer that wants as little as 6 kB of RAM. It was the solely lattice candidate remaining in the third spherical of NIST’s additional-signatures competitors, and a big half of our report is dedicated to it.

The trade-off lay in its assumptions. Instead of NTRU and SIS (issues with a long time of cryptanalysis behind them), Hawk’s safety rests on the Lattice Isomorphism Problem and the one-more-SVP assumption, each comparatively younger.

Shortly earlier than we finalized the report, Straznickas and Weis of Anthropic found a structural weakness in Hawk’s lattice building: key restoration in reality relied on fixing SVP in a lattice of solely about half the dimension the designers assumed. This minimize tens of bits from the estimated key-recovery price of the proposed parameter units, and the authors demonstrated a full end-to-end key restoration towards HAWK-256, the scheme’s problem parameter set supposed for cryptanalysis (the proposed HAWK-512 and HAWK-1024 units stay out of sensible attain even after the assault). The Hawk staff confirmed the assault and withdrew the scheme from NIST’s course of, noting that patching it by doubling parameters would erase the compactness that made Hawk engaging.

We retained the Hawk chapter in the report as a result of the assault exploits a particular algebraic function of the chosen quantity area slightly than the design paradigm itself. Whether a redesign can keep away from it’s an open query. Hawk can also be now the clearest out there illustration of why we argue for conservative assumptions and a safety margin. A scheme might be compact, quick, and three rounds deep right into a standardization course of, and nonetheless lose a good portion of its estimated safety to a single paper.

Scheme Sizes

All schemes on this desk, SPHINCS+ included, are stateless: the signer retains no document of previous signatures. Stateful hash-based schemes resembling XMSS obtain smaller signatures at the price of managing that state; see the hash-based report for that comparability.

What Keeps This from Being a Done Deal

No key derivation for Falcon. The single printed building for BIP 32-style derivation on Falcon rerandomizes the secret foundation, which inflates the signature-norm certain by an enormous issue, blowing the on-chain signature as much as roughly 23.7 kB. Worse, its proposed parameters fall brief of the scheme’s personal safety situation, and repairing them drives sizes additional up. There is presently no workable public-key derivation for Falcon; we contemplate this one of the most attention-grabbing open issues the report identifies.

The Falcon normal isn’t last. NIST chosen Falcon, however the FN-DSA draft has not but been printed. Standardization is what brings audited implementations, check vectors, and {hardware} help. The huge adoption makes a consensus-critical integration simpler and safer. We argue that it is smart to attend for the Falcon normal to be printed: till then, Falcon is a shifting goal.

Falcon-WS. A latest variant relaxes one inner parameter and compensates with rejection sampling, bringing the mixed measurement all the way down to 1,114 bytes at Category 1 and 2,387 bytes at Category 5. This is noticeably beneath plain Falcon. We view it as a genuinely promising course, with the normal caveat for younger schemes: it should seemingly not be in the normal, and it wants extra cryptanalysis. A niche has already been present in the strong-unforgeability proof of a follow-up work (plain unforgeability is unaffected).

Could a greater scheme nonetheless seem? The most promising recognized course past the schemes above is the Fiat-Shamir line that started with BLISS in 2013, whose latest member (a CRYPTO 2025 scheme by Gärtner, lined in our report) reaches sizes aggressive with Falcon below well-studied assumptions. What has saved this line out of follow is implementation safety: BLISS was damaged by way of facet channels in its non-constant-time Gaussian sampling, and no later scheme in the line resolves this. The latest one warns that its sampling could also be even more durable to guard. Until that modifications, we see these schemes as engaging on paper slightly than deployable.

Lattices and hashes are complementary. A lattice scheme may function one element of a hybrid scheme. In SHRINCS, the stateless restoration path is presently a SPHINCS+ signature of a number of kilobytes; for instance a Falcon (or Falcon-WS) signature in that slot is way smaller and sooner to confirm, making the rare fallback less expensive whereas leaving the on a regular basis path untouched.

Our Conclusion

Among the lattice candidates, the rating is unambiguous. Hawk is withdrawn after the Anthropic assault. Dilithium is the best to implement and the just one with a key-derivation story, however its sizes are onerous to justify for Bitcoin. Falcon affords the finest mixture of compactness, verification pace, and mature assumptions, and its most important disadvantage (floating-point signing) has a recognized, sensible mitigation. If we needed to choose a lattice-based signature scheme for Bitcoin immediately, we’d select Falcon-1024.

For immediately, our views are unchanged from the hash-based report: the conservative near-term possibility stays a hash-based scheme, which depends on the most mature assumptions and carries minimal danger. This could be a transitional section for Bitcoin. Once FN-DSA is finalized, bringing a set specification, audited libraries, and {hardware} help, Falcon may enhance on purely hash-based signatures considerably, and a hybrid deployment lets the two households complement one another.

The full report, together with full algorithm descriptions, safety analyses, parameter derivations, and the wallet-derivation constructions, with no prior publicity to lattice cryptography assumed, is obtainable on ePrint. Questions and suggestions are welcome, and we hope the report supplies a helpful start line for additional work on the open issues recognized above.

Follow Blockstream Research on X and subscribe to our e-newsletter for future posts on this sequence.