Feedback-ID: i525146e8:Fastmail
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
Precedence: list


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