tl;dr: We can remove the problem of Rule #5 pinning by ensuring that all
transactions in the mempool are always replaceable.


Currently Bitcoin Core implements rule #5 of BIP-125:

    The number of original transactions to be replaced and their descendant
    transactions which will be evicted from the mempool must not exceed a total
    of 100 transactions.

As of Bitcoin Core v24.0rc3, this rule is implemented via the
MAX_REPLACEMENT_CANDIDATES limit in GetEntriesForConflicts:

    // Rule #5: don't consider replacing more than MAX_REPLACEMENT_CANDIDATES
    // entries from the mempool. This potentially overestimates the number of actual
    // descendants (i.e. if multiple conflicts share a descendant, it will be counted multiple
    // times), but we just want to be conservative to avoid doing too much work.
    if (nConflictingCount > MAX_REPLACEMENT_CANDIDATES) {
        return strprintf("rejecting replacement %s; too many potential replacements (%d > %d)\n",
                         txid.ToString(),
                         nConflictingCount,
                         MAX_REPLACEMENT_CANDIDATES);
    }

There is no justification for this rule beyond avoiding "too much work"; the
exact number was picked at random when the BIP was written to provide an
initial conservative limit, and is not justified by benchmarks or memory usage
calculations. It may in fact be the case that this rule can be removed entirely
as the overall mempool size limits naturally limit the maximum number of
possible replacements.


But for the sake of argument, let's suppose some kind of max replacement limit
is required. Can we avoid rule #5 pinning? The answer is yes, we can, with the
following invariant:

    No transaction may be accepted into the mempool that would cause another
    transaction to be unable to be replaced due to Rule #5.

We'll call this the Replaceability Invariant. Implementing this rule is simple:
for each transaction maintain an integer, nReplacementCandidates. When a
non-conflicting transaction is considered for acceptance to the mempool, verify
that nReplacementCandidates + 1 < MAX_REPLACEMENT_CANDIDATES for each
unconfirmed parent. When a transaction is accepted, increment
nReplacementCandidates by 1 for each unconfirmed parent.

When a *conflicting* transaction is considered for acceptance, we do _not_ need
to verify anything: we've already guaranteed that every transaction in the
mempool is replaceable! The only thing we may need to do is to decrement
nReplacementCandidates by however many children we have replaced, for all
unconfirmed parents.

When a block is mined, note how the nReplacementCandidates of all unconfirmed
transactions remains unchanged because a confirmed transaction can't spend an
unconfirmed txout.

The only special case to handle is a reorg that changes a transaction from
confirmed to unconfirmed. Setting nReplacementCandidates to
MAX_REPLACEMENT_CANDIDATES would be fine in that very rare case.


Note that like the existing MAX_REPLACEMENT_CANDIDATES check, the
Replaceability Invariant overestimates the number of transactions to be
replaced in the event that multiple children are spent by the same transaction.
That's ok: diamond tx graphs are even more unusual than unconfirmed children,
and there's no reason to bend over backwards to accomodate them.

Prior art: this proposed rule is similar in spirit to the package limits aready
implemented in Bitcoin Core.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org