Correctly setting feerate with unconfirmed ancestors

feerate-unconfirmed-ancestors.md

   Mempool #1
+------------------------------------------------------------------------------+
|                                                                              |
|      1 sat/byte                  1 sat/byte                  1 sat/byte      |
|   +-------------+             +-------------+             +-------------+    |
|   |     tx1     |------------>|     tx2     |------------>|     tx3     |    |
|   +-------------+             +-------------+             +-------------+    |
|                                                                              |
+------------------------------------------------------------------------------+

Let's assume that all transactions have the same weight for simplicity.
Ask bitcoind to fundrawtransaction with target feerate = 10 sat/byte.

It currently just does:

   Mempool #2
+-----------------------------------------------------------------------------------------------------------+
|                                                                                                           |
|      1 sat/byte                  1 sat/byte                  1 sat/byte                 10 sat/byte       |
|   +-------------+             +-------------+             +-------------+             +-------------+     |
|   |     tx1     |------------>|     tx2     |------------>|     tx3     |------------>|     tx4     |     |
|   +-------------+             +-------------+             +-------------+             +-------------+     |
|                                                                                                           |
+-----------------------------------------------------------------------------------------------------------+

But we expect the result to look more like:

   Mempool #3
+-----------------------------------------------------------------------------------------------------------+
|                                                                                                           |
|      1 sat/byte                  1 sat/byte                  1 sat/byte                 37 sat/byte       |
|   +-------------+             +-------------+             +-------------+             +-------------+     |
|   |     tx1     |------------>|     tx2     |------------>|     tx3     |------------>|     tx4     |     |
|   +-------------+             +-------------+             +-------------+             +-------------+     |
|                                                                                                           |
+-----------------------------------------------------------------------------------------------------------+

However it's not that simple, imagine we started with something like:

   Mempool #4
+------------------------------------------------------------------------------+
|                                                                              |
|     40 sat/byte                  1 sat/byte                  1 sat/byte      |
|   +-------------+             +-------------+             +-------------+    |
|   |     tx1     |------------>|     tx2     |------------>|     tx3     |    |
|   +-------------+             +-------------+             +-------------+    |
|                                                                              |
+------------------------------------------------------------------------------+

Then if we just aim for a feerate of 10 sat/byte for the whole ancestor package, we'd have:

   Mempool #5
+-----------------------------------------------------------------------------------------------------------+
|                                                                                                           |
|     40 sat/byte                  1 sat/byte                  1 sat/byte                  1 sat/byte       |
|   +-------------+             +-------------+             +-------------+             +-------------+     |
|   |     tx1     |------------>|     tx2     |------------>|     tx3     |------------>|     tx4     |     |
|   +-------------+             +-------------+             +-------------+             +-------------+     |
|                                                                                                           |
+-----------------------------------------------------------------------------------------------------------+

But if tx1 confirms alone (which makes sense because it pays a high feerate), then we're stuck with:

   Mempool #6
+-------------------------------------------------------------------------------+
|                                                                               |
|      1 sat/byte                  1 sat/byte                  1 sat/byte       |
|   +-------------+             +-------------+             +-------------+     |
|   |     tx2     |------------>|     tx3     |------------>|     tx4     |     |
|   +-------------+             +-------------+             +-------------+     |
|                                                                               |
+-------------------------------------------------------------------------------+

So our tx4's effective feerate is 1 sat/byte, whereas we asked for 10 sat/byte!

A very simple rule could be: pay enough fees to bring all ancestors who have a feerate smaller than requested to that requested feerate.
The algorithm would look something like:

let fees = 0
# visit all ancestors, but only once (dedupe shared ancestors)
for ancestor <- ancestors.toSet
  if (ancestor.feerate < target_feerate)
    let missing_fees = (target_feerate - ancestor.feerate) * ancestor.weight
    fees += missing_fees
  else
    # nothing to do

If we start with mempool #1 as described above, this would yield:

   Mempool #3
+-----------------------------------------------------------------------------------------------------------+
|                                                                                                           |
|      1 sat/byte                  1 sat/byte                  1 sat/byte                 37 sat/byte       |
|   +-------------+             +-------------+             +-------------+             +-------------+     |
|   |     tx1     |------------>|     tx2     |------------>|     tx3     |------------>|     tx4     |     |
|   +-------------+             +-------------+             +-------------+             +-------------+     |
|                                                                                                           |
+-----------------------------------------------------------------------------------------------------------+

If we start with mempool #4 as described above, the result would then be:

   Mempool #7
+-----------------------------------------------------------------------------------------------------------+
|                                                                                                           |
|     40 sat/byte                  1 sat/byte                  1 sat/byte                 28 sat/byte       |
|   +-------------+             +-------------+             +-------------+             +-------------+     |
|   |     tx1     |------------>|     tx2     |------------>|     tx3     |------------>|     tx4     |     |
|   +-------------+             +-------------+             +-------------+             +-------------+     |
|                                                                                                           |
+-----------------------------------------------------------------------------------------------------------+

This makes sense, because if tx1 confirms alone, then the feerate of the remaining package would be 10 sat/byte
which is what we wanted.