Changeset View
Changeset View
Standalone View
Standalone View
src/wallet/coinselection.cpp
Show All 11 Lines | |||||
// Descending order comparator | // Descending order comparator | ||||
struct { | struct { | ||||
bool operator()(const OutputGroup &a, const OutputGroup &b) const { | bool operator()(const OutputGroup &a, const OutputGroup &b) const { | ||||
return a.effective_value > b.effective_value; | return a.effective_value > b.effective_value; | ||||
} | } | ||||
} descending; | } descending; | ||||
static const size_t TOTAL_TRIES = 100000; | |||||
/** | /** | ||||
* This is the Branch and Bound Coin Selection algorithm designed by Murch. It | * This is the Branch and Bound Coin Selection algorithm designed by Murch. It | ||||
* searches for an input set that can pay for the spending target and does not | * searches for an input set that can pay for the spending target and does not | ||||
* exceed the spending target by more than the cost of creating and spending a | * exceed the spending target by more than the cost of creating and spending a | ||||
* change output. The algorithm uses a depth-first search on a binary tree. In | * change output. The algorithm uses a depth-first search on a binary tree. In | ||||
* the binary tree, each node corresponds to the inclusion or the omission of a | * the binary tree, each node corresponds to the inclusion or the omission of a | ||||
* UTXO. UTXOs are sorted by their effective values and the trees is explored | * UTXO. UTXOs are sorted by their effective values and the trees is explored | ||||
* deterministically per the inclusion branch first. At each node, the algorithm | * deterministically per the inclusion branch first. At each node, the algorithm | ||||
Show All 18 Lines | |||||
* unnecessary to test equivalent combinations. This allows us to skip testing | * unnecessary to test equivalent combinations. This allows us to skip testing | ||||
* the inclusion of UTXOs that match the effective value and waste of an omitted | * the inclusion of UTXOs that match the effective value and waste of an omitted | ||||
* predecessor. | * predecessor. | ||||
* | * | ||||
* The Branch and Bound algorithm is described in detail in Murch's Master | * The Branch and Bound algorithm is described in detail in Murch's Master | ||||
* Thesis: | * Thesis: | ||||
* https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf | * https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf | ||||
* | * | ||||
* @param const std::vector<CInputCoin>& utxo_pool The set of UTXOs that we are | * @param utxo_pool The set of UTXOs that we are choosing from. These UTXOs will | ||||
* choosing from. These UTXOs will be sorted in descending order by effective | * be sorted in descending order by effective value and the CInputCoins' | ||||
* value and the CInputCoins' values are their effective values. | * values are their effective values. | ||||
* @param const Amount& target_value This is the value that we want to select. | * @param target_value This is the value that we want to select. | ||||
* It is the lower bound of the range. | * It is the lower bound of the range. | ||||
* @param const Amount& cost_of_change This is the cost of creating and | * @param cost_of_change This is the cost of creating and spending a change | ||||
* spending a change output. This plus target_value is the upper bound of the | * output. This plus target_value is the upper bound of the range. | ||||
* range. | * @param out_set This is an output parameter for the set of CInputCoins that | ||||
* @param std::set<CInputCoin>& out_set -> This is an output parameter for the | * have been selected. | ||||
* set of CInputCoins that have been selected. | * @param value_ret This is an output parameter for the total value of the | ||||
* @param Amount& value_ret -> This is an output parameter for the total value | * CInputCoins that were selected. | ||||
* of the CInputCoins that were selected. | * @param not_input_fees -> The fees that need to be paid for the outputs and | ||||
* @param Amount not_input_fees -> The fees that need to be paid for the | * fixed size overhead (version, locktime, marker and flag) | ||||
* outputs and fixed size overhead (version, locktime, marker and flag) | |||||
*/ | */ | ||||
static const size_t TOTAL_TRIES = 100000; | |||||
bool SelectCoinsBnB(std::vector<OutputGroup> &utxo_pool, | bool SelectCoinsBnB(std::vector<OutputGroup> &utxo_pool, | ||||
const Amount &target_value, const Amount &cost_of_change, | const Amount &target_value, const Amount &cost_of_change, | ||||
std::set<CInputCoin> &out_set, Amount &value_ret, | std::set<CInputCoin> &out_set, Amount &value_ret, | ||||
const Amount not_input_fees) { | const Amount not_input_fees) { | ||||
out_set.clear(); | out_set.clear(); | ||||
Amount curr_value = Amount::zero(); | Amount curr_value = Amount::zero(); | ||||
// select the utxo at this index | // select the utxo at this index | ||||
▲ Show 20 Lines • Show All 349 Lines • Show Last 20 Lines |