Coin Selection with Murch’s algorithm #10637

This is an implementation of the Branch and Bound coin selection algorithm written by Murch (@xekyo). I have it set so this algorithm will run first and if it fails, it will fall back to the current coin selection algorithm. The coin selection algorithms and tests have been refactored to separate files instead of having them all in wallet.cpp.

I have added some tests for the new algorithm and a test for all of coin selection in general. However, more tests may be needed, but I will need help with coming up with more test cases.

This PR uses some code borrowed from #10360 to use effective values when selecting coins.

Have you tested the effect of random exploration vs largest first exploration?

• Either way, BranchAndBound already guarantees that the global utxo set doesn’t grow (for one output transactions) due to saving the change output.
• LFE guarantees the creation of a minimal input set, and purposefully finds a possible solution. This should minimize the input set size variance. In my simulations BranchAndBound with LFE already caused a smaller average UTXO footprint than legacy Core selection.
• Random Exploration could find a larger input set by skipping a key UTXO higher up in the tree. This could lead to the selection of a larger number of inputs, or in an edge case could even cause tries to be exhausted before a solution is found. This may increase input set variance, or could perhaps even exhaust small UTXOs too quickly for BnB to often find a viable solution.

I am not sure there is a significant privacy benefit for Random Exploration as for either selection method an attacker would already need to know about another eligible input that would achieve an exact match when switched out for one of the input set.

What benefit do you expect from using Random Exploration?

Noting that this PR has fairly heavy overlap with #10360 .

From chatting with @achow101 the intention of this PR is to touch as little as possible while still getting BranchNBound coin selection.

To make this successful it should really only be run on first iteration of the loop in CreateTransaction, when nFeeRet == 0 and only use effective value for the BnB coin selection step, rather than the knapsack as well. Once nFeeRet becomes more than zero, interactions start to get strange without a more complete overhaul like #10360.

@sipa one question is if we should allow the wallet to consider consolidation-level prices for that change. Perhaps the user is in a hurry now, but would consider spending that change at a much slower pace.

Maybe for a first pass only consider the selected feerate, then Future Work allow a parameter which has more aggressive change protection given longer timescales.

just fyi, I have used your code as a reference for this code

https://github.com/bitcoinjs/coinselect/pull/13

I have to say, I don’t understand the target size; maybe there is a bug there.

In wallet.cpp, in CWallet::CreateTransaction, you create nValue, which seems to be the sum of all the outputs. Because the BnB is used only at the first pass, nFeeRet is 0 and nValueToSelect is just the sum of all the outputs.

This is then used as the exact target in the BnB algorithm.

