BDK Coin Selection

bdk_coin_select is a tool to help you select inputs for making Bitcoin (ticker: BTC) transactions. It's got zero dependencies so you can paste it into your project without concern.

⚠ This work is only ready to use by those who expect (potentially catastrophic) bugs and will have the time to investigate them and contribute back to this crate.

Constructing the CoinSelector

The main structure is CoinSelector. To construct it, we specify a list of candidate UTXOs and a transaction base_weight. The base_weight includes the recipient outputs and mandatory inputs (if any).

use std::str::FromStr;
use bdk_coin_select::{ CoinSelector, Candidate, TR_KEYSPEND_TXIN_WEIGHT};
use bitcoin::{ Address, Network, Transaction, TxIn, TxOut };

// The address where we want to send our coins.
let recipient_addr = 
    Address::from_str("tb1pvjf9t34fznr53u5tqhejz4nr69luzkhlvsdsdfq9pglutrpve2xq7hps46").unwrap();

let candidates = vec![
    Candidate {
        // How many inputs does this candidate represents. Needed so we can 
        // figure out the weight of the varint that encodes the number of inputs
        input_count: 1,
        // the value of the input
        value: 1_000_000,
        // the total weight of the input(s).
        // you may need to use miniscript to figure out the correct value here.
        weight: TR_KEYSPEND_TXIN_WEIGHT, 
        // wether it's a segwit input. Needed so we know whether to include the
        // segwit header in total weight calculations.
        is_segwit: true
    },
    Candidate {
        // A candidate can represent multiple inputs in the case where you 
        // always want some inputs to be spent together.
        input_count: 2,
        weight: 2*TR_KEYSPEND_TXIN_WEIGHT,
        value: 3_000_000,
        is_segwit: true
    }
];

let base_tx = Transaction {
    input: vec![],
    // include your recipient outputs here
    output: vec![TxOut {
        value: 900_000,
        script_pubkey: recipient_addr.payload.script_pubkey(),
    }],
    lock_time: bitcoin::absolute::LockTime::from_height(0).unwrap(),
    version: 0x02,
};
let base_weight = base_tx.weight().to_wu() as u32;
println!("base weight: {}", base_weight);

// You can now select coins!
let mut coin_selector = CoinSelector::new(&candidates, base_weight);
coin_selector.select(0);

Change Policy

A change policy determines whether the drain output(s) should be in the final solution. The determination is simple: if the excess value is above a threshold then the drain should be added. To construct a change policy you always provide DrainWeights which tell the coin selector the weight cost of adding the drain. DrainWeights includes two weights. One is the weight of the drain output(s). The other is the weight of spending the drain output later on (the input weight).

use std::str::FromStr;
use bdk_coin_select::{CoinSelector, Candidate, DrainWeights, TXIN_BASE_WEIGHT, ChangePolicy, TR_KEYSPEND_TXIN_WEIGHT};
use bitcoin::{Address, Network, Transaction, TxIn, TxOut};
const TR_SATISFACTION_WEIGHT: u32 = 66;
let base_tx = Transaction {
    input: vec![],
    output: vec![/* include your recipient outputs here */],
    lock_time: bitcoin::absolute::LockTime::from_height(0).unwrap(),
    version: 0x02,
};
let base_weight = base_tx.weight().to_wu() as u32;

// The change output that may or may not be included in the final transaction.
let drain_addr =
    Address::from_str("tb1pvjf9t34fznr53u5tqhejz4nr69luzkhlvsdsdfq9pglutrpve2xq7hps46")
    .expect("address must be valid")
    .require_network(Network::Testnet)
    .expect("network must match");

// The drain output(s) may or may not be included in the final tx. We calculate
// the drain weight to include the output length varint weight changes from
// including the drain output(s).
let drain_output_weight = {
    let mut tx_with_drain = base_tx.clone();
    tx_with_drain.output.push(TxOut {
        script_pubkey: drain_addr.script_pubkey(),
        ..Default::default()
    });
    tx_with_drain.weight().to_wu() as u32 - base_weight
};
println!("drain output weight: {}", drain_output_weight);

let drain_weights = DrainWeights {
    output_weight: drain_output_weight,
    spend_weight: TR_KEYSPEND_TXIN_WEIGHT,
};

// This constructs a change policy that creates change when the change value is
// greater than or equal to the dust limit.
let change_policy = ChangePolicy::min_value(
    drain_weights,
    drain_addr.script_pubkey().dust_value().to_sat(),
);

Branch and Bound

You can use methods such as [CoinSelector::select] to manually select coins, or methods such as [CoinSelector::select_until_target_met] for a rudimentary automatic selection. However, if you wish to automatically select coins to optimize for a given metric, [CoinSelector::run_bnb] can be used.

