Add waste metric for coin selection

[benthecarman]

Implementation of the coin selection waste metric from https://github.com/bitcoin/bitcoin/pull/22009

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

I plan on adding more of the tests but wanted to get this out there as I am new to rust and I am guessing I have some things I need to fix.

[notmandatory]

Some good suggestions came up in our team chat today from @LLFourn and @afilini about his PR.

• your calculate_waste function could be implemented on the CoinSelectionResult struct, which already contains the .selected utxos.
• then it would be straight forward to create a function (maybe on Wallet?) that does coin_select() for different CoinSelectionAlgorithm implementations and returns the optimal result.

Also @rajarshimaitra reminded us that tomorrows PR review club will be on this topic, so good for anyone interested to attend.

[notmandatory]

moving this one to DRAFT until we figure out how to integrate it.

[csralvall]

Hey @benthecarman, are you still working on this? May I continue your work?

[benthecarman]

Hey @benthecarman, are you still working on this? May I continue your work?

Feel free to!

[csralvall]

Some good suggestions came up in our team chat today from @LLFourn and @afilini about his PR.

• your calculate_waste function could be implemented on the CoinSelectionResult struct, which already contains the .selected utxos.
• then it would be straight forward to create a function (maybe on Wallet?) that does coin_select() for different CoinSelectionAlgorithm implementations and returns the optimal result.

Also @rajarshimaitra reminded us that tomorrows PR review club will be on this topic, so good for anyone interested to attend.

Although CoinSelectionResult may be related to the calculate_waste function, and the shared selected parameter makes it more natural to think so, I found some drawbacks in this approach. Schmidty noted in the PR review club that there were two waste metrics in use currently in Bitcoin Core. The one computed by the function GetSelectionWaste and the one used by BnB to improve the selection. Currently, GetSelectionWaste in Bitcoin Core master branch, is implemented as an independent function, not an associated one nor a method, and SelectionResult implements a public wrapper method around it to make comparisons between different algorithms. This approach allows the future refactoring of the BnB to deduplicate the calculation of the waste metric and, at the same time, the current comparison of the coin selection algorithms. I suggest to follow the implementation of Bitcoin Core. To make calculate_waste an independent function, with a public wrapper (e.g.: get_waste) method around it in the CoinSelectionResult. This will give us the same flexibility mentioned above.

[rajarshimaitra]

@csralvall That makes sense.. Eventually we would want to use the waste function to compare potential wastes between different coin selections.. It makes sense that it can be different than what BnB uses internally..

I think I understand the approach you are suggesting, although would be more clear when I see the code.. Feel free to update the PR (or make new one) and I would review..

[murchandamus]

Can you please provide some more doc details within the code on waste metric? Is it used by core too? I would like to learn more about the rationale behind the waste calculations and see how that can be used to make selction-algo choices efficient.

I recently wrote a blog post about this, let me know if you have open questions, I'd be happy to incorporate feedback: https://murch.one/posts/waste-metric/

It makes sense that it can be different than what BnB uses internally.

Yeah, that's actually a good point. So far, I don't see a reason why the two would diverge, but another contributor recently suggested that we could introduce additional heuristics based on privacy and confirmation-reliability to aid in prioritization of SelectionResults. These additional heuristics might only apply to the choice between the solutions from different algorithms rather than internally to BnB.

[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)