However, you should add the cost of the outputs + the small cost of the tx overhead into the target (done here for the simple case on 1 output - https://github.com/Xekyo/CoinSelectionSimulator/blob/master/src/main/scala/one/murch/bitcoin/coinselection/StackEfficientTailRecursiveBnB.scala#L28 )

Maybe it’s done somewhere, but I don’t see it.

That eff. value accounts for the inputs of the new transaction, but not for the outputs (plus the overhead of the tx itself, but that is only about 10 bytes).

In SelectCoinsMinConf, you already have the target, which does not account for that.

@achow101 for some reason, when I do simulations either on @Xekyo set (in scala) or on bitcoinjs randomly generated data (with the algo rewritten into javascript), the total fees are actually lower when I make the target lower (that is, when I do not include the output cost in the target). So maybe tightening the target rejects more transactions and then the fallbacks somehow make better results.

I will investigate more when I have the time and write results here https://github.com/Xekyo/CoinSelectionSimulator/issues/5

[…]the total fees are actually lower when I make the target lower (that is, when I do not include the output cost in the target). @runn1ng: Um wait. “Target” is the amount to be selected. We are talking about the “cost of change” parameter that gives the leniency window for the exact match, right? Also, do you mean “input cost” instead of “output cost”?

It would be lovely if you could post your experiment’s results somewhere, so we all have the same dataset to discuss.

edit: ignore the graphs, see comment below

 0
 1~~~Anyway. I tried changing the cost of change on your scala code, as I wrote here - https://github.com/Xekyo/CoinSelectionSimulator/pull/8 . Now I tried values from 0 to 100 as percent, and this is the result (note that left axis doesn't start at 0)~~~
 2
 3![chart](https://user-images.githubusercontent.com/104945/28156350-aae80dca-67b2-11e7-810e-61eb70867996.png)
 4
 5[google spreadsheet link](https://docs.google.com/spreadsheets/d/1ePfoi08uV_QU48Q68aAu6apB-BG9DwM52JRgxNgSWPk/edit?usp=sharing)
 6
 7~~~x axis is how much percent of the current cost of change is used; y axis is total cost on the big honeypot data set.~~~
 8
 9~~~On the small random test cases there is no difference (what matters more there is the fallback, but that's for another experiment).~~~
10
11~~~Note that there was a [typo](https://github.com/Xekyo/CoinSelectionSimulator/pull/4/files) in the original experiments for the paper, which makes the cost of change "factor" 83%~~~

edit: ignore the graphs, see comment below

0
1~~~If you I try the same at the bitcoinjs example - [defined here](https://github.com/bitcoinjs/coinselect/blob/master/stats/index.js#L9) - small random examples with relatively few utxos - the graph looks completely different, and very dependent on what is a "backup plan" in the case of not found match~~~
2
3![chart 1](https://user-images.githubusercontent.com/104945/28161722-d7710484-67c4-11e7-84cd-09f86393622c.png)
4
5[google sheet](https://docs.google.com/spreadsheets/d/1zUen5aiKfDwRIRkOg-QJgAE0uEn-_OsrSUQwJm2xWDs/edit?usp=sharing)
6
7~~~"rand" is random, "min" is sorting the utxos from the biggest to the lowest and starting from the biggest. (Both are total cost.) I am not sure what "min" strategy does on the big data.~~~
8
9~~~(Just for interest, when I tried 100-200%, the graph goes up again, but not that quickly)~~~

edit: ignore the graphs, see comment below

0
1![chart 2](https://user-images.githubusercontent.com/104945/28207255-47c33440-6889-11e7-9e50-dcfcc444c81e.png)
2
3~~~Again, it's always better to take the "minimal" strategy (that is, to sort utxos by value size descending, and then take from the start until it's enough).~~~
4
5~~~If you want to replicate this experiment - note that it takes, for reasons I don't understand, terribly long time, and you will have to parallelize the simulation - luckily, that's trivial with scala paralel collections - see the commits at https://github.com/runn1ng/CoinSelectionSimulator/tree/exp_multi~~~
6
7~~~I would like to hear [@Xekyo](/bitcoin-bitcoin/contributor/xekyo/) opinions :)~~~
8
9~~~Also I would like to try this PR strategy, that is, to take the current core strategy as a backup.... but that is too complicated (especially in the javascript code), so I won't do it.~~~

@runn1ng: re random data: I’d surmise that BnB doesn’t perform well on small datasets as there are too few possible combinations. That could easily cause the fallback algorithm to dominate.

re moneypot: What I do find confusing is that your total cost is so much higher than my result with Branch and Bound + Single Random Draw of 58,940,772.30. Were you still running with fixed fees of 10000 satoshi/kB?

I haven’t comprehensively tested all possible fallback algorithms, it is possible that Largest First selection as a fallback to BnB is more efficient as it doesn’t take away as many small utxo that can be used to create combinations.

Do I understand correctly that you calculated “cost of change” and then took a percentage of that, or is this percentage only on the cost of the input? If you did the former, it appears that using just the cost of an additional output as “cost of change” leads to a minimum, considering that 34 bytes is 18.7% of what I proposed as “cost of change” with output+input.

What I do find confusing is that your total cost is so much higher than my result with Branch and Bound + Single Random Draw of 58,940,772.30. Were you still running with fixed fees of 10000 satoshi/kB?

That is weird indeed.

I am running code from your repo. To be sure I reverted all my local changes and I still get 72506973.

When I made the correction here https://github.com/Xekyo/CoinSelectionSimulator/pull/9 , I get total cost 70858076

I use only StackEfficientTailRecursiveBnB, should I try the other BnBs? edit: well, they get stack overflow, so I won’t. :D

I get totally different numbers than in your paper with the other scenarios too. The numbers don’t correspond to neither of the three tables, unfortunately.

edit: oooh, that’s because I am running “MoneyPot After LF”, which was the default scenario, but it’s actually with additional UTXOs from a previous run. The actual scenario from the paper (the first one) is TestCaseMoneyPotEmpty, right.

I found out that the two repos for coinselect simulation returned different results for the same strategy, so I painstakingly went through both of them and found where they differ… and put tons of of PRs to both, so they now both return the same results with the same fees + setup

The differences in simulations were:

• how they deal with insufficient funds (and how they detect it)
• what is minimum change
• what are the sizes of “defaut” input/output
• some small bugs

…and those added to significant differences. Anyway, when I fixed all the issues, those are the results/graphs I get:

this is for the moneypot scenario, with the fees 10 sat/bitcoin

google sheet

this is for the moneypot scenario, when I increase the fee to 200 sat/bitcoin (but I left the values, so more utxos become unspendable)

google sheet

In both, rand is slightly better. I am not sure what happened, if it’s because the scenario is different (without the large UTXO set) or because of the subtle differences in benchmarking. The shape is similar though.

This is the scenario of small randomly generated wallets

google sheet

BnB+LF performs better, optimum about 50% cost of change.

So, different strategies/parameters are better at different scenarios. Again, there is danger of overfitting on one scenario - plus there might be some more subtle bugs in the benchmark code… in my wallet code, I will probably just use BnB+LF with 50% of cost and call it a day :)

I haven’t shown this in graphs, but having BnB is always better than not having it. :)

If you want to repeat the tests, my forks of the repos are here 1 2

@Xekyo

Do I understand correctly that you calculated “cost of change” and then took a percentage of that, or is this percentage only on the cost of the input? If you did the former, it appears that using just the cost of an additional output as “cost of change” leads to a minimum, considering that 34 bytes is 18.7% of what I proposed as “cost of change” with output+input.

Hm, that doesn’t seem to be the case, the minimum is not 18%, but 30% to 50% on these two scenarios.

@achow101

@runn1ng would you be able to try the strategy with Core’s current selector as fallback? The easiest way to do that would be to add/modify the test cases for coin selection.

Hm, I already spent too much time on this… :/ I will see if I have time to look into the bitcoin coin selection tests and how to add benchmarks there, but not promising anything.

@instagibbs

I think - and that’s a speculation - that it’s because the target is “tighter”, so the BnB will reject more “lose” matches and will continue searching until it finds better match. So less fee is spent then, even when some matches are rejected that didn’t have to be (and those spend more on fees).

Btw. An interesting thing I just noticed - in the “small random” example, there is not that many BnB matches in the first place! Around 30 (out of 10.000 transactions). It still has an effect on the result…

I have squashed this even more (by getting a diff and re-committing) and hopefully made each commit a more logical chunk of code.

I have also changed this to use the discard fee rate for the change fee rate. The cost of change is also now calculated with the fee rate for making an output being the effective fee rate (fee rate being used) and the fee rate for spending the change being the discard fee rate.

The original commits are available in a separate branch here: https://github.com/achow101/bitcoin/tree/bnb-coin-select-orig (just in case I screwed something up).

@achow101 Travis failure is due to some weird behavior of travis to merge in latest master, but keep the yaml or config from the past (maybe when the pull was created).

You might be able to fix it by force pushing the last commit (EDITOR=true git commit --amend && git push origin bnb-coin -f) or just rebase on master.

@achow101 I cannot find it in the comments anymore, but you asked me for the simulation data some time ago

I tried the simulation on two targets.

First scenario (moneypot scenario) is I think from here (note - large file; one line is one income/expense) https://github.com/Xekyo/CoinSelectionSimulator/tree/master/src/main/resources/scenarios

Second is randomly generated from here https://github.com/bitcoinjs/coinselect/blob/master/stats/index.js

It would probably be better if you run the c++ core code directly though; my simulations were on the javascript + scala code

I am looking at this commit

https://github.com/achow101/bitcoin/commit/0fb73ae532aab061d3df0be54579b6d40c1e93ff

I have to say, I don’t understand, why are long term fees used in the waste calculation and what exactly does this mean

0CCoinControl temp;
1temp.m_confirm_target = 1008;
2CFeeRate long_term_feerate = GetMinimumFeeRate(temp, ::mempool, ::feeEstimator, &feeCalc);

long_term_feerate will be some very small fee that guarantees send in 1008 blocks, right? Why is that used in the waste calculation?

Pieter pointed out that the algorithm doesn’t necessarily find the best solution when it discovers the first solution. However, it was then at first not clear how to make the trade-off between making the input set smaller or reducing the excess in the selection.

The idea is that during high fee rates, it might be beneficial to the user if a smaller input count is preferred in exchange for a higher excess, while at low fee rates, a higher input count might be acceptable to achieve a smaller excess.

We came up with the waste metric to combine both of these dimensions:

waste = excess + #inputs * (feeRate - longterm feeRate)

where excess is the amount that we overshoot the selection target, and the second term derives from how much more expensive it is to spend the inputs right now than we expect in the longterm.

The algorithm now doesn’t stop on the first solution, but continues to search for a solution with a lower waste metric (using that as another bound) until either it has searched all possibilities or runs into the maximum allowed tries.

I tried my javascript simulations with the additional code (the waste comparation) and it actually had slightly worse results (higher total cost)

BUT it might be some bug in the simulation, I don’t have that much time for experimenting right now

Some simulation that actually test the resulting total fees on a given scenario - similar to @Xekyo repo - but on actual bitcoin binary - would be probably nice. So the testing would be on this code and not on re-implementations.

I am thinking how hard would that be on regtest, with the current python qa testing framework.

Rebased this.

I’ll try to fix up some of the fee estimation things wrt segwit. @runn1ng I’ll see if I can do any sort of simulation stuff.

I have rebased this and added a new commit that uses an actual prototype change output and gets its size and spend size instead of hardcoding constants.

I finally have the time to work on simulations for this and will be doing so over the next few weeks. @karel-3d What are the axes of the simulation graphs that you posted earlier?

See #10637 (comment) for updated results

I figured out how to run simulations with this. https://github.com/achow101/bitcoin/tree/bnb-simulate contains the modifications and script that I am using to simulate the behavior. It uses the test framework to setup 2 nodes. One node will then mine a bunch of blocks and send money to the other node as the scenarios specify. Then the other node will spend from those UTXOs as the scenario specifies. At the end, a bunch of data is printed out.

All of this is done in test/functional/simulate-coinselection.py. Modify that file as necessary if you wan to run simulations.

There is also a modification there to print to the debug.log about whether BnB was used or not. To calculate the BnB usage, grep through the debug.log file. This will require running the simulation with --nocleanup so that the datadir is not removed after it completes.

I simulated BnB and compared that to the current coin selection behavior (cherry-picked the above commit and removed the printing to debug.log part). I used set the following parameters: -dustrelayfee=0 -paytxfee=0.00001000. Setting the dust relay fee to 0 is to allow the dust UTXOs to be added. The transaction fee rate was set to be a fixed 1 sat/byte.

The data from the above simulation is as follows:

The results from this aren’t very impressive, and that’s likely because the BnB algorithm was used for a very small percentage of the coin selections, less than 3%. I will be doing more simulations with different parameters and the other datasets.

See #10637 (comment) for updated results

Another simulation with the same dataset but with a fee of 10 sat/byte instead of 1.

The difference here is a bit more pronounced, but I’m not quite sure how to interpret this result. @Xekyo, can you comment?

One other thing I noticed is that, with these large datasets and trying to go through them as fast as possible, BnB does take a noticeably longer, but I think that is expected behavior. I don’t expect that to actually have that much of an impact in practice.

See #10637 (comment) for updated results

I’ve done several more simulations. I did simulations at 4 feerates, 1 sat/byte, 10 sat/byte, 100 sat/byte and 500 sat/byte for the 3 moneypot scenarios provided at https://github.com/Xekyo/CoinSelectionSimulator/tree/master/src/main/resources/scenarios.

Results

Derived-1L-2O scenario

derived-balanced.csv

moneypot.csv

@achow101 the axes are - X is how “tight” the target is - by which I mean, I took the cost of change and I multiplied it by a factor. So I took cost of change just X% of the cost in the original algorithm.

Y is total cost from Murch thesis (what is spent + what it costs to spend the resulting utxos).

Btw. I wrote @Xekyo it would be nice to make a BIP with this algorithm, so we don’t have to write “Murch algorithm” and have the algorithm specified as a BIP. (There are already BIPs that don’t describe the protocol, just wallet behaviour.)

See #10637 (comment) for updated results

I have done some more simulations, this time with a variable fee rate. The fee data I am using is pulled from https://bitcoinfees.info/. The fee files are available here.

There are two fee things, one of them has each fee rate repeated 8 times in a row, the other cycles through the list 8 times.

Results:

Derived-1L-2O scenario

derived-balanced.csv

moneypot.csv

There is a mismatch here with the “#changes created” and “BnB usage”. Every time you use BnB, there should no change be created. I would suspect that the “excess” from BnB is not being dropped to the benefits of the fees, but instead put into a change output?

Edit: oh, saw your comment upon send. Good, curious about new results!

See #10637 (comment) for updated results

Here are the new simulation results with all of the bugs fixed hopefully:

@achow101: Row 4 has “min input set” of 0, but a transaction must have at least one input. Why do you think did the BnB usage almost halve? Are you using the solution of the RandomSelector if it has a lower waste metric? Otherwise, I’d expect the BnB usage to increase with higher fees since the target window for a solution without a change output increases.

The minChange of 0.00005428 also seems oddly low. Did the wallet balance dip to zero in your simulation?

I’ve had another idea for an optimization of the exploration: We see a lot of unspent values duplicated at round figures (e.g. 0.1 BTC, 10,000 sats). When exploring the combination tree, we should never allow a second branch to place the same value in the same position.

E.g. before, when you would have the unspent set of one UTXO with 1,000,000 and 100 UTXO with 100,000, and are looking for a target of 1,150,000, you’d explore: 1,000,000 /
100,000(A) /
0 100,000(B) —–> Σ=1,200,000 –> too much, cut branch
100,000(C) —–> Σ=1,200,000 –> too much, cut branch … and once you’ve tried all 99 other 100 with 100,000(A), you’d try the remaining 98 100,000s with 100,000(B) and so forth.

If we don’t allow expanding a branch that has the same value at the same position this becomes:

1,000,000 /
| 100,000(A) | /
| 0 100,000(B) —–> Σ=1,200,000 –> too much, cut branch |
| 100,000(C-CV) —–> don’t expand, already considered 100,000 in combo with this 0th and 1st | 100,000(B-CV) —–> don’t expand, already considered 100,000 in combo with this 0th Done, no solution.

In practice this could be implemented by remembering the value of the last item that we backtracked from and requiring that any new UTXO we consider for that position is at least one satoshi smaller.

Row 4 has “min input set” of 0, but a transaction must have at least one input.

That’s strange. I’ll rerun that simulation.

Why do you think did the BnB usage almost halve?

I think that’s a consequence of the bug I fixed. The BnB usage in the previous simulations was the number of times that BnB was hit, but BnB wasn’t actually used for the actual coin selection; the normal normal coin selector was used. So some inputs weren’t actually consumed, and additional change outputs were created which would then allow for more hits with BnB as there are more UTXOs.

Are you using the solution of the RandomSelector if it has a lower waste metric

No, the random selector is not implemented yet.

The minChange of 0.00005428 also seems oddly low. Did the wallet balance dip to zero in your simulation?

I believe it did. Such low values of min change do line up with the min change values for the normal coin selector though.

When exploring the combination tree, we should never allow a second branch to place the same value in the same position.

We still need to take into account the waste though; two outputs with the same effective value could still have different waste values which may make one output more desireable than another even with the same values. When we backtrack, we aren’t always cutting off a branch; we could have backtracked in order to find something else with a lower waste value.

See #10637 (comment) for updated results

@Xekyo These are the new results for that one simulation. I think that was just a spurious error:

All of the valid results for varying fee rate simulations, but readable

We still need to take into account the waste though; two outputs with the same effective value could still have different waste values which may make one output more desireable than another even with the same values. When we backtrack, we aren’t always cutting off a branch; we could have backtracked in order to find something else with a lower waste value.

Okay: We should not allow two outputs with the same effective value and same waste. I guess that would mean that we should potentially sort the UTXO for BnB by effective value first and then by waste.