Bump unconfirmed ancestor transactions to target feerate (wallet)


Host: glozow  -  PR author: Xekyo

The PR branch HEAD was 898ad9d590 at the time of this review club meeting.


  • The wallet funds a transaction by selecting inputs to cover its payment amount(s) and the fee at the user’s target feerate. This process is known as coin selection, which we have discussed in previous review clubs #22009, #17526 and #17331.

    • Notably, each candidate coin is considered using an “effective value,” introduced in PR #17331. This deducts the cost to spend this input at the target feerate from its nValue.
  • Since PR #7600, the BlockAssembler algorithm has used ancestor feerate, rather than individual feerate, to select transactions for inclusion in blocks. This strategy also enables users to fee-bump transactions using Child Pays for Parent (CPFP). We have discussed the BlockAssembler implementation in a previous review club meeting.

  • On the flip side of CPFP, a transaction’s “effective” feerate depends on the UTXOs used to fund it: if unconfirmed UTXOs are used, since the transaction cannot be mined without its ancestors, its “effective” feerate may decrease. Even while not trying to boost an unconfirmed transaction using CPFP, if the wallet funds a transaction using unconfirmed UTXOs with feerates lower than the target feerate, it may underestimate the amount of fees to put on this transaction. This issue has been an open problem for years; see #9645, #9864, and #15553.

  • Goal: when funding a transaction using unconfirmed inputs, in addition to funding the payment(s) and this transaction’s fee, also include the fees necessary to bump those unconfirmed transactions to the target feerate.

  • One naive solution would be to select all the inputs, and then calculate the cost of bumping unconfirmed ancestors and add that to the fees. However, if the selected inputs cannot cover the cost of ancestor fees, the selection process needs to be repeated; this strategy would (re)introduce a looped coin selection algorithm and make changeless solutions much less common.

  • Consider another solution which updates the “effective value” of a coin, reducing it by the fee necessary to bump its ancestor set to the target feerate: effective_value = nValue - cost_to_spend - max(0, target_feerate * ancestor_size - ancestor_fees). For example, if the target feerate is 20sat/vB, the UTXO has type P2WPKH and value 100ksat, and transaction’s ancestor fee and vsize are 1200sat and 600vB respectively, the coin’s effective value would be 100000sat - (20sat/vB * 68vB) - (20sat/vB * 600vB - 1200sat) = 87840sat.

  • However, this problem is much more complicated than simply using the ancestor size and fees of unconfirmed UTXOs:

    • Multiple UTXOs may come from the same transaction or share the same ancestry. We don’t need to bump those transactions more than once.

    • An ancestor’s feerate may be higher than the target feerate.

    • An ancestor may have a low feerate, but be already fee-bumped by another transaction in the mempool.

    • If the transaction replaces existing transactions in the mempool, one or multiple transactions may be evicted. After these evictions, some transactions may now need bumping, and others may no longer need bumping. For example, we may be replacing a previous CPFP child with an even higher feerate child.

  • PR #26152 adds MiniMiner, a “mini” version of the block assembly algorithm designed to calculate the cost to bump an unconfirmed UTXO to a target feerate. It uses MiniMiner to include the fees to bump any unconfirmed ancestors when funding a transaction.

  • MiniMiner operates on a limited set of mempool entries rather than the entire mempool, and does not care about consensus rules such as block size and sigop limits. The limited set includes the “clusters” of each unconfirmed transaction from which the wallet might spend a UTXO from. A cluster includes all mempool entries “connected” to a transaction. This includes parents and children, ancestors and descendants, as well as “siblings” (a transaction that shares a parent) and “coparents,” (a transaction that shares a child), etc.

  • The PR adds a CTxMemPool::CalculateCluster function to calculate a set of transactions’ clusters. It uses the epoch-based traversal strategy described in PR #17268 and first introduced in PR #17925.

  • MiniMiner provides two functions: CalculateBumpFees() provides the bump fee for each UTXO independently, ignoring any cases where there are shared ancestries. This function is intended for calculating effective values in AvailableCoins, when it is unknown exactly which coins might be spent. CalculateTotalBumpFees() provides the bump fee for a set of UTXOs to be spent together, taking into consideration when UTXOs have shared ancestry. It is intended for calculating the final fee to put on the transaction.


  1. Did you review the PR? Concept ACK, approach ACK, tested ACK, or NACK?

  2. What issue does this PR solve?

  3. In CalculateCluster, what does a transaction’s “cluster” consist of?

  4. Why does the MiniMiner require an entire cluster? Why can’t it just use the union of each transaction’s ancestor sets?

  5. We know that a transaction’s individual feerate is not necessarily indicative of how a miner will prioritize it. That is, if transaction X and Y have feerates fX and fY, fX > fY doesn’t necessarily imply that X will be selected sooner than Y. If two independent mempool transactions X and Y have ancestor feerates gX and gY where gX > gY, which of the following are possible? (Here, “independent” means that their respective clusters have no overlapping transactions).

    • a. X is selected sooner than Y
    • b. X is selected later than Y
  6. The MiniMiner constructor accepts a mempool reference and a list of outpoints the wallet might be interested in spending. Given an outpoint, it may be one of four possible types:

    • a confirmed UTXO
    • a UTXO created by a mempool transaction and has not been spent yet
    • a UTXO created by a mempool transaction and has already been spent by another mempool transaction
    • a UTXO that does not exist in mempool or chainstate (perhaps not yet submitted to mempool)

    How does the MiniMiner constructor detect and handle each case?

  7. MiniMiner builds a descendant_set_by_txid cache, but not an ancestor_set_by_txid cache. Instead, it calculates ancestor sets on the fly. Do you think this approach makes sense? Why or why not?

  8. At a high level, describe how MiniMiner::CalculateBumpFees() works. Why can’t we just use the ancestor feerate of each transaction?

  9. Can CalculateBumpFees() overestimate, underestimate, both, or neither? By how much?

  10. What are the similarities and differences in implementation between CalculateBumpFees and CalculateTotalBumpFees?

  11. One potential approach for constructing the block is to define a custom ancestor score comparator for MockMempoolEntry (or even just reuse CompareTxMemPoolEntryByAncestorFee from txmempool like the BlockAssembler does), and then iterate through a list of entries sorted by ancestor score. Why would this approach work for BlockAssembler but not for MiniMiner?

  12. This functionality is only used by the wallet. Instead of adding CalculateBumpFees to the chain interface, should we just add it as a utility function in the wallet?

  13. Describe the approach taken in the “Bump unconfirmed parent txs to target feerate” commit.

  14. What test cases are included in wallet_spend_unconfirmed.py added in the same commit? Can you think of any other test cases to add?

  15. Two coin selection results may require different fees for bumping ancestors. How does the wallet choose which one to use? (Hint: can you identify how bump fees come into play in GetSelectionWaste())?

  16. How does the PR handle spending unconfirmed UTXOs with overlapping ancestry? (Hint: what does the code here do)?

