Project Eleven
Research
projecteleven.com (opens in a new tab)

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+.

View .md file
Contents
  1. The lifetime budget of stateless hash-based signatures
  2. The problem: how higher signature lifetime budgets interact with constrained hardware
  3. Background: how SPHINCS+ and SPHINCS-G sign
  4. Parameters
  5. Signing
  6. What this construction does instead
  7. The core idea: a taller top tree
  8. Episodes
  9. The digest does not see the episode
  10. What changes in the signature
  11. The signing process
  12. Nobody can steer signatures
  13. Fixing security bits
  14. The easy fix
  15. Making it practical: caching and pruning
  16. Caching the top tree
  17. Pruning the top tree
  18. Numbers: this construction against SPHINCS+ at 2^{30}
  19. Signature size and verification
  20. Grinding
  21. Key generation
  22. Slot preparation
  23. 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 2642^{64} 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 2242^{24} (about 16.8 million signatures) up to 2302^{30} (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 2402^{40} (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 2h/B2^h / B tries on average (hh is the hypertree height, BB 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 2302^{30}, 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 qS=224q_S = 2^{24} set from our SPHINCS-G benchmarks (opens in a new tab).

ParameterValue
Hash output nn16 bytes
Hypertree height h0h_024
Layers dd3: a top tree of height 10, then two trees of height 7
FORSk=19k = 19 trees of height a=9a = 9
WOTSWOTS+C, w=4w = 4, 64 chains, no checksum

Signing

SPHINCS+ signs in three steps. The message digest selects a position, one of the 2242^{24} 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 BB slots in advance. When a message arrives, it grinds candidate randomizers RR until the first one, R′R', whose digest hits a prepared slot, which takes 2h/B2^h / B tries on average. It then releases that slot's preimages.

What this construction does instead

It makes only the top tree taller, by h′′h'' 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 224+h′′2^{24 + h''} signatures at 128-bit security with one extra FORS tree. The overhead is small: the signature grows by 16⋅h′′+116 \cdot h'' + 1 bytes (plus 160 B for an extra FORS tree) and verification by h′′h'' 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 hh 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 10+h′′10 + h'' instead of 10. The two lower trees, of height 7, do not change.

Episodes

The leaf index now has 24+h′′24 + h'' bits, split in two:

  • Episode ee, the h′′h'' high bits. It selects one height-10 subtree of the top tree, with root roote\mathrm{root}_e.
  • In-episode position jj, the 24 low bits. The message digest picks it, exactly as in SPHINCS+.

A simple way to picture it: the top tree is 2h′′2^{h''} copies of the SPHINCS+ top tree, joined by h′′h'' extra Merkle levels. Each copy is an episode, a full SPHINCS+ position space of 2242^{24} leaves.

Hypertree layout of the construction: three layers, with a top tree h′′h'' 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 jj, and nothing else. The episode is handled outside it:

  • ee travels in the signature as one byte.
  • ee is bound through the hash addresses. Every FORS, WOTS+C and Merkle hash under position (e,j)(e, j) carries ee, so material revealed in one episode is useless in another.
  • The verifier rejects any ee outside the valid range.

Keeping ee 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 roote\mathrm{root}_e up to the top root. That path is h′′h'' plain Merkle nodes, with no WOTS block. Everything below roote\mathrm{root}_e is a normal SPHINCS+ opening.

The signing process

Signing keeps the usual prepared-slot search, with one change: each slot draws its full position (e,j)(e, j) at random, from a secret PRF and a fresh nonce, and stores ee next to jj. The signer then grinds randomizers RR comparing only jj, and the first digest that matches a prepared slot wins; the signature uses that slot's ee (if two slots share jj, the one prepared first wins).

Since ee is never hashed, one hash still tests every slot at once, so the search costs 224/B2^{24} / B 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 h′′h'' bits against a genuinely taller SPHINCS+, and, at h′′=6h'' = 6, gets them back with one extra FORS tree.

The digest fixes jj, not ee. For any digest, a forger can try all 2h′′2^{h''} positions that share that jj 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 P=2h′′P = 2^{h''} times more positions, minus exactly log⁡2P=h′′\log_2 P = h'' bits.

The easy fix

Each extra FORS tree adds about 5.8 bits and changes nothing else in the construction.

Parameter setBits at full budgetBudget at ≥ 128 bits
h′′=6, k=19h'' = 6,\ k = 19122.8 at 2302^{30}229.302^{29.30}
h′′=6, k=20h'' = 6,\ k = 20128.7 at 2302^{30}230.082^{30.08}

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 treeMemory, h′′=6h'' = 6Slot preparation (SHA-256 compressions)vs SPHINCS+
Whole tree2 MiB101,992+0%
Episode roots and above2 KiB382,567+275%
Nothing0≈ 18.1M≈ +17,600%

The baseline is a SPHINCS+ slot of the qS=224q_S = 2^{24} 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 2h′′2^{h''} 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 PP live episodes the budget is P⋅224P \cdot 2^{24}, for any PP from 1 to 2h′′2^{h''}, and key generation costs about PP times the SPHINCS+ key generation.

The example below has h′′=3h'' = 3 and P=5P = 5 live episodes: two nodes are pruned.

Pruning example with h′′=3h'' = 3 and P=5P = 5 live episodes: episodes 5 to 7 are replaced by two PRF values, so the budget is 5⋅2245 \cdot 2^{24} 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 2302^{30}

At 2302^{30} signatures, the construction's signatures are 959 B (12.4%) smaller than the SPHINCS+ 2302^{30} 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 qS=230q_S = 2^{30} set from sphincs.art (opens in a new tab): h=26h = 26 (10 + 8 + 8), k=24k = 24 FORS trees of height 10. The construction starts from the qS=224q_S = 2^{24} set (h=24h = 24, 10 + 7 + 7, k=19k = 19, a=9a = 9), raises its top tree by h′′=6h'' = 6 and adds one FORS tree (k=20k = 20). Both are sized for 2302^{30} 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

SchemeBudgetSignaturevs SPHINCS+ 2302^{30} setVerification (compressions)
SPHINCS+, qS=224q_S = 2^{24} set2242^{24}6,524 B−15.7%566
SPHINCS+, qS=230q_S = 2^{30} set2302^{30}7,740 B—644
This construction, h′′=6, k=20h'' = 6,\ k = 202302^{30}6,781 B−12.4%582

The SPHINCS+ 2302^{30} 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 2242^{24} set (3,200 B with 20 trees) and adds 16⋅h′′16 \cdot h'' 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 2h/B2^h / B attempts.

SchemeDigest-selected bitsHash calls to hit, B=32B = 32 (mean)99th percentile
SPHINCS-G on the qS=230q_S = 2^{30} set264.19M19.32M
This construction, h′′=6h'' = 6241.05M4.83M

To match the scheme, SPHINCS-G on the 2302^{30} set would need B=128B = 128 prepared slots instead of 32.

Key generation

SchemeBudgetKey generation (compressions)× SPHINCS+
SPHINCS+, qS=224q_S = 2^{24} or 2302^{30} set2242^{24} or 2302^{30}280,5751
This construction, h′′=6h'' = 6, pruned to 1 episode2242^{24}280,5871
This construction, h′′=6h'' = 6, pruned to 16 episodes2282^{28}4,489,21916
This construction, h′′=6h'' = 6, no pruning2302^{30}17,956,86364

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

SchemeTop-tree cacheSlot preparation (compressions)
SPHINCS-G on the qS=230q_S = 2^{30} set32 KiB≈ 216,700
This construction, whole top tree cached2 MiB≈ 103,500
This construction, height 4 and above cached128 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 2302^{30}-set slot, because its FORS trees and lower layers are smaller.

The construction pays key generation in proportion to the budget, once; the SPHINCS+ 2302^{30} 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 2302^{30}).

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.