Hash Based Digital Signature Parameter Explorer

Bitcoin Has a Post-Quantum Problem

Bitcoin authorizes spending with ECDSA and Schnorr signatures, whose security rests on the discrete logarithm problem. A cryptanalytically relevant quantum computer would solve that problem and could forge those signatures, spending coins it does not own. Hash-based signatures are one replacement, relying only on the kind of hashing Bitcoin already uses, and the choices they involve are what this site lays out.

This site is built to navigate that decision space. Every scheme and parameter choice trades signature size, signing and verification cost, statefulness and signature budget against one another, and the site presents those tradeoffs side by side.

Bitcoin authorizes spending with elliptic curve cryptography. Shor's algorithm would enable a cryptographically relevant quantum computer to solve the elliptic curve discrete logarithm problem and forge these signatures. Hash-based signature schemes rely only on properties of hash functions, which Bitcoin already depends on. Hash-based Signature Schemes for Bitcoin by Kudinov and Nick surveys these schemes and their parameter selection for Bitcoin, and SHRINCS specifies a scheme that combines a stateful component with a stateless SLH-DSA (FIPS 205) component.

These constructions are built using a handful of primitives: one-time signatures (e.g., WOTS), few-time signatures (e.g., FORS), and Merkle trees that aggregate many such key pairs under a single public key. This tool explores the parameter space of these constructions and the tradeoffs. Users can adjust the parameters and observe the effect on signature size, public key size, signing and verification cost, state management requirements, and the maximum number of signatures per key. It also shows what these changes mean for block space consumption and transaction throughput. Figures can be cross-checked against the SPHINCS-Parameters scripts.

For each of the \(n\) message bits the signer holds two secret values, \(sk_{i,0}\) and \(sk_{i,1}\), and publishes their hashes as the public key. Signing reveals, for each bit \(m_i\), the secret value \(\boldsymbol{sk_{i,m_i}}\). The verifier hashes each revealed value and compares it with \(\boldsymbol{pk_{i,m_i}}\).

Visualization

Secret
key
Public
key
\(m_i\)
\(sk_{i,0}\)
\(sk_{i,1}\)
Hash call
\(pk_{i,0}\)
\(pk_{i,1}\)

Click a message bit to flip it. Filled \(sk\) values are revealed in the signature; outlined \(pk\) values are the ones the verifier checks.

WOTS signs an \(n\)-bit message with hash chains. The message is written as \(\mathrm{len}_1\) base-\(w\) digits \(b_i\), followed by the \(\mathrm{len}_2\) base-\(w\) digits of the checksum \(\boldsymbol{C = \sum_i (w - 1 - b_i)}\). Chain \(i\) starts at a secret value \(sk_i\) and takes \(w - 1\) hash calls to reach \(pk_i\). The signature reveals the value at position \(\boldsymbol{b_i}\) of each chain, and the verifier completes the remaining \(\boldsymbol{w - 1 - b_i}\) steps. Raising a message digit lowers the checksum, so a forger would have to run a checksum chain backward.

WOTS+C replaces the checksum chains of WOTS with a search. The signer hashes \(m \,\|\, \mathbf{count}\) into a digest \(\boldsymbol{d}\) of \(\mathrm{len}_1\) base-\(w\) digits \(a_i\), and increments the counter until the first \(\boldsymbol{l = \mathbf{len}_1 - z}\) digits sum to \(\boldsymbol{S_{w,n}}\) and the last \(z\) are zero. The verifier checks both conditions, so the signature carries \(l\) chain values and the counter. With the sum fixed, raising one digit lowers another, which needs an earlier chain value.

Visualization

\(sk_i\)\(pk_i\)
Message
Checksum

Click a message digit to increment it. Filled values are revealed in the signature; shaded values are computed by the signer, outlined values by the verifier.

Visualization

\(sk_i\)\(pk_i\)

A digest that meets both conditions, resampled when a parameter changes. Filled values are revealed in the signature; shaded values are computed by the signer, outlined values by the verifier. Zero-chains are not part of the signature.

XMSS authenticates \(\boldsymbol{2^h}\) WOTS+C public keys as the leaves of a Merkle tree of height \(h\), and the root is the public key. To sign, the signer takes the next unused leaf \(i\), signs the randomized message digest with that leaf's WOTS+C key, and attaches the authentication path, the \(\boldsymbol{h}\) sibling nodes from the leaf to the root. The signature is \(\boldsymbol{(i, R, \sigma_{\mathbf{OTS}}, \mathbf{AuthPath}_i)}\). The verifier recomputes the leaf from \(\sigma_{\mathrm{OTS}}\), hashes up the path, and compares the result with the root. Each leaf signs once, so the signer stores the index of the next unused leaf.

