# Why does WOTS+ need a checksum during signing operation?

I was reviewing WOTS+ scheme for consideration in our private blockchain, and noticed that it had a small overhead of calculating a checksum as seen in the following pseudocode excerpt from the SPHINCS+ submission to NIST

wots_sign(M, SK.seed, PK.seed, ADRS) {
csum = 0;

// convert message to base w
msg = base_w(M, w, len_1);

// **compute checksum** <<<<============
for ( i = 0; i < len_1; i++ ) {
csum = csum + w - 1 - msg[i];
}

// convert csum to base w
csum = csum << ( 8 - ( ( len_2 * lg(w) ) % 8 ));
len_2_bytes = ceil( ( len_2 * lg(w) ) / 8 );
msg = msg || base_w(toByte(csum, len_2_bytes), w, len_2);
for ( i = 0; i < len; i++ ) {
sig[i] = chain(sk, 0, msg[i], PK.seed, ADRS);
}
return sig;
}
//Algorithm 5: wots_sign – Generating a WOTS+ signature on a message M.


Why is it there? Is it necessary for the security of the scheme?

Update

According to "On the Security of the Winternitz One-Time Signature Scheme", the checksum deters "second-key" and "key-collision" attack should there be a functional forgery oracle. How relevant an attack is it to WOTS+ and to other regular signature schemes?

To understand why we need a "checksum", we can take a look all the way back to 1979 paper "A Certified Digital Signature" by Raphle Merkle.

From page 14 on the treatment of the Lamport-Diffie OTS:

The method as described thus far suffers from the defect that B can alter m by changing bits that are 1's into 0's. ... However, 0's cannot be changed to 1's.

This is because, if one changes 1 to 0, she/he can simply calculate the image of the hash for that bit and get another valid signature.

The countermeasure as proposed was, quote:

by signing a new message m', which is exactly twice as long as m and is computed by concatenating m with the bitwise complement of m.

The similar method was used in WOTS, except instead of concatenating m with its bitwise complement, it's concatenated with the "additive" complement of the sum of its indicies.

So this is more like a padding scheme (similar in purpose to that used in RSA), but since it's a number, we'll just call it a checksum.

As to the update in OP, the checksum also plays an important role in the provable security reduction of WOTS.

Recall the idea WOTS scheme in essence, without checksums yet: for a message $$m = (m_1, m_2, ..., m_n),$$ where $$m_i\in \{{0,...,W\}}$$, signature value is $$\sigma = (\sigma_1, ..., \sigma_n)$$, so that $$\sigma_i$$ is the $$(m_i + 1)$$-preimage of the public key value $$p_i$$. Verification check is: $$p_i = Hash^{m_i + 1}(\sigma_i).$$

This scheme (without checksum) could be simply broken: after the signer issued a valid signature for some message $$m = (m_1, m_2, ..., m_n)$$, anyone can trivially create a signature for any message $$m' = (m'_1, ..., m'_n)$$ if $$m'_i \le m_i$$ for all $$i$$. Indeed, if you have $$(m_i+1)$$-preimage of some value (in this case, $$p_i$$), you have also a $$(m'_i+1)$$-preimage.

How to fix the scheme? The idea is the following: in addition to "sign" (more precisely - find corresponding preimages of public key) message $$m$$, you must also "sign" some additional string $$c=(c_1, ..., c_l)$$, which is built from $$m$$ in a special way $$c = c(m)$$. This transformation ($$c(m)$$) guarantees the following property: if $$m'_i < m_i$$ for all $$i$$, then, vice-versa, $$c'_j > c_j$$ at least for some $$j$$ (for corresponding $$c=c(m)$$ and $$c'=c(m')$$ ). This property will block the forgery attack described above. Indeed, if the attacker decreases message value in some position, i.e. $$m'_i < m_i$$, she automatically increases at least some position in the checksum - $$c'_j > c_j$$.

How to find such a magic transformation $$c$$? It turns out, that it could be very simple. E.g., you can use just a "complement" - a string of the same length, so that $$c_i = W - m_i$$. Easy to see, that it guarantees the desired property ("if all $$m'_i \le m_i$$, then $$c'_j > c_j$$ for at least some $$j$$"). Although, it satisfies even a stronger property: "if $$m'_i \le m_i$$ for some $$i$$, then $$c'_i > c_i$$". But it doesn't help us in any way. Also, this transformation is a bit heavy (the length of checksum is the same as length of a message, so that it doubles the signature size and public key size).

Finally, the question is could we construct another, more space-effective transformation with the desired property? Yes, it could be shown that the most space-effective $$c$$ is a checksum described in WOTS scheme (as well as its successors - WOTS+, SPHINCS and so on). It has a length of roughly $$log_W n$$ (compare to $$n$$ - length of naive "complement").