diff options
author | glozow <gloriajzhao@gmail.com> | 2022-03-07 13:45:06 +0000 |
---|---|---|
committer | glozow <gloriajzhao@gmail.com> | 2022-03-25 11:56:46 +0000 |
commit | 1e52e6bd0a8888efb4ed247d74ec7ca9dfc2e002 (patch) | |
tree | 6bfea8ddf30f453c9e41f1278d09202f87814f01 /src/wallet/coinselection.cpp | |
parent | c9b5790e8da8a88d9022dd9725a1f7bb4474cbf7 (diff) | |
download | bitcoin-1e52e6bd0a8888efb4ed247d74ec7ca9dfc2e002.tar.xz |
refactor coin selection for parameterizable change target
no behavior changes, since the target is always MIN_CHANGE
Diffstat (limited to 'src/wallet/coinselection.cpp')
-rw-r--r-- | src/wallet/coinselection.cpp | 30 |
1 files changed, 24 insertions, 6 deletions
diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index 38c5939232..b1784b4d9b 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -187,11 +187,24 @@ std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& ut return std::nullopt; } -static void ApproximateBestSubset(FastRandomContext& insecure_rand, 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; @@ -217,6 +230,8 @@ static void ApproximateBestSubset(FastRandomContext& insecure_rand, const std::v if (nTotal >= nTargetValue) { fReachedTarget = true; + // If the total is between nTargetValue and nBest, it's our new best + // approximation. if (nTotal < nBest) { nBest = nTotal; @@ -231,12 +246,15 @@ static void ApproximateBestSubset(FastRandomContext& insecure_rand, const std::v } } -std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue, FastRandomContext& rng) +std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue, + CAmount change_target, FastRandomContext& rng) { SelectionResult result(nTargetValue); // 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; @@ -246,7 +264,7 @@ std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& 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()) { @@ -273,14 +291,14 @@ std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, CAmount nBest; ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue, vfBest, nBest); - if (nBest != nTargetValue && nTotalLower >= nTargetValue + MIN_CHANGE) { - ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue + MIN_CHANGE, 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++) { |