Consolidate `amount_needed` and `fee_amount` in one parameter

[csralvall]

Currently, the coin_select method from CoinSelectionAlgorithm has
seven parameters.
One of them, amount_needed (the sum of the outgoing vout values) is only used
to compound the amount that the selected utxos must satisfy to create the
transaction.
Another parameter involved in that compounded amount is
fee_amount. It has two use cases. The first one, to pass the accumulated fees
for each txout and transaction’s header. The other is to accumulate
the resulting fees from the current selection (in LargestFirstCoinSelection
and OldestFirstCoinSelection).

Both parameters can be consolidated in one parameter like:

/// `target_amount`: the outgoing amount in satoshis and the fees already
///                  accumulated from added outputs and transaction’s header.

I think that this’ll still be valid in the future, as coin selection algorithms
consider those values fixed at the moment of coin_select. Also, the algorithm
would return only the fee_amount of the tx inputs in vin, which would reduce
the carry of the state through functions, remove the need for variable shadowing
and differentiate the vin fee amount from the rest of fees.

The following code illustrates some of the ideas above:

• New coin_select signature (old):

    fn coin_select(
        &self,
        database: &D,
        required_utxos: Vec<WeightedUtxo>,
        optional_utxos: Vec<WeightedUtxo>,
        fee_rate: FeeRate,
        target_amount: u64,
    ) -> Result<CoinSelectionResult, Error>;

• New CoinSelectionResult meaning (old):

/// Result of a successful coin selection
#[derive(Debug)]
pub struct CoinSelectionResult {
    /// List of outputs selected for use as inputs
    pub selected: Vec<Utxo>,
    /// Total fee amount for the selected utxos
    pub fee_amount: u64,
}

• New select_sorted_utxos (old):

fn select_sorted_utxos(
    utxos: impl Iterator<Item = (bool, WeightedUtxo)>,
    fee_rate: FeeRate,
    target_amount: u64,
) -> Result<CoinSelectionResult, Error> {
    let mut selected_amount = 0;
    let mut fee_amount = 0; // fee_amount is local
    let selected = utxos
        .scan(
            (&mut selected_amount, &mut fee_amount),
            |(selected_amount, fee_amount), (must_use, weighted_utxo)| {
            // target_amount doesn't change (fee_amount accumulates the selected utxos fees)
                if must_use || **selected_amount < target_amount + **fee_amount {
                    **fee_amount +=
                        fee_rate.fee_wu(TXIN_BASE_WEIGHT + weighted_utxo.satisfaction_weight);
                    **selected_amount += weighted_utxo.utxo.txout().value;
                    ...
                    Some(weighted_utxo.utxo)
                } else {
                    None
                }
            },
        )
        .collect::<Vec<_>>();
        ...
}

• Replace of actual_target in coin_select (old):

let actual_target = fee_amount + amount_needed;
actual_target = target_amount

• Change single_random_draw (old) and bnb (old) methods:

fn single_random_draw(
    &self,
    required_utxos: Vec<OutputGroup>,
    mut optional_utxos: Vec<OutputGroup>,
    curr_value: i64,
    target_amount: u64,
) -> CoinSelectionResult

fn bnb(
    &self,
    required_utxos: Vec<OutputGroup>,
    mut optional_utxos: Vec<OutputGroup>,
    mut curr_value: i64,
    mut curr_available_value: i64,
    target_amount: u64,
    cost_of_change: f32,
) -> Result<CoinSelectionResult, Error>

• Change calculate_cs_result (old):

fn calculate_cs_result(
    mut selected_utxos: Vec<OutputGroup>,
    mut required_utxos: Vec<OutputGroup>,
) -> CoinSelectionResult {
    selected_utxos.append(&mut required_utxos);
    let fee_amount = selected_utxos.iter().map(|u| u.fee).sum::<u64>();
    let selected = selected_utxos
        .into_iter()
        .map(|u| u.weighted_utxo.utxo)
        .collect::<Vec<_>>();

    CoinSelectionResult {
        selected,
        fee_amount,
    }
}

• Sum vin fee amount to total fee amount instead of using "variable shadowing"
  (old):

  fee_amount += coin_selection.fee_amount;

This implies some backward incompatible changes so I want to know if there is
support for this, and hear ideas/opinions before opening any PR.

[LLFourn]

Just wanted to leave a note that as part of my work on bdk_core I plan to re-engineer coin selection. The current list of parameters looks like:

#[derive(Debug, Clone, Copy)]
pub struct CoinSelectorOpt {
    /// The value we need to select.
    pub target_value: u64,
    /// The feerate we should try and achieve.
    pub target_feerate: f32,
    /// The minimum absolute fee.
    pub min_absolute_fee: u64,
    /// The weight of the template transaction including fixed inputs and outputs.
    pub base_weight: u32,
    /// The weight of the drain (change) output.
    pub drain_weight: u32,
    /// The input value of the template transaction.
    pub starting_input_value: u64,
}

In addition to this you pass in a list of possible UTXOs to select from. More big picture my idea would be to get rid of the CoinSelectionAlgorithm trait and change TxBuilder so it returns a CoinSelector. From there you can get your transaction when you satisfy the constraints of the coin selection.

Your changes sound reasonable to me and may be worth doing in the meantime. Getting bdk_core into bdk will take a few more months.

[danielabrozzoni]

Concept ACK, the change looks reasonable, and I find the current fee_amount/amount_needed to be definitely confusing :)

[csralvall]

Thank you both for your feedback! I opened #662 to bring more eyes to this.

I've not done a deep review of your proposal @LLFourn, just skimmed it, but
since you mentioned it. Are you thinking in TxBuilder as a module that
returns a coin selection "specification" or "contract" (CoinSelector) that must be fulfilled
by the used selection algorithm to create the final transaction?
Please, correct me if I'm wrong.
Also, I cannot interpretate the meaning of CoinSelectorOpt, what is it?