Add Coin Selection Algos

[yancyribbens]

Bitcoin Core has a number of coin-selection strategies that are not currently represented here in rust-bitcoin. I'd like to start a discussion about adding the coin-selection algos used by Bitcoin Core to Rust Bitcoin, in particular, BnB search. To that end, I can offer an early implementation I began some time ago as a starting point.

The questions I have are:

1. do we like the strategy implemented here as a starting point to iterate on.
2. what needs to be be changed/updated at a minimum to move this under the rust-bitcoin commons.
3. what are some improvements/recommendations that should be added going forward. I have a list of improvements that I can think of, although I'm interested to hear what others have in mind.

Also note, there is a Rust coin-selection strategy in the BDK here that can also be used for inspiration and discussion.

[DanGould]

rust-bitcoin seems more focused on strong typing for bitcoin crypto & serialization. Wallet management including coin selection seems to be more of the role of BDK, where you'll find lots of discussion about this problem already.

After BDK 1.0 is released I hear rumors there will be a concerted effort to make coin selection a first class problem that BDK intends to solve. There are some musings here: bitcoindevkit/bdk#773. @evanlinjin would know more.

[Kixunil]

Yeah, let's not make this library everything but a kitchen sink. A simple coin selection crate could live in this org but I'm not sure if it makes sense without something like BDK.

[yancyribbens]

@DanGould I noticed the rust-wallet hasn't implemented a sophisticated selection strategy yet (see the TODO. If we had a standalone crate for coin-selection that could be used as a dependency by the rust-wallet. If BDK also develops something similar, maybe we could coordinate efforts or use whichever. In the meantime, I don't mind advancing a version under the rust-bitcoin organization.

[apoelstra]

I agree that coin selection algorithms do not belong in rust-bitcoin the project. When we were talking on IRC @yancyribbens I thought you meant moving a coin selection crate into the rust-bitcoin organization, which I'd be fine with provided the crate met our requirements (mostly, being actively maintained and having a MSRV of 1.41).

[yancyribbens]

@apoelstra I verified this crate works with version 1.41 by changing the default version of rustc to 1.41 using rustup default 1.41. I can also commit to being a active maintainer. Just curious, why 1.41?

[apoelstra]

We have three criteria that we use to choose our MSRV:

• It should be available in debian stable (and sometimes oldstable if stable is really new :))
• It should be (close to) the version compilable by mrustc, so that people can bootstrap the compiler in a reasonable time without downloading rustc binaries
• It should be >2 years old

We also have a soft requirement that we don't like changing the MSRV very frequently, because every time we have to do it across several crates at once and we're still unsure what the sanest process for that should be.

We have this tracking issue where we note which compiler features we'd really like to have, so that when we do bump our MSRV we can try to choose the "most stable one" that has all the features we want.

We also have this issue which proposes bumping the MSRV now to 1.48 but it has not achieved consensus so I'm doubtful that it'll happen anytime soon.

[yancyribbens]

@apoelstra when you suggested starting a discussion to include coin-selection as part of the rust bitcoin org I started the discussion here. Is there a place I should move this discussion so it's not confusing? I did intend to include coin-selection as a stand-alone repo in rust-bitcoin organization.

[Kixunil]

You wrote at the correct place. The issue is we have a naming collision - Rust Bitcoin is both name of the organization and of the crate. I suggest explicitly typing "Rust Bitcoin organization" when you mean that. We don't have a better way to distinguish yet.

[yancyribbens]

Ok thanks. I'll keep that in mind in the future!

[apoelstra]

Yep, sorry -- and it does add to the confusion that org-wide discussions happen in this specific repo, because AFAIK there is no better place for them.

[yancyribbens]

Hi all, I wanted to follow up on this discussion. It seems to me that the main objection to adding a standalone coin-selection repo to the rust-bitcoin organization is the rumor that BDK may be also working on this (or working on this in the future?). I think the other criteria have been met (active maintainer and compatible MSRV). Is there any other feedback, comments or considerations? If not, do we want to add this under the rust-bitcoin organization?

[yancyribbens]

@sanket1729 Yes, it's only BnB currently and is small but has good test coverage imo. I can add a README and basic CI setup before adding it to the organization. Is there an example or documentation for the CI setup you can recommend?

[Kixunil]

Oh, wow, from quick glance it looks really simple. I'm just not sure about the Utxo trait. Maybe it could be just Borrow<TxOut> (but I'm very tired rn so I could be totally missing something)

[tcharding]

