hashsig

⚠ UNAUDITED — NOT FOR PRODUCTION

This is research-grade cryptography. It has not undergone formal security review. Do not use it to secure real funds or production systems. Misuse of stateful hash-based signatures (e.g. state reuse across devices) is catastrophic and silent.

A Go implementation of the hash-based post-quantum signature primitives from Kudinov & Nick, Hash-based Signature Schemes for Bitcoin (IACR eprint 2025/2203, Revision 2025-12-05).

hashsig ships the full primitive stack — tweakable hashes, WOTS+C, balanced and unbalanced XMSS, PORS+FP, Octopus, SPHINCS+ W+C P+FP — together with two composite wrappers:

• SHRINCS — single-device, stateful unbalanced-XMSS primary (~324-byte signatures) with a stateless SPHINCS+ fallback (~4 KB). Paper §B.3.
• SHRIMPS — multi-device, two SPHINCS+ instances under one public key: a compact instance (~2.5 KB) for the per-device common case and a fallback instance (~4 KB) after the compact budget is spent. Delving thread 2355.

Every wire layout matches the paper's description byte-for-byte; committed test vectors pin this across language implementations.

Repository layout

hashsig/
├── spec/                  paper PDF, parameter tables, pseudocode notes
├── test-vectors/          shared KATs (JSON) — cross-language ground truth
├── go/                    Go module (github.com/andrepatta/hashsig/go)
└── cpp/                   C++ scaffold

spec/ and test-vectors/ live at the repo root by design: they are the cross-cutting source of truth that every language implementation consumes.

Packages

Import path	Paper	What it provides
github.com/andrepatta/hashsig/go/internal/hash	§2, §13	SHA-256 tweakable hash family (F, H, T_l, PRF, PRFmsgR), SHA-512 Hmsg, 22-byte compressed ADRS
github.com/andrepatta/hashsig/go/wotsc	§4, §5	WOTS-TW + WOTS+C one-time signatures, with parallel counter grind
github.com/andrepatta/hashsig/go/xmss	§7, §B.3	Balanced XMSS, caterpillar-shaped unbalanced XMSS
github.com/andrepatta/hashsig/go/pors	§10, Alg. 1	PORS+FP few-time signature over a left-filled Merkle tree
github.com/andrepatta/hashsig/go/octopus	§C	Minimal batched authentication set over mixed-depth leaves
github.com/andrepatta/hashsig/go/sphincs	§8, §11	Hypertree XMSS^MT and SPHINCS+ (W+C P+FP) stateless scheme
github.com/andrepatta/hashsig/go/shrincs	§B.3	SHRINCS wrapper: stateful primary + stateless fallback
github.com/andrepatta/hashsig/go/shrimps	—	SHRIMPS wrapper: compact + fallback SPHINCS+ pair
github.com/andrepatta/hashsig/go/hd	§14, Fig. 15	Hardened hierarchical derivation (BIP32-style HMAC-SHA512)
github.com/andrepatta/hashsig/go/state	—	StateIO interface + CRC32 trailer helpers
github.com/andrepatta/hashsig/go/state/filestate	—	Filesystem StateIO (write-to-tmp + fsync + rename)
github.com/andrepatta/hashsig/go/state/advisorylock	—	flock-based cross-process uniqueness wrapper

The module root exposes no API — import a sub-package directly.

Parameter sets

All parameter sets target NIST L1 security (128-bit classical, 64-bit quantum) with a SHA-256 tweakable hash at 16-byte output. Hmsg is SHA-512.

SHRINCS (single-device)

The signer emits the stateful path whenever its body is strictly smaller than the stateless body (paper §B.3 min-rule). At L1 the crossover sits at q = 232; TreeHeight = 8 (NumLeaves = 256) is the smallest power-of-two that covers every usable stateful slot below the crossover.

• Stateful primary — unbalanced XMSS with WOTS+C leaves at (n=16, m=9, w=16, z=0, S=135, rBits=32): ℓ = 18 chains, OTS signature = 292 B.
• Stateless fallback — SPHINCS+ (W+C P+FP) at the paper's bold Table 1 row (H=40, D=5, K=11, a=14, w=256, S=2040, MMax=118): signature = 4036 B.
• Public key — 32 B = PK.seed ‖ H(pk_stateful ‖ pk_stateless).

A SHRINCS-L variant is also available via NewStatefulKeyLiquid, matching the Liquid-optimised tuple from the Blockstream SHRINCS Simplicity verifier.

SHRIMPS (multi-device)

Two SPHINCS+ (W+C P+FP) instances share one PK.seed; the public key commits to the hash of their roots.

• Compact instance — (H=12, D=1, K=8, a=17, w=16, S=240, MMax=105) at q_s = 2^10: signature = 2548 B.
• Fallback instance — same tuple as the SHRINCS fallback above: signature = 4036 B.
• Public key — 32 B = PK.seed ‖ H(pk_compact ‖ pk_fallback).

