Re: [bitcoin-dev] Removing BIP-125 Rule #5 Pinning with the Always-Replaceable Invariant

From: Suhas Daftuar <sdaftuar@gmail•com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Removing BIP-125 Rule #5 Pinning with the Always-Replaceable Invariant
Date: Mon, 7 Nov 2022 16:21:11 -0500	[thread overview]
Message-ID: <CAFp6fsH0BXn51DqpJLWn56ecohCJZ+skVvabGBRmjeK5u08vdg@mail.gmail.com> (raw)
In-Reply-To: <Y2ln2fJ+8+Q0qS0E@petertodd.org>

[-- Attachment #1: Type: text/plain, Size: 4888 bytes --]

Hello bitcoin-dev,

The description in the OP is completely broken for the simple reason that
Bitcoin transactions can have multiple inputs, and so a single transaction
can conflict with multiple in-mempool transactions. The proposal would
limit the number of descendants of each in-mempool transaction to
MAX_REPLACEMENT_CANDIDATES (note that this is duplicative of the existing
Bitcoin Core descendant limits), but a transaction that has, say, 500
inputs might arrive and conflict with 500 unrelated in-mempool
transactions. This could result in 12,500 evictions -- far more than the
100 that was intended.

Also, note that those 500 transactions might instead have 24 ancestors each
(again, using the default chain limits in Bitcoin Core) -- this would
result in 12,000 transactions whose state would be updated as a result of
evicting those 500 transactions. Hopefully this gives some perspective on
why we have a limit.

On Mon, Nov 7, 2022 at 3:17 PM Peter Todd via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:

> 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
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 5963 bytes --]