Note: SLH-DSA-256S's parameters are used as an example; actual numbers below vary.
SLH-DSA (aka SPHINCS+) is a framework that allows a large amount (typically around 264) of few-time public keys to be compressed into a single 32-byte "root" public key. In order to achieve this compression, every SLH-DSA signature includes a proof that the public key used for signing is a subkey of the "root" public key. This allows us to use few-time post-quantum signature schemes, like HORS or FORS, in a stateless signature scheme.
Compressing 264 items requires a balanced merkle tree of depth 64, which is impractical. So, SLH-DSA splits our 64-depth merkle tree into 8 layers of 8-deep merkle trees; in order to link the lower merkle tree as an entry in the upper merkle tree, every leaf of a merkle tree uses a one-time signature scheme to deterministically sign the root of the lower layer. Since each one-time signature scheme can only ever sign one item (the root of the tree below it), the proving scheme does not leak any information useful for forgeries.
How can we make few-time signature schemes practical in a stateless signature scheme? We can't use a few-time signature keypair too many times, or forging a signature becomes trivially easy. In order to make a few-time signature scheme practical, we would need to associate an absurd amount of public keys (trillions of trillions) to ensure that one key is not used more times than it's rated for. We can't carry state, so each few-time signature keypair needs to be picked randomly from a list. However, storing and transmitting such a large, random-access public key would be impossible, at best.
SLH-DSA answers this question with an elegant three-part solution:
Choose a seed capable of generating ~264 few-time or one-time signature keys on demand;
Deterministically create a small (3-8 deep) merkle tree committing each set of keypairs;
Use a one-time signature scheme to deterministically link each tree to the root of the tree below it; the determinism ensures we only use each one-time signature to sign exactly one value.
Because of the way SLH-DSA generates "subtrees", we only need to generate the root tree of the hypertree to generate a public key, and we only need to generate the subtree that the authentication path follows while signing. This means that, despite a fully expanded hypertree taking up hundreds of exabytes of space, we only need to generate a few megabytes to create a keypair or sign a value, while reaping all of the benefits of an exabytes-large public key.
An SLH-DSA signature is a set of parameters inputted into a function that computes a public key; the signature is valid if the computed public key matches what we expected.
We start by computing the few-time signature public key from the provided parameters; if all the parameters are correct (eg, the signature is valid), then the computed public key will be a member of the hypertree at a known position. This position is computed by a hash of the message and a nonce, so it's implicitly known where this key should be in the hypertree if we have the right signature-message pair.
f401f8d326267f65cef883bb7fe6422f
632676dcbb4229714840c40d1dff4c3d
A nonce is used to defend against signing-oracle attacks.
44635a44cde8909b964f6af509b2bb28
There's 33 components in the FORS signature. If the FORS signature is valid, it will be equal to a FORS public key at a known location within the lowest layer of the merkle hypertree.
The FORS signature is the signature that actually signs your message.
f401f8d326267f65cef883bb7fe6422f
There's 22 individual Winternitz proofs, one for each "subtree" of the hypertree. These proofs collectively prove that the leaves used in the authentication path are part of the public key.
Each Winternitz proof signs either your FORS public key or another Winternitz proof, until the verifier reaches the top of the hypertree.
The authentication path determines the path we traverse down the hypertree. For your selected parameter set, there are 266 possible authentication paths, each leading to a single few-time public key.
Every single few-time public key is part of your public key (and every one could be published, if the lot weren't so massive), so the authentication path merely serves as a simple mechanism for proving that a subkey is within your merkle tree root without publishing the entire exabytes-large collection of public keys.
Note: Some parameters have authentication paths are too large to render in the browser; in which case, you will see a simple list rather than a fancy graph.
Public Key
This is public key 5217059169026229512 out of 73786976294838206464.
The "signature" part of each signature uses a few-time public key scheme, called the Forest of Random Subsets. Using this scheme, we can prove knowledge of a public key's secret key by providing a set of values that hash to that public key. Using a forest of random subsets, we publish specific values (while keeping others hidden) to prove knowledge repeatedly, while sharing information in the form of which values we choose to publish.
In this instance, we sign 198 bits of data using 33 public keys, each of which is responsible for signing a 6-bit slice of the message. If the signature is valid, then the hash of resulting public keys will be a known value, which can then be proven to be within the hypertree using the subsequent Winternitz proofs.
Secret Key
(Index = 27)
Merkle Up w/ Left Hash
(Because Index & 1)
Merkle Up w/ Left Hash
(Because Index & 2)
Merkle Up w/ Right Hash
(Because ~Index & 4)
Merkle Up w/ Left Hash
(Because Index & 8)
Merkle Up w/ Left Hash
(Because Index & 16)
Merkle Up w/ Right Hash
(Because ~Index & 32)
Public Key #0
The few-time public key is the combined hash of all public keys. If any of the 6-bit signatures are incorrect, then the computed public key will also be incorrect. Using each of the public keys computed above, we can calculate the public key used in the few-time signature scheme:
44635a44cde8909b964f6af509b2bb28
Each "step" in the authentication path above requires it's own Winternitz proof to prove that the tree below is indeed a member of the tree above. In order to do this, each leaf of every tree is a one-time signature public key, and every "step up" through the tree includes a signature of the root of the lower tree.
As we walk up the trees to verify the signature, we confirm that the root of the previous tree has a valid signature in the proof. We then can verify that the public key we used to verify the signature was in the upper tree by continuing up the merkle tree. We repeat this until we reach the highest possible node, which should be our public key.
If a signature is invalid, or a one-time public key is invalid, or anything at all is invalid, then the resulting merkle root won't be equal to our public key. A verifier can't determine if any of the intermediary steps are incorrect, so it's a constant-time all-or-nothing proof.
Signed Message
(FORS Public Key)
Public Key #2
(Index = 2)
Merkle Up w/ Right Hash
(Because ~Index & 1)
Merkle Up w/ Left Hash
(Because Index & 2)
Merkle Up w/ Right Hash
(Because ~Index & 4)
Merkle Root #0
Similarly to a FORS signature, a Winternitz signature is a set of parameters which, when the parameters are a valid signature, compute the public key of the signer. This lets us use the computed public key as the leaf of the next merkle tree; if the computed public key (and thus the signature) is incorrect, then we will not compute the same hypertree merkle root.