For CI we use bash scripts, they are all slightly different, and a total time sink - feel free to ping me if you have any trouble. My suggestion would be to write a minimal one, we can iterate later (see rust-bitcoin/bitcoin/contrib/test.sh and rust-bitcoin/hashes/contrib/test.sh for examples). The CI scripts are run by rust.yml github action but you should not need to touch that).

[yancyribbens]

@tcharding thanks. I think this should do for a minimal one to start: p2pderivatives/rust-bitcoin-coin-selection@e172a78

[tcharding]

Thanks for having a go man, I added some comments to that link.

[tcharding]

I added issue p2pderivatives/rust-bitcoin-coin-selection#9 with a few observations.

[yancyribbens]

@tcharding thanks! There are a few PR's to address your observations:

p2pderivatives/rust-bitcoin-coin-selection#8
p2pderivatives/rust-bitcoin-coin-selection#10

[yancyribbens]

@tcharding thanks for all the help getting this ready. I've added one last change for now to test.sh which is bechmarks: p2pderivatives/rust-bitcoin-coin-selection#15

[murchandamus]

I glanced at the Branch and Bound algorithm in the https://github.com/p2pderivatives/rust-bitcoin-coin-selection repository. It seems to me that there might be some basic features missing before it should be merged into a production system. For example, I have the impression that it currently runs with the values of the UTXOs rather than the effective values. This means that the input selection will not account for the fees that the inputs need, it will be undershooting the target.

I will also leave some issues on the repository to point out some additional observations.

[apoelstra]

Thanks for taking a look!

It looks like these issues are serious enough that the BnB algorithm won't actually hit the target feerate -- which is serious but fortunately a very easy property to measure, which I hadn't considred until now.

Before bringing this crate into rust-bitcoin I'd like to see a fuzztest that attempts to produce various transactions with various feerates, and guarantees that we always hit the target (or fail to select).

[yancyribbens]

Thanks @xekyo @apoelstra - It's true this current implementation doesn't consider the fee rate, which seems to be a large oversight. In fact, in working on some further performance optimizations recently, I believe I've found other edge cases where a solution should be found but in fact is not (another serious problem). I'll create this as an issue to be solved as well.

[murchandamus]

I find that first trying to achieve the main objectives first and using that to building up a bit of a test corset can help a lot with ensuring that refactors for optimizations do not introduce bugs. Often, the code that just solves the main objectives is also fast enough, and it is unnecessary to complicate the code to speed it up. E.g. when people only call coin selection once an hour, it does not matter that much whether it takes 0.5 s or 0.1 s. So, perhaps performance improvements should only become the focus when a user of the crate complains that they are using it to build tens of thousands of transactions per day and it is not fast enough. :)

[yancyribbens]

Good piont. And my recent contributions to core have helped my understanding of the logic (and waste metric) much more since I wrote this first years ago.

[yancyribbens]

I'm a bit disappointed that I didn't catch this earlier, however it's in part because the tests used worked primarily with whole numbers which I pulled from the current core implementation. If more tests with fractional inputs are considered, there are combinations of UTXO that should be found but are not. Here's the issue I created:

p2pderivatives/rust-bitcoin-coin-selection#20

This will probably require a complete re-write taking into account some of @xekyo findings as well.

[yancyribbens]

@xekyo I created a PR to fix missing solution problems. Before I move on to fixing your suggestions, I wondered if you wanted to a take a look. It seems like before implementing back tracking, the next thing to do is work on the waste calculation. Thanks!

[yancyribbens]

p2pderivatives/rust-bitcoin-coin-selection#21

[yancyribbens]

SRD selection algorithm PR: p2pderivatives/rust-bitcoin-coin-selection#22

[yancyribbens]

There's a new PR for SRD here: p2pderivatives/rust-bitcoin-coin-selection#23

[yancyribbens]

does anyone else have any suggestions before merging this? p2pderivatives/rust-bitcoin-coin-selection#23

[stevenroose]

I was actually looking into coin selection recently and eventually ended up piggy backing BDK's implementation. I reached out to them about the idea of pulling some non-BDK-specific wallet-related things into the bitcoin-wallet crate that is archived now. It was kinda annoying having to use the BDK traits in order to use their impl. It could easily be generalized.

But this new crate seems interesting.

[yancyribbens]

Well, it's not really new. I've been working on it on and off for an embarrassingly long time. I'm a bit stalled at the moment but maybe taking a look at the BDK implementation will help.

