Bump unconfirmed ancestor transactions to target feerate (wallet)

Nov 23, 2022

https://github.com/bitcoin/bitcoin/pull/26152

Host: glozow - PR author: Xekyo

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

Notes

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.

Questions

Did you review the PR? Concept ACK, approach ACK, tested ACK, or NACK?
What issue does this PR solve?
In CalculateCluster, what does a transaction’s “cluster” consist of?
Why does the MiniMiner require an entire cluster? Why can’t it just use the union of each transaction’s ancestor sets?
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
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?
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?
At a high level, describe how MiniMiner::CalculateBumpFees() works. Why can’t we just use the ancestor feerate of each transaction?
Can CalculateBumpFees() overestimate, underestimate, both, or neither? By how much?
What are the similarities and differences in implementation between CalculateBumpFees and CalculateTotalBumpFees?
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?
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?
Describe the approach taken in the “Bump unconfirmed parent txs to target feerate” commit.
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?
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())?
How does the PR handle spending unconfirmed UTXOs with overlapping ancestry? (Hint: what does the code here do)?

Meeting Log

17:00

<glozow> #startmeeting

17:00

<glozow> Hi everyone! Welcome to Bitcoin Core PR review club!

17:00

<kouloumos> hi!

17:00

<hernanmarino_> Hi Gloria !

17:00

<stickies-v> hi!

17:00

<ishaanam[m]> hi

17:00

<josie[m]> hi

17:00

<hernanmarino_> and everyone :)

17:00

<emzy> hi

17:00

<BlueMoon> Hello!

17:01

<glozow> hello friends! ^_^

17:01

<pablomartin> Hello!

17:01

<lightlike> Hi

17:01

<yashraj> hi

17:01

<brunoerg> hu

17:01

<glozow> We're looking at #26152 today, notes here: https://bitcoincore.reviews/26152

17:01

<LarryRuane> hi

17:01

<brunoerg> hi*

17:01

<glozow> Have y'all had a chance to look at the notes and/or review the PR? how about a y/n?

17:01

<b_101> hi all

17:02

<stickies-v> 0.5y - a lot to cover!

17:02

<LarryRuane> notes y, review 0.5y

17: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

17:02

<emzy> n

17:02

<ishaanam[m]> y, I looked at the notes, reviewed the wallet part of the pr

17:02

<pablomartin> y for the notes, pending review

17:02

<yashraj> y, notes

17:03

<glozow> yes there's a lot to cover, but hopefully interesting enough to keep us going

17:03

<b_101> y/n

17:03

<glozow> Let's start with the first question: What issue does this PR address?

17:03

<kouloumos> notes y, review 0.1y, didn't got out of the mempool rabbit hole yet

17:04

<hernanmarino_> It fixes an overestimation in the effective value of unconfirmed UTXOs by the fees necessary to bump their ancestor transactions.

17:04

<glozow> Right, I presume the MiniMiner implementation will be the most difficult to review (?)

17: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).

17:04

<hernanmarino_> I quitted when I got to the MiniMiner :))

17: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

17: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

17:06

<glozow> LarryRuane: hernanmarino_: stickies-v: yes, thank you!

17: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?

17: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 ..."

17:08

<LarryRuane> ishaanam[m]: +1 (IIUC)

17: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

17:08

<stickies-v> that's interesting, I hadn't considered the feedback loop, thanks LarryRuane - makes sense!

17:09

<glozow> Before we jump in, would anybody like to give us an overview of the approach taken in this PR?

17:09

<Murch> LarryRuane: Not necessarily. We will only consider unconfirmed UTXOs in later backoff attempts on Coin Selection.

17: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?

17:10

<LarryRuane> So we do prioritize confirmed UTXOs in coin selection (IIUC)

17:10

<hernanmarino_> glozow : I think Murch will be able to answer that :D

17:11

<glozow> Yes, we already *only* try to use unconfirmed inputs to fund the transaction if we can't cover it using confirmed ones.

17: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.

17:11

<Murch> hernanmarino_: Sure, but that's not the point of it :D

17:11

<LarryRuane> glozow: Murch: also we only use _change_ outputs (change to ourselves)?

17:11

<hernanmarino_> :D

17: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

17:12

<glozow> LarryRuane: here is the code Murch is referring to https://github.com/bitcoin/bitcoin/blob/38d06e1561013f4ca845fd5ba6ffcc64de67f9c0/src/wallet/spend.cpp#L617-L663

17: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?

17:12

<Murch> LarryRuane: Correct, assuming that you haven't enabled “allowUnsafe”

17:13

<Murch> guest: That's not quite it. Consider what the wallet knows about its UTXOs and what information it might be missing

17: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!

17: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

17:14

<LarryRuane> Murch: oh i see, that makes sense

17: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

17:14

<LarryRuane> "simulate the mining process" -- but without the Pow haha

17:15

<LarryRuane> the code in this PR is really interesting, it must have been a blast to write, @murch!

17: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

17: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.

17:15

<LarryRuane> stickies-v: good point!

17:16

<glozow> *not very interesting in this context

17:16

<LarryRuane> hey if not too much sidetracking, isn't the getblocktemplate RPC out of favor these days?

17:16

<LarryRuane> thought i'd read that somewhere

17:17

<glozow> I'll move on to the implementation questions.

17: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)

17:17

<LarryRuane> given a set (vector) of transactions, return deduped vector of all connected transactions (ancestors and decendants recursively)

17:17

<hernanmarino_> It consists of all in-mempool ancestors of a set of transactions not already in the mempool (considering ancestor and descendant limits)

17:17

<LarryRuane> the list won't include the original transactions, except those that are connected to other transactions in the cluster

17: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?

17: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

17: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

17:21

<stickies-v> because in the beginning of the function we visit them all with `for (const auto& it : cluster) { visited(it); }`

17:21

<stickies-v> oh wait. it's opposite. they're always included haha. whoops

17:21

<glozow> Er, I'm pretty sure the cluster includes those specified in `txids`? in the beginning we also initialize `cluster{GetIterVec(txids)}`

17:21

<LarryRuane> stickies-v: yes but let's say we're spending from two outputs of the same ancestor transaction? would that do it?

17: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

17: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?

17:22

<josibake> at least from my understanding

17: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

17:22

<LarryRuane> glozow: you're right, thanks, i had missed that

17:23

<stickies-v> yep josibake glozow you're right

17: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

17: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.

17:24

<Murch> It's the maximal strongly connected component of the initial transactions

17: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)

17: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?

17: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).

17:25

<josibake> or perhaps a better question, who is deciding which txids to pass to CalculateCluster? the wallet?

17:25

<LarryRuane> josibake: I think that's perfectly okay (and normal), you just get the union

17:26

<LarryRuane> lightlike: is the actual miner conditionally compiled in? (i don't recall)

17: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

17:27

<Murch> only the result of the graph analysis.

100

17:27

<Murch> josibake: The wallet asks for all of the transactions that created unconfirmed UTXOs in its pool

101

17:28

<hernanmarino_> Murch : that's interesting

102

17: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.

103

17:28

<josibake> Murch: ah, got it! that makes more sense

104

17:29

<glozow> I can understand why the duplication of the algo could be considered an inferior approach, feedback welcome of course

105

17:29

<Murch> Also, we need to stop assembling the block at a specific feerate which is a different mechanism than running out of space

106

17:30

<glozow> Yes, though I must admit that the `BlockAssembler::blockMinFeeRate` also achieves this

107

17: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

108

17:31

<glozow> it's a good way to compare the algos we can fuzz them pretty easily given they have this in common

109

17:31

<lightlike> glozow: ah, thanks. Don't know the BlockAssembler enough to have an opinion, just wanted to understand the reasons.

110

17: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

111

17:32

<LarryRuane> then that function can be unit-tested too very easily

112

17: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.

113

17:34

<LarryRuane> glozow: seems like you made a good engineering decision

114

17:35

<LarryRuane> (er, you and murch I guess)

115

17:35

<josibake> regarding CalcCluster (and sorry if this was asked already, had some issues with my irc client), but why the `GetIterVec` function?

116

17:36

<LarryRuane> josibake: you mean why not make it inline?

117

17: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

118

17:36

<glozow> oh! is it LarryRuane's question?

119

17:37

<LarryRuane> glozow: oh that's good to know! wasn't aware of that effort

120

17:38

<LarryRuane> epochs == really cool idea

121

17: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

122

17: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

123

17:38

<glozow> haha yes `txiter` is an alias for a very very long type

124

17:39

<glozow> txiter def: https://github.com/bitcoin/bitcoin/blob/38d06e1561013f4ca845fd5ba6ffcc64de67f9c0/src/txmempool.h#L406

125

17:39

<glozow> indexed_transaction_set: https://github.com/bitcoin/bitcoin/blob/38d06e1561013f4ca845fd5ba6ffcc64de67f9c0/src/txmempool.h#L374

126

17:39

<josibake> im guessing txiters are specific to epochs then? (also , read a little on the epoch pr's as background, very cool idea)

127

17:40

<glozow> Ah no, txiters are just mapTx iterators. The entry's `m_epoch` can change without the txiter changing

128

17: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?

129

17: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?

130

17:41

<pablomartin> josibake: could you pls share that epoch pr?

131

17:42

<glozow> Epoch Mempool: https://github.com/bitcoin/bitcoin/pull/17925 and https://github.com/bitcoin/bitcoin/pull/17268

132

17:42

<glozow> (would people be interested in an epoch mempool review club?

133

17: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

134

17:42

<glozow> )

135

17:42

<pablomartin> glozow: as we discussed before, we need descendant and even siblings... ?

136

17:42

<Murch> Hint: The test-cases might provide some ideas

137

17: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.

138

17: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

139

17: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`

140

17: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!

141

17: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

142

17:43

<Murch> pablomartin: Why though? What mistake might we make if we don't consider them?

143

17:43

<josibake> well, i take that back. because the cluster includes more than strictly the ancestory for a single tx

144

17:44

<Murch> josibake: Njet. What if your sibling has bumped the parent already to a higher package feerate than what you're aiming for?

145

17:44

<josibake> stickies-v: thanks, that helps!

146

17:44

<glozow> pablomartin: lightlike: yes exactly. to find out how much to bump, we need to know whether something is already bumped.

147

17:44

<Murch> There is also another issue that hasn't been mentioned yet

148

17:44

<Murch> Or only indirectly, I guess

149

17:45

<glozow> and josibake: yes that's the general idea. we don't need anything that cannot impact these transactions during block assembly

150

17:45

<LarryRuane> Murch: a little more context please? issue with not consideringly only ancestors?

151

17: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

152

17: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?

153

17:46

<Murch> Children pay for parents, but parents cannot pay for children

154

17: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?)

155

17:47

<pablomartin> Murch: true, I agree (only children pay for parents -> direction)

156

17: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

157

17:47

<ishaanam[m]> LarryRuane: yes

158

17: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!

159

17:48

<pablomartin> Murch: so you need to check if sibling were already bumping common parents...

160

17:48

<lightlike> sure - but the low-fee children would be included in the Cluster at first, and then discarded later, right?

161

17: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

162

17:49

<LarryRuane> Murch: that's mind-bending! cool tho

163

17: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

164

17: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

165

17: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

166

17: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

167

17: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

168

17:52

<Murch> pablomartin: Yep!

169

17: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?

170

17:53

<glozow> (a) X is selected sooner than Y

171

17:53

<glozow> (b) X is selected later than Y

172

17: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)

173

17: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

174

17:54

<LarryRuane> this would, in effect, "remove" those low-feerate ancestors from Y's ancestor set, which may then increase Y's ancestor feerate

175

17: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

176

17:54

<glozow> LarryRuane: bingo! both are possible!

177

17: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 :)

178

17:55

<pablomartin> glozow: sure

179

17:55

<LarryRuane> glozow: +1 yes!

180

17:55

<josibake> definitely interested in continuing next week

181

17: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

182

17:55

<josibake> glozow: also, yes to having a epoch review club in the future

183

17:55

<ishaanam[m]> glozow: yes

184

17:55

<LarryRuane> josibake: +1

185

17:55

<stickies-v> (to everyone voting yes: thanks for kicking me out of (hosting) job. names are noted)

186

17:55

<d33r_gee> glozow +1

187

17:55

<hernanmarino_> glozow : yes please

188

17:56

<stickies-v> but yes, I would also like to continue this PR next week - very interesting!

189

17:56

<Murch> Cool

190

17:56

<glozow> Great :) let's do one more question and then to be continued - hahaha sorry stickies-v

191

17:56

<LarryRuane> josebake: i'm not sure epoch is itself enough for an entire review club...

192

17:56

<josibake> stickies-v: >:D

193

17:56

<Murch> Also looking forward to the further questions and comments your review will unearth

194

17:56

<glozow> Can `CalculateBumpFees()` overestimate, underestimate, both, or neither? By how much?

195

17:57

<ishaanam[m]> Murch: great!

196

17:58

<josibake> my guess is overestimate

197

17:59

<glozow> josibake: yes!

198

17:59

<glozow> Next week, we'll get to why that is, and how the PR resolves it :)

199

17: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)

200

17: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.

201

17:59

<Murch> err.

202

18:00

<Murch> The latter is also an overestimate

203

18:00

<pablomartin> glozow: yes pls

204

18:00

<josibake> Murch: in the case of a later sibling, i think that would also be an overestimate?