Changing the way that RBF works is an excellent idea. Bitcoin is overdue
for revisiting these rules. Thanks to @glowzo et al for kicking off the
discussion.

I've been thinking about RBF for a very long time[1], and it's been fun to
see other people's thoughts on the topics. Here's my current thinking about
this, and proposal for how we should update the rules.

### Changing the Rules? How to Change Them
Regarding how to change them, Bram and aj are right -- we should move to a
model where transaction relay candidates are evaluated on their net
increase in fees per byte paid, and remove the requirement that the gross
fee of the preceding transaction is met or exceeded.

Our current ruleset is over complicated because it attempts to solve two
problems at once: the miner's best interests (highest possible fee take)
and relay policy.

I believe this is a mistake and the mempool should change its goals.
Instead, the mempool relay design for RBFs should be built around 1)
increasing the the per-byte fees paid of a transaction and 2) providing a
simple policy for applications building on top of bitcoin, such that
knowledge of the mempool is not required for successfully issuing
relay-able RBF transactions.

(A simple "must increase the per-byte feerate" heuristic for RBF relay
candidates has the nice benefit of being easy to program to on the
application side, and only requires knowledge of the previous candidate
transaction, not the entire mempool or any previous tx's relative position
within it.)

Finally, when blockspace is competitive , this simple policy ensures that
the per-byte value of every subsequent relayed transaction increases the
per-byte value of pending bytes for the next block. This provides a measure
of DoS protection and ensures that every relayed byte is more valuable (to
the miner/network) than the last.

*The only time that RBF is critical for relay is during full block periods
-- if there's not enough transactions to fill a block, using RBF to ensure
that a transaction is mined in a timely manner is moot. As such, RBF rules
should not be concerned with low-block environments.

### Mempools and Relay
The mempool currently serves two masters: the profit motive of the miner
and the relay motive of a utxo holder. It is in the interest of a user to
send the miner a high per-byte tx, such that it might end up in the next
block. It is in the miner's best interest to include the highest per-byte
set of transactions in their block template.

There is some conflation here in the current RBF policies between what is
in the mempool and what is considered a candidate for the block template.
If a miner has already included a more profitable package of txs into their
block template than a more valuable per-byte tx that the network has
relayed to them, it should be the responsibility of the block template
constructor to reject the new proposed tx, not the nodes relaying the
transaction to said miner.

This is a policy that the miner can (and should) implement at the level of
the template construction, however.

Is it the responsibility of the mempool to provide the best "historical"
block opportunity for a miner (e.g. the highest paying block given all txs
it's ever seen)? I would say no, that the ability of a utxo owner to
re-state the spend condition of a pending transaction is more important,
from a use-case perspective, and that the mempool should concern itself
solely with relaying increasingly more profitable bytes to miners. Let the
miners concern themselves with deciding what the best policy for their own
block construction is, and the mempool with relaying the highest value
bytes for the network. Net-net, this will benefit everyone as it becomes
easier for users to re-submit txs with increasingly greater feerates,
creating more active competition for available blockspace as more
applications are able to include it as a feature (and it works, reliable,
as a relay mechanism).

### Packages and RBF
Packages make the increasing per-byte rule less of a guarantee that
increasing the per-byte value of a single transaction will net a given
miner more fees than including the entire package.

Let's decompose this a bit. It's helpful to think of tx packages as
'composable txs'. Basically when you consider a 'package' it is actually a
large tx with sub-components, the individual txs. As a 'composed tx', you
can calculate the per-byte feerate of the entire set. This is the number
that you, as someone issuing an RBF, would need to beat in order to move
your tx up in the pending block queue.

RBF, however, is a transaction level policy: it allows you to replace any
*one* component of a package, or tree, with the side effect of possibly
invalidating other candidate txs. If the 'composed tx' (aka package) had a
net per-byte value that was higher than the new replacement transaction
because of a leaf tx that had an outsized per-byte feerate, then it would
be more profitable for the miner to have mined the entire package rather
than the replacement.

This edge case complicates the picture for the miner. Considered from the
viewpoint of the user issuing the RBF, however, it is far simpler. In the
ideal case, a person is issuing an RBF because the previous tx tree, even
with its high fee sub-component, was not a candidate for the next block.
And, in some cases, increasing the sub-component's per-byte feerate will
not achieve the goal of moving the tx any closer to being mined. It's only
by increasing the feerate above the present feerate of the candidate plus
desendents (tx package) that the transaction will advance in the queue.

While not uncomplicated, this is a simple enough metric for a wallet to
track, and does not require any knowledge of the current mempool to
effectively surpass. It's the wallet's responsibility to track this though;
failure to take descendants into account when deciding on the next per-byte
feerate for an RBF *will* mean that your RBF will be ineffective at
achieving the goal of getting your UTXO spent. Any wallet is incentivized
to always provide a higher per-byte feerate than the 'composed tx' (tx and
its descendants), so as to ensure an actual improvement in the unconfirmed
transaction's position in the block queue, so to speak.

Note that the v2 protocol for channel opens in lightning uses an RBF
negotiation that adheres basically to these rules (ea transaction must have
a strictly greater per-byte feerate).

We enforce a rate of 65/64th as the required increase in feerate for each
subsequent channel open transaction.

https://github.com/lightning/bolts/pull/851/files#diff-ed04ca2c673fd6aabde69389511fa9ee60cb44d6b2ef6c88b549ffaa753d6afeR1154

### RBF and DoS

Admittedly, changing these rules will increase the number of times that any
UTXO is eligible to be retransmitted (relayed) via the bitcoin node
network. Strictly increasing the per-byte feerate however ensures that this
re-relay is increasingly more expensive to the UTXO owner, however.


### in exitus
These are the things I've been thinking about with regards to RBF. I hope
they can help to highlight the challenges in the RBF design space a bit
more clearly, as well as spelling out the case for using a simple heuristic
such as "solely increasing per-byte feerate" as a good candidate for the
revised RBF policy.

~niftynei

[1]
https://basicbitch.software/posts/2018-12-27-Explaining-Replace-By-Fee.html