From 5c03483e26ab414d22ef192691b2336c1bb3cb02 Mon Sep 17 00:00:00 2001 From: AlSzacrel Date: Sat, 13 Sep 2014 02:09:18 +0200 Subject: Coinselection prunes extraneous inputs from ApproximateBestSubset A further pass over the available inputs has been added to ApproximateBestSubset after a candidate set has been found. It will prune any extraneous inputs in the selected subset, in order to decrease the number of input and the resulting change. --- src/wallet/wallet.cpp | 13 +++++++++++++ 1 file changed, 13 insertions(+) (limited to 'src') diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index d23d54e678..06b77bb9b9 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -1620,6 +1620,19 @@ static void ApproximateBestSubset(vector= nTargetValue) { fReachedTarget = true; + + for (unsigned int i = 0; i < vValue.size(); i++) + { + //The target has been reached, but the candidate set may contain extraneous inputs. + //This iterates over all inputs and deducts any that are included, but smaller + //than the amount nTargetValue is still exceeded by. + if (vfIncluded[i] && (nTotal - vValue[i].first) >= nTargetValue ) + { + vfIncluded[i] = false; + nTotal -= vValue[i].first; + } + } + if (nTotal < nBest) { nBest = nTotal; -- cgit v1.2.3 From af9510e0374443b093d633a91c4f1f8bf5071292 Mon Sep 17 00:00:00 2001 From: Murch Date: Sun, 6 Dec 2015 22:20:41 +0100 Subject: Moved set reduction to the end of ApproximateBestSubset to reduce performance impact --- src/wallet/wallet.cpp | 27 +++++++++++---------------- 1 file changed, 11 insertions(+), 16 deletions(-) (limited to 'src') diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index 06b77bb9b9..f9e8a97ae6 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -1605,7 +1605,7 @@ static void ApproximateBestSubset(vector= nTargetValue) { fReachedTarget = true; - - for (unsigned int i = 0; i < vValue.size(); i++) - { - //The target has been reached, but the candidate set may contain extraneous inputs. - //This iterates over all inputs and deducts any that are included, but smaller - //than the amount nTargetValue is still exceeded by. - if (vfIncluded[i] && (nTotal - vValue[i].first) >= nTargetValue ) - { - vfIncluded[i] = false; - nTotal -= vValue[i].first; - } - } - if (nTotal < nBest) { nBest = nTotal; vfBest = vfIncluded; } - nTotal -= vValue[i].first; - vfIncluded[i] = false; } } } } } + + //Reduces the approximate best subset by removing any inputs that are smaller than the surplus of nTotal beyond nTargetValue. + for (unsigned int i = 0; i < vValue.size(); i++) + { + if (vfBest[i] && (nBest - vValue[i].first) >= nTargetValue ) + { + vfBest[i] = false; + nBest -= vValue[i].first; + } + } } bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, int nConfMine, int nConfTheirs, vector vCoins, -- cgit v1.2.3 From fc0f52d78085b6ef97d6821fc7592326c2d9b495 Mon Sep 17 00:00:00 2001 From: Murch Date: Mon, 7 Dec 2015 00:15:36 +0100 Subject: Added a test for the pruning of extraneous inputs after ApproximateBestSet --- src/wallet/test/wallet_tests.cpp | 18 ++++++++++++++++++ src/wallet/wallet.cpp | 14 ++++++++------ 2 files changed, 26 insertions(+), 6 deletions(-) (limited to 'src') diff --git a/src/wallet/test/wallet_tests.cpp b/src/wallet/test/wallet_tests.cpp index 8b9292bd14..5e8ccd90ab 100644 --- a/src/wallet/test/wallet_tests.cpp +++ b/src/wallet/test/wallet_tests.cpp @@ -328,4 +328,22 @@ BOOST_AUTO_TEST_CASE(coin_selection_tests) empty_wallet(); } +BOOST_AUTO_TEST_CASE(pruning_in_ApproximateBestSet) +{ + CoinSet setCoinsRet; + CAmount nValueRet; + + LOCK(wallet.cs_wallet); + + empty_wallet(); + for (int i = 0; i < 12; i++) + { + add_coin(10*CENT); + } + add_coin(100*CENT); + add_coin(100*CENT); + BOOST_CHECK(wallet.SelectCoinsMinConf(221*CENT, 1, 6, vCoins, setCoinsRet, nValueRet)); + BOOST_CHECK_EQUAL(nValueRet, 230*CENT); +} + BOOST_AUTO_TEST_SUITE_END() diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index f9e8a97ae6..a262769c4d 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -1605,7 +1605,7 @@ static void ApproximateBestSubset(vector= nTargetValue ) - { - vfBest[i] = false; - nBest -= vValue[i].first; - } + if (vfBest[i] && (nBest - vValue[i].first) >= nTargetValue ) + { + vfBest[i] = false; + nBest -= vValue[i].first; + } } } -- cgit v1.2.3