search

p2pderivatives / rust-bitcoin-coin-selection

10 stars 5 forks source link

Examine all possible combinations #21

Closed yancyribbens closed 8 months ago

yancyribbens commented 1 year ago

Closes https://github.com/p2pderivatives/rust-bitcoin-coin-selection/issues/20

Try all possible combinations and record the best match. This is of course very slow and needs to be improved before is ready to use on large size UTXO pools. The number of possible combinations of a pool size of nwould be:

The summation (sigma) for k from i..n of C(n, k)= n!/[k!(n-k)!]

murchandamus commented 1 year ago

Ah, I just reread your comment on rust-bitcoin. Yeah, waste metric would seem higher priority than speeding up BnB. In fact, I would probably implement handling of fee rates and effective values first to ensure that your input selections can actually pay for the transaction, get that to work with a simple algorithm like SRD, then implement waste metric as a fitness function to pick among multiple candidates, then move on to more complex solution approaches like BnB.

yancyribbens commented 1 year ago

@Xekyo thanks for the feedback. I've added effective values in a simple algorithm (SRD) https://github.com/p2pderivatives/rust-bitcoin-coin-selection/pull/22. I think it would make sense to address the remainder of the comments you made when I create the next PR with an updated BnB selection algorithm.

yancyribbens commented 8 months ago

closing in favor of https://github.com/p2pderivatives/rust-bitcoin-coin-selection/pull/30