SPHINCS minus : Efficient Stateless Post-Quantum Signature Verification on the EVM
Special thanks to Vitalik Buterin, Jean-Philippe Aumasson, Justin Drake, Chelsea Komlo, Mauro Toscano, ZKnox and colleagues from the EF PQ & cryptography team for all the discussions, reviews and feedback.
Introduction
Quantum computers will eventually break ECDSA, the signature scheme that secures Ethereum and Bitcoin accounts today. Recent resource estimates by Babbush et al. [1] bring this timeline closer than previously expected, making post-quantum signature verification at the execution layer an urgent problem. In this post we introduce SPHINCS-, a family of EVM-optimised variants derived from SPHINCS+ and from recent work on compact hash-based signatures. Our goal is simple: minimize pure on-chain verification cost without relying on a precompile or a protocol change.
We show that a Solidity implementation of a SPHINCS variant, aligned with NIST’s draft for limited-signature parameter sets, can already verify a standardized-style post-quantum signature on Ethereum at practical cost (150K gas). We also provide a formal proof of the verifiers using lean 4 with Verity. This is great news for organisations that are looking to get FIPS compliance on Ethereum. We then explore more aggressive non-standard variants that replace the standard hash components with an EVM-native keccak-based construction and reduce the signature budget to the range relevant for blockchain wallets. Across these variants, we study the trade-off between verifier gas, signer work, signature size, and per-key signature budget.
1. Origin of the idea
A discussion with Vitalik about post-quantum cryptography on Ethereum surfaced a simple observation: the EVM already has a cheap KECCAK256 opcode, and SPHINCS+ is built entirely from a similar hash function. Replacing the standard’s SHAKE256 with KECCAK256 would let the verifier run natively on-chain, without a precompile.
NIST standardized SPHINCS+ as “SLH-DSA” [3] with a 2^64 signature budget which is way beyond the usage of a blockchain wallet. According to dune, the average annual 99.9th percentile of Ethereum mainnet transactions per active address is about 431 transactions yearly since the Merge. So we explored the same scheme but with a more conservative signature budget.
The remaining ingredients came from recent work on compressing SPHINCS+ signatures. Among others, Drake et al. [4] describe a target-sum Winternitz encoding that eliminates the checksum overhead. Kudinov and Nick [5] systematised this further in their report on hash-based signatures for Bitcoin, detailing WOTS+C checksum grinding, FORS+C and PORS+FP counter grinding / forced pruning, and showing how to push signature sizes well below SLH-DSA at reduced signature-count budgets. From the same line of work, Nick proposed SHRINCS [6] and SHRIMPS [7], demonstrating that stateful/stateless hybrids can bring hash-based signatures down to 324 bytes on a primary device and ~2.5 KB across independent backup devices. By combining these ideas we can get an EVM-native hash based signature scheme with aggressively verifier-optimised parameters making post-quantum signatures practical on Ethereum today.
We leveraged Blockstream research parameter search tool to explore SPHINCS+ variant and adapt it to the EVM (check this repo to explore the parameter tradeof). This post describes the parameter space, explains what each knob does to the EVM verifier and the signer, and presents the resulting variant family. Special shout-out to Tom Wambsgans for helping me with the exploration.
2. Background: How SPHINCS+ Works
A hash function is one-way: easy to compute forward, infeasible to reverse. Hash-based signatures exploit this asymmetry by committing to secret values with hashes, then later revealing selected secrets as signatures. Three building blocks make this practical: hash chains, which encode choices by revealing positions in a one-way sequence; Merkle trees, which compress many one-time public keys into a single root; and few-time schemes, which let a key sign a small number of messages before it must be retired. SPHINCS+ stacks these pieces into a stateless hash-based signature scheme built on a hypertree, a tree of trees. At the leaves are FORS instances, “Forest of Random Subsets,” which provide few-time signatures. Above them are layers of XMSS trees, each using WOTS+, Winternitz One-Time Signatures, to authenticate the layer below.
To sign a message M you start by hashing it with a randomizer and your public key information. Such that :
H_msg(Randomizer, PK.seed,PK.root, M) => ( md , idx_tree , idx_leaf )
This hash gives you three things: a message digest md, plus two indices that pick which subtree and which leaf of the hypertree will do the actual signing.
Think of the hypertree as a giant filing cabinet. The message tells you which drawer idx_tree and which folder idx_leaf to use. The message digest is then chopped into k chunks of a bits, and each chunks as a value which selects one secret in that folder. Reveal those secrets, and that’s your signature.
Note that with a d=1 parameter you don’t have subtrees so idx_tree is always giving you the outer tree.
You can check how this works visually at https://sphincsminus.org/
A signature contains:
- A FORS signature: k secret leaf values plus k Merkle authentication paths, compressed into one FORS public key.
- d WOTS+ signatures: one per hypertree layer, each consisting of l hash chains.
- d Merkle authentication paths: one per hypertree layer, each of height h/d.
The verifier walks this structure bottom-up: verify the FORS opening, compress it to a FORS public key, use it as the message for the first WOTS+ layer, walk the Merkle auth path to reach the next layer, repeat d times until reaching the root. Every step is a hash evaluation. The total number of hashes the verifier computes determines the on-chain gas cost.
2.1 Standardisation
NIST has already standardized several PQ signature schemes, including the lattice-based ML-DSA [2] and FN-DSA (Falcon) still in draft. Hash-based signatures are an attractive alternative: their security rests entirely on the properties of hash functions, well-understood with minimal assumptions these primitives are simpler to understand than lattice constructions.
3. The Parameters and what they do
3.1 Hash output size: n => how many bytes each hash produces
The output size of all hash evaluations. Standard SLH-DSA offers n=16/24/32 bytes (128/192/256-bit).
EVM impact: Every Merkle node, WOTS+ chain value, and FORS leaf is n bytes. At n=16, signatures are half the size of n=32.
Security: n caps preimage security at 8n bits. n=16 gives 128-bit, sufficient for our target.
Our choice: n=16. Minimum for 128-bit security, smallest possible signatures.
3.2 Hypertree layers: d => how many trees are stacked
The number of XMSS subtree layers. Standard SLH-DSA uses d=7 to d=22.
EVM impact. The verifier performs d WOTS+ verifications and d Merkle auth path walks. Doubling d roughly doubles verification work from the hypertree portion.
Signer impact. Each layer requires building a full subtree of 2^(h/d) leaves. With d=2 the signer builds two subtrees; with d=3, three. This is the dominant signing cost.
Our choice: d=2. Minimises on-chain WOTS+ verifications. Every sweep confirmed d=2 as optimal for EVM gas.
3.3 Hypertree height: h => how many signatures one key can produce
Total hypertree height. Determines signature capacity q_s. The scheme addresses 2^h FORS instances.
EVM impact: The verifier walks h total Merkle authentication nodes (h/d per layer, d layers). Increasing h by 4 adds ~800 gas, a modest cost.
Security impact: Larger h means more FORS instances (2^h of them), so signatures are less likely to collide on the same instance. Since FORS-reuse is the dominant degradation mechanism at high signature counts, increasing h lets a key sustain more signatures before security drops below the target. The exact security level at a given signature count is a joint function of h, k, and a ; see the per-variant sec_N columns in §5 for concrete numbers.
Signer impact: Subtree size is 2^(h/2) with d=2. Going from h=16 to h=24 increases subtree size from 256 to 4,096 leaves, a 16x increase in signing work.
The trade-off: h is the primary knob for signing-speed vs security-at-high-signature-counts. Larger h costs little on the verifier (200 gas/unit) but dramatically increases signer work.
3.4 FORS trees: k and tree height: a => how the few-time signature is structured
FORS uses k independent binary trees, each of height a (2^a leaves). The signature reveals one leaf per tree plus its auth path.
EVM impact: The verifier computes approximately (k-1)*(1+a) + 2 hashes for the FORS portion. With FORS+C, the signer forces the last index to zero, eliminating one tree from the signature and saving (1+a)*n bytes and (1+a) hashes.
Security. FORS one-time security is ka bits. For 128-bit: ka >= 128. Higher a means slower degradation under reuse (each reuse reveals a smaller fraction of the tree).
Signer impact. FORS+C grinding requires expected 2^a attempts. Higher a means exponentially more grinding.
3.5 Winternitz parameter: w => chain length vs chain count tradeoff
The base of the WOTS+ system. The verifier completes l hash chains to position w-1.
EVM impact. The most consequential parameter for gas. Chain count l is determined by n and w. For n=16:
| w | l | Verify chain steps (with +C) | WOTS body per layer |
|---|---|---|---|
| 8 | 43 | 43*7 - S_wn | 688 B |
| 16 | 32 | 32*15 - S_wn | 512 B |
| 32 | 26 | 26*31 - S_wn | 416 B |
| 256 | 16 | 16*255 - S_wn | 256 B |
Higher w means fewer chains (smaller signatures) but longer chains (more hashes per chain). The formula is given by : l = ceil(security_bits / log2(w))
The gas optimisation finding under a raw calldata-floor model, high-w variants look attractive. But once real verifier execution is modelled, chain work dominates. w=8 wins because the chains are short (7 steps max) even though there are more of them (43 chains). Credits to Emile for finding this family. This was the single most important lesson from the parameter search: one must model actual verifier execution, not just opcode gas plus calldata.
3.6 Target digit sum: S_wn => how hard the signer grinds to shrink the verifier
In WOTS+C, the signer grinds until the digit sum equals exactly S_wn, replacing the standard WOTS checksum.
EVM impact. The verifier computes l*(w-1) - S_wn chain steps per layer. Higher S_wn = fewer steps = cheaper. Linear relationship.
Signer impact. Higher S_wn means fewer valid encodings, more grinding. Smooth knob trading signer work for verifier savings.
Security impact. None. S_wn does not affect cryptographic security. It only shifts cost between signer and verifier.
3.7 Summary
Parameter Verifier cost Signer cost Security
--------- ------------- ----------- --------
n=16 Minimum calldata -- 128-bit cap
d=2 2 WOTS+ verifies 2 subtree builds --
h up +200 gas/unit x16 per 4 units More sigs at 128-bit
k up More FORS trees -- Higher k*a
a up Taller auth paths Exponential grind Slower degradation on reuse
w=8 Short chains (7) 43 chains, moderate --
S_wn up Fewer chain steps Harder grinding None
4. The Calibrated Gas Model
We used https://github.com/nconsigny/EVM-SPHINCs-Parameters with EIP-7623 and EIP-7976 floor pricing to look for variants. We measured real verifier traces for the deployed variants and found the ranking diverged from the raw model. Variants with smaller signatures (higher w or PORS-based) looked best under the floor model, but variants with fewer total hash evaluations (w=8, FORS+C) were cheaper in practice. The raw model overvalued signature size and undervalued execution cost.
We fitted a coarse model against measured traces:
ExecGas = 36,118 + 194 * ops
where ops is the verifier’s total hash evaluation count. This recovered the correct gas ordering across variants and became the default search metric.
The distinction matters because of the EIP-7623 floor:
TotalGas = max(StdCalldata + ExecGas, CalldataFloor)
Some variants are floor-bound, others exec-bound. Adding one hash to the verifier costs ~194 gas on the exec path and nothing on the floor path, while saving one signature byte saves 16 gas on both paths. This asymmetry is why w=8 (more chains, shorter, fewer total hashes) beats w=32 (fewer chains, longer, more total hashes) once execution is properly modeled. We also checked for keccak cost increase +20% as we are expecting a keccak repricing in the following hard forks.
5. The Variant Family
TLDR; C13 is the optimized variant for laptop signers; C11 & C12 are optimized for hardware wallet signers; SLH-DSA-SHA2-128-24 is doable on powerful laptops or HSMs.
Depending on the parameter set you have different security degradation and signing times. Security degradation for the variant we chose is the following :
| Variant | Family | h | d | a | k | w | l | Signature Size (bytes) | sign_h (hash call) | Verify (gas EVM) |
|---|---|---|---|---|---|---|---|---|---|---|
| C13 | WOTS+C / FORS+C | 24 | 2 | 16 | 8 | 8 | 43 | 3,704 B | 4.3 M | 127 K |
| C12 | vanilla SPHINCS+ | 20 | 5 | 7 | 20 | 8 | 45 | 6,512 B | 36.6 K | 276 K |
| SLH-DSA-SHA2-128-24 | vanilla SPHINCS+ | 22 | 1 | 24 | 6 | 4 | 68 | 3,856 B | ~1.07 B | 142 K |
| SLH-DSA-Keccak-128-24 | vanilla SPHINCS+ | 22 | 1 | 24 | 6 | 4 | 68 | 3,856 B | ~1.07 B | 94 K |
Check the verifiers contracts at https://github.com/nconsigny/SPHINCS-/tree/main/src
-
Family: the SPHINCS+ construction style can be vanilla SPHINCS+ or WOTS+C / FORS+C the compact construction with grinding
-
h; d; a ; k; w; l : the construction parameters see the description above §3
-
sign_h: hash-function calls during keygen + one signature, zero-memory signer (no inter-sign caching). A high number means a lot of work for the hardware (bad)
-
sec_N: security bits at 2^N signatures per key
-
Verify (pure): Foundry
gasleft()measurement of the assembly block
C11 and C12 are light enough to run on a hardware wallet with respectively 390s and 47.5s signature times measured on a ST33K1M5 secure element (Ledger nano S+). On the other hand SLH-DSA-SHA2-128-24 is the FIPS-aligned alternative: much larger signer cost even on a laptop-class signer. The Keccak twin trades bit-exact NIST compliance for ~34 % cheaper on-chain verification.
6. Limitations and the “leanSPHINCS” horizon
SPHINCS- is non-standard: keccak256 instead of SHAKE256 (breaks FIPS 205), bounded signature count (2^14 to 2^20 vs. the standard’s 2^64), no matching NIST parameter sets. It would be interesting for NIST to consider specifying the hypertree structure and parameters independently of the hash instantiation (eg. the NIST SHA-3 permutation without SHAKE’s sponge padding or with Poseidon). Alternatively, publishing guidance on how implementers may perform hash-function substitution while maintaining the security properties of SLH-DSA would also be appreciated.
That said, the gap with the standard is narrowing. NIST is actively working on smaller SLH-DSA parameter sets [9 & 10] with a 2^24 signature limit (rls128cs1, rls192cs1, rls256cs1) targeting certificate and firmware signing. NIST recently released new parameters set in Special Publication 800 [11] with the initial public draft for the 128-24 variants that we used. SPHINCS- operates in the same design space from 2^14 to 2^20, and the techniques developed here keccak substitution, EVM gas modelling, WOTS+C/FORS+C compression would also apply to any future standardised small-budget SLH-DSA parameter set.
In the future, the underlying hash function should be ZK friendly to fit the zkEVM constraints. We name this future variant “leanSPHINCS”.
This is also where protocol-level aggregation enters the picture. A recent draft EIP, “Frame type for PQ sig and STARK aggregation,” lets transactions declare lightweight (scheme, data_hash, verification_key) dependencies instead of carrying signatures on-chain; mempool nodes and builders fold these off-chain into a single recursive STARK in the block header. A leanSPHINCS verification then costs 3,000 gas at the frame level because verification is paid once by the prover, not re-executed by every node. The catch is the ZK-friendly hash requirement: keccak is orders of magnitude more expensive to arithmetize, so only leanSPHINCS verifies natively inside the aggregation circuit. A keccak-based SPHINCS- signature could still ride the pipeline, but must first be STARK-wrapped client-side, shifting that one-off proving cost onto the signer’s device.
In the meanwhile SPHINCS- could be a bridge: the most gas-efficient hash based PQ option deployable today, without waiting for any protocol change. The hardware wallet constraint is addressed in a companion post on JARDIN (publication soon™), which reduces compact signing to 3 seconds on ST secure elements.
References
[1] R. Babbush et al. “Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities.” arXiv:2603.28846, 2026. https://arxiv.org/abs/2603.28846
[2] National Institute of Standards and Technology. “Module-Lattice-Based Digital Signature Standard.” FIPS 204, August 2024. https://csrc.nist.gov/pubs/fips/204/final
[3] National Institute of Standards and Technology. “Stateless Hash-Based Digital Signature Standard.” FIPS 205, August 2024. https://csrc.nist.gov/pubs/fips/205/final
[4] J. Drake, D. Khovratovich, M. Kudinov, and B. Wagner. “Hash-Based Multi-Signatures for Post-Quantum Ethereum.” ePrint 2025/055, 2025. https://eprint.iacr.org/2025/055
[5] M. Kudinov and J. Nick. “Hash-based Signature Schemes for Bitcoin.” ePrint 2025/2203, 2025. https://eprint.iacr.org/2025/2203
[6] J. Nick. “SHRINCS: 324-byte stateful post-quantum signatures with static backups.” Delving Bitcoin, December 2025. https://delvingbitcoin.org/t/shrincs-324-byte-stateful-post-quantum-signatures-with-static-backups/2158
[7] J. Nick. “SHRIMPS: 2.5 KB post-quantum signatures across multiple stateful devices.” Delving Bitcoin, March 2026. https://delvingbitcoin.org/t/shrimps-2-5-kb-post-quantum-signatures-across-multiple-stateful-devices/2355
[8] EIP-8141: Frame Transactions https://eips.ethereum.org/EIPS/eip-8141
[9] J. Dang. “SPHINCS+ Smaller Parameter Sets.” NIST PQC Seminar, 2025. https://csrc.nist.gov/csrc/media/presentations/2025/sphincs-smaller-parameter-sets/sphincs-dang_2.2.pdf
[10] Scott Fluhrer & Quynh Dang “Smaller Sphincs+ or, Honey, I Shrunk the Signatures.” ePrint 2024/018, 2024 https://eprint.iacr.org/2024/018.pdf.
[11] NIST Special Publication 800 Additional SLH-DSA Parameter Sets for Limited-Signature Use Cases Initial Public Draft https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-230.ipd.pdf
[12] ZKnox / Kohaku. “Post-quantum account pattern.” https://github.com/ethereum/kohaku/tree/master/packages/pq-account/lib