Race conditions across mempools

[hlb8122]

Background
Given the nature of bitcoin there is no guarantee that mempools will be in sync across disparate nodes. Stamp deals with high volume transactions and hence is subject to this lack of consistency.

Scenario A

1. Alice sends a stamp transaction to a Bobs relay server.
2. Bobs relay server broadcasts the transaction.
3. Alice uses the change outputs from that transaction in order to send to Carol.
4. Carol has not received the transaction sent to Bob yet. And therefore rejects the transaction.

Scenario B

1. Alice receives a stamp transaction from Bob.
2. She uses one these UTXOs to send a stamp to Carol.
3. Bobs stamp transaction has not been accepted by Carols relay server yet. And therefore rejects the transaction.

Current mitigation
At the time of writing, on transaction rejection, the client checks the existence of the UTXOs of said transaction, and if any are missing from the mempool of the electrum server the client deletes them.

Problem with current mitigation
In both scenarios there is no guarantee that the electrum server will have any of the UTXOs of problem transactions, especially when the time between messages is small. In which case they will be removed from clients UTXO and the user loses funds that they would otherwise be able to spend.

Additionally, the reverse problem could arise. Whereby UTXOs are actually spent, however the electrum server reports them as unspent - causing them to be reinstated back into the transaction pool.

These funds could be reinstated by reprocessing message history, however this is cumbersome and messages may be deleted prior to a reprocess.

Possible solutions
Instead of immediately removing UTXOs which don't exist in the electrum servers mempool, tag them as "unconfirmed" + current block height and leave them frozen. On new blocks check all unconfirmed frozen transactions and if they remain unconfirmed for ~2 blocks then discard them. This can be viewed of some kind of garbage collection mechanism.

The original design was to leave broken frozen UTXOs and clean them up on startup. This has three distinct downsides:

1. Funds can still be lost if the restart is sufficiently short after transaction rejection.
2. If the user doesn't restart broken UTXOs may aggregate.
3. Adds extra burden to startup times, amortizing this over the lifespan of the application is better.