1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
|
Return-Path: <pete@petertodd.org>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137])
by lists.linuxfoundation.org (Postfix) with ESMTP id 9F590C002D
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 7 Nov 2022 20:17:38 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp4.osuosl.org (Postfix) with ESMTP id 78CDD408F9
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 7 Nov 2022 20:17:38 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 78CDD408F9
Authentication-Results: smtp4.osuosl.org; dkim=pass (2048-bit key,
unprotected) header.d=messagingengine.com header.i=@messagingengine.com
header.a=rsa-sha256 header.s=fm1 header.b=iyG4dklZ
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.602
X-Spam-Level:
X-Spam-Status: No, score=-2.602 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001]
autolearn=ham autolearn_force=no
Received: from smtp4.osuosl.org ([127.0.0.1])
by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id z2ng3Dhm6O2M
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 7 Nov 2022 20:17:36 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 66E73408BC
Received: from wout5-smtp.messagingengine.com (wout5-smtp.messagingengine.com
[64.147.123.21])
by smtp4.osuosl.org (Postfix) with ESMTPS id 66E73408BC
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 7 Nov 2022 20:17:36 +0000 (UTC)
Received: from compute1.internal (compute1.nyi.internal [10.202.2.41])
by mailout.west.internal (Postfix) with ESMTP id A3A7232009E1
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 7 Nov 2022 15:17:33 -0500 (EST)
Received: from mailfrontend1 ([10.202.2.162])
by compute1.internal (MEProxy); Mon, 07 Nov 2022 15:17:33 -0500
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=
messagingengine.com; h=cc:content-type:date:date:feedback-id
:feedback-id:from:from:in-reply-to:message-id:mime-version
:reply-to:sender:subject:subject:to:to:x-me-proxy:x-me-proxy
:x-me-sender:x-me-sender:x-sasl-enc; s=fm1; t=1667852253; x=
1667938653; bh=KdguMCYYxvyHBw4tAMN69WbCvg0F8oapflzWaUjgVv8=; b=i
yG4dklZEZBOrRGTeqtNdpnT50G7rdWPp7FDUgjWnOSdkEYZZDa/0lU6G5w+knOP5
IGisnUX307glpkA2lWXL08/3fQt+UT86VlzlN/H31KXUJq7N3xPJ5Js+TkpobhAr
Pjf/u6d72qp8l+zUQ8+NapVFDeFIKC/PYjGLNqjP7tW7hJo233RAA5RXLsZNUHhX
qSG7zxk/9EpuDCi/jW2ECBF27fvDPbZoe15CKAYtk6M5o5Iobekyhuyr1XcQrMA2
+NXi1w7rDTKbL99FQS/U8o/ekTVAn1exbNILZBpymVs+rBvuae+6hbENnHle6jkj
duAm+fwHBUNp9DPAgxLSQ==
X-ME-Sender: <xms:3GdpYwlUDGnTPqFbBlYTaPolqfd-J9nxnDae-QO6yORjtOTffhCC_A>
<xme:3GdpY_35AVyx5NmMk-BR0st7I6GUHfmTVcN54M7UJhe-ZNpelPVYnW7trMeXzPpsc
hJNC24XHY9a_3ellhU>
X-ME-Received: <xmr:3GdpY-oWDcZnDEsz5_T9u1Rj2IaH5TT_YXYtqDPCVDrUX8ir_whDa87iT1vmqA>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvgedrvdekgddufeefucetufdoteggodetrfdotf
fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen
uceurghilhhouhhtmecufedttdenucenucfjughrpeffhffvuffkgggtugesghdtreertd
dtvdenucfhrhhomheprfgvthgvrhcuvfhougguuceophgvthgvsehpvghtvghrthhouggu
rdhorhhgqeenucggtffrrghtthgvrhhnpefhteevgeeuvdekheeivdeffeduuedufefhte
elheffgfelueefieffjeefffeuleenucffohhmrghinhepphgvthgvrhhtohguugdrohhr
ghenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehpvg
htvgesphgvthgvrhhtohguugdrohhrgh
X-ME-Proxy: <xmx:3GdpY8lpxGZnOeqQ4qTRa7p75XhIk17_uqFwTTAqXe7UvXNLkrgsnA>
<xmx:3GdpY-1kO0htwA5vdNTeIygR2ZAbtPUukd3lw3e8oO3L4EmpRtWc9g>
<xmx:3GdpYzuDWS9eXx_UNtFJTHSmUMyJ1RqR8cScTz91LDWq6WNRsrFZQQ>
<xmx:3WdpY8BCY7kiwANe8YXboAzkuFupPQZfVU2cWLmZuxNsolsVpCIu6g>
Feedback-ID: i525146e8:Fastmail
Received: by mail.messagingengine.com (Postfix) with ESMTPA for
<bitcoin-dev@lists.linuxfoundation.org>; Mon,
7 Nov 2022 15:17:32 -0500 (EST)
Received: by localhost (Postfix, from userid 1000)
id 884855F83B; Mon, 7 Nov 2022 15:17:29 -0500 (EST)
Date: Mon, 7 Nov 2022 15:17:29 -0500
From: Peter Todd <pete@petertodd.org>
To: bitcoin-dev@lists.linuxfoundation.org
Message-ID: <Y2ln2fJ+8+Q0qS0E@petertodd.org>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha512;
protocol="application/pgp-signature"; boundary="SJbM/+xIlehVFAWP"
Content-Disposition: inline
Subject: [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 20:17:38 -0000
--SJbM/+xIlehVFAWP
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
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 t=
otal
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_CANDIDAT=
ES
// 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 repl=
acements (%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 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 replacement li=
mit
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 sim=
ple:
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 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 transact=
ion.
That's ok: diamond tx graphs are even more unusual than unconfirmed childre=
n,
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.
--=20
https://petertodd.org 'peter'[:-1]@petertodd.org
--SJbM/+xIlehVFAWP
Content-Type: application/pgp-signature; name="signature.asc"
-----BEGIN PGP SIGNATURE-----
iQIzBAEBCgAdFiEE0RcYcKRzsEwFZ3N5Lly11TVRLzcFAmNpZ8wACgkQLly11TVR
LzezDw/8DNG8Stac5svYqva2Jd/RDziBtTdWqoRsmw58AIbOer5X8WClltO+ALko
gUY2EB3WTbFY/WfXG9XcIXnboJ/uTuw5H55R0bzYTS4P9O8Fjz50xyk4A194C/Nm
6K6lwZsI1qLkupiWkp/58MHN9KzDbCYgmMgJfROsmXUysjm0RDUpUQ/En73PUgbH
3pnpZbme3ozbPRW124SF4VsH/+7tZRMK3bqCbH0vm2ovTFV7w4R4qH+CQY2sw34+
820I4NFa+CxcEpztoIMZYiCD3psMyrXUmacBvdC2iFZowht3gTSphsuzjE9U+/5P
K9c3W4Z/34bC+ZjumBbUnjMUOTgBxfC4G3JtYIwvIUuyUSPrDtIlbzuE4wZn/e4Q
xPOCzfWayRUAaTrQNWEoQrWAdWpJBci7z5WYFL9aoNqXFjvtmULEnjlWCPStjW/l
sveon93uwlZvYjtjBagNrMzg3BjCPHXTGaSWbV3CYH+JBp5RXdmVYV7A+FRFU4wP
XcqPiWyv78fMk6gydj/rco/BWpNXFoqqwZ4csCRLI0CgPbqdWmHxYE0WDYcwtF/u
n14S8Tf+Hg37htNWU+4kIJYDQkSvtBx9z2Ve82WKx0noHry0qLwoy2zz5BpRGkN8
8qQ9aeEW5xtkmz0/X4cu0LWHBj2qBa5kgnvL4u89j8Ky9vx4/n4=
=Vg3Z
-----END PGP SIGNATURE-----
--SJbM/+xIlehVFAWP--
|
