[Pool] Outstanding: Recover Previously Invalidated Transactions During a Reorg about grin HOT 14 CLOSED

I'll take care of it. I made my first pass a while ago, but when it was 80% ready tx pool was completely rewritten:)

from grin.

ready to tackle it if @antiochp hasn't done it already:)

from grin.

We are definitely seeing this right now in testnet1 and I think this is causing a lot of unintuitive issues with user wallets.

Everytime we see a fork (and we're seeing a bunch) and we finally get back to a stable state some set of users discover their coins are missing - and I suspect most of these issues are explained by txs being invalidated/disappearing due to a re-org.

from grin.

I think there are also several different cases here that we would want to take into consideration -

Chain A re-orgs to become Chain B, rewinding to some common block A_n == B_n and building the new chain from there.
Where block A_n+1 is on chain A but not on chain B.
And block B_n+1 is on chain B but not on chain A.

• Tx1 was valid on chain A but no longer valid on chain B (spends an output from block A_n+1)
• Tx2 was not valid on chain A but is now valid on chain B (spends an output from block B_n+1)
• Tx3_A and Tx3_B are valid on chain A and chain B respectively (a common output is spent from block A_n|B_n)

That third one is basically a combination of the previous two but we would need to be able to handle the case where we have multiple txs in there "reusing" outputs.
Where it is invalid to reuse an output on the same chain (double spend), but potentially valid to reuse an output on a different chain (also technically a double spend?, just a successful one?).

from grin.

Any pool of outstanding transactions that should be mined again after a reorg would tie into the stem pool. Should we fold this issue into the dandelion impl. #719 and close this bug?

from grin.

No, this isn't a network thing, it's purely internal to a node. A transaction gets evicted from the mempool when a block including it gets accepted. But if that blocks gets invalidated, the transaction needs to make it back in the mempool. There's no dandelion interaction.

from grin.

I understand the last comment - a tx is in an accepted block which may be invalidated later on, so we need to keep them (txs) for some period of time to return back to mempool if needed.
Are there any other scenarios which should be covered by this case?

from grin.

We could try to keep transactions around during restarts too but I wouldn't make that an important requirement.

from grin.

Also there might be some edge cases where we have to revert to previous transaction state with Dandelion aggregation see https://github.com/mimblewimble/grin/blob/master/doc/dandelion/simulation.md

from grin.

I've given this some thoughts but I'm not sure I'll have time to tackle it soon enough, given everything that's happening. So I'll just write this down for now.

The best entry point seems to be Pool.reconcile_block and more specifically remaining_transactions. The Vec of transaction entries getting evicted could be kept to the side with the block hash that evicted them. When the block is orphaned, corresponding entries could be re-added.

From a design standpoint, this would have to be fairly close to both the chain and the pool and I'm not sure it belongs to either. So the coordination may be better implemented in the servers crate as some sort of adapter. The actual cache could be mantained there or in the pool. It should also keep a bounded number of entries (perhaps just enough for the last 10 blocks).

from grin.

Agreed on not coupling this too closely to the pool itself. We still evict them from the pool, they just get maintained elsewhere for a bounded period of time (and some bounded storage) before we actually forget about them permanently.

I'd like to keep the pool impl as simple as possible - rentry into the pool adds some unavoidable complexity but it can be external to the pool proper.

from grin.

@hashmap still planning to work on this?

from grin.

@ignopeverell If someone has capacity to start now I don't mind, if not I'll take another attempt in couple weeks or earlier

from grin.

#1829 attempts to fix this in the simplest way possible.

• Every time we add a tx to the txpool (after we have successfully validated it) -
  • add it to a reorg_cache (ringbuffer of recent txs).
• Then every time we see a new block and call reconcile_block() on the txpool -
  • iterate over the reorg_cache and reapply each tx to the txpool

This leverages the existing txpool validation logic to ensure txs are valid (if they are valid they can be added to the pool and if they can be added to the pool then we probably should add them back in).

Performance wise we are simply reprocessing txs when attempting to (re)-add them to the pool, so this is no worse than our existing txpool processing logic.

from grin.