This library provides efficient algorithms to compose a set of unspent transaction outputs (UTXOs). That is, this crate provides methods for automatic coin-selection for use with Bitcoin wallet development in Rust.
For more details on how automatic coin-selection works:
This project provides a Rust clone of the excellent Bitcoin Core coin-selection algorithms in combination with Rust Bitcoin types. Special care is taken to make this Rust implementation highly performant (see benchmarks) and correct with numerous unit tests (cargo test), property tests and fuzz tests.
Bitcoin and Rust Bitcoin are closely followed providing timely updates such that the newest changes are ported and utilized by this project. Bug fixes and improvements are submitted back to these upstream projects.
use bitcoin_units::{FeeRate, Amount, Weight};
use bitcoin_coin_selection::{WeightedUtxo, select_coins, errors::SelectionError::*};
fn main() {
let utxo_amt = Amount::from_sat_u32(314);
let utxo = WeightedUtxo::new(utxo_amt, Weight::ZERO, FeeRate::ZERO, FeeRate::ZERO).unwrap();
let pool = vec![utxo];
let target = utxo_amt;
let coins = select_coins(target, Amount::ZERO, Weight::ZERO, &pool);
match coins {
Ok((i, utxos)) => println!("solution found: {:?} in {} iterations", utxos, i),
Err(InsufficentFunds) => println!("insufficent funds"),
Err(IterationLimitReached) => {},
Err(Overflow(_)) => println!("addition overflow"),
Err(ProgramError) => println!("un-expected result"),
Err(SolutionNotFound) => println!("solution not found"),
Err(MaxWeightExceeded) => println!("max weight exceeded"),
}The current implemented selection algorithms available are:
- select_coins - combines two search routines,
branch_and_boundandsingle_random_draw. - single_random_draw - randomly select a set of UTXOs. Creates a change output.
- branch_and_bound - deterministically attempt to find an exact match. Attempts to find a changeless solution.
- coin_grinder - deterministically attempt to find a solution with the lowest weight. Creates a change output.
select_coins is the default algorithm one should use. It attempts to find a changeless solution (not requiring a change output) using branch_and_bound using single_random_draw as a fallback. It follows that branch_and_bound may find a solution while single_random_draw always finds a solution unless an error occurs. Please see the links about for more details on producing a changeless solution.
Detailed algorithm API documentation can be found here.
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 coin_grinder
> cargo fuzz run select_coins
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 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.
A basic performance comparison between implementations using commodity hardware (My rather old laptop).
| implementation | pool size | ns/iter |
|---|---|---|
| Rust SRD | 1,000 | 21,888 |
| Rust BnB | 1,000 | 495,910 |
| C++ Core BnB | 1,000 | 816,374 |
Note: The measurements where recorded using rustc 1.90 stable. Expect worse performance with MSRV.
This library should always compile with any combination of features on Rust 1.74.0.