Meeting Log

  117:00 <glozow> #startmeeting
  217:00 <glozow> Hi everyone! Welcome to Bitcoin Core PR review club!
  317:00 <kouloumos> hi!
  417:00 <hernanmarino_> Hi Gloria !
  517:00 <stickies-v> hi!
  617:00 <ishaanam[m]> hi
  717:00 <josie[m]> hi
  817:00 <hernanmarino_> and everyone :)
  917:00 <emzy> hi
 1017:00 <BlueMoon> Hello!
 1117:01 <glozow> hello friends! ^_^
 1217:01 <pablomartin> Hello!
 1317:01 <lightlike> Hi
 1417:01 <yashraj> hi
 1517:01 <brunoerg> hu
 1617:01 <glozow> We're looking at #26152 today, notes here: https://bitcoincore.reviews/26152
 1717:01 <LarryRuane> hi
 1817:01 <brunoerg> hi*
 1917:01 <glozow> Have y'all had a chance to look at the notes and/or review the PR? how about a y/n?
 2017:01 <b_101> hi all
 2117:02 <stickies-v> 0.5y - a lot to cover!
 2217:02 <LarryRuane> notes y, review 0.5y
 2317:02 <hernanmarino_> Just did a light reading of the notes and first questions a couple of hours ago, I will thoroughly revier the PR later
 2417:02 <emzy> n
 2517:02 <ishaanam[m]> y, I looked at the notes, reviewed the wallet part of the pr
 2617:02 <pablomartin> y for the notes, pending review
 2717:02 <yashraj> y, notes
 2817:03 <glozow> yes there's a lot to cover, but hopefully interesting enough to keep us going
 2917:03 <b_101> y/n
 3017:03 <glozow> Let's start with the first question: What issue does this PR address?
 3117:03 <kouloumos> notes y, review 0.1y, didn't got out of the mempool rabbit hole yet
 3217:04 <hernanmarino_> It fixes an overestimation in the effective value of unconfirmed UTXOs by the fees necessary to bump their ancestor transactions.
 3317:04 <glozow> Right, I presume the MiniMiner implementation will be the most difficult to review (?)
 3417:04 <LarryRuane> The Core wallet may construct a transaction with a lower fee than required by the requested feerate. This transaction won't be mined as quickly as expected (given the requested feerate).
 3517:04 <hernanmarino_> I quitted when I got to the MiniMiner :))
 3617:05 <LarryRuane> Positive feedback loop: The resulting larger number of unconfirmed UTXOs coin selection has available to it, the more likely it will choose these UTXOs, creating even more too-low fee unconfirmed transactions
 3717:05 <stickies-v> the wallet fee estimation doesn't take into account that it also has to pay for all unconfirmed ancestors with a lower feerate than the target
 3817:06 <glozow> LarryRuane: hernanmarino_: stickies-v: yes, thank you!
 3917:06 <ishaanam[m]> Would it be correct to describe this PR as fixing an inconsistency between what a miner sees as our transaction's feerate vs what the wallet sees as the transaction's feerate?
 4017:07 <LarryRuane> That positive feedback loop idea came from https://github.com/bitcoin/bitcoin/issues/15553#issue-418076345 "This can contribute to long unconfirmed chains forming ..."
 4117:08 <LarryRuane> ishaanam[m]: +1 (IIUC)
 4217:08 <glozow> ishaanam[m]: yes, i definitely think so! CPFP has 2 sides to it: it lets us fee-bump tx ancestors, but also means we *must* pay for them. we've basically only implemented the former to do it intentionally
 4317:08 <stickies-v> that's interesting, I hadn't considered the feedback loop, thanks LarryRuane - makes sense!
 4417:09 <glozow> Before we jump in, would anybody like to give us an overview of the approach taken in this PR?
 4517:09 <Murch> LarryRuane: Not necessarily. We will only consider unconfirmed UTXOs in later backoff attempts on Coin Selection.
 4617:10 <LarryRuane> Murch: ah, thank you, that actually answers a question I was just about to ask: From notes: "Goal: when funding a transaction using unconfirmed inputs...also include the fees necessary to bump " -- Would this be a reason to avoid using unconfirmed outputs?
 4717:10 <LarryRuane> So we do prioritize confirmed UTXOs in coin selection (IIUC)
 4817:10 <hernanmarino_> glozow : I think Murch will be able to answer that :D
 4917:11 <glozow> Yes, we already *only* try to use unconfirmed inputs to fund the transaction if we can't cover it using confirmed ones.
 5017:11 <Murch> In the first round of coin selection attempts, we only use UTXOs that have six confirmations on UTXOs received from external wallets, and one confirmation on UTXOs sent to ourselves.
 5117:11 <Murch> hernanmarino_: Sure, but that's not the point of it :D
 5217:11 <LarryRuane> glozow: Murch: also we only use _change_ outputs (change to ourselves)?
 5317:11 <hernanmarino_> :D
 5417:11 <guest> at a very high level, this PR tries to accurately determine the bump fee by organizing them into clusters and then passes them to the MiniMiner to see how the transactions would be ranked
 5517:12 <glozow> LarryRuane: here is the code Murch is referring to https://github.com/bitcoin/bitcoin/blob/38d06e1561013f4ca845fd5ba6ffcc64de67f9c0/src/wallet/spend.cpp#L617-L663
 5617:12 <stickies-v> we simulate the mining process to calculate how much we'd have to pay to bump up an outpoint's ancestor feerate to the target feerate, and use that to decrease an outpoint's effective value?
 5717:12 <Murch> LarryRuane: Correct, assuming that you haven't enabled “allowUnsafe”
 5817:13 <Murch> guest: That's not quite it. Consider what the wallet knows about its UTXOs and what information it might be missing
 5917:13 <LarryRuane> Murch: thanks, seems like one reason you would want to "allowUnsafe" is if you're making a refund transactions... someone sent you a payment, but now you want to give a refund, you SHOULD use that payment's output, or else the payment may get replaced and you've issued the refund!
 6017:13 <Murch> LarryRuane: Right, but in that case you will also explicitly pick a specific UTXO, in which case the automatic filtering of your UTXO pool does not apply
 6117:14 <LarryRuane> Murch: oh i see, that makes sense
 6217:14 <glozow> stickies-v: exactly. the first half of the PR implements a "bump fee" calculator. It's implemented using the same algorithm as the miner (we'll get to why that is later). The second half adds wallet functionality, deducting the bump fees from the effective values, and adding another mini miner function to calculate the total bump fees once the exact coins have been selected
 6317:14 <LarryRuane> "simulate the mining process" -- but without the Pow haha
 6417:15 <LarryRuane> the code in this PR is really interesting, it must have been a blast to write, @murch!
 6517:15 <stickies-v> LarryRuane: yeah which is why I actually proposed calling it `MiniBlockAssembler` instead of `MiniMiner` hah but now I'm phrasing it like that myself
 6617:15 <glozow> LarryRuane: Ah right good call - psa when we refer to the "mining algorithm" here we're talking about the block template creation algorithm. The other, more famous algorithm, is not very interesting.
 6717:15 <LarryRuane> stickies-v: good point!
 6817:16 <glozow> *not very interesting in this context
 6917:16 <LarryRuane> hey if not too much sidetracking, isn't the getblocktemplate RPC out of favor these days?
 7017:16 <LarryRuane> thought i'd read that somewhere
 7117:17 <glozow> I'll move on to the implementation questions.
 7217:17 <glozow> In `CalculateCluster`, what does a transaction’s “cluster” consist of? (code here: https://github.com/bitcoin-core-review-club/bitcoin/commit/995107782a1a512811d54f7abf29249f351a7cbf#diff-c065d4cd2398ad0dbcef393c5dfc53f465bf44723348892395fffd2fb3bac522R1218)
 7317:17 <LarryRuane> given a set (vector) of transactions, return deduped vector of all connected transactions (ancestors and decendants recursively)
 7417:17 <hernanmarino_> It consists of all in-mempool ancestors of a set of transactions not already in the mempool (considering ancestor and descendant limits)
 7517:17 <LarryRuane> the list won't include the original transactions, except those that are connected to other transactions in the cluster
 7617:19 <LarryRuane> can i ask a general mempool question (feel free to ignore): why does so much of the code use `mapTx` iterators, rather than just some kind of direct reference?
 7717:19 <Murch> LarryRuane: Thanks, it is a very interesting project. A lot of the code was created by glozow, and we also had a lot of input from achow101
 7817:20 <stickies-v> LarryRuane: "except those that are connected to other transactions in the cluster" the transactions specified in `txids` can never be included in the cluster, I think
 7917:21 <stickies-v> because in the beginning of the function we visit them all with `for (const auto& it : cluster) { visited(it); }`
 8017:21 <stickies-v> oh wait. it's opposite. they're always included haha. whoops
 8117:21 <glozow> Er, I'm pretty sure the cluster includes those specified in `txids`? in the beginning we also initialize `cluster{GetIterVec(txids)}`
 8217:21 <LarryRuane> stickies-v: yes but let's say we're spending from two outputs of the same ancestor transaction? would that do it?
 8317:22 <Murch> Mh, maybe I'm misunderstanding you, but the cluster is the set of all transactions that are either ancestors or descendants to any other transactions in the cluster
 8417:22 <josibake> stickies-v: this was something i was a little fuzzy on .. they are already in the cluster and then we visit all of them so that they don't get added again?
 8517:22 <josibake> at least from my understanding
 8617:22 <josibake> but we initialize cluster from the list of txids and we don't remove anything, so the original txids would also be in the cluster
 8717:22 <LarryRuane> glozow: you're right, thanks, i had missed that
 8817:23 <stickies-v> yep josibake glozow you're right
 8917:23 <glozow> Murch: you are correct. LarryRuane and hernanmarino_'s answers were part of the way there so I was waiting for more answers :P
 9017:23 <glozow> Yes, a cluster is every single "connected" transaction. So a "sibling" i.e. a child of your parent, who is neither your ancestor nor your descendant, would be part of your cluster.
 9117:24 <Murch> It's the maximal strongly connected component of the initial transactions
 9217:24 <LarryRuane> `CalculateCluster()` is really interesting, I had written python code months ago that does almost exactly the same thing (while trying to understand package relay)
 9317:25 <josibake> something that occurred to me, what happens if a list of txids is passed to calculate cluster where the txids themselves create distinct clusters?
 9417:25 <lightlike> did you introduce the MiniMiner because adjusting the actual miner for this use case would be too complicated? I think the algorithm is kind of implemented twice now (even with some adjustments).
 9517:25 <josibake> or perhaps a better question, who is deciding which txids to pass to CalculateCluster? the wallet?
 9617:25 <LarryRuane> josibake: I think that's perfectly okay (and normal), you just get the union
 9717:26 <LarryRuane> lightlike: is the actual miner conditionally compiled in? (i don't recall)
 9817:27 <Murch> Well, in that case, the approach of this PR is owed that the wallet doesn't know about unconfirmed transactions unless they pertain to itself. So when we spend unconfirmed UTXOs we must get more information from the mempool. It turned out that we were basically recreating block building on the wallet side then to cover all of the possible constellations of transaction relations, so we instead used the existing data structures in mempool to extract
 9917:27 <Murch> only the result of the graph analysis.
10017:27 <Murch> josibake: The wallet asks for all of the transactions that created unconfirmed UTXOs in its pool
10117:28 <hernanmarino_> Murch : that's interesting
10217:28 <glozow> lightlike: good question, there's a few reasons: We only need to operate on a cluster and not the entire mempool + don't need to apply any of the checks that `BlockAssembler` does. I also got a suggestion to do this without holding the mempool lock. We'd also need to change the block assembler to be tracking bump fees rather than building the block template - the amount of refactoring necessary was equivalent to rewriting.
10317:28 <josibake> Murch: ah, got it! that makes more sense
10417:29 <glozow> I can understand why the duplication of the algo could be considered an inferior approach, feedback welcome of course
10517:29 <Murch> Also, we need to stop assembling the block at a specific feerate which is a different mechanism than running out of space
10617:30 <glozow> Yes, though I must admit that the `BlockAssembler::blockMinFeeRate` also achieves this
10717:31 <josibake> glozow: i think the reasons specified make a lot of sense. if anything, sounds like an opportunity to pull the algo out into it's own function and have both MiniMiner and and BlockAssembler call it? but haven't looked at block assembler to know if that's feasible/sane
10817:31 <glozow> it's a good way to compare the algos we can fuzz them pretty easily given they have this in common
10917:31 <lightlike> glozow: ah, thanks. Don't know the BlockAssembler enough to have an opinion, just wanted to understand the reasons.
11017:31 <LarryRuane> josibake: I like that idea (pull the common code, if there's a significant amount of it) out into a separate function or class, then call from both places
11117:32 <LarryRuane> then that function can be unit-tested too very easily
11217:33 <glozow> josibake: yeah, considered that too, but a "general algorithm" is pretty much the only thing they have in common at this point. For instance, `BlockAssembler` builds a `mapModifiedTx` to "make changes" to mapTx, while `MiniMiner` operates directly on copies of the mempool entries. One builds a block template and the other builds a map of outpoint to bumpfee.
11317:34 <LarryRuane> glozow: seems like you made a good engineering decision
11417:35 <LarryRuane> (er, you and murch I guess)
11517:35 <josibake> regarding CalcCluster (and sorry if this was asked already, had some issues with my irc client), but why the `GetIterVec` function?
11617:36 <LarryRuane> josibake: you mean why not make it inline?
11717:36 <glozow> josibake: good question, brings us to the Epoch Mempool topic. A vector is much smaller than a set. we have a wider effort to switch, though it's taken years. I felt that new code should try to use epochs and vectors instead of setEntries
11817:36 <glozow> oh! is it LarryRuane's question?
11917:37 <LarryRuane> glozow: oh that's good to know! wasn't aware of that effort
12017:38 <LarryRuane> epochs == really cool idea
12117:38 <josibake> glozow: thanks, that makes more sense. i think i need to dig in more as to what a txiter is before i fully grok whats going on
12217:38 <josibake> LarryRuane: not really concerned about inline or not, just curious why we were starting with a list of txids and then converting it to a vec of txiter's
12317:38 <glozow> haha yes `txiter` is an alias for a very very long type
12417:39 <glozow> txiter def: https://github.com/bitcoin/bitcoin/blob/38d06e1561013f4ca845fd5ba6ffcc64de67f9c0/src/txmempool.h#L406
12517:39 <glozow> indexed_transaction_set: https://github.com/bitcoin/bitcoin/blob/38d06e1561013f4ca845fd5ba6ffcc64de67f9c0/src/txmempool.h#L374
12617:39 <josibake> im guessing txiters are specific to epochs then? (also , read a little on the epoch pr's as background, very cool idea)
12717:40 <glozow> Ah no, txiters are just mapTx iterators. The entry's `m_epoch` can change without the txiter changing
12817:40 <glozow> Continuing with the CalculateCluster commit. A transaction's cluster is both necessary and sufficient for calculating its bump fees. Let's show "sufficient" first: why do we only need the cluster and not the whole mempool to calculate what a transaction's mining "priority" will be?
12917:41 <glozow> And why does the `MiniMiner` require an entire cluster? Why can’t it just use the union of each transaction’s ancestor sets?
13017:41 <pablomartin> josibake: could you pls share that epoch pr?
13117:42 <glozow> Epoch Mempool: https://github.com/bitcoin/bitcoin/pull/17925 and https://github.com/bitcoin/bitcoin/pull/17268
13217:42 <glozow> (would people be interested in an epoch mempool review club?
13317:42 <LarryRuane> first question, I don't think we care what the mining priority is, just that this newly-created tx has the requested feerate
13417:42 <glozow> )
13517:42 <pablomartin> glozow: as we discussed before, we need descendant and even siblings... ?
13617:42 <Murch> Hint: The test-cases might provide some ideas
13717:42 <lightlike> because some of the ancestors may already have been paid for by some of their other descendants - so we don't have to do it with our transaction.
13817:42 <josibake> re: sufficient, a transactions mining priority is determined by it's ancestor fee, right? so we dont need to know anything about a tx except it's full ancestory
13917:42 <stickies-v> josibake: I'll try and explain my understanding briefly. CTxMemPoolEntry wraps a CTransaction and adds some mempool-specific stats to it. CTXMemPool stores CTxMemPoolEntry objects in a boost multi-index (`mapTx`) so we can quickly query the mempool in different ways. `txiter` is a shorthand for boost iterators that point to CTxMemPoolEntry objects in `mapTx`
14017:43 <stickies-v> We use `txiter` for internal consistency (e.g. ensuring multiindex stays up to date, and that entries are still in mempool). I hope my explanation didn't contain too many inaccuraries - again, just my understanding!
14117:43 <LarryRuane> lightlike: +1, Because an ancestor (A) may have a CPFP child that is already increasing A's effective feerate, so we don't need to "help" A
14217:43 <Murch> pablomartin: Why though? What mistake might we make if we don't consider them?
14317:43 <josibake> well, i take that back. because the cluster includes more than strictly the ancestory for a single tx
14417:44 <Murch> josibake: Njet. What if your sibling has bumped the parent already to a higher package feerate than what you're aiming for?
14517:44 <josibake> stickies-v: thanks, that helps!
14617:44 <glozow> pablomartin: lightlike: yes exactly. to find out how much to bump, we need to know whether something is already bumped.
14717:44 <Murch> There is also another issue that hasn't been mentioned yet
14817:44 <Murch> Or only indirectly, I guess
14917:45 <glozow> and josibake: yes that's the general idea. we don't need anything that cannot impact these transactions during block assembly
15017:45 <LarryRuane> Murch: a little more context please? issue with not consideringly only ancestors?
15117:46 <Murch> You can't just sum up all ancestors and take their summed up fee and weight, because some of the ancestors might have a higher effective feerate than what you're aiming for by themselves and will not actually be part of your package
15217:46 — lightlike we just have to make sure that we don't pay for something that has low-fee descendants (that does the opposite of bumping them). But I guess the BlockAssembly algorithm takes care of that?
15317:46 <Murch> Children pay for parents, but parents cannot pay for children
15417:47 <LarryRuane> that's mean ... oh i forgot to mention at the start of the meeting, in the notes, the effective_value expression should use max, not min (correct?)
15517:47 <pablomartin> Murch: true, I agree (only children pay for parents -> direction)
15617:47 <Murch> So, if your grandparent tx has a higher feerate, you may only need to bump the parent, but if you had summed up the two, you would underestimate the bump fee
15717:47 <ishaanam[m]> LarryRuane: yes
15817:47 <glozow> LarryRuane: yes, its should be max. ishaanam also pointed this out to me. I'll fix it when I add the logs later today. Thanks you both for catching!
15917:48 <pablomartin> Murch: so you need to check if sibling were already bumping common parents...
16017:48 <lightlike> sure - but the low-fee children would be included in the Cluster at first, and then discarded later, right?
16117:48 <Murch> however, if your parent tx has a higher feerate than what you're aiming for, it might still have a lower ancestor feerate, because it's bumping a grandparent.—In that case, you do have to bump both the parent and grandparent
16217:49 <LarryRuane> Murch: that's mind-bending! cool tho
16317:50 <LarryRuane> and just to be clear.. when we say "bump" we just mean reduce the EV of the output that we're considering spending
16417:50 <Murch> So, you can't just skip over txs that have a higher individual feerate, but you can also not just take their summed up fees and weights. You actually have to traverse the cluster in order to find out which ancestors, descendants and cousins are relevant
16517:50 <glozow> Yes, so there really isn't a quick and easy way of calculating the bump fees just by looking at aggregate feerates etc. running the mining algorithm on the cluster is the easiest way imo, even if it seems like a lot
16617:51 <Murch> LarryRuane: Yes, reduce the effective value of the UTXO in order to pay a higher fee when it's used that will go towards elevating ancestors to the target feerate
16717:52 <Murch> lightlike: Yeah, we first collect siblings, niblings, cousins, etc., but if they do not bump some of the shared ancestry, we can disregard them for the bumpfee calculation
16817:52 <Murch> pablomartin: Yep!
16917:53 <glozow> To hammer this home: If two mempool transactions X and Y have ancestor feerates gX and gY where gX > gY, which of the following are possible?
17017:53 <glozow> (a) X is selected sooner than Y
17117:53 <glozow> (b) X is selected later than Y
17217:53 <LarryRuane> sorry I didn't really look yet, but are there tests, I could imagine setting up these weird graphs and then making sure the algorithm does the right thing (right as determined manually)
17317:53 <LarryRuane> glozow: Both are possible! (a) is obvious, but (b) can happen if some of Y's ancestors have (other) decendants that are high feerate
17417:54 <LarryRuane> this would, in effect, "remove" those low-feerate ancestors from Y's ancestor set, which may then increase Y's ancestor feerate
17517:54 <Murch> LarryRuane: I've created a bunch of graphs that will exhibit these sort of issues for the functional tests. I'm not 100% sure that they're exhaustive yet, though
17617:54 <glozow> LarryRuane: bingo! both are possible!
17717:54 <glozow> To all: We're running out of time and have just looked at the concept + approach today, and didn't really get into wallet. Would you all be interested in continuing with this PR next week? The questions will be the same, but we'll have more time to dive into implementation and tests :)
17817:55 <pablomartin> glozow: sure
17917:55 <LarryRuane> glozow: +1 yes!
18017:55 <josibake> definitely interested in continuing next week
18117:55 <Murch> ishaanam: I wrote the test with unconfirmed and confirmed UTXOs you proposed, but I've not finished my update of the PR yet
18217:55 <josibake> glozow: also, yes to having a epoch review club in the future
18317:55 <ishaanam[m]> glozow: yes
18417:55 <LarryRuane> josibake: +1
18517:55 <stickies-v> (to everyone voting yes: thanks for kicking me out of (hosting) job. names are noted)
18617:55 <d33r_gee> glozow +1
18717:55 <hernanmarino_> glozow : yes please
18817:56 <stickies-v> but yes, I would also like to continue this PR next week - very interesting!
18917:56 <Murch> Cool
19017:56 <glozow> Great :) let's do one more question and then to be continued - hahaha sorry stickies-v
19117:56 <LarryRuane> josebake: i'm not sure epoch is itself enough for an entire review club...
19217:56 <josibake> stickies-v:  >:D
19317:56 <Murch> Also looking forward to the further questions and comments your review will unearth
19417:56 <glozow> Can `CalculateBumpFees()` overestimate, underestimate, both, or neither? By how much?
19517:57 <ishaanam[m]> Murch: great!
19617:58 <josibake> my guess is overestimate
19717:59 <glozow> josibake: yes!
19817:59 <glozow> Next week, we'll get to why that is, and how the PR resolves it :)
19917:59 <ishaanam[m]> CalculateBumpFees can overestimate since it doesn't take into account two sibling transactions both being selected (since the calculation is done independently)
20017:59 <Murch> Methinks that for an individual UTXO the result of CalculateBumpFees() should be accurate regarding the available information. But it can overestimate, if two UTXOs have overlapping ancestries and are spent together. It can underestimate if there is a later sibling transaction that bumps an ancestor harder than our own, but that's not really a mistake.
20117:59 <Murch> err.
20218:00 <Murch> The latter is also an overestimate
20318:00 <pablomartin> glozow: yes pls
20418:00 <josibake> Murch: in the case of a later sibling, i think that would also be an overestimate?
20518:00 <glozow> ishaanam[m]: yep exactly, if any UTXOs have overlapping ancestors, they'll both count
20618:00 <hernanmarino_> I have to go, thank you all for everything, see you next week !
20718:00 <Murch> Anyway, what I wanted to get at was that more transactions published after ours might take precedence and outdate our prior estimate
20818:00 <glozow> (exercise for the attendees: can it *ever* underestimate?)
20918:00 <josibake> glozow: thanks for hosting! great questions on the PR, too
21018:01 <glozow> Thanks everyone for a wonderful session! See you next week!
21118:01 <glozow> #endmeeting