test: Add algo assert to bnb_search_test #29206

Adds algo assertion to bnb_search tests. This also highlights a test bug here. The case where fees are high which should cause bnb to select fewer inputs isn't actually being tested here since the result is making assertion on what's returned by knapsack, not bnb.

<!--e57a25ab6845829454e8d69fc972939a-->

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

<!--006a51241073e994b41acfe9ec718e94-->

Code Coverage

For detailed information about the code coverage, see the test coverage report.

<!--021abf342d371248e50ceaed478a90ca-->

Reviews

See the guideline for information on the review process.

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

<!--174a7506f384e20aa4161008e828411d-->

Conflicts

Reviewers, this pull request conflicts with the following ones:

• #29532 (Refactor BnB tests by murchandamus)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

hmm it looks like now it is testing bnb for all cases and not any are knapsack. Maybe my branch was stale and after re-basing it is now correct.

Ah wait I see what happened. If the check for fee_rate is removed from bnb like I pointed out here: https://github.com/bitcoin/bitcoin/pull/26061/files there is no test failure. However, the reason there's no test failure when that is removed is not that there is no tests, because there is here https://github.com/bitcoin/bitcoin/blob/master/src/wallet/test/coinselector_tests.cpp#L403. However, if that is removed, the test still passes because it falls back to using knapsack. Anyway, by adding the assert for bnb algo name, the test will now fail if the results for knapsack are returned when we expect bnb to be tested.

Thanks @yancyribbens for your report. There are a number of issues with these tests specifically and the coinselector_tests suite in general. They recently resurfaced when we were addressing an issue with SFFO and BnB via #28994. In the specific test with result13, the 9 is a preselected input and therefore BnB is returning 9+1 instead of 10.

Either way, you are looking at hopefully soon obsoleted tests. In conjunction with that bugfix I started working on completely rewriting the coinselector_tests in #28985.

In the specific test with result13, the 9 is a preselected input and therefore BnB is returning 9+1 instead of 10.

Ok. The test reads that it expects [9, 1] as a result AFAICT and since the fee_rate is set to be high (fee_rate > long_term_feerate) it should be 10. I verified that the BnB algo is actually doing the correct thing, although it's good to know there are some fixes coming for the tests.

In the test case the 9 is pre-selected and therefore has to be used. This is why BnB returns 9+1 instead of 10.

Concept NACK

Tests should ensure that the expected outcome is achieved. The expected outcome here is that the coin selection process returns the input set that has the best waste score.

I don’t think it’s useful to require that the best input set was produced by BnB. While in our current implementation the best input set is guaranteed to be found by BnB, it is possible that future coin selection improvements would enable another algorithm to produce the same result. As such, requiring that BnB produced the input set is a layer violation that tests an implementation detail rather than the outcome.

I don’t think it’s useful to require that the best input set was produced by BnB

That's fine, however the tests in question are part of the bnb_search_test. So if it's not testing BnB, I feel like the tests should be moved to a different test. It's confusing imo to understand how BnB works if the tests cases labeled as bnb_search_test are not acutally testing bnb_search.

The presence of BnB ensures that these expected input set will be found. The presence of BnB does neither preclude another algorithm from finding the same solution, nor cause the BnB solution to be necessarily picked among two equivalent solutions produced by two different algorithms. Hence it does not make sense to require that the solution was produced by BnB, only that the best solution will be found.

The presence of BnB ensures that these expected input set will be found. The presence of BnB does neither preclude another algorithm from finding the same solution, nor cause the BnB solution to be necessarily picked among two equivalent solutions produced by two different algorithms. Hence it does not make sense to require that the solution was produced by BnB, only that the best solution will be found.

I noted earlier that my objection is that this test should go elsewhere then if it's not testing BnB. Also, as I demonstrated in a separate PR, I can remove a valuable part of the waste metric calculation and no test fails. Therefore this PR increases the test coverage by adding that code section to the test suite.

This PR does not seem to have conceptual support.