``` BIP: ? Title: SHRINCS: A Compact Hash-Based Signature Scheme Authors: conduition Ethan Heilman Mikhail Kudinov Oleksandr Kurbatov Jonas Nick remix7531 Status: Draft Type: Specification Assigned: ? License: CC0-1.0 or MIT ``` ## Abstract This document specifies SHRINCS (_Shrunken SPHINCS_), a hash-based post-quantum signature scheme, for use in Bitcoin transaction authorization. SHRINCS combines compact stateful hash-based signatures with a stateless fallback[^hbsb]. It is instantiated with SHA256, targeting NIST security category 1: 128 bits of classical and 64 bits of quantum security. A security proof is TODO. This specification describes the key generation, signing, and verification algorithms of SHRINCS. ## Motivation SHRINCS offers compact post-quantum signatures under conservative cryptographic assumptions. It relies solely on the security of its underlying hash function. In this specification, that function is SHA256, which is already fundamental to Bitcoin's security. Signature schemes from other post-quantum families also rely on hash-function security but additionally require separate hardness assumptions, such as the hardness of lattice problems. Bitcoin outputs may remain unspent for long periods, making conservative cryptographic assumptions particularly valuable. This conservatism gives hash-based signature schemes like SHRINCS a distinct place in the cryptographic design space, even when schemes from other families offer better size or performance. Signature size is particularly important in Bitcoin because signatures consume scarce block space. SHRINCS therefore offers signers a compact stateful signing path at the cost of additional implementation complexity. This path allows SHRINCS to leverage the fact that a key pair in Bitcoin is typically used only a few times. As a result, stateful SHRINCS signatures can be many times smaller than those of standardized hash-based signature schemes. The minimum combined size of a SHRINCS public key and stateful signature is roughly 13.23x smaller than that of SLH-DSA-SHA2-128s[^slhdsa] and 6.26x smaller than that of the lattice-based ML-DSA-44 scheme (which targets NIST security category 2, whereas SHRINCS targets category 1). ## Overview At a high level, a SHRINCS instance combines two hash-based signature schemes: 1. A **stateful** component — a flexible XMSS (FXMSS) tree of WOTS+C[^sphincs+c] one-time signatures. 2. A **stateless** component — SLH-DSA[^slhdsa], the NIST-standardized variant of SPHINCS+[^sphincs+], with a non-standard parameter set. A signature from either component is sufficient to pass verification. The signer uses the stateful component as its compact, primary path, and falls back to the stateless component when signing state is unavailable (lost, corrupted, or intentionally reset, e.g. after seed recovery). The **stateful** component, FXMSS, generates small signatures. It is a variant of XMSS[^xmss]. In XMSS, the public key is the root of a Merkle tree whose leaves are one-time-signature public keys, and each signature is a single one-time signature together with the Merkle authentication path from its leaf to the root. The signer must maintain state so that no leaf is used to sign more than once. FXMSS is _flexible_ in that the signer chooses the shape of the tree. An _unbalanced_ tree minimizes the size of the first few signatures but makes each subsequent signature larger, suiting signers that produce few signatures. A _balanced_ tree instead produces constant-size signatures. The **stateless** component generates larger signatures, but does not require the signer to manage state. An SLH-DSA parameter set determines its _signature budget_: the maximum number of signatures that may be produced under one public key while retaining the targeted security level. Standardized SLH-DSA supports a budget of 264 signatures; the non-standard parameter set used here reduces this to 240, which in turn yields signatures smaller than SLH-DSA-SHA2-128s. Each component produces a 16-byte root hash as part of its public key. These two roots, together with a 16-byte seed value, form the 48-byte SHRINCS public key: ```py PK = pk_seed || sl_root || sf_root ``` The SHRINCS verification algorithm consists mostly of evaluating a series of hash functions on elements of the signature to recompute a certain hash. Ultimately the verifier recomputes one of the SHRINCS public key components: a stateful signature is checked against `sf_root`, a stateless signature against `sl_root`. Public key and signature sizes are summarized below: | Item | Size (min - max) | |:--|:--| | Public key | 48 bytes | | Stateful signature | 548 - 4619 bytes | | Stateless signature | 5777 bytes | ### Relation to SLH-DSA The stateless component of SHRINCS uses the SLH-DSA algorithms defined in NIST FIPS-205 with a parameter set that is not among those standardized in FIPS-205 (see [Parameters](#parameters)). The hash functions are instantiated with SHA256, as in the FIPS-205 parameter sets of the SHA2 family at security category 1. The algorithms specified below, `slh_dsa_sign` and `slh_dsa_verify`, match the FIPS-205 algorithms `slh_sign` (Algorithm 22) and `slh_verify` (Algorithm 24), except that in this document `slh_dsa_sign` receives optional additional randomness from its caller rather than generating it internally as in FIPS-205 Algorithm 22. An SLH-DSA implementation that supports custom parameter sets can therefore be used for the stateless component of SHRINCS, with a thin wrapper to produce SHRINCS signatures. This document nonetheless respecifies these algorithms in full, rather than referring to FIPS-205, in order to present both components of SHRINCS in one consistent notation. The exact correspondence between parameters common between this document and FIPS-205 is given in [the section on stateless parameters](#stateless-parameters). ## Performance SHRINCS performance during key generation, signing, and verification is dominated by hash function calls. The tables below therefore report SHA256 compression counts computed by [`impl/meta.py`](./impl/meta.py). The signing and verification counts assume a 32-byte caller-supplied message and an empty context. Actual runtimes depend on the implementation, including its use of SHA256 hardware acceleration.[^sha_ni_bench] ### Verification In this table we show exact compression counts, and show the maximum _compressions per byte_ (C/B) needed to verify a SHRINCS stateful and stateless signature. | Signing Component | Verify Cost in SHA256 Compressions (min - max) | C/B (max) | |-|-|-| | Stateful SHRINCS | 255 - 509 | 0.465 | | Stateless SHRINCS | 467 - 2792 | 0.483 | The variance in stateful verify compression count can be caused by signers supplying larger stateful signatures, which require additional hash invocations to verify. The variance in stateless compression count can be controlled by the signer with no change to signature size, and is owed to the fact that the signatures of the WOTS-TW subscheme have a non-constant verification cost which depends on a signer-controlled hash. SHRINCS verification time can be reduced using CPU instructions designed specifically for SHA256[^sha_ni_bench] or by evaluating independent SHA256 computations in parallel with vectorized (SIMD) CPU instructions[^simd_bench]. For comparison, the cost of BIP-340 Schnorr verification can be expressed as an equivalent number of SHA256 compression calls by benchmarking both operations on the same system. One benchmark using libsecp256k1's SHA256 implementation found that BIP-340 verification, including public-key parsing, took the same time as 127 compression calls, or 1.98 equivalent compressions per byte of the 64-byte signature.[^bip340_sha256_bench] ### Key Generation SHRINCS key generation is much slower than verification because it generates the stateless component's top-layer XMSS tree and the stateful component's FXMSS tree. The cost of key-generation depends on the _structure_ of the stateful component's FXMSS tree - See the [FXMSS](#fxmss) specification section for a full explanation. In general, putting more up-front work into key-generation allows the key a larger stateful signature budget. The key-generation cost of the stateless component is constant. Here we have illustrated several examples of SHRINCS key generation costs for different stateful structures. Note this cost includes both stateful and stateless components. | Stateful Structure | Total Key Generation Cost in SHA256 Compressions | Stateful Signature Budget | |-|-|-| | UXMSS; depth 31 | 309054 | 32 | | UXMSS; depth 255 | 425982 | 256 | | BXMSS; depth 5 | 309054 | 25 | | BXMSS; depth 8 | 425982 | 28 | | BXMSS; depth 10 | 826878 | 210 | | BXMSS; depth 12 | 2430462 | 212 | | BXMSS; depth 16 | 34502142 | 216 | | BXMSS; depth 20 | 547649022 | 220 | SHRINCS key-generation performance can be improved by evaluating independent SHA256 hashes in parallel using vectorized CPU instructions[^simd_bench][^sha256x8], or using CUDA or Vulkan[^vulkan]. One can also improve SHRINCS key-generation performance at the cost of stateless signature budget, using hypertree pruning[^pruning]. ### Signing SHRINCS signing performance depends on whether the signer uses the stateful or stateless component. - In the stateless component, signing performance varies slightly from message to message. - In the stateful component, signing performance differs vastly depending on the structure used for the stateful FXMSS tree. | Signature Type | Average Signing Cost in SHA256 Compressions | Stateful Signature Budget | |-|-|-| | Stateless | 1707229 | | | Stateful (UXMSS; depth 31) | 16510 | 32 | | Stateful (UXMSS; depth 255) | 133326 | 256 | | Stateful (BXMSS; depth 5) | 16522 | 25 | | Stateful (BXMSS; depth 8) | 133447 | 28 | | Stateful (BXMSS; depth 10) | 534341 | 210 | | Stateful (BXMSS; depth 12) | 2137923 | 212 | | Stateful (BXMSS; depth 16) | 34209599 | 216 | | Stateful (BXMSS; depth 20) | 547356475 | 220 | SHRINCS signing performance can be improved by evaluating independent SHA256 hashes in parallel using vectorized CPU instructions[^simd_bench][^sha256x8], or using CUDA or Vulkan[^vulkan]. To improve stateful signing performance further at the cost of memory, one can cache leaves or internal nodes in the [FXMSS](#fxmss) tree which are produced during key-generation or prior signing attempts. Caching reduces the fraction of the FXMSS tree which the signer must regenerate on each signing attempt, which is by far the greatest computational cost in stateful signing. Caching can therefore result in very significant (orders of magnitude) speedups, depending on the stateful tree structure. The stateless component also admits a small speedup if an implementation can [cache the top-level XMSS tree](https://conduition.io/code/fast-slh-dsa/#XMSS-Tree-Caching). One can also improve stateless SHRINCS signing performance at the cost of stateless signature budget, using hypertree pruning[^pruning]. ## Rationale ### Why not use a standardized SLH-DSA parameter set? The stateless component of SHRINCS uses a non-standard SLH-DSA parameter set, primarily to reduce the signature budget from 264 to 240 signatures per public key. Reducing the signature budget reduces the stateless signature size from 7,856 bytes for SLH-DSA-SHA2-128s to 5777 bytes for the stateless component of SHRINCS, a reduction of 26%. The stateless parameter set also requires 23% fewer SHA256 compressions for average-case signing and 28% fewer for worst-case verification than SLH-DSA-SHA2-128s. The 240 signature budget remains far beyond what could be exercised on-chain. With Bitcoin's current 4 MB block size limit, 200 years of blocks would consume approximately 0.66% of a key's signature budget if all block space were used for stateless SHRINCS signatures under that public key. The 240 signature budget is not reduced further for two reasons. First, off-chain protocols may generate many signatures under one public key. Off-chain protocols are not constrained by block space and may produce many signatures that never appear on the blockchain. A budget of 240 permits approximately 1.1 trillion signatures under a single public key, leaving substantial room for such protocols. Second, a smaller budget would be easier to exhaust through repeated adversarial signing requests. An attacker who can request signatures can in principle exhaust any finite signature budget, but a smaller budget makes such an attack more practical. With a sufficiently small budget, an implementation would need to count signatures persistently and stop signing before the budget was exhausted, making the scheme effectively stateful. The time required to generate each signature limits how quickly the budget can be exhausted. Signing devices that require manual approval for every signature cannot feasibly exhaust a 240 budget, while automated signers can use rate limiting to make exhaustion impractical. At a sustained rate of 1,000 signatures per second, producing 240 signatures would take approximately 35 years. ### Why not support multiple parameter sets? The parameters of both SHRINCS components can be tuned to provide different trade-offs among signature size, signature budget, and key-generation, signing, and verification costs. SHRINCS could therefore allow signers to select among multiple parameter sets at key generation. SHRINCS instead fixes a single parameter set for both the stateful and stateless components. This choice has three motivations: - Misuse resistance. Wallet developers could misunderstand or misuse different parameter sets, or choose unsafe parameters. - Implementation and integration. Supporting multiple parameter sets would increase verifier implementation complexity and test coverage requirements, make behavior across parameter sets harder to analyze, and complicate resource accounting in protocols that use SHRINCS. - Privacy. Multiple parameter sets would make wallet fingerprinting easier, reducing anonymity sets across the network. The selected parameter set balances signature size, signature budget, and key-generation, signing, and verification costs for a broad range of on-chain and off-chain Bitcoin use cases. ### Why these specific parameters? The stateless parameter set specified here was selected using automated parameter-search and analysis tools.[^sl_param_tool][^sl_param_search] Among the candidate parameter sets meeting the targeted security level and 240 signature budget, the stateless parameter set specified here minimizes signature size subject to keeping its key-generation cost, average signing cost, and worst-case verification cost below those of SLH-DSA-SHA2-128s. The stateful parameter set specified here keeps its worst-case verification cost per signature byte close to that of the stateless component. One way the stateful signature size could be reduced further is to increase `WOTS_C_CHAIN_BITS`, which decreases `WOTS_C_CHAIN_COUNT`. However, this would increase key-generation and signing costs and raise the worst-case verification cost per signature byte above that of the stateless component. Signatures from both components have a lower worst-case verification cost per byte than BIP340 signatures. This leaves room for a witness discount that partly compensates for the larger signature size. Such a discount could increase effective block capacity without a proportional increase in worst-case signature-verification work. This specification does not define such a discount. ### Why not use a SPHINCS+ variant with smaller signatures for the stateless component? Using the SLH-DSA algorithms defined in FIPS-205 allows an SLH-DSA implementation that supports custom parameter sets to be adapted for the stateless component specified here with little additional work. The stateless component also benefits from analysis of these algorithms conducted during the development and standardization of SLH-DSA. This choice comes at the cost of larger signatures. For the same 240 signature budget, using SPHINCS+C[^sphincs+c] or replacing FORS with PORS+FP[^porsfp] could produce stateless signatures approximately 15% smaller than those specified here. The ability to reuse SLH-DSA implementations and draw on its existing security analysis justifies this size trade-off. ### Why not a hybrid scheme? A hybrid signature scheme combines two signature schemes so that it remains unforgeable as long as either component remains unforgeable. The simplest construction pairs the two public keys, concatenates the two signatures, and accepts only if both signatures verify. SHRINCS can therefore be used as the post-quantum component of a hybrid without modification, for example together with BIP340. A dedicated non-black-box combiner can preserve stronger security properties or reduce the combined signature size. Bird-of-Prey-2[^bop], for example, preserves strong unforgeability when one component is compromised. Strong unforgeability prevents an attacker from producing a different valid signature for a message for which it has already obtained a valid signature. This specification does not define a dedicated hybrid signature scheme for the following reasons: - **Limited additional benefit.** Strong unforgeability does not appear to provide an additional property required for Bitcoin transaction authorization. Producing a different valid signature for an already signed transaction neither authorizes a different transaction nor changes its transaction identifier, because witness data is excluded from the transaction identifier. For a hybrid of BIP340 and SHRINCS, Bird-of-Prey-2 could reduce the combined signature size by 32 bytes relative to concatenation.[^bop-delving] - **Complexity.** A Bird-of-Prey-2 combiner for BIP340 and SHRINCS would require modified BIP340 signing and verification algorithms rather than treating BIP340 as a black box. It would also require showing that SHRINCS satisfies the requirements imposed on the post-quantum component by the Bird-of-Prey-2 security proof.[^bop] - **Cryptographic assumptions.** The SHRINCS instance specified here is hash-based and uses SHA256, which BIP340 already relies on for security. It therefore does not introduce an entirely new family of cryptographic assumptions. The limited additional benefits of a dedicated combiner do not justify its complexity. Applications that want to hedge against state reuse, implementation flaws, or other failures affecting SHRINCS can instead combine it with another signature scheme through concatenation. ### Why NIST security category 1? The SHRINCS instance specified here targets NIST security category 1 to match BIP340's approximately 128-bit classical security level.[^bip340-security] The instance of SHRINCS specified here uses 16-byte outputs for its tweakable hash functions and pseudorandom functions, matching the output length used by the SHA2 category 1 parameter sets in FIPS-205.[^slhdsa][^why128] ### Why SHA256 and not some newer hash function? SHA256 is already part of Bitcoin's consensus rules and fundamental to Bitcoin's security. Using it for SHRINCS avoids adding another hash function to consensus validation and allows implementations to reuse existing code and any available hardware acceleration. ### Why use WOTS+C in the stateful path? SLH-DSA signs with WOTS-TW, the Winternitz one-time signature scheme with a checksum. The stateful path instead uses WOTS+C,[^sphincs+c] a variant that produces smaller signatures. WOTS+C is not compatible with SLH-DSA, so it is used only on the stateful path, where compatibility is not required. An alternative choice would be to use WOTS-TW in the stateful path too, which would reduce code surface at the cost of signature size and verification time. With the parameter set specified here, this would result in stateful signatures up to approximately 8% larger and require more hash computations for verification on average, although the exact number would depend on the signed message. The additional code complexity appears to be worth the efficiency gains in this case: The stateful component would be the primary signing tool used in Bitcoin transactions, and thus the WOTS+C optimization is warranted. ### Why statefulness? Stateful signing is a significant departure from the signature schemes already used in Bitcoin. Although SHRINCS also supports a stateless path, its stateful path requires signers to keep track of how many times each key pair has been used for stateful signing. This state-management burden introduces implementation complexity, and incorrect state management can compromise security. Signers using the stateful component accept this implementation complexity and its associated risks in exchange for smaller signatures and a lower maximum verification cost. The smallest stateful signature is approximately 10.54 times smaller than a stateless signature. Verification of a maximum-depth stateful signature requires 509 SHA256 compressions. A stateless signature requires at most 2792 SHA256 compressions, approximately 5.49 times as many. ### Isn't statefulness unsafe? The security of stateful signing requires that a state counter value is never reused under the same key pair. Reusing a state counter value under the same key pair can enable anyone who observes the resulting signatures to produce forgeries. Implementations can prevent such reuse by enforcing the invariants specified in [On Managing State](#on-managing-state). Implementations that cannot safely manage state can still generate valid SHRINCS key pairs and sign using the stateless component. If a key pair's state counter is lost, corrupted, or otherwise uncertain, an implementation MUST refuse stateful signing. The stateless fallback allows the implementation to do so while always maintaining the ability to sign with that key pair. State reuse can be detected before publication by comparing a stateful signature with earlier signatures, providing defense in depth against failures in the signer's state management. Each stateful signature reveals the WOTS+C leaf it uses and can be rejected if the same leaf identifier has previously been observed under the same key pair. This defense assumes that an honest party performs the check and has access to the earlier signature. It therefore does not replace the signer's state-management requirements. ### Why does the stateful path use "flexible" XMSS? SHRINCS uses FXMSS in its stateful component, which supports binary merkle trees of (almost) arbitrary structure. This is because supporting only one tree shape, such as balanced XMSS (BXMSS) or unbalanced XMSS (UXMSS), locks out some use-cases from using the stateful path. Balanced and unbalanced XMSS tree shapes have completely different usage profiles and trade-offs against one-another. | Property | UXMSS | BXMSS | |:-:|:-:|:-:| | Keygen speed | Fast | Slow | | Signature budget | Sign only a few times | Sign many times | | Signature size | Compact, grows with use | Larger, fixed-size | | Primary use cases | Personal wallets; single-use certification; cooperative signing | Address reuse; L2 protocols; persistent identity | SHRINCS verifiers should therefore support either shape, so that the more-efficient stateful component can satisfy the needs of as many users as possible. After all, verifiers need not care about exactly how many signatures a keypair can produce - They need only validate that a signature is authentic against its public key. The naive way to support both balanced/unbalanced shapes would be to publish or commit a flag into each SHRINCS public key that identifies whether the stateful component uses balanced or unbalanced XMSS, and then react appropriately to that flag in the verifier. In SHRINCS, the verifier is agnostic to the stateful XMSS tree structure, which enables a single unified verifier code path that covers any signer's tree, no matter how it is structured. This "flexible XMSS" (FXMSS) verifier can accept signatures from other more complex XMSS tree structures as well as BXMSS and UXMSS. This means stateful SHRINCS FXMSS trees can be designed to fit highly specialized use-cases, e.g. a keypair which produces constant size signatures for the first `n` signatures and then the size doubles; or a keypair which produces short signatures of increasing size a la UXMSS, until some threshold point where the signature size locks to a constant size until the rest of the XMSS budget is exhausted. Many possibilities exist, but this specification prescribes only the BXMSS and UXMSS tree shapes and encourages further research into other tree shapes before suggesting their use in production. Meanwhile, the FXMSS verifier is left open to accept signatures from unorthodox tree shapes for the sake of forwards compatibility. ### Does FXMSS have a big enough signature budget? FXMSS admits trees of depth at most 255, but leaf indexing uses 64-bit unsigned integers, so in theory one could generate a BXMSS tree of at most depth 64 containing 264 WOTS+C leaves. However, this is impractical because FXMSS is a single-tree design XMSS-variant. A single-tree design puts a fundamental limit on the signer: *The signature budget is limited to the number of WOTS+C keys that can be constructed **up-front,*** during key-generation. This is because all WOTS+C keys in FXMSS must be arranged into a single merkle tree, whose root must be known before the SHRINCS public key can be fully computed. Assuming an extremely well-optimized and highly-parallel GPU implementation of WOTS+C key-generation which can execute one SHA256 compression per nanosecond on average, the most WOTS+C keys this signer could generate per second would be about 221, or about 232 WOTS+C keys per hour. Only after generating a suitable number of these WOTS+C keys can SHRINCS key-generation be completed. Let's be optimistic and assume this high-speed signer allocates one minute for key generation. She would produce about 115 million WOTS+C keys. She spends an extra tenth of a second computing the merkle root of all these WOTS+C leaves. Her FXMSS signature budget would be about 115,000,000. For the average consumer Bitcoin wallet, this is far more signatures than would ever be needed. For off-chain protocols, though, the FXMSS signature budget can be exhausted surprisingly fast. Consider a busy lightning channel which signs 5 new commitment transactions per second on average. **A signature budget of 115 million would only last 266 days** before the signer would run out of fresh WOTS+C keys, and would need to switch to the stateless path. Single-tree XMSS could be generalized to *multi-tree XMSS,* written XMSSMT, which is specified alongside standard XMSS in RFC-8391[^xmss] as a stateful many-time hash-based signature scheme. XMSSMT allows signers to use SPHINCS-style hypertrees to keep key-generation performance bounded while supporting very large signature budgets. SHRINCS opts not to support XMSSMT, due to the additional code complexity, attack surface, and challenging security interplay with flexible tree structures that would be introduced. High-frequency off-chain use-cases can be handled adequately by the stateless component of SHRINCS, which has sufficient signature budget (240) to allow a 1000 TPS Lightning channel to operate continuously for over 30 years. The additional size of stateless signatures only becomes a problem in rare non-cooperative edge cases where force-closures are needed. ### What about hardware wallets? Low-power signers, especially early-generation hardware wallets, typically lack the fast and highly-parallel computing hardware needed for efficient key-generation and signing in a hash-based signature scheme.[^ledger-bench][^trezor-bench] Thankfully, signing with the stateful component of SHRINCS is very efficient and requires about 133326 hash invocations per signature for UXMSS. Most of that work can be cached up-front during the stateful key-generation, which only requires about 133631 SHA256 compressions - and even that can be reduced by decreasing the UXMSS tree depth. The stateless component is much harder for low-power signers to work with because its parameters are more-or-less fixed, and it requires about 1707229 SHA256 compressions to sign. To remedy this, hardware wallets can implement a software-level trade-off in SLH-DSA called *hypertree pruning*[^pruning] which reduces the secure signature budget of the key from 240 to some arbitrary lower bound, in exchange for significantly faster signing and key-generation. Since these hardware wallets typically have very weak processing power and require human interaction to produce a set of signatures, a signature budget of 240 is already overkill in this context, and so can safely be reduced while preserving the stateless property of SLH-DSA (assuming the key is not exported to a higher-power signing device). Implementations using hypertree pruning must reproduce the same pruning strategy when regenerating a key. ## Specification ### Parameters Here follow the parameters of the stateful and stateless components. #### Stateful Parameters | Parameter | Value | Description | |:-:|:-:|:--| | `WOTS_C_CHAIN_BITS` | 4 | The number of bits encoded by each Winternitz key chain. | | `WOTS_C_CHAIN_COUNT` | 32 | The number of Winternitz chains. | | `FXMSS_HEIGHT` | 255 | The imaginary height of the FXMSS tree, i.e. the maximum depth of a WOTS+C leaf node. | #### Stateless Parameters The FIPS-205 column gives the name of the parameter in FIPS-205. | Parameter | FIPS-205 | Value | Description | |:-:|:-:|:-:|:--| | — | `n` | 16 | The byte length of the hash outputs, i.e. the security parameter. It is not a named parameter in SHRINCS: every tweakable hash function truncates its output to 16 bytes. | | `WOTS_TW_CHAIN_BITS` | `lg_w` | 4 | The number of bits encoded by each Winternitz key chain. | | `SPHX_LAYER_COUNT` | `d` | 5 | The number of XMSS layers in the SLH-DSA hypertree. | | `SPHX_XMSS_HEIGHT` | `h'` | 9 | The height of each XMSS layer within the SLH-DSA hypertree. | | `SPHX_FORS_HEIGHT` | `a` | 13 | The height of each FORS tree used in the SLH-DSA signature. | | `SPHX_FORS_COUNT` | `k` | 10 | The number of FORS trees used in the SLH-DSA signature. | ### Derived Constants The following constants are derived from the parameters above. We show formulas for how these are computed, using the integer operations defined under [Utilities](#utilities). #### Stateful Constants | Constant | Value | Formula | Description | |:-:|:-:|:-:|:-:| | `WOTS_C_CHAINS_SIZE` | 512 | `WOTS_C_CHAIN_COUNT * 16` | The byte size of a full set of concatenated WOTS chain hashes. | | `WOTS_C_CONSTANT_SUM` | 240 | `ceildiv(WOTS_C_CHAIN_COUNT * (2**WOTS_C_CHAIN_BITS - 1), 2)` | The most likely sum for Winternitz hash chain indexes. | |`FXMSS_SIGNATURE_SIZE_MIN`| 530 | `2 + WOTS_C_CHAINS_SIZE + 16` | The minimum byte size of an FXMSS signature. | |`FXMSS_SIGNATURE_SIZE_MAX`| 4594 | `2 + WOTS_C_CHAINS_SIZE + 16 * FXMSS_HEIGHT` | The maximum byte size of an FXMSS signature. | |`SHRINCS_SF_SIGNATURE_SIZE_MIN`| 548 | `1 + 16 + 1 + FXMSS_SIGNATURE_SIZE_MIN` | The minimum byte size of a stateful SHRINCS signature: a randomizer, a leaf index, and an FXMSS signature. | |`SHRINCS_SF_SIGNATURE_SIZE_MAX`| 4619 | `1 + 16 + 8 + FXMSS_SIGNATURE_SIZE_MAX` | The maximum byte size of a stateful SHRINCS signature. Must stay below `SHRINCS_SL_SIGNATURE_SIZE`, so that the two signature shapes remain distinguishable by length. | #### Stateless Constants The FIPS-205 column gives the name of the parameter in FIPS-205. | Constant | FIPS-205 | Value | Formula | Description | |:-:|:-:|:-:|:-:|:-:| | `WOTS_TW_CHAIN_COUNT1` | `len1` | 32 | `ceildiv(128, WOTS_TW_CHAIN_BITS)` | The number of Winternitz message chains per WOTS key. | | `WOTS_TW_CHECKSUM_MAX` | `max_checksum` | 480 | `WOTS_TW_CHAIN_COUNT1 * (2**WOTS_TW_CHAIN_BITS - 1)` | The maximum possible sum of Winternitz hash chain indexes. | | `WOTS_TW_CHAIN_COUNT2` | `len2` | 3 | `ceildiv(WOTS_TW_CHECKSUM_MAX.bit_length(), WOTS_TW_CHAIN_BITS)` | The number of Winternitz checksum chains per WOTS key. | | `WOTS_TW_CHAIN_COUNT` | `len` | 35 | `WOTS_TW_CHAIN_COUNT1 + WOTS_TW_CHAIN_COUNT2` | The overall number of Winternitz chains per WOTS key. | | `WOTS_TW_CHAINS_SIZE` | (Not named in FIPS-205) | 560 | `WOTS_TW_CHAIN_COUNT * 16` | The byte size of a full set of concatenated WOTS chain hashes. | | `SPHX_XMSS_SIGNATURE_SIZE` | (Not named in FIPS-205) | 704 | `WOTS_TW_CHAINS_SIZE + 16 * SPHX_XMSS_HEIGHT` | The byte size of a serialized XMSS signature. | | `HYPERTREE_SIGNATURE_SIZE` | (Not named in FIPS-205) | 3520 | `SPHX_LAYER_COUNT * SPHX_XMSS_SIGNATURE_SIZE` | The byte size of a hypertree signature. | | `FORS_DIGEST_SIZE` | (Not named in FIPS-205) | 17 | `ceildiv(SPHX_FORS_COUNT * SPHX_FORS_HEIGHT, 8)` | The byte size of a FORS message digest. Contains enough bits to select a random index for each FORS tree. | | `FORS_SIGNATURE_SIZE` | (Not named in FIPS-205) | 2240 | `16 * SPHX_FORS_COUNT * (SPHX_FORS_HEIGHT + 1)` | The byte size of a FORS signature. | | `SPHX_SIGNATURE_SIZE` | (Not named in FIPS-205) | 5776 | `16 + FORS_SIGNATURE_SIZE + HYPERTREE_SIGNATURE_SIZE` | The byte size of an SLH-DSA signature. | | `SHRINCS_SL_SIGNATURE_SIZE` | (Not named in FIPS-205) | 5777 | `1 + SPHX_SIGNATURE_SIZE` | The byte size of a stateless SHRINCS signature. | | `SPHX_TREE_INDEX_BITS` | (Not named in FIPS-205) | 36 | `SPHX_XMSS_HEIGHT * (SPHX_LAYER_COUNT - 1)` | The number of bits needed to represent the index of an XMSS tree in the hypertree. | | (Not named in SHRINCS) | `h` | 45 | `SPHX_LAYER_COUNT * SPHX_XMSS_HEIGHT` | The total height of the SLH-DSA hypertree. | | (Not named in SHRINCS) | `m` | 24 | `ceildiv(SPHX_FORS_HEIGHT * SPHX_FORS_COUNT, 8) + ceildiv(SPHX_XMSS_HEIGHT * (SPHX_LAYER_COUNT - 1), 8) + ceildiv(SPHX_XMSS_HEIGHT, 8)` | The byte length of the message digest. | ### Key Generation Inputs Generating a SHRINCS key is straightforward and consists only of generating 48 random bytes. This is then split into 3 x 16-byte seeds. - `sk_seed` is the core component of the secret key. Exposing this compromises the security of the keypair. - `sk_prf` is a secret value used to derive per-message randomness. - `pk_seed` is the public seed included in the public key. Note this is the bare minimum needed to generate a full SHRINCS public key. More performant (but larger) secret key representations are possible. #### Padding To save computational effort, `pk_seed` is padded with zero bytes to a length of 64 bytes in most cases. This aligns with the SHA256 block size, so that `pk_seed` can be absorbed into the SHA256 state, and that midstate can be cached & reused. ### Value Types A function signature states the size of each value it takes and returns, in the notation below. `impl/shrincs.py` declares that notation as [`typing.Annotated`](https://docs.python.org/3/library/typing.html#typing.Annotated) metadata, so that it can be checked mechanically. They are inert in the implementation, and the sizes they state are requirements on any implementation. - `Bytes[n]` is a byte string of exactly `n` bytes. `n` may be an arithmetic expression over the constants this document defines, evaluated for the parameter set in force, as in `Bytes[2 + WOTS_C_CHAINS_SIZE]`. - `Bytes[a:b]` is a byte string of at least `a` and at most `b` bytes. Both bounds are inclusive, unlike a Python slice. Either may be omitted: `Bytes[a:]` is at least `a` bytes, and `Bytes[:b]` at most `b`. - A bare `bytes` is bounded only by its callers. - `UInt8`, `UInt16`, `UInt32` and `UInt64` are integers in the ranges `[0, 2**8)`, `[0, 2**16)`, `[0, 2**32)` and `[0, 2**64)` respectively, serialized as described in [Utilities](#utilities). A bare `int` is an integer of unbounded width, and no value in this specification is negative. - `Array[T, n]` is a sequence of exactly `n` values of type `T`. `n` may be an arithmetic expression over the constants this document defines, as it may in `Bytes[n]`. - `list[T]` is a sequence of values of type `T`, as many of them as the paragraph beneath the signature states. - `tuple[...]` is a fixed group of values of the given types, in that order, returned by the functions which produce more than one. Each element is written into the field its caller gives it, so the group has no size of its own. - `Union[T, U]` is a value of one of the given types. Where this specification returns one, its length tells the reader which. - `Optional[T]` is either a `T` or the absence of one. - `bool` is true or false. Where an address includes one, it is serialized as a single byte, 1 for true and 0 for false. These sizes are normative. A value is written into a field wide enough to hold it. Writing one into a narrower field is an error rather than a value reduced to fit, and every field this specification writes is wide enough for every value which can reach it. ### Utilities We make use of the following utility helper functions in specifying SHRINCS. - `a // b`: divides the integer `a` by the integer `b`, rounding the quotient down. - `ceildiv(a, b)`: divides the integer `a` by the integer `b`, rounding the quotient up. - `sum(x)`: sums a sequence of numbers `x`. - `replicate(b, n)`: returns a bytestring of length `n` containing only the repeated byte `b`. - `zeros(n)`: returns a bytestring of length `n` containing only repeated zero bytes. - `range(start, end)`: returns the ascending sequence of all integers `i` such that `start <= i < end`. - `concat(array)`: concatenates an array of byte strings. Every algorithm and every derived constant in this specification is computed with exact integer arithmetic. Division in them appears only in the two integer forms above, so the specification never leaves a rounding decision to the implementation. Note that `ceildiv(a, b)` must round up for every `a` it is given: writing it as a division that rounds toward zero, which is what the division operator does in most languages, would silently round down instead. Every quantity in this specification denotes a mathematical integer, and every operation on one is exact. Nothing overflows, underflows, wraps, is reduced modulo a word size, saturates, or is truncated; a difference is never clamped at zero, and the only rounding is that of the two division forms above. If an operation would produce a result outside the range specified for that value, the operation violates the specification. It does not produce a different value within the range. The [value types](#value-types) above are therefore refinements, not representations. `UInt8` through `UInt64` assert that a value lies in `[0, 2**8)` through `[0, 2**64)`. They do not make it a machine word, and no arithmetic is ever performed modulo `2**bits`. Unless stated otherwise, all integers are serialized to and parsed from bytes as fixed-width, big-endian (network byte order) values, where the width is the size of the byte field the integer occupies. #### `base_2b(...)` Decomposes the bytes `x` into `outlen` groups of `b` bits which are each parsed as an integer in the range `[0, 2**b)`. The leading `outlen * b` bits of `x` are parsed, and so `x` must have accordingly sufficient length. ```py def base_2b(x: bytes, b: int, outlen: int) -> list[int]: assert len(x) >= ceildiv(outlen * b, 8) baseb = [0] * outlen # output array j = 0 # counts the bytes read from the input x. acc = 0 # accumulator, collects bits from x bits_filled = 0 # counts the bits accumulated for i in range(outlen): while bits_filled < b: acc = (acc << 8) + x[j] j += 1 bits_filled += 8 bits_filled -= b baseb[i] = acc >> bits_filled acc %= 2**bits_filled # prevent accumulator from overflowing return baseb ``` ### Building Blocks SHRINCS is a high-level construction built out of many smaller sub-schemes. To fully specify SHRINCS we start by defining the lowest level building blocks - addresses and the _hash functions_ and _pseudorandom functions_ (PRFs) - followed by the one-time signature schemes WOTS-TW and WOTS+C, and then the few-time signature scheme FORS, and finally we will move on to the higher-level constructions like XMSS and SLH-DSA, which together form SHRINCS. ``` ADRS \ hash functions & PRFs / \ / / \ / / \ WOTS+C WOTS-TW FORS / \ / / \ / FXMSS SLH-DSA \ (contains XMSS) \ / \ / \ / SHRINCS ``` ### ADRS A critical security property of SHRINCS and its components is that every hash function invocation used in the verification algorithm must be _unique,_ so that inputs used in one hash function cannot be reused to produce the same output in another hash function. To accomplish this goal, we will use _tweakable hash functions_ (explained below) which modify a hash function with some context-dependent location information. This unambiguously specifies the exact instance of the hash function in the signing/verification algorithms where the hash function is being used. This location is called an _address_ and we encode it into a 22-byte array, often called an `ADRS`.[^adrs] #### Stateless ADRS Format | `ADRS` Field | Size | Purpose | |:-:|:-:|:-:| | `layer` | 1 byte | Specifies the layer in the SLH-DSA hypertree. The topmost layer is at layer `SPHX_LAYER_COUNT - 1`. | | `tree_address` | 8 bytes | A 64-bit integer serialized with big-endian encoding. Specifies the index of an XMSS tree within a layer of the SLH-DSA hypertree. | | `type` | 1 byte | A context-dependent flag which gives meaning to the remaining 12 bytes. | | `payload` | 12 bytes |
Usage depends on the `type` field.

| #### Stateful ADRS Format | `ADRS` Field | Size | Purpose | |:-:|:-:|:-:| | `node_height` | 1 byte | Specifies the height of a node or leaf in the FXMSS tree. The root node is at height `FXMSS_HEIGHT`. | | `node_index` | 8 bytes | A 64-bit integer serialized with big-endian encoding. Specifies the node index (from the left) within a layer of the FXMSS tree. | | `type` | 1 byte | A context-dependent flag which gives meaning to the remaining 12 bytes. | | `payload` | 12 bytes |
Usage depends on the `type` field.

| #### ADRS Types | `ADRS` Type | Value | Purpose | Signing Path | |:-:|:-:|:-:|:-:| | `SL_WOTS_TW_HASH` | 0 | Used when iterating WOTS-TW hash chains. | Stateless | | `SL_WOTS_TW_PK` | 1 | Used when compressing WOTS-TW public keys. | Stateless | | `SL_XMSS_TREE` | 2 | Used when combining merkle nodes in the SLH-DSA hypertree. | Stateless | | `SL_FORS_TREE` | 3 | Used when combining merkle nodes in FORS trees. | Stateless | | `SL_FORS_ROOTS` | 4 | Used when compressing FORS merkle roots together. | Stateless | | `SL_WOTS_TW_PRF` | 5 | Used when generating WOTS-TW secret preimages. | Stateless | | `SL_FORS_PRF` | 6 | Used when generating FORS secret preimages. | Stateless | | `SF_WOTS_C_HASH` | 16 | Used when iterating WOTS+C hash chains. | Stateful | | `SF_WOTS_C_PK` | 17 | Used when compressing WOTS+C public keys. | Stateful | | `SF_FXMSS_TREE` | 18 | Used when combining merkle nodes in the stateful FXMSS tree. | Stateful | | `SF_WOTS_C_PRF` | 21 | Used when generating WOTS+C secret preimages. | Stateful | | `SF_WOTS_C_GRIND` | 22 | Used when grinding WOTS+C message digests. | Stateful | #### ADRS Payloads Each `ADRS` type gives different contextual meaning to the 12 bytes of the ADRS `payload` field. The following table describes how they are used under each ADRS type flag. | Stateless `ADRS` Type | Payload Format |            | Stateful `ADRS` Type | Payload Format | |:-:|-|:-:|:-:|-| | `SL_WOTS_TW_HASH` | 4 bytes: key pair index
4 bytes: chain index
4 bytes: hash index | | `SF_WOTS_C_HASH` | 4 bytes: zero padding
4 bytes: chain index
4 bytes: hash index | | `SL_WOTS_TW_PK` | 4 bytes: key pair index
8 bytes: zero padding | | `SF_WOTS_C_PK` | 12 bytes: zero padding | | `SL_XMSS_TREE` | 4 bytes: zero padding
4 bytes: tree height
4 bytes: tree index | | `SF_FXMSS_TREE` | 12 bytes: zero padding | | `SL_FORS_TREE` | 4 bytes: key pair index
4 bytes: tree height
4 bytes: tree index | | `SF_WOTS_C_PRF` | 2 bytes: tree structure
2 bytes: zero padding
4 bytes: chain index
4 bytes: zero padding | | `SL_FORS_ROOTS` | 4 bytes: key pair index
8 bytes: zero padding | | `SF_WOTS_C_GRIND` | 12 bytes: zero padding | | `SL_WOTS_TW_PRF` | 4 bytes: key pair index
4 bytes: chain index
4 bytes: zero padding | | | | | `SL_FORS_PRF` | 4 bytes: key pair index
4 bytes: zero padding
4 bytes: tree index | | | | The implementation below represents each address type as an immutable record which exposes only its meaningful fields. Serializing a record produces the 22-byte format above, with every unused payload word set to zero. ```py @dataclass(frozen=True) class Address: """ Base class for typed addresses used by tweakable hash functions. `height` and `index` encode the common 9-byte prefix. On the stateless path they identify a hypertree layer and XMSS tree. On the stateful path they identify an FXMSS node. Concrete subclasses select the address type and expose its meaningful payload fields. """ height: UInt8 index: UInt64 def pack( self, address_type: UInt8, word1: UInt32 = 0, word2: UInt32 = 0, word3: UInt32 = 0, ) -> Bytes[22]: """ Serializes the common prefix, address type, and three payload words to 22 bytes. """ return (self.height.to_bytes(1) + self.index.to_bytes(8) + address_type.to_bytes(1) + word1.to_bytes(4) + word2.to_bytes(4) + word3.to_bytes(4)) @dataclass(frozen=True) class WotsTwHash(Address): keypair_index: UInt32 chain_index: UInt32 hash_index: UInt32 def to_bytes(self) -> Bytes[22]: return self.pack(SL_WOTS_TW_HASH, word1=self.keypair_index, word2=self.chain_index, word3=self.hash_index) @dataclass(frozen=True) class WotsTwPrf(Address): keypair_index: UInt32 chain_index: UInt32 def to_bytes(self) -> Bytes[22]: return self.pack(SL_WOTS_TW_PRF, word1=self.keypair_index, word2=self.chain_index) @dataclass(frozen=True) class WotsTwPk(Address): keypair_index: UInt32 def to_bytes(self) -> Bytes[22]: return self.pack(SL_WOTS_TW_PK, word1=self.keypair_index) @dataclass(frozen=True) class XmssTree(Address): tree_height: UInt32 tree_index: UInt32 def to_bytes(self) -> Bytes[22]: return self.pack(SL_XMSS_TREE, word2=self.tree_height, word3=self.tree_index) @dataclass(frozen=True) class ForsTree(Address): keypair_index: UInt32 tree_height: UInt32 tree_index: UInt32 def to_bytes(self) -> Bytes[22]: return self.pack(SL_FORS_TREE, word1=self.keypair_index, word2=self.tree_height, word3=self.tree_index) @dataclass(frozen=True) class ForsRoots(Address): keypair_index: UInt32 def to_bytes(self) -> Bytes[22]: return self.pack(SL_FORS_ROOTS, word1=self.keypair_index) @dataclass(frozen=True) class ForsPrf(Address): keypair_index: UInt32 tree_index: UInt32 def to_bytes(self) -> Bytes[22]: return self.pack(SL_FORS_PRF, word1=self.keypair_index, word3=self.tree_index) @dataclass(frozen=True) class WotsCHash(Address): chain_index: UInt32 hash_index: UInt32 def to_bytes(self) -> Bytes[22]: return self.pack(SF_WOTS_C_HASH, word2=self.chain_index, word3=self.hash_index) @dataclass(frozen=True) class WotsCPrf(Address): tree_balanced: bool tree_depth: UInt8 chain_index: UInt32 def to_bytes(self) -> Bytes[22]: return self.pack( SF_WOTS_C_PRF, word1=int(self.tree_balanced) * 2**24 + self.tree_depth * 2**16, word2=self.chain_index, ) @dataclass(frozen=True) class WotsCPk(Address): def to_bytes(self) -> Bytes[22]: return self.pack(SF_WOTS_C_PK) @dataclass(frozen=True) class WotsCGrind(Address): def to_bytes(self) -> Bytes[22]: return self.pack(SF_WOTS_C_GRIND) @dataclass(frozen=True) class FxmssTree(Address): def to_bytes(self) -> Bytes[22]: return self.pack(SF_FXMSS_TREE) ``` The following figures show, for each `ADRS` type, how the 22-byte address is laid out: the common leading fields (`layer` and `tree_address` for stateless types, `node_height` and `node_index` for stateful types) and the `type` field, followed by the type-specific interpretation of the 12-byte `payload`. Field widths are drawn proportional to their byte sizes, with byte offsets along the top. Stateless (`SL_*`) `ADRS` types, used along the SLH-DSA hypertree signing path. Stateful (`SF_*`) `ADRS` types, used along the FXMSS signing path. ### Hash and Pseudorandom Functions SHRINCS builds all of these functions from SHA256 as the base hash function, which we invoke as the primitive function `sha256(x)`, returning a 32-byte array. Outputs are often truncated, which we denote using Pythonic list-slicing notation: `sha256(x)[:16]`. The `sha256` hash function. - Inputs: - `message`: a message of at most `2**61 - 1` bytes. - Output: - a 32-byte hash. ```py def sha256(message: Bytes[:2**61 - 1]) -> Bytes[32]: return hashlib.sha256(bytes(message)).digest() ``` SHA-256 accepts an input of at most `2**61 - 1` bytes: its padding encodes the message length in a 64-bit field that counts bits, so the input cannot exceed `2**64 - 1` bits. HMAC-SHA256 prepends a single 64-byte block to the message before hashing it, so `hmac_sha256` accepts at most `2**61 - 1 - 64` bytes. These two primitive limits are the root of every message-length bound in the scheme; the resulting cap on a SHRINCS message is derived in [Maximum Message Length](#maximum-message-length). These functions fall into three families, described in the following sections: _tweakable hash functions_, _pseudorandom functions_, and _message digest functions_. Though built on the same primitive, they play conceptually distinct roles and are relied on for different security properties. #### Tweakable Hash Functions A tweakable hash function can be thought of as a hash function which supports additional independent parameters that scope it to a specific role. Concretely, each invocation is parameterized by a public parameter, `pk_seed`, and a tweak, the `ADRS`, so that the same input hashed at two different positions yields unrelated outputs. ##### `T_sl(...)` The `T_sl` tweaked hash function. Compresses `WOTS_TW_CHAIN_COUNT` Winternitz chain tips into a single 16-byte hash. - Inputs: - `pk_seed`: a 16-byte public seed. - `ADRS`: a `WotsTwPk` address. - `M_l`: a `WOTS_TW_CHAINS_SIZE`-byte concatenation of chain tips. - Output: - a 16-byte hash. This function is only used in the stateless path, and by both the signer and the verifier. ```py def T_sl(pk_seed: Bytes[16], ADRS: WotsTwPk, M_l: Bytes[WOTS_TW_CHAINS_SIZE]) -> Bytes[16]: return sha256(pk_seed + zeros(48) + ADRS.to_bytes() + M_l)[:16] ``` ##### `T_sf(...)` The `T_sf` tweaked hash function. Compresses `WOTS_C_CHAIN_COUNT` Winternitz chain tips into a single 16-byte hash. - Inputs: - `pk_seed`: a 16-byte public seed. - `ADRS`: a `WotsCPk` address. - `M_l`: a `WOTS_C_CHAINS_SIZE`-byte concatenation of chain tips. - Output: - a 16-byte hash. This function is only used in the stateful path, and by both the signer and the verifier. ```py def T_sf(pk_seed: Bytes[16], ADRS: WotsCPk, M_l: Bytes[WOTS_C_CHAINS_SIZE]) -> Bytes[16]: return sha256(pk_seed + zeros(48) + ADRS.to_bytes() + M_l)[:16] ``` ##### `T_k(...)` The `T_k` tweaked hash function. Compresses `SPHX_FORS_COUNT` FORS tree roots into a single 16-byte hash. - Inputs: - `pk_seed`: a 16-byte public seed. - `ADRS`: a `ForsRoots` address. - `M_k`: a `SPHX_FORS_COUNT * 16`-byte concatenation of FORS tree roots. - Output: - a 16-byte hash. This function is only used in the stateless path, and by both the signer and the verifier. ```py def T_k(pk_seed: Bytes[16], ADRS: ForsRoots, M_k: Bytes[SPHX_FORS_COUNT * 16]) -> Bytes[16]: return sha256(pk_seed + zeros(48) + ADRS.to_bytes() + M_k)[:16] ``` ##### `F(...)` The `F` tweaked hash function. Hashes a single 16-byte input, to generate and iterate Winternitz hash chains and to hash FORS leaves. - Inputs: - `pk_seed`: a 16-byte public seed. - `ADRS`: a `WotsTwHash`, `WotsCHash` or `ForsTree` address. - `M_1`: a 16-byte hash. - Output: - a 16-byte hash. This function is used in both stateful and stateless paths, and by both the signer and the verifier. ```py def F(pk_seed: Bytes[16], ADRS: Union[WotsTwHash, WotsCHash, ForsTree], M_1: Bytes[16]) -> Bytes[16]: return sha256(pk_seed + zeros(48) + ADRS.to_bytes() + M_1)[:16] ``` ##### `H(...)` The `H` tweaked hash function. Combines a pair of 16-byte Merkle child nodes into their 16-byte parent, building the Merkle trees in XMSS and FORS. - Inputs: - `pk_seed`: a 16-byte public seed. - `ADRS`: an `XmssTree`, `FxmssTree` or `ForsTree` address. - `M_2`: a 32-byte concatenation of two child node hashes. - Output: - a 16-byte hash. This function is used in both stateful and stateless paths, and by both the signer and the verifier. ```py def H(pk_seed: Bytes[16], ADRS: Union[XmssTree, FxmssTree, ForsTree], M_2: Bytes[32]) -> Bytes[16]: return sha256(pk_seed + zeros(48) + ADRS.to_bytes() + M_2)[:16] ``` ##### `H_grind(...)` The `H_grind` tweaked hash function. Maps a 32-byte `digest` and grinding `counter` into the constant-sum message space for WOTS+C. - Inputs: - `pk_seed`: a 16-byte public seed. - `ADRS`: a `WotsCGrind` address, of which only the leading 10 bytes are hashed. - `digest`: a 32-byte digest. - `counter`: a 16-bit unsigned integer. - Output: - a 16-byte hash. This function is only used in the stateful path, and by both the signer and the verifier. ```py def H_grind(pk_seed: Bytes[16], ADRS: WotsCGrind, digest: Bytes[32], counter: UInt16) -> Bytes[16]: return sha256(pk_seed + zeros(48) + ADRS.to_bytes()[:10] + digest + zeros(4) + counter.to_bytes(2))[:16] ``` The extra 4 bytes of padding before the counter ensures the counter lines up with the SHA256 message schedule boundaries. Notice we only use the first 10 bytes of `ADRS`. This ensures the entire hash input fits inside a single SHA256 compression call, given the cached `pk_seed` input. The remaining 12 bytes are always zero padding. #### Pseudorandom Functions A _pseudorandom function_ produces output indistinguishable from random to anyone who does not know its key. SHRINCS instantiates its two pseudorandom functions as _keyed hash functions_, that is, hash functions that take a dedicated key input alongside the message. Both are keyed by a secret: `PRF` is keyed by `sk_seed` and derives secret key material, while `PRF_msg` is keyed by `sk_prf` and derives the per-message randomizer. `PRF_msg` comes in a stateless and a stateful variant, `PRF_msg_sl` and `PRF_msg_sf`, both built on HMAC-SHA256[^hmac], which we invoke as the function `hmac_sha256(key, message)`. ##### `hmac_sha256(...)` The `hmac_sha256` keyed hash function. - Inputs: - `key`: a key of at most 64 bytes. - `message`: a message of at most `2**61 - 1 - 64` bytes. - Output: - a 32-byte hash. ```py def hmac_sha256(key: Bytes[:64], message: Bytes[:2**61 - 1 - 64]) -> Bytes[32]: padded_key = key + zeros(64 - len(key)) inner = sha256(xor(padded_key, replicate(0x36, 64)) + message) return sha256(xor(padded_key, replicate(0x5C, 64)) + inner) ``` ##### `PRF(...)` The `PRF` pseudorandom function. Derives a secret 16-byte preimage from `sk_seed`, for signing and key generation. - Inputs: - `pk_seed`: a 16-byte public seed. - `sk_seed`: a 16-byte secret. - `ADRS`: a `WotsTwPrf`, `WotsCPrf` or `ForsPrf` address. - Output: - a 16-byte hash. This function is used in both stateful and stateless paths, but only by the signer. ```py def PRF( pk_seed: Bytes[16], sk_seed: Bytes[16], ADRS: Union[WotsTwPrf, WotsCPrf, ForsPrf] ) -> Bytes[16]: return sha256(pk_seed + zeros(48) + ADRS.to_bytes() + sk_seed)[:16] ``` Note the order of the arguments passed to `PRF` is _not_ the same order in which those arguments are processed by `sha256`. This aligns with definitions in FIPS-205[^slhdsa]. ##### `PRF_msg_sl(...)` The `PRF_msg_sl` pseudorandom function. Derives the per-message randomizer for the stateless path via HMAC-SHA256. - Inputs: - `sk_prf`: a 16-byte secret. - `opt_rand`: a 16-byte value. - `M`: a variable-length message. - Output: - a 16-byte hash. This function is only used in the stateless path, and only by the signer. `opt_rand` is set to either `pk_seed` (giving the "deterministic variant" of SLH-DSA[^slhdsa]), or a 16-byte random value sampled from a secure RNG (the "hedged variant" of SLH-DSA, which increases resistance to side-channel attacks). ```py def PRF_msg_sl(sk_prf: Bytes[16], opt_rand: Bytes[16], M: bytes) -> Bytes[16]: return hmac_sha256(key=sk_prf, message=opt_rand + M)[:16] ``` ##### `PRF_msg_sf(...)` The `PRF_msg_sf` function. Derives the per-message randomizer for the stateful path via HMAC-SHA256. - Inputs: - `sk_prf`: a 16-byte secret. - `pk_seed`: a 16-byte public seed. - `leaf_height`: an 8-bit unsigned integer, the height of the signing leaf. - `leaf_index`: a 64-bit unsigned integer, the index of the signing leaf. - `M`: a variable-length message. - Output: - a 16-byte hash. This function is only used in the stateful path, and only by the signer. ```py def PRF_msg_sf( sk_prf: Bytes[16], pk_seed: Bytes[16], leaf_height: UInt8, leaf_index: UInt64, M: bytes ) -> Bytes[16]: leaf = leaf_height.to_bytes(1) + leaf_index.to_bytes(8) return hmac_sha256(key=sk_prf + replicate(0xFF, 48), message=pk_seed + leaf + M)[:16] ``` The `sk_prf` is padded with `0xFF` up until it is 64 bytes long. This ensures domain separation between stateful and stateless paths. We remove the randomization input option for the stateful path compared to `PRF_msg_sl` as the same WOTS+C instance can sign a message only once, but in a misuse scenario where the same message is queried for a signature under the same state, producing exactly the same signature will not constitute a forgery. We only use the first 9 bytes of `ADRS`, because these bytes encode the position of the WOTS+C leaf in the FXMSS tree. #### Message Digest Functions Signing does not hash the user's message directly. Instead, the message is compressed together with a randomizer `R` into a short digest, which the one-time and few-time signatures then sign. SHRINCS uses a different digest function on each path. The stateless `H_msg_sl` is a keyed hash function, keyed by `R`. The stateful `H_msg_sf` additionally binds the position of the signing leaf, and so takes a tweak (the `ADRS`) in addition to `R`; it is therefore a tweakable hash function rather than a plain keyed hash. ##### `H_msg_sl(...)` The `H_msg_sl` message hash function. Produces the 32-byte signing digest for the stateless path. - Inputs: - `R`: a 16-byte randomizer. - `pk_seed`: a 16-byte public seed. - `sl_root`: the 16-byte stateless root hash. - `M`: a variable-length message. - Output: - a 32-byte hash. This function is only used in the stateless path, and by both the signer and the verifier. Note that `pk_seed` is not padded in this keyed hash function. ```py def H_msg_sl(R: Bytes[16], pk_seed: Bytes[16], sl_root: Bytes[16], M: bytes) -> Bytes[32]: return sha256(R + pk_seed + sha256(R + pk_seed + sl_root + M) + zeros(4)) ``` The outer hash computes the first 32-byte MGF1-SHA-256 block. `slh_dsa_digest_message` consumes its first `m = 24` bytes, which match the FIPS-205 definition for this parameter set.[^slhdsa][^mgf1] ##### `H_msg_sf(...)` The `H_msg_sf` message hash function. Produces the 32-byte signing digest for the stateful path. - Inputs: - `R`: a 16-byte randomizer. - `pk_seed`: a 16-byte public seed. - `sf_root`: the 16-byte stateful root hash. - `leaf_height`: an 8-bit unsigned integer, the height of the signing leaf. - `leaf_index`: a 64-bit unsigned integer, the index of the signing leaf. - `M`: a variable-length message. - Output: - a 32-byte hash. This function is only used in the stateful path, and by both the signer and the verifier. Note that `pk_seed` is not padded in this tweakable hash function. ```py def H_msg_sf( R: Bytes[16], pk_seed: Bytes[16], sf_root: Bytes[16], leaf_height: UInt8, leaf_index: UInt64, M: bytes, ) -> Bytes[32]: leaf = leaf_height.to_bytes(1) + leaf_index.to_bytes(8) return sha256(R + pk_seed + sha256(R + pk_seed + sf_root + leaf + M) + leaf) ``` Notice we only use the first 9 bytes of `ADRS`, because these bytes encode the position of the WOTS+C leaf in the FXMSS tree. Unlike `H_msg_sl`, `H_msg_sf` is specific to the stateful component and therefore need not match the definition of `H_msg` in FIPS-205[^slhdsa]. This accounts for two intentional differences from `H_msg_sl`: - There is no trailing 4-byte zero-padding on the outer hash. That padding exists only to make `H_msg_sl` match the MGF1-SHA-256[^mgf1] definition mandated by FIPS-205, which does not apply here. - The WOTS+C leaf position given by `ADRS` is bound into both the inner and outer hash inputs. This domain-separates the stateful digest by the leaf used to sign it. #### Implementation Notes - The only difference between `T_sf`, `T_sl`, `T_k`, `F`, and `H` is the byte-length of the third input parameter. They are defined as different hash functions for security. - `PRF_msg_sl` may be replaced with an XOF such as MGF1-SHA-256 or SHAKE256, from which the caller can sample multiple randomizers for the purposes of grinding to implement hypertree pruning[^pruning] more efficiently. For security, the XOF itself needs to provide the required security guarantees of a PRF, and the XOF should absorb the same inputs as `PRF_msg_sl`. - `F(...)` is the most performance-critical hash function to optimize, as it dominates the runtime of signing, keygen, and verification. - The padded `pk_seed` should be absorbed into a SHA256 midstate which is cached and reused. **This doubles performance.** - These tweakable hash functions often handle secret inputs like `sk_seed`, so implementations should be free of control flows which branch and leak side-channel information based on potentially-secret data. Inputs should not be copied in memory unless securely erased afterwards. - Many of these hash functions are invoked on independent data, and so can be run in parallel. Platforms with access to vectorized (SIMD) instruction sets on x86[^simd_x86] or ARM[^simd_arm] CPUs may utilize them to parallelize SHA256[^sha256x8] to improve performance significantly: a factor of 4 or more in some cases. - Implementors can use SHA2 hardware acceleration[^sha_ni], though this is best used to accelerate verification, not signing or keygen[^sha_ni_bench]. ### WOTS Schemes A _one-time signature_ (OTS) scheme restricts signers to creating at most one signature per keypair. If this assumption is broken by publishing distinct signatures, then adversaries will be capable of forging new ones. While limited in their practical utility, hash-based OTS schemes are a crucial building block to construct more advanced hash-based signature schemes. The following two sections describe a pair of related one-time signature schemes: WOTS-TW and WOTS+C. - WOTS+C is used for the stateful signing path. - WOTS-TW is used for the stateless signing path. Both WOTS-TW and WOTS+C are variants of the original _Winternitz one-time signature scheme_ (WOTS),[^merkle] but each has a distinct performance profile and features. WOTS-TW is standardized in SLH-DSA[^slhdsa] and so we use it to preserve compatibility. WOTS+C produces shorter signatures with faster and constant-work verification, but is not compatible with SLH-DSA and so we only use it on the stateful path where compatibility is not a concern. WOTS+C can also technically fail when signing, a rare edge case which parameters must be carefully engineered to avoid. #### Informal Description Here follows an intuitive description of Winternitz OTS (WOTS) schemes in general. A WOTS private key is an array of secret preimages. Each preimage is hashed, and the output is then hashed again, and so on, forming a _chain_ of hashes. After some prescribed number of steps in the chain (iterating the hash function) we reach the _tip_ of the hash chain. The _tips_ of those hash chains form the Winternitz public key. To sign, the key holder maps an approved message to a set of integers which each index a node in a hash chain, and reveals the hashes at those indexes as the Winternitz signature. The verifier maps the message to those same integers as the signer did, and finishes computing the hash chains. If the signer revealed the correct nodes, then the verifier will have recomputed the same hash chain tips that compose the signer's public key. This diagram illustrates a simplified example of WOTS, using 4 hash chains of length 4 to sign an 8-bit message. As written, this would be insecure: Adversaries could forge signatures by finding a message which maps to a higher set of indexes. WOTS-TW and WOTS+C differ only in their solutions to this problem: WOTS-TW appends additional "checksum" hash chains, while WOTS+C appends a two-byte counter which the signer must grind to find a set of indexes which sum to a specific constant. ### WOTS Algorithm Both WOTS schemes iterate their hash chains the same way, differing only in the `ADRS` type the steps are tweaked by. Each scheme therefore has its own chaining function, which sets that type itself rather than leaving it to every caller. #### `wots_tw_chain_iter(...)` The WOTS-TW hash chain iteration function. Iterates the hash chain from index `start` by `steps` steps, returning the node at index `start + steps`. Each step is tweaked by the address of the chain, with the hash index set to that step. - Inputs: - `node`: a 16-byte hash. - `start`: a 32-bit unsigned integer, the index of `node` in its hash chain, less than `2**WOTS_TW_CHAIN_BITS`. - `steps`: a 32-bit unsigned integer, the number of steps to take up the chain; `start + steps` must not exceed `2**WOTS_TW_CHAIN_BITS - 1`. - `pk_seed`: a 16-byte public seed. - `layer`: an 8-bit unsigned integer, the hypertree layer of the XMSS tree. - `tree_address`: a 64-bit unsigned integer, the index of the XMSS tree in its layer. - `keypair_index`: a 32-bit unsigned integer, the index of the WOTS-TW keypair. - `chain_index`: a 32-bit unsigned integer, the index of the chain within the keypair. - Output: - a 16-byte hash at index `start + steps`. This function is only used in the stateless path, and by both the signer and the verifier. ```py def wots_tw_chain_iter( node: Bytes[16], start: UInt32, steps: UInt32, pk_seed: Bytes[16], layer: UInt8, tree_address: UInt64, keypair_index: UInt32, chain_index: UInt32, ) -> Bytes[16]: for j in range(start, start+steps): node = F(pk_seed, WotsTwHash(layer, tree_address, keypair_index, chain_index, j), node) return node ``` #### `wots_c_chain_iter(...)` The WOTS+C hash chain iteration function. Iterates the hash chain from index `start` by `steps` steps, returning the node at index `start + steps`. Each step is tweaked by the address of the chain, with the hash index set to that step. - Inputs: - `node`: a 16-byte hash. - `start`: a 32-bit unsigned integer, the index of `node` in its hash chain, less than `2**WOTS_C_CHAIN_BITS`. - `steps`: a 32-bit unsigned integer, the number of steps to take up the chain; `start + steps` must not exceed `2**WOTS_C_CHAIN_BITS - 1`. - `pk_seed`: a 16-byte public seed. - `node_height`: an 8-bit unsigned integer, the height of the WOTS+C leaf in the FXMSS tree. - `node_index`: a 64-bit unsigned integer, the index of the WOTS+C leaf in the FXMSS tree. - `chain_index`: a 32-bit unsigned integer, the index of the chain within the keypair. - Output: - a 16-byte hash at index `start + steps`. This function is only used in the stateful path, and by both the signer and the verifier. ```py def wots_c_chain_iter( node: Bytes[16], start: UInt32, steps: UInt32, pk_seed: Bytes[16], node_height: UInt8, node_index: UInt64, chain_index: UInt32, ) -> Bytes[16]: for j in range(start, start+steps): node = F(pk_seed, WotsCHash(node_height, node_index, chain_index, j), node) return node ``` ### WOTS-TW WOTS-TW is the classic variant of Winternitz one-time signatures[^merkle] which uses a checksum to prevent forgeries. In WOTS-TW, a 128-bit message is mapped directly into an array of `WOTS_TW_CHAIN_COUNT1` hash chain indexes, and the checksum is simply the negation of the sum of those indexes. This checksum is then encoded into `WOTS_TW_CHAIN_COUNT2` hash chain indexes which are appended to the message indexes before signing and verification. This process starts by breaking a 128-bit message into `WOTS_TW_CHAIN_COUNT1` integers of `WOTS_TW_CHAIN_BITS` bits each in the range `[0, 2**WOTS_TW_CHAIN_BITS)`. The maximum possible sum of those indexes would be if every index was equal to `2**WOTS_TW_CHAIN_BITS - 1`, so the maximum sum is ```py WOTS_TW_CHECKSUM_MAX = WOTS_TW_CHAIN_COUNT1 * (2**WOTS_TW_CHAIN_BITS - 1) ``` This constant is also defined explicitly in the earlier [table of derived constants](#derived-constants). Given an array of `msg_indexes`, the checksum can be computed by: ```py checksum = WOTS_TW_CHECKSUM_MAX - sum(msg_indexes) ``` This checksum is then converted into `WOTS_TW_CHAIN_COUNT2` integers of `WOTS_TW_CHAIN_BITS` bits each, which are appended to the original `msg_indexes`. #### `wots_tw_message_to_indexes(...)` The WOTS-TW message map function. Converts a 16-byte `message` into a checksummed array of `WOTS_TW_CHAIN_COUNT` chain indexes in `[0, 2**WOTS_TW_CHAIN_BITS)`. - Inputs: - `message`: a 16-byte hash. - Output: - a checksummed array of `WOTS_TW_CHAIN_COUNT` `WOTS_TW_CHAIN_BITS`-bit unsigned integers. This function is only used in the stateless path, and by both the signer and the verifier. ```py def wots_tw_message_to_indexes(message: Bytes[16]) -> Array[UInt16, WOTS_TW_CHAIN_COUNT]: msg_indexes = base_2b(message, WOTS_TW_CHAIN_BITS, WOTS_TW_CHAIN_COUNT1) checksum = WOTS_TW_CHECKSUM_MAX - sum(msg_indexes) checksum_indexes = [0] * WOTS_TW_CHAIN_COUNT2 for i in range(WOTS_TW_CHAIN_COUNT2): checksum_indexes[WOTS_TW_CHAIN_COUNT2 - 1 - i] = checksum % (2**WOTS_TW_CHAIN_BITS) checksum //= 2**WOTS_TW_CHAIN_BITS return msg_indexes + checksum_indexes ``` Alternative implementation, equivalent to `wots_tw_message_to_indexes` but using the more complex FIPS-205 algorithm. ```py def wots_tw_message_to_indexes_alt(message: Bytes[16]) -> Array[UInt16, WOTS_TW_CHAIN_COUNT]: SPHX_WOTS_CHECKSUM_SHIFT = (8 - (WOTS_TW_CHAIN_BITS * WOTS_TW_CHAIN_COUNT2) % 8) % 8 SPHX_WOTS_CHECKSUM_BYTE_LEN = ceildiv(WOTS_TW_CHAIN_COUNT2 * WOTS_TW_CHAIN_BITS, 8) msg_indexes = base_2b(message, WOTS_TW_CHAIN_BITS, WOTS_TW_CHAIN_COUNT1) checksum = (WOTS_TW_CHECKSUM_MAX - sum(msg_indexes)) * 2**SPHX_WOTS_CHECKSUM_SHIFT checksum_bytes = checksum.to_bytes(SPHX_WOTS_CHECKSUM_BYTE_LEN) checksum_indexes = base_2b(checksum_bytes, WOTS_TW_CHAIN_BITS, WOTS_TW_CHAIN_COUNT2) return msg_indexes + checksum_indexes ``` This algorithm is used by both signer and verifier, and **it is security-critical for both implementations to match.** Note especially how the _low-order_ bits of the checksum are shifted off first, and they are inserted snugly at the very end of the checksum indexes, with some padding bits which are always zero in between them and the message indexes. The checksum bits are NOT appended directly to the message indexes. ##### Example Consider the following message indexes: ```py msg = [10, 11, 2, 2, 3, 12, 15, 8, 1, 2, 8, 2, 2, 10, 9, 13, 10, 11, 2, 2, 3, 12, 15, 8, 1, 2, 8, 2, 2, 10, 9, 13] ``` The checksum of these message indexes is: ```py checksum = WOTS_TW_CHECKSUM_MAX - sum(msg) = 260 = 0b100000100 ``` The original message has a binary representation: ``` 1010 1011 0010 ... 1010 1001 1101 ``` After appending the checksum, the final checksummed index sequence should look like this: ``` 1010 1011 0010 ... 1010 1001 1101 0001 0000 0100 ^^^^^^^^^^^^^^ checksum ``` #### `wots_tw_pubkey_gen(...)` The WOTS-TW public key generation function. Computes the 16-byte WOTS-TW public key of the keypair at `keypair_index` in the XMSS tree at `layer` and `tree_address`. - Inputs: - `sk_seed`: a 16-byte secret. - `pk_seed`: a 16-byte public seed. - `layer`: an 8-bit unsigned integer, the hypertree layer of the XMSS tree. - `tree_address`: a 64-bit unsigned integer, the index of the XMSS tree in its layer. - `keypair_index`: a 32-bit unsigned integer, the index of the WOTS-TW keypair. - Output: - a 16-byte hash representing the WOTS-TW public key. This function is only used in the stateless path, and only by the signer. ```py def wots_tw_pubkey_gen( sk_seed: Bytes[16], pk_seed: Bytes[16], layer: UInt8, tree_address: UInt64, keypair_index: UInt32, ) -> Bytes[16]: wots_pk = [b''] * WOTS_TW_CHAIN_COUNT for i in range(WOTS_TW_CHAIN_COUNT): sk = PRF(pk_seed, sk_seed, WotsTwPrf(layer, tree_address, keypair_index, i)) wots_pk[i] = wots_tw_chain_iter( sk, 0, 2**WOTS_TW_CHAIN_BITS - 1, pk_seed, layer, tree_address, keypair_index, i ) return T_sl(pk_seed, WotsTwPk(layer, tree_address, keypair_index), concat(wots_pk)) ``` #### `wots_tw_sign(...)` The WOTS-TW signing function. Produces a WOTS-TW signature on a 16-byte `message`, with the keypair at `keypair_index` in the XMSS tree at `layer` and `tree_address`. - Inputs: - `message`: a 16-byte message to sign. - `sk_seed`: a 16-byte secret. - `pk_seed`: a 16-byte public seed. - `layer`: an 8-bit unsigned integer, the hypertree layer of the XMSS tree. - `tree_address`: a 64-bit unsigned integer, the index of the XMSS tree in its layer. - `keypair_index`: a 32-bit unsigned integer, the index of the WOTS-TW keypair. - Output: - a `WOTS_TW_CHAINS_SIZE`-byte signature. This function is only used in the stateless path, and only by the signer. ```py def wots_tw_sign( message: Bytes[16], sk_seed: Bytes[16], pk_seed: Bytes[16], layer: UInt8, tree_address: UInt64, keypair_index: UInt32, ) -> Bytes[WOTS_TW_CHAINS_SIZE]: indexes = wots_tw_message_to_indexes(message) signature = [b''] * WOTS_TW_CHAIN_COUNT for i in range(WOTS_TW_CHAIN_COUNT): sk = PRF(pk_seed, sk_seed, WotsTwPrf(layer, tree_address, keypair_index, i)) signature[i] = wots_tw_chain_iter( sk, 0, indexes[i], pk_seed, layer, tree_address, keypair_index, i ) return concat(signature) ``` #### `wots_tw_pubkey_from_sig(...)` The WOTS-TW verification function. Recovers a WOTS-TW public key from a `signature` on a 16-byte `message`. - Inputs: - `signature`: a `WOTS_TW_CHAINS_SIZE`-byte signature. - `message`: a 16-byte message. - `pk_seed`: a 16-byte public seed. - `layer`: an 8-bit unsigned integer, the hypertree layer of the XMSS tree. - `tree_address`: a 64-bit unsigned integer, the index of the XMSS tree in its layer. - `keypair_index`: a 32-bit unsigned integer, the index of the WOTS-TW keypair. - Output: - a 16-byte hash representing the WOTS-TW public key. This function is only used in the stateless path, and by both the signer and the verifier. ```py def wots_tw_pubkey_from_sig( signature: Bytes[WOTS_TW_CHAINS_SIZE], message: Bytes[16], pk_seed: Bytes[16], layer: UInt8, tree_address: UInt64, keypair_index: UInt32, ) -> Bytes[16]: indexes = wots_tw_message_to_indexes(message) wots_pk = [b''] * WOTS_TW_CHAIN_COUNT for i in range(WOTS_TW_CHAIN_COUNT): steps = 2**WOTS_TW_CHAIN_BITS - 1 - indexes[i] wots_pk[i] = wots_tw_chain_iter( signature[i*16 : (i+1)*16], indexes[i], steps, pk_seed, layer, tree_address, keypair_index, i ) return T_sl(pk_seed, WotsTwPk(layer, tree_address, keypair_index), concat(wots_pk)) ``` ### WOTS+C WOTS+C was designed as an improvement to WOTS-TW[^sphincs+c]. It is superior in compactness & performance, but we nonetheless use WOTS-TW for the stateless path to retain compatibility with SLH-DSA[^slhdsa], while WOTS+C is used in the custom stateful component of SHRINCS to reduce signature size. WOTS+C replaces the checksum in WOTS-TW with a protocol requirement that any message must be mapped to a set of indexes that sum to a fixed constant. This prevents WOTS forgeries because an incremental increase in any index of a hash chain must be balanced out by decrementing a different index. It also ensures a fixed-work verifier because the total number of hash operations needed to complete every WOTS hash chain is fixed. The constant-sum parameter `WOTS_C_CONSTANT_SUM` is chosen to maximize the probability that a randomly selected set of indexes will sum to this value. It can be computed by: ```py WOTS_C_CONSTANT_SUM = ceildiv(WOTS_C_CHAIN_COUNT * (2**WOTS_C_CHAIN_BITS - 1), 2) ``` Only a subset of index-sets have this "constant-sum" property - for the chosen parameters, about 2122 out of the possible 2128 sets of indexes. To map a given message onto this subset, the signer must _grind_ a hash function applied to the message and a rolling integer counter. The hash function ensures the surjective mapping of messages to index-sets is one-way and distributed randomly. If the mapping were not one-way, an attacker could work backwards to find other messages valid under the same signature. Eventually the signer finds a counter which maps the message to a set of indexes that sum to `WOTS_C_CONSTANT_SUM`. This counter is appended to the WOTS+C signature. The verifier rejects counters which don't map the message to a constant-sum index-set. #### `wots_c_grind_to_constant_sum(...)` The WOTS+C grinding function. Grinds up to 2^16 counters until one maps `message_digest` to a constant-sum index set, returning the lowest such counter and its index set. - Inputs: - `pk_seed`: a 16-byte public seed. - `message_digest`: a 32-byte intermediate message digest (from `H_msg_sf`). - `node_height`: an 8-bit unsigned integer, the height of the WOTS+C leaf in the FXMSS tree. - `node_index`: a 64-bit unsigned integer, the index of the WOTS+C leaf in the FXMSS tree. - Outputs: - the smallest valid grinding `counter`: a 16-bit unsigned integer. - the constant-sum set of hash chain indexes it yields: `WOTS_C_CHAIN_COUNT` `WOTS_C_CHAIN_BITS`-bit unsigned integers. - or null, in place of both. This function is only used in the stateful path, and only by the signer. ```py def wots_c_grind_to_constant_sum( pk_seed: Bytes[16], message_digest: Bytes[32], node_height: UInt8, node_index: UInt64 ) -> Optional[tuple[UInt16, Array[UInt16, WOTS_C_CHAIN_COUNT]]]: ADRS = WotsCGrind(node_height, node_index) for i in range(2**16): hashed = H_grind(pk_seed, ADRS, message_digest, i) indexes = base_2b(hashed, WOTS_C_CHAIN_BITS, WOTS_C_CHAIN_COUNT) if sum(indexes) == WOTS_C_CONSTANT_SUM: return (i, indexes) return None # practically impossible ``` We max out at 216 grinding attempts because the counter is serialized as a 16-bit unsigned integer in the WOTS+C signature encoding - Counters larger than this would not fit into a signature. There is technically a chance that the signer may exhaust all of these attempts without finding a valid counter; however, we have engineered our parameter set such that this probability is less than 1 chance in 21450[^wotsgrind] - practically impossible. > [!NOTE] > [The `return None` control path can typically be ignored in real-world implementations](#on-signing-fallibility). #### `wots_c_map_digest(...)` The WOTS+C digest validation function. Evaluates a signature's grinding `counter` and returns the constant-sum index set it yields, or null if the counter is invalid. - Inputs: - `pk_seed`: a 16-byte public seed. - `message_digest`: a 32-byte intermediate message digest (from `H_msg_sf`). - `node_height`: an 8-bit unsigned integer, the height of the WOTS+C leaf in the FXMSS tree. - `node_index`: a 64-bit unsigned integer, the index of the WOTS+C leaf in the FXMSS tree. - `counter`: a 16-bit unsigned integer. - Output: - a constant-sum set of hash chain indexes (`WOTS_C_CHAIN_COUNT` `WOTS_C_CHAIN_BITS`-bit unsigned integers), or null. This function is only used in the stateful path, and only by the verifier. ```py def wots_c_map_digest( pk_seed: Bytes[16], message_digest: Bytes[32], node_height: UInt8, node_index: UInt64, counter: UInt16, ) -> Optional[Array[UInt16, WOTS_C_CHAIN_COUNT]]: hashed = H_grind(pk_seed, WotsCGrind(node_height, node_index), message_digest, counter) indexes = base_2b(hashed, WOTS_C_CHAIN_BITS, WOTS_C_CHAIN_COUNT) if sum(indexes) == WOTS_C_CONSTANT_SUM: return indexes else: return None ``` #### `wots_c_pubkey_gen(...)` The WOTS+C public key generation function. Computes the 16-byte WOTS+C public key of the leaf at `node_height` and `node_index` in the FXMSS tree. - Inputs: - `sk_seed`: a 16-byte secret. - `pk_seed`: a 16-byte public seed. - `node_height`: an 8-bit unsigned integer, the height of the WOTS+C leaf in the FXMSS tree. - `node_index`: a 64-bit unsigned integer, the index of the WOTS+C leaf in the FXMSS tree. - `tree_balanced`: a boolean, true for a balanced (BXMSS) tree and false for an unbalanced (UXMSS) tree. - `tree_depth`: an 8-bit unsigned integer, the depth of the FXMSS tree. - Output: - a 16-byte hash representing the WOTS+C public key. This function is only used in the stateful path, and only by the signer. ```py def wots_c_pubkey_gen( sk_seed: Bytes[16], pk_seed: Bytes[16], node_height: UInt8, node_index: UInt64, tree_balanced: bool, tree_depth: UInt8, ) -> Bytes[16]: wots_pk = [b''] * WOTS_C_CHAIN_COUNT for i in range(WOTS_C_CHAIN_COUNT): sk = PRF( pk_seed, sk_seed, WotsCPrf(node_height, node_index, tree_balanced, tree_depth, i) ) wots_pk[i] = wots_c_chain_iter( sk, 0, 2**WOTS_C_CHAIN_BITS - 1, pk_seed, node_height, node_index, i ) return T_sf(pk_seed, WotsCPk(node_height, node_index), concat(wots_pk)) ``` #### `wots_c_sign(...)` The WOTS+C signing function. Produces a WOTS+C signature on a 32-byte `message_digest`, with the leaf at `node_height` and `node_index` in the FXMSS tree. - Inputs: - `message_digest`: a 32-byte message digest to sign. - `sk_seed`: a 16-byte secret. - `pk_seed`: a 16-byte public seed. - `node_height`: an 8-bit unsigned integer, the height of the WOTS+C leaf in the FXMSS tree. - `node_index`: a 64-bit unsigned integer, the index of the WOTS+C leaf in the FXMSS tree. - `tree_balanced`: a boolean, true for a balanced (BXMSS) tree and false for an unbalanced (UXMSS) tree. - `tree_depth`: an 8-bit unsigned integer, the depth of the FXMSS tree. - Output: - a `2 + WOTS_C_CHAINS_SIZE`-byte signature, or null. This function is only used in the stateful path, and only by the signer. ```py def wots_c_sign( message_digest: Bytes[32], sk_seed: Bytes[16], pk_seed: Bytes[16], node_height: UInt8, node_index: UInt64, tree_balanced: bool, tree_depth: UInt8, ) -> Optional[Bytes[2 + WOTS_C_CHAINS_SIZE]]: grinded = wots_c_grind_to_constant_sum(pk_seed, message_digest, node_height, node_index) if grinded is None: return None # practically impossible counter, indexes = grinded signature = [b''] * WOTS_C_CHAIN_COUNT for i in range(WOTS_C_CHAIN_COUNT): sk = PRF( pk_seed, sk_seed, WotsCPrf(node_height, node_index, tree_balanced, tree_depth, i) ) signature[i] = wots_c_chain_iter( sk, 0, indexes[i], pk_seed, node_height, node_index, i ) return counter.to_bytes(2) + concat(signature) ``` > [!NOTE] > [The `return None` control path can typically be ignored in real-world implementations](#on-signing-fallibility). #### `wots_c_pubkey_from_sig(...)` The WOTS+C verification function. Recovers a WOTS+C public key from a `signature` on a 32-byte `message_digest`. - Inputs: - `signature`: a `2 + WOTS_C_CHAINS_SIZE`-byte signature. - `message_digest`: a 32-byte message digest. - `pk_seed`: a 16-byte public seed. - `node_height`: an 8-bit unsigned integer, the height of the WOTS+C leaf in the FXMSS tree. - `node_index`: a 64-bit unsigned integer, the index of the WOTS+C leaf in the FXMSS tree. - Output: - a 16-byte hash representing the WOTS+C public key, or null. This function is only used in the stateful path, and only by the verifier. ```py def wots_c_pubkey_from_sig( signature: Bytes[2 + WOTS_C_CHAINS_SIZE], message_digest: Bytes[32], pk_seed: Bytes[16], node_height: UInt8, node_index: UInt64, ) -> Optional[Bytes[16]]: counter = int.from_bytes(signature[0:2]) indexes = wots_c_map_digest(pk_seed, message_digest, node_height, node_index, counter) # Reject if counter doesn't satisfy the constant-sum requirement. if indexes is None: return None wots_pk = [b''] * WOTS_C_CHAIN_COUNT for i in range(WOTS_C_CHAIN_COUNT): steps = 2**WOTS_C_CHAIN_BITS - 1 - indexes[i] wots_pk[i] = wots_c_chain_iter( signature[2+i*16 : 2+(i+1)*16], indexes[i], steps, pk_seed, node_height, node_index, i ) return T_sf(pk_seed, WotsCPk(node_height, node_index), concat(wots_pk)) ``` ### XMSS The _eXtended Merkle Signature Scheme_ (XMSS) is a stateful hash-based signature scheme which can produce signatures on up to a fixed number of messages. Conceptually, an XMSS keypair is a merkle tree whose leaves are one-time signature (OTS) keypairs. The XMSS public key is the root hash of the merkle tree. An XMSS signature is an OTS signature alongside a merkle tree authentication proof which links the OTS public key to the merkle root hash. The verifier recomputes the OTS public key, and follows the merkle proof to recompute the XMSS public key. In SHRINCS, we instantiate XMSS twice, to be used differently in both stateful and stateless components of a SHRINCS keypair. ``` XMSS (balanced) | FXMSS (flexible) | root | root ___/ \___ | / \ O O | O L / \ / \ | / \ O O O O | L O / \ / \ / \ / \ | / \ L L L L L L L L | L L O = inner Merkle node L = WOTS leaf (OTS keypair) ``` Both schemes are Merkle trees whose leaves are OTS keypairs and whose root is the public key. Their tree structures differ: XMSS (stateless path) is always a perfectly balanced tree of fixed height, while FXMSS (stateful path) admits flexible structures, with WOTS+C leaves placed at varying depths. - In the stateless component, traditional balanced XMSS is used with WOTS-TW as the leaf OTS scheme to certify child layers of the SLH-DSA hypertree, and to certify FORS public keys. - In the stateful component, Flexible XMSS (FXMSS) is used with WOTS+C to sign messages directly. In XMSS (stateless path), merkle trees are always perfectly balanced, and always have a fixed height `SPHX_XMSS_HEIGHT`. This matches the XMSS tree structure specified in FIPS-205. In FXMSS (stateful path), merkle trees can be balanced or unbalanced, and the WOTS+C leaf keys may be placed up to `FXMSS_HEIGHT` layers deep. This permits more flexible constructions. Notably for security, XMSS is always used as part of the SPHINCS (SLH-DSA) framework to sign trusted messages generated by the signer, while FXMSS is used as a standalone scheme and so may sign untrusted messages. This means the interfaces of both XMSS and FXMSS are slightly different, and this is a crucial security requirement. >[!note] > ### On Merkle Tree Positions > > Every node in an XMSS or FXMSS merkle tree is identified by a pair of coordinates: a _height_ and an _index_. > > The index counts nodes from the left within a layer, starting at zero. > The node at height `h` and index `i` has child nodes at indexes `2*i` (left) and `2*i + 1` (right) at height `h - 1`. > Conversely, the ancestor of that node `j` layers above it has index `i >> j`, and the sibling of that ancestor has index `(i >> j) ^ 1`. > > More specifically for the different merkle tree constructions of XMSS, FXMSS, and FORS: > > - In XMSS, the WOTS-TW leaves sit at height 0, and the root sits at height `SPHX_XMSS_HEIGHT`. > All leaves share a common layer. > - In FXMSS, the WOTS+C leaves can sit at any height, and the root always sits at height `FXMSS_HEIGHT`. > We often refer to a node's depth as its distance below the root: `depth = FXMSS_HEIGHT - height`. > Because WOTS+C leaves may be placed at different depths, there is no common leaf layer. > A leaf sits at height 0 only at the maximum depth of 255. > In this sense `FXMSS_HEIGHT` is an "imaginary" height because no real FXMSS tree can fully explore the enormous possible space of 2256 nodes. > - In FORS, the preimage leaves sit at height 0, and the root of each of the merkle trees in the forest is at height `SPHX_FORS_HEIGHT`. > All leaves share a common layer, but internally FORS tree node indexes count across the entire forest, and so the indexing scheme is more subtle. > A node at index `i` in the `j`-th FORS tree at height `h` actually has a forest-wide index of `j * 2**(SPHX_FORS_HEIGHT - h) + i`, which is filled in the `tree_index` field in `ADRS` under the `SL_FORS_TREE` type. > In other words, the index of a FORS node or leaf must account for all the other nodes to its left at the same height in the other FORS trees. > > When merkle nodes are combined with the hash function `H`, the coordinates written into the `ADRS` are those of the node being computed (the parent), not of its children. > In XMSS, the tree height field of an `SL_XMSS_TREE` address therefore only takes values 1 through `SPHX_XMSS_HEIGHT` - Leaf nodes are not addressed by tree coordinates at all, but through the WOTS-TW keypair index, which equals the leaf's index at height 0. > In FXMSS (stateful path), a WOTS+C leaf's coordinates are carried in the `node_height` and `node_index` fields of `ADRS`. Unlike a directionless merkle tree, XMSS requires explicit left/right direction in the structure of its merkle tree for security.[^xmss-directional] The following sections describe the XMSS and FXMSS algorithms. ### XMSS (stateless) These algorithms are used only for the stateless XMSS sub-scheme. #### `xmss_node(...)` The XMSS internal node computation function. Recursively computes the XMSS node at the given `node_index` and `node_height`, in the XMSS tree at `layer` and `tree_address`. - Inputs: - `sk_seed`: a 16-byte secret. - `node_index`: a 32-bit unsigned integer, the index (from the left) of the node in the XMSS layer. - `node_height`: a 32-bit unsigned integer, the height (from the bottom) of the node in the XMSS layer. - `pk_seed`: a 16-byte public seed. - `layer`: an 8-bit unsigned integer, the hypertree layer of the XMSS tree. - `tree_address`: a 64-bit unsigned integer, the index of the XMSS tree in its layer. - Output: - a 16-byte XMSS node hash. This function is only used in the stateless path, and only by the signer. ```py def xmss_node( sk_seed: Bytes[16], node_index: UInt32, node_height: UInt32, pk_seed: Bytes[16], layer: UInt8, tree_address: UInt64, ) -> Bytes[16]: if node_height == 0: # Bottom layer: return the WOTS-TW pubkey hash. return wots_tw_pubkey_gen(sk_seed, pk_seed, layer, tree_address, node_index) # Recursively derive the left/right child nodes. lchild_index = 2 * node_index child_height = node_height - 1 lchild = xmss_node(sk_seed, lchild_index, child_height, pk_seed, layer, tree_address) rchild = xmss_node(sk_seed, lchild_index + 1, child_height, pk_seed, layer, tree_address) # Compute and return the parent node. parent = XmssTree(layer, tree_address, node_height, node_index) return H(pk_seed, parent, lchild + rchild) ``` #### `xmss_sign(...)` The XMSS signing function. Produces a deterministic WOTS-TW signature at leaf `keypair_index` and appends the Merkle authentication path to form an XMSS signature, in the XMSS tree at `layer` and `tree_address`. - Inputs: - `message`: a 16-byte message to sign. - `sk_seed`: a 16-byte secret. - `keypair_index`: a 32-bit unsigned integer, the index of the WOTS-TW keypair to sign with. - `pk_seed`: a 16-byte public seed. - `layer`: an 8-bit unsigned integer, the hypertree layer of the XMSS tree. - `tree_address`: a 64-bit unsigned integer, the index of the XMSS tree in its layer. - Output: - a `SPHX_XMSS_SIGNATURE_SIZE`-byte signature. This function is only used in the stateless path, and only by the signer. ```py def xmss_sign( message: Bytes[16], sk_seed: Bytes[16], keypair_index: UInt32, pk_seed: Bytes[16], layer: UInt8, tree_address: UInt64, ) -> Bytes[SPHX_XMSS_SIGNATURE_SIZE]: # Sign the message with WOTS-TW. sig = wots_tw_sign(message, sk_seed, pk_seed, layer, tree_address, keypair_index) # Append the Merkle authentication path. for j in range(SPHX_XMSS_HEIGHT): sibling_index = (keypair_index // 2**j) ^ 1 sig += xmss_node(sk_seed, sibling_index, j, pk_seed, layer, tree_address) return sig ``` #### `xmss_pubkey_from_sig(...)` The XMSS verification function. Recovers an XMSS root from a `signature` on a 16-byte `message` at leaf `keypair_index`, in the XMSS tree at `layer` and `tree_address`. - Inputs: - `keypair_index`: a 32-bit unsigned integer, the index of the WOTS-TW keypair to sign with. - `signature`: a `SPHX_XMSS_SIGNATURE_SIZE`-byte signature. - `message`: a 16-byte message. - `pk_seed`: a 16-byte public seed. - `layer`: an 8-bit unsigned integer, the hypertree layer of the XMSS tree. - `tree_address`: a 64-bit unsigned integer, the index of the XMSS tree in its layer. - Output: - a 16-byte XMSS root node hash. This function is only used in the stateless path, and by both the signer and the verifier. ```py def xmss_pubkey_from_sig( keypair_index: UInt32, signature: Bytes[SPHX_XMSS_SIGNATURE_SIZE], message: Bytes[16], pk_seed: Bytes[16], layer: UInt8, tree_address: UInt64, ) -> Bytes[16]: wots_sig = signature[0 : WOTS_TW_CHAINS_SIZE] xmss_auth = signature[WOTS_TW_CHAINS_SIZE : SPHX_XMSS_SIGNATURE_SIZE] node = wots_tw_pubkey_from_sig(wots_sig, message, pk_seed, layer, tree_address, keypair_index) for k in range(SPHX_XMSS_HEIGHT): parent = XmssTree(layer, tree_address, k + 1, keypair_index // 2**(k+1)) sibling = xmss_auth[k*16 : (k+1)*16] if (keypair_index // 2**k) % 2 == 1: node = H(pk_seed, parent, sibling + node) else: node = H(pk_seed, parent, node + sibling) return node ``` ### Hypertree Signing The SHRINCS stateless path utilizes the design strategy of a _hypertree,_ first introduced by the original SPHINCS paper[^sphincs]. A hypertree is a tree of XMSS trees arranged into _layers_, where each OTS leaf signs the root hash of a child XMSS tree on the next layer down to certify the child tree's authenticity. Every child tree is thus verifiably connected to the root tree, in a similar fashion to TLS certificate chains. Each tree has `2**SPHX_XMSS_HEIGHT` such certified children. Because each XMSS tree is generated deterministically from a seed, the signer does not need to worry about OTS key reuse when certifying child XMSS trees, and so she can avoid caching every XMSS tree in the hypertree. The signer can _just-in-time_ generate the XMSS trees that will be used for a specific signature, and thereafter those trees can be discarded from memory. This diagram shows a simplified example with three layers of XMSS trees with height 2. A hypertree signature is simply a chain of `SPHX_LAYER_COUNT` XMSS signatures, starting from the bottom-layer which signs a given 16-byte message. The following algorithms are used only for stateless hypertree signing and verification. #### `hypertree_sign(...)` The hypertree signing function. Signs a 16-byte `message` through a hypertree of XMSS trees. - Inputs: - `message`: a 16-byte message to sign. - `sk_seed`: a 16-byte secret. - `pk_seed`: a 16-byte public seed. - `tree_index`: a 64-bit unsigned integer, the index (from the left) of the bottom-layer XMSS tree to sign with. - `leaf_index`: a 32-bit unsigned integer, the index (from the left) of the WOTS-TW key in the bottom-layer XMSS tree to sign with. - Output: - a `HYPERTREE_SIGNATURE_SIZE`-byte signature. This function is only used in the stateless path, and only by the signer. ```py def hypertree_sign( message: Bytes[16], sk_seed: Bytes[16], pk_seed: Bytes[16], tree_index: UInt64, leaf_index: UInt32, ) -> Bytes[HYPERTREE_SIGNATURE_SIZE]: sig = b"" for j in range(SPHX_LAYER_COUNT - 1): layer_sig = xmss_sign(message, sk_seed, leaf_index, pk_seed, j, tree_index) message = xmss_pubkey_from_sig(leaf_index, layer_sig, message, pk_seed, j, tree_index) leaf_index = tree_index % (2**SPHX_XMSS_HEIGHT) tree_index //= 2**SPHX_XMSS_HEIGHT sig += layer_sig layer_sig = xmss_sign(message, sk_seed, leaf_index, pk_seed, SPHX_LAYER_COUNT - 1, tree_index) sig += layer_sig return sig ``` #### `hypertree_verify(...)` The hypertree verification function. Recovers the hypertree root from a `signature` and compares it against `sl_root`. - Inputs: - `message`: a 16-byte message. - `signature`: a `HYPERTREE_SIGNATURE_SIZE`-byte signature. - `pk_seed`: a 16-byte public seed. - `tree_index`: a 64-bit unsigned integer, the index (from the left) of the bottom-layer XMSS tree to sign with. - `leaf_index`: a 32-bit unsigned integer, the index (from the left) of the WOTS-TW key in the bottom-layer XMSS tree to sign with. - `sl_root`: the 16-byte root hash of the stateless root tree. - Output: - a boolean indicating if the signature is valid. This function is only used in the stateless path, and only by the verifier. ```py def hypertree_verify( message: Bytes[16], signature: Bytes[HYPERTREE_SIGNATURE_SIZE], pk_seed: Bytes[16], tree_index: UInt64, leaf_index: UInt32, sl_root: Bytes[16], ) -> bool: for j in range(SPHX_LAYER_COUNT - 1): layer_sig = signature[j * SPHX_XMSS_SIGNATURE_SIZE : (j+1) * SPHX_XMSS_SIGNATURE_SIZE] message = xmss_pubkey_from_sig(leaf_index, layer_sig, message, pk_seed, j, tree_index) leaf_index = tree_index % (2**SPHX_XMSS_HEIGHT) tree_index //= 2**SPHX_XMSS_HEIGHT layer_sig = signature[(SPHX_LAYER_COUNT - 1) * SPHX_XMSS_SIGNATURE_SIZE : HYPERTREE_SIGNATURE_SIZE] message = xmss_pubkey_from_sig(leaf_index, layer_sig, message, pk_seed, SPHX_LAYER_COUNT - 1, tree_index) return message == sl_root ``` ### FXMSS FXMSS is the stateful signature component used by SHRINCS. An FXMSS signer selects a tree structure at key generation, subject to the addressing constraints described below.[^fxmss_node_index] The tree structure determines which positions in the FXMSS tree contain WOTS+C public keys. The FXMSS verifier is agnostic to the positions of WOTS+C public keys other than the one used for the signature. It recomputes the FXMSS root from the WOTS+C signature, the position of the corresponding public key, and the Merkle authentication path. This allows signers to select their FXMSS tree structure at key generation without changing the verifier. Because of this flexibility, it is necessary for signers to remember what structure of FXMSS tree they created at key generation time. To encourage interoperability, we define an encoding for FXMSS tree structures which will be stored in the SHRINCS signer's serialized secret key as two additional bytes. A _tree structure_ for FXMSS is encoded as a tuple of two numbers: ***shape*** and ***depth***. - ***Shape*** is a flag byte that defines which FXMSS nodes are to be WOTS+C leaves. We will describe two recommended tree shapes below. - ***Depth*** is an 8-bit unsigned integer describing the height of the FXMSS tree, or more precisely, the distance from the root node to the deepest leaf node. These two parameters define the FXMSS _tree structure_. The shape and depth bytes will be encoded in the serialized SHRINCS secret key so that implementations which import the key have a clear directive for how to build the same FXMSS tree in the SHRINCS stateful path. Implementations which import SHRINCS keys MUST respect the shape and depth bytes to reproduce the stateful tree and issue valid stateful signatures. #### Tree Shapes This specification prescribes two FXMSS tree shapes: **Unbalanced XMSS (UXMSS)** and **Balanced XMSS (BXMSS)**. Both shapes use the same FXMSS verifier. They differ in how WOTS+C public keys are placed in the tree and selected for signing. The two shapes are identified by their respective constants. | Shape Flag | Value | Description | |:-:|:-:|:-:| | `FXMSS_SHAPE_UNBALANCED` | 0 | Indicates UXMSS, with a left-leaning unbalanced tree. | | `FXMSS_SHAPE_BALANCED` | 1 | Indicates BXMSS, with a balanced tree of specific depth. | | ... | 2...255 | Reserved. | We leave open the possibility to define new shape flags for new XMSS tree structures, but we encourage signers to utilize the recommended shapes wherever possible, for the sake of security and anonymity. The following sections describe the usage properties of the two shapes, and we let the variable `depth` represent the depth byte as a parameter of the shape. ##### `FXMSS_SHAPE_UNBALANCED` When the shape byte is set to `FXMSS_SHAPE_UNBALANCED`, signers use an unbalanced, left-leaning XMSS tree of height `depth`. ``` root / \ O leaf / \ O leaf / \ O leaf / \ ... leaf / O / \ leaf leaf ``` This FXMSS tree shape allows signers to generate very short stateful signatures for the first few signatures, since the signer can use the shallowest WOTS+C leaves right away, and these have very short merkle authentication paths. However, since each WOTS+C leaf can be used only once, subsequent signatures will grow larger at a rate of 16 or 17 bytes per signature issued as the merkle authentication path grows in length, with the exception of the last signature which has the same length as the penultimate one.[^last_two_sigs] Eventually, after `depth + 1` signatures, the UXMSS stateful path will be exhausted and unusable, and the last few stateful signatures will be very large. For most use cases, unless compute power is very limited, we recommend setting `depth = FXMSS_HEIGHT` for UXMSS (the maximum), as even a WOTS+C leaf at maximum depth will still produce a shorter signature than the stateless path. FXMSS depth cannot exceed `FXMSS_HEIGHT = 255` because the FXMSS node height number is encoded into the signature and `ADRS` as a single byte. ##### `FXMSS_SHAPE_BALANCED` When the shape byte is set to `FXMSS_SHAPE_BALANCED`, signers use a balanced binary XMSS tree, of height `depth`. ``` root / \ / \ O O / \ / \ ... ... ... ... / \ / \ O O O O / \ / \ / \ / \ leaf leaf leaf leaf leaf leaf leaf leaf ``` This FXMSS tree shape allows signers to generate a larger quantity of stateful signatures. Unlike UXMSS, stateful SHRINCS signatures using a BXMSS tree will have a consistent size, up until the stateful path is exhausted, because all WOTS+C leaves will use the same merkle authentication path length. The `depth` of the BXMSS tree at key generation time has a significant impact on the performance of the SHRINCS stateful signing path. The exact size of the constant-size signatures is also dictated by `depth`: each step further from the root node we take, we must add 16 bytes to the FXMSS signature. Furthermore, each step doubles the number of leaf nodes, and so doubles the signature budget, but also doubles the amount of computational work needed for BXMSS key generation and/or signing. Signer implementations may specify any height for BXMSS trees depending on their use-cases, but typical safe defaults range from `depth = 8` (256 signatures, matching the budget of UXMSS) to `depth = 20` (1 million signatures), or more in special circumstances. ##### Custom Shapes Signers _may_ design custom shapes,[^fxmss_node_index] as the verifier is agnostic to the shape of the signer's FXMSS tree. This specification only defines two shapes: BXMSS and UXMSS. For security and privacy we highly recommend signers stick to the two prescribed shapes. ##### Caveats - Only nodes with index less than `2**64` are indexable in FXMSS.[^fxmss_node_index] - Some tree structures are invalid or impractical to generate, such as a balanced tree of height 255. - A tree of depth 0 has no stateful signatures, whatever its shape. Its root is the only position a WOTS+C leaf could occupy, and a signature made there carries no authentication path, so it falls below `FXMSS_SIGNATURE_SIZE_MIN` and every verifier rejects it. Signers MUST NOT issue a stateful signature under a depth-zero key; every state counter falls back to the stateless path. The signature counts given for each shape above therefore apply only from depth 1 upwards. - Implementations must take care when using SHRINCS secret keys imported from untrusted sources, especially if depending on shape and depth bytes for security-critical logic. #### Algorithms These algorithms are used only for the stateful FXMSS sub-scheme. #### `fxmss_node(...)` The FXMSS internal node computation function. Recursively computes the FXMSS node at the given `node_index` and `node_height` for a tree of the given shape and depth. - Inputs: - `sk_seed`: a 16-byte secret. - `node_index`: a 64-bit unsigned integer, the index (from the left) of the node in the FXMSS layer. - `node_height`: an 8-bit unsigned integer, the height (from the bottom) of the node in the FXMSS tree. - `pk_seed`: a 16-byte public seed. - `tree_balanced`: a boolean, true for a balanced (BXMSS) tree and false for an unbalanced (UXMSS) tree. - `tree_depth`: an 8-bit unsigned integer, the depth of the FXMSS tree. - Output: - a 16-byte FXMSS node hash. This function is only used in the stateful path, and only by the signer. ```py def fxmss_node( sk_seed: Bytes[16], node_index: UInt64, node_height: UInt8, pk_seed: Bytes[16], tree_balanced: bool, tree_depth: UInt8, ) -> Bytes[16]: node_depth = FXMSS_HEIGHT - node_height # Leaves are at the bottom layer or right children on the unbalanced spine. if node_depth == tree_depth or (not tree_balanced and node_index == 1): return wots_c_pubkey_gen( sk_seed, pk_seed, node_height, node_index, tree_balanced, tree_depth ) # Catch and throw if control would enter an infinite recursive loop. if tree_balanced: assert node_depth < tree_depth else: assert node_index == 0 # Recursively derive the left/right child nodes. lchild_index = 2 * node_index child_height = node_height - 1 lchild = fxmss_node( sk_seed, lchild_index, child_height, pk_seed, tree_balanced, tree_depth ) rchild = fxmss_node( sk_seed, lchild_index + 1, child_height, pk_seed, tree_balanced, tree_depth ) # Compute and return the parent node. return H(pk_seed, FxmssTree(node_height, node_index), lchild + rchild) ``` #### `fxmss_sign(...)` The FXMSS signing function. Produces a deterministic WOTS+C signature at the leaf given by `leaf_index`/`leaf_height` and appends the Merkle authentication path to form an FXMSS signature. - Inputs: - `message_digest`: a 32-byte message digest. - `sk_seed`: a 16-byte secret. - `leaf_index`: a 64-bit unsigned integer, the index (from the left) of the signing leaf in the FXMSS layer. - `leaf_height`: an 8-bit unsigned integer, the height (from the bottom) of the signing leaf in the FXMSS tree. - `pk_seed`: a 16-byte public seed. - `tree_balanced`: a boolean, true for a balanced (BXMSS) tree and false for an unbalanced (UXMSS) tree. - `tree_depth`: an 8-bit unsigned integer, the depth of the FXMSS tree. - Output: - a `2 + 16 * (WOTS_C_CHAIN_COUNT + FXMSS_HEIGHT - leaf_height)`-byte signature, or null. This function is only used in the stateful path, and only by the signer. ```py def fxmss_sign( message_digest: Bytes[32], sk_seed: Bytes[16], leaf_index: UInt64, leaf_height: UInt8, pk_seed: Bytes[16], tree_balanced: bool, tree_depth: UInt8, ) -> Optional[Bytes[FXMSS_SIGNATURE_SIZE_MIN:FXMSS_SIGNATURE_SIZE_MAX]]: leaf_depth = FXMSS_HEIGHT - leaf_height # Validate the leaf is positioned correctly for the specified tree structure. if tree_balanced: assert leaf_depth == tree_depth else: assert leaf_index == 1 or leaf_depth == tree_depth sig = wots_c_sign( message_digest, sk_seed, pk_seed, leaf_height, leaf_index, tree_balanced, tree_depth ) if sig is None: return None # practically impossible # Append the Merkle authentication path. for j in range(leaf_depth): sibling_index = (leaf_index // 2**j) ^ 1 sibling_height = leaf_height + j sig += fxmss_node( sk_seed, sibling_index, sibling_height, pk_seed, tree_balanced, tree_depth ) return sig ``` > [!NOTE] > [The `return None` control path can typically be ignored in real-world implementations](#on-signing-fallibility). #### `fxmss_pubkey_from_sig(...)` The FXMSS verification function. Recovers an FXMSS root from a `signature` on a 32-byte `message_digest`. The `leaf_height` and `leaf_index` arguments give the position of the WOTS+C leaf in the tree. - Inputs: - `leaf_index`: a 64-bit unsigned integer, the left-to-right position of the WOTS+C signing leaf. - `leaf_height`: an 8-bit unsigned integer, the height of the WOTS+C signing leaf. - `signature`: a signature of length proportional to the leaf depth `FXMSS_HEIGHT - leaf_height`. Specifically: `len(signature) == 2 + 16 * (WOTS_C_CHAIN_COUNT + FXMSS_HEIGHT - leaf_height)`. - `message_digest`: a 32-byte message digest. - `pk_seed`: a 16-byte public seed. - Output: - a 16-byte FXMSS root node hash, or null. This function is only used in the stateful path, and only by the verifier. ```py def fxmss_pubkey_from_sig( leaf_index: UInt64, leaf_height: UInt8, signature: Bytes[FXMSS_SIGNATURE_SIZE_MIN:FXMSS_SIGNATURE_SIZE_MAX], message_digest: Bytes[32], pk_seed: Bytes[16], ) -> Optional[Bytes[16]]: wots_sig = signature[0 : 2+WOTS_C_CHAINS_SIZE] xmss_auth = signature[2+WOTS_C_CHAINS_SIZE : len(signature)] leaf_depth = FXMSS_HEIGHT - leaf_height # Ensure the XMSS path size matches leaf_depth. assert len(xmss_auth) == leaf_depth * 16 # Ensure leaf_index describes a valid position in the FXMSS tree. assert leaf_index < 2 ** min(64, leaf_depth) node = wots_c_pubkey_from_sig( wots_sig, message_digest, pk_seed, leaf_height, leaf_index ) if node is None: return None for k in range(leaf_depth): parent = FxmssTree(leaf_height + k + 1, leaf_index // 2**(k+1)) sibling = xmss_auth[k*16 : (k+1)*16] if (leaf_index // 2**k) % 2 == 1: node = H(pk_seed, parent, sibling + node) else: node = H(pk_seed, parent, node + sibling) return node ``` ### FORS The stateless signing path of SHRINCS uses Forest Of Random Subsets (FORS), a hash-based _few-time_ signature scheme (FTS), to sign messages. Compared to one-time signature (OTS) schemes like Winternitz, FTS schemes are characterized by security which resists forgery even when a keypair is reused to sign multiple messages. The degradation in security can be quantified and calibrated using parameters, so that forgery-resistance does not fall below a target bound. FORS is one such FTS scheme. #### Informal Description Here follows an informal description of the FORS FTS scheme as it is defined in FIPS-205.[^slhdsa] A FORS keypair consists of a _forest_ of merkle trees of a fixed size, where each leaf is a hash of a preimage derived by a PRF. We parameterize the number of merkle trees as `SPHX_FORS_COUNT`, and the height of each tree as `SPHX_FORS_HEIGHT`. The FORS public key is a hash of the merkle roots of the entire forest. When signing, a message and randomizer `R` are mapped via a hash to a set of `SPHX_FORS_COUNT` integer indexes, of `SPHX_FORS_HEIGHT` bits each. Each index identifies a specific preimage from each merkle tree which the signer must reveal, along with a merkle authentication path. The verifier uses the preimages and merkle paths to recompute the roots of each tree, and finally recomputes the FORS public key to verify the signature. This diagram illustrates a toy FORS keypair, with merkle trees of height 2. Messages are mapped to a set of `k` 2-bit integers which select an index from each tree. Each signature reveals one of the preimages in each merkle tree in the forest. Over the course of many signatures, the signer may reuse preimages that have already been revealed in prior signatures, because some messages may map to intersecting index-sets. Unless he has an efficient way to find preimages, an adversary must hope the signer publishes signatures that admit a forgery by mixing and matching preimages from prior signatures. The adversary _cannot_ control which index-sets the victim signs, and so he cannot trick the signer into exposing specific preimages, even if the adversary can query the signer for arbitrary signatures. However, the adversary _may_ grind to find a message-randomizer pair which maps to an index-set that is a _subset_ of the index-sets signed previously, which would admit a forgery. The probability that this occurs with a randomly sampled index-set can be made arbitrarily low by using more and taller trees, or by reducing the limit on the number of signatures the signer is expected to produce. This is formalized as the security notion of _interleaved target-subset resilience._[^sphincs+] ### FORS Algorithms The following sections describe the algorithms needed for FORS key-generation, signing, and verification. #### `fors_sk_gen(...)` The FORS secret preimage generation function. Generates the secret 16-byte preimage of the FORS leaf at forest-wide index `node_index`, for the FORS keypair at `keypair_index` in the XMSS tree at `layer` and `tree_address`. - Inputs: - `sk_seed`: a 16-byte secret. - `pk_seed`: a 16-byte public seed. - `layer`: an 8-bit unsigned integer, the hypertree layer of the XMSS tree. - `tree_address`: a 64-bit unsigned integer, the index of the XMSS tree in its layer. - `keypair_index`: a 32-bit unsigned integer, the index of the FORS keypair. - `node_index`: a 32-bit unsigned integer, a forest-wide leaf index in `[0, SPHX_FORS_COUNT * 2**SPHX_FORS_HEIGHT)`. - Output: - a 16-byte preimage. This function is only used in the stateless path, and only by the signer. Note the `node_index` of a FORS leaf or node is _indexed across the entire forest,_ not just within a single tree. The index of leaf `l` in tree `t` is `t * 2**SPHX_FORS_HEIGHT + l`. ```py def fors_sk_gen( sk_seed: Bytes[16], pk_seed: Bytes[16], layer: UInt8, tree_address: UInt64, keypair_index: UInt32, node_index: UInt32, ) -> Bytes[16]: return PRF(pk_seed, sk_seed, ForsPrf(layer, tree_address, keypair_index, node_index)) ``` #### `fors_node(...)` The FORS internal node computation function. Recursively computes the FORS node at the forest-wide `node_index` and `node_height`, for the FORS keypair at `keypair_index` in the XMSS tree at `layer` and `tree_address`. - Inputs: - `sk_seed`: a 16-byte secret. - `node_index`: a 32-bit unsigned integer, a forest-wide node index in `[0, SPHX_FORS_COUNT * 2**(SPHX_FORS_HEIGHT - node_height))`. - `node_height`: a 32-bit unsigned integer, a node height in `[0, SPHX_FORS_HEIGHT]`. - `pk_seed`: a 16-byte public seed. - `layer`: an 8-bit unsigned integer, the hypertree layer of the XMSS tree. - `tree_address`: a 64-bit unsigned integer, the index of the XMSS tree in its layer. - `keypair_index`: a 32-bit unsigned integer, the index of the FORS keypair. - Output: - a 16-byte FORS node hash. This function is only used in the stateless path, and only by the signer. Note the `node_index` of a FORS leaf or node is _indexed across the entire forest,_ not just within a single tree. The index of node `l` in tree `t` at height `h` is `t * 2**(SPHX_FORS_HEIGHT - h) + l`. ```py def fors_node( sk_seed: Bytes[16], node_index: UInt32, node_height: UInt32, pk_seed: Bytes[16], layer: UInt8, tree_address: UInt64, keypair_index: UInt32, ) -> Bytes[16]: if node_height == 0: preimage = fors_sk_gen( sk_seed, pk_seed, layer, tree_address, keypair_index, node_index ) leaf = ForsTree(layer, tree_address, keypair_index, 0, node_index) return F(pk_seed, leaf, preimage) lchild_index = 2 * node_index child_height = node_height - 1 lchild = fors_node( sk_seed, lchild_index, child_height, pk_seed, layer, tree_address, keypair_index ) rchild = fors_node( sk_seed, lchild_index + 1, child_height, pk_seed, layer, tree_address, keypair_index ) parent = ForsTree(layer, tree_address, keypair_index, node_height, node_index) return H(pk_seed, parent, lchild + rchild) ``` #### `fors_sign(...)` The FORS signing function. Produces a FORS signature on a `message_digest`, for the FORS keypair at `keypair_index` in the XMSS tree at `layer` and `tree_address`. - Inputs: - `message_digest`: a `FORS_DIGEST_SIZE`-byte message digest. - `sk_seed`: a 16-byte secret. - `pk_seed`: a 16-byte public seed. - `layer`: an 8-bit unsigned integer, the hypertree layer of the XMSS tree. - `tree_address`: a 64-bit unsigned integer, the index of the XMSS tree in its layer. - `keypair_index`: a 32-bit unsigned integer, the index of the FORS keypair. - Output: - a `FORS_SIGNATURE_SIZE`-byte signature. This function is only used in the stateless path, and only by the signer. ```py def fors_sign( message_digest: Bytes[FORS_DIGEST_SIZE], sk_seed: Bytes[16], pk_seed: Bytes[16], layer: UInt8, tree_address: UInt64, keypair_index: UInt32, ) -> Bytes[FORS_SIGNATURE_SIZE]: sig = b"" index_set = base_2b(message_digest, SPHX_FORS_HEIGHT, SPHX_FORS_COUNT) for i in range(SPHX_FORS_COUNT): leaf_index = i * 2**SPHX_FORS_HEIGHT + index_set[i] sig += fors_sk_gen(sk_seed, pk_seed, layer, tree_address, keypair_index, leaf_index) for j in range(SPHX_FORS_HEIGHT): sibling_index = i * 2**(SPHX_FORS_HEIGHT - j) + ((index_set[i] // 2**j) ^ 1) sig += fors_node( sk_seed, sibling_index, j, pk_seed, layer, tree_address, keypair_index ) return sig ``` #### `fors_pubkey_from_sig(...)` The FORS verification function. Recovers a FORS public key from a `signature` on a `message_digest`, for the FORS keypair at `keypair_index` in the XMSS tree at `layer` and `tree_address`. - Inputs: - `signature`: a `FORS_SIGNATURE_SIZE`-byte signature. - `message_digest`: a `FORS_DIGEST_SIZE`-byte message digest. - `pk_seed`: a 16-byte public seed. - `layer`: an 8-bit unsigned integer, the hypertree layer of the XMSS tree. - `tree_address`: a 64-bit unsigned integer, the index of the XMSS tree in its layer. - `keypair_index`: a 32-bit unsigned integer, the index of the FORS keypair. - Output: - a 16-byte hash of the FORS public key. This function is only used in the stateless path, and by both the signer and the verifier. ```py def fors_pubkey_from_sig( signature: Bytes[FORS_SIGNATURE_SIZE], message_digest: Bytes[FORS_DIGEST_SIZE], pk_seed: Bytes[16], layer: UInt8, tree_address: UInt64, keypair_index: UInt32, ) -> Bytes[16]: index_set = base_2b(message_digest, SPHX_FORS_HEIGHT, SPHX_FORS_COUNT) offset = 0 roots = b"" for i in range(SPHX_FORS_COUNT): preimage = signature[offset : offset+16] offset += 16 tree_index = i * 2**SPHX_FORS_HEIGHT + index_set[i] leaf = ForsTree(layer, tree_address, keypair_index, 0, tree_index) node = F(pk_seed, leaf, preimage) for j in range(SPHX_FORS_HEIGHT): parent = ForsTree( layer, tree_address, keypair_index, j + 1, tree_index // 2**(j+1) ) sibling = signature[offset : offset+16] offset += 16 if (index_set[i] // 2**j) % 2 == 1: node = H(pk_seed, parent, sibling + node) else: node = H(pk_seed, parent, node + sibling) roots += node return T_k(pk_seed, ForsRoots(layer, tree_address, keypair_index), roots) ``` ### SLH-DSA The stateless signing path of SHRINCS uses the _StateLess Hash-based Digital Signature Algorithm_ (SLH-DSA) defined in FIPS-205[^slhdsa] with a non-standard parameter set. SLH-DSA is built out of the WOTS-TW, XMSS, and FORS subschemes already defined earlier in this document. In SLH-DSA, the signer uses a hypertree of XMSS trees to sign one of many possible FORS keypairs, which then signs the actual message. The addition of FORS makes SLH-DSA secure against a limited degree of leaf reuse, allowing us to discard state-management requirements. By hashing a _randomizer_ with the message, the signer randomly selects the exact position of the FORS keypair used to sign the message, in a way the verifier can reproduce. This ensures an adversary querying the signer for signatures cannot control which FORS keypair a signer will use, nor can they predictably control which FORS keypair to use for a forgery. The randomizer is sampled pseudorandomly by the signer, using the `PRF_msg_sl` hash function. The signer uses the selected FORS keypair to sign the message, and then certifies the FORS public key using a hypertree signature. The final SLH-DSA signature consists of: - A 16-byte _randomizer_ - A FORS signature on a message - A hypertree signature on the FORS public key The following sections describe the algorithms used for SLH-DSA. #### `slh_dsa_digest_message(...)` The SLH-DSA message hashing function. Derives the FORS message digest, bottom-layer XMSS tree index, and FORS keypair index from `message` under `H_msg_sl`. - Inputs: - `R`: a 16-byte randomizer. - `pk_seed`: a 16-byte public seed. - `sl_root`: the 16-byte root hash of the stateless root tree. - `message`: a variable-length message. - Outputs: - a `FORS_DIGEST_SIZE`-byte message digest, ready for use by FORS. - a 64-bit unsigned integer, a pseudorandomly selected index of a bottom-layer XMSS tree, in `[0, 2**SPHX_TREE_INDEX_BITS)`. - a 32-bit unsigned integer, a pseudorandomly selected index of a FORS key within an XMSS tree, in `[0, 2**SPHX_XMSS_HEIGHT)`. This function is only used in the stateless path, and by both the signer and the verifier. ```py def slh_dsa_digest_message( R: Bytes[16], pk_seed: Bytes[16], sl_root: Bytes[16], message: bytes ) -> tuple[Bytes[FORS_DIGEST_SIZE], UInt64, UInt32]: digest = H_msg_sl(R, pk_seed, sl_root, message) fors_digest = digest[:FORS_DIGEST_SIZE] offset = FORS_DIGEST_SIZE tree_index_digest = digest[offset : offset + ceildiv(SPHX_TREE_INDEX_BITS, 8)] offset += len(tree_index_digest) leaf_index_digest = digest[offset : offset + ceildiv(SPHX_XMSS_HEIGHT, 8)] tree_index = int.from_bytes(tree_index_digest) % (2**SPHX_TREE_INDEX_BITS) leaf_index = int.from_bytes(leaf_index_digest) % (2**SPHX_XMSS_HEIGHT) return (fors_digest, tree_index, leaf_index) ``` #### `slh_dsa_sign(...)` The SLH-DSA signing function. Signs `message` with `sk_seed`, prepending the context `ctx`; uses `pk_seed` as the public seed, derives the randomizer from `sk_prf`/`opt_rand`, and binds the signature to `sl_root`. Verifiers must use `slh_dsa_verify` with the same `ctx`. When provided, `opt_rand` supplies the additional randomness used to derive the randomizer. If omitted, the algorithm uses `pk_seed` in its place, resulting in the _deterministic variant_ of SLH-DSA. The resulting signature is composed of (1) a randomizer, (2) a FORS signature, and (3) a hypertree signature, all concatenated together. - Inputs: - `message`: a variable-length message. - `ctx`: a context of at most 255 bytes. - `sk_seed`: a 16-byte secret. - `sk_prf`: a 16-byte secret. - `pk_seed`: a 16-byte public seed. - `sl_root`: the 16-byte root hash of the stateless root tree. - `opt_rand`: optional 16-byte additional randomness. - Output: - a `SPHX_SIGNATURE_SIZE`-byte signature. This function is only used in the stateless path, and only by the signer. ```py def slh_dsa_sign( message: bytes, ctx: Bytes[:255], sk_seed: Bytes[16], sk_prf: Bytes[16], pk_seed: Bytes[16], sl_root: Bytes[16], opt_rand: Optional[Bytes[16]], ) -> Bytes[SPHX_SIGNATURE_SIZE]: contextualized_msg = (0).to_bytes(1) + len(ctx).to_bytes(1) + ctx + message if opt_rand is None: opt_rand = pk_seed # deterministic mode R = PRF_msg_sl(sk_prf, opt_rand, contextualized_msg) fors_digest, tree_index, leaf_index = slh_dsa_digest_message(R, pk_seed, sl_root, contextualized_msg) fors_signature = fors_sign(fors_digest, sk_seed, pk_seed, 0, tree_index, leaf_index) fors_pubkey = fors_pubkey_from_sig( fors_signature, fors_digest, pk_seed, 0, tree_index, leaf_index ) hypertree_signature = hypertree_sign(fors_pubkey, sk_seed, pk_seed, tree_index, leaf_index) return R + fors_signature + hypertree_signature ``` #### `slh_dsa_verify(...)` The SLH-DSA verification function. Recovers the root-tree root from a `signature` on `message` (with context `ctx`) and checks it against `sl_root`. Signatures must be produced via `slh_dsa_sign` with the same `ctx`. - Inputs: - `message`: a variable-length message. - `signature`: a candidate signature, of any length. Any length other than `SPHX_SIGNATURE_SIZE` is not a signature, and is rejected. - `ctx`: a context of at most 255 bytes. - `pk_seed`: a 16-byte public seed. - `sl_root`: the 16-byte root hash of the stateless root tree. - Output: - a boolean indicating if the signature is valid. This function is only used in the stateless path, and only by the verifier. ```py def slh_dsa_verify( message: bytes, signature: bytes, ctx: Bytes[:255], pk_seed: Bytes[16], sl_root: Bytes[16], ) -> bool: contextualized_msg = (0).to_bytes(1) + len(ctx).to_bytes(1) + ctx + message if len(signature) != SPHX_SIGNATURE_SIZE: return False R = signature[0:16] fors_signature = signature[16 : 16 + FORS_SIGNATURE_SIZE] hypertree_signature = signature[16 + FORS_SIGNATURE_SIZE : SPHX_SIGNATURE_SIZE] fors_digest, tree_index, leaf_index = slh_dsa_digest_message(R, pk_seed, sl_root, contextualized_msg) fors_pubkey = fors_pubkey_from_sig( fors_signature, fors_digest, pk_seed, 0, tree_index, leaf_index ) return hypertree_verify(fors_pubkey, hypertree_signature, pk_seed, tree_index, leaf_index, sl_root) ``` ### SHRINCS Above we have defined all the prerequisite building blocks of the SHRINCS scheme, and we are ready to define the high-level stateful and stateless key-generation, signing, and verification algorithms of SHRINCS. As described earlier in the [overview](#overview), SHRINCS combines FXMSS (stateful) and SLH-DSA (stateless) into a single unified signature scheme. The stateful path admits very compact and efficient signatures, while the stateless path allows signers to retain signing capability even if state has been lost or corrupted. #### SHRINCS Keys A SHRINCS key pair starts its life at key-generation, which the caller seeds with 48 random bytes. These 48 random bytes are partitioned into 3 x 16-byte chunks: `sk_seed`, `sk_prf`, and `pk_seed`. From `sk_seed` and `pk_seed`, the key-generation procedure derives the roots of two merkle trees: `sl_root` and `sf_root`. These represent the stateless and stateful keypairs respectively. No additional parameters are needed to derive `sl_root`, but to derive `sf_root` the caller needs to know which `sf_structure` to apply in FXMSS (see [the section on FXMSS](#fxmss) for more details). Once both roots are generated, the caller combines them with `pk_seed` to form the SHRINCS public key: ```py shrincs_pubkey = pk_seed + sl_root + sf_root ``` This encoding is chosen such that slicing off the last 16 bytes (`sf_root`) yields the public key produced by the SLH-DSA key-generation algorithm with the non-standard parameter set used by the stateless component. The SHRINCS secret key is encoded as: ```py shrincs_seckey = sk_seed + sk_prf + pk_seed + sl_root + sf_structure + sf_root ``` This encoding is chosen such that slicing off the last 18 bytes (`sf_structure + sf_root`) yields a valid secret key for the stateless component. #### Contexts The high-level `shrincs_sign` and `shrincs_verify` functions accept a context parameter `ctx`, which restricts signature validity to within a specific use-case, protocol, or other such zone of specificity. Signatures created by `shrincs_sign` when given a certain `ctx` are invalid if verified using `shrincs_verify` with any other context value. Typically `ctx` is set to some hard-coded constant value, to prevent misuse. For example, if a signer creates a signature with `ctx = b"bitcoin-tx"`, this signature cannot be replayed with `ctx = b"auth-challenge"`. This mirrors the interface of SLH-DSA[^slhdsa], and in fact the stateless signing component passes `ctx` transparently through to the `slh_dsa_sign` and `slh_dsa_verify` functions. #### On Managing State A SHRINCS secret key needs its accompanying state to use the high-efficiency stateful signing component. Every SHRINCS key has a fixed number of stateful signature slots which allow the signer to use compact WOTS+C signatures via the FXMSS (stateful) signing path. As previously discussed in [the section on WOTS](#wots-schemes), reusing a one-time signature keypair within FXMSS to sign distinct messages will break the security of the scheme and permit forgeries. To avoid using the same WOTS+C keypair more than once, signers using FXMSS must track a single integer, called the _state counter._ This counter tracks the number of signatures previously issued by the keypair. It increments once for every stateful FXMSS signature created, and _must never decrement._ When signing, the SHRINCS stateful signing algorithm chooses which WOTS+C leaf to use based on the state counter and the FXMSS tree structure. It is **absolutely critical for security that signers manage state counters extremely carefully.** Implementors must take care to avoid many dangerous state management practices which lead to state reuse: - State counters must not be backed up and restored by any mechanism. - State counters must not live in unprotected storage (e.g. shared memory, a user-accessible folder, etc). - State counters must not be exported and imported into other software. - Implementations must not allow concurrent signing. - Signers must increment the state counter in persistent storage _before_ returning an FXMSS signature to the caller. Signers are highly encouraged to store state counters only in durable, persistent, rollback-resistant storage which is protected against unauthorized modification. If correct state is not available for any reason, such as when restoring from a static backup, then a SHRINCS implementation MUST refuse to sign with the stateful path, and utilize only the stateless signing path. #### Maximum Message Length Every message SHRINCS hashes is bounded in length, because it is ultimately absorbed by SHA-256, which accepts at most `2**61 - 1` bytes. `shrincs_sign` and `shrincs_verify` cap `message` at `2**61 - 384` bytes. This cap is set by the longest prefix a message can sit behind. On the stateless path it reaches the innermost hash behind `98` bytes of fixed prefixes (the 64-byte HMAC block, the 16-byte `opt_rand`, the 2-byte SLH-DSA message prefix, and the 16-byte `sf_root`); on the stateful path, behind `107` (the 64-byte HMAC block, the 16-byte `pk_seed`, the 9-byte leaf position, the 2-byte binding prefix, and the 16-byte `sl_root`), which is the longer of the two. The caller's `ctx` is prepended on either path, adding up to a further 255 bytes, so the longest prefix any message sits behind is `362`. SHA-256's limit then gives an exact maximum of `2**61 - 363` bytes, which we round down to `2**61 - 384`, the largest multiple of SHA-256's 64-byte block size that stays within this limit. The intermediate functions accept *a variable-length message*. Its length still carries an upper bound, just an implicit one, set by the primitive bounds above rather than stated at each function: a SHRINCS `message` is already capped, and each intermediate prepends at most a known number of bytes to it, so every hash input stays within SHA-256's limit by construction. No realistic message will ever approach this cap. #### SHRINCS Algorithms The following sections describe algorithms used for SHRINCS. #### `shrincs_keygen(...)` The SHRINCS key generation function. Computes the secret and public keys from a 48-byte `seed` and the stateful tree `sf_structure`. - Inputs: - `seed`: a 48-byte random seed. Must be sampled from a CSRNG. - `sf_structure`: a 2-byte identifier describing the FXMSS tree structure: a shape byte, which must be one of the `FXMSS_SHAPE_*` values, followed by a depth byte. See the recommended depths for each shape in [Tree Shapes](#tree-shapes). - Outputs: - an 82-byte SHRINCS secret key. - a 48-byte SHRINCS public key. This function is used only during key generation. > [!WARNING] > The `sf_structure` argument, consisting of a shape byte followed by a depth byte `d`, must come > from a trusted source or else be validated. If an adversary can control it, they may cause > key-generation to fail, or hang consuming compute resources. Computing the root of a balanced tree > of depth `d` requires `2**d` WOTS+C public-key generations, so implementations should reject a > depth they cannot afford to compute. ```py def shrincs_keygen(seed: Bytes[48], sf_structure: Bytes[2]) -> tuple[Bytes[82], Bytes[48]]: assert sf_structure[0] == FXMSS_SHAPE_UNBALANCED or sf_structure[0] == FXMSS_SHAPE_BALANCED sk_seed = seed[0:16] sk_prf = seed[16:32] pk_seed = seed[32:48] sl_root = xmss_node(sk_seed, 0, SPHX_XMSS_HEIGHT, pk_seed, SPHX_LAYER_COUNT - 1, 0) tree_balanced = sf_structure[0] == FXMSS_SHAPE_BALANCED sf_root = fxmss_node( sk_seed, 0, FXMSS_HEIGHT, pk_seed, tree_balanced, sf_structure[1] ) shrincs_seckey = sk_seed + sk_prf + pk_seed + sl_root + sf_structure + sf_root shrincs_pubkey = pk_seed + sl_root + sf_root return (shrincs_seckey, shrincs_pubkey) ``` #### `shrincs_sf_leaf_select(...)` The SHRINCS stateful-path leaf-selection function. Computes the position `(index, height)` of the next WOTS+C leaf for the given `sf_structure` and `state_ctr`. - Inputs: - `sf_structure`: a 2-byte identifier describing the FXMSS tree structure. - `state_ctr`: a 64-bit unsigned integer, the number of stateful signatures the keypair has previously issued, or `None`. - Outputs: - a 64-bit unsigned integer, the left-to-right index of the next WOTS+C leaf in the FXMSS tree. - an 8-bit unsigned integer, the bottom-to-top height of the next WOTS+C leaf in the FXMSS tree. Returns `None` if `state_ctr` is `None`, or if it is at least the number of WOTS+C leaves in the FXMSS tree (as defined by its structure). A depth-zero tree has no usable leaf, so a depth-zero key signs only on the stateless path. This function is only used in the stateful path, and only by the signer. ```py def shrincs_sf_leaf_select( sf_structure: Bytes[2], state_ctr: Optional[UInt64] ) -> Optional[tuple[UInt64, UInt8]]: if state_ctr is None: return None tree_shape, tree_depth = sf_structure[0], sf_structure[1] # A depth-zero tree holds no usable WOTS+C leaf. if tree_depth == 0: return None if tree_shape == FXMSS_SHAPE_UNBALANCED: if state_ctr == tree_depth: return (0, FXMSS_HEIGHT - tree_depth) if state_ctr < tree_depth: return (1, FXMSS_HEIGHT - 1 - state_ctr) elif tree_shape == FXMSS_SHAPE_BALANCED: if state_ctr < 2**tree_depth: return (state_ctr, FXMSS_HEIGHT - tree_depth) # - unknown FXMSS tree shape # - no more signatures left return None ``` #### `shrincs_sign(...)` The SHRINCS signing function. Signs `message` and `ctx` with the serialized secret key `shrincs_seckey`: uses the stateful FXMSS path when `state_ctr` is valid for the key's tree structure, otherwise falls back to the stateless SLH-DSA path. Verifiers must use `shrincs_verify` with the same `ctx`. - Inputs: - `message`: a message of at most `2**61 - 384` bytes. - `ctx`: a context of at most 255 bytes. - `shrincs_seckey`: an 82-byte SHRINCS secret key. - `state_ctr`: a 64-bit unsigned integer, the number of stateful signatures the keypair has previously issued, or `None` to sign statelessly. - `opt_rand`: optional 16-byte additional randomness for SLH-DSA (unused in the stateful path; if omitted, the stateless path uses the deterministic variant of SLH-DSA). - Output: - a `SHRINCS_SL_SIGNATURE_SIZE`-byte stateless signature, or a stateful signature of at least `SHRINCS_SF_SIGNATURE_SIZE_MIN` bytes and at most `SHRINCS_SF_SIGNATURE_SIZE_MAX` bytes, or null. This function is used only by the signer. > [!WARNING] > The two-byte FXMSS tree structure encoded in `shrincs_seckey`, consisting of a shape byte followed > by a depth byte `d`, must come from a trusted source or else be validated. If an adversary can > control it, they may cause signing to fail, or hang consuming compute resources. Computing the > authentication path for a balanced tree of depth `d` from scratch requires `(2**d) - 1` WOTS+C > public-key generations, so implementations should reject a depth they cannot afford to compute. > [!CAUTION] > Using the same key to sign different `(message, ctx)` pairs with the same `state_ctr` is > a security vulnerability. SHRINCS implementations must wrap `shrincs_sign` with code > which increments and saves the state counter as `state_ctr + 1` on a persistent, > rollback-resistant storage medium before the signature is returned to the caller. ```py def shrincs_sign( message: Bytes[:2**61 - 384], ctx: Bytes[:255], shrincs_seckey: Bytes[82], state_ctr: Optional[UInt64], opt_rand: Optional[Bytes[16]], ) -> Optional[Union[Bytes[SHRINCS_SL_SIGNATURE_SIZE], Bytes[SHRINCS_SF_SIGNATURE_SIZE_MIN:SHRINCS_SF_SIGNATURE_SIZE_MAX]]]: sk_seed = shrincs_seckey[0:16] sk_prf = shrincs_seckey[16:32] pk_seed = shrincs_seckey[32:48] sl_root = shrincs_seckey[48:64] sf_structure = shrincs_seckey[64:66] sf_root = shrincs_seckey[66:82] leaf_position = shrincs_sf_leaf_select(sf_structure, state_ctr) # Stateless signing path. if leaf_position is None: # Bind the stateless signature to the stateful keypair. return bytes([FXMSS_HEIGHT]) + slh_dsa_sign(sf_root + message, ctx, sk_seed, sk_prf, pk_seed, sl_root, opt_rand) # Stateful signing path. leaf_index, leaf_height = leaf_position # Bind the stateful signature to the stateless keypair and context in the # same manner as the stateless component. bound_message = (0).to_bytes(1) + len(ctx).to_bytes(1) + ctx + sl_root + message R = PRF_msg_sf(sk_prf, pk_seed, leaf_height, leaf_index, bound_message) # Bind the stateful signature to the stateless keypair. message_digest = H_msg_sf( R, pk_seed, sf_root, leaf_height, leaf_index, bound_message ) tree_balanced = sf_structure[0] == FXMSS_SHAPE_BALANCED fxmss_signature = fxmss_sign( message_digest, sk_seed, leaf_index, leaf_height, pk_seed, tree_balanced, sf_structure[1] ) if fxmss_signature is None: return None # practically impossible # Encode the leaf index with a byte size proportional to its maximum = 2**min(64, leaf_depth) leaf_depth = FXMSS_HEIGHT - leaf_height leaf_index_bytes = leaf_index.to_bytes(ceildiv(min(leaf_depth, 64), 8)) return bytes([leaf_height]) + R + leaf_index_bytes + fxmss_signature ``` > [!NOTE] > [The `return None` control path can typically be ignored in real-world implementations](#on-signing-fallibility). #### `shrincs_verify(...)` The SHRINCS verification function. Returns true iff `signature` is a valid stateful or stateless SHRINCS signature on `message` under `shrincs_pubkey`. Signatures must be produced via `shrincs_sign` with the same `ctx`. The first byte of `signature` is called the _indicator byte_ and it tells the verifier which signing component to use: Byte `b == FXMSS_HEIGHT` indicates a stateless signature, any other byte `b < FXMSS_HEIGHT` indicates a stateful signature using a WOTS+C leaf at height `b` (i.e. depth `FXMSS_HEIGHT - b`). The verifier recomputes `sl_root` on the stateless path and `sf_root` on the stateful path, and compares the result against the public key. This implementation validates the length of the entire signature against the indicator byte, but one could also stream the signature byte-by-byte during verification, allowing for signature validation in memory-constrained environments. - Inputs: - `message`: a message of at most `2**61 - 384` bytes. - `signature`: a candidate signature, of any length. The stateless path accepts exactly `SHRINCS_SL_SIGNATURE_SIZE` bytes. Stateful signature lengths range from `SHRINCS_SF_SIGNATURE_SIZE_MIN` to `SHRINCS_SF_SIGNATURE_SIZE_MAX`, and the indicator byte determines the exact accepted length. Every other length is rejected. - `ctx`: a context of at most 255 bytes. - `shrincs_pubkey`: a 48-byte SHRINCS public key. - Output: - a boolean indicating if the signature is valid. This function is used only by the verifier. ```py def shrincs_verify( message: Bytes[:2**61 - 384], signature: bytes, ctx: Bytes[:255], shrincs_pubkey: Bytes[48] ) -> bool: if len(shrincs_pubkey) != 48: return False pk_seed = shrincs_pubkey[0:16] sl_root = shrincs_pubkey[16:32] sf_root = shrincs_pubkey[32:48] if len(signature) == 0: return False indicator = signature[0] # Stateless verification path. if indicator == FXMSS_HEIGHT: # Stateless signatures must be bound to the stateful keypair. return slh_dsa_verify(sf_root + message, signature[1:], ctx, pk_seed, sl_root) # Stateful verification path. The size bounds are the FXMSS bounds plus a variable-size header. elif 0 <= indicator < FXMSS_HEIGHT: # Signature must have correct length. if not SHRINCS_SF_SIGNATURE_SIZE_MIN <= len(signature) <= SHRINCS_SF_SIGNATURE_SIZE_MAX: return False R = signature[1:17] leaf_height = indicator leaf_depth = FXMSS_HEIGHT - leaf_height leaf_index_size = ceildiv(min(leaf_depth, 64), 8) leaf_index = int.from_bytes(signature[17 : 17+leaf_index_size]) # Reject a leaf_index that names no position in a tree of this depth. if leaf_index >= 2 ** min(64, leaf_depth): return False fxmss_signature = signature[17+leaf_index_size:] # The FXMSS part must be a WOTS+C signature plus leaf_depth merkle nodes. if len(fxmss_signature) != 2 + WOTS_C_CHAINS_SIZE + leaf_depth * 16: return False # Stateful signatures must be bound to the stateless keypair and context # in the same manner as the stateless component. bound_message = (0).to_bytes(1) + len(ctx).to_bytes(1) + ctx + sl_root + message message_digest = H_msg_sf( R, pk_seed, sf_root, leaf_height, leaf_index, bound_message ) root = fxmss_pubkey_from_sig(leaf_index, leaf_height, fxmss_signature, message_digest, pk_seed) if root is None: return False return root == sf_root # Negative indicator, not a valid SHRINCS signature. else: return False ``` ## On Signing Fallibility The declared return type of some signer functions like `fxmss_sign` is `Optional`, indicating the function may return `None` if the function fails. This originates from an edge case condition in `wots_c_grind_to_constant_sum` and bubbles up the stack in the stateful signing path, all the way up to `shrincs_sign`. While this edge case is technically possible to hit, it has such a low probability due to the parameters we use that it is essentially impossible in our universe. See [the docs for `wots_c_grind_to_constant_sum`](#wots_c_grind_to_constant_sum) to see why. Still, as this python code is the official specification of SHRINCS, we must account for even extremely low-probability paths in the control flow of the algorithms. Real-world implementations may treat `shrincs_sign`, `fxmss_sign`, `wots_c_sign`, and `wots_c_grind_to_constant_sum` as infallible functions, provided all input invariants are satisfied. ## Reference Implementation We provide a naive, highly inefficient, and non-constant-time pure Python 3 implementation of the SHRINCS algorithms in [`impl/shrincs.py`](./impl/shrincs.py), which is the normative source for the algorithms specified in this document. Tests are provided in [`impl/test.py`](./impl/test.py). Comprehensive test vectors covering every algorithm are still TODO; they are required to advance this proposal from Draft to Complete. > [!WARNING] > The implementation is for demonstration purposes only and not to be used in production environments. > It exists to generate test vectors and to serve as an executable specification to write independent implementations against. > It does not sample or protect secret key material, and it performs no state management at all: `shrincs_sign` takes the state counter as a caller-supplied argument and does nothing to prevent the same counter being used twice. > See [On Managing State](#on-managing-state) for the rules a real implementation must enforce. ## Optimized Implementation A fully optimized implementation of SHRINCS is still TODO. ## Acknowledgements We would like to thank: - Mike Casey, for his feedback during the process of drafting SHRINCS. - Andreas Hülsing, for his input on the SHRINCS security proof. - Boris Nagaev, for his input on the SHRINCS specification and for his work exploring higher-level SHRINCS constructions. ## Copyright This document and the SHRINCS reference code are licensed under either the CC0-1.0 or MIT license, at your option. ## Footnotes [^slhdsa]: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.205.pdf [^hbsb]: The underlying construction is sketched in the appendix of "Hash-based Signature Schemes for Bitcoin", https://eprint.iacr.org/2025/2203. [^adrs]: The 22-byte `ADRS` format aligns with the ADRSc format in SLH-DSA and FIPS-205[^slhdsa] for SHA2 parameter sets. [^xmss]: https://www.rfc-editor.org/rfc/rfc8391.html [^mgf1]: https://datatracker.ietf.org/doc/html/rfc8017#appendix-B.2.1 - It is possible to restrict ourselves to a single outer SHA256 invocation to match MGF1-SHA-256, because the SHRINCS parameter set does not require outputs larger than 32 bytes. [^hmac]: https://datatracker.ietf.org/doc/html/rfc2104 [^simd_x86]: https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html [^simd_arm]: https://arm-software.github.io/acle/neon_intrinsics/advsimd.html [^sha_ni]: https://en.wikipedia.org/wiki/SHA_instruction_set [^sha_ni_bench]: https://conduition.io/code/fast-slh-dsa/#Hardware-Acceleration [^simd_bench]: https://conduition.io/code/fast-slh-dsa/#Vectorized-Hashing [^sha256x8]: The [`sphincs/sphincsplus`](https://github.com/sphincs/sphincsplus/tree/7ec789ace6874d875f4bb84cb61b81155398167e) reference-code repository includes a [vectorized SHA256 implementation](https://github.com/sphincs/sphincsplus/blob/7ec789ace6874d875f4bb84cb61b81155398167e/sha2-avx2/sha256avx.c). [^vulkan]: For comparison, a 2025 benchmark of a [Vulkan implementation of SLH-DSA-SHA2-128s](https://conduition.io/code/fast-slh-dsa/#Vulkan-for-SLH-DSA) reports a signing time of 2.67 ms on a commodity RTX 3060 Ti GPU. [^pruning]: https://conduition.io/cryptography/hypertree-pruning/ [^sl_param_tool]: https://blockstreamresearch.github.io/SPHINCS-Parameters/site/stateless.html [^sl_param_search]: https://github.com/conduition/slh-experiments/blob/d0c56b173a2b1ecacaf9222aafa6868b1b7df504/param_search.py - To recover the SHRINCS parameters from this script, run it with the following arguments: `param_search.py --max-sigs '2**40' --secbits 128 --max-verify-hashes 2800 --max-kilohashes 2200 --no-cache --max-sig-size 5800` [^ledger-bench]: https://youtu.be/V59OkKfATng?si=Q6MsI7VBm5NMdJWZ&t=2297 [^trezor-bench]: https://github.com/trezor/trezor-firmware/pull/4901 and https://gist.github.com/onvej-sl/3851bdae7ae5aa1f2624ca769737ea2e [^merkle]: https://www.ralphmerkle.com/papers/Certified1979.pdf [^sphincs]: https://eprint.iacr.org/2014/795.pdf [^sphincs+]: https://sphincs.org/data/sphincs+-paper.pdf [^sphincs+c]: https://eprint.iacr.org/2022/778 [^porsfp]: https://eprint.iacr.org/2025/2069 [^wotsgrind]: https://gist.github.com/conduition/c19f00d9420eee009c9f33d9cd991bd6 [^bop]: https://eprint.iacr.org/2025/1844 [^bop-delving]: https://delvingbitcoin.org/t/bird-of-prey-2-non-malleable-schnorr-pq-signatures/2514 [^bip340-security]: The best known classical attacks against the elliptic-curve discrete logarithm problem in secp256k1 require work proportional to the square root of the group order. Since that order is approximately 2256, these attacks require approximately 2128 group operations. [^why128]: Although Bitcoin relies on full 32-byte SHA256 outputs elsewhere, this specification uses 16-byte hash outputs. By the birthday paradox, a generic search can find two inputs with the same 16-byte hash output after approximately 264 evaluations. This does not conflict with the category 1 target because SHRINCS does not rely on preventing such collisions to resist signature forgery. [^xmss-directional]: Can we still prove XMSS secure if we use an unstructured (directionless) tree, a la taproot? (better privacy and XMSS clients are more flexible) No. Unstructured XMSS trees would give an attacker an advantage in multi-target attacks. Say you have an XMSS tree with height two (i.e. four leaves). Let's say you reveal the two intermediate nodes in the first layer to an attacker, e.g. by signing a transaction. The hash function used to compute both of these nodes must be the same - otherwise it would not be a directionless tree - So the attacker can try preimage search on both hash function outputs at once. This doubles their chances of successfully finding a preimage. Scaled up, with more target hashes, the attacker increases their advantage even more. [^fxmss_node_index]: The key requirement for a valid FXMSS tree shape is that the indexes of all nodes must fit in a 64-bit unsigned integer. This means that while FXMSS trees can be up to 255 layers deep, only the leftmost 264 nodes in each layer are indexable. This provides plenty of space while maintaining a fixed max-length encoding for node indexes. [^last_two_sigs]: The last two UXMSS leaves are both at equal depth, and so their signatures both have the same length. [^bip340_sha256_bench]: https://github.com/mjthatch/bip340-vs-sha256