diff options
| -rw-r--r-- | src/Makefile.test.include | 3 | ||||
| -rw-r--r-- | src/wallet/test/coinselector_tests.cpp | 171 |
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() |