Visualization

Each leaf is a WOTS+C public key: one hash call compresses the ends of its \(l\) chains. Each inner node is one hash call on its two children, and the root is the public key.

XMSSMT stacks \(\boldsymbol{d}\) layers of XMSS trees of height \(h'\) into a hypertree of total height \(\boldsymbol{h = d \cdot h'}\). The root of the top-layer tree is the public key. The root of each lower tree is signed by a WOTS+C key from the tree above it, and a bottom-layer WOTS+C key signs the randomized message digest. The signature holds the leaf index \(i\), the randomness \(R\), and for each layer \(\boldsymbol{(\sigma_{\mathbf{OTS}}, \mathbf{AuthPath})}\). The verifier recomputes each layer's root from the one below and compares the top-layer root with the public key. The signer stores the next unused bottom-layer leaf index.

Visualization

Each leaf is a WOTS+C public key: one hash call compresses the ends of its \(l\) chains. Each inner node is one hash call on its two children. Layers are numbered from the bottom, and the top-layer root is the public key.

FXMSS is an unbalanced Merkle tree (UXMSS) of WOTS+C leaves whose \(\boldsymbol{\mathbf{depth}}\) the signer chooses at key generation. Signature \(q\) uses a leaf at depth \(\min(q, \mathrm{depth})\), so signatures grow by one node up to the full depth. The key holds \(\boldsymbol{\mathrm{depth} + 1}\) signatures, and the signer stores the next unused leaf index.

Visualization

Each leaf is a WOTS+C public key: one hash call compresses the ends of its \(l\) chains. Each inner node is one hash call on its two children, and the root is the public key.

FORS (Forest of Random Subsets) is a few-time signature made of \(\boldsymbol{k}\) Merkle trees of height \(\boldsymbol{a}\) whose leaves are secret values, with the public key one hash call on the \(k\) roots. The randomized message digest is split into \(k\) indices of \(a\) bits, and the signature reveals the indexed leaf of each tree with its authentication path. Each signature reveals \(k\) more leaves, so the probability of a forgery grows with the number of signatures \(\boldsymbol{q}\). FORS+C grinds a counter until the last tree's index is 0, which removes that tree's authentication path from the signature.

Visualization

Each tree has \(2^a\) secret leaves; the filled square is the leaf a signature reveals. The verifier hashes it up its authentication path to the tree's root and compresses the \(k\) roots into the public key.

PORS+FP is a few-time signature made of one Merkle tree of \(t = k \cdot 2^a\) secret leaves, filled from the left, whose root is the public key. The randomized message digest selects \(\boldsymbol{k}\) distinct leaves, and the signature reveals them with their Octopus authentication set. The signer grinds the digest until that set has at most \(\boldsymbol{m_{\max}}\) nodes, so every signature carries \(k + m_{\max}\) values. Each signature reveals \(k\) more leaves, so the probability of a forgery grows with the number of signatures \(\boldsymbol{q}\).

Visualization

The tree has \(t\) secret leaves; the filled squares are leaves a signature reveals, \(k\) in all. The verifier hashes them up with the authentication set to the root.

TL;DR: Reusing a WOTS key exposes values on every chain, which drops its security from about 128 bits to a few dozen. HG-WOTS hides most of its groups behind a group chain in each signature, so groups that stayed hidden in earlier signatures remain unexposed, and the key can sign a few times while its security falls gradually.

HG-WOTS splits the hash chains of a one-time key into \(\boldsymbol{k}\) groups of \(s\) chains. The chain ends of a group hash into the start of a group chain, and the \(k\) group chain ends hash into the public key. A signature hides \(\boldsymbol{j}\) groups and sends one node on each hidden group chain, and reveals the other \(k - j\), sending one node on each of their chains. The message picks the hidden groups and every position.

The distances to the chain ends add up to a fixed total, \(\boldsymbol{d_g}\) in each revealed group and \(\boldsymbol{d_h}\) across the hidden groups. Moving one node forward to sign a different message would force another node backward, which would mean inverting the hash, so no checksum chains are needed. Each group chain carries message bits, and the forgery probability grows with the number of signatures \(\boldsymbol{q}\).

Visualization

One key signing a sampled message. Filled cells are the nodes the signature sends, shaded cells the ones the signer computes to reach them, and outlined cells the ones the verifier computes. A revealed group's group chain is walked from its start. A hidden group sends nothing from its chains, drawn dashed.

