Return-Path: Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id B2256C002D for ; 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 ; 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 ; 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 ; Mon, 7 Nov 2022 21:21:26 +0000 (UTC) Received: by mail-lf1-x12e.google.com with SMTP id bp15so18460462lfb.13 for ; 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: In-Reply-To: From: Suhas Daftuar Date: Mon, 7 Nov 2022 16:21:11 -0500 Message-ID: To: Bitcoin Protocol Discussion 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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
Hello bitcoin-dev,

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.

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.


On Mon,= Nov 7, 2022 at 3:17 PM Peter Todd via bitcoin-dev <bitcoin-dev@lists.li= nuxfoundation.org> wrote:
tl;dr: We can remove the problem of Rule #5 pinning by ens= uring that all
transactions in the mempool are always replaceable.


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

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

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

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

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 us= age
calculations. It may in fact be the case that this rule can be removed enti= rely
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 replacemen= t limit
is required. Can we avoid rule #5 pinning? The answer is yes, we can, with = the
following invariant:

=C2=A0 =C2=A0 No transaction may be accepted into the mempool that would ca= use another
=C2=A0 =C2=A0 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, ve= rify
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 unconfirm= ed
transactions remains unchanged because a confirmed transaction can't sp= end an
unconfirmed txout.

The only special case to handle is a reorg that changes a transaction from<= br> 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 transact= ion.
That's ok: diamond tx graphs are even more unusual than unconfirmed chi= ldren,
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 ar= eady
implemented in Bitcoin Core.

--
http= s://petertodd.org 'peter'[:-1]@petertodd.org
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--0000000000006a466f05ece80148--