search

bitcoindevkit / coin-select

Tool to help you select inputs for making bitcoin transactions.
Other
12 stars 6 forks source link

Implement lowest fee metric correctly #13

Closed LLFourn closed 8 months ago

LLFourn commented 8 months ago

This replaces #11. This first commit just fixes the metric to make the tests fail. Note the previous calculation was overthinking it. The fee metric is just inputs - outputs + long_term_feerate * change_weight.

Next steps:

  1. Make ci actually run the tests and get them to fail.
  2. Fix the metric lower bound
LLFourn commented 8 months ago

This now includes a fix for the lowest fee metric. The bound function uses the simplification from #14 to precisely target the amount of negative effective value it could use to remove the change output which is the position of the possible lowest fee. This is where most of complexity of the code comes from and unfortunately the logic of this branch isn't being hit by the proptests. I tried playing around with the parameters of proptest and running a lot more times to hit it but it refused. I had to write a manual test to target this branch.

Also I made a change to branch and bound in 17cc8f234430720a734e42cef28f8f22fc82a766

We now score the branch before bounding its children. This allows the parent branch to improve the best score which may exclude its children (this leads to less iterations to find the best solution in one of the tests).

LLFourn commented 8 months ago

This is where most of complexity of the code comes from and unfortunately the logic of this branch isn't being hit by the proptests. I tried playing around with the parameters of proptest and running a lot more times to hit it but it refused.

I figured out why the tests weren't hitting it and fixed that: https://github.com/bitcoindevkit/coin-select/pull/13/commits/9e1cecd47dc369a863999696266f303940d9b45e

If we only add a drain when it wouldn't increase waste then it is impossible to decrease waste by adding a new input -- but the logic of the bound function has to account for this situation. So by using min_value_and_waste we never test it!