Author: Jonasnick
Abstract : Stateful hash-based signatures can be very efficient if the number of signatures generated from the public key is small. A major problem with stateful schemes is the need to back up the state and update it correctly after each signature operation. By directly combining a stateless hash-based scheme (such as a variant of SPHINCS+) with an unbalanced XMSS tree (carrying a one-time signature public key, which is stateful, of course) we obtain a scheme called "SHRINCS". It is very efficient when only a small number of signatures are needed and can be backed up with a static seed. More precisely, the SHRINCS public key is a hash of both the stateful and stateless public keys. We assume that key generation occurs in a signing device capable of securely storing the state. Therefore, this signer can use an efficient stateful signature scheme to generate signatures. When the state is known to be corrupted or lost (for example, when the wallet is restored using a static seed), only a stateless signature scheme can be used. Therefore, SHRINCS utilizes the efficiency of stateful signature schemes in normal operation, while retaining robust stateless signatures as a backup.
SHRINCS
The SHRINCS scheme was briefly introduced in the appendix of my report, " Hash Function-Based Signature Schemes Applicable to Bitcoin ." This article provides a more comprehensive explanation, and feedback is welcome.
The construction of SHRINCS requires a stateless signature scheme and a stateful signature scheme (the latter capable of generating small signatures). SHRINCS consists of the following algorithms:
- $\textsf{KeyGen}() \rightarrow (\mathit{seed}, \mathit{pk}, \mathit{state})$: This key generation algorithm generates a master seed and derives private keys $\mathit{sk}_1$ and $\mathit{sk}_2$, used for stateful and stateless signature schemes, respectively. Using these two private keys, it generates public keys $pk1$ and $pk2$, used for stateful and stateless signatures, respectively. Finally, $KeyGen$ returns the tuple $(\mathit{seed}, \mathit{pk}, \mathit{state})$, where $\mathit{pk} = H(\mathit{pk}_1, \mathit{pk}_2)$, and $state$ is the initial state for stateful signatures.
- $\textsf{Restore}(\mathit{seed}) \rightarrow (\mathit{seed}, \mathit{pk}, \mathit{state})$: The restoration algorithm regenerates the SHRINCS public key from a seed, sets $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}$, then the signature algorithm re-derives the private key $\mathit{sk}_1$ and the public key $\mathit{pk}_2$, and runs the $\textsf{Sign}$ signature algorithm with a stateful signature scheme using $\mathit{sk}_1$, $\mathit{state}$, and the message $m$. Then, it returns the updated state $\mathit{state}'$ and the signature concatenated with $\mathit{pk}_2$. Otherwise (if the state is corrupted), then re-derive the private key $\mathit{sk}_2$ and the public key $\mathit{pk}_1$, and run the stateless signature scheme using $\mathit{sk}_2$ and $m$, returning $\mathit{state}' = \mathit{state}$ and a signature concatenated with $\mathit{pk}_1$.
- $\textsf{Verify}(\mathit{pk}, m, \mathit{sig}) \rightarrow {\textsf{true}, \textsf{false}}$: Verification algorithm, which parses the signature $\mathit{sig}$ into $\mathit{sig}' | \mathit{pk}'$, verifies $\mathit{sig}'$ according to stateless or stateful schemes (in hash function-based signature schemes, this means restoring the public key), and then checks if the hash values of the two public keys are equal to $\mathit{pk}$.
Therefore, after a signer that can preserve state is initialized, it signs using a stateful scheme; however, whenever a device is restored using a seed, it signs only using a stateless scheme. Because the stateful signing mode is much more efficient in SHRINCS, signing with a restored device is much more expensive than signing with the device that initially ran $\textsf{KeyGen}$.
Regarding stateless signature schemes in SHRINCS, candidates include SLH-DSA, or a variant of SPHINCS+ that we detailed in this report. Depending on the parameters, the signature size ranges from 3KB to 8KB, while the public key is 16 bytes (belonging to NIST Security Level 1). As for stateful signature schemes, SHRINCS uses what we call "unbalanced XMSS". A regular XMSS public key is the root of a Merkle tree constructed from numerous one-time signature (OTS) public keys. One-time signature schemes only allow one public key to generate one signature; otherwise, the public key is insecure. Therefore, the signature state is the number of signatures already created, initially $q=0$. To sign a message with XMSS, the signer increments $q$, signs with the $q$-th one-time public key in the Merkle tree, and then calculates the authentication path to the root (the so-called "Merkle evidence"). The final signature is essentially the one-time signature plus the authentication path.
SHRINCS does not directly use an unbalanced Merkle tree composed of one-time signatures (public keys). Instead, it uses an unbalanced tree in the stateful signature scheme portion. Therefore, the first one-time signature public key is at depth 1, the second at depth 2, and so on. This minimizes the length of the authentication path for early signatures, which is ideal for scenarios where only a small number of signatures are expected. For this "unbalanced XMSS" scheme, the $q$-th signature is the $q$-th one-time signature and its authentication path. Under NIST security level 1, the authentication path size is $q \cdot 16$ bytes, while the one-time signature size is 292 bytes. More specifically, the one-time signature scheme we use is WOTS+C (see the paper for details).
In summary, when using lossless state signatures, the signature size of SHRINCS is $\min(292 + q \cdot 16, s_l) + 16$, where $q$ is the number of signatures generated for this public key in stateful mode, and $s_l$ is the size of the signature generated using the stateless scheme. If $q = 1$, the signature is 11 times smaller than the NIST standardized scheme (ML-DSA) with the smallest signature size. I estimate that the average $q$ value for a regular Bitcoin wallet is between 1 and 2. The main drawback of SHRINCS is that its security requires secure state management. However, unlike fully stateful schemes (where a mishap in state management can be disastrous), in SHRINCS, you can always switch to stateless mode whenever you have doubts.
(over)