TL;DR: HagGrid nests HG-WOTS: each unit holds smaller units with their own chains, and at every level the signature opens one unit and hides the rest, so every level carries message bits. A forger needs earlier signatures that opened the same unit at every level, which buys more security per node than HG-WOTS, at the cost of more hash calls to build the key and to verify.

HagGrid nests HG-WOTS. In HG-WOTS a group holds plain hash chains; in HagGrid a unit holds smaller units, each with its own chain running up to its parent, repeated over several levels down to a bottom group of chains. At every level the signature hides all units but one, sending one node on each of their chains at a position the message picks, and opens the remaining one, so every level carries message bits. In the opened bottom group it sends one node on each chain.

Visualization

One key signing a sampled message. At every level the signature opens one unit, whose chain the verifier walks from its start, and sends one node on the chain of each other unit. Filled cells are the nodes the signature sends, shaded cells the ones the signer computes to reach them, and outlined cells the ones the verifier computes. Only the units under the opened ones are drawn.

HGT is a Merkle tree of \(\boldsymbol{N}\) leaf keys, each an HG-WOTS or a HagGrid key. The message hash picks \(\boldsymbol{K}\) distinct leaves, and the signature carries a leaf signature for each with one Merkle multiproof up to the root. A separate field of the message hash must pass a grinding threshold. The signer keeps no state and rebuilds every leaf for each signature, so leaves are picked again across signatures, and the security after \(\boldsymbol{r}\) signatures depends on the security of a leaf key after reuse.

Visualization

One leaf

One leaf

The tree above, and one leaf signing a sampled message below. Filled cells are the nodes the signature sends, shaded cells the ones the signer computes to reach them, and outlined cells the ones the verifier computes.

SPHINCS+, standardized as SLH-DSA in FIPS 205, places a FORS key pair at every bottom-layer leaf of an XMSSMT hypertree. Signing hashes the message with randomness \(R\) into a digest that is split into the \(\boldsymbol{k}\) FORS indices, a tree index, and a leaf index. The selected leaf's FORS key signs the digest, the OTS key of that leaf signs the FORS public key, and each layer above signs the root below it, as in XMSSMT. The signature is \(\boldsymbol{(R, \sigma_{\mathbf{FORS}}, \sigma_{\mathbf{HT}})}\). Because the digest picks the leaf, the signer keeps no state, and the same FORS key pair can be selected more than once. The OTS is WOTS.

Visualization

Each hypertree leaf is an OTS public key, and each inner node is one hash call on its two children. Under the selected bottom-layer leaf sits its FORS key pair: \(k\) trees of \(2^a\) secret leaves whose roots one hash call compresses into the FORS public key.

SHRINCS combines two hash-based signature schemes under one public key, and a signature from either one passes verification. The stateful component is an FXMSS tree of WOTS+C leaves, and the stateless component is SLH-DSA with a non-standard parameter set. The signer uses the stateful component and falls back to the stateless one when signing state is unavailable. Each component contributes a root to the public key \(\boldsymbol{\mathrm{pk\_seed} \,\|\, \mathrm{stateless\_root} \,\|\, \mathrm{stateful\_root}}\), and the first byte of a signature, the indicator byte, tells the verifier which component signed. The parameters below start at the values given in the specification.

Visualization

The stateful component above and the stateless component below. A stateful signature is checked against \(\mathrm{stateful\_root}\), a stateless one against \(\mathrm{stateless\_root}\).

SHRIMPS combines two SPHINCS+ instances under a single public key, which is a hash of the public keys of both instances. The compact instance is parameterized for \(\boldsymbol{q_s = n_{\text{dev}} \cdot n_{\text{dsig}}}\) signatures, where \(n_{\text{dev}}\) is an upper bound on the number of device initializations and \(n_{\text{dsig}}\) the number of signatures each device makes through it. The fallback instance has a large \(q_s\). A device loaded from the seed derives both key pairs and keeps per-key state, signing through the compact instance until it has made \(n_{\text{dsig}}\) signatures, then through the fallback instance. A signature is a SPHINCS+ signature under the selected instance and the public key of the other instance, the sibling public key. The compact instance uses WOTS+C and PORS+FP. The parameters below start at the values in the Delving Bitcoin post, with the fallback at SLH-DSA-SHA2-128s.

Visualization

The compact instance above and the fallback instance below. Under the compact instance's selected bottom-layer leaf sits one PORS+FP tree of \(t = k \cdot 2^a\) secret leaves, of which a signature reveals \(k\); under the fallback instance's sits a FORS key pair.