Minor bug? CalculateAncestorsAndCheckLimits off-by-one error when checking ancestor/descendant count limits

mjdietzx commented at 11:49 pm on November 28, 2021: contributor

A subtle (and minor) bug in how limits are calculated & checked in CalculateAncestorsAndCheckLimits https://github.com/bitcoin/bitcoin/blob/master/src/txmempool.cpp#L207

This helper can be invoked in a few cases:

CTxMemPool::CalculateMemPoolAncestors invokes it, if fSearchForParents is true, and entry is not in the mempool, then CalculateAncestorsAndCheckLimits will be exact/correct.
CTxMemPool::CalculateMemPoolAncestors invokes it, in the cases where entry is already in the mempool, we have an off-by-one error here https://github.com/bitcoin/bitcoin/blob/master/src/txmempool.cpp#L230 (because stageit->GetCountWithDescendants() will include entry in its count

So (2) highlights the case where there’s a bug, and it’s quite common.

We also need to think about how CTxMemPool::CheckPackageLimits uses this helper. I think it works better in this case because we have the assumption:

0Calculate all in-mempool ancestors of a set of transactions not already in the mempool and
1* check ancestor and descendant limits

ie we know none of the txns in package are in the mempool. So no double counting.

I doubt this is a serious bug, but I though it’s at least worth bringing up. It also seemed tricky to fix this with minimal/simple changes that works in all cases this helper is/may be used.

ie here https://github.com/bitcoin/bitcoin/blob/master/src/txmempool.cpp#L309, when fSearchForParents is true and one/some of the parents of this transaction are not in the mempool. Currently these parents (and any of their potential ancestors) are not included in the unconfirmed parents check. Again I don’t know if this actually matters, or if its unnecessary complexity, but want to check

mjdietzx added the label Bug on Nov 28, 2021

fanquake commented at 2:36 am on November 29, 2021: member

cc @glozow

glozow commented at 5:12 am on November 29, 2021: member

This is a good observation: the if (stageit->GetCountWithDescendants() + entry_count > limitDescendantCount) condition will overestimate the descendant count when entry is an in-mempool descendant of the entry in stageit. In the 3 cases you’ve nicely enumerated, this logic is only hit when CalculateMemPoolAncestors() is called for an in-mempool entry:

CTxMemPool::CalculateMemPoolAncestors invokes it, in the cases where entry is already in the mempool, we have an off-by-one error here https://github.com/bitcoin/bitcoin/blob/master/src/txmempool.cpp#L230 (because stageit->GetCountWithDescendants() will include entry in its count

In practice, these calls are always made with ancestor/descendant limits set to noLimit (see calls in miner.cpp, mempool removal, and verify by grepping for CalculateMemPoolAncestors(... false)). While this means the “bug” never results in a failure due to the overestimation, it is brittle to rely on this caller behavior.

Re: correctness in CheckPackageLimits, package will never contain in-mempool entries. It would currently result in a rejected package; in the future, we will de-duplicate and remove already-in-mempool transactiosn from the argument passed in to CheckPackageLimits(). If you’re curious, see this assertion in the draft implementation.

Thanks for bringing this up @mjdietzx. This is not an issue in practice, but is brittle code that can be patched pretty simply, e.g. by creating separate interfaces/code paths for an in-mempool and outside-mempool entry. We can group it in with a refactor, e.g. making the limits members of txmempool.

mjdietzx commented at 2:21 pm on November 29, 2021: contributor

Thanks, nice write-up @glozow. Agreed on all points. And after reading your comment and double checking codebase I realize that the incorrect case “case 2” is not currently hit.

Anyways I do think the code is brittle and there’s room for improvement (I may give it another try making it a little more robust myself) in CalculateAncestorsAndCheckLimits. And in a followup to #22698 I may try optimizing IsRBFOptIn a bit by putting a hard bound here, where “case 2” would be hit:

0pool.CalculateMemPoolAncestors(entry, ancestors, noLimit, noLimit, /* limitDescendantCount= */ MAX_BIP125_REPLACEMENT_CANDIDATES, noLimit, dummy, false);

There’s a little more to it (the optimization), but that just highlights the case where the caller (myself a week ago) encounters some unexpected behavior with CalculateMemPoolAncestors

glozow added the label Mempool on Aug 4, 2022

glozow commented at 9:13 am on August 4, 2022: member

Closing this as resolved based on the last couple messages

glozow closed this on Aug 4, 2022

bitcoin locked this on Aug 4, 2023

Minor bug? CalculateAncestorsAndCheckLimits off-by-one error when checking ancestor/descendant count limits #23621