Merge bitcoin/bitcoin#23711: docs: RBF policy and mempool limit exemptions

82858bab64274506cfcd365a6588a1a9141fb22c [doc] CPFP carve out and single-conflict RBF exemption (glozow)
1fd49eb498c75a1d14193bb736d195a3dc75ae12 [doc] clarify RBF difference from BIP125 (glozow)
919ae8b8cdeccfc04026293153b876e27469a027 [doc] current rbf policy (glozow)

Pull request description:

  Since RBF was first implemented and BIP125 was written, our code has changed, people have highlighted implementation differences, and some people have proposed further changes to it. Many people seem to support the idea of documenting our _current_ RBF policy as it stands today.

  As the ancestor/descendant limit carve-out exemptions are very related to RBF, it seemed appropriate to group them with this PR.

  Related to #22806 - it seems that these policies are the most confusing for people, or at least the most documentation-requested.

ACKs for top commit:
  dunxen:
    ACK 82858ba
  t-bast:
    ACK https://github.com/bitcoin/bitcoin/pull/23711/commits/82858bab64274506cfcd365a6588a1a9141fb22c, thanks @glozow!
  darosior:
    re-ACK 82858bab64274506cfcd365a6588a1a9141fb22c
  ariard:
    ACK 82858ba

Tree-SHA512: 5d296537cce3488c18179c0aa76c739ca02fdc424e5aa17129b4cdd0d057358f86bcc1e92a9857bd2c60495f834fe9d9406d1a9f8ac5cfc8f0f4f4c27ec4f8e1

4 files changed, 143 insertions, 4 deletions

