[Mempool] Improve removal of invalid transactions after reorgs

sdaftuar commented at 1:32 am on October 30, 2015: member

@TheBlueMatt This is a rebased version of #6656 (which in turn built off #6595).

As previously reported in #6595, there’s currently a bug where we don’t remove transactions that become invalid after a reorg due to the transaction’s locktime. The solution proposed in #6595 doesn’t exhibit great behavior because it doesn’t make sense to evict locktime-invalid transactions in the middle of a reorg before the new tip is updated (since typically the block height is the same or greater at the end); @TheBlueMatt addressed this in #6656, which is rebased and included here.

I have also added a commit that vastly improves the efficiency of CTxMemPool::removeForReorg(), by tracking in each mempool entry whether or not the transaction spends a coinbase. Then in removeForReorg(), we only access coins for those transactions that spend a coinbase, instead of looking up all inputs for all transactions in the mempool (which is slow and blows up the UTXO cache).

I compared this code with and without this last commit on some historical data, and observed that this drastically improves runtime of removeForReorg() and reduces memory usage in pcoinsTip. Running this code on historical data on a few days in July, I observed 4 reorgs, and the runtime of removeForReorg() went from ranging between 167ms - 719ms down to between 5.5ms-16ms; meanwhile pcoinsTip memory usage (after the call to removeForReorg()) was reduced by between 144MB - 413MB.

When BIP68 support is merged we’ll probably want to update this approach, since IsFinalTx() will become a more expensive function that needs to look at inputs.

dcousens commented at 4:10 am on October 30, 2015: contributor

concept ACK

laanwj added the label Mempool on Oct 31, 2015

TheBlueMatt commented at 10:18 pm on November 5, 2015: member

Didnt look too closely, but the last commit seems reasonable.

petertodd commented at 8:32 pm on November 10, 2015: contributor

Needs rebase

sdaftuar force-pushed on Nov 10, 2015

sdaftuar commented at 9:42 pm on November 10, 2015: member

Rebased

sipa commented at 7:49 am on November 11, 2015: member

utACK.

For BIP68 transactions maybe it makes sense to replace the spendscoinbase flag with a minimum height/time at which the transaction becomes valid (which also generalized the wanted behaviour for coinbase-spending transactions).

morcos commented at 8:54 pm on November 12, 2015: member

@sipa, @sdaftuar and I discussed adding the BIP68 time and locktime at length. We were waiting for the code to finalize, and had gotten hung up on the locktime potentially being quite recent and therefore causing a great many transactions to have all 3 heights recalculated on a reorg. But now I’m realizing it makes a lot of sense to only include BIP68 and coinbase height, and then separately scan for locktime since its so easy!

In any case, I think this should be merged and that should be a future improvement. I will review shortly.

sdaftuar commented at 9:00 pm on November 12, 2015: member

Nits fixed.

morcos commented at 10:28 pm on November 12, 2015: member

utACK

gmaxwell added this to the milestone 0.12.0 on Nov 14, 2015

sdaftuar force-pushed on Nov 17, 2015

sdaftuar commented at 8:34 pm on November 17, 2015: member

Rebased

dcousens commented at 0:34 am on November 18, 2015: contributor

Easiest to read with ?w=0 (omits white space changes).

dcousens commented at 0:35 am on November 18, 2015: contributor

once-over utACK

gmaxwell commented at 11:27 pm on November 22, 2015: contributor

I think this needs an update for MTP, as it appears to be using adjusted time. @TheBlueMatt

sdaftuar commented at 4:02 pm on November 23, 2015: member

@gmaxwell Oops – thanks for catching that. I thought it might make sense to pull removeForReorg out of the mempool and into main, so that we can keep policy code more organized and hopefully duplicate less logic.

If this approach seems okay, I’ll try to go back and clean up the commit history here.

ping @TheBlueMatt

TheBlueMatt commented at 8:06 pm on November 23, 2015: member

I’m not a huge fan. This isnt actually policy code, its code who’s behavior is derived from consensus rules, so I dont think it belongs in main. I’d much rather pass the MTP spendable-height to CTxMemPool::…() than to do this all in main.

sdaftuar force-pushed on Nov 23, 2015

sdaftuar commented at 9:07 pm on November 23, 2015: member

Ok I tried the smaller change of just passing through the MTP into removeForReorg, is this what you had in mind?

sdaftuar commented at 1:10 pm on November 24, 2015: member

