SHRINCS: 324-byte stateful post-quantum signatures with static backups

[jonasnick]

Abstract: Stateful hash-based signature schemes can be very efficient when the number of signatures generated by a public key is small. One major problem with stateful schemes is that the state needs to be backed up and updated correctly after every signing operation. By using a straightforward combination of a stateless hash-based scheme (such as a variant of SPHINCS+) and an unbalanced XMSS tree of one-time signatures (stateful), we obtain a scheme that we call SHRINCS. It is extremely efficient when only a few signatures are required and can be backed up with a static seed. More precisely, the SHRINCS public key is a hash of the stateful and stateless public keys. We assume key generation happens on a signing device that is able to keep state securely. Therefore, the signing device can use efficient stateful signatures to sign for the public key. When the state is known to be corrupted or lost, for example when a static seed backup has been restored, the signing device only uses stateless signatures. As a result, SHRINCS provides the efficiency of stateful signatures during normal operation while maintaining the robustness of stateless signatures as a fallback.

SHRINCS

SHRINCS is briefly covered deep in the appendix of our report “Hash-based Signatures for Bitcoin” (Hash-based Signature Schemes for Bitcoin) by Mikhail Kudinov and myself. This post gives a fuller explanation and invites feedback.

The construction of SHRINCS requires a stateless signature scheme and a stateful signature scheme that generates small signatures. SHRINCS consists of the following algorithms:

• \textsf{KeyGen}() \rightarrow (\mathit{seed}, \mathit{pk}, \mathit{state}): The keygen algorithm draws a master seed, derives secret keys \mathit{sk}_1 and \mathit{sk}_2 for the stateful and stateless signature schemes, respectively. Using these, it generates public keys \mathit{pk}_1 and \mathit{pk}_2 for the stateful and stateless schemes. Finally, \textsf{KeyGen} returns the tuple (\mathit{seed}, \mathit{pk}, \mathit{state}) where \mathit{pk} = H(\mathit{pk}_1, \mathit{pk}_2) and \mathit{state} is the initial state of the stateful scheme.
• \textsf{Restore}(\mathit{seed}) \rightarrow (\mathit{seed}, \mathit{pk}, \mathit{state}): The restore algorithm rederives the SHRINCS public key \mathit{pk}, sets \mathit{state} to \textsf{LOST} and returns the tuple (\mathit{seed}, \mathit{pk}, \mathit{state}).
• \textsf{Sign}(\mathit{seed}, \mathit{state}, m) \rightarrow (\mathit{state}', \mathit{sig}): If \mathit{state} \neq \textsf{LOST}, the signing algorithm rederives \mathit{sk}_1 and \mathit{pk}_2 and runs the \textsf{Sign} algorithm of the stateful scheme with \mathit{sk}_1, \mathit{state} and message m. Then, it returns the updated state \mathit{state}' along with the signature concatenated with \mathit{pk}_2. Otherwise, the signing algorithm rederives \mathit{sk}_2 and \mathit{pk}_1, runs the \textsf{Sign} algorithm of the stateless scheme with \mathit{sk}_2 and m, and returns \mathit{state}' = \mathit{state} and the signature concatenated with \mathit{pk}_1.
• \textsf{Verify}(\mathit{pk}, m, \mathit{sig}) \rightarrow \{\textsf{true}, \textsf{false}\}: The verification algorithm parses \mathit{sig} as \mathit{sig}' \| \mathit{pk}', verifies \mathit{sig}' according to the stateless or stateful scheme (which recovers the signing public key in hash-based schemes), and checks that the two public keys hash to \mathit{pk}.

So, when a signing device capable of maintaining state securely is initialized, it signs with the stateful scheme, but whenever a device is restored with the seed, it only signs with the stateless scheme. Because the stateful path is much more efficient in SHRINCS, signing from a restored device is much more expensive than from the device that originally ran \textsf{KeyGen}.

For the stateless signature scheme in SHRINCS, candidates include SLH-DSA or one of the variants of SPHINCS+ that we cover in detail in the report. Depending on the parameters, signature size is between 3KB and 8KB and the public key is 16 bytes (at NIST security level 1). For the stateful scheme SHRINCS uses what we call “unbalanced XMSS”. A regular XMSS public key is essentially a Merkle tree of one-time signature (OTS) public keys. A one-time signature scheme can generate no more than a single signature for a public key, otherwise it becomes insecure. So, the signing state is just the number of signatures that have already been produced, initialized at q=0. To sign a message in XMSS, the signer increments q, produces a signature with the q-th one-time public key in the Merkle tree, and computes the authentication path (aka “Merkle proof”) to the root. The final signature is essentially the one-time signature concatenated with the authentication path.

Instead of using a balanced Merkle tree of OTSs, we use an unbalanced tree for the stateful part of SHRINCS. Thus, the first OTS is at depth 1, the second OTS at depth 2 and so on. This minimizes authentication path length for early signatures, which is optimal when few signatures are expected. The q-th signature for this “unbalanced XMSS” scheme is the q-th OTS signature and its authentication path. At NIST security level 1, the size of the authentication path is q \cdot 16 bytes and the size of the OTS signature is 292 bytes. More precisely, for the OTS we use WOTS+C (for details, check the paper).

Putting it all together, when signing with intact state, the signature size of SHRINCS is \min(292 + q \cdot 16, s_l) + 16 where q is the number of signatures that have been generated for the public key through the stateful path and s_l is the size of signatures generated with the stateless scheme. For q = 1 this signature is more than 11x smaller than the smallest NIST-standardized scheme (ML-DSA). I’d expect that average q for regular Bitcoin wallets is between 1 and 2. The main downside of SHRINCS remains that security requires secure state management. However, unlike pure stateful schemes where state mismanagement can be catastrophic, if in doubt, SHRINCS signers can always fall back to the stateless path.

[moonsettler]

128 bit sounds a bit small for PQC. that’s 64 bits against Grover’s. per envelope bytes ofc. and this would be against short range attacks…

[jonasnick]

128 bit corresponds to “security level 1” as defined in NIST’s PQC evaluation criteria. We have a section in the report arguing that Level 1 already provides considerable security. In summary, “64 bits against Grover’s” does not take into account the hash function circuit evaluation required in each Grover iteration. The current best circuit for SHA-256 has a depth of 2^{14} gates. Moreover, Grover’s algorithm doesn’t parallelize well: running it on k machines only gives a \sqrt{k} speedup. If you assume quantum computers can evaluate 2^{64} gates in a decade (roughly matching the number of cycles my laptop can perform), you’d need 268 million quantum computers running Grover’s algorithm for a decade.

That said, SHRINCS at NIST security level 3 (192-bit classical / 96-bit quantum) would have signature size of \min(612 + q \cdot 24, s_l) + 24 bytes, so 660 bytes for q = 1: with Winternitz parameter w = 256, we get l = 192/8 = 24 chains, each with 24-byte output. Including 32-byte randomness and 4-byte counter, WOTS+C’s signature size is 24 \times 24 + 32 + 4 = 612 bytes.

[moonsettler]

What has been bothering me about WOTS is that one could build an ASIC, that given a WOTS signature starts churning an alternative, by mutating the message, that would produce a valid envelope where every byte is >= than the original. And that it would be perfectly in the realm of possibility for it to find a collision at sufficient scale. Small checksums only seem to make finding a collision marginally more difficult. Not very convincing given the difficulty bitcoin miners are working with.

Or am I missing something?

Sadly the only way I found to make the WOTS signature 100% immutable is to double the envelope and signature size, where every byte of the message digest is accompanied by it’s modulo negated value as well, that means to move any forward the hash chain, an other would need to be moved backward (which is a preimage problem). While this doubles the size and computation cost, but it would still be significantly more compact than Lamport.

edit: Never mind!

[jonasnick]

I’m not sure if I understand your attack exactly, but it seems like this is prevented by the checksum. Any alternative message m' that is not equal to the original message m and where each digit of m' is greater than or equal the corresponding digit in m is guaranteed to have a smaller checksum. Thus, in WOTS+C, verification would fail because this checksum would not match the hardcoded checksum. In WOTS, creating a valid signature would require revealing a preimage in one of the checksum chains.

[moonsettler]

OK, got it! I was thinking of hash based checksums (clearly the wrong approach here). But instead what you do is sum up their modulo negated values which is guaranteed to be smaller if you walk any chain forward and it’s only like 2 bytes.

[conduition]

I really like this! I have always felt that a balance could be struck between stateful and stateless hash-based signing, and SHRINCS does that very neatly. Also as a side effect, SHRINCS discourages address reuse because transactions get more expensive the more you reuse an address.

I think users could accept the possibility of the highly-expensive stateless SPHINCS signature, provided it is only a fallback in the event they lose their wallet state.

I do see some pitfalls though, common to any stateful scheme. A fault injection attack could be disastrous. For example, if a host computer could cause a hardware wallet to accidentally reset its state by strategic power-cycling, then the wallet might sign a message with a reused XMSS leaf, permitting forgery. Or consider cases where users duplicate the same wallet seed onto different devices. It’d be easy for them to accidentally sign and publish two different transactions with the same XMSS leaf.

These aren’t intractable, just novel for bitcoiners to contend with. Perhaps wallet devs would gladly grapple these dragons if it means offering low-cost transactions.

---

Another way to frame SHRINCS would be to standardize two schemes in tapscript: SPHINCS (or a variant), and WOTS, and let wallets decide which to use and how to structure them inside script trees. After all, an XMSS tree structure is more or less the same as taproot’s script trees, except that taproot tree nodes are lexi-sorted before hashing, and lack the context-specific hash-tweaking that XMSS typically has.

Although not as pretty or unified as a single signing scheme, this would be more modular, and thus easier to standardize as BIPs. We can adopt one or the other piecemeal by redefining opcodes, instead of fully committing to both at once.

[jonasnick]

Thanks @conduition for the feedback.

Or consider cases where users duplicate the same wallet seed onto different devices.

Just to clarify the intended SHRINCS functionality as currently described: when a device imports a wallet seed, it must always use the stateless signing path. Only the device that originally generated the seed is permitted to use the stateful path. This is definitely a restriction which would need to be relaxed to allow fully offline seed generation, for example.

host computer could cause a hardware wallet to accidentally reset its state by strategic power-cycling

I agree that there are still pitfalls like this. It would be very interesting to hear from hardware wallet developers about how feasible it is in practice to keep state securely.

Another way to frame SHRINCS would be to standardize two schemes in tapscript and let wallets decide which to use and how to structure them inside script trees

So this would effectively introduce OP_SPHINCS and OP_WOTS rather than a single OP_SHRINCS, and let wallets implement the SHRINCS scheme via the Taproot tree. I agree this is a valid approach.

I also think a standalone OP_SPHINCS could be valuable on its own, since some wallets may want to use a hash-based signature scheme but cannot keep state at all. Are there other use cases you have in mind that would particularly benefit from this modularity?

One downside of letting wallets decide the tree structure is that it can leave fingerprints on the blockchain that are harmful to privacy. It’s also slightly less efficient compared to OP_SHRINCS (because of the 16-byte hashes at NIST level one, compared to 32-byte hashes in the Taproot tree).

[conduition]

Just to clarify the intended SHRINCS functionality as currently described: when a device imports a wallet seed, it must always use the stateless signing path.

Unfortunately wallet software can’t always be 100% certain whether its seed is in use on multiple devices. Users can copy wallet data files between computers, or even do so accidentally, such as when cloning an entire operating system during a recovery from full-disk backup. As a real-world case-study, consider the unfortunate souls who’ve lost coins to punishment transactions, as a result of restoring outdated states for lightning channels.

Unlike with lightning though, a SHRINCS wallet may have some indication that state has been lost or corrupted. E.g. the wallet comes online and sees 10 new outgoing transactions created after the wallet was last opened. The wallet would probably have a chance to react before any grave errors are made.

Another thing to consider is that state management only matters for keys which may have issued XMSS signatures. If state gets corrupted or the seed is imported, hot-wallets could heuristically guess things like: “this address never received any coins before, so we probably have never signed any messages with its XMSS key. Should be safe to use XMSS for this address if we ever end up with UTXOs there”. Obviously this is fraught with risky assumptions on user behavior… but still, neat to have engineering options.

One downside of letting wallets decide the tree structure is that it can leave fingerprints on the blockchain that are harmful to privacy. It’s also slightly less efficient compared to OP_SHRINCS (because of the 16-byte hashes at NIST level one, compared to 32-byte hashes in the Taproot tree).

Fair point. Simple solution for that: Instead of OP_WOTS, deploy OP_XMSS, and set the XMSS protocol to use NIST-1 length hashes with proper tweaking. Though i’m unsure if the savings would be worthwhile given that most wallets should be effectively incentivized to avoid address reuse either way.

Are there other use cases you have in mind that would particularly benefit from this modularity?

Not particularly. It’s an aesthetic/organizational preference from my PoV: Why introduce an opcode which is basically OR(unbalanced_xmss_key, sphincs_key), if we already have tools to handle such binary logic for payment conditions already?

[conduition]

Quick second thought: If we do deploy XMSS as an opcode instead of using taproot+WOTS, then the XMSS merkle branches should be directionless (lexi-sorted before hashing) like taproot trees. The reason is succinctness and privacy.

Vanilla XMSS must reveal the path of the WOTS leaf in the tree which, besides wasting blockspace, means that if you know the tree structure, you also know how many signatures that key has previously issued, and how many it has left.

A directionless balanced XMSS tree obscures that information, or at least makes it ambiguous. An observer who sees a merkle proof for this tree, can’t tell for sure without external data (like previous signatures) whether the signature they’re looking at is the first signature from this key, or the last, or any in between, even if they know the XMSS tree height.

For an unbalanced XMSS tree like in SHRINCS, simply seeing the merkle path length reveals the signature count. But it’s also impossible to tell a balanced directionless XMSS tree from an unbalanced one as an observer. Verifiers don’t need to know, as long as the WOTS signature and authentication path recompute into the correct root hash.

Wallets and users would be free to choose the XMSS tree height and structure on their own, but the final on-chain fingerprint will be mostly indistinguishable from case to case. A directionless XMSS signature from a balanced height=2 tree looks the same as the second signature from an unbalanced tree.

[jonasnick]

Users can copy wallet data files between computers, or even do so accidentally, such as when cloning an entire operating system during a recovery from full-disk backup.

Yes, this is why I mentioned “assume key generation happens on a signing device that is able to keep state securely.” in the original post. It follows that the main deployment target for SHRINCS is dedicated signing devices where users do not have the ability to interfere with the state (intentionally or accidentally).

Thinking out lout (half-baked idea follows): To use SHRINCS wallet on a desktop wallet it seems to be sufficient to find some place to store state that cannot be accidentally backed up. This is not my area of expertise, but it seems like a storage slot on the TPM could potentially be used for that. It provides the following functionality:

• Initialize(secret): Initializes the slot such that it can only be read or written to when the secret is presented.
• Write(secret, data)
• Read(secret) -> data

For security, we require that that the slot can really only be read/written with the secret. Thus, the data won’t be part of a disk backup. Additionally, a Read will never return data that has been written to the slot before the last Write. For efficiency, we want that the slot is persistent (e.g., across reboots).

On my Intel CPU, this sort of slot appears to be relatively easy to instantiate after installing tpm2-tools:

• tpm2_nvdefine "$NV_INDEX" -C o -s "$MAX_SIZE" -a "authread|authwrite|no_da" -p "$AUTH_VALUE" initializes the slot at $NV_INDEX such that the string $AUTH_VALUE is required to read/write.
• echo -n "$DATA_TO_WRITE" | tpm2_nvwrite "$NV_INDEX" -C "$NV_INDEX" -P "$AUTH_VALUE" -i - writes the data.
• tpm2_nvread "$NV_INDEX" -C "$NV_INDEX" -P "$AUTH_VALUE" -o "$OUTPUT_FILE" reads the data.

On NixOS, running the tool from a non-root user requires the user to be in the tss group.

Using the secure slot, the software wallet could work as follows:

• Initialize(): The wallet runs (seed, pk, state) <- SHRINCS.KeyGen(), draws an authentication token t for the secure slot, runs Slot.Initialize(t), Slot.Write(t, hash(state)) and stores (seed, pk, state, t) on disk.
• Sign(m) -> sig: Read (seed, pk, state, t) from disk.
  • If state != LOST: Read h' <- Slot.Read(t). If h' != hash(state), write state := LOST to disk and rerun Sign(m). Otherwise, run (state', sig) <- SHRINCS.Sign(seed, state, m), write hash(state') to the slot, write the updated state’` to disk and return the signature.
  • Else, return SHRINCS.Sign(seed, state, m).

Unfortunately, this isn’t really secure, because the user may run Wallet.Sign in parallel with different messages. Without some sort of lock, both invocations may load the same state from disk and get the same result from the slot.

[conduition]

assume key generation happens on a signing device that is able to keep state securely

Ahhhhh I didn’t realize that assumption included keeping state secure from the user too.

Clever idea with the TPM, though I would simplify it a little. Store only a decryption key in the TPM, and store the state on-disk, but encrypted under that key. If the encrypted state is backed up, it will be missing the TPM’s key, making state decryption impossible. Read/write locking on the encrypted state files can then be managed by the application layer.

Alternatively, store the XMSS key’s seed itself in the TPM. This makes backed-up state files non-toxic, because after restoring the files, it’s impossible to accidentally sign anything. The user would need to input their seed phrase to fully restore the wallet. Wallet devs would have some choice as to how to proceed from there.

Feels weird to engineer a system that makes it harder to recover files.

[jonasnick]

That would be a nice simplification indeed, but if you restore a disk backup (with an old wallet state) on the same machine, the TPM would still have the decryption key or XMSS key. What would prevent reusing that old state for signing?

[conduition]

Ah you’re right, that would be a bad footgun. Maybe one could force the issue by rotating the TPM auth value or decryption key after every new signature, making old disk backups completely invalid? But then we’re back to the same synchronization issue as with your first approach, where two parallel requests would result in a race condition when writing to the TPM. So might as well just use your state commitments idea.

Come to think of it, is there anything special about a TPM in this context besides its isolation from the hard drive? If all you need is an independent authenticated CRUD interface to commit to some state, that interface could be almost anything… a webserver, a database, a nostr relay, a thumb drive, heck maybe you could even use OP_RETURN. Certainly many options to explore here…