# Winternitz Parameter in WOTS+ and XMSS

What is the parameter for? I read that in XMSS it is a member of the set {4, 16}, but what does it exactly mean? I also read that the bigger the $$w$$ parameter, the shorter the signatures but the keygen, sign and vrfy become slower. How do I pick an optimal $$w$$ parameter? Is it the height of the Merkle tree?

The size of a Winternitz signature is roughly $$mn/w$$ bits and signing roughly requires $$2^wm/w$$ hash operations, where $$m$$ is the bit length of the hash value to be signed, $$n$$ is the output length of the hash function used in the scheme, and $$w$$ is the Winternitz parameter determining the tradeoff between signature size and signature generation time.

The reference paper here goes into detail on how the parameter $$w$$ is used in various algorithms. Per the paper:

The parameter $$w$$ can be chosen from the set {4, 16}. A larger value of $$w$$ results in shorter signatures but slower overall signing operations; it has little effect on security. Choices of $$w$$ are limited to the values 4 and 16 since these values yield optimal trade-offs and easy implementation.

An example of the parameter being used is in Algorithm 5: WOTS_sign - Generating a signature from a private key and a message.

Section 2.2 of this paper goes into further detail about time-memory tradeoff.

Additionally section 4 goes into further depth with performance comparisons of different parameters.

The height of the merkle tree is an independent parameter. The Winternitz parameter — $$w$$ — comes up because to sign or verify a WOTS+ signature the first step is to encode your message as a list of integers from $$0$$ to $$w - 1$$ (inclusive). For example the string "hello" is encoded in ascii as 01101000 01100101 01101100 01101100 01101111. If $$w$$ were $$16$$ then each integer would correspond to $$4$$ bits of the message. Like this:

0110 1000 0110 0101 0110 1100 0110 1100 0110 1111
6    8    6    5    6   12    6   12    6   15


If $$w$$ were $$4$$ then each integer would correspond to $$2$$ bits and the sequence would be like that:

01 10 10 00 01 10 01 01 01 10 11 00 01 10 11 00 01 10 11 11
1  2  2  0  1  2  1  1  1  2  3  0  1  2  3  0  1  2  3  3


So $$4$$ and $$16$$ are just values that make conversion simple and efficient. A big $$w$$ makes for a small sequence of big numbers, a small $$w$$ makes a big sequence of small numbers. Bigger sequences tend to result in bigger signatures. Bigger numbers increase the amount of hashes you need to calculate.

If your hashes have $$n$$ bytes and you're signing a message of $$m$$ bytes then the length of your signature will be

$$n\cdot\left(\left\lceil \frac{8\cdot m}{\log_2(w)} \right\rceil + \left\lfloor \frac{\log_2\left(\left\lceil \frac{8\cdot m}{\log_2(w)} \right\rceil \cdot (w - 1)\right)}{\log_2(w)} \right\rfloor + 1 \right)$$

bytes. So you could try plugging some values of $$w$$ to see which ones give you a reasonable size.