# SHRIMPS: 2.5 KB post-quantum signatures across multiple stateful devices

Source URL: https://blog.blockstream.com/shrimps-2-5-kb-post-quantum-signatures-across-multiple-stateful-devices
Updated: 2026-11-18T15:36:15.000Z
Author: Jonas Nick
Published: Mar 27, 2026
Category: Blockstream Research, Quantum

---

**Abstract**: [SHRINCS](https://blog.blockstream.com/shrincs-324-byte-stateful-post-quantum-signatures-with-static-backups/) achieves very small hash-based signatures using a stateful signer while still allowing for static backups. However, its efficient stateful path requires transferring state to any new device, which is error-prone, so in practice any restored or secondary device will typically fall back to large stateless signatures. SHRIMPS removes this single-device constraint. In settings where each key is used for only a small number of signatures (as is typical in Bitcoin), a static seed backup can be loaded into many independent stateful signing devices, each producing a \~2564-byte signature at 128-bit security. The construction requires an upper bound on the number of device initializations; with a conservative bound of 𝑛dev =210, SHRIMPS signatures are up to three times smaller than SLH-DSA (7856 bytes). SHRIMPS can be combined with SHRINCS: the primary device produces \~324-byte signatures, while any backup device produces signatures under 3 KB.

For background, see our explainer on [the quantum threat to Bitcoin](https://blog.blockstream.com/quantum-computing-and-bitcoin-eli5/).

## Basic SHRIMPS

In SPHINCS+, the parameter 𝑞𝑠 bounds the number of signatures that can be securely produced under a single key. Smaller 𝑞𝑠 allows smaller signature sizes. The construction of SHRIMPS combines two SPHINCS+ instances under a single public key: a compact instance with 𝑞𝑠 =𝑛dev where 𝑛dev is an upper bound on the number of device initializations, and a fallback instance with sufficiently large 𝑞𝑠 (e.g., 240 or 264). The SHRIMPS public key is a hash of the public keys of both instances.

![](https://storage.googleapis.com/dxp-staging-assets/blog/body/shrimps-2-5-kb-post-quantum-signatures-across-multiple-stateful-devices/SHRIMPS.png)

A signing device is initialized by loading the seed, which deterministically derives both SPHINCS+ key pairs. To sign, the device looks up its persistent state for this key to determine whether it has signed before: if not, it signs through the compact instance and updates its state; otherwise, it signs through the fallback instance.

A SHRIMPS signature consists of a SPHINCS+ signature under the selected instance and the public key of the other instance (16 bytes[\[1\]](https://delvingbitcoin.org/t/shrimps-2-5-kb-post-quantum-signatures-across-multiple-stateful-devices/2355#footnote-7115-1)). The verifier reconstructs the signing instance’s public key from the SPHINCS+ signature, hashes both public keys to reconstruct pk, and compares it to the known public key. The 16-byte sibling public key is the only overhead beyond a standard SPHINCS+ signature.

Since each device signs at most once through the compact instance, the total number of compact-path signatures across all devices is at most 𝑛dev, which is exactly the number of signatures the compact instance is parameterized to support.

More generally, the compact instance can allow each device 𝑛dsig signatures before switching to the fallback, at the cost of increasing 𝑞𝑠 to 𝑛dev ⋅𝑛dsig. In Bitcoin, keys are commonly used for only a few signatures, so a small 𝑛dsig keeps most signatures on the compact path.

In Bitcoin wallet setups, initializing a device with a seed is typically a manual process that happens rarely. 𝑛dev =210 =1024 is conservative; it is hard to imagine importing a single seed into more than a thousand devices. A device that loses its state and re-initializes from the seed will use the compact path again, consuming an additional signature from the compact instance’s 𝑞𝑠 budget.

The fallback instance can be any SPHINCS+ parameterization with sufficiently large 𝑞𝑠. Using SLH-DSA (SPHINCS+ with 𝑞𝑠 =264), the fallback signature is 7856 bytes; using a SPHINCS+ variant with 𝑞𝑠 =240 from [Hash-based Signature Schemes for Bitcoin](https://eprint.iacr.org/2025/2203), it is less than 4.5 KB.

The following table shows selected compact-path parameter sets, where sizes are shown as the SPHINCS+ signature size plus the 16-byte sibling public key.

| 𝑞𝑠 | Parameters                                                   | Size + 16 | Sign cost |
| ---- | ------------------------------------------------------------ | --------- | --------- |
| 25   | W+C P+FP (𝑘,𝑎,ℎ,𝑑) \=(10,12,12,1), 𝑤 \=16, 𝑆𝑤,𝑛 \=240 | 2324 B    | 2.5M      |
| 210  | W+C P+FP (𝑘,𝑎,ℎ,𝑑) \=(8,17,12,1), 𝑤 \=16, 𝑆𝑤,𝑛 \=240  | 2564 B    | 6.8M      |
| 210  | W+C P+FP (𝑘,𝑎,ℎ,𝑑) \=(12,12,12,1), 𝑤 \=16, 𝑆𝑤,𝑛 \=240 | 2708 B    | 2.4M      |
| 212  | W+C P+FP (𝑘,𝑎,ℎ,𝑑) \=(10,14,14,1), 𝑤 \=16, 𝑆𝑤,𝑛 \=240 | 2628 B    | 9.9M      |
| 212  | W+C P+FP (𝑘,𝑎,ℎ,𝑑) \=(12,13,12,1), 𝑤 \=16, 𝑆𝑤,𝑛 \=240 | 2884 B    | 2.7M      |
| 214  | W+C P+FP (𝑘,𝑎,ℎ,𝑑) \=(8,17,16,1), 𝑤 \=16, 𝑆𝑤,𝑛 \=240  | 2580 B    | 41.0M     |
| 214  | W+C P+FP (𝑘,𝑎,ℎ,𝑑) \=(10,15,14,1), 𝑤 \=16, 𝑆𝑤,𝑛 \=240 | 2772 B    | 10.9M     |
| 214  | W+C P+FP (𝑘,𝑎,ℎ,𝑑) \=(10,12,22,2), 𝑤 \=16, 𝑆𝑤,𝑛 \=240 | 3000 B    | 2.5M      |

Sign cost is in SHA-256 compression calls. For comparison, SLH-DSA (𝑞𝑠 =264) produces 7856-byte signatures at 2.3M compression calls. Verification costs 0.30 compressions per signature byte; the 𝑑 =1 parameter sets above achieve \~0.19 (about 35% lower), while the 𝑑 =2 sets achieve \~0.25\. Each row can be reproduced using the `--params` option of `costs.sage` in [SPHINCS-Parameters](https://github.com/BlockstreamResearch/SPHINCS-Parameters) (commit `f2ea2a2`):

sage costs.sage --params <scheme> <q\_s> <k> <a> <h> <d> <w> <S\_wn>  

For example, the second row: `sage costs.sage --params W+C_P+FP 10 8 17 12 1 16 240`

## State Management

The compact path requires per-key state: the device stores a counter of compact-path signatures made (⌈log2⁡(𝑛dsig +1)⌉ bits).

With key derivation (similar to BIP-32) from a single seed, each derived key is a separate SHRIMPS instance. The device must maintain this state for every derived key, or store a single bit per key indicating that the fallback path should be used.

If the number of compact-path signatures exceeds the 𝑞𝑠 budget (for example, because more devices were initialized than anticipated, or because a device failed to update its state), security does not break down immediately. Instead, it degrades gradually. The following table shows how security decreases for the (𝑘,𝑎,ℎ,𝑑) =(8,17,12,1) parameter set as the total number of compact-path signatures grows beyond the 𝑞𝑠 =210 budget:

| Total compact-path signatures | Security   |
| ----------------------------- | ---------- |
| 210 (budget)                  | 128.0 bits |
| 211                           | 128.0 bits |
| 212                           | 125.1 bits |
| 213                           | 120.4 bits |
| 214                           | 115.0 bits |
| 215                           | 108.9 bits |

As an aside, statefulness is a strong assumption, but the associated risk is localized to individual wallets that mismanage their state. By contrast, alternative post-quantum schemes carry systemic risks: new cryptographic assumptions (lattices, isogenies) or larger signatures.

## Discussion

If we assume stateful wallets and can bound the number of device initializations, SHRIMPS compact-path signatures are smaller than SLH-DSA at lower verification cost and comparable signing cost. With 𝑛dev =210 and 𝑛dsig =1, signatures are 2564 bytes, about three times smaller than SLH-DSA’s 7856 bytes. Increasing 𝑛dsig to allow more signatures per device costs additional bytes and signing time, but even at 𝑛dsig =24 the signature size remains under 3000 bytes.

SHRINCS already assumes stateful wallets, so SHRIMPS can be combined with SHRINCS: the primary device uses SHRINCS’s efficient stateful path (\~324-byte signatures), while any backup device uses the SHRIMPS compact path instead of falling back to full stateless signatures.

A comparison of key generation costs is left to future work. The parameter sets in this post all constrain verification cost per byte to be at most that of SLH-DSA (\~0.30 compressions per byte). Relaxing this constraint (for example, allowing verification cost comparable to Schnorr signature verification per byte) would permit 𝑤 =256, potentially yielding even smaller signatures. We leave this exploration to future work as well.

---

_Thanks to Mikhail Kudinov and Oleksandr Kurbatov for the discussions that led to SHRIMPS and their feedback on earlier versions of this post._

---

1. A SPHINCS+ public key consists of a public seed (PK.seed, 16 bytes) and a hypertree root (PK.root, 16 bytes). Both SHRIMPS instances share the same PK.seed, so the sibling only needs to include PK.root. [↩︎](https://delvingbitcoin.org/t/shrimps-2-5-kb-post-quantum-signatures-across-multiple-stateful-devices/2355#footnote-ref-7115-1)

Originally posted: <https://delvingbitcoin.org/t/shrimps-2-5-kb-post-quantum-signatures-across-multiple-stateful-devices/2355>

## Blog Categories

- [All Posts](https://blog.blockstream.com/)
- [Blockstream Finance](https://blog.blockstream.com/blockstream-finance)
- [Company](https://blog.blockstream.com/company)
- [Lightning Network](https://blog.blockstream.com/lightning-network)
- [Blockstream Mining](https://blog.blockstream.com/blockstream-mining)
- [Blockstream Explorer](https://blog.blockstream.com/blockstream-explorer)
- [Blockstream Satellite](https://blog.blockstream.com/blockstream-satellite)
- [Liquid Network](https://blog.blockstream.com/liquid-network)
- [Blockstream Jade](https://blog.blockstream.com/blockstream-jade)
- [Blockstream AMP](https://blog.blockstream.com/blockstream-amp)
- [Blockstream App](https://blog.blockstream.com/blockstream-app)
- [Blockstream Research](https://blog.blockstream.com/blockstream-research)
- [Cryptocurrency Data Feed](https://blog.blockstream.com/cryptocurrency-data-feed)
- [Elements](https://blog.blockstream.com/elements)
- [Layer-2 Roundup](https://blog.blockstream.com/layer-2-roundup)
- [Quarterly Report](https://blog.blockstream.com/quarterly-report)
- [Layer-2 Report](https://blog.blockstream.com/layer-2-report)
- [Simplicity Language](https://blog.blockstream.com/simplicity-language)
- [Quarterly Update](https://blog.blockstream.com/quarterly-update)
- [Quantum](https://blog.blockstream.com/quantum)
- [Enterprise](https://blog.blockstream.com/enterprise)
- [Insights](https://blog.blockstream.com/insights)
- [Simplicity](https://blog.blockstream.com/simplicity)
- [Developer](https://blog.blockstream.com/developer)
- [Security](https://blog.blockstream.com/security)
- [Jade](https://blog.blockstream.com/jade)
- [Liquid](https://blog.blockstream.com/liquid)
- [Lightning](https://blog.blockstream.com/lightning)
- [Research](https://blog.blockstream.com/research)
- [Core Lightning](https://blog.blockstream.com/core-lightning)
