Add waste metric for coin selection

[csralvall]

Description

Waste is a metric introduced by the BnB algorithm as part of its bounding procedure. Later, it was included as a high level function to use in comparison of different coin selection algorithms in bitcoin/bitcoin#22009.

This implementations considers waste as the sum of two values:

• Timing cost
• Creation cost

waste = timing_cost + creation_cost

---

Timing cost is the cost associated to the current fee rate and some long term fee rate used as a treshold to consolidate UTXOs.

timing_cost = txin_size * current_fee_rate - txin_size * long_term_fee_rate

Timing cost can be negative if the current_fee_rate is cheaper than the long_term_fee_rate, or zero if they are equal.

The name of this cost is derived from the action of making bets against some kind of market (in this case the fee market) to gain profits using the interpretation of the future behaviour of that market based on a partial information game.

---

Creation cost is the cost associated to the surplus of coins besides the transaction amount and transaction fees. It can happen in the form of a change output or in the form of excess fees paid to the miner.

Change cost is derived from the cost of adding the extra output to the transaction and spending that output in the future.

change_cost = current_fee_rate * change_output_size + long_term_feerate * change_spend_size

Excess happens when there is not change, and the surplus of coins is spend as part of the fees to the miner:

excess = tx_total_value - tx_fees - target

Where target is the desired amount to send.

Creation cost can be zero if there is a perfect match as result of the coin selection algorithm.

---

So, waste can be zero or negative if the creation cost is zero and the timing cost is less than or equal to zero

Later this can be used in the wallet to select the most optimal coin selection algorithm.

This PR continues the work initiated by @benthecarman in #435 and address some of the features described in #483.

The current PR is based mainly in the following sources:

• GetSelectionWaste from Bitcoin Core.
• Draft PR #435.
• Bitcoin Core PR Review Club #22009.

Notes to the reviewers

While running cargo clippy some warnings may arise due to the lack of documentation of the new functions, those will be resolved once the code changes are finished. The same applies for the CHANGELOG.md file.

Checklists

All Submissions:

• [x] I've signed all my commits
• [x] I followed the contribution guidelines
• [x] I ran cargo fmt and cargo clippy before committing

New Features:

• [x] I've added tests for the new feature
• [x] I've added docs for the new feature
• [x] I've updated CHANGELOG.md

[danielabrozzoni]

Tests are failing, can you please update the PR? :) https://github.com/bitcoindevkit/bdk/pull/515 introduced the is_spent field in LocalUtxo, since you're testing coin selection (which uses only unspent utxos) you probably want to set it to false all the time :)

[csralvall]

