Automated coin selection

[darosior]

The first release of the software won't come with any automated coin selection. Users will have to pick their coins on the interface when crafting a spending transaction ("coin control"). We might want to implement some automated coin selections in the future.

If we do it, what coin selections should we implement? How should people define which one to use? I can think of a few strategies we could have:

• Regular BnB
• Oldest-coin (or a BnB biased toward using old coins) first to prevent them to have to rotate their coins in a dedicated transaction.
• Regular BnB + batch in coins that are about to "expire"

Also, i don't think it's worth re-implementing the wheel. Coin selection algorithm can be tricky to implement, and have been implemented many times already. Let's just re-use and contribute review to an existing implementation. For this purpose i've asked @danielabrozzoni if she thought it could be reasonable to make @bitcoindevkit's coinselection into its own crate.

Thoughts? Is there any interest from users to have this?

[danielabrozzoni]

@evanlinjin is currently working on our coin selection implementation as a part of the bdk_core update: https://github.com/LLFourn/bdk_core_staging/tree/master/bdk_core/src/coin_select

This means that it's going to take a while before we are able to decouple it in a different repository (finishing and integrating bdk with bdk_core is currently the priority)

Oldest-coin (or a BnB biased toward using old coins)
Regular BnB + batch in coins that are about to "expire"

The BNB in bdk_core now uses custom function for the score - while in Bitcoin Core the waste metric is hardcoded into the code, in bdk you'll be able to decide if you want to use the waste metric, or supply your own scoring function (which might be "waste metric with a bias towards expiring coins"), so it should be flexible enough for this! 😄

TL;DR: I'm hyped, the new CS should be pretty cool, we will eventually (/hopefully) move it to another crate, but it's going to take time (~3 months?)

[darosior]

Awesome. :) 3 months works. Thank you guys for doing this work! ------- Original Message ------- Le lundi 10 octobre 2022 à 11:37 AM, Daniela Brozzoni ***@***.***> a écrit :

…

***@***.***(https://github.com/evanlinjin) is currently working on our coin selection implementation as a part of the bdk_core update: https://github.com/LLFourn/bdk_core_staging/tree/master/bdk_core/src/coin_select This means that it's going to take a while before we are able to decouple it in a different repository (finishing and integrating bdk with bdk_core is currently the priority) > Oldest-coin (or a BnB biased toward using old coins) > Regular BnB + batch in coins that are about to "expire" The BNB in bdk_core now uses custom function for the score - while in Bitcoin Core the waste metric is hardcoded into the code, in bdk you'll be able to decide if you want to use the waste metric, or supply your own scoring function (which might be "waste metric with a bias towards expiring coins"), so it should be flexible enough for this! 😄 TL;DR: I'm hyped, the new CS should be pretty cool, we will eventually (/hopefully) move it to another crate, but it's going to take time (~3 months?) — Reply to this email directly, [view it on GitHub](#51 (comment)), or [unsubscribe](https://github.com/notifications/unsubscribe-auth/AFLK3F27NCVJD5VFC2VODE3WCPPVNANCNFSM6AAAAAAQ7SUVO4). You are receiving this because you authored the thread.Message ID: ***@***.***>

[evanlinjin]

@darosior @danielabrozzoni The bdk_core::coin_select module is very close to completion. @LLFourn will be putting in the final touches to the API in the next few days all so. After that, we will do even more testing.

If minisafe needs it soon, we can create a stable bdk_core repository and add slowly add in finished submodules from the staging repository.

[darosior]

Good to hear!

If minisafe needs it soon, we can create a stable bdk_core repository and add slowly add in finished submodules from the staging repository.

It's not a short-term (~2 months) priority. It could become one depending on whether it's a feature desired by our future users. So no need to rush this just for us. :)
Note also that we don't use BDK (yet?) so we'll have to wait for the coin selection to be in its own crate anyways.

[evanlinjin]

@darosior Awesome, we will definitely get it done before then :)

Note also that we don't use BDK (yet?) so we'll have to wait for the coin selection to be in its own crate anyways.

My understanding is that bdk_core would be in it's own repository (and would be lightweight and std-lib would be optional).

[danielabrozzoni]

we don't use BDK (yet?)

😏😉

My understanding is that bdk_core would be in it's own repository (and would be lightweight and std-lib would be optional).

Revault would still need it in a different crate tho, so that they can pull the algorithm without SpkTrackers, SparseChains, and other non-cs-related-but-still-pretty-cool stuff

[LLFourn]

I believe that CS API will be ready for experimentation by the end of the week but with breaking changes happening till the end of the year.

So it sounds like you would like coin selection to be a separate crate. I think this is worth doing if we make sure that it only depends on rust-bitcoin and not rust-miniscript.

[darosior]

That makes sense, and a crate depending only on rust-bitcoin (or parts of it) would be ideal for us. By the way, what MSRV are you going for?

[darosior]

Hey everyone, what's the status of the coin selection in BDK / BDK core? Do you think we could start using it in say a month?

[LLFourn]

Yeah @darosior. I put CS on the backburner to focus on other things. It's ready for usage from an API point of view. It will be zero-dependency (doesn't even need rust-bitcoin). The thing that I'm not quite happy with is that the only real "algorithm" that has been implemented is the waste metric. I don't really think it's a good choice -- it has a tendency to over consolidate. It will spend everything in your wallet if the current feerate is lower than the long term feerate. I think the best one to recommend is to just try and minimize fee while also taking into account the cost of the change within that.

[EDIT] the code in the bdk core repo is not what I'm talking about -- it's the code in one of the PRs: https://github.com/LLFourn/bdk_core_staging/tree/0331b058d64ff3acc43a3584a94173605b594b48/bdk_coin_selection/src

[darosior]

Nice. We could have a shot at integrating it here in a branch and provide a tested review of your PR this way.

Going for a suboptimal CS algorithm at first is fine for us. And the waste metric might actually not not be unreasonable as (combined with a bias toward using older coins) it could make rotating coins seamless.

Do you have a MSRV?

[LLFourn]

I'll work on this next week and get something that can be released. I'll try and put the MSRV to 1.48.0. "spending older coins" I think should be possible but you'd need to roll it yourself (make a branch and bound metric that gives better scores to solutions that spend older coins ).

[darosior]

Cool!

Yeah re applying a bias to BnB that's what i meant, we'd do it ourselves of course.

[jp1ac4]

Hi @darosior, I can work on this issue next before continuing with #43.

[darosior]

Just for facilitating reachability, the latest state of the implementation upstream is now at bitcoindevkit/bdk#1072.