bitcoin_coin_selection/
lib.rs

1//! Rust Bitcoin coin selection library.
2//!
3//! Efficient algorithms for choosing an optimal UTXO set.
4
5// Coding conventions.
6#![deny(non_upper_case_globals)]
7#![deny(non_camel_case_types)]
8#![deny(non_snake_case)]
9#![deny(unused_mut)]
10#![deny(missing_docs)]
11// Experimental features we need.
12#![cfg_attr(docsrs, feature(doc_cfg))]
13
14mod branch_and_bound;
15mod single_random_draw;
16
17/// Possible returned error types if no match is found.
18pub mod errors;
19
20use std::cmp::Ordering;
21
22use bitcoin_units::{Amount, FeeRate, SignedAmount, Weight};
23#[cfg(feature = "rand")]
24#[cfg_attr(docsrs, doc(cfg(feature = "rand")))]
25use rand::thread_rng;
26
27pub use crate::branch_and_bound::branch_and_bound;
28use crate::errors::{OverflowError, SelectionError};
29#[cfg(feature = "rand")]
30#[cfg_attr(docsrs, doc(cfg(feature = "rand")))]
31pub use crate::single_random_draw::single_random_draw;
32
33pub(crate) type Return<'a> = Result<(u32, Vec<&'a WeightedUtxo>), SelectionError>;
34
35// https://github.com/bitcoin/bitcoin/blob/f722a9bd132222d9d5cd503b5af25c905b205cdb/src/wallet/coinselection.h#L20
36const CHANGE_LOWER: Amount = Amount::from_sat_u32(50_000);
37
38/// Computes the value of an output accounting for the cost to spend it.
39///
40/// The effective_value can be calculated as: value - (fee_rate * weight).
41///
42/// Note: the effective value of a `Transaction` may increase less than the effective value of
43/// a `TxOut` when adding another `TxOut` to the transaction. This happens when the new
44/// `TxOut` added causes the output length `VarInt` to increase its encoding length.
45///
46/// # Parameters
47///
48/// * `fee_rate` - the fee rate of the transaction being created.
49/// * `weight` - the utxo spending conditions weight.
50/// * `value` - the utxo value to spend.
51pub(crate) fn effective_value(
52    fee_rate: FeeRate,
53    weight: Weight,
54    value: Amount,
55) -> Option<SignedAmount> {
56    let signed_input_fee: SignedAmount = fee_rate.fee_wu(weight)?.to_signed();
57    let eff_value = (value.to_signed() - signed_input_fee).unwrap();
58    Some(eff_value)
59}
60
61#[derive(Debug, Clone, PartialEq, Eq)]
62/// Represents the spendable conditions of a `UTXO`.
63pub struct WeightedUtxo {
64    /// The `Amount` that the output contributes towards the selection target.
65    value: Amount,
66    /// The estimated `Weight` (satisfaction weight + base weight) of the output.
67    weight: Weight,
68    /// The positive effective value `(value - fee)`.  This value is stored as a `u64` for
69    /// better performance.
70    effective_value: u64,
71    /// The `SignedAmount` required to spend the output at the given `fee_rate`.
72    fee: SignedAmount,
73    /// The `SignedAmount` required to spend the output at the given `long_term_fee_rate`.
74    long_term_fee: SignedAmount,
75    /// A metric for how wasteful it is to spend this `WeightedUtxo` given the current fee
76    /// environment.
77    waste: i64,
78}
79
80impl WeightedUtxo {
81    /// Creates a new `WeightedUtxo`.
82    pub fn new(
83        value: Amount,
84        weight: Weight,
85        fee_rate: FeeRate,
86        long_term_fee_rate: FeeRate,
87    ) -> Option<WeightedUtxo> {
88        let positive_effective_value = Self::positive_effective_value(fee_rate, weight, value);
89
90        if let Some(effective_value) = positive_effective_value {
91            let fee = fee_rate.fee_wu(weight)?.to_signed();
92            let long_term_fee: SignedAmount = long_term_fee_rate.fee_wu(weight)?.to_signed();
93            let waste = Self::calculate_waste_score(fee, long_term_fee);
94            return Some(Self { value, weight, effective_value, fee, long_term_fee, waste });
95        }
96
97        None
98    }
99
100    /// Calculates if the current fee environment is expensive.
101    pub fn is_fee_expensive(&self) -> bool { self.fee > self.long_term_fee }
102
103    /// Returns the associated value.
104    pub fn value(&self) -> Amount { self.value }
105
106    /// Returns the associated weight.
107    pub fn weight(&self) -> Weight { self.weight }
108
109    /// Returns the calculated effective value.
110    pub fn effective_value(&self) -> Amount { Amount::from_sat(self.effective_value).unwrap() }
111
112    fn positive_effective_value(fee_rate: FeeRate, weight: Weight, value: Amount) -> Option<u64> {
113        if let Some(eff_value) = effective_value(fee_rate, weight, value) {
114            if let Ok(unsigned) = eff_value.to_unsigned() {
115                return Some(unsigned.to_sat());
116            }
117        }
118
119        None
120    }
121
122    fn calculate_waste_score(fee: SignedAmount, long_term_fee: SignedAmount) -> i64 {
123        fee.to_sat() - long_term_fee.to_sat()
124    }
125}
126
127impl Ord for WeightedUtxo {
128    fn cmp(&self, other: &Self) -> Ordering {
129        other.effective_value.cmp(&self.effective_value).then(self.weight.cmp(&other.weight))
130    }
131}
132
133impl PartialOrd for WeightedUtxo {
134    fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(other)) }
135}
136
137/// Attempt a match with [`branch_and_bound`] falling back to [`single_random_draw`].
138///
139/// If [`branch_and_bound`] fails to find a changeless solution (basically, an exact match), then
140/// run [`single_random_draw`] and attempt a random selection.  This solution is also employed by
141/// the Bitcoin Core wallet written in C++.  Therefore, this implementation attempts to return the
142/// same results as one would find if running the Core wallet.
143///
144/// If the maximum weight is exceeded, then the least valuable inputs are removed from the current
145/// selection using weight as a tie breaker.  In so doing, minimize the number of UTXOs included
146/// by preferring more valuable UITXOs in the result.
147///
148/// # Parameters
149///
150/// * target: Target spend `Amount`.
151/// * cost_of_change: The `Amount` needed to produce a change output.
152/// * `max_weight` - the maximum selection weight allowed.
153/// * weighted_utxos: The candidate Weighted UTXOs from which to choose a selection from.
154///
155/// # Returns
156///
157/// The best solution found and the number of iterations to find it.  Note that if the iteration
158/// count equals `ITERATION_LIMIT`, a better solution may exist than the one found.
159///
160/// # Errors
161///
162/// If an arithmetic overflow occurs, the target can't be reached, or an un-expected error occurs.
163/// That is, if sufficient funds are supplied, and an overflow does not occur, then a solution
164/// should always be found.  Anything else would be an un-expected program error which ought never
165/// happen.
166#[cfg(feature = "rand")]
167#[cfg_attr(docsrs, doc(cfg(feature = "rand")))]
168pub fn select_coins(
169    target: Amount,
170    cost_of_change: Amount,
171    max_weight: Weight,
172    weighted_utxos: &[WeightedUtxo],
173) -> Return<'_> {
174    let bnb_result = branch_and_bound(target, cost_of_change, max_weight, weighted_utxos);
175
176    if bnb_result.is_err() {
177        single_random_draw(target, max_weight, &mut thread_rng(), weighted_utxos)
178    } else {
179        bnb_result
180    }
181}
182
183#[cfg(test)]
184mod tests {
185    use std::str::FromStr;
186
187    use arbitrary::{Arbitrary, Result, Unstructured};
188    use arbtest::arbtest;
189    use bitcoin_units::{Amount, CheckedSum, Weight};
190
191    use super::*;
192    use crate::SelectionError::{InsufficentFunds, Overflow, ProgramError};
193
194    pub fn build_pool() -> Vec<WeightedUtxo> {
195        let amts = [27_336, 238, 9_225, 20_540, 35_590, 49_463, 6_331, 35_548, 50_363, 28_009];
196        let weight = Weight::ZERO;
197        let fee_rate = FeeRate::ZERO;
198        let lt_fee_rate = FeeRate::ZERO;
199
200        let utxos: Vec<_> = amts
201            .iter()
202            .filter_map(|a| {
203                let amt = Amount::from_sat_u32(*a);
204                WeightedUtxo::new(amt, weight, fee_rate, lt_fee_rate)
205            })
206            .collect();
207
208        utxos
209    }
210
211    pub fn assert_ref_eq(inputs: Vec<&WeightedUtxo>, expected: Vec<WeightedUtxo>) {
212        let expected_ref: Vec<&WeightedUtxo> = expected.iter().collect();
213        assert_eq!(inputs, expected_ref);
214    }
215
216    pub fn assert_target_selection(
217        utxos: &Vec<&WeightedUtxo>,
218        target: Amount,
219        upper_bound: Option<Amount>,
220    ) {
221        let utxos: Vec<WeightedUtxo> = utxos.iter().map(|&u| u.clone()).collect();
222        let eff_value_sum = Selection::effective_value_sum(&utxos).unwrap();
223        assert!(eff_value_sum >= target);
224
225        if let Some(ub) = upper_bound {
226            assert!(eff_value_sum <= ub);
227        }
228    }
229
230    pub(crate) fn parse_fee_rate(f: &str) -> FeeRate {
231        let rate_parts: Vec<_> = f.split(" ").collect();
232        let rate = rate_parts[0].parse::<u32>().unwrap();
233
234        match rate_parts.len() {
235            1 => {
236                assert!(rate == 0, "Try adding sat/kwu or sat/vB to fee_rate");
237                FeeRate::ZERO
238            }
239
240            2 => match rate_parts[1] {
241                "sat/kwu" => FeeRate::from_sat_per_kwu(rate),
242                "sat/vB" => FeeRate::from_sat_per_vb(rate),
243                "0" => FeeRate::ZERO,
244                _ => panic!("only support sat/kwu or sat/vB rates"),
245            },
246
247            _ => panic!("number, space then rate not parsed.  example: 10 sat/kwu"),
248        }
249    }
250
251    #[derive(Debug)]
252    pub struct Selection {
253        pub utxos: Vec<WeightedUtxo>,
254        pub fee_rate: FeeRate,
255        pub long_term_fee_rate: FeeRate,
256    }
257
258    impl<'a> Arbitrary<'a> for Selection {
259        fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
260            let init: Vec<(Amount, Weight)> = Vec::arbitrary(u)?;
261            let fee_rate = FeeRate::arbitrary(u)?;
262            let long_term_fee_rate = FeeRate::arbitrary(u)?;
263            let utxos: Vec<WeightedUtxo> = init
264                .iter()
265                .filter_map(|i| WeightedUtxo::new(i.0, i.1, fee_rate, long_term_fee_rate))
266                .collect();
267
268            Ok(Selection { utxos, fee_rate, long_term_fee_rate })
269        }
270    }
271
272    // TODO check about adding this to rust-bitcoins from_str for Weight
273    fn parse_weight(weight: &str) -> Weight {
274        let size_parts: Vec<_> = weight.split(" ").collect();
275        let size_int = size_parts[0].parse::<u64>().unwrap();
276        match size_parts[1] {
277            "wu" => Weight::from_wu(size_int),
278            "vB" => Weight::from_vb(size_int).unwrap(),
279            _ => panic!("only support wu or vB sizes"),
280        }
281    }
282
283    impl Selection {
284        pub fn new(utxos: &[&str], fee_rate: FeeRate, long_term_fee_rate: FeeRate) -> Selection {
285            let utxos: Vec<_> = utxos
286                .iter()
287                .filter_map(|u| {
288                    let val_with_size: Vec<_> = u.split("/").collect();
289                    let weight = parse_weight(val_with_size[1]);
290                    let val = val_with_size[0];
291
292                    let abs_val = if val.starts_with("e") {
293                        let val = val.replace("e(", "").replace(")", "");
294                        let eff_value = SignedAmount::from_str(&val).unwrap();
295                        compute_absolute_value(eff_value, weight, fee_rate)
296                    } else {
297                        Amount::from_str(val).unwrap()
298                    };
299
300                    WeightedUtxo::new(abs_val, weight, fee_rate, long_term_fee_rate)
301                })
302                .collect();
303
304            Selection { utxos, fee_rate, long_term_fee_rate }
305        }
306
307        fn effective_value_sum(utxos: &[WeightedUtxo]) -> Option<Amount> {
308            utxos.iter().map(|u| u.effective_value()).checked_sum()
309        }
310
311        pub fn available_value(&self) -> Option<Amount> { Self::effective_value_sum(&self.utxos) }
312
313        pub fn weight_total(&self) -> Option<Weight> {
314            self.utxos.iter().map(|u| u.weight()).try_fold(Weight::ZERO, Weight::checked_add)
315        }
316    }
317
318    pub fn compute_absolute_value(
319        effective_value: SignedAmount,
320        weight: Weight,
321        fee_rate: FeeRate,
322    ) -> Amount {
323        let signed_fee = fee_rate.fee_wu(weight).unwrap().to_signed();
324        let signed_absolute_value = (effective_value + signed_fee).unwrap();
325        signed_absolute_value.to_unsigned().unwrap()
326    }
327
328    #[test]
329    fn weighted_utxo_constructor_overflow() {
330        let value = Amount::from_sat_u32(100);
331        let weight = Weight::MAX;
332        let fee_rate = FeeRate::MAX;
333        let long_term_fee_rate = FeeRate::MAX;
334
335        let utxo = WeightedUtxo::new(value, weight, fee_rate, long_term_fee_rate);
336        assert!(utxo.is_none());
337    }
338
339    #[test]
340    fn weighted_utxo_constructor_negative_eff_value() {
341        let value = Amount::from_sat_u32(1);
342        let weight = Weight::from_vb(68).unwrap();
343        let fee_rate = FeeRate::from_sat_per_kwu(20);
344        let long_term_fee_rate = FeeRate::from_sat_per_kwu(20);
345
346        let utxo = WeightedUtxo::new(value, weight, fee_rate, long_term_fee_rate);
347        assert!(utxo.is_none());
348    }
349
350    #[test]
351    fn select_coins_no_solution() {
352        // Test the code branch where both SRD and BnB fail.
353        let target = Amount::from_sat_u32(255432);
354        let cost_of_change = Amount::ZERO;
355        let max_weight = Weight::from_wu(40_000);
356        let pool = build_pool(); // eff value sum 262643
357
358        let result = select_coins(target, cost_of_change, max_weight, &pool);
359
360        match result {
361            Err(crate::SelectionError::InsufficentFunds) => {}
362            _ => panic!("un-expected result: {:?}", result),
363        }
364    }
365
366    #[test]
367    fn select_coins_srd_solution() {
368        let target = (Amount::from_sat_u32(255432) - CHANGE_LOWER).unwrap();
369        let cost_of_change = Amount::ZERO;
370        let max_weight = Weight::from_wu(40_000);
371        let pool = build_pool();
372
373        let result = select_coins(target, cost_of_change, max_weight, &pool);
374        let (_iterations, utxos) = result.unwrap();
375        let sum: Amount = utxos.into_iter().map(|u| u.value()).checked_sum().unwrap();
376        assert!(sum > target);
377    }
378
379    #[test]
380    fn select_coins_bnb_solution() {
381        let target = Amount::from_sat_u32(255432);
382        let max_weight = Weight::from_wu(40_000);
383        let pool = build_pool();
384
385        // set cost_of_change to be the difference
386        // between the total pool sum and the target amount
387        // plus 1.  This creates an upper bound that the sum
388        // of all utxos will fall bellow resulting in a BnB match.
389        let cost_of_change = Amount::from_sat_u32(7211);
390
391        let result = select_coins(target, cost_of_change, max_weight, &pool);
392        let (iterations, utxos) = result.unwrap();
393        let sum: Amount = utxos.into_iter().map(|u| u.value()).checked_sum().unwrap();
394        assert!(sum > target);
395        assert!(sum <= (target + cost_of_change).unwrap());
396        assert_eq!(16, iterations);
397    }
398
399    #[test]
400    fn select_coins_proptest() {
401        arbtest(|u| {
402            let candidate_selection = Selection::arbitrary(u)?;
403            let target = Amount::arbitrary(u)?;
404            let cost_of_change = Amount::arbitrary(u)?;
405            let max_weight = Weight::arbitrary(u)?;
406
407            let candidate_utxos = candidate_selection.utxos.clone();
408            let result = select_coins(target, cost_of_change, max_weight, &candidate_utxos);
409
410            match result {
411                Ok((i, utxos)) => {
412                    assert!(i > 0);
413                    crate::tests::assert_target_selection(&utxos, target, None);
414                }
415                Err(InsufficentFunds) => {
416                    let available_value = candidate_selection.available_value().unwrap();
417                    assert!(available_value < (target + CHANGE_LOWER).unwrap());
418                }
419                Err(Overflow(_)) => {
420                    let available_value = candidate_selection.available_value();
421                    let weight_total = candidate_selection.weight_total();
422                    assert!(
423                        available_value.is_none()
424                            || weight_total.is_none()
425                            || target.checked_add(CHANGE_LOWER).is_none()
426                    );
427                }
428                Err(ProgramError) => panic!("un-expected program error"),
429                _ => {}
430            }
431
432            Ok(())
433        });
434    }
435}
bitcoin_coin_selection/lib.rs

bitcoin_coin_selection/
lib.rs
