aboutsummaryrefslogtreecommitdiff
path: root/src/wallet/coinselection.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/wallet/coinselection.cpp')
-rw-r--r--src/wallet/coinselection.cpp237
1 files changed, 159 insertions, 78 deletions
diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 23faad027f..b568e90998 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -50,8 +50,8 @@ struct {
* The Branch and Bound algorithm is described in detail in Murch's Master Thesis:
* https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf
*
- * @param const std::vector<CInputCoin>& utxo_pool The set of UTXOs that we are choosing from.
- * These UTXOs will be sorted in descending order by effective value and the CInputCoins'
+ * @param const std::vector<OutputGroup>& utxo_pool The set of UTXO groups that we are choosing from.
+ * These UTXO groups will be sorted in descending order by effective value and the OutputGroups'
* values are their effective values.
* @param const CAmount& selection_target This is the value that we want to select. It is the lower
* bound of the range.
@@ -64,16 +64,15 @@ static const size_t TOTAL_TRIES = 100000;
std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change)
{
- SelectionResult result(selection_target);
+ SelectionResult result(selection_target, SelectionAlgorithm::BNB);
CAmount curr_value = 0;
-
- std::vector<bool> curr_selection; // select the utxo at this index
- curr_selection.reserve(utxo_pool.size());
+ std::vector<size_t> curr_selection; // selected utxo indexes
// Calculate curr_available_value
CAmount curr_available_value = 0;
for (const OutputGroup& utxo : utxo_pool) {
- // Assert that this utxo is not negative. It should never be negative, effective value calculation should have removed it
+ // Assert that this utxo is not negative. It should never be negative,
+ // effective value calculation should have removed it
assert(utxo.GetSelectionAmount() > 0);
curr_available_value += utxo.GetSelectionAmount();
}
@@ -85,15 +84,15 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo
std::sort(utxo_pool.begin(), utxo_pool.end(), descending);
CAmount curr_waste = 0;
- std::vector<bool> best_selection;
+ std::vector<size_t> best_selection;
CAmount best_waste = MAX_MONEY;
// Depth First search loop for choosing the UTXOs
- for (size_t i = 0; i < TOTAL_TRIES; ++i) {
+ for (size_t curr_try = 0, utxo_pool_index = 0; curr_try < TOTAL_TRIES; ++curr_try, ++utxo_pool_index) {
// Conditions for starting a backtrack
bool backtrack = false;
- if (curr_value + curr_available_value < selection_target || // Cannot possibly reach target with the amount remaining in the curr_available_value.
- curr_value > selection_target + cost_of_change || // Selected value is out of range, go back and try other branch
+ if (curr_value + curr_available_value < selection_target || // Cannot possibly reach target with the amount remaining in the curr_available_value.
+ curr_value > selection_target + cost_of_change || // Selected value is out of range, go back and try other branch
(curr_waste > best_waste && (utxo_pool.at(0).fee - utxo_pool.at(0).long_term_fee) > 0)) { // Don't select things which we know will be more wasteful if the waste is increasing
backtrack = true;
} else if (curr_value >= selection_target) { // Selected value is within range
@@ -104,48 +103,44 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo
// explore any more UTXOs to avoid burning money like that.
if (curr_waste <= best_waste) {
best_selection = curr_selection;
- best_selection.resize(utxo_pool.size());
best_waste = curr_waste;
- if (best_waste == 0) {
- break;
- }
}
curr_waste -= (curr_value - selection_target); // Remove the excess value as we will be selecting different coins now
backtrack = true;
}
- // Backtracking, moving backwards
- if (backtrack) {
- // Walk backwards to find the last included UTXO that still needs to have its omission branch traversed.
- while (!curr_selection.empty() && !curr_selection.back()) {
- curr_selection.pop_back();
- curr_available_value += utxo_pool.at(curr_selection.size()).GetSelectionAmount();
- }
-
+ if (backtrack) { // Backtracking, moving backwards
if (curr_selection.empty()) { // We have walked back to the first utxo and no branch is untraversed. All solutions searched
break;
}
+ // Add omitted UTXOs back to lookahead before traversing the omission branch of last included UTXO.
+ for (--utxo_pool_index; utxo_pool_index > curr_selection.back(); --utxo_pool_index) {
+ curr_available_value += utxo_pool.at(utxo_pool_index).GetSelectionAmount();
+ }
+
// Output was included on previous iterations, try excluding now.
- curr_selection.back() = false;
- OutputGroup& utxo = utxo_pool.at(curr_selection.size() - 1);
+ assert(utxo_pool_index == curr_selection.back());
+ OutputGroup& utxo = utxo_pool.at(utxo_pool_index);
curr_value -= utxo.GetSelectionAmount();
curr_waste -= utxo.fee - utxo.long_term_fee;
+ curr_selection.pop_back();
} else { // Moving forwards, continuing down this branch
- OutputGroup& utxo = utxo_pool.at(curr_selection.size());
+ OutputGroup& utxo = utxo_pool.at(utxo_pool_index);
// Remove this utxo from the curr_available_value utxo amount
curr_available_value -= utxo.GetSelectionAmount();
- // Avoid searching a branch if the previous UTXO has the same value and same waste and was excluded. Since the ratio of fee to
- // long term fee is the same, we only need to check if one of those values match in order to know that the waste is the same.
- if (!curr_selection.empty() && !curr_selection.back() &&
- utxo.GetSelectionAmount() == utxo_pool.at(curr_selection.size() - 1).GetSelectionAmount() &&
- utxo.fee == utxo_pool.at(curr_selection.size() - 1).fee) {
- curr_selection.push_back(false);
- } else {
+ if (curr_selection.empty() ||
+ // The previous index is included and therefore not relevant for exclusion shortcut
+ (utxo_pool_index - 1) == curr_selection.back() ||
+ // Avoid searching a branch if the previous UTXO has the same value and same waste and was excluded.
+ // Since the ratio of fee to long term fee is the same, we only need to check if one of those values match in order to know that the waste is the same.
+ utxo.GetSelectionAmount() != utxo_pool.at(utxo_pool_index - 1).GetSelectionAmount() ||
+ utxo.fee != utxo_pool.at(utxo_pool_index - 1).fee)
+ {
// Inclusion branch first (Largest First Exploration)
- curr_selection.push_back(true);
+ curr_selection.push_back(utxo_pool_index);
curr_value += utxo.GetSelectionAmount();
curr_waste += utxo.fee - utxo.long_term_fee;
}
@@ -158,23 +153,29 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo
}
// Set output set
- for (size_t i = 0; i < best_selection.size(); ++i) {
- if (best_selection.at(i)) {
- result.AddInput(utxo_pool.at(i));
- }
+ for (const size_t& i : best_selection) {
+ result.AddInput(utxo_pool.at(i));
}
+ result.ComputeAndSetWaste(cost_of_change, cost_of_change, CAmount{0});
+ assert(best_waste == result.GetWaste());
return result;
}
-std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value)
+std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, FastRandomContext& rng)
{
- SelectionResult result(target_value);
+ SelectionResult result(target_value, SelectionAlgorithm::SRD);
+
+ // Include change for SRD as we want to avoid making really small change if the selection just
+ // barely meets the target. Just use the lower bound change target instead of the randomly
+ // generated one, since SRD will result in a random change amount anyway; avoid making the
+ // target needlessly large.
+ target_value += CHANGE_LOWER;
std::vector<size_t> indexes;
indexes.resize(utxo_pool.size());
std::iota(indexes.begin(), indexes.end(), 0);
- Shuffle(indexes.begin(), indexes.end(), FastRandomContext());
+ Shuffle(indexes.begin(), indexes.end(), rng);
CAmount selected_eff_value = 0;
for (const size_t i : indexes) {
@@ -189,16 +190,27 @@ std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& ut
return std::nullopt;
}
-static void ApproximateBestSubset(const std::vector<OutputGroup>& groups, const CAmount& nTotalLower, const CAmount& nTargetValue,
+/** Find a subset of the OutputGroups that is at least as large as, but as close as possible to, the
+ * target amount; solve subset sum.
+ * param@[in] groups OutputGroups to choose from, sorted by value in descending order.
+ * param@[in] nTotalLower Total (effective) value of the UTXOs in groups.
+ * param@[in] nTargetValue Subset sum target, not including change.
+ * param@[out] vfBest Boolean vector representing the subset chosen that is closest to
+ * nTargetValue, with indices corresponding to groups. If the ith
+ * entry is true, that means the ith group in groups was selected.
+ * param@[out] nBest Total amount of subset chosen that is closest to nTargetValue.
+ * param@[in] iterations Maximum number of tries.
+ */
+static void ApproximateBestSubset(FastRandomContext& insecure_rand, const std::vector<OutputGroup>& groups,
+ const CAmount& nTotalLower, const CAmount& nTargetValue,
std::vector<char>& vfBest, CAmount& nBest, int iterations = 1000)
{
std::vector<char> vfIncluded;
+ // Worst case "best" approximation is just all of the groups.
vfBest.assign(groups.size(), true);
nBest = nTotalLower;
- FastRandomContext insecure_rand;
-
for (int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++)
{
vfIncluded.assign(groups.size(), false);
@@ -221,6 +233,8 @@ static void ApproximateBestSubset(const std::vector<OutputGroup>& groups, const
if (nTotal >= nTargetValue)
{
fReachedTarget = true;
+ // If the total is between nTargetValue and nBest, it's our new best
+ // approximation.
if (nTotal < nBest)
{
nBest = nTotal;
@@ -235,22 +249,25 @@ static void ApproximateBestSubset(const std::vector<OutputGroup>& groups, const
}
}
-std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue)
+std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
+ CAmount change_target, FastRandomContext& rng)
{
- SelectionResult result(nTargetValue);
+ SelectionResult result(nTargetValue, SelectionAlgorithm::KNAPSACK);
// List of values less than target
std::optional<OutputGroup> lowest_larger;
+ // Groups with selection amount smaller than the target and any change we might produce.
+ // Don't include groups larger than this, because they will only cause us to overshoot.
std::vector<OutputGroup> applicable_groups;
CAmount nTotalLower = 0;
- Shuffle(groups.begin(), groups.end(), FastRandomContext());
+ Shuffle(groups.begin(), groups.end(), rng);
for (const OutputGroup& group : groups) {
if (group.GetSelectionAmount() == nTargetValue) {
result.AddInput(group);
return result;
- } else if (group.GetSelectionAmount() < nTargetValue + MIN_CHANGE) {
+ } else if (group.GetSelectionAmount() < nTargetValue + change_target) {
applicable_groups.push_back(group);
nTotalLower += group.GetSelectionAmount();
} else if (!lowest_larger || group.GetSelectionAmount() < lowest_larger->GetSelectionAmount()) {
@@ -276,15 +293,15 @@ std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups,
std::vector<char> vfBest;
CAmount nBest;
- ApproximateBestSubset(applicable_groups, nTotalLower, nTargetValue, vfBest, nBest);
- if (nBest != nTargetValue && nTotalLower >= nTargetValue + MIN_CHANGE) {
- ApproximateBestSubset(applicable_groups, nTotalLower, nTargetValue + MIN_CHANGE, vfBest, nBest);
+ ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue, vfBest, nBest);
+ if (nBest != nTargetValue && nTotalLower >= nTargetValue + change_target) {
+ ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue + change_target, vfBest, nBest);
}
// If we have a bigger coin and (either the stochastic approximation didn't find a good solution,
// or the next bigger coin is closer), return the bigger coin
if (lowest_larger &&
- ((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || lowest_larger->GetSelectionAmount() <= nBest)) {
+ ((nBest != nTargetValue && nBest < nTargetValue + change_target) || lowest_larger->GetSelectionAmount() <= nBest)) {
result.AddInput(*lowest_larger);
} else {
for (unsigned int i = 0; i < applicable_groups.size(); i++) {
@@ -293,7 +310,7 @@ std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups,
}
}
- if (LogAcceptCategory(BCLog::SELECTCOINS)) {
+ if (LogAcceptCategory(BCLog::SELECTCOINS, BCLog::Level::Debug)) {
std::string log_message{"Coin selection best subset: "};
for (unsigned int i = 0; i < applicable_groups.size(); i++) {
if (vfBest[i]) {
@@ -313,29 +330,23 @@ std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups,
******************************************************************************/
-void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants, bool positive_only) {
- // Compute the effective value first
- const CAmount coin_fee = output.m_input_bytes < 0 ? 0 : m_effective_feerate.GetFee(output.m_input_bytes);
- const CAmount ev = output.txout.nValue - coin_fee;
-
+void OutputGroup::Insert(const COutput& output, size_t ancestors, size_t descendants, bool positive_only) {
// Filter for positive only here before adding the coin
- if (positive_only && ev <= 0) return;
+ if (positive_only && output.GetEffectiveValue() <= 0) return;
m_outputs.push_back(output);
- CInputCoin& coin = m_outputs.back();
+ COutput& coin = m_outputs.back();
- coin.m_fee = coin_fee;
- fee += coin.m_fee;
+ fee += coin.GetFee();
- coin.m_long_term_fee = coin.m_input_bytes < 0 ? 0 : m_long_term_feerate.GetFee(coin.m_input_bytes);
- long_term_fee += coin.m_long_term_fee;
+ coin.long_term_fee = coin.input_bytes < 0 ? 0 : m_long_term_feerate.GetFee(coin.input_bytes);
+ long_term_fee += coin.long_term_fee;
- coin.effective_value = ev;
- effective_value += coin.effective_value;
+ effective_value += coin.GetEffectiveValue();
- m_from_me &= from_me;
- m_value += output.txout.nValue;
- m_depth = std::min(m_depth, depth);
+ m_from_me &= coin.from_me;
+ m_value += coin.txout.nValue;
+ m_depth = std::min(m_depth, coin.depth);
// ancestors here express the number of ancestors the new coin will end up having, which is
// the sum, rather than the max; this will overestimate in the cases where multiple inputs
// have common ancestors
@@ -357,7 +368,7 @@ CAmount OutputGroup::GetSelectionAmount() const
return m_subtract_fee_outputs ? m_value : effective_value;
}
-CAmount GetSelectionWaste(const std::set<CInputCoin>& inputs, CAmount change_cost, CAmount target, bool use_effective_value)
+CAmount GetSelectionWaste(const std::set<COutput>& inputs, CAmount change_cost, CAmount target, bool use_effective_value)
{
// This function should not be called with empty inputs as that would mean the selection failed
assert(!inputs.empty());
@@ -365,9 +376,9 @@ CAmount GetSelectionWaste(const std::set<CInputCoin>& inputs, CAmount change_cos
// Always consider the cost of spending an input now vs in the future.
CAmount waste = 0;
CAmount selected_effective_value = 0;
- for (const CInputCoin& coin : inputs) {
- waste += coin.m_fee - coin.m_long_term_fee;
- selected_effective_value += use_effective_value ? coin.effective_value : coin.txout.nValue;
+ for (const COutput& coin : inputs) {
+ waste += coin.GetFee() - coin.long_term_fee;
+ selected_effective_value += use_effective_value ? coin.GetEffectiveValue() : coin.txout.nValue;
}
if (change_cost) {
@@ -384,9 +395,26 @@ CAmount GetSelectionWaste(const std::set<CInputCoin>& inputs, CAmount change_cos
return waste;
}
-void SelectionResult::ComputeAndSetWaste(CAmount change_cost)
+CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_fee, FastRandomContext& rng)
+{
+ if (payment_value <= CHANGE_LOWER / 2) {
+ return change_fee + CHANGE_LOWER;
+ } else {
+ // random value between 50ksat and min (payment_value * 2, 1milsat)
+ const auto upper_bound = std::min(payment_value * 2, CHANGE_UPPER);
+ return change_fee + rng.randrange(upper_bound - CHANGE_LOWER) + CHANGE_LOWER;
+ }
+}
+
+void SelectionResult::ComputeAndSetWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee)
{
- m_waste = GetSelectionWaste(m_selected_inputs, change_cost, m_target, m_use_effective);
+ const CAmount change = GetChange(min_viable_change, change_fee);
+
+ if (change > 0) {
+ m_waste = GetSelectionWaste(m_selected_inputs, change_cost, m_target, m_use_effective);
+ } else {
+ m_waste = GetSelectionWaste(m_selected_inputs, 0, m_target, m_use_effective);
+ }
}
CAmount SelectionResult::GetWaste() const
@@ -399,6 +427,11 @@ CAmount SelectionResult::GetSelectedValue() const
return std::accumulate(m_selected_inputs.cbegin(), m_selected_inputs.cend(), CAmount{0}, [](CAmount sum, const auto& coin) { return sum + coin.txout.nValue; });
}
+CAmount SelectionResult::GetSelectedEffectiveValue() const
+{
+ return std::accumulate(m_selected_inputs.cbegin(), m_selected_inputs.cend(), CAmount{0}, [](CAmount sum, const auto& coin) { return sum + coin.GetEffectiveValue(); });
+}
+
void SelectionResult::Clear()
{
m_selected_inputs.clear();
@@ -411,14 +444,24 @@ void SelectionResult::AddInput(const OutputGroup& group)
m_use_effective = !group.m_subtract_fee_outputs;
}
-const std::set<CInputCoin>& SelectionResult::GetInputSet() const
+void SelectionResult::Merge(const SelectionResult& other)
+{
+ m_target += other.m_target;
+ m_use_effective |= other.m_use_effective;
+ if (m_algo == SelectionAlgorithm::MANUAL) {
+ m_algo = other.m_algo;
+ }
+ util::insert(m_selected_inputs, other.m_selected_inputs);
+}
+
+const std::set<COutput>& SelectionResult::GetInputSet() const
{
return m_selected_inputs;
}
-std::vector<CInputCoin> SelectionResult::GetShuffledInputVector() const
+std::vector<COutput> SelectionResult::GetShuffledInputVector() const
{
- std::vector<CInputCoin> coins(m_selected_inputs.begin(), m_selected_inputs.end());
+ std::vector<COutput> coins(m_selected_inputs.begin(), m_selected_inputs.end());
Shuffle(coins.begin(), coins.end(), FastRandomContext());
return coins;
}
@@ -430,4 +473,42 @@ bool SelectionResult::operator<(SelectionResult other) const
// As this operator is only used in std::min_element, we want the result that has more inputs when waste are equal.
return *m_waste < *other.m_waste || (*m_waste == *other.m_waste && m_selected_inputs.size() > other.m_selected_inputs.size());
}
+
+std::string COutput::ToString() const
+{
+ return strprintf("COutput(%s, %d, %d) [%s]", outpoint.hash.ToString(), outpoint.n, depth, FormatMoney(txout.nValue));
+}
+
+std::string GetAlgorithmName(const SelectionAlgorithm algo)
+{
+ switch (algo)
+ {
+ case SelectionAlgorithm::BNB: return "bnb";
+ case SelectionAlgorithm::KNAPSACK: return "knapsack";
+ case SelectionAlgorithm::SRD: return "srd";
+ case SelectionAlgorithm::MANUAL: return "manual";
+ // No default case to allow for compiler to warn
+ }
+ assert(false);
+}
+
+CAmount SelectionResult::GetChange(const CAmount min_viable_change, const CAmount change_fee) const
+{
+ // change = SUM(inputs) - SUM(outputs) - fees
+ // 1) With SFFO we don't pay any fees
+ // 2) Otherwise we pay all the fees:
+ // - input fees are covered by GetSelectedEffectiveValue()
+ // - non_input_fee is included in m_target
+ // - change_fee
+ const CAmount change = m_use_effective
+ ? GetSelectedEffectiveValue() - m_target - change_fee
+ : GetSelectedValue() - m_target;
+
+ if (change < min_viable_change) {
+ return 0;
+ }
+
+ return change;
+}
+
} // namespace wallet
generated by cgit v1.2.3 (git 2.26.2) at 2025-03-23 09:42:33 +0000