Built-in metrics are provided in the [metrics] submodule. Currently, only the LowestFee metric is considered stable.

use bdk_coin_select::{ Candidate, CoinSelector, FeeRate, Target, ChangePolicy };
use bdk_coin_select::metrics::LowestFee;
let candidates = [];
let base_weight = 0;
let drain_weights = bdk_coin_select::DrainWeights::default();
let dust_limit = 0;
let long_term_feerate = FeeRate::default_min_relay_fee();

let mut coin_selector = CoinSelector::new(&candidates, base_weight);

let target = Target {
    feerate: FeeRate::default_min_relay_fee(),
    min_fee: 0,
    value: 210_000,
};

// We use a change policy that introduces a change output if doing so reduces
// the "waste" and that the change output's value is at least that of the 
// `dust_limit`.
let change_policy = ChangePolicy::min_value_and_waste(
    drain_weights,
    dust_limit,
    target.feerate,
    long_term_feerate,
);

// This metric minimizes transaction fees paid over time. The 
// `long_term_feerate` is used to calculate the additional fee from spending 
// the change output in the future.
let metric = LowestFee {
    target,
    long_term_feerate,
    change_policy
};

// We run the branch and bound algorithm with a max round limit of 100,000.
match coin_selector.run_bnb(metric, 100_000) {
    Err(err) => println!("failed to find a solution: {}", err),
    Ok(score) => {
        println!("we found a solution with score {}", score);

        let selection = coin_selector
            .apply_selection(&candidates)
            .collect::<Vec<_>>();
        let change = coin_selector.drain(target, change_policy);

        println!("we selected {} inputs", selection.len());
        println!("We are including a change output of {} value (0 means not change)", change.value);
    }
};

Finalizing a Selection

• is_target_met checks whether the current state of CoinSelector meets the Target.
• apply_selection applies the selection to the original list of candidate TxOuts.

use bdk_coin_select::{CoinSelector, Candidate, DrainWeights, Target, ChangePolicy, TR_KEYSPEND_TXIN_WEIGHT, Drain};
use bitcoin::{Amount, TxOut, Address};
let base_weight = 0_u32;
let drain_weights = DrainWeights::new_tr_keyspend();
use core::str::FromStr;

// A random target, as an example.
let target = Target {
    value: 21_000,
    ..Default::default()
};
// Am arbitary drain policy, for the example.
let change_policy = ChangePolicy::min_value(drain_weights, 1337);

// This is a list of candidate txouts for coin selection. If a txout is picked,
// our transaction's input will spend it.
let candidate_txouts = vec![
    TxOut {
        value: 100_000,
        script_pubkey: Address::from_str("bc1p5cyxnuxmeuwuvkwfem96lqzszd02n6xdcjrs20cac6yqjjwudpxqkedrcr").unwrap().payload.script_pubkey(),
    },
    TxOut {
        value: 150_000,
        script_pubkey: Address::from_str("bc1p4qhjn9zdvkux4e44uhx8tc55attvtyu358kutcqkudyccelu0was9fqzwh").unwrap().payload.script_pubkey(),
    },
    TxOut {
        value: 200_000,
        script_pubkey: Address::from_str("bc1p0d0rhyynq0awa9m8cqrcr8f5nxqx3aw29w4ru5u9my3h0sfygnzs9khxz8").unwrap().payload.script_pubkey()
    }
];
// We transform the candidate txouts into something `CoinSelector` can 
// understand.
let candidates = candidate_txouts
    .iter()
    .map(|txout| Candidate {
        input_count: 1,
        value: txout.value,
        weight: TR_KEYSPEND_TXIN_WEIGHT, // you need to figure out the weight of the txin somehow
        is_segwit: txout.script_pubkey.is_witness_program(),
    })
    .collect::<Vec<_>>();

let mut selector = CoinSelector::new(&candidates, base_weight);
selector
    .select_until_target_met(target,  Drain::none())
    .expect("we've got enough coins");

// Get a list of coins that are selected.
let selected_coins = selector
    .apply_selection(&candidate_txouts)
    .collect::<Vec<_>>();
assert_eq!(selected_coins.len(), 1);

// Determine whether we should add a change output.
let drain = selector.drain(target, change_policy);

if drain.is_some() {
    // add our change output to the transaction
    let change_value = drain.value;
}

Minimum Supported Rust Version (MSRV)

This library is tested to compile on 1.54

To build with the MSRV, you will need to pin the following dependencies:

# tempfile 3.7.0 has MSRV 1.63.0+
cargo update -p tempfile --precise "3.6.0"