Yes, you are right! I will try to rebase my branch in top of master to get all last changes (including #515) and then apply the correction. Let me know if you have any doubt about this.

[csralvall]

It seems that the only failing test remaining are related to missing documentation. I don't know if you want to discuss the implementation further, but I'm willing to add documentation to pass the test and then iterate again, in case something is missing.

[danielabrozzoni]

I'll look into the code ASAP, sorry for the waiting :)

[csralvall]

Thanks for the review! Let me explain myself. I made a few assumptioms before started working in this PR:

1. Originally I followed this suggestion from Steve to drop the struct WasteMetric in favor of a helper function associated with the CoinSelectionAlgorithm. I tried this approach but the generic database bound imposed some constraints to the signature of the calculate_waste function that didn't make sense to me at that moment. So I decided to implement it as a general function related to the CoinSelectionResult through the get_waste method.

   I will try to use your proposed approach and create the struct Waste.

[csralvall]

Some things that I've experienced while trying to make Waste a struct:

1. If it will be exposed through CoinSelectionResult it should be a public struct.
2. If we don't want pub struct Waste we can use struct Waste internally and pass the inner value to the CoinSelectionResult struct.
3. If we proceed with the public struct, an extra de-reference from the waste field of CoinSelectionResult will be required (waste.value).

All options seem cumbersome IMHO.

I reviewed the coinselection module from bitcoin and they have structured the Waste calculus in three different functions:

• GetSelectionWaste who does all the work and is not associated with any struct (for testing purposes).
• ComputAndSetWaste a setter (something similar to get_waste).
• GetWaste a getter.

Although all of that it's still a work in progress, because the values of the waste metric are hardcoded for SelectCoinsBnB.

[afilini]

If it will be exposed through CoinSelectionResult it should be a public struct.

Yes, because custom coin selection algorithms should also be able to calculate waste

If we proceed with the public struct, an extra de-reference from the waste field of CoinSelectionResult will be required

I don't really understand this, if you want you could also implement Deref so that Waste can behave like an i64. But I don't think it's that bad to just read the inner value. Also, if you only have one field you can also definite it as struct Waste(pub i64) and add a getter for the inner value so that you don't have to use waste.0.

I haven't reviewed the whole code yet, but I did spend some time trying to remove some useless cloning in the code: I pushed my code here, feel free to take the two top commits and apply them to your PR.

[csralvall]

I don't really understand this, if you want you could also implement Deref so that Waste can behave like an i64. But I don't think it's that bad to just read the inner value. Also, if you only have one field you can also definite it as struct Waste(pub i64) and add a getter for the inner value so that you don't have to use waste.0.

I didn't know about Deref, but now that I followed your suggestion I find struct Waste(pub i64) cleaner. That's was all about, I prefer to have straight semantics in the code. I don't know if there is a case of use for the getter if we can use destructuring assignment, but I can implement one if you think it's necessary.

I haven't reviewed the whole code yet, but I did spend some time trying to remove some useless cloning in the code: I pushed my code here, feel free to take the two top commits and apply them to your PR.

Thanks for this! There are things that I'm still learning about Rust and made some clunky decisions.

[csralvall]

Do you think that this is ready to start documenting it?

[notmandatory]

Hi, please rebase to pickup changes in #596. Thanks!

[danielabrozzoni]

Once it compiles, I think it's ready 😄

[csralvall]

I added some REVIEW comments in mod.rs and coin_selection.rs because I need some clarification of what to do with those sections of code.

[murchandamus]

I don't feel like I'm familiar enough to "ACK" here, but my prior comments appear to have been all addressed. So, I guess "Concept ACK"? :)

[csralvall]

I realized that I should return the fee amount related to the change output together with the change TxOut. I could implement an enum like:

pub enum Excess {
    NoChange(Error::InsufficientFunds),
    // Change(change_output, change_output_fee)
    Change(TxOut, u64),
}

Then the signature of Waste::calculate would be:

    pub fn calculate(
        selected: &[WeightedUtxo],
        weighted_drain_output: WeightedTxOut,
        target: u64,
        fee_rate: FeeRate,
    ) -> Result<(Waste, Excess), Error>

And we can decide later if we join the change output with the other outputs inside coin_select or create_tx. Either way, if we keep the change above, CoinSelectionResult would look like this:

pub struct CoinSelectionResult {
    /// List of outputs selected for use as inputs
    pub selected: Vec<Utxo>,
    /// Total fee amount in satoshi
    pub fee_amount: u64,
    /// Waste value of current coin selection
    pub waste: Waste,
    /// Remaining amount after coin_select
    pub excess: Excess,
}

