aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/Makefile.test.include3
-rw-r--r--src/wallet/test/coinselector_tests.cpp171
2 files changed, 173 insertions, 1 deletions
diff --git a/src/Makefile.test.include b/src/Makefile.test.include
index 4ee9102519..4d0819ab79 100644
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -94,7 +94,8 @@ BITCOIN_TESTS += \
wallet/test/wallet_test_fixture.h \
wallet/test/accounting_tests.cpp \
wallet/test/wallet_tests.cpp \
- wallet/test/crypto_tests.cpp
+ wallet/test/crypto_tests.cpp \
+ wallet/test/coinselector_tests.cpp
endif
test_test_bitcoin_SOURCES = $(BITCOIN_TESTS) $(JSON_TEST_FILES) $(RAW_TEST_FILES)
diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp
new file mode 100644
index 0000000000..d4f432e361
--- /dev/null
+++ b/src/wallet/test/coinselector_tests.cpp
@@ -0,0 +1,171 @@
+// Copyright (c) 2017 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include "wallet/wallet.h"
+#include "wallet/coinselection.h"
+#include "amount.h"
+#include "primitives/transaction.h"
+#include "random.h"
+#include "test/test_bitcoin.h"
+#include "wallet/test/wallet_test_fixture.h"
+
+#include <boost/test/unit_test.hpp>
+#include <random>
+
+BOOST_FIXTURE_TEST_SUITE(coin_selection_tests, WalletTestingSetup)
+
+typedef std::set<CInputCoin> CoinSet;
+
+static std::vector<COutput> vCoins;
+static const CWallet testWallet("dummy", CWalletDBWrapper::CreateDummy());
+
+static void add_coin(const CAmount& nValue, int nInput, std::vector<CInputCoin>& set)
+{
+ CMutableTransaction tx;
+ tx.vout.resize(nInput + 1);
+ tx.vout[nInput].nValue = nValue;
+ set.emplace_back(MakeTransactionRef(tx), nInput);
+}
+
+static void add_coin(const CAmount& nValue, int nInput, CoinSet& set)
+{
+ CMutableTransaction tx;
+ tx.vout.resize(nInput + 1);
+ tx.vout[nInput].nValue = nValue;
+ set.emplace(MakeTransactionRef(tx), nInput);
+}
+
+static bool equal_sets(CoinSet a, CoinSet b)
+{
+ std::pair<CoinSet::iterator, CoinSet::iterator> ret = mismatch(a.begin(), a.end(), b.begin());
+ return ret.first == a.end() && ret.second == b.end();
+}
+
+static CAmount make_hard_case(int utxos, std::vector<CInputCoin>& utxo_pool)
+{
+ utxo_pool.clear();
+ CAmount target = 0;
+ for (int i = 0; i < utxos; ++i) {
+ target += (CAmount)1 << (utxos+i);
+ add_coin((CAmount)1 << (utxos+i), 2*i, utxo_pool);
+ add_coin(((CAmount)1 << (utxos+i)) + ((CAmount)1 << (utxos-1-i)), 2*i + 1, utxo_pool);
+ }
+ return target;
+}
+
+// Branch and bound coin selection tests
+BOOST_AUTO_TEST_CASE(bnb_search_test)
+{
+
+ LOCK(testWallet.cs_wallet);
+
+ // Setup
+ std::vector<CInputCoin> utxo_pool;
+ CoinSet selection;
+ CoinSet actual_selection;
+ CAmount value_ret = 0;
+ CAmount not_input_fees = 0;
+
+ /////////////////////////
+ // Known Outcome tests //
+ /////////////////////////
+ BOOST_TEST_MESSAGE("Testing known outcomes");
+
+ // Empty utxo pool
+ BOOST_CHECK(!SelectCoinsBnB(utxo_pool, 1 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
+ selection.clear();
+
+ // Add utxos
+ add_coin(1 * CENT, 1, utxo_pool);
+ add_coin(2 * CENT, 2, utxo_pool);
+ add_coin(3 * CENT, 3, utxo_pool);
+ add_coin(4 * CENT, 4, utxo_pool);
+
+ // Select 1 Cent
+ add_coin(1 * CENT, 1, actual_selection);
+ BOOST_CHECK(SelectCoinsBnB(utxo_pool, 1 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
+ BOOST_CHECK(equal_sets(selection, actual_selection));
+ actual_selection.clear();
+ selection.clear();
+
+ // Select 2 Cent
+ add_coin(2 * CENT, 2, actual_selection);
+ BOOST_CHECK(SelectCoinsBnB(utxo_pool, 2 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
+ BOOST_CHECK(equal_sets(selection, actual_selection));
+ actual_selection.clear();
+ selection.clear();
+
+ // Select 5 Cent
+ add_coin(3 * CENT, 3, actual_selection);
+ add_coin(2 * CENT, 2, actual_selection);
+ BOOST_CHECK(SelectCoinsBnB(utxo_pool, 5 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
+ BOOST_CHECK(equal_sets(selection, actual_selection));
+ actual_selection.clear();
+ selection.clear();
+
+ // Select 11 Cent, not possible
+ BOOST_CHECK(!SelectCoinsBnB(utxo_pool, 11 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
+ actual_selection.clear();
+ selection.clear();
+
+ // Select 10 Cent
+ add_coin(5 * CENT, 5, utxo_pool);
+ add_coin(4 * CENT, 4, actual_selection);
+ add_coin(3 * CENT, 3, actual_selection);
+ add_coin(2 * CENT, 2, actual_selection);
+ add_coin(1 * CENT, 1, actual_selection);
+ BOOST_CHECK(SelectCoinsBnB(utxo_pool, 10 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
+ BOOST_CHECK(equal_sets(selection, actual_selection));
+ actual_selection.clear();
+ selection.clear();
+
+ // Negative effective value
+ // Select 10 Cent but have 1 Cent not be possible because too small
+ add_coin(5 * CENT, 5, actual_selection);
+ add_coin(3 * CENT, 3, actual_selection);
+ add_coin(2 * CENT, 2, actual_selection);
+ BOOST_CHECK(SelectCoinsBnB(utxo_pool, 10 * CENT, 5000, selection, value_ret, not_input_fees));
+
+ // Select 0.25 Cent, not possible
+ BOOST_CHECK(!SelectCoinsBnB(utxo_pool, 0.25 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
+ actual_selection.clear();
+ selection.clear();
+
+ // Iteration exhaustion test
+ CAmount target = make_hard_case(17, utxo_pool);
+ BOOST_CHECK(!SelectCoinsBnB(utxo_pool, target, 0, selection, value_ret, not_input_fees)); // Should exhaust
+ target = make_hard_case(14, utxo_pool);
+ BOOST_CHECK(SelectCoinsBnB(utxo_pool, target, 0, selection, value_ret, not_input_fees)); // Should not exhaust
+
+ // Test same value early bailout optimization
+ add_coin(7 * CENT, 7, actual_selection);
+ add_coin(7 * CENT, 7, actual_selection);
+ add_coin(7 * CENT, 7, actual_selection);
+ add_coin(7 * CENT, 7, actual_selection);
+ add_coin(2 * CENT, 7, actual_selection);
+ add_coin(7 * CENT, 7, utxo_pool);
+ add_coin(7 * CENT, 7, utxo_pool);
+ add_coin(7 * CENT, 7, utxo_pool);
+ add_coin(7 * CENT, 7, utxo_pool);
+ add_coin(2 * CENT, 7, utxo_pool);
+ for (int i = 0; i < 50000; ++i) {
+ add_coin(5 * CENT, 7, utxo_pool);
+ }
+ BOOST_CHECK(SelectCoinsBnB(utxo_pool, 30 * CENT, 5000, selection, value_ret, not_input_fees));
+
+ ////////////////////
+ // Behavior tests //
+ ////////////////////
+ // Select 1 Cent with pool of only greater than 5 Cent
+ utxo_pool.clear();
+ for (int i = 5; i <= 20; ++i) {
+ add_coin(i * CENT, i, utxo_pool);
+ }
+ // Run 100 times, to make sure it is never finding a solution
+ for (int i = 0; i < 100; ++i) {
+ BOOST_CHECK(!SelectCoinsBnB(utxo_pool, 1 * CENT, 2 * CENT, selection, value_ret, not_input_fees));
+ }
+}
+
+BOOST_AUTO_TEST_SUITE_END()