Limiting the overlap of IOTA signatures when double spending

IOTA uses Winternitz one-time signatures to sign off on spending iotas from an address. The nature of these signatures is such that during the signing process 50% of the private key to that address is exposed. This is normally no problem, because the addresses are supposed to be used only once.

But there’s the rub. It has been shown time and again that it is possible to get into a situation where you have to spend again from the same address. For example when withdrawing from an exchange to the same address multiple times, while you spent some of it in between withdrawals. Anyway, the exact way is not important. Suffice to say that people still get into this situation regularly.

The problem that now arises is that the moment you spend the second time from this address your chance of being subjected to an intercept attack is pretty large. The moment you sign again and send that transaction out you expose a second random 50% of your private key, allowing a well-prepared hacker to start brute forcing his own transaction bundle that will spend the funds to his own address instead. Then it becomes a race which transaction bundle gets confirmed first. And you can be sure that the hacker has a ot of intimate knowledge about the process to improve his change of being the first one selected for confirmation!

While discussing this with a few Discord moderators I thought of a way we can limit the exposure of the signature. We need to take two things into account.

1. First there is the way the signing happens, which causes certain exposed fragments of the private key to be easier to use for this hack attempt.
2. And second there is the randomness of the process, which makes for a random overlap of the two 50% exposures.

Statistics will show that the chances of overlap are graded on a Bell curve, with 0% overlap and 100% overlap being extremely unlikely, and 75% overlap being the most likely. But statistics are working with large samples. And here we have a sample size of only two. So in reality you will end up with an overlap that can be on the entire scale of 0–100%. Which, if you are unlucky, could be towards the 100% end, which makes hacking an interception bundle together exponentially easier to do.

My proposal

While thinking about this it became clear that we can use a much better signing process for the wallets. IoT devices are extremely unlikely to get into a double-spend situation. So we only have to modify the signing process for the wallets. And as luck would have it, wallets run on much more capable hardware. So we can throw more computing resources at the solution for both things we needed to take into account:

1. The signing itself. Currently the amount of hashing necessary to verify a signature is variable for the various signature fragments. The actual amounts are pretty random, since they are dictated by the input data, which contains hash values (the address and bundle hash, for example). And hash values by nature are very random. But if the amount of hashes necessary for the signature depends on this, why not make sure that there is at least a minimum amount of hashing necessary after the signature?
2. The overlap of the signatures. Again, due to the randomness of the input data, the overlap is random as well. But it does not have to be. We can make it so that the input data is such that a second spend results in a signature that overlaps the signature of the previous spend as much as possible.

Funny enough, both these solutions can be achieved in the same way. We take a page out of the Proof of Work book and use a field in the data as a nonce field. We can then generate a signature multiple times, each time incrementing the nonce, and then we can select the best nonce/signature combination. For the two cases, here is what we could do:

1. Generate 4 or 5 different nonce/signature combinations, then select the one that results in the most hashes necessary to check the signature. We could even require at least a minimum total amount of hashes and keep on incrementing the nonce until we find one.
2. Since double spends are rare events and need extreme measures, we want to take a lot more time than normal, and check anywhere from hundreds to even milllions of nonce/signature combinations to find a signature that, in combination with the previous signature, exposes the least amount of combined fragments. That makes hacking an interception bundle together exponentially more difficult.

Note that trying a number of signatures does not really amount to much time when compared to the amount of times taken to do the PoW once the bundle is signed. So instead of checking 4 or 5 combinations when signing the first spend we could even do more. I guess we need to find the right parameters here that give us a balance between speed and security.

Anyway, it would not be hard to implement these anti-hacking measures in any wallet. So I am looking forward to seeing my ideas implemented soon!