Bitcoin Coin-Selection

This library provides efficient algorithms to compose a set of unspent transaction outputs (UTXOs). When a Bitcoin wallet creates a transaction, there is a diverse set of trade-offs to decide which UTXOs to choose. The trade-offs for deciding which set of UTXOs to use are described in depth here: An Evaluation of Coin Selection Stratagies as well as here: What is the Waste Metric?.

Usage

The current interface is provided via select_coins() function. The required parameters are:

target - The desired transaction amount.
cost_of_change - How expensive it is to create a new output (UTXO).
max_weight - The maximum allowed UTXO selection weight. weighted_utxos - The set of possible weighted UTXOs to choose from.

As discussed in the literature above, we want to find a "changeless" solution. A changeless solution is one that exceeds the target however is less than target + cost_of_change. If no changeless solution can be found, then creating a change output by splitting a UTXO is the next best outcome. To that end, select_coins() initially attempts a Branch and Bound selection algorithm to find a changeless solution. If no changeless solution is found, then select_coins() falls back to a Single Random Draw selection strategy.

Fuzz tests

To run fuzz tests, install cargo fuzz.

The following fuzz tests can then be run:

> cargo fuzz run single_random_draw 
> cargo fuzz run branch_and_bound 
> cargo fuzz run select_coins

Property tests

This project has a number of property tests created using arbtest. The property tests build a random pool of UTXOs and random selection parameters and then assert the results are correct. To continuously run only the property tests, a simple shell script runs them in a loop.

To continuously run the property tests:

> run_proptests.sh

Benchmarks

Benchmarks for the Branch and Bound Selection algorithm are written using Criterion.

To run the benchmarks use:

> cargo bench

Note: criterion requires rustc version 1.65 to run the benchmarks.

performance comparison

A basic performance comparison between implementations using commodity hardware (My rather old laptop).

Note: The measurements where recorded using rustc 1.89 stable. Expect worse performance with MSRV.

Minimum Supported Rust Version (MSRV)

This library should always compile with any combination of features on Rust 1.63.0.

Release Notes

• CHANGELOG