[yancyribbens]

I've merged an updated version of SRD p2pderivatives/rust-bitcoin-coin-selection#23. Thanks again Murch (http://murch.one/) and Thibaut Le Guilly for the reviews.

[yancyribbens]

Happy New Years all,

I've created a new Rust BnB coin selection algo here: p2pderivatives/rust-bitcoin-coin-selection#28

Also of interest, I did a quick benchmark to compare this new Rust implementation vs the existing Bitcoin Core (timed on my laptop):

Rust Implementation: 897,593 ns/op

C++ implementation: 816,374 ns/op

Maybe there's some Rust compiler tricks to improve the Rust implementation further? Appreciate any feedback or review.

Cheers

[yancyribbens]

I've created a new PR to change the return type of Single Random Draw: p2pderivatives/rust-bitcoin-coin-selection#33

cc @Kixunil

[yancyribbens]

I think this interface is ready for a V1 version and can be published:

interface in lib.rs

pub fn select_coins(
    target: Amount,
    cost_of_change: Amount,
    fee_rate: FeeRate,
    long_term_fee_rate: FeeRate,
    weighted_utxos: &[WeightedUtxo],
) -> Option<std::vec::IntoIter<&WeightedUtxo>> {

latest PR to cleanup interface: p2pderivatives/rust-bitcoin-coin-selection#36

@apoelstra @Kixunil does this interface seem sane? Is there any other items that should be complete before moving this over to the rust-bitcoin organization?

@murchandamus friendly ping that p2pderivatives/rust-bitcoin-coin-selection#30 is still open for review. I believe this PR closes all the issues you opened.

Cheers!

[Kixunil]

output is not an input. I guess you'll see better what I mean when I get around making the changes.

[yancyribbens]

output is not an input. I guess you'll see better what I mean when I get around making the changes.

I had thought ExtendedTxIn had a way to reference the output that created it. Just thinking about a way for the Output to predict it's size instead of using WeightedUtxo.

[Kixunil]

That's a previous one, change is the new one.

[yancyribbens]

@Kixunil I added a PR to use InputWeightPrediction instead of cost_of_change: p2pderivatives/rust-bitcoin-coin-selection#37

[yancyribbens]

And perhaps make UTXO generic (at least it could be AsRef)

@Kixunil What about this?:

pub fn select_coins<T: WeightedUtxo>(
    target: Amount,
    fee_rate: FeeRate,
    change_weight_prediction: InputWeightPrediction,
    long_term_fee_rate: FeeRate,
    weighted_utxos: &[T],
) -> Option<std::vec::IntoIter<&T>> {

And the trait used in the trait bound:

/// The WeightedUtxo trait provides the necessary interfaces for coin-selection. 
pub trait WeightedUtxo {
    /// The weight of a UTXO once the spending conditions are satisfied.
    fn satisfaction_weight(&self) -> Weight;
    /// The concrete UTXO.
    fn utxo(&self) -> TxOut;
}

[yancyribbens]

Before bringing this crate into rust-bitcoin I'd like to see a fuzztest that attempts to produce various transactions with various feerates, and guarantees that we always hit the target (or fail to select).

@apoelstra is this still something you would like to see done? @murchandamus was able to give it a review but I think there might be some confusion because the project is in Rust (i'm still trying to get some clarification). I believe fuzz testing or model testing could be added to show all solutions are found. The other disagreement is if this is actually a depth first search which I think can be shown that it is. Part of the issue I'm running into is that there's not really anybody that seems to know bitcoin cores implementation well enough to code review and that also has the time/knowledge of rust to offer feedback. I guess in short - any help/advice here would be greatly appreciated.

[apoelstra]

At a minimum, yes, I would like to see fuzztesting that the code is never wrong in the "bad" direction.

But I would also like to see a reviewer signoff from somebody known and active in the rust-bitcoin community, and as you say, reviewer bandwidth is extremely limited which means that I don't know who or when will find time.

[yancyribbens]

Alright, thanks for the feedback. I'll add fuzz testing then to my todo list.

[yancyribbens]

I'm going to go ahead and merge p2pderivatives/rust-bitcoin-coin-selection#30 since it's unlikely I'll get anymore feedback. I think it's 100x better than the previous implementation. Also the benchmark times are comparable to the bitcoin core implementation. Furthermore, I'm convinced after the review, feedback and addition of more tests, that the implementation results are correct. Thanks to all those that provided reviews so far, it's very much appreciated!

[yancyribbens]

Merged.