#coin #bitcoin #utxo #coinselection #coin-selection

bitcoin-coin-selection

Libary providing utility functions to efficiently select a set of UTXOs

7 unstable releases (3 breaking)

0.6.1 Oct 21, 2024
0.6.0 Oct 9, 2024
0.5.0 Jul 19, 2024
0.4.1 Jul 12, 2024
0.3.1 Jun 30, 2024

#3 in #utxo

CC0 license

48KB
743 lines

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).
fee_rate - The current fee_rate.
long_term_fee_rate - The long_term_fee_rate which helps determine if fee_rate is expensive or cheap.
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.

Benchmarks

To run the benchmarks use: cargo bench.

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

Fuzz

Fuzz with cargo fuzz run select_coins_srd, cargo fuzz run select_coins_bnb or cargo fuzz run select_coins.

performance comparison

A basic performance comparison between this Rust BnB implementation and Bitcoin Core using commodity hardware (My rather old laptop).

implementation pool size ns/iter
Rust BnB 1,000 897,810
C++ Core BnB 1,000 816,374

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

Minimum Supported Rust Version (MSRV)

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

Release Notes

Dependencies

~7.5MB
~93K SLoC