Implement BNB Selection

[rajarshimaitra]

Implement the BNB Coin selection algorithm and add tests via suitable test vectors.

BNB tries to select inputs in such a way that no change outputs are required. So the total value of the selected outputs should not exceed the target + dust value

You are expected to follow the thesis of Mark Erhard, Algorithm 10 closely. Here the author tries to explain the concepts by visualizing a tree but in reality we are not going to create the tree in our program but rather walk through the imaginary tree using recursion.

The user level public function

pub fn select_coin_bnb(
    inputs: Vec<OutputGroup>,
    options: CoinSelectionOpt,
) -> Result<SelectionOutput, SelectionError>

should follow Algorithm 9.

The private function

fn bnb(
    inputs_in_desc_value: &Vec<(usize, OutputGroup)>,
    selected_inputs: &[usize],
    effective_value: u64,
    depth: usize,
    bnp_tries: u32,
    options: &CoinSelectionOpt,
) -> Vec<usize>

should follow Algorithm 10. NOTE: mutation of variables should not happen rather those state changes should be passed on correctly in the recursive calls.

In order to do BNP we need to find the exact match so the effective value of a target is optimal rather than recomputing fee at every step. So implement the private function fn effective_value(output: &OutputGroup, option: &CoinSelectionOpt) -> u64 first.

For practical purposes we are not going to explore all possible subsets and we want the algorithm to finish faster. So bnp_tries are decremented for every recursion call and if it reaches 0, terminate the search.

Read the code of generating subsets for understanding, how to manipulate selections using Vec.

Read the implementation of SRD on how to calculate fee and waste.

[i-am-yuvi]

I'll give it a try!!

[i-am-yuvi]

is this still open?? @delcin-raj ?

[NeoZ666]

29