[Pool] Outstanding: Recover Previously Invalidated Transactions During a Reorg

[MoaningMyrtle]

This is more of a longer-term project, as it's not necessary for basic operation of the system. However, in order for transaction pools to operate reliably, I believe there will need to be a system to return transactions invalidated on a fork that was previously head to the pool, so that any transactions that conflict between the fork and new head are not lost forever. This requires a bit more machinery than in most existing blockchains because recovering the transaction from the block itself is not possible.

Conceptually, I was thinking that the pool should retain recently invalidated transactions in their entirety for a period of time (some acceptable reorg depth), which can be much less than the cut-through reorg depth because this property is not necessary for correctness, only usability. Even in the worst case, some miners (those who built the blocks that constitute the new head) should have a consistent view of the transaction pool without any loss. Any thoughts?

[antiochp]

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.

[antiochp]

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?).

[sesam]

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?

[ignopeverell]

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.

[hashmap]

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?

[ignopeverell]

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

[quentinlesceller]

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

[ignopeverell]

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).

[hashmap]

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:)

[antiochp]

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.

[ignopeverell]

@hashmap still planning to work on this?

[hashmap]

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

[hashmap]

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

[antiochp]

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.