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?.
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.
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
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 | 22,446 |
| Rust BnB | 1,000 | 582.180 |
| C++ Core BnB | 1,000 | 816,374 |
Note: The measurements where recorded using rustc 1.89 stable. Expect worse performance with MSRV.
This library should always compile with any combination of features on Rust 1.63.0.