Hash-Based Signatures

What Are Hash-Based Signatures?

Hash-based signatures are a family of digital signature schemes constructed using only cryptographic hash functions as their underlying primitive. Unlike elliptic curve cryptography (used in Bitcoin's ECDSA and Schnorr signatures), which relies on the difficulty of the discrete logarithm problem, hash-based signatures rely solely on properties like preimage resistance and collision resistance of hash functions such as SHA-256.

This distinction matters because Shor's algorithm running on a sufficiently powerful quantum computer could break elliptic curve signatures in polynomial time. Hash functions, by contrast, are only weakened (not broken) by quantum attacks: Grover's algorithm halves their effective security, meaning a 256-bit hash still provides 128-bit security against quantum adversaries. Hash-based signatures are therefore considered inherently quantum-resistant.

The concept dates back to 1979 when Leslie Lamport introduced the first one-time signature scheme built from hash functions. Decades of refinement have produced practical schemes now standardized by NIST as part of the Post-Quantum Cryptography initiative.

How It Works

All hash-based signature schemes build on the same foundation: one-time signatures combined with Merkle trees to support multiple signings from a single public key.

Lamport One-Time Signatures

The Lamport scheme is the conceptual building block. To generate a key pair for signing a 256-bit message hash:

1. Generate 256 pairs of random 256-bit values (512 values total). These form the private key, totaling about 16 KB.
2. Hash each of the 512 values to produce 512 hash outputs. These form the public key (also about 16 KB).
3. To sign, hash the message to get a 256-bit digest. For each bit of the digest, reveal one value from the corresponding pair: the first value if the bit is 0, the second if the bit is 1. The 256 revealed values form the signature (about 8 KB).
4. To verify, the verifier hashes each revealed value and checks that it matches the corresponding entry in the public key.

// Lamport signature concept (simplified)
// Key generation
for i in 0..255:
  sk[i][0] = random_256_bits()
  sk[i][1] = random_256_bits()
  pk[i][0] = SHA256(sk[i][0])
  pk[i][1] = SHA256(sk[i][1])

// Signing
digest = SHA256(message)
for i in 0..255:
  sig[i] = sk[i][digest_bit(i)]

// Verification
for i in 0..255:
  assert SHA256(sig[i]) == pk[i][digest_bit(i)]

The critical limitation: each Lamport key pair can sign exactly one message. Reusing a key to sign a second message reveals additional private key values, potentially allowing an attacker to forge signatures.

Merkle Tree Construction

Ralph Merkle solved the one-time limitation in 1979 by combining many one-time key pairs into a Merkle tree. The tree's root serves as the single public key, and each leaf corresponds to one Lamport key pair:

1. Generate 2^h one-time key pairs (where h is the tree height)
2. Hash each public key to create the tree's leaves
3. Build the Merkle tree up to a single root hash
4. To sign the i-th message, use the i-th one-time key and include the Merkle authentication path (the sibling hashes needed to reconstruct the root)

A tree of height 20 supports 2^20 (about 1 million) signatures. The signer must track which leaves have been used, making this a stateful scheme.

XMSS: Extended Merkle Signature Scheme

XMSS, specified in RFC 8391 and approved in NIST SP 800-208 (October 2020), refines the Merkle tree approach with several improvements: it uses a more efficient one-time signature variant called WOTS+ (Winternitz One-Time Signature Plus) that reduces signature sizes by encoding multiple message bits per chain, and it supports multi-tree constructions (XMSS^MT) for larger signing capacities.

With typical parameters (XMSS-SHA2_20_256), XMSS produces signatures of roughly 2,500 bytes with a 68-byte public key. The multi-tree variant extends signing capacity by chaining multiple trees together.

XMSS is stateful: the signer must maintain a counter of which one-time keys have been used and must never reuse a key. If the state is lost, duplicated, or rolled back (for example, restoring a backup), the same one-time key could be used twice, breaking security. This makes XMSS best suited for controlled environments like firmware signing or certificate authorities, not general-purpose wallets.

LMS and HSS

The Leighton-Micali Signature (LMS) system, specified in RFC 8554, is a second stateful scheme approved alongside XMSS in NIST SP 800-208. LMS uses a simpler design than XMSS, and its multi-tree variant (HSS, Hierarchical Signature System) allows chaining multiple LMS trees for larger signing capacities. Both LMS and XMSS share the same stateful limitation: key reuse breaks security.

SLH-DSA (SPHINCS+): The Stateless Alternative

SLH-DSA, standardized as FIPS 205 in August 2024, eliminates statefulness entirely. Instead of a single Merkle tree with a counter, SPHINCS+ uses a "hypertree" of many smaller trees. The signer deterministically selects which tree and leaf to use based on a pseudorandom function of the message and secret key. This means the same key pair can sign an unlimited number of messages without tracking state.

The cost of statelessness is larger signatures. FIPS 205 defines 12 parameter sets across three security levels, with "s" variants optimized for smaller signatures and "f" variants optimized for faster signing:

For comparison, a Bitcoin Schnorr signature is 64 bytes and an ECDSA signature is roughly 72 bytes. Even the smallest SLH-DSA signature is over 100 times larger.

Why Hash-Based Signatures Are the Most Conservative PQC Approach

Post-quantum cryptography offers several families of algorithms: lattice-based (ML-DSA, formerly Dilithium), code-based (Classic McEliece), and hash-based. Among these, hash-based signatures stand out for requiring the fewest and most well-understood cryptographic assumptions.

Lattice-based schemes rely on the hardness of problems like Module Learning With Errors (MLWE), which, while believed to be quantum-resistant, have been studied for far less time than hash functions. Hash functions like SHA-256 have been analyzed by cryptographers for decades, and their security properties are deeply understood.

If SHA-256 remains collision-resistant (an assumption Bitcoin already depends on for proof of work, Merkle trees, and address derivation), then hash-based signatures remain secure. There is no additional mathematical structure an attacker could exploit. This "minimal assumptions" property is why cryptographers often describe hash-based signatures as the safest long-term bet for post-quantum security.

Use Cases

Firmware and Software Signing

Stateful schemes like XMSS and LMS are already approved for signing firmware updates, software packages, and code. These environments have controlled signing infrastructure where state management is feasible, signature size is less critical (signatures are verified once, not stored on-chain), and long-term security matters because firmware may run for decades.

Certificate Authorities and PKI

Root certificates and long-lived signing keys are prime candidates for hash-based signatures. A root CA that signs a limited number of intermediate certificates fits the stateful model well, and the large signature size is acceptable because certificates are verified infrequently.

Bitcoin and Cryptocurrency

The Bitcoin community is actively researching post-quantum migration paths that could incorporate hash-based signatures. BIP-360, merged in February 2026, proposes Pay-to-Merkle-Root (P2MR) as a quantum-safe output format. BIP-361 outlines a structured sunset of legacy signature types that are vulnerable to quantum attacks. For a deeper analysis, see Post-Quantum Cryptography and Bitcoin.

However, raw hash-based signatures face significant challenges for on-chain use. A 7,856-byte SLH-DSA signature would consume substantial block space, increasing transaction costs and reducing throughput. Researchers are exploring compressed variants: in March 2026, Blockstream engineers demonstrated a hash-based signature scheme called SHRINCS that compresses post-quantum proofs to roughly 324 bytes, potentially making on-chain use viable.

Layer 2 protocols like Spark and Lightning could benefit from hash-based signatures in different ways. Off-chain transactions have more flexibility with signature sizes since they do not compete for block space, and cooperative signing protocols could integrate post-quantum primitives without the same on-chain size constraints.

Long-Term Data Authentication

Documents, records, and data that must remain verifiable for decades (legal contracts, medical records, government archives) benefit from hash-based signatures. The concern known as "harvest now, decrypt later" applies here: adversaries may store signed data today and attempt to forge signatures once quantum computers become available.

Risks and Considerations

Signature Size

The most significant practical limitation is signature size. At 7,856 to 49,856 bytes, SLH-DSA signatures are orders of magnitude larger than ECDSA (72 bytes) or Schnorr (64 bytes). For systems where bandwidth, storage, or block space is constrained, this creates real engineering challenges. Even the stateful XMSS scheme produces signatures of roughly 2,500 bytes.

Stateful Key Management

XMSS and LMS require signers to maintain state tracking which one-time keys have been used. If a signer's state is lost, corrupted, or restored from an old backup, the same one-time key may be reused, completely breaking security. This rules out stateful schemes for most consumer wallet scenarios where backups, device migrations, and recovery from seed phrases are standard practice.

Signing Performance

SLH-DSA signing is computationally expensive compared to elliptic curve schemes. The "s" (small signature) parameter sets can take tens of milliseconds to sign on modern hardware, while the "f" (fast) variants trade larger signatures for faster signing. Verification is generally faster than signing but still slower than ECDSA or Schnorr verification. For high-throughput applications like routing nodes processing thousands of transactions per second, this overhead could become a bottleneck.

Limited Signing Capacity (Stateful Schemes)

Stateful schemes have a hard cap on the number of signatures a key pair can produce. An XMSS tree with height 20 supports roughly one million signatures. While sufficient for firmware signing, this is inadequate for a Bitcoin wallet that might generate a new signature with every transaction over many years. The multi-tree variants (XMSS^MT, HSS) increase capacity but also increase signature sizes.

Transition Complexity

Migrating existing systems to hash-based signatures is not a drop-in replacement. Key sizes, signature formats, and verification logic all change substantially. For Bitcoin specifically, a post-quantum migration would require new address types, consensus rule changes, and potentially years of ecosystem coordination, as discussed in Bitcoin's Taproot quantum vulnerability analysis.

This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.