Abstract: SHRINCS 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.
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.
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]). 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, 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 | |
|---|---|---|---|
| W+C P+FP | 2324 B | 2.5M | |
| W+C P+FP | 2564 B | 6.8M | |
| W+C P+FP | 2708 B | 2.4M | |
| W+C P+FP | 2628 B | 9.9M | |
| W+C P+FP | 2884 B | 2.7M | |
| W+C P+FP | 2580 B | 41.0M | |
| W+C P+FP | 2772 B | 10.9M | |
| W+C P+FP | 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 (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 |
|---|---|
| 128.0 bits | |
| 128.0 bits | |
| 125.1 bits | |
| 120.4 bits | |
| 115.0 bits | |
| 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.
- 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. β©οΈ
Originally posted: https://delvingbitcoin.org/t/shrimps-2-5-kb-post-quantum-signatures-across-multiple-stateful-devices/2355