Lux Proposals
← All proposals
LP-0021Final

LP-021: THBS-SE — Selected-Element Threshold SLH-DSA for Permissionless Chains

Abstract

THBS-SE (Threshold Hash-Based Signatures with Selected-Element

Reconstruction) is the v1 construction that produces a FIPS 205

SLH-DSA signature from a t-of-n committee on a public-BFT chain

without a TEE, without a designated aggregator, and with no

long-lived secret material outside party-local Shamir leaves. The

construction's central insight: threshold only the per-signature

FORS / WOTS+ atoms that the final signature reveals anyway, and

never reconstruct the master seed. The wire output is byte-

identical to a single-party FIPS 205 signature; unmodified

cloudflare/circl/sign/slhdsa.Verify accepts it.

Motivation

SLH-DSA (FIPS 205) is the canonical post-quantum hash-based

signature standard. It is also notoriously hard to threshold: the

secret key is a single 32-byte seed S, and the FIPS 205 sign

procedure deterministically derives the WOTS+ chain bases and FORS

leaves from S. Any t-of-n construction that reconstructs S — even

transiently — places S in the memory of whichever party computes

the final signature.

Two well-known obstructions from the literature:

v1 bypasses this obstruction with a different decomposition: the

construction never tries to threshold the WHOLE seed. It thresholds

only the per-signature material the signature reveals to the

verifier anyway, and binds the share-reconstruction to the

specific slot the signature signs at.

A v1.0 honest open item: the strict-atom-assembly path (assembling

the FIPS 205 signature directly from per-atom share

reconstructions of message-selected FORS leaves and WOTS+ chain

bases, bypassing the canonical slh_sign_internal procedure

entirely) requires a Magnetar-internal re-implementation of FIPS

205 §5/§6.2/§7/§8 because cloudflare/circl/slhdsa does not

expose these as public APIs. v1.0 ships a PUBLIC COMBINER path: the

seed is briefly present in the combiner's memory for one

slhdsa.SignDeterministic call and is zeroized before return; the

combiner role is PUBLIC (anyone can be the combiner, no privileged

aggregator). This is materially stronger than a TEE-attested

privileged-aggregator model (no host in the TCB) and materially

weaker than the strict invariant. The strict path is the

Magnetar v1.1 work item.

Specification

Construction shape

1. Committee selection. Public randomness (the v1 randomness

beacon at LP-176, plus per-slot domain-separated derivation)

selects an over-committee of size n with threshold t. The

over-committee tolerates n - t silent withholders.

2. Leaderless PVSS / DKG for the slot-local key. v1.0 ships a

reference setup with a deterministic dealer pattern; production

deployments run the leaderless publicly-verifiable secret

sharing path. Either path's output: a slot-local SLH-DSA seed

S, byte-wise Shamir-shared across (n, t) via GF(257), with

(PK, SK) derived from S. After setup, no party holds S;

each party holds its own share share_i.

3. Joint SLH-DSA root commitment. (PK, committee, n, t) is

published as the slot-local public material. The PK is what

external verifiers check signatures against.

4. Round-1 commitments. Party p_i samples per-round mask

r_i, computes the masked share s'_i = share_i XOR r_i, and

broadcasts a commitment


   D_i = cSHAKE256(r_i || s'_i || tau)

where tau is the slot binding encoding plus the message plus

the party ID. The broadcast carries `(party_id, slot_id, D_i,

availability_bit). Each party persists (slot_id, H(slot_id ||

msg))` in its local slot guard.

5. Round-2 selected-atom Shamir reveals. After Round-1 quorum

is observable, each party reveals PartialSig = r_i || s'_i.

Idempotent replay: re-issuing Round 1+2 for the same `(slot_id,

msg)` returns the persisted messages; a genuine equivocation

attempt (same slot_id, different msg) raises

ThbsSeEquivocationError without emitting the second message.

6. Public combiner. Any party (validator, block proposer, RPC

node, passive watcher) collects >= t Round-2 reveals. For

each, the combiner re-derives D_i from the partial sig + slot

binding + message + party ID; a mismatch produces a typed

ThbsSeShareEvidence blob carrying

reason = ThbsSeShareCommitMismatch. Valid reveals are XOR'd to

recover each party's share_i. The seed is Lagrange-interpolated

over GF(257) via shamirReconstructGF. The FIPS 205 ctx is

bound via


   ctx = tagThbsSeCtxPrefix || slot_id   (32 bytes, ≤ 255 per FIPS 205 §10.2)

The combiner calls slhdsa.SignDeterministic(seed, msg, ctx),

zeroizes the seed + intermediates, and returns the

magnetar.Signature{Mode, FIPS 205 wire bytes} blob.

7. Verification. Standard FIPS 205 verify:

slhdsa.Verify(pk, msg, sig, ctx). The reference exposes this

as VerifyBytesCtx (~/work/lux/magnetar/ref/go/pkg/magnetar/wire.go)

for stateless dispatch.

The hard invariant

The construction's load-bearing invariant (verbatim from

thbsse.go:60-61):

