5

Since 2015, Bitcoin Core has included a -limitdescendantcount configuration parameter (added in this commit) that forbids a transaction in a node's mempool from having more than x descendants accepted into that mempool (default x is 25). I think this addresses two concerns:

  • Excessive package comparisons: for ancestor feerate mining, a node builds multiple different virtual packages containing related transactions and derives their package feerate. If the package feerate is higher than the feerate of the individual transactions contained within it, the node will prefer to keep and mine that package over the individual transactions. The more related transactions there are in a mempool, the greater the number of packages that need to be compared; given the choice of 25 as the value here, I'm guessing the number of comparisons that needs to be made isn't combinatorial but can be exponential in the worst case.

  • Wasted bandwidth and censorship: if a node accepts one parent with as many descendents as is possible to fit in its mempool, then a miner producing a block with a transaction that conflicts with the parent can invalidate the entire mempool. This can waste a huge amount of relay node bandwidth (~150 MB every 10 minutes times ~50,000 nodes is 540 TB per day, not including inv overhead). It may also be able to use this mechanism to prevent other people's unrelated transactions from confirming at low cost to the denial of service attacker.

Which of those concerns is the one that most motivates keeping this limit at 25? I realize the answer there might be opinionated (and so a poor choice for this site), but imagine that we had to disentangle the concerns and have two different limits: one for preventing excessive comparisons and one for reducing the liklihood of wasted bandwidth. In that case, what limitdescendantcount values would we use for each of those different cases?

Improve this question

1 Answer 1

Reset to default
7

Your first point ("Excessive package comparisons") gets at the essence of the issue, though it's not exactly what you described.

There are two main operations where the ancestor and descendant limits come up in practice: mining and eviction. When constructing a block template, what we do is iterate over the mempool in descending "ancestor feerate order", where the ancestor feerate of a transaction is defined as the minimum of it's own feerate and the total feerate including its unconfirmed ancestors (dependencies). We select the highest such transaction for inclusion in the block candidate, including all unconfirmed ancestors, and then we'd like to update the sort order of the remaining transactions so that we no longer include as ancestors the transactions which have been selected.

So if you imagine that we might select a transaction with 24 ancestors as our first choice, then for each of the 25 transactions that we add to the block, we must potentially update the ancestor scores of 24 transactions that descend from those transactions. So there's (up to) an n^2 blowup here in the amount of work we do for each transaction we add, where n is the number of ancestors or descendants that we permit.

Something similar happens in the eviction algorithm. There, we look at the transaction that has the worst feerate-with-descendants score, and evict it along with all descendants. After we do so, we have to update the descendant scores of all the ancestors of those evicted transactions, which again is an n^2 amount of work we might have to do.

The reason we have these limits is related to these O(n^2) computations that come up. 25 seemed low enough that we can mostly manage; raising it to (say) 100 would mean these algorithms could take 16 times as long to run (in the worst case).

For some additional background, there was some discussion on the bitcoin-dev mailing list back when these limits were proposed:

Improve this answer
2
  • 1
    Excellent answer, thanks! It occurs to me, looking at my original question, that we do have separate limits to address the separate problems. -limit(ancestor|descendant)count addresses the quadratic blowup in template creation; -limit(ancestor|descendant)size addresses the problem of a single mined replacement invalidating an excessive amount of mempool contents (in addition to addressing other problems mentioned in your emails).
    – David A. Harding
    Commented May 5, 2023 at 21:50
  • 3
    Yes, that's right. The size limits (in vbytes) actually address a couple different issues. The ancestor size limit is there to ensure that we don't take a transaction to our mempool that is unlikely to confirm anytime soon because it depends on too many transactions (imagine a transaction that required 1MB of ancestors to be confirmed first). The descendant size limit is there to mitigate the problem of "free relay" when transactions are evicted from the mempool (when the mempool gets full, we evict some tx and its descendants, and we don't want that to be too large).
    – sdaftuar
    Commented May 6, 2023 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.