Add tests for the Branch and Bound algorithm

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()