> "A revealed value is allowed only if it is also present in the

> final SLH-DSA signature."

Allowed reveals (encoded in the canonical wire shape)

Forbidden reveals (enforced)

Enforcement points:

Wire byte-identity theorem

The output of Combine on >= t valid Round-2 reveals is byte-

identical to the output of `slhdsa.SignDeterministic(seed, msg,

ctx)` on the original (seed, msg, ctx) tuple. The byte-identity

holds because:

The load-bearing gate is

~/work/lux/magnetar/ref/go/pkg/magnetar/thbsse_test.go::TestThbsSE_Wire_FIPS205Verifiable

(declared at line 99). The test:

1. Generates a committee.

2. Runs the full Setup → Round-1 → Round-2 → Combine ceremony.

3. Strips the MAGS frame from the output.

4. Calls `cloudflare/circl/sign/slhdsa.Verify(pk, msg, payload,

ctx)`.

5. Asserts the verify returns true across all three FIPS 205

parameter sets (M192s, M192f, M256s).

A wire change that breaks this test breaks FIPS 205 byte-identity

and is a v1 regression.

Slot binding

Every signature is bound to a slot tuple


(chain_id, epoch, slot, height, committee_id, message_domain)

The binding flows into:

This means the same committee CANNOT reuse the same share material

at a different slot, and any verifier holding the slot tuple can

derive ctx and call FIPS 205 Verify directly. The slot binding

is part of the verification interface, not an implementation

detail.

Slot guard and equivocation evidence

Each party tracks the set of slots it has already signed at via

ThbsSeSlotGuard. A second signature attempt at the same slot

under a different message hash is REFUSED locally and produces a

slashable ThbsSeEquivocationError carrying a public-form

ThbsSeEvidence blob the consensus layer consumes. The evidence

is publicly verifiable via VerifyThbsSeEvidence — a pure

function, no committee state required.

Over-selected committee

(n, t) with n > t tolerates up to n - t silent withholders.

Combine picks any t valid Round-2 reveals; the Lagrange

interpolation is determined by any t evaluation points.

Disjoint sub-quora of size t produce byte-equal signatures

(deterministic public combiner).

This is the v1 liveness guarantee on the THBS-SE path: a

permissionless chain can lose up to n - t validators in a slot

and still finalize. The cert at PQ-heavy mode (LP-217; was the

Polaris cert composition in LP-017, historical) inherits this

liveness for its Magnetar leg.

Public-BFT state hygiene

The construction's safety on a public-BFT chain rests on five

pieces of state hygiene:

1. Slot binding (§Slot-binding) — the FIPS 205 ctx is the

verifier-side encoding of the slot tuple; reuse across slots is

detectable by anyone holding the slot tuple.

2. Slashing evidence — both equivocation evidence and share-

commit-mismatch evidence are typed, public, and consumed by

the consensus layer via VerifyThbsSeEvidence /

VerifyThbsSeShareEvidence.

3. Over-selected committee — silent withholders cannot stall

the slot; honest sub-quora produce the same signature.

4. Public combiner — no privileged aggregator role. Any peer

can produce the final signature from valid Round-2 reveals.

The combine is a pure function.

5. Idempotent replay — re-issuing the same (slot_id, msg)

ceremony is a no-op; genuine equivocation (same slot_id,

different msg) is detected and produces slashable evidence

instead of a second signature.

Why this bypasses Cozzo-Smart / Bonte-Smart-Tan

The Cozzo-Smart obstruction targets schemes that try to threshold

the FULL seed-to-signature computation. THBS-SE does not. It

thresholds only the per-signature material the signature reveals.

The seed reconstruction in Combine is on the public-combiner

side, not on any privileged-aggregator side; the seed is briefly

present in the combiner's memory and zeroized.

The Bonte-Smart-Tan obstruction reinforces the seed-threshold

issue for hash-based schemes specifically. THBS-SE's response is

to make the combiner role PUBLIC: no single party is privileged,

so no single party's memory-disclosure event reveals the seed to

any party with a privileged-trust position. A peer-local memory-

disclosure adversary at exactly the combine moment could observe

the seed; this is the v1.0 honest open item, addressed by the

v1.1 strict-atom-assembly path.

The crucial v1 point: THBS-SE achieves FIPS 205 wire byte-identity

without a TEE. The TEE-only extension (LP-020 slhdsa-tee) is

required when the threat model demands "seed never in any host's

