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 coin_grinder;
16mod single_random_draw;
17
18mod weighted_utxo;
19
20pub use crate::weighted_utxo::WeightedUtxo;
21
22/// Possible returned error types if no match is found.
23pub mod errors;
24
25use bitcoin_units::{Amount, FeeRate, SignedAmount, Weight};
26#[cfg(feature = "rand")]
27#[cfg_attr(docsrs, doc(cfg(feature = "rand")))]
28use rand::thread_rng;
29
30pub use crate::branch_and_bound::branch_and_bound;
31pub use crate::coin_grinder::coin_grinder;
32use crate::errors::{OverflowError, SelectionError};
33#[cfg(feature = "rand")]
34#[cfg_attr(docsrs, doc(cfg(feature = "rand")))]
35pub use crate::single_random_draw::single_random_draw;
36
37pub(crate) type Return<'a> = Result<(u32, Vec<&'a WeightedUtxo>), SelectionError>;
38
39// https://github.com/bitcoin/bitcoin/blob/f722a9bd132222d9d5cd503b5af25c905b205cdb/src/wallet/coinselection.h#L20
40const CHANGE_LOWER: Amount = Amount::from_sat_u32(50_000);
41
42/// Computes the value of an output accounting for the cost to spend it.
43///
44/// The effective_value can be calculated as: value - (fee_rate * weight).
45///
46/// Note: the effective value of a `Transaction` may increase less than the effective value of
47/// a `TxOut` when adding another `TxOut` to the transaction. This happens when the new
48/// `TxOut` added causes the output length `VarInt` to increase its encoding length.
49///
50/// # Parameters
51///
52/// * `fee_rate` - the fee rate of the transaction being created.
53/// * `weight` - the utxo spending conditions weight.
54/// * `value` - the utxo value to spend.
55pub(crate) fn effective_value(
56    fee_rate: FeeRate,
57    weight: Weight,
58    value: Amount,
59) -> Option<SignedAmount> {
60    let signed_input_fee: SignedAmount = fee_rate.to_fee(weight).to_signed();
61    let eff_value = (value.to_signed() - signed_input_fee).unwrap();
62    Some(eff_value)
63}
64
65/// Attempt a match with [`branch_and_bound`] falling back to [`single_random_draw`].
66///
67/// If [`branch_and_bound`] fails to find a changeless solution (basically, an exact match), then
68/// run [`single_random_draw`] and attempt a random selection.  This solution is also employed by
69/// the Bitcoin Core wallet written in C++.  Therefore, this implementation attempts to return the
70/// same results as one would find if running the Core wallet.
71///
72/// If the maximum weight is exceeded, then the least valuable inputs are removed from the current
73/// selection using weight as a tie breaker.  In so doing, minimize the number of UTXOs included
74/// by preferring more valuable UITXOs in the result.
75///
76/// # Parameters
77///
78/// * target: Target spend `Amount`.
79/// * cost_of_change: The `Amount` needed to produce a change output.
80/// * `max_weight` - the maximum selection weight allowed.
81/// * weighted_utxos: The candidate Weighted UTXOs from which to choose a selection from.
82///
83/// # Returns
84///
85/// A tuple `(u32, Vec<&'a WeightedUtxo>` is returned on success where `u32` is the number of
86/// iterations to find the solution and `Vec<&'a WeightedUtxo>` is the best found selection.
87/// Note that if the iteration count equals `ITERATION_LIMIT`, a better solution may exist than the
88/// one found.
89#[cfg(feature = "rand")]
90#[cfg_attr(docsrs, doc(cfg(feature = "rand")))]
91pub fn select_coins<'a, T: IntoIterator<Item = &'a WeightedUtxo> + std::marker::Copy>(
92    target: Amount,
93    cost_of_change: Amount,
94    max_weight: Weight,
95    weighted_utxos: T,
96) -> Return<'a> {
97    let bnb_result = branch_and_bound(target, cost_of_change, max_weight, weighted_utxos);
98
99    if bnb_result.is_err() {
100        single_random_draw(target, max_weight, &mut thread_rng(), weighted_utxos)
101    } else {
102        bnb_result
103    }
104}
105
106#[cfg(test)]
107mod tests {
108    use std::str::FromStr;
109
110    use arbitrary::{Arbitrary, Result, Unstructured};
111    use arbtest::arbtest;
112    use bitcoin_units::{Amount, Weight};
113
114    use super::*;
115    use crate::SelectionError::{InsufficentFunds, Overflow, ProgramError};
116
117    pub fn build_pool() -> Vec<WeightedUtxo> {
118        let amts = [27_336, 238, 9_225, 20_540, 35_590, 49_463, 6_331, 35_548, 50_363, 28_009];
119        let weight = Weight::ZERO;
120        let fee_rate = FeeRate::ZERO;
121        let lt_fee_rate = FeeRate::ZERO;
122
123        let utxos: Vec<_> = amts
124            .iter()
125            .filter_map(|a| {
126                let amt = Amount::from_sat_u32(*a);
127                WeightedUtxo::new(amt, weight, fee_rate, lt_fee_rate)
128            })
129            .collect();
130
131        utxos
132    }
133
134    pub fn assert_ref_eq(inputs: Vec<&WeightedUtxo>, expected: Vec<WeightedUtxo>) {
135        let expected_ref: Vec<&WeightedUtxo> = expected.iter().collect();
136        assert_eq!(inputs, expected_ref);
137    }
138
139    pub fn assert_target_selection(
140        utxos: &Vec<&WeightedUtxo>,
141        target: Amount,
142        upper_bound: Option<Amount>,
143    ) {
144        let utxos: Vec<WeightedUtxo> = utxos.iter().map(|&u| u.clone()).collect();
145        let eff_value_sum = Selection::effective_value_sum(&utxos).unwrap();
146        assert!(eff_value_sum >= target);
147
148        if let Some(ub) = upper_bound {
149            assert!(eff_value_sum <= ub);
150        }
151    }
152
153    pub(crate) fn parse_fee_rate(f: &str) -> FeeRate {
154        let rate_parts: Vec<_> = f.split(" ").collect();
155        let rate = rate_parts[0].parse::<u32>().unwrap();
156
157        match rate_parts.len() {
158            1 => {
159                assert!(rate == 0, "Try adding sat/kwu or sat/vB to fee_rate");
160                FeeRate::ZERO
161            }
162
163            2 => match rate_parts[1] {
164                "sat/kwu" => FeeRate::from_sat_per_kwu(rate),
165                "sat/vB" => FeeRate::from_sat_per_vb(rate),
166                "0" => FeeRate::ZERO,
167                _ => panic!("only support sat/kwu or sat/vB rates"),
168            },
169
170            _ => panic!("number, space then rate not parsed.  example: 10 sat/kwu"),
171        }
172    }
173
174    #[derive(Debug)]
175    pub struct Selection {
176        pub utxos: Vec<WeightedUtxo>,
177        pub fee_rate: FeeRate,
178        pub long_term_fee_rate: FeeRate,
179    }
180
181    impl<'a> Arbitrary<'a> for Selection {
182        fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
183            let init: Vec<(Amount, Weight)> = Vec::arbitrary(u)?;
184            let fee_rate = FeeRate::arbitrary(u)?;
185            let long_term_fee_rate = FeeRate::arbitrary(u)?;
186            let utxos: Vec<WeightedUtxo> = init
187                .iter()
188                .filter_map(|i| WeightedUtxo::new(i.0, i.1, fee_rate, long_term_fee_rate))
189                .collect();
190
191            Ok(Selection { utxos, fee_rate, long_term_fee_rate })
192        }
193    }
194
195    // TODO check about adding this to rust-bitcoins from_str for Weight
196    fn parse_weight(weight: &str) -> Weight {
197        let size_parts: Vec<_> = weight.split(" ").collect();
198        let size_int = size_parts[0].parse::<u64>().unwrap();
199        match size_parts[1] {
200            "wu" => Weight::from_wu(size_int),
201            "vB" => Weight::from_vb(size_int).unwrap(),
202            _ => panic!("only support wu or vB sizes"),
203        }
204    }
205
206    impl Selection {
207        pub fn new(utxos: &[&str], fee_rate: FeeRate, long_term_fee_rate: FeeRate) -> Selection {
208            let utxos: Vec<_> = utxos
209                .iter()
210                .filter_map(|u| {
211                    let val_with_size: Vec<_> = u.split("/").collect();
212                    let weight = parse_weight(val_with_size[1]);
213                    let val = val_with_size[0];
214
215                    let abs_val = if val.starts_with("e") {
216                        let val = val.replace("e(", "").replace(")", "");
217                        let eff_value = SignedAmount::from_str(&val).unwrap();
218                        compute_absolute_value(eff_value, weight, fee_rate)
219                    } else {
220                        Amount::from_str(val).unwrap()
221                    };
222
223                    WeightedUtxo::new(abs_val, weight, fee_rate, long_term_fee_rate)
224                })
225                .collect();
226
227            Selection { utxos, fee_rate, long_term_fee_rate }
228        }
229
230        fn effective_value_sum(utxos: &[WeightedUtxo]) -> Option<Amount> {
231            utxos.iter().map(|u| u.effective_value()).try_fold(Amount::ZERO, Amount::checked_add)
232        }
233
234        pub fn available_value(&self) -> Option<Amount> { Self::effective_value_sum(&self.utxos) }
235
236        pub fn weight_total(&self) -> Option<Weight> {
237            self.utxos.iter().map(|u| u.weight()).try_fold(Weight::ZERO, Weight::checked_add)
238        }
239    }
240
241    pub fn compute_absolute_value(
242        effective_value: SignedAmount,
243        weight: Weight,
244        fee_rate: FeeRate,
245    ) -> Amount {
246        let signed_fee = fee_rate.fee_wu(weight).unwrap().to_signed();
247        let signed_absolute_value = (effective_value + signed_fee).unwrap();
248        signed_absolute_value.to_unsigned().unwrap()
249    }
250
251    #[test]
252    fn select_coins_no_solution() {
253        // Test the code branch where both SRD and BnB fail.
254        let target = Amount::from_sat_u32(255432);
255        let cost_of_change = Amount::ZERO;
256        let max_weight = Weight::from_wu(40_000);
257        let pool = build_pool(); // eff value sum 262643
258
259        let result = select_coins(target, cost_of_change, max_weight, &pool);
260
261        match result {
262            Err(crate::SelectionError::InsufficentFunds) => {}
263            _ => panic!("un-expected result: {:?}", result),
264        }
265    }
266
267    #[test]
268    fn select_coins_srd_solution() {
269        let target = (Amount::from_sat_u32(255432) - CHANGE_LOWER).unwrap();
270        let cost_of_change = Amount::ZERO;
271        let max_weight = Weight::from_wu(40_000);
272        let pool = build_pool();
273
274        let result = select_coins(target, cost_of_change, max_weight, &pool);
275        let (_iterations, utxos) = result.unwrap();
276        let sum: Amount = utxos
277            .into_iter()
278            .map(|u| u.value())
279            .try_fold(Amount::ZERO, Amount::checked_add)
280            .unwrap();
281        assert!(sum > target);
282    }
283
284    #[test]
285    fn select_coins_bnb_solution() {
286        let target = Amount::from_sat_u32(255432);
287        let max_weight = Weight::from_wu(40_000);
288        let pool = build_pool();
289
290        // set cost_of_change to be the difference
291        // between the total pool sum and the target amount
292        // plus 1.  This creates an upper bound that the sum
293        // of all utxos will fall bellow resulting in a BnB match.
294        let cost_of_change = Amount::from_sat_u32(7211);
295
296        let result = select_coins(target, cost_of_change, max_weight, &pool);
297        let (iterations, utxos) = result.unwrap();
298        let sum: Amount = utxos
299            .into_iter()
300            .map(|u| u.value())
301            .try_fold(Amount::ZERO, Amount::checked_add)
302            .unwrap();
303        assert!(sum > target);
304        assert!(sum <= (target + cost_of_change).unwrap());
305        assert_eq!(16, iterations);
306    }
307
308    #[test]
309    fn select_coins_proptest() {
310        arbtest(|u| {
311            let candidate_selection = Selection::arbitrary(u)?;
312            let target = Amount::arbitrary(u)?;
313            let cost_of_change = Amount::arbitrary(u)?;
314            let max_weight = Weight::arbitrary(u)?;
315
316            let candidate_utxos = candidate_selection.utxos.clone();
317            let result = select_coins(target, cost_of_change, max_weight, &candidate_utxos);
318
319            match result {
320                Ok((i, utxos)) => {
321                    assert!(i > 0);
322                    crate::tests::assert_target_selection(&utxos, target, None);
323                }
324                Err(InsufficentFunds) => {
325                    let available_value = candidate_selection.available_value().unwrap();
326                    assert!(available_value < (target + CHANGE_LOWER).unwrap());
327                }
328                Err(Overflow(_)) => {
329                    let available_value = candidate_selection.available_value();
330                    let weight_total = candidate_selection.weight_total();
331                    assert!(
332                        available_value.is_none()
333                            || weight_total.is_none()
334                            || target.checked_add(CHANGE_LOWER).is_none()
335                    );
336                }
337                Err(ProgramError) => panic!("un-expected program error"),
338                _ => {}
339            }
340
341            Ok(())
342        });
343    }
344}
bitcoin_coin_selection/lib.rs

bitcoin_coin_selection/
lib.rs