Signature sizes at a glance

Scheme	Body size	Overhead above inner sig
SHRINCS stateful, q = 0	324 B	16 B sibling pk
SHRINCS stateful, q = 232	4036 B	16 B sibling pk
SHRINCS stateless	4052 B	16 B sibling pk
SHRIMPS compact	2564 B	16 B sibling pk
SHRIMPS fallback	4052 B	16 B sibling pk

The 16-byte sibling-pk tail is the only overhead beyond the raw inner signature. Both composite wrappers ship the active path's signature followed by the sibling instance's 16-byte root; the verifier recovers the active public key from the signature and checks the composite-root binding.

Usage

go get github.com/andrepatta/hashsig/go

SHRINCS

import (
    "context"
    "crypto/rand"

    "github.com/andrepatta/hashsig/go/shrincs"
    "github.com/andrepatta/hashsig/go/state/filestate"
)

var seed [32]byte
_, _ = rand.Read(seed[:])

ctx := context.Background()
key, err := shrincs.NewStatefulKey(ctx, seed,
    filestate.New("/var/lib/wallet/shrincs.state"))
if err != nil {
    // handle
}

sig, err := key.Sign(ctx, msg)
ok := shrincs.Verify(key.PublicKey, msg, sig) // true

Recovery from a mnemonic without trusted state:

restored, _ := shrincs.Restore(ctx, seed)
sig, _ := restored.Sign(ctx, msg) // always the stateless SPHINCS+ fallback

SHRIMPS

import "github.com/andrepatta/hashsig/go/shrimps"

key, err := shrimps.NewKey(ctx, seed, "device-a",
    filestate.New("/var/lib/wallet/shrimps-a.state"),
    /* nDev */ 4, /* nDsig */ 8,
)
defer key.Close()

sig, _ := key.Sign(ctx, msg)
ok := shrimps.Verify(key.PublicKey, msg, sig) // true

A second NewKey with the same (seed, device) pair in the same process returns ErrDeviceInUse — the in-process registry prevents accidental state overlap. Cross-process uniqueness is the caller's responsibility; wrap any StateIO in state/advisorylock to get it.

State management

Stateful signing is unforgiving: the security of SHRINCS's primary path collapses if a single leaf is ever used twice. hashsig defends against this at several layers.

1. Persist before sign. The signer writes q+1 to disk before computing the signature for leaf q. A crash between persist and return wastes one slot but never reuses one.
2. Atomic write-then-rename with parent-dir fsync. filestate writes to <path>.tmp, fsyncs the file, renames, then fsyncs the parent directory.
3. CRC32 trailer. Every persisted body carries a CRC32-IEEE trailer so single-bit corruption is caught on read.
4. Cached-root equality check. The state file stores the two Merkle roots derived from the seed; on load, a mismatch with the in-memory roots signals seed/file mismatch and the load fails closed.
5. Type-level enforcement of the state ≠ LOST predicate. StatefulKey and RestoredKey are distinct types. A RestoredKey has no method that reaches the stateful path — stricter than the paper's runtime predicate, and not bypassable by caller mistake.

Callers who need cross-process exclusion can wrap any StateIO in state/advisorylock, which takes an exclusive flock at open time and releases it at close.

Test vectors

