Fix coinbase-spend mempool inconsistency after reorgs

TheBlueMatt commented at 10:43 pm on November 12, 2014: member

We were previously not removing transactions from mempool during reorg if they spent a coinbase. While this broke the mempool-invariant of safe-to-put-in-next-block it doesnt matter as mining code double-checks anyway (unless you’re running with -debug or -regtest during a 100-block reorg, then you will assert-crash). This takes the expensive solution of checking transactions for this case during a reorg-off (these transactions will not be resurrected after the reorg completes, as they should, however), though alternatively we could redefine the mempool invariant to safe-to-put-in-next-block-but-may-include-immature-coinbase-spends (but only do so /during/ a reorg, not before or after, unless someone added an rpc or otherwise forced a reorg to a block, which we should probably add at some point anyway or so, see my mempoolfix2 branch for a maybe-ok proposal to implement that one instead).

Also includes a new block-tester which will crash master (because -regtest implies CTxMemPool::check, as does -debug).

TheBlueMatt force-pushed on Nov 13, 2014

in src/main.cpp: in d0608f623a outdated

1843@@ -1844,10 +1844,10 @@ bool static DisconnectTip(CValidationState &state) {
1844         // ignore validation errors in resurrected transactions
1845         list<CTransaction> removed;
1846         CValidationState stateDummy;
1847-        if (!tx.IsCoinBase())
1848-            if (!AcceptToMemoryPool(mempool, stateDummy, tx, false, NULL))
1849-                mempool.remove(tx, removed, true);
1850+        if (tx.IsCoinBase() || !AcceptToMemoryPool(mempool, stateDummy, tx, false, NULL))
1851+            mempool.remove(tx, removed, true);

luke-jr commented at 0:36 am on November 13, 2014:

Won’t AcceptToMemoryPool short-circuit since it’s already in there? (irrelevant if the short-circuit returns true or false)

TheBlueMatt commented at 0:41 am on November 13, 2014:

Huh? The AcceptToMemoryPool is returning the tx that is being resurrected.

luke-jr commented at 1:57 am on November 13, 2014:

AcceptToMemoryPool isn’t returning any tx, it’s trying to add the already-set-variable tx to the memory pool.

TheBlueMatt commented at 2:00 am on November 13, 2014:

AcceptToMemoryPool is returning the tx to the mempool (ie is doing the resurrecting), sorry that comment was entirely unclear.

luke-jr commented at 2:07 am on November 13, 2014:

Got it. The mempool.remove still doesn’t make sense, though…

TheBlueMatt commented at 2:12 am on November 13, 2014:

I didnt change the mempool.remove??? I just made it remove dependents of a coinbase transaction by changing the conditional…

luke-jr commented at 2:51 am on November 13, 2014:

I’m not sure it made sense before the change either. Maybe I’m missing something.

TheBlueMatt commented at 2:53 am on November 13, 2014:

Well it certainly makes sense now (ie now, if a coinbase is removed during a reorg, it will remove its dependants from mempool, which it did not use to)

in src/txmempool.cpp: in d0608f623a outdated

445@@ -445,6 +446,31 @@ void CTxMemPool::remove(const CTransaction &tx, std::list<CTransaction>& removed
446     }
447 }
448 
449+void CTxMemPool::removeCoinbaseSpends(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight)
450+{
451+    // Remove transactions spending a coinbase which are now immature

luke-jr commented at 0:37 am on November 13, 2014:

Why would they be immature? In the rare event of a reorg-to-chain-with-more-work-but-less-height?

TheBlueMatt commented at 0:40 am on November 13, 2014:

Yes, and to keep mempool consistent during reorgs.

TheBlueMatt force-pushed on Nov 13, 2014

laanwj added the label Bug on Nov 13, 2014

laanwj added the label Priority High on Nov 13, 2014

sipa commented at 2:47 pm on November 17, 2014: member

@TheBlueMatt Can you get this in a state where the tests pass (perhaps by delaying the enabling of large-reorg)?

TheBlueMatt closed this on Nov 18, 2014

TheBlueMatt reopened this on Nov 18, 2014

TheBlueMatt force-pushed on Nov 18, 2014

TheBlueMatt force-pushed on Nov 19, 2014

gavinandresen commented at 4:24 pm on November 19, 2014: contributor

Upon review… it seems to me the first immature-coinbase-in-the-mempool bug is due to this code:

 0   // Resurrect mempool transactions from the disconnected block.
 1    BOOST_FOREACH(const CTransaction &tx, block.vtx) {
 2        // ignore validation errors in resurrected transactions
 3        list<CTransaction> removed;
 4        CValidationState stateDummy;
 5        if (!tx.IsCoinBase())
 6            if (!AcceptToMemoryPool(mempool, stateDummy, tx, false, NULL))
 7                mempool.remove(tx, removed, true);
 8    }
 9    mempool.check(pcoinsTip);
10    // Update chainActive and related variables.
11    UpdateTip(pindexDelete->pprev);

AcceptToMemoryPool calls CheckInputs(), which does check for coinbase maturity. Seems to me just moving UpdateTip() to before the resurrect-into-mempool loop would fix that bug.

Coinbase spends right at the maturity threshold would get dropped from the mempool, but I don’t think I care (our wallet code should rebroadcast the spend if it doesn’t stay in a block).

The other bug, a coinbase spend in the mempool that becomes immature when DisconnectTip() happens: I think I’m ok with the proposed fix, but it feels like there might be a simpler and more robust solution– maybe the mempool should keep a list of all coinbase-spending transactions inside it (add to that list in addUnchecked()), and remove-then-AcceptToMemoryPool all of them (and any dependents) after a DisconnectTip().

ACK on the work queue optimization.

TheBlueMatt commented at 7:31 pm on November 19, 2014: member

@gavinandresen re: first bug: its not about transactions that are in the block, its about transactions in mempool, so calling AcceptToMemoryPool on anything that is within that loop wont help, afaict.

TheBlueMatt force-pushed on Nov 20, 2014

ghost commented at 5:49 am on November 24, 2014: none

You don’t need a large reorganization. Just connect some peers and start mining, then send some of the coinbase to each of the peers and keep mining, you will see it. The problem and solution is clear since this issue has been known since 5 years ago. :+1:

TheBlueMatt commented at 6:10 am on November 24, 2014: member

@john-connor I’d love to know what issue you’re referring to here. There is certainly no way to “send some of the coinbase to each of the peers” and, in #2821 you seem to think it is a locking issue, but the proper locks appear to be taken in the block creation code.

gavinandresen commented at 8:24 pm on November 24, 2014: contributor

FYI: I’m working on tests for these cases using @sipa’s excellent invalidatblock: https://github.com/gavinandresen/bitcoin-git/tree/coinbase_in_mempool_tests

gavinandresen commented at 3:57 pm on November 25, 2014: contributor

Fails a test case I wrote:

Spend a coinbase at depth 100+2, only in mempool (not confirmed)
Re-org back to depth 99

EXPECT: mempool empty RESULT: mempool contains the spend

See https://github.com/gavinandresen/bitcoin-git/commit/24eba4feffd29c0bee3e2296f04ed789b0b715f7 for code. (spend_101 is the transaction that is being left in the mempool)

ghost commented at 9:12 am on November 26, 2014: none

@TheBlueMatt I never mentioned “locks”. Setup a testnet of N peers and start mining, let the coinbase mature spend it around to the “loosely organized” peers (addresses), when N or more nodes generate a block a reorganization will possibly happen leaving some of the mempool’s full of (now) invalid transactions. gavinandresen’s latest test results confirm my theory. So, just remove them from the mempool during a reorganization and the assert should never be hit. If do not have the mining thread running you will never hit the assert either which masks the problem. These transactions also seem to make it into the wallet.dat and they should not. I’ve confirmed this because the problem follows the wallet.dat file.

TheBlueMatt commented at 1:29 am on November 27, 2014: member

@john-connor So…you’re referring to the bug that both of these pulls fix in different ways?

TheBlueMatt referenced this in commit 07c92aa881 on Nov 27, 2014

TheBlueMatt commented at 7:47 am on November 27, 2014: member

Note that the failures here are only from the test-update. I spent a while trying to get it to not overrun travis’ memory, and while I have one I think should work, I miscompiled it and then left and forgot to even push the source…so its gonna be till next week before I can get that updated. In any case, its been passing locally for a while, and I also added gavin’s tester from #5368 on a branch with this at https://github.com/TheBlueMatt/bitcoin/commits/mempoolfix3 (which passes as well)

ghost commented at 1:47 am on November 28, 2014: none

@TheBlueMatt These don’t fix the entire problem(s) but is a start.The invalid transaction will make it into the mempool long enough to get broadcasted out to the network where it will cause further mempool pollution. So, it’s still going to waste global network bandwidth. Luckily the wallet is smart enough to not allow the invalid transaction onto the network during a resend so it stops with the mempool.

TheBlueMatt commented at 2:21 am on November 28, 2014: member

Huh? The transactions are valid, but become invalid during a reorg (not even after)… Each node is responsible for keeping its mempool valid, not its peers. Again, I’m really not sure what bug you’re talking about.

On November 27, 2014 8:47:40 PM EST, John Connor notifications@github.com wrote:

@TheBlueMatt These don’t exactly fix the problem(s). The invalid transaction will make it into the mempool long enough to get broadcasted out to the network where it will cause further mempool pollution. So, it’s still going to waste global network bandwidth.

Reply to this email directly or view it on GitHub: #5267 (comment)

ghost commented at 7:54 pm on November 28, 2014: none

@TheBlueMatt then we are talking about two very similar but different bugs. I’ll open an issue that shows the full problem.

sipa commented at 12:14 pm on November 29, 2014: member

@gavinandresen @TheBlueMatt Just to be clear about the off-by-one: a transaction that made it into block N, can be spent at block N+100, which means with 101 confirmations (as the block it’s in already counts for 1).

TheBlueMatt commented at 5:56 pm on November 29, 2014: member

Hmm? The confusion actually wasn’t about which block can spend an output, but about the definition of the memorial mempool’s spendability requirement.

On November 29, 2014 7:14:16 AM EST, Pieter Wuille notifications@github.com wrote:

@gavinandresen @TheBlueMatt Just to be clear about the off-by-one: a transaction that made it into block N, can be spent at block N+100, which means with 101 confirmations (as the block it’s in already counts for 1).

Reply to this email directly or view it on GitHub: #5267 (comment)

in src/txmempool.cpp: in e671008cc8 outdated

484+}
485+
486+void CTxMemPool::removeConflicts(const CTransaction &tx)
487 {
488     // Remove transactions which depend on inputs of tx, recursively
489     list<CTransaction> result;

dgenr8 commented at 11:45 pm on November 29, 2014:

@TheBlueMatt This declaration can be removed.

TheBlueMatt force-pushed on Dec 4, 2014

TheBlueMatt commented at 10:07 am on December 4, 2014: member

I rebased on top of master, allowing me to pull in @gavinandresen’s test from #5368 without depending on another pull req, fixed the block-tester issues, and removed the commit which got rid of the removed-tx tracking (that @dgenr8 had issues with, though I’m still not able to reproduce…I’ll reintroduce that in a separate pull req).

TheBlueMatt force-pushed on Dec 4, 2014

sipa commented at 3:25 pm on December 4, 2014: member

@TheBlueMatt If you can get Travis to succeed here, I’ll reconsider, but right now this is just not mergable.

TheBlueMatt force-pushed on Dec 4, 2014

TheBlueMatt commented at 8:11 pm on December 4, 2014: member

@sipa I said the failures are just the test-update, could easily merge without it…anyway, I removed that commit, I’ll add it again via another pull.

sipa commented at 8:14 pm on December 4, 2014: member

@TheBlueMatt Sorry, missed that. I knew that the problem was just in the tester, but really - if Travis doesn’t pass, I tend to ignore it.

sipa commented at 2:00 am on December 5, 2014: member

Untested ACK; I prefer this approach over #5368, and it seems to pass the same tests.

gavinandresen commented at 2:23 am on December 5, 2014: contributor

Untested ACK, I have no preference on which version of this makes it in.

laanwj added this to the milestone 0.10.0 on Dec 5, 2014

Remove coinbase-dependant transactions during reorg.

This still leaves transactions in mempool that are potentially
invalid if the maturity period has been reorged out of, but at
least they're not missing inputs entirely.

868d041622

Remove txn which are invalidated by coinbase maturity during reorg 723d12c098

Make CTxMemPool::check more thourough by using CheckInputs b7b4318f3a

TheBlueMatt force-pushed on Dec 8, 2014

TheBlueMatt commented at 10:06 pm on December 8, 2014: member

Rebased for dumb merge conflict (new tests in rpc-test.sh).

Make CTxMemPool::remove more effecient by avoiding recursion 7fd6219af7

RPC-test based on invalidateblock for mempool coinbase spends 34318d7fad

TheBlueMatt force-pushed on Dec 8, 2014

TheBlueMatt commented at 10:10 pm on December 8, 2014: member

Oh, and resolved sipa’s nit.

sipa commented at 2:21 pm on December 9, 2014: member

Which one?

laanwj commented at 7:28 am on December 10, 2014: member

utACK commithash 34318d7fad7922ce56ff47908ff70e2c8a42ee56.

I have no preference which one makes it in either, #5267 or #5368. Which I suppose means that @sipa’s preference for this one is the tie-breaker. (signature)

TheBlueMatt commented at 7:31 am on December 10, 2014: member

@sipa the “while(!thing.empty())” vs “while (thing.size())” one.

laanwj referenced this in commit 9ae5a037a4 on Dec 11, 2014

in src/txmempool.cpp: in 34318d7fad

544@@ -513,17 +545,22 @@ void CTxMemPool::check(const CCoinsViewCache *pcoins) const
545 
546     uint64_t checkTotal = 0;
547 
548+    CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(pcoins));

laanwj commented at 12:35 pm on December 11, 2014:

People may wonder about this so this const_cast needs a comment why it doesn’t break expectations: the resulting child cache is never flushed so it is effectively const, and we don’t have a CConstCoinsViewCache that would make this explicit.

laanwj merged this on Dec 11, 2014

laanwj closed this on Dec 11, 2014

laanwj referenced this in commit 41cced2106 on Dec 11, 2014

TheBlueMatt deleted the branch on Dec 12, 2014

MarcoFalke locked this on Sep 8, 2021

Fix coinbase-spend mempool inconsistency after reorgs #5267