-
Notifications
You must be signed in to change notification settings - Fork 9
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Do you recommend to use BnB in real wallet apps? #3
Comments
Oh only now I found this thesis http://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf and this thread |
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. |
Hey @Runn1ng, 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: bitcoin/bitcoin#10637 Note that not creating a change output prevents you from doing CPFP on your own transaction. |
Where is the lookahead vector in the c++ code? I cannot find it anywhere. The code uses 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. :) |
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. |
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.
The text was updated successfully, but these errors were encountered: