bitcoinjs
Adding Branch and Bound algorithm
https://github.com/bitcoinjs/coinselect/issues/10
In the end, I used the C++ code from core PR as a reference ( https://github.com/bitcoin/bitcoin/pull/10637 ), not the scala code.
It seems to be working, and performing rather well! Although it matches only in <10% of cases in the simulation, the reduction of the fees is significant.
The only question is what to take as a fallback. In the original paper and in the scala code that goes with it, random shuffle + accumulative is being used. In this module simulation, min+accumulative has the best results. (Even with the total costs from https://github.com/bitcoinjs/coinselect/pull/11 )
However, when I tried to implement the "minimal" fallback into the scala code, the utxo set in the big example exploded, which caused larger total cost, plus the BnB search was significantly slower.
As I wrote in the linked pull request, I will try to port the big example into this code, what will happen.
Code comments are welcome :) it's a big chunk of code. The comments in there are almost directly from the bitcoin-core PR
I will also try to port the bitcoin-core tests in the PR here.
(both the scala algorithm and the C++ implementations are MIT licence, as is this code :) )
I haven't done the tests yet; as I said "I will also try to port the bitcoin-core tests in the PR here", which I will do today :)
Np, lots of comments here :))
On Jul 6, 2017 8:46 AM, "Daniel Cousens" [email protected] wrote:
Sorry for the delay here, reading now.
— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/bitcoinjs/coinselect/pull/13#issuecomment-313310687, or mute the thread https://github.com/notifications/unsubscribe-auth/AAGZ8XRZA5BUk1_X3jtX53zJzV9zyXTvks5sLIKsgaJpZM4OLeIj .
Looks good to me, at least for merge/ongoing research/testing :) - not for release until everything is tested though.
Hey, I was not really able to look at the code (holiday :)), will go through the notes etc
Hm, I thought that for tests, I will copy blackjack tests, since they should be similar... but there are not blackjack tests :sob: :cry: ok then
Hm, I now have no idea, what to return in BnB algorithm as fee, when the algorithm fails to find a match
I will probably return just 0, since the strategy doesn't return anything meaningful for this.
I have added some tests (mostly copying from accumulative.json) and fixed NaN issues.
It should be working.
However, the costOfChange/costPerInput/costPerOutput will need to have a revision with segwit.
Hm. I don't know how to display the missed branches in the coverage...
edit: oh, nyc's HTML export is useful. Correcting, comitting.
Probably ready to merge now? Maybe the naming is confusing (bnb at some places, "branchandbound" at others)
OK, bcash is finally solved (what a time sink), so I have time to return back to work on this :)
I see bitcoin core have added a waste metric and bunch of other stuff to BnB
lol. Not from me :) I stopped working on any bitcoin-related stuff, 0 mood to return