Date: Fri, 18 Feb 2022 00:32:25 +1000
From: Anthony Towns <aj@erisian.com.au>
To: Matt Corallo <lf-lists@mattcorallo.com>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
 darosior <darosior@protonmail.com>
Message-ID: <20220217143225.GB1429@erisian.com.au>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <9Vw6LCkr2d2uOBanXeIuGxA1fUGGOeV1OHlgBifbmij1Afs0ISjfKK-vmcnRZfBG4GwJhIVLMisjvS_zohS-cW0FkzZaCKa6Mn7VWolznJs=@protonmail.com>
 <8be86b19-04eb-af12-a54c-e1140ac62e3f@mattcorallo.com>
User-Agent: Mutt/1.10.1 (2018-07-13)
Subject: Re: [bitcoin-dev] Thoughts on fee bumping
Precedence: list

On Thu, Feb 10, 2022 at 07:12:16PM -0500, Matt Corallo via bitcoin-dev wrote:
> This is where *all* the complexity comes from. If our goal is to "ensure a
> bump increases a miner's overall revenue" (thus not wasting relay for
> everyone else), then we precisely *do* need
> > Special consideration for "what should be in the next
> > block" and/or the caching of block templates seems like an imposing
> > dependency
> Whether a transaction increases a miner's revenue depends precisely on
> whether the transaction (package) being replaced is in the next block - if
> it is, you care about the absolute fee of the package and its replacement.

On Thu, Feb 10, 2022 at 11:44:38PM +0000, darosior via bitcoin-dev wrote:
> It's not that simple. As a miner, if i have less than 1vMB of transactions in my mempool. I don't want a 10sats/vb transaction paying 100000sats by a 100sats/vb transaction paying only 10000sats.

Is it really true that miners do/should care about that?

If you did this particular example, the miner would be losing 90k sats
in fees, which would be at most 1.44 *millionths* of a percent of the
block reward with the subsidy at 6.25BTC per block, even if there were
no other transactions in the mempool. Even cumulatively, 10sats/vb over
1MB versus 100sats/vb over 10kB is only a 1.44% loss of block revenue.

I suspect the "economically rational" choice would be to happily trade
off that immediate loss against even a small chance of a simpler policy
encouraging higher adoption of bitcoin, _or_ a small chance of more
on-chain activity due to higher adoption of bitcoin protocols like
lightning and thus a lower chance of an empty mempool in future.

If the network has an "empty mempool" (say less than 2MvB-10MvB of
backlog even if you have access to every valid 1+ sat/vB tx on any node
connected to the network), then I don't think you'll generally have txs
with fee rates greater than ~20 sat/vB (ie 20x the minimum fee rate),
which means your maximum loss is about 3% of block revenue, at least
while the block subsidy remains at 6.25BTC/block.

Certainly those percentages can be expected to double every four years as
the block reward halves (assuming we don't also reduce the min relay fee
and block min tx fee), but I think for both miners and network stability,
it'd be better to have the mempool backlog increase over time, which
would both mean there's no/less need to worry about the special case of
the mempool being empty, and give a better incentive for people to pay
higher fees for quicker confirmations.

If we accept that logic (and assuming we had some additional policy
to prevent p2p relay spam due to replacement txs), we could make
the mempool accept policy for replacements just be (something like)
"[package] feerate is greater than max(descendent fee rate)", which
seems like it'd be pretty straightforward to deal with in general?


Thinking about it a little more; I think the decision as to whether
you want to have a "100kvB at 10sat/vb" tx or a conflicting "1kvB at
100sat/vb" tx in your mempool if you're going to take into account
unrelated, lower fee rate txs that are also in the mempool makes block
building "more" of an NP-hard problem and makes the greedy solution
we've currently got much more suboptimal -- if you really want to do that
optimally, I think you have to have a mempool that retains conflicting
txs and runs a dynamic programming solution to pick the best set, rather
than today's simple greedy algorithms both for building the block and
populating the mempool?

For example, if you had two such replacements come through the network,
a miner could want to flip from initially accepting the first replacement,
to unaccepting it:

Initial mempool: two big txs at 100k each, many small transactions at
15s/vB and 1s/vB

 [100kvB at 20s/vB] [850kvB at 15s/vB] [100kvB at 12s/vB] [1000kvB at 1s/vB]
   -> 0.148 BTC for 1MvB (100*20 + 850*15 + 50*1)