Through the use of NoChange(err) here we can avoid passing params.drain_wallet as parameter to coin_select. And with Change(output, output_fee) we can keep the same functionality of this line (that wouldn't be removed with the fix for #147 ) through output.script_pubkey and output.value

[murchandamus]

Also, returning the total resulting fee with the coin selection result will make it easier to handle spending unconfirmed inputs when the parent transaction has a lower feerate than what you intend for the new transaction you're building to have. I mean, if you e.g. want to automatically bump the parent transaction to the same feerate so you achieve the intended feerate, and if you want to account for that additional in the waste metric later.

[csralvall]

I'm not sure that I've understood what you said correctly. You were thinking in something like the following situation?

• Tx_A ----> UTXO_A (fee rate = 5, confirmed)
• Tx_B ----> UTXO_B(fee rate = 3, unconfirmed)
• (UTXO_A, UTXO_B) ----> Tx_C(fee rate = 5).

The original transaction that generated UTXO_B is Tx_B, and coin select re-bumps the fee for it (not implemented currently), lets call it Tx_B_bis. You said that the extra amount that comes from [Tx_B.fee_amount - Tx_B_bis.fee_amount] can now be considered as part of the fee amount of Tx_C and waste can account it?

I'm unsure because fee_amount isn't new for CoinSelectionResult.

As a side note, I'm planning to propose a modification for the fee amount returned by CoinSelectionResult. To avoid carriage of state through multiple functions, I was considering to just return the fee amount for the selected inputs and then add it to the fee amount of the rest of the transaction (inside create_tx).

[danielabrozzoni]

pub enum Excess {
    NoChange(Error::InsufficientFunds),
    // Change(change_output, change_output_fee)
    Change(TxOut, u64),
}

Written like this, Excess::NoChange always contains an Error::InsufficientFunds. Is this what you want to achieve? If so, why? Couldn't you have no change while having enough funds?

[murchandamus]

I'm not sure that I've understood what you said correctly. You were thinking in something like the following situation?

* `Tx_A` ----> UTXO_A (fee rate = 5, confirmed)

* `Tx_B` ----> UTXO_B(fee rate = 3, unconfirmed)

* (UTXO_A, UTXO_B) ----> `Tx_C`(fee rate = 5).

The original transaction that generated UTXO_B is Tx_B, and coin select re-bumps the fee for it (not implemented currently), lets call it Tx_B_bis. You said that the extra amount that comes from [Tx_B.fee_amount - Tx_B_bis.fee_amount] can now be considered as part of the fee amount of Tx_C and waste can account it?

Yeah, if you spend an unconfirmed input from a transaction that paid a lower feerate than the new transaction you're creating, you need to add more fees to the new transaction so that the transaction package in total will have the intended feerate. I.e. in your example:

Tx_A— vsize: 200 vB, fee: 1000 sats, feerate: 5 sat/vB ↦ UTXO_A Tx_B— vsize:150 vB, fee: 450 sats, feerate: 3 sat/vB ↦ UTXO_B

If Tx_C is spending UTXO_A and UTXO_B and has a vsize of 200 vB, how much fees should it pay to reach an effective feerate of 5 sat/vB? ⇒ Tx_A has the same feerate already, so doesn't need to be bumped. Tx_B pays less than Tx_C, so Tx_C has to add (5 sat/vB - 3 sat/vB)×Tx_B.vsize = 300 sats to bump Tx_B to 5 sat/vB, and must pay 200 vB × 5 sat/vB for itself, i.e. if Tx_C pays a total of 1,300 sat/vB the transaction package {Tx_A, Tx_B, Tx_C} will have an effective feerate of 5 sat/vB.

[csralvall]

pub enum Excess {
    NoChange(Error::InsufficientFunds),
    // Change(change_output, change_output_fee)
    Change(TxOut, u64),
}

Written like this, Excess::NoChange always contains an Error::InsufficientFunds. Is this what you want to achieve? If so, why? Couldn't you have no change while having enough funds?

I realized that I can't do that. The idea came up because I was to tied up to the code in create_tx. I will probably turn to the structure used in #630.

[danielabrozzoni]

Hey, we are in the process of releasing BDK 1.0, which will under the hood work quite differently from the current BDK. For this reason, I'm closing all the PRs that don't really apply anymore. If you think this is a mistake, feel free to rebase on master and re-open!

(Specifically, the coin selection is being rewritten from scratch)