rust_coinselect/algorithms/
coingrinder.rs

1use crate::{
2    types::{
3        CoinSelectionOpt, OutputGroup, SelectionError, SelectionOutput, WasteMetric, TOTAL_TRIES,
4    },
5    utils::{
6        calculate_fee, calculate_fee_and_waste, insufficient_funds, prepare_output_groups,
7        PreparedOutputGroup,
8    },
9};
10
11#[derive(Debug, Clone)]
12struct BestSelection {
13    selected: Vec<usize>,
14    value: u64,
15    weight: u64,
16    input_count: usize,
17}
18
19impl BestSelection {
20    fn is_better_than(&self, other: &Self) -> bool {
21        self.weight < other.weight
22            || (self.weight == other.weight && self.value < other.value)
23            || (self.weight == other.weight
24                && self.value == other.value
25                && self.input_count < other.input_count)
26            || (self.weight == other.weight
27                && self.value == other.value
28                && self.input_count == other.input_count
29                && self.selected < other.selected)
30    }
31}
32
33/// Deterministic change-producing fallback issuing the least total weight to minimize the fee.
34///
35/// BnB is the changeless path. CoinGrinder is the fallback for when change is expected: it searches
36/// for a selection that covers the target and total fee, then minimizes selected input weight. This
37/// avoids the old least-change behavior where many tiny inputs could be linked together merely to
38/// shave the change amount down by a few sats.
39pub fn select_coin_coingrinder(
40    inputs: &[OutputGroup],
41    options: &CoinSelectionOpt,
42) -> Result<SelectionOutput, SelectionError> {
43    let insufficient_funds_error = insufficient_funds(inputs, options);
44    let mut inputs = prepare_output_groups(inputs, options)?;
45
46    inputs.sort_by(|a, b| {
47        b.value
48            .cmp(&a.value)
49            .then_with(|| a.weight.cmp(&b.weight))
50            .then_with(|| a.index.cmp(&b.index))
51    });
52
53    let mut remaining_value = vec![0u64; inputs.len() + 1];
54    for index in (0..inputs.len()).rev() {
55        remaining_value[index] = remaining_value[index + 1] + inputs[index].value;
56    }
57
58    let mut best = None;
59    let mut selected = Vec::new();
60    let mut tries = TOTAL_TRIES;
61    let base_fee = calculate_fee(
62        options.base_weight + options.change_weight,
63        options.target_feerate,
64    )
65    .max(options.min_absolute_fee);
66
67    search(
68        &inputs,
69        &remaining_value,
70        0,
71        0,
72        0,
73        0,
74        &mut selected,
75        options,
76        base_fee,
77        &mut best,
78        &mut tries,
79    )?;
80
81    let best = best.ok_or(insufficient_funds_error)?;
82    let (fee, waste) = calculate_fee_and_waste(options, best.value, best.weight)?;
83
84    Ok(SelectionOutput {
85        selected_inputs: best.selected,
86        waste: WasteMetric(waste),
87        fee,
88    })
89}
90
91#[allow(clippy::too_many_arguments)]
92fn search(
93    inputs: &[PreparedOutputGroup],
94    remaining_value: &[u64],
95    index: usize,
96    value: u64,
97    weight: u64,
98    input_count: usize,
99    selected: &mut Vec<usize>,
100    options: &CoinSelectionOpt,
101    base_fee: u64,
102    best: &mut Option<BestSelection>,
103    tries: &mut u32,
104) -> Result<(), SelectionError> {
105    if *tries == 0 || index >= inputs.len() {
106        return Ok(());
107    }
108    if value + remaining_value[index] < options.target_value + base_fee {
109        return Ok(());
110    }
111    if best.as_ref().is_some_and(|best| weight > best.weight) {
112        return Ok(());
113    }
114
115    *tries -= 1;
116
117    let candidate = &inputs[index];
118    let new_value = value + candidate.value;
119    let new_weight = weight + candidate.weight;
120    let new_input_count = input_count + candidate.input_count;
121    selected.push(candidate.index);
122
123    let required_value = options.target_value + base_fee;
124    if new_value >= required_value {
125        let candidate_best = BestSelection {
126            selected: selected.clone(),
127            value: new_value,
128            weight: new_weight,
129            input_count: new_input_count,
130        };
131        if best
132            .as_ref()
133            .is_none_or(|current| candidate_best.is_better_than(current))
134        {
135            *best = Some(candidate_best);
136        }
137    } else {
138        search(
139            inputs,
140            remaining_value,
141            index + 1,
142            new_value,
143            new_weight,
144            new_input_count,
145            selected,
146            options,
147            base_fee,
148            best,
149            tries,
150        )?;
151    }
152    selected.pop();
153
154    search(
155        inputs,
156        remaining_value,
157        index + 1,
158        value,
159        weight,
160        input_count,
161        selected,
162        options,
163        base_fee,
164        best,
165        tries,
166    )
167}
168
169#[cfg(test)]
170mod test {
171    use crate::{
172        algorithms::coingrinder::select_coin_coingrinder,
173        types::{basic_output_group, CoinSelectionOpt, ExcessStrategy, SelectionError},
174    };
175
176    fn setup_options(target_value: u64) -> CoinSelectionOpt {
177        CoinSelectionOpt {
178            target_value,
179            target_feerate: 1.0,
180            long_term_feerate: Some(1.0),
181            min_absolute_fee: 0,
182            base_weight: 0,
183            change_weight: 50,
184            change_cost: 20,
185            min_change_value: 100,
186            excess_strategy: ExcessStrategy::ToChange,
187        }
188    }
189
190    #[test]
191    fn test_coingrinder_prefers_lower_weight_over_lower_change() {
192        let inputs = vec![
193            basic_output_group(10_500, 100),
194            basic_output_group(4_000, 80),
195            basic_output_group(3_500, 80),
196            basic_output_group(3_000, 80),
197        ];
198
199        let result = select_coin_coingrinder(&inputs, &setup_options(10_000)).unwrap();
200        assert_eq!(result.selected_inputs, vec![0]);
201    }
202
203    #[test]
204    fn test_coingrinder_uses_multiple_inputs_when_needed() {
205        let inputs = vec![
206            basic_output_group(6_000, 90),
207            basic_output_group(5_000, 90),
208            basic_output_group(2_000, 50),
209        ];
210
211        let result = select_coin_coingrinder(&inputs, &setup_options(10_000)).unwrap();
212        let mut selected = result.selected_inputs;
213        selected.sort();
214        assert_eq!(selected, vec![0, 1]);
215    }
216
217    #[test]
218    fn test_coingrinder_insufficient_funds() {
219        let inputs = vec![basic_output_group(1_000, 100)];
220
221        let result = select_coin_coingrinder(&inputs, &setup_options(10_000));
222        assert!(matches!(
223            result,
224            Err(SelectionError::InsufficientFunds { .. })
225        ));
226    }
227}
rust_coinselect/algorithms/coingrinder.rs

rust_coinselect/algorithms/
coingrinder.rs
