path: root/35/1cc4ea8b0d6cd7242143619a3b1d0a9e539360

Return-Path: <sdaftuar@gmail.com>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136])
 by lists.linuxfoundation.org (Postfix) with ESMTP id B2256C002D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon,  7 Nov 2022 21:21:28 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp3.osuosl.org (Postfix) with ESMTP id 86A8560BD6
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon,  7 Nov 2022 21:21:28 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 86A8560BD6
Authentication-Results: smtp3.osuosl.org;
 dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
 header.a=rsa-sha256 header.s=20210112 header.b=KYTh/OQ7
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level: 
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
 HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
 SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Received: from smtp3.osuosl.org ([127.0.0.1])
 by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id xTWqLCqjun9d
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon,  7 Nov 2022 21:21:27 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 13BE060BDB
Received: from mail-lf1-x12e.google.com (mail-lf1-x12e.google.com
 [IPv6:2a00:1450:4864:20::12e])
 by smtp3.osuosl.org (Postfix) with ESMTPS id 13BE060BDB
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon,  7 Nov 2022 21:21:26 +0000 (UTC)
Received: by mail-lf1-x12e.google.com with SMTP id bp15so18460462lfb.13
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 07 Nov 2022 13:21:26 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
 h=to:subject:message-id:date:from:in-reply-to:references:mime-version
 :from:to:cc:subject:date:message-id:reply-to;
 bh=8NDEtSjduVzi6ZTgOSGrwTE5tCBYru9wL4R9epW2v34=;
 b=KYTh/OQ7Rfd0tTS2+SP/PYlvWVswvetn0rryN1rut97UynpFLU8iwx+NiVcCkaDKPg
 17BBPkhu1yexK8VN07NBsO75Z979GGC1QRZLToUhWyixmwJtDgSajO14faupCYZnGC5Z
 s6cwjx3okTNDhLamWBKF2sGIkFDbWcdL7aFdqj+KyawXgqgbPev+u+GS/gW4jaFYgbkV
 OxijgQKP7R+luLQlHUWIijxKsocNtVKUmpzRC/SQ9KSICFg56bBwEjVhX0BndZq2zrZE
 kQkW+2HofrKq8uY9yHc/gkMQEwvqg4JIvSbByGYXKNJ9cVrWNUjUSFyrZvX924y2viZZ
 iY5g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20210112;
 h=to:subject:message-id:date:from:in-reply-to:references:mime-version
 :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to;
 bh=8NDEtSjduVzi6ZTgOSGrwTE5tCBYru9wL4R9epW2v34=;
 b=Pwq4yTEKOIBJRj0rgr6/698FPGsBtixNCuDlZOATikotFFY8/HKDrMcWqG1tClzYkK
 R+aWkAF1jWeE3qfhBA1fDbEHn9gmhXcTBcqOvZ0hSo+cR11xHrFhTWv9w7xkbr6nWGW9
 w0K9BalV+uxjzcDxVBoD0XxvSVj4TbbXfCtEYx9J3RpLCSNb/xjdSj5vPrIf5O4buhU6
 VDXENYFQXfoX/E9devv2oFVgVQ/8cBDVwdZ2mDZbC6WILQVwYHC8863R6tybj0GlbgF3
 UzSvlUF9dLQkmp5lLtxJiBDGlO5qupN0ztw02gD6FTBe0vMyrrme+scYI6O6PfHWeauT
 NeZA==
X-Gm-Message-State: ACrzQf3qibFwCA61dwsPkFW79EiFfFeeWPt/363E5qlUufEPFXtx75c9
 kuZJIwHwQec1GanrcDf1AuS1JdIwYNAyoV1YDg2Qs5Nu
X-Google-Smtp-Source: AMsMyM7+HWJ9wgraEqebKvLH6acMj8DdNZZmW7s4W6W1u0c9aD9XQsfPKtFOJFtS7KkKYThRGBNpeO54gvbJymw+Ncc=
X-Received: by 2002:ac2:5dc8:0:b0:4aa:26a2:bd94 with SMTP id
 x8-20020ac25dc8000000b004aa26a2bd94mr17277876lfq.60.1667856083861; Mon, 07
 Nov 2022 13:21:23 -0800 (PST)
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
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Mon, 07 Nov 2022 21:21:28 -0000

--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--