diff --git a/doc/bips.md b/doc/bips.md
index b5fa9315d3..27adcedd31 100644
--- a/doc/bips.md
+++ b/doc/bips.md
@@ -32,7 +32,7 @@ BIPs that are implemented by Bitcoin Core (up-to-date up to **v22.0**):
 * [`BIP 111`](https://github.com/bitcoin/bips/blob/master/bip-0111.mediawiki): `NODE_BLOOM` service bit added, and enforced for all peer versions as of **v0.13.0** ([PR #6579](https://github.com/bitcoin/bitcoin/pull/6579) and [PR #6641](https://github.com/bitcoin/bitcoin/pull/6641)).
 * [`BIP 112`](https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki): The CHECKSEQUENCEVERIFY opcode has been implemented since **v0.12.1** ([PR #7524](https://github.com/bitcoin/bitcoin/pull/7524)), and has been *buried* since **v0.19.0** ([PR #16060](https://github.com/bitcoin/bitcoin/pull/16060)).
 * [`BIP 113`](https://github.com/bitcoin/bips/blob/master/bip-0113.mediawiki): Median time past lock-time calculations have been implemented since **v0.12.1** ([PR #6566](https://github.com/bitcoin/bitcoin/pull/6566)), and has been *buried* since **v0.19.0** ([PR #16060](https://github.com/bitcoin/bitcoin/pull/16060)).
-* [`BIP 125`](https://github.com/bitcoin/bips/blob/master/bip-0125.mediawiki): Opt-in full replace-by-fee signaling honoured in mempool and mining as of **v0.12.0** ([PR 6871](https://github.com/bitcoin/bitcoin/pull/6871)). Enabled by default in the wallet GUI as of **v0.18.1** ([PR #11605](https://github.com/bitcoin/bitcoin/pull/11605))
+* [`BIP 125`](https://github.com/bitcoin/bips/blob/master/bip-0125.mediawiki): Opt-in full replace-by-fee signaling partially implemented. See doc/policy/mempool-replacements.md.
 * [`BIP 130`](https://github.com/bitcoin/bips/blob/master/bip-0130.mediawiki): direct headers announcement is negotiated with peer versions `>=70012` as of **v0.12.0** ([PR 6494](https://github.com/bitcoin/bitcoin/pull/6494)).
 * [`BIP 133`](https://github.com/bitcoin/bips/blob/master/bip-0133.mediawiki): feefilter messages are respected and sent for peer versions `>=70013` as of **v0.13.0** ([PR 7542](https://github.com/bitcoin/bitcoin/pull/7542)).
 * [`BIP 141`](https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki): Segregated Witness (Consensus Layer) as of **v0.13.0** ([PR 8149](https://github.com/bitcoin/bitcoin/pull/8149)), defined for mainnet as of **v0.13.1** ([PR 8937](https://github.com/bitcoin/bitcoin/pull/8937)), and *buried* since **v0.19.0** ([PR #16060](https://github.com/bitcoin/bitcoin/pull/16060)).
diff --git a/doc/policy/README.md b/doc/policy/README.md
index 9c83f4b56e..6e8686365d 100644
--- a/doc/policy/README.md
+++ b/doc/policy/README.md
@@ -1,10 +1,15 @@
 # Transaction Relay Policy
 
-Policy is a set of validation rules, in addition to consensus, enforced for unconfirmed
-transactions.
+**Policy** (Mempool or Transaction Relay Policy) is the node's set of validation rules, in addition
+to consensus, enforced for unconfirmed transactions before submitting them to the mempool. These
+rules are local to the node and configurable (e.g. `-minrelaytxfee`, `-limitancestorsize`,
+`-incrementalRelayFee`). Policy may include restrictions on the transaction itself, the transaction
+in relation to the current chain tip, and the transaction in relation to the node's mempool
+contents. Policy is *not* applied to transactions in blocks.
 
 This documentation is not an exhaustive list of all policy rules.
 
+- [Mempool Limits](mempool-limits.md)
+- [Mempool Replacements](mempool-replacements.md)
 - [Packages](packages.md)
 
-
diff --git a/doc/policy/mempool-limits.md b/doc/policy/mempool-limits.md
new file mode 100644
index 0000000000..73ab017f1b
--- /dev/null
+++ b/doc/policy/mempool-limits.md
@@ -0,0 +1,65 @@
+# Mempool Limits
+
+## Definitions
+
+Given any two transactions Tx0 and Tx1 where Tx1 spends an output of Tx0,
+Tx0 is a *parent* of Tx1 and Tx1 is a *child* of Tx0.
+
+A transaction's *ancestors* include, recursively, its parents, the parents of its parents, etc.
+A transaction's *descendants* include, recursively, its children, the children of its children, etc.
+
+A mempool entry's *ancestor count* is the total number of in-mempool (unconfirmed) transactions in
+its ancestor set, including itself.
+A mempool entry's *descendant count* is the total number of in-mempool (unconfirmed) transactions in
+its descendant set, including itself.
+
+A mempool entry's *ancestor size* is the aggregated virtual size of in-mempool (unconfirmed)
+transactions in its ancestor set, including itself.
+A mempool entry's *descendant size* is the aggregated virtual size of in-mempool (unconfirmed)
+transactions in its descendant set, including itself.
+
+Transactions submitted to the mempool must not exceed the ancestor and descendant limits (aka
+mempool *package limits*) set by the node (see `-limitancestorcount`, `-limitancestorsize`,
+`-limitdescendantcount`, `-limitdescendantsize`).
+
+## Exemptions
+
+### CPFP Carve Out
+
+**CPFP Carve Out** if a transaction candidate for submission to the
+mempool would cause some mempool entry to exceed its descendant limits, an exemption is made if all
+of the following conditions are met:
+
+1. The candidate transaction is no more than 10,000 virtual bytes.
+
+2. The candidate transaction has an ancestor count of 2 (itself and exactly 1 ancestor).
+
+3. The in-mempool transaction's descendant count, including the candidate transaction, would only
+   exceed the limit by 1.
+
+*Rationale*: this rule was introduced to prevent pinning by domination of a transaction's descendant
+limits in two-party contract protocols such as LN.  Also see the [mailing list
+post](https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-November/016518.html).
+
+This rule was introduced in [PR #15681](https://github.com/bitcoin/bitcoin/pull/15681).
+
+### Single-Conflict RBF Carve Out
+
+When a candidate transaction for submission to the mempool would replace mempool entries, it may
+also decrease the descendant count of other mempool entries. Since ancestor/descendant limits are
+calculated prior to removing the would-be-replaced transactions, they may be overestimated.
+
+An exemption is given for a candidate transaction that would replace mempool transactions and meets
+all of the following conditions:
+
+1. The candidate transaction has exactly 1 directly conflicting transaction.
+
+2. The candidate transaction does not spend any unconfirmed inputs that are not also spent by the
+   directly conflicting transaction.
+
+The following discounts are given to account for the would-be-replaced transaction(s):
+
+1. The descendant count limit is temporarily increased by 1.
+
+2. The descendant size limit temporarily is increased by the virtual size of the to-be-replaced
+   directly conflicting transaction.
diff --git a/doc/policy/mempool-replacements.md b/doc/policy/mempool-replacements.md
new file mode 100644
index 0000000000..3e844f8d7b
--- /dev/null
+++ b/doc/policy/mempool-replacements.md
@@ -0,0 +1,69 @@
+# Mempool Replacements
+
+## Current Replace-by-Fee Policy
+
+A transaction conflicts with an in-mempool transaction ("directly conflicting transaction") if they
+spend one or more of the same inputs. A transaction may conflict with multiple in-mempool
+transactions.
+
+A transaction ("replacement transaction") may replace its directly conflicting transactions and
+their in-mempool descendants (together, "original transactions") if, in addition to passing all
+other consensus and policy rules, each of the following conditions are met:
+
+1. The directly conflicting transactions all signal replaceability explicitly. A transaction is
+   signaling replaceability if any of its inputs have an nSequence number less than (0xffffffff - 1).
+
+   *Rationale*: See [BIP125
+   explanation](https://github.com/bitcoin/bips/blob/master/bip-0125.mediawiki#motivation).
+
+2. The replacement transaction only include an unconfirmed input if that input was included in
+   one of the directly conflicting transactions. An unconfirmed input spends an output from a
+   currently-unconfirmed transaction.
+
+   *Rationale*: When RBF was originally implemented, the mempool did not keep track of
+   ancestor feerates yet. This rule was suggested as a temporary restriction.
+
+3. The replacement transaction pays an absolute fee of at least the sum paid by the original
+   transactions.
+
+   *Rationale*: Only requiring the replacement transaction to have a higher feerate could allow an
+   attacker to bypass node minimum relay feerate requirements and cause the network to repeatedly
+   relay slightly smaller replacement transactions without adding any more fees. Additionally, if
+   any of the original transactions would be included in the next block assembled by an economically
+   rational miner, a replacement policy allowing the replacement transaction to decrease the absolute
+   fees in the next block would be incentive-incompatible.
+
+4. The additional fees (difference between absolute fee paid by the replacement transaction and the
+   sum paid by the original transactions) pays for the replacement transaction's bandwidth at or
+   above the rate set by the node's incremental relay feerate. For example, if the incremental relay
+   feerate is 1 satoshi/vB and the replacement transaction is 500 virtual bytes total, then the
+   replacement pays a fee at least 500 satoshis higher than the sum of the original transactions.
+
+   *Rationale*: Try to prevent DoS attacks where an attacker causes the network to repeatedly relay
+   transactions each paying a tiny additional amount in fees, e.g. just 1 satoshi.
+
+5. The number of original transactions does not exceed 100. More precisely, the sum of all
+   directly conflicting transactions' descendant counts (number of transactions inclusive of itself
+   and its descendants) must not exceed 100; it is possible that this overestimates the true number
+   of original transactions.
+
+   *Rationale*: Try to prevent DoS attacks where an attacker is able to easily occupy and flush out
+   significant portions of the node's mempool using replacements with multiple directly conflicting
+   transactions, each with large descendant sets.
+
+This set of rules is similar but distinct from BIP125.
+
+## History
+
+* Opt-in full replace-by-fee (without inherited signaling) honoured in mempool and mining as of
+  **v0.12.0** ([PR 6871](https://github.com/bitcoin/bitcoin/pull/6871)).
+
+* [BIP125](https://github.com/bitcoin/bips/blob/master/bip-0125.mediawiki) defined based on
+  Bitcoin Core implementation.
+
+* The incremental relay feerate used to calculate the required additional fees is distinct from
+  `minRelayTxFee` and configurable using `-incrementalrelayfee`
+  ([PR #9380](https://github.com/bitcoin/bitcoin/pull/9380)).
+
+* RBF enabled by default in the wallet GUI as of **v0.18.1** ([PR
+  #11605](https://github.com/bitcoin/bitcoin/pull/11605)).