test-vectors/*.json is the cross-language conformance contract. Each file is a deterministic set of known-answer tests produced from the Go reference implementation.

File	Coverage
hash.json	SHA-256 tweakable hash family, ADRS layout
wotsc.json	baseW, WOTS-TW + WOTS+C roundtrips, BE counter-pack widths
xmss.json	Balanced + unbalanced XMSS roundtrips, UXMSS auth-path sizes
pors.json	HashToSubset, balanced + unbalanced tree shape, roundtrip
octopus.json	Paper Figure 21 example verbatim, mixed-depth cases
sphincs.json	Paper Table 1 q_s ∈ {2^30, 2^40} and Table 2 q_s = 2^20 size oracles, plus byte-exact roundtrips at SHRIMPS compact and SHRINCS/SHRIMPS fallback
hd.json	Hardened hierarchical-derivation KATs
shrincs.json	Composite pubkey, stateful roundtrips at q ∈ {0, 1, 232}, stateless roundtrip, state-file layout, dispatch-boundary cases
shrimps.json	Composite pubkey, compact + fallback roundtrips, state-file layout, length-dispatch disjointness

make vectors   # regenerate from Go reference implementation
make check     # re-run Go tests against committed vectors (catches drift)

A failing make check after make vectors signals non-determinism in the implementation and must be investigated, not papered over.

Development

make build     # cd go && go build ./...
make test      # cd go && go test ./...
make vet       # cd go && go vet ./...
make lint      # cd go && golangci-lint run ./...
make tidy      # cd go && go mod tidy

Go commands run from the go/ subdirectory (module github.com/andrepatta/hashsig/go). See CONTRIBUTING.md for project invariants.

Status

Shipped

Primitives

• SHA-256 tweakable hash family (F, H, T_l, PRF, PRFmsgR) + SHA-512 Hmsg (§2, §13)
• 22-byte compressed ADRS (SPHINCS+ SHA-256 layout), address types 0..6 + WOTS+C T* = 7
• WOTS-TW (§4) — baseW decode, checksum chains, chain function, keygen, sign, verify
• WOTS+C (§5) — trial-hash predicate (sum = S, last z digits zero), ℓ = len1 − z chains signed, verifier-side completion. Reject of unreachable len1·log₂w > 8·N regime at construction
• Parallel-deterministic WOTS+C counter grind (returns the smallest valid counter)
• Balanced XMSS (§7) with either WOTS-TW or WOTS+C leaves
• XMSS^MT hypertree (§8)
• Unbalanced (caterpillar-shaped) XMSS (§B.3)
• PORS+FP (§10, Algorithm 1) with left-filled tree for non-power-of-two k
• Octopus (§C) generalised to mixed-depth leaves
• SPHINCS+ W+C P+FP (§11) outer grinding via R = PRFmsg(SK.prf, opt, m, counter) — counter inside PRFmsg, no wire counter
• SPHINCS+.PKFromSig factored out of Verify for composite-scheme binding

Composite wrappers

• SHRINCS stateful primary + stateless fallback, pk = H(pk_stateful ‖ pk_stateless), thread-literal 16-byte sibling overhead
• SHRINCS-L (Liquid-optimised) variant via NewStatefulKeyLiquid
• SHRIMPS two-instance wrapper, thread-literal [SPHINCS+ sig][16 B sibling] wire, length-dispatched between compact and fallback
• SHRIMPS compact at w=256 factory (smaller signatures at higher per-chain verify cost)
• StatefulKeyPool for paper §14 precomputed key pool, one sub-seed per member via hardened HD
• RestoredKey type split enforces "state ≠ LOST" at compile time, stricter than paper's runtime predicate

State persistence

• StateIO interface + CRC32-IEEE trailer
• Atomic filesystem backend (write-to-tmp + fsync + rename + parent-dir fsync)
• Persist-before-sign ordering for SHRINCS stateful path
• Advisory-flock StateIO wrapper for cross-process uniqueness
• Cached-root equality check on load (catches seed/file mismatch)

HD derivation

• Hardened-only hierarchical derivation (§14, Fig. 15) — BIP32-style HMAC-SHA512 with hashsig-specific master label
• DeriveMaster, DeriveChild, DerivePath API
• Consumed by StatefulKeyPool for per-member sub-seeds

Test vectors (cross-language conformance)

• hash.json — F / H / T_l / PRF / PRFmsgR / Hmsg roundtrips + ADRS layout
• wotsc.json — baseW, sizes, WOTS-TW + WOTS+C roundtrips, BE counter-pack at 6 widths
• xmss.json — balanced + unbalanced roundtrips, UXMSS auth-path-length map
• pors.json — HashToSubset edge cases, balanced + unbalanced tree shape, roundtrip
• octopus.json — paper Figure 21 verbatim, mixed-depth cases
• sphincs.json — paper Table 1 q_s ∈ {2^30, 2^40} oracles, Table 2 q_s = 2^20 oracles at w ∈ {16, 256}, SHRIMPS compact alternative (k, a) rows at q_s ∈ {2^5, 2^10, 2^12, 2^14}, SHRIMPS compact w=256 oracle, byte-exact roundtrips
• hd.json — master + child + path derivation KATs
• shrincs.json — pubkey, stateful roundtrips at q ∈ {0, 1, 232}, stateless roundtrip, state-file body at ctr ∈ {0, 1, 255}, CRC trailer, dispatch-boundary cases at q ∈ {0, 231, 232, 233}
• shrimps.json — pubkey, compact + fallback roundtrips, state-file body, length-dispatch disjointness
• CI guard: make vectors against a clean checkout fails the build if any committed KAT drifts

Design notes (in spec/notes/)

• Hybrid SHRINCS + SHRIMPS composite construction (three-path commitment + tag-byte dispatch)
• Static-backup sweep (shared recovery-pk across a key-set, consensus-layer sketch)

In progress

• Replace flat SHA-256(seed ‖ label) sub-seed derivation inside shrincs.NewStatefulKey and shrimps.NewKey with hd.DeriveChild / hd.DeriveMaster. The HD primitive is shipped and already consumed by StatefulKeyPool; wiring it into the wrapper constructors changes every downstream signature byte, so the change moves separately from the primitive's landing.

Deferred

• StrictSingleUse mode on shrimps.Key — wallet-layer rotation discipline is the current answer; the doc.go note explains the savings model. Reopen if a downstream caller needs library-level enforcement.
• TPM-backed rollback detection (hash(state) stored in an NV slot) — FileStateIO catches CRC-level corruption but not a deliberate restore of an older backup. The advisory-flock wrapper covers the cross-process case.
• OS-keyring / secret-service monotonic-counter tag as an alternative rollback guard — neither paper nor threads prescribe a specific mechanism.
• BDS / BDSFix tree traversal (§B.2) for UXMSS signing — correctness-safe under the current naïve regeneration (a few ms at NumLeaves = 256), so purely a performance item.
• Incremental per-layer caching inside the SPHINCS+ hypertree signer — the fallback params (h=40, d=5) rebuild every layer per signature. Performance-only.
• Public-API constructors for alternative paper parameter rows. Size oracles and package-private factories exist for paper Table 1 q_s = 2^30, Table 2 q_s = 2^20 at w ∈ {16, 256}, SHRIMPS compact alternatives at q_s ∈ {2^5, 2^12, 2^14}, and SHRIMPS compact at w = 256. Exposing them as NewKeyAt… entry points is gated on a concrete caller.
• go/hybrid/ package implementing the three-path SHRINCS + SHRIMPS composite. Design note at spec/notes/hybrid-shrincs-shrimps.md specifies the commitment structure (Option B: nested, stateful paired outside) and tag-byte dispatch. All cryptographic primitives the composite needs are shipped.
• go/state/tpmstate/ package for the TPM design above.

Out of scope (paper-deprioritised for Bitcoin use)

• TL-WOTS-TW (§6, Appendix A) — paper: "signature size is a primary constraint for Bitcoin … we do not consider it further"
• FORS and FORS+C (§9) — PORS+FP strictly dominates per §10; hashsig commits to PORS+FP
• Raw Lamport OTS (§3) — pedagogical only
• Multi-OTS/FTS multi-signature (§15.1) — consensus-layer construction
• Distributed / threshold signatures (§15.2, §15.3) — paper flags the CRV storage cost and MPC overhead as unreasonable at Bitcoin scale
• Non-hardened HD derivation — paper §14 argues it cannot work for hash-based pks without new hardness assumptions
• Directionless / lexi-sorted XMSS privacy variant — paper does not standardise; security proofs would need redoing
• Cross-input signature aggregation — consensus-layer concern
• Plain SPX and Table 1 F+C rows — SPX is the SLH-DSA baseline hashsig compares against, not a configuration it proposes; F+C variants use an FTS that PORS+FP dominates

Scope

In scope. Primitives and composite wrappers for the paper's W+C P+FP flavour of SPHINCS+, the §B.3 unbalanced-tree construction, and the two stateful composites built on top (SHRINCS, SHRIMPS). Supporting machinery: hardened HD derivation, CRC-verified state persistence, advisory-lock cross-process uniqueness.

Out of scope. Bitcoin-layer code — transaction hashing, script interpreter, address encoding, mempool primitives. hashsig ships signature primitives only; consumers write the chain-layer glue in their project.

hashsig commits to the subset of the paper the authors recommend for Bitcoin-style use: WOTS+C at every hypertree layer, PORS+FP at the bottom (paper §10: PORS+FP strictly dominates FORS+C on size), and parameter sets tuned for 2^10–2^40 signatures per public key rather than the NIST standardisation target of 2^64. The paper's SLH-DSA baseline row, TL-WOTS-TW (§6, paper: "signature size is a primary constraint for Bitcoin … we do not consider it further"), FORS+C, raw Lamport OTS, and general-purpose multi-signature and threshold constructions are described in the paper but are either deprioritised there for Bitcoin use or dominated by a variant hashsig already ships.

References

• Paper: Kudinov & Nick, Hash-based Signature Schemes for Bitcoin, IACR eprint 2025/2203, Revision 2025-12-05. https://eprint.iacr.org/2025/2203
• SHRINCS discussion: https://delvingbitcoin.org/t/shrincs-324-byte-stateful-post-quantum-signatures-with-static-backups/2158
• SHRINCS announcement: https://blog.blockstream.com/shrincs-324-byte-stateful-post-quantum-signatures-with-static-backups/
• SHRIMPS discussion: https://delvingbitcoin.org/t/shrimps-2-5-kb-post-quantum-signatures-across-multiple-stateful-devices/2355
• SHRINCS Simplicity verifier: https://github.com/BlockstreamResearch/shrincs-simplicity-verifier
• Parameter-exploration scripts: https://github.com/BlockstreamResearch/SPHINCS-Parameters

License

MIT — see LICENSE.