MIME-Version: 1.0
References: <Y2ln2fJ+8+Q0qS0E@petertodd.org>
In-Reply-To: <Y2ln2fJ+8+Q0qS0E@petertodd.org>
From: Suhas Daftuar <sdaftuar@gmail.com>
Date: Mon, 7 Nov 2022 16:21:11 -0500
Message-ID: <CAFp6fsH0BXn51DqpJLWn56ecohCJZ+skVvabGBRmjeK5u08vdg@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000006a466f05ece80148"
Subject: Re: [bitcoin-dev] Removing BIP-125 Rule #5 Pinning with the
 Always-Replaceable Invariant
Precedence: list

--0000000000006a466f05ece80148
Content-Type: text/plain; charset="UTF-8"

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
>

--0000000000006a466f05ece80148
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div dir=3D"ltr"><div>Hello bitcoin-dev,</div><div><br></d=
iv><div>The description in the OP is completely broken for the simple reaso=
n that Bitcoin transactions can have multiple inputs, and so a single trans=
action can conflict with multiple in-mempool transactions. The proposal wou=
ld limit the number of descendants of each in-mempool transaction to MAX_RE=
PLACEMENT_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.</di=
v><div><br></div><div>Also, note that those 500 transactions might instead =
have 24 ancestors each (again, using the default chain limits in Bitcoin Co=
re) -- this would result in 12,000 transactions whose state would be update=
d as a result of evicting those 500 transactions. Hopefully this gives some=
 perspective on why we have a limit.</div><div><br></div><div><br></div></d=
iv><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Mon,=
 Nov 7, 2022 at 3:17 PM Peter Todd via bitcoin-dev &lt;<a href=3D"mailto:bi=
tcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.li=
nuxfoundation.org</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote"=
 style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);p=
adding-left:1ex">tl;dr: We can remove the problem of Rule #5 pinning by ens=
uring that all<br>
transactions in the mempool are always replaceable.<br>
<br>
<br>
Currently Bitcoin Core implements rule #5 of BIP-125:<br>
<br>
=C2=A0 =C2=A0 The number of original transactions to be replaced and their =
descendant<br>
=C2=A0 =C2=A0 transactions which will be evicted from the mempool must not =
exceed a total<br>
=C2=A0 =C2=A0 of 100 transactions.<br>
<br>
As of Bitcoin Core v24.0rc3, this rule is implemented via the<br>
MAX_REPLACEMENT_CANDIDATES limit in GetEntriesForConflicts:<br>
<br>
=C2=A0 =C2=A0 // Rule #5: don&#39;t consider replacing more than MAX_REPLAC=
EMENT_CANDIDATES<br>
=C2=A0 =C2=A0 // entries from the mempool. This potentially overestimates t=
he number of actual<br>
=C2=A0 =C2=A0 // descendants (i.e. if multiple conflicts share a descendant=
, it will be counted multiple<br>
=C2=A0 =C2=A0 // times), but we just want to be conservative to avoid doing=
 too much work.<br>
=C2=A0 =C2=A0 if (nConflictingCount &gt; MAX_REPLACEMENT_CANDIDATES) {<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 return strprintf(&quot;rejecting replacement %s=
; too many potential replacements (%d &gt; %d)\n&quot;,<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0txid.ToString(),<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0nConflictingCount,<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0MAX_REPLACEMENT_CANDIDATES);<br>
=C2=A0 =C2=A0 }<br>
<br>
There is no justification for this rule beyond avoiding &quot;too much work=
&quot;; the<br>
exact number was picked at random when the BIP was written to provide an<br=
>
initial conservative limit, and is not justified by benchmarks or memory us=
age<br>
calculations. It may in fact be the case that this rule can be removed enti=
rely<br>
as the overall mempool size limits naturally limit the maximum number of<br=
>
possible replacements.<br>
<br>
<br>
But for the sake of argument, let&#39;s suppose some kind of max replacemen=
t limit<br>
is required. Can we avoid rule #5 pinning? The answer is yes, we can, with =
the<br>
following invariant:<br>
<br>
=C2=A0 =C2=A0 No transaction may be accepted into the mempool that would ca=
use another<br>
=C2=A0 =C2=A0 transaction to be unable to be replaced due to Rule #5.<br>
<br>
We&#39;ll call this the Replaceability Invariant. Implementing this rule is=
 simple:<br>
for each transaction maintain an integer, nReplacementCandidates. When a<br=
>
non-conflicting transaction is considered for acceptance to the mempool, ve=
rify<br>
that nReplacementCandidates + 1 &lt; MAX_REPLACEMENT_CANDIDATES for each<br=
>
unconfirmed parent. When a transaction is accepted, increment<br>
nReplacementCandidates by 1 for each unconfirmed parent.<br>
<br>
When a *conflicting* transaction is considered for acceptance, we do _not_ =
need<br>
to verify anything: we&#39;ve already guaranteed that every transaction in =
the<br>
mempool is replaceable! The only thing we may need to do is to decrement<br=
>
nReplacementCandidates by however many children we have replaced, for all<b=
r>
unconfirmed parents.<br>
<br>
When a block is mined, note how the nReplacementCandidates of all unconfirm=
ed<br>
transactions remains unchanged because a confirmed transaction can&#39;t sp=
end an<br>
unconfirmed txout.<br>
<br>
The only special case to handle is a reorg that changes a transaction from<=
br>
confirmed to unconfirmed. Setting nReplacementCandidates to<br>
MAX_REPLACEMENT_CANDIDATES would be fine in that very rare case.<br>
<br>
<br>
Note that like the existing MAX_REPLACEMENT_CANDIDATES check, the<br>
Replaceability Invariant overestimates the number of transactions to be<br>
replaced in the event that multiple children are spent by the same transact=
ion.<br>
That&#39;s ok: diamond tx graphs are even more unusual than unconfirmed chi=
ldren,<br>
and there&#39;s no reason to bend over backwards to accomodate them.<br>
<br>
Prior art: this proposed rule is similar in spirit to the package limits ar=
eady<br>
implemented in Bitcoin Core.<br>
<br>
-- <br>
<a href=3D"https://petertodd.org" rel=3D"noreferrer" target=3D"_blank">http=
s://petertodd.org</a> &#39;peter&#39;[:-1]@<a href=3D"http://petertodd.org"=
 rel=3D"noreferrer" target=3D"_blank">petertodd.org</a><br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>
</div>

--0000000000006a466f05ece80148--