18:22 < BlueMatt> anyway, I’d prefer to not duplicate the code….can we pull that out into a function? @TheBlueMatt: Yeah I also didn’t want to duplicate that code, but it seemed like the right way to do that would be to reuse the CheckFinalTx function, which does very little, here’s what it looks like:

 0bool CheckFinalTx(const CTransaction &tx, int flags)
 1{
 2    AssertLockHeld(cs_main);
 3
 4    // By convention a negative value for flags indicates that the
 5    // current network-enforced consensus rules should be used. In
 6    // a future soft-fork scenario that would mean checking which
 7    // rules would be enforced for the next block and setting the
 8    // appropriate flags. At the present time no soft-forks are
 9    // scheduled, so no flags are set.
10    flags = std::max(flags, 0);
11
12    // CheckFinalTx() uses chainActive.Height()+1 to evaluate
13    // nLockTime because when IsFinalTx() is called within
14    // CBlock::AcceptBlock(), the height of the block *being*
15    // evaluated is what is used. Thus if we want to know if a
16    // transaction can be part of the *next* block, we need to call
17    // IsFinalTx() with one more than chainActive.Height().
18    const int nBlockHeight = chainActive.Height() + 1;
19
20    // Timestamps on the other hand don't get any special treatment,
21    // because we can't know what timestamp the next block will have,
22    // and there aren't timestamp applications where it matters.
23    // However this changes once median past time-locks are enforced:
24    const int64_t nBlockTime = (flags & LOCKTIME_MEDIAN_TIME_PAST)
25                             ? chainActive.Tip()->GetMedianTimePast()
26                             : GetAdjustedTime();
27
28    return IsFinalTx(tx, nBlockHeight, nBlockTime);
29}

We’re basically duplicating all the code here (except maybe that std::max(flags, 0); I don’t really understand what that is) already, so pulling out the one line to avoid duplicating that doesn’t seem worth it… I’d rather find a way to reuse the whole function (which is what I did in my first attempt).

My only other idea here would be to change CTxMemPool::removeForReorg to take a “flags” argument only, and then invoke CheckFinalTx instead of IsFinalTx.

NicolasDorier commented at 6:24 am on November 26, 2015: contributor

in #6312 IsFinalTx (renamed LockTime) is responsible for calculating the nBlockTime from flags. LockTime function can be called by removeForReorg with the passed flag, this would prevent code duplication.

6312 is ready to merge once it get more ACK, this could be rebased on it, would make things simpler.

sipa commented at 12:57 pm on November 28, 2015: member

Needs rebase.

Add failing test checking timelocked-txn removal during reorg 0c9959a308

Fix removal of time-locked transactions during reorg 9b060e5cfb

Fix comment in removeForReorg b0a064c4b8

Make indentation in ActivateBestChainStep readable 474b84a741

removeForReorg calls once-per-disconnect-> once-per-reorg bb8ea1f630

Track coinbase spends in CTxMemPoolEntry

This allows us to optimize CTxMemPool::removeForReorg.

7e49f5f8b4

Don't call removeForReorg if DisconnectTip fails b7fa4aa387

Fix removeForReorg to use MedianTimePast 2d8860e820

sdaftuar force-pushed on Nov 30, 2015

sdaftuar commented at 7:51 pm on November 30, 2015: member

Rebased, and I changed the last commit to call CheckFinalTx. I don’t love this, but it avoids the code duplication of having all the callers separately calculate what time to pass in. @NicolasDorier We’ll want to reimplement this function after #6312, since LockTime will be a more expensive function to call. I’m happy to tackle that when the time comes, but I don’t want to rebase this on #6312 since this is tagged for 0.12 and fixes a bug. For now, I think this formulation should be easy to merge into #6312, since I’m now just passing the flags variable through to CheckFinalTx.

laanwj merged this on Dec 1, 2015

laanwj closed this on Dec 1, 2015

laanwj referenced this in commit 2ef5ffa59a on Dec 1, 2015

str4d referenced this in commit a27464a1e3 on Feb 3, 2018

str4d referenced this in commit 945a3feb97 on Feb 8, 2018

zkbot referenced this in commit 84c19b8a87 on Feb 8, 2018

str4d referenced this in commit e62cc5a174 on Feb 8, 2018

zkbot referenced this in commit e1f3a15fdc on Feb 8, 2018

str4d referenced this in commit bc8a1685b9 on Feb 8, 2018

str4d referenced this in commit a458a698ff on Feb 14, 2018

str4d referenced this in commit 93cf692703 on Feb 16, 2018

zkbot referenced this in commit eb3128ab0a on Feb 19, 2018

zkbot referenced this in commit 6d6b780969 on Feb 20, 2018

zkbot referenced this in commit 49274558c6 on Feb 20, 2018

random-zebra referenced this in commit 6bc917e859 on Jul 6, 2020

MarcoFalke locked this on Sep 8, 2021

[Mempool] Improve removal of invalid transactions after reorgs #6915