Raising SPHINCS-like lifetime budgets on constrained hardware
SPHINCS-G grinding doubles with every extra bit of lifetime budget. We describe a construction that reaches 2³⁰ signatures by making only the top tree taller, with randomly drawn episodes, keeping the search as short as at 2²⁴ and signatures smaller than SPHINCS+.
Contents
- The lifetime budget of stateless hash-based signatures
- The problem: how higher signature lifetime budgets interact with constrained hardware
- Background: how SPHINCS+ and SPHINCS-G sign
- Parameters
- Signing
- What this construction does instead
- The core idea: a taller top tree
- Episodes
- The digest does not see the episode
- What changes in the signature
- The signing process
- Nobody can steer signatures
- Fixing security bits
- The easy fix
- Making it practical: caching and pruning
- Caching the top tree
- Pruning the top tree
- Numbers: this construction against SPHINCS+ at 2^{30}
- Signature size and verification
- Grinding
- Key generation
- Slot preparation
- Conclusion
The lifetime budget of stateless hash-based signatures
There's an intense ongoing discussion among large public blockchains that have committed to hash-based cryptography about how to get the default parameter sets for account signatures right. The most interesting example is currently leanSPHINCS, the candidate account signature for Ethereum's execution layer.
On sphincs.art (opens in a new tab), maintained by EF researchers, there are already different sets of potential parameters, each carrying its own strengths and trade-offs. Among these parameters, one of the key variables is the so-called "lifetime budget" of the signature scheme.
Although this concept might be unfamiliar to people who are used to traditional elliptic-curve-based schemes, hash-based signature schemes inspired by SPHINCS+ have a lifetime budget, meaning the number of signatures that can be produced safely, that is, without losing any bits of the target security level (for example 128 bits), before security starts to gracefully degrade.
There is therefore an ongoing discussion within the public blockchain community about getting this specific parameter right without destroying performance across the various signing use cases. The original SLH-DSA (FIPS 205) parameter sets use a budget of potential signatures, which is so astronomically big that users would basically never have to track the number of signatures produced in real-life scenarios, especially on blockchains where transactions carry anti-spam measures and gas costs.
However, using the full original lifetime budget would make signatures impractical on various axes, hence new sets are being discussed. On sphincs.art, there are sets taking into consideration lifetime budgets from (about 16.8 million signatures) up to (about 1.07 billion signatures), while in other networks' proposals, such as SHRINCS (opens in a new tab) for Bitcoin, the proposed stateless path goes as far as (about 1.1 trillion signatures).
As mentioned in previous articles, including our benchmark analysis of SPHINCS-like signature schemes (opens in a new tab), standard accounts on Ethereum and Bitcoin produce very few signatures. Every signature is a transaction that pays fees, so most keys sign only a handful of times: in one analysis of Ethereum's transaction history (opens in a new tab), about 94% of addresses had sent fewer than 10 transactions, and fewer than 1% had sent 100 or more. However, there are special use cases, such as bridges, exchanges, and other signature-intensive environments, where the lifetime starts becoming more relevant. Furthermore, there is no clear answer as to which lifetime is big enough for a scheme to be properly "stateless", in the sense that keeping track of spent signatures is completely irrelevant for most use cases.
In this article, we discuss an alternative SPHINCS-like construction with a different approach to the lifetime budget.
The problem: how higher signature lifetime budgets interact with constrained hardware
Constrained signers, such as hardware wallets and MPC setups, need dedicated techniques to sign efficiently with hash-based schemes, where a single signature can take hundreds of thousands of hash computations. Our own SPHINCS-G is one of them: it moves the expensive work offline into prepared slots, and online signing becomes a search for a randomizer that lands the message on one of them.
However, SPHINCS-G is built on grinding, and grinding scales poorly with the budget. The search takes tries on average ( is the hypertree height, the number of prepared slots), so every doubling of the budget doubles the search, unless the signer also doubles its prepared slots. It also combines poorly with hypertree pruning because the search runs over the whole index space, pruned positions included, so pruning shrinks the budget without shrinking the search.
The budgets discussed today remain manageable. Even at , SPHINCS-G with 32 prepared slots needs about 4.2 million hashes on average. Higher budgets, however, might call for a different approach, such as the one described below, which raises the budget without lengthening the search.
Background: how SPHINCS+ and SPHINCS-G sign
SPHINCS-G is a SPHINCS+ variant signing procedure that produces signatures indistinguishable from standard SPHINCS+ ones. Its trick is to do the expensive work before the message arrives.
Parameters
We take into consideration the following parameter set for SPHINCS+, the set from our SPHINCS-G benchmarks (opens in a new tab).
| Parameter | Value |
|---|---|
| Hash output | 16 bytes |
| Hypertree height | 24 |
| Layers | 3: a top tree of height 10, then two trees of height 7 |
| FORS | trees of height |
| WOTS | WOTS+C, , 64 chains, no checksum |
Signing
SPHINCS+ signs in three steps. The message digest selects a position, one of the leaves of the hypertree. The signer computes that position: its FORS trees, and the WOTS+ signatures and authentication paths up to the root. It then releases the FORS preimages that the digest picks. All of this work starts only once the message is known.
SPHINCS-G moves the expensive step before the message arrives. The signer prepares the material of slots in advance. When a message arrives, it grinds candidate randomizers until the first one, , whose digest hits a prepared slot, which takes tries on average. It then releases that slot's preimages.
What this construction does instead
It makes only the top tree taller, by levels. The extra index bits form an episode. Each prepared slot draws its own episode at random, and the message digest never sees it. This is inspired by SPHINCS-PE (opens in a new tab), which splits the hypertree at an episode boundary and prepares the upper part once for a bounded run of signatures, leveraging episodes.
As a result, this construction keeps the same search as SPHINCS-G, because the digest still selects only 24 bits, while supporting up to signatures at 128-bit security with one extra FORS tree. The overhead is small: the signature grows by bytes (plus 160 B for an extra FORS tree) and verification by hash calls. It also needs no state as the signer never chooses, schedules or remembers an episode, and an attacker cannot steer signatures into one.
The core idea: a taller top tree
The construction aims to raise without making the grinding search more expensive. The overall structure is extremely similar, three hypertree layers with the same FORS trees (plus one extra), but the top tree is taller: height instead of 10. The two lower trees, of height 7, do not change.
Episodes
The leaf index now has bits, split in two:
- Episode , the high bits. It selects one height-10 subtree of the top tree, with root .
- In-episode position , the 24 low bits. The message digest picks it, exactly as in SPHINCS+.
A simple way to picture it: the top tree is copies of the SPHINCS+ top tree, joined by extra Merkle levels. Each copy is an episode, a full SPHINCS+ position space of leaves.
Hypertree layout of the construction: three layers, with a top tree levels taller than in SPHINCS+. The highlighted subtree is the episode chosen by the prepared slot.
The digest still picks the 24 low bits, through the height-10 episode subtree and two trees of height 7; the episode above them comes from the prepared slot.
The digest does not see the episode
The message hash outputs the FORS indices and , and nothing else. The episode is handled outside it:
- travels in the signature as one byte.
- is bound through the hash addresses. Every FORS, WOTS+C and Merkle hash under position carries , so material revealed in one episode is useless in another.
- The verifier rejects any outside the valid range.
Keeping out of the digest is the design choice everything else follows from. It keeps the search short (see The signing process) and it is also where the security cost comes from (see Fixing security bits).
What changes in the signature
Apart from the extra FORS tree, only two things: the episode byte, and the authentication path from up to the top root. That path is plain Merkle nodes, with no WOTS block. Everything below is a normal SPHINCS+ opening.
The signing process
Signing keeps the usual prepared-slot search, with one change: each slot draws its full position at random, from a secret PRF and a fresh nonce, and stores next to . The signer then grinds randomizers comparing only , and the first digest that matches a prepared slot wins; the signature uses that slot's (if two slots share , the one prepared first wins).
Since is never hashed, one hash still tests every slot at once, so the search costs tries whatever episodes the slots sit in. The used slot is then retired and replaced by a fresh random one, so nobody picks the episode and nobody has to remember it.
Nobody can steer signatures
Every signature lands on a slot drawn uniformly and independently, and its position is revealed only when the signature is released. An attacker who interrupts, crashes or resets the signer, or discards signatures it does not like, only causes fresh uniform slots to be drawn.
Fixing security bits
The scheme loses exactly bits against a genuinely taller SPHINCS+, and, at , gets them back with one extra FORS tree.
The digest fixes , not . For any digest, a forger can try all positions that share that and use whichever has leaked the most. Its chances add up across episodes.
The expected effect is exact and simple: the scheme is a SPHINCS+ with times more positions, minus exactly bits.
The easy fix
Each extra FORS tree adds about 5.8 bits and changes nothing else in the construction.
| Parameter set | Bits at full budget | Budget at ≥ 128 bits |
|---|---|---|
| 122.8 at | ||
| 128.7 at |
One extra tree costs +160 B of signature (+2.4%), +10 hash calls of verification and about +1.5% of slot preparation. Key generation and the search do not change.
Making it practical: caching and pruning
Caching the top tree, which is a practice already widely known and used across SPHINCS+ signers, brings slot preparation back to regular SPHINCS+ cost; only the one-time key generation takes longer. On the other hand, pruning lets key generation scale with the budget actually needed by the user.
Caching the top tree
Each new slot needs the authentication path of its leaf in the top tree. Consecutive slots land in different, unpredictable episodes, so the signer cannot reuse one episode subtree across slots the way a stateful design would.
Instead, the signer caches the upper part of the whole top tree. A slot then rebuilds only the small subtree around its own leaf.
| Cached part of the top tree | Memory, | Slot preparation (SHA-256 compressions) | vs SPHINCS+ |
|---|---|---|---|
| Whole tree | 2 MiB | 101,992 | +0% |
| Episode roots and above | 2 KiB | 382,567 | +275% |
| Nothing | 0 | ≈ 18.1M | ≈ +17,600% |
The baseline is a SPHINCS+ slot of the set with its own top tree cached: 101,992 compressions and 32 KiB, the cached signing figure from our SPHINCS-G benchmarks.
Pruning the top tree
Key generation must compute the top-tree root over every leaf, which costs times the SPHINCS+ key generation. Pruning skips episodes that will never be used: their subtree is replaced by a single pseudorandom value, computed with a PRF under a dedicated address type.
With live episodes the budget is , for any from 1 to , and key generation costs about times the SPHINCS+ key generation.
The example below has and live episodes: two nodes are pruned.
Pruning example with and live episodes: episodes 5 to 7 are replaced by two PRF values, so the budget is signatures.
The verifier sees the same tree shape at every pruning level and only the signer knows which nodes are PRF values, so the same verifier can be used by every signer, regardless of their pruning level.
Numbers: this construction against SPHINCS+ at
At signatures, the construction's signatures are 959 B (12.4%) smaller than the SPHINCS+ set, verify with 62 fewer compressions, and need 4× less grinding than SPHINCS-G on that set. In exchange, key generation is 64× larger, paid once and offline.
The baseline is the set from sphincs.art (opens in a new tab): (10 + 8 + 8), FORS trees of height 10. The construction starts from the set (, 10 + 7 + 7, , ), raises its top tree by and adds one FORS tree (). Both are sized for signatures at 128 bits.
Figures count SHA-256 compressions, as in the benchmarks, with WOTS+C (64 chains, 4-byte counter) and a one-byte episode in the construction's signature.
Signature size and verification
| Scheme | Budget | Signature | vs SPHINCS+ set | Verification (compressions) |
|---|---|---|---|---|
| SPHINCS+, set | 6,524 B | −15.7% | 566 | |
| SPHINCS+, set | 7,740 B | — | 644 | |
| This construction, | 6,781 B | −12.4% | 582 |
The SPHINCS+ signature is the randomizer (16 B), FORS (4,224 B), three WOTS+C blocks (3,084 B) and the Merkle paths (416 B). The scheme keeps the smaller FORS of the set (3,200 B with 20 trees) and adds B of path and 1 B for the episode.
Grinding
Standard SPHINCS+ signing has no search; the grinding applies only when signing with SPHINCS-G. Each attempt costs 2 hash calls, and the mean is attempts.
| Scheme | Digest-selected bits | Hash calls to hit, (mean) | 99th percentile |
|---|---|---|---|
| SPHINCS-G on the set | 26 | 4.19M | 19.32M |
| This construction, | 24 | 1.05M | 4.83M |
To match the scheme, SPHINCS-G on the set would need prepared slots instead of 32.
Key generation
| Scheme | Budget | Key generation (compressions) | × SPHINCS+ |
|---|---|---|---|
| SPHINCS+, or set | or | 280,575 | 1 |
| This construction, , pruned to 1 episode | 280,587 | 1 | |
| This construction, , pruned to 16 episodes | 4,489,219 | 16 | |
| This construction, , no pruning | 17,956,863 | 64 |
Both SPHINCS+ sets have a top tree of height 10, so their key generation is the same. Each episode costs one such tree, plus 2 compressions per pruned block.
Slot preparation
| Scheme | Top-tree cache | Slot preparation (compressions) |
|---|---|---|
| SPHINCS-G on the set | 32 KiB | ≈ 216,700 |
| This construction, whole top tree cached | 2 MiB | ≈ 103,500 |
| This construction, height 4 and above cached | 128 KiB | ≈ 107,900 |
Slot figures are the cached signing counts from our SPHINCS-G benchmarks, which also include the message hash, plus 1,535 for the extra FORS tree and any subtree rebuilt below the cache. A slot in this scheme costs about half as much as a -set slot, because its FORS trees and lower layers are smaller.
The construction pays key generation in proportion to the budget, once; the SPHINCS+ set pays 959 B and 62 compressions on every signature and, when signed with SPHINCS-G, twice the slot work and 4× the grinding.
Conclusion
If larger lifetime budgets have to be considered, constructions like this one can help keep them practical on constrained hardware. Raising the budget no longer means a longer search for the signer, pruning lets each user pay only for the budget they need (more than 99% of users could safely prune most of the episodes, while still staying in safe stateless territory), and signatures stay smaller than those of an equivalent SPHINCS+ set (about 12% smaller at ).
However, the construction comes with open points and trade-offs. It needs a proper security proof. Pruning has its own downsides, including privacy, as over many signatures, the episodes a key uses reveal roughly how many are live, and with it the budget its owner chose. And the signer must cache the upper part of the top tree to keep slot preparation cheap, a memory cost that the most constrained devices may struggle with. These trade-offs need to be weighed for each use case before anything like this is deployed.