memory"; the public-BFT path of THBS-SE is the construction for

when the threat model is "no privileged party".

Pin to magnetar v1.0.0

The production code path for THBS-SE is

~/work/lux/magnetar/ref/go/pkg/magnetar/thbsse.go. Magnetar

v1.0.0 (tag v1.0.0 at ~/work/lux/magnetar, commit f8268db)

is the v1 release that ships THBS-SE as the canonical

permissionless threshold primitive. Threshold v1.8.10 still pins

magnetar v0.5.2 transitively

(~/work/lux/threshold/go.mod:150); the version bump to v1.0.0

is the in-flight task tracked at the magnetar repo (HONEST OPEN:

the version pin lands as a follow-up commit on threshold's main).

Rationale

Why threshold only the revealed elements

A FIPS 205 SLH-DSA signature reveals a small, message-selected

subset of the hypertree: specific FORS leaves, specific WOTS+

chain bases. Thresholding the WHOLE hypertree is wasteful (most

of it is never revealed) AND hard (the unrevealed branches must

stay private to maintain FIPS 205 security). Thresholding only

the revealed elements is the minimal-information sharing

consistent with FIPS 205 byte-identity.

Why a public combiner

A designated combiner is a single point of failure (liveness) AND

a single privileged trust target (safety). A public combiner

distributes both: any party can produce the signature, so liveness

is committee-bounded, not combiner-bounded; no party is

privileged, so the safety story does not depend on any single

combiner's compute base.

Why slot binding in the ctx

FIPS 205 ctx is a verifier-side input: the relying party MUST

supply ctx that matches the signing-party's ctx. Encoding the

slot binding into ctx means the relying party's verifier check

inherits the slot binding "for free" — no additional protocol

state is needed at verify time.

Why GF(257) for Shamir

GF(257) lets each byte of the 32-byte seed be Shamir-shared

independently. The choice of q = 257 is the smallest prime

greater than 256; reconstruction over GF(257) is byte-wise and

matches the seed's natural byte representation.

Backwards Compatibility

None. v1 is the lock-in. THBS-SE is the v1 permissionless

threshold path for hash-based signatures; no pre-v1 equivalent

exists.

Test Cases

The headline byte-identity gate:

The invariant gates:

KAT vectors at

~/work/lux/magnetar/vectors/thbsse-sign.json pin the ceremony's

deterministic outputs for regression testing.

Reference Implementation

Security Considerations

The v1.0 ship state's HONEST OPEN ITEM: the strictest formulation

of the invariant ("no party or combiner EVER reconstructs SK.seed,

even transiently in memory") requires the strict-atom-assembly

path. v1.0 ships a PUBLIC COMBINER path: the seed is briefly

present in the combiner's memory for one

slhdsa.SignDeterministic call and is zeroized before return.

This is materially STRONGER than a TEE-attested privileged-

aggregator model because no host sits in the TCB and the

combiner role is PUBLIC — anyone can be the combiner on their

own substrate.

This is materially WEAKER than the strict invariant because a

peer-local memory-disclosure adversary at exactly the combine

moment could observe the seed.

The strict-atom-assembly path (assembling the FIPS 205 signature

directly from per-atom share reconstructions of message-selected

FORS leaves and WOTS+ chain bases, bypassing the canonical

slh_sign_internal procedure) requires a Magnetar-internal re-

implementation of FIPS 205 §5 (WOTS+ chain), §6.2 (FORS sign),

§7 (XMSS), §8 (hypertree). cloudflare/circl/slhdsa does not

expose these operations as public APIs. The strict path is

tracked at ~/work/lux/magnetar/BLOCKERS.md::MAGNETAR-STRICT-ATOM-V11.

The slot binding in ctx is load-bearing. A verifier that does

NOT supply the matching ctx will fail to verify a valid signature

AND will accept a signature on a different slot if the wrong ctx

is supplied. The relying party's responsibility is to derive ctx

from the slot tuple it observes on chain, NOT from the signature

itself.

The equivocation evidence path is the slashing pipeline's input.

A party that signs two distinct messages at the same slot

produces evidence VerifyThbsSeEvidence accepts. The consensus

layer's slashing rule consumes this evidence and slashes the

equivocating party's stake.

The over-selected committee tradeoff: a larger n for fixed t

buys liveness (more silent withholders tolerated) but increases

the per-round broadcast cost. v1 deployments tune (n, t) per

slot's value-at-risk; a sovereign L1 with a small value-at-risk

runs (n = 4, t = 3); a high-value L1 runs (n = 21, t = 14).

The PQ-heavy cert (LP-217; was the Polaris cert in LP-017,

historical) consumes whatever (n, t) the L1's spawn tx (LP-018)

bound.

Copyright

Copyright and related rights waived via CC0.