Do you recommend to use BnB in real wallet apps?

[karelbilek]

Hello,

I run to this code from the PDF, and I really like the BnB strategy, since it seems to have the "best results" (lowest total cost).

Do you recommend to use it in real-life apps? Are there some positives/negatives that you can think of?

Why am I asking. I am writing Trezor web wallet, we are currently using FIFO algorithm, but right now I am refactoring the logic and I am thinking of using coinselect library, and porting the BnB algorithm to this library. I am now porting your scala logic to JS.

[karelbilek]

Oh only now I found this thesis

http://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf

and this thread

https://github.com/bitcoin/bitcoin/issues/7664#issuecomment-258324747

[karelbilek]

Also, the paper doesn't mention the computational complexity of the Branch-and-Bound algorithm. It seems to me it has an upper limit on the number of tries, so it is O(n) where n is the number of utxos, but I am not completely sure.

[murchandamus]

Hey @runn1ng, I think that the algorithm works well to produce transactions that do not have a change output. With a tail recursive implementation it is pretty quick and can even work well on large utxo pools. It does not perform well on a set of utxo where there are lots of inputs that are smaller than the target but never add up to an exact match, which is why it should have some limit on exploring the otherwise exponential search tree.

For my simulation I let it fall back to random selection on the wallet's utxo pool which in combination worked even better than Bitcoin Core's selection at reducing the utxo pool, and produced the lowest average fees (under the assumption of constant fee rates throughout the simulation).

Andrew Chow is implementing it as a first pass for Bitcoin Core which will probably deploy it with 0.16: https://github.com/bitcoin/bitcoin/pull/10637

Note that not creating a change output prevents you from doing CPFP on your own transaction.

[karelbilek]

Where is the lookahead vector in the c++ code? I cannot find it anywhere.

The code uses remaining value that gets increased/decreased, I am not 100% sure if it does the same thing or not :D

edit: oh OK now I see it, the c++ code does the backtracking more explicitly and thus does't need the lookahead and computes it on the fly (if I understand correctly). I am not sure what is more efficient; the c++ code seems easier to read. :)

[murchandamus]

achow101 solved the lookahead by keeping track of the remainder while moving up and down on the UTXO set instead of calculating the values for each depth. Having the lookahead in a separate structure allows you to backtrack multiple steps at once if you also keep track of which utxo was last included. Don't think it matters much.