Replacement for the 20s/vB tx paying a higher fee rate but lower total
fee; that's worth including:

 [10kvB at 100s/vB] [850kvB at 15s/vB] [100kvB at 12s/vB [1000kvB at 1s/vB]
   -> 0.1499 BTC for 1MvB (10*100 + 850*15 + 100*12 + 40*1)

Later, replacement for the 12s/vB tx comes in, also paying higher fee
rate but lower total fee. Worth including, but only if you revert the
original replacement:

 [100kvB at 20s/vB] [50kvB at 20s/vB] [850kvB at 15s/vB] [1000kvB at 1s/vB]
   -> 0.16 BTC for 1MvB (150*20 + 850*15)

 [10kvB at 100s/vB] [50kvB at 20s/vB] [850kvB at 15s/vB] [1000kvB at 1s/vB]
   -> 0.1484 BTC for 1MvB (10*100 + 50*20 + 850*15 + 90*1)

Algorithms/mempool policies you might have, and their results with
this example:

 * current RBF rules: reject both replacements because they don't
   increase the absolute fee, thus get the minimum block fees of
   0.148 BTC

 * reject RBF unless it increases the fee rate, and get 0.1484 BTC in
   fees

 * reject RBF if it's lower fee rate or immediately decreases the block
   reward: so, accept the first replacement, but reject the second,
   getting 0.1499 BTC

 * only discard a conflicting tx when it pays both a lower fee rate and
   lower absolute fees, and choose amongst conflicting txs optimally
   via some complicated tx allocation algorithm when generating a block,
   and get 0.16 BTC

In this example, those techniques give 92.5%, 92.75%, 93.69% and 100% of
total possible fees you could collect; and 99.813%, 99.819%, 99.84% and
100% of the total possible block reward at 6.25BTC/block.

Is there a plausible example where the difference isn't that marginal?
Seems like the simplest solution of just checking the (package/descendent)
fee rate increases works well enough here at least.

If 90kvB of unrelated txs at 14s/vB were then added to the mempool, then
replacing both txs becomes (just barely) optimal, meaning the smartest
possible algorithm and the dumbest one of just considering the fee rate
produce the same result, while the others are worse:

 [10kvB at 100s/vB] [50kvB at 20s/vB] [850kvB at 15s/vB] [90kvB at 14s/vB]
   -> 0.1601 BTC for 1MvB
   (accepting both)

 [100kvB at 20s/vB] [50kvB at 20s/vB] [850kvB at 15s/vB] [90kvB at 14s/vB]
   -> 0.1575 BTC for 1MvB 
   (accepting only the second replacement)

 [10kvB at 100s/vB] [850kvB at 15s/vB] [90kvB at 14s/vB] [100kvB at 12s/vB]
   -> 0.1551 BTC for 1MvB
   (first replacement only, optimal tx selection: 10*100, 850*15, 50*14, 100*12)

 [100kvB at 20s/vB] [850kvB at 15s/vB] [90kvB at 14s/vB] [100kvB at 12s/vB]
   -> 0.1545 BTC for 1MvB
   (accepting neither replacement)

 [10kvB at 100s/vB] [850kvB at 15s/vB] [90kvB at 14s/vB] [100kvB at 12s/vB]
   -> 0.1506 BTC for 1MvB 
   (first replacement only, greedy tx selection: 10*100, 850*15, 90*14, 50*1)

Always accepting (package/descendent) fee rate increases removes the
possibility of pinning entirely, I think -- you still have the problem
where someone else might get a conflicting transaction confirmed first,
but they can't get a conflicting tx stuck in the mempool without
confirming if you're willing to pay enough to get it confirmed.


Note that if we did have this policy, you could abuse it to cheaply drain
people's mempools: if there was a 300MB backlog, you could publish 2980
100kB txs paying a fee rate just below the next block fee, meaning you'd
kick out the previous backlog and your transactions take up all but the
top 2MB of the mempool; if you then replace them all with perhaps 2980
100B txs paying a slightly higher fee rate, the default mempool will be
left with only 2.3MB, at an ultimate cost to you of only about 30% of a
block in fees, and you could then fill the mempool back up by spamming
300MB of ultra low fee rate txs.

I think spam prevention at the outbound relay level isn't enough to
prevent that: an attacker could contact every public node and relay the
txs directly, clearing out the mempool of most public nodes directly. So
you'd want some sort of spam prevention on inbound txs too?

So I think you'd need to carefully think about relay spam before making
this sort of change.  Also, if we had tx rebroadcast implemented then
having just a few nodes with large mempools might allow the network to
recover from this situation automatically.

Cheers,
aj