From: Peter Todd <pete@petertodd•org>
To: bitcoin-dev@lists•linuxfoundation.org
Subject: [bitcoin-dev] Removing BIP-125 Rule #5 Pinning with the Always-Replaceable Invariant
Date: Mon, 7 Nov 2022 15:17:29 -0500 [thread overview]
Message-ID: <Y2ln2fJ+8+Q0qS0E@petertodd.org> (raw)
[-- Attachment #1: Type: text/plain, Size: 3576 bytes --]
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
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]
next reply other threads:[~2022-11-07 20:17 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-11-07 20:17 Peter Todd [this message]
2022-11-07 21:17 ` [bitcoin-dev] Using Full-RBF to fix BIP-125 Rule #3 Pinning with nLockTime Peter Todd
2022-11-07 22:55 ` Antoine Riard
2022-11-09 12:41 ` Peter Todd
2022-11-11 3:00 ` David A. Harding
2022-11-07 21:21 ` [bitcoin-dev] Removing BIP-125 Rule #5 Pinning with the Always-Replaceable Invariant Suhas Daftuar
2022-11-07 21:27 ` Peter Todd
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=Y2ln2fJ+8+Q0qS0E@petertodd.org \
--to=pete@petertodd$(echo .)org \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox