CPFP: Allow telling coin selector that a candidate has unconfirmed parents

[LLFourn]

I guess this is just a new field on Candidate which lets you say the combined weight and fee of all parents. I think the approach to use in practice in bdk is to roll all inputs that are in an unconfirmed tree into a single candidate. This will give you the correct answer but has the disadvantage of forcing you to spend them altogether. Needs some design work before trying to implement it. Looking at the actual CPFP related logic in core might provide some inspiration.

[murchandamus]

Unfortunately, the problem of assessing the effective feerate of a new transaction in the context of its ancestry can become fairly complex. E.g. when parents have a higher feerate than the transaction to be created, they do not encumber the confirmation of the new transaction; or when a lower feerate parent transaction is already reprioritized by another child transaction, it may similarly not require a bump.

We worked on solving this problem for Bitcoin Core in bitcoin/bitcoin#27021.

[jp1ac4]

I guess this is just a new field on Candidate which lets you say the combined weight and fee of all parents.

Please note that we followed a similar approach in Liana, where we increase a candidate's weight if it has ancestors at a lower feerate:
https://github.com/wizardsardine/liana/blob/27570b4de97e7068ba79cfae1b4495d517eb6cfc/liana/src/spend.rs#L299-L330

With this approach, we ignore the more complex scenarios described above and also assume no two candidates have ancestors in common. It would be good if coin selection could check for a given selection if two candidates have ancestors in common and to consider each common ancestor transaction only once. For that, I guess it would be necessary to keep track of each ancestor txid's individual weight and fee when defining candidates.

[aagbotemi]

I've been working on this across bdk_chain, bdk-tx, and bdk_wallet.

Added ancestor_bump_fee: u64 to Candidate, a fixed sat amount representing the additional fee the child must pay to bring its unconfirmed ancestors up to the target feerate. When parents already meet the target, the deficit is zero. Cross-candidate deduplication is handled post-selection in bdk_chain via aggregate_ancestor_package().

Related: bitcoindevkit/bdk_wallet#48

[evanlinjin]

@jp1ac4 a possible solution for double counting ancestors is to have a bitmask for each candidate that represents a subset of all (relevant) unconfirmed ancestor txs.

Edit: But the bitmask solution restricts the number of unconfirmed ancestors we can have.

[evanlinjin]

A problem I ran into: We cannot guarantee that a wallet will have all "unconfirmed ancestors" of their UTXOs. The missing ancestors may be underpaying for our target feerate. Hence, we may undershoot the required fee for the transaction we are creating - which is dangerous.

Possible solutions that I came up with (all downstream):

• Tag those UTXOs as unable-to-price-accurately and only pick them as a last resort. This would be bdk_chain::CanonicalView's responsibility imo.
• Have our chain sources fetch ancestors for UTXOs until reach a confirmed ancestor. May need some back and forth between CanonicalView and the chain sources.

Would love some input on this.

[murchandamus]

In Bitcoin Core, we generally try to avoid unconfirmed inputs and only use them as a fallback. You could perhaps consider it two separate levels of backoff: 1. only confirmed UTXOs, 2. unconfirmed UTXOs, 3. unconfirmed UTXOs that cannot be priced correctly.

IIRC, some of the Lightning implementations couldn’t accurately estimate feerates as they don’t have a mempool, so they would create transactions at a conservative feerate and bump the feerates of any unconfirmed transactions by the larger of some percentage or the minimum incremental feerate every hour they remained unconfirmed. Something like that might also work for UTXOs that cannot be priced correctly, but may be a bit of a privacy hazard. If signing requires unlocking the wallet or similar, you could create multiple versions of the transaction with increasing feerates locked to increasing future block heights, e.g., double in three block, 3× in six blocks, etc. Just spitballin’, tho.