diff --git a/src/Makefile.test.include b/src/Makefile.test.include index e757cdc3a..06d26548f 100644 --- a/src/Makefile.test.include +++ b/src/Makefile.test.include @@ -1,209 +1,210 @@ # Copyright (c) 2013-2016 The Bitcoin Core developers # Distributed under the MIT software license, see the accompanying # file COPYING or http://www.opensource.org/licenses/mit-license.php. TESTS += test/test_bitcoin LOG_DRIVER = $(srcdir)/test/test-bitcoin-driver EXTRA_DIST += test/test-bitcoin-driver bin_PROGRAMS += test/test_bitcoin noinst_PROGRAMS += test/test_bitcoin_fuzzy TEST_SRCDIR = test TEST_BINARY=test/test_bitcoin$(EXEEXT) JSON_TEST_FILES = \ test/data/script_tests.json \ test/data/base58_keys_valid.json \ test/data/base58_encode_decode.json \ test/data/base58_keys_invalid.json \ test/data/blockfilters.json \ test/data/tx_invalid.json \ test/data/tx_valid.json \ test/data/sighash.json RAW_TEST_FILES = GENERATED_TEST_FILES = $(JSON_TEST_FILES:.json=.json.h) $(RAW_TEST_FILES:.raw=.raw.h) # test_bitcoin binary # BITCOIN_TESTS =\ test/scriptnum10.h \ test/activation_tests.cpp \ test/addrman_tests.cpp \ test/allocator_tests.cpp \ test/amount_tests.cpp \ test/arith_uint256_tests.cpp \ test/avalanche_tests.cpp \ test/base32_tests.cpp \ test/base58_tests.cpp \ test/base64_tests.cpp \ test/bip32_tests.cpp \ test/blockchain_tests.cpp \ test/blockcheck_tests.cpp \ test/blockencodings_tests.cpp \ test/blockfilter_tests.cpp \ test/blockindex_tests.cpp \ test/blockstatus_tests.cpp \ test/bloom_tests.cpp \ test/bswap_tests.cpp \ test/cashaddr_tests.cpp \ test/cashaddrenc_tests.cpp \ test/checkdatasig_tests.cpp \ test/checkpoints_tests.cpp \ test/checkqueue_tests.cpp \ test/coins_tests.cpp \ test/compress_tests.cpp \ test/config_tests.cpp \ test/core_io_tests.cpp \ test/crypto_tests.cpp \ test/cuckoocache_tests.cpp \ test/dbwrapper_tests.cpp \ test/DoS_tests.cpp \ test/dstencode_tests.cpp \ test/excessiveblock_tests.cpp \ test/feerate_tests.cpp \ test/finalization_tests.cpp \ test/getarg_tests.cpp \ test/hash_tests.cpp \ test/inv_tests.cpp \ test/jsonutil.cpp \ test/jsonutil.h \ test/key_tests.cpp \ test/lcg_tests.cpp \ test/lcg.h \ test/limitedmap_tests.cpp \ test/main_tests.cpp \ test/mempool_tests.cpp \ test/merkle_tests.cpp \ test/miner_tests.cpp \ test/monolith_opcodes_tests.cpp \ test/multisig_tests.cpp \ test/net_tests.cpp \ test/netbase_tests.cpp \ test/pmt_tests.cpp \ test/policyestimator_tests.cpp \ test/pow_tests.cpp \ test/prevector_tests.cpp \ test/radix_tests.cpp \ test/raii_event_tests.cpp \ test/random_tests.cpp \ test/rcu_tests.cpp \ test/reverselock_tests.cpp \ test/rpc_tests.cpp \ test/rpc_server_tests.cpp \ test/rwcollection_tests.cpp \ test/sanity_tests.cpp \ test/scheduler_tests.cpp \ test/schnorr_tests.cpp \ test/script_commitment_tests.cpp \ test/script_P2SH_tests.cpp \ test/script_standard_tests.cpp \ test/script_tests.cpp \ test/scriptflags.cpp \ test/scriptflags.h \ test/scriptnum_tests.cpp \ test/serialize_tests.cpp \ test/sigcache_tests.cpp \ test/sigencoding_tests.cpp \ test/sighash_tests.cpp \ test/sighashtype_tests.cpp \ test/sigopcount_tests.cpp \ test/sigutil.cpp \ test/sigutil.h \ test/skiplist_tests.cpp \ test/streams_tests.cpp \ test/sync_tests.cpp \ test/test_bitcoin.cpp \ test/test_bitcoin.h \ test/test_bitcoin_main.cpp \ test/timedata_tests.cpp \ test/transaction_tests.cpp \ test/txindex_tests.cpp \ test/txvalidationcache_tests.cpp \ test/uint256_tests.cpp \ test/undo_tests.cpp \ test/univalue_tests.cpp \ test/util_tests.cpp \ test/validation_tests.cpp \ test/work_comparator_tests.cpp \ rpc/test/server_tests.cpp if ENABLE_WALLET BITCOIN_TESTS += \ wallet/test/wallet_test_fixture.cpp \ wallet/test/wallet_test_fixture.h \ wallet/test/accounting_tests.cpp \ wallet/test/wallet_tests.cpp \ wallet/test/walletdb_tests.cpp \ - wallet/test/wallet_crypto_tests.cpp + wallet/test/wallet_crypto_tests.cpp \ + wallet/test/coinselector_tests.cpp endif test_test_bitcoin_SOURCES = $(BITCOIN_TESTS) $(JSON_TEST_FILES) $(RAW_TEST_FILES) test_test_bitcoin_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) $(TESTDEFS) $(EVENT_CFLAGS) test_test_bitcoin_LDADD = if ENABLE_WALLET test_test_bitcoin_LDADD += $(LIBBITCOIN_WALLET) endif test_test_bitcoin_LDADD += $(LIBBITCOIN_SERVER) $(LIBBITCOIN_CLI) $(LIBBITCOIN_COMMON) $(LIBBITCOIN_UTIL) $(LIBBITCOIN_CONSENSUS) $(LIBBITCOIN_CRYPTO) $(LIBUNIVALUE) \ $(LIBLEVELDB) $(LIBLEVELDB_SSE42) $(LIBMEMENV) $(BOOST_LIBS) $(BOOST_UNIT_TEST_FRAMEWORK_LIB) $(LIBSECP256K1) $(EVENT_LIBS) $(EVENT_PTHREADS_LIBS) test_test_bitcoin_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) test_test_bitcoin_LDADD += $(LIBBITCOIN_CONSENSUS) $(BDB_LIBS) $(SSL_LIBS) $(CRYPTO_LIBS) $(MINIUPNPC_LIBS) test_test_bitcoin_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS) -static if ENABLE_ZMQ test_test_bitcoin_LDADD += $(ZMQ_LIBS) endif # # test_bitcoin_fuzzy binary # test_test_bitcoin_fuzzy_SOURCES = test/test_bitcoin_fuzzy.cpp test_test_bitcoin_fuzzy_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) test_test_bitcoin_fuzzy_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) test_test_bitcoin_fuzzy_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS) test_test_bitcoin_fuzzy_LDADD = \ $(LIBUNIVALUE) \ $(LIBBITCOIN_SERVER) \ $(LIBBITCOIN_COMMON) \ $(LIBBITCOIN_UTIL) \ $(LIBBITCOIN_CONSENSUS) \ $(LIBBITCOIN_CRYPTO) \ $(LIBSECP256K1) test_test_bitcoin_fuzzy_LDADD += $(BOOST_LIBS) $(CRYPTO_LIBS) # nodist_test_test_bitcoin_SOURCES = $(GENERATED_TEST_FILES) $(BITCOIN_TESTS): $(GENERATED_TEST_FILES) CLEAN_BITCOIN_TEST = test/*.gcda test/*.gcno $(GENERATED_TEST_FILES) CLEANFILES += $(CLEAN_BITCOIN_TEST) bitcoin_test: $(TEST_BINARY) bitcoin_test_check: $(TEST_BINARY) FORCE $(MAKE) check-TESTS TESTS=$^ bitcoin_test_clean : FORCE rm -f $(CLEAN_BITCOIN_TEST) $(test_test_bitcoin_OBJECTS) $(TEST_BINARY) check-local: @echo "Running test/util/bitcoin-util-test.py..." $(top_builddir)/test/util/bitcoin-util-test.py $(AM_V_at)$(MAKE) $(AM_MAKEFLAGS) -C secp256k1 check if EMBEDDED_UNIVALUE $(AM_V_at)$(MAKE) $(AM_MAKEFLAGS) -C univalue check endif %.json.h: %.json @$(MKDIR_P) $(@D) @{ \ echo "namespace json_tests{" && \ echo "static unsigned const char $(*F)[] = {" && \ $(HEXDUMP) -v -e '8/1 "0x%02x, "' -e '"\n"' $< | $(SED) -e 's/0x ,//g' && \ echo "};};"; \ } > "$@.new" && mv -f "$@.new" "$@" @echo "Generated $@" diff --git a/src/test/CMakeLists.txt b/src/test/CMakeLists.txt index 1ffc5d462..96b4fb3e7 100644 --- a/src/test/CMakeLists.txt +++ b/src/test/CMakeLists.txt @@ -1,174 +1,175 @@ # Copyright (c) 2018 The Bitcoin developers project(bitcoin-test) # Process json files. file(MAKE_DIRECTORY "${CMAKE_CURRENT_BINARY_DIR}/data") find_program(PYTHON python) function(gen_json_header NAME) set(HEADERS "") foreach(f ${ARGN}) set(h "${CMAKE_CURRENT_BINARY_DIR}/${f}.h") # Get the proper name for the test variable. get_filename_component(TEST_NAME ${f} NAME_WE) add_custom_command(OUTPUT ${h} COMMAND ${PYTHON} ARGS "${CMAKE_CURRENT_SOURCE_DIR}/data/generate_header.py" "${TEST_NAME}" "${CMAKE_CURRENT_SOURCE_DIR}/${f}" > ${h} MAIN_DEPENDENCY ${f} DEPENDS "data/generate_header.py" VERBATIM ) list(APPEND HEADERS ${h}) endforeach(f) set(${NAME} "${HEADERS}" PARENT_SCOPE) endfunction() gen_json_header(JSON_HEADERS data/script_tests.json data/base58_keys_valid.json data/base58_encode_decode.json data/base58_keys_invalid.json data/blockfilters.json data/tx_invalid.json data/tx_valid.json data/sighash.json ) include(TestSuite) create_test_suite(bitcoin) add_dependencies(check check-bitcoin) add_test_to_suite(bitcoin test_bitcoin activation_tests.cpp addrman_tests.cpp allocator_tests.cpp amount_tests.cpp arith_uint256_tests.cpp avalanche_tests.cpp base32_tests.cpp base58_tests.cpp base64_tests.cpp bip32_tests.cpp blockchain_tests.cpp blockcheck_tests.cpp blockencodings_tests.cpp blockfilter_tests.cpp blockindex_tests.cpp blockstatus_tests.cpp bloom_tests.cpp bswap_tests.cpp cashaddr_tests.cpp cashaddrenc_tests.cpp checkdatasig_tests.cpp checkpoints_tests.cpp checkqueue_tests.cpp coins_tests.cpp compress_tests.cpp config_tests.cpp core_io_tests.cpp crypto_tests.cpp cuckoocache_tests.cpp dbwrapper_tests.cpp DoS_tests.cpp dstencode_tests.cpp excessiveblock_tests.cpp feerate_tests.cpp finalization_tests.cpp getarg_tests.cpp hash_tests.cpp inv_tests.cpp jsonutil.cpp key_tests.cpp lcg_tests.cpp limitedmap_tests.cpp main_tests.cpp mempool_tests.cpp merkle_tests.cpp miner_tests.cpp monolith_opcodes_tests.cpp multisig_tests.cpp net_tests.cpp netbase_tests.cpp pmt_tests.cpp policyestimator_tests.cpp pow_tests.cpp prevector_tests.cpp radix_tests.cpp raii_event_tests.cpp random_tests.cpp rcu_tests.cpp reverselock_tests.cpp rpc_tests.cpp rpc_server_tests.cpp rwcollection_tests.cpp sanity_tests.cpp scheduler_tests.cpp schnorr_tests.cpp script_commitment_tests.cpp script_P2SH_tests.cpp script_standard_tests.cpp script_tests.cpp scriptflags.cpp scriptnum_tests.cpp serialize_tests.cpp sigcache_tests.cpp sigencoding_tests.cpp sighash_tests.cpp sighashtype_tests.cpp sigopcount_tests.cpp sigutil.cpp skiplist_tests.cpp streams_tests.cpp sync_tests.cpp test_bitcoin.cpp test_bitcoin_main.cpp timedata_tests.cpp transaction_tests.cpp txindex_tests.cpp txvalidationcache_tests.cpp uint256_tests.cpp undo_tests.cpp univalue_tests.cpp util_tests.cpp validation_tests.cpp work_comparator_tests.cpp # RPC Tests ../rpc/test/server_tests.cpp # Tests generated from JSON ${JSON_HEADERS} ) find_package(Boost 1.58 REQUIRED unit_test_framework) target_link_libraries(test_bitcoin Boost::unit_test_framework rpcclient server) # We need to detect if the BOOST_TEST_DYN_LINK flag is required. set(CMAKE_REQUIRED_LIBRARIES Boost::unit_test_framework) check_cxx_source_compiles(" #define BOOST_TEST_DYN_LINK #define BOOST_TEST_MAIN #include " BOOST_TEST_DYN_LINK) if(BOOST_TEST_DYN_LINK) target_compile_definitions(test_bitcoin PRIVATE BOOST_TEST_DYN_LINK) endif(BOOST_TEST_DYN_LINK) if(BUILD_BITCOIN_WALLET) target_sources(test_bitcoin PRIVATE ../wallet/test/wallet_test_fixture.cpp ../wallet/test/accounting_tests.cpp ../wallet/test/wallet_tests.cpp ../wallet/test/walletdb_tests.cpp ../wallet/test/wallet_crypto_tests.cpp + ../wallet/test/coinselector_tests.cpp ) endif() diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index 48f8aa9bf..e7216be57 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -1,205 +1,205 @@ // 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 #include #include // Descending order comparator struct { bool operator()(const CInputCoin &a, const CInputCoin &b) const { return a.effective_value > b.effective_value; } } descending; /** * This is the Branch and Bound Coin Selection algorithm designed by Murch. It * searches for an input set that can pay for the spending target and does not * exceed the spending target by more than the cost of creating and spending a * change output. The algorithm uses a depth-first search on a binary tree. In * the binary tree, each node corresponds to the inclusion or the omission of a * UTXO. UTXOs are sorted by their effective values and the trees is explored * deterministically per the inclusion branch first. At each node, the algorithm * checks whether the selection is within the target range. While the selection * has not reached the target range, more UTXOs are included. When a selection's * value exceeds the target range, the complete subtree deriving from this * selection can be omitted. At that point, the last included UTXO is deselected * and the corresponding omission branch explored instead. The search ends after * the complete tree has been searched or after a limited number of tries. * * The search continues to search for better solutions after one solution has * been found. The best solution is chosen by minimizing the waste metric. The * waste metric is defined as the cost to spend the current inputs at the given * fee rate minus the long term expected cost to spend the inputs, plus the * amount the selection exceeds the spending target: * * waste = selectionTotal - target + inputs × (currentFeeRate - longTermFeeRate) * * The algorithm uses two additional optimizations. A lookahead keeps track of * the total value of the unexplored UTXOs. A subtree is not explored if the * lookahead indicates that the target range cannot be reached. Further, it is * unnecessary to test equivalent combinations. This allows us to skip testing * the inclusion of UTXOs that match the effective value and waste of an omitted * predecessor. * * The Branch and Bound algorithm is described in detail in Murch's Master * Thesis: * https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf * * @param const std::vector& utxo_pool The set of UTXOs that we are * choosing from. These UTXOs will be sorted in descending order by effective * value and the CInputCoins' values are their effective values. * @param const Amount& target_value This is the value that we want to select. * It is the lower bound of the range. * @param const Amount& cost_of_change This is the cost of creating and * spending a change output. This plus target_value is the upper bound of the * range. * @param std::set& out_set -> This is an output parameter for the * set of CInputCoins that have been selected. * @param Amount& value_ret -> This is an output parameter for the total value * of the CInputCoins that were selected. * @param Amount not_input_fees -> The fees that need to be paid for the * outputs and fixed size overhead (version, locktime, marker and flag) */ static const size_t TOTAL_TRIES = 100000; bool SelectCoinsBnB(std::vector &utxo_pool, const Amount &target_value, const Amount &cost_of_change, std::set &out_set, Amount &value_ret, - Amount not_input_fees) { + const Amount not_input_fees) { out_set.clear(); Amount curr_value = Amount::zero(); // select the utxo at this index std::vector curr_selection; curr_selection.reserve(utxo_pool.size()); Amount actual_target = not_input_fees + target_value; // Calculate curr_available_value Amount curr_available_value = Amount::zero(); for (const CInputCoin &utxo : utxo_pool) { // Assert that this utxo is not negative. It should never be negative, // effective value calculation should have removed it assert(utxo.effective_value > Amount::zero()); curr_available_value += utxo.effective_value; } if (curr_available_value < actual_target) { return false; } // Sort the utxo_pool std::sort(utxo_pool.begin(), utxo_pool.end(), descending); Amount curr_waste = Amount::zero(); std::vector best_selection; Amount best_waste = MAX_MONEY; // Depth First search loop for choosing the UTXOs for (size_t i = 0; i < TOTAL_TRIES; ++i) { // Conditions for starting a backtrack bool backtrack = false; if (curr_value + curr_available_value < actual_target || // Cannot possibly reach target with the amount // remaining in the curr_available_value. curr_value > actual_target + cost_of_change || // Selected value is out of range, go back // and try other branch (curr_waste > best_waste && (utxo_pool.at(0).fee - utxo_pool.at(0).long_term_fee) > Amount::zero())) { // Don't select things which we know will be more wasteful if the // waste is increasing backtrack = true; } // Selected value is within range else if (curr_value >= actual_target) { // This is the excess value which is added to the waste for the // below comparison. Adding another UTXO after this check could // bring the waste down if the long term fee is higher than the // current fee. However we are not going to explore that because // this optimization for the waste is only done when we have hit our // target value. Adding any more UTXOs will be just burning the // UTXO; it will go entirely to fees. Thus we aren't going to // explore any more UTXOs to avoid burning money like that. curr_waste += (curr_value - actual_target); if (curr_waste <= best_waste) { best_selection = curr_selection; best_selection.resize(utxo_pool.size()); best_waste = curr_waste; } // Remove the excess value as we will be selecting different coins // now curr_waste -= (curr_value - actual_target); backtrack = true; } // Backtracking, moving backwards if (backtrack) { // Walk backwards to find the last included UTXO that still needs to // have its omission branch traversed. while (!curr_selection.empty() && !curr_selection.back()) { curr_selection.pop_back(); curr_available_value += utxo_pool.at(curr_selection.size()).effective_value; } if (curr_selection.empty()) { // We have walked back to the first utxo and no branch is // untraversed. All solutions searched break; } // Output was included on previous iterations, try excluding now. curr_selection.back() = false; CInputCoin &utxo = utxo_pool.at(curr_selection.size() - 1); curr_value -= utxo.effective_value; curr_waste -= utxo.fee - utxo.long_term_fee; } // Moving forwards, continuing down this branch else { CInputCoin &utxo = utxo_pool.at(curr_selection.size()); // Remove this utxo from the curr_available_value utxo amount curr_available_value -= utxo.effective_value; // Avoid searching a branch if the previous UTXO has the same value // and same waste and was excluded. Since the ratio of fee to long // term fee is the same, we only need to check if one of those // values match in order to know that the waste is the same. if (!curr_selection.empty() && !curr_selection.back() && utxo.effective_value == utxo_pool.at(curr_selection.size() - 1).effective_value && utxo.fee == utxo_pool.at(curr_selection.size() - 1).fee) { curr_selection.push_back(false); } else { // Inclusion branch first (Largest First Exploration) curr_selection.push_back(true); curr_value += utxo.effective_value; curr_waste += utxo.fee - utxo.long_term_fee; } } } // Check for solution if (best_selection.empty()) { return false; } // Set output set value_ret = Amount::zero(); for (size_t i = 0; i < best_selection.size(); ++i) { if (best_selection.at(i)) { out_set.insert(utxo_pool.at(i)); value_ret += utxo_pool.at(i).txout.nValue; } } return true; } diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h index eedee8490..b1b88c7e9 100644 --- a/src/wallet/coinselection.h +++ b/src/wallet/coinselection.h @@ -1,56 +1,56 @@ // 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. #ifndef BITCOIN_COINSELECTION_H #define BITCOIN_COINSELECTION_H #include #include #include //! target minimum change amount static const Amount MIN_CHANGE = CENT; //! final minimum change amount after paying for fees static const Amount MIN_FINAL_CHANGE = MIN_CHANGE / 2; class CInputCoin { public: CInputCoin(const CTransactionRef &tx, unsigned int i) { if (!tx) { throw std::invalid_argument("tx should not be null"); } if (i >= tx->vout.size()) { throw std::out_of_range("The output index is out of range"); } outpoint = COutPoint(tx->GetId(), i); txout = tx->vout[i]; effective_value = txout.nValue; } COutPoint outpoint; CTxOut txout; Amount effective_value; Amount fee = Amount::zero(); Amount long_term_fee = Amount::zero(); bool operator<(const CInputCoin &rhs) const { return outpoint < rhs.outpoint; } bool operator!=(const CInputCoin &rhs) const { return outpoint != rhs.outpoint; } bool operator==(const CInputCoin &rhs) const { return outpoint == rhs.outpoint; } }; bool SelectCoinsBnB(std::vector &utxo_pool, const Amount &target_value, const Amount &cost_of_change, std::set &out_set, Amount &value_ret, - Amount not_input_fees); + const Amount not_input_fees); #endif // BITCOIN_COINSELECTION_H diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp new file mode 100644 index 000000000..984417728 --- /dev/null +++ b/src/wallet/test/coinselector_tests.cpp @@ -0,0 +1,184 @@ +// 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 +#include +#include +#include +#include + +#include +#include + +#include + +#include + +BOOST_FIXTURE_TEST_SUITE(coinselector_tests, WalletTestingSetup) + +typedef std::set CoinSet; + +static std::vector vCoins; + +static void add_coin(const Amount nValue, int nInput, + std::vector &set) { + CMutableTransaction tx; + tx.vout.resize(nInput + 1); + tx.vout[nInput].nValue = nValue; + set.emplace_back(MakeTransactionRef(tx), nInput); +} + +static void add_coin(const Amount 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 ret = + mismatch(a.begin(), a.end(), b.begin()); + return ret.first == a.end() && ret.second == b.end(); +} + +static Amount make_hard_case(int utxos, std::vector &utxo_pool) { + utxo_pool.clear(); + Amount target = Amount::zero(); + for (int i = 0; i < utxos; ++i) { + const Amount base = (int64_t(1) << (utxos + i)) * SATOSHI; + target += base; + add_coin(base, 2 * i, utxo_pool); + add_coin(base + (int64_t(1) << (utxos - 1 - i)) * SATOSHI, 2 * i + 1, + utxo_pool); + } + return target; +} + +// Branch and bound coin selection tests +BOOST_AUTO_TEST_CASE(bnb_search_test) { + LOCK(m_wallet.cs_wallet); + + // Setup + std::vector utxo_pool; + CoinSet selection; + CoinSet actual_selection; + Amount value_ret = Amount::zero(); + Amount not_input_fees = Amount::zero(); + + ///////////////////////// + // Known Outcome tests // + ///////////////////////// + BOOST_TEST_MESSAGE("Testing known outcomes"); + + // Empty utxo pool + BOOST_CHECK(!SelectCoinsBnB(utxo_pool, 1 * CENT, CENT / 2, 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, CENT / 2, 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, CENT / 2, 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, CENT / 2, 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, CENT / 2, 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, CENT / 2, 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 * SATOSHI, selection, + value_ret, not_input_fees)); + + // Select 0.25 Cent, not possible + BOOST_CHECK(!SelectCoinsBnB(utxo_pool, CENT / 4, CENT / 2, selection, + value_ret, not_input_fees)); + actual_selection.clear(); + selection.clear(); + + // Iteration exhaustion test + Amount target = make_hard_case(17, utxo_pool); + // Should exhaust + BOOST_CHECK(!SelectCoinsBnB(utxo_pool, target, Amount::zero(), selection, + value_ret, not_input_fees)); + target = make_hard_case(14, utxo_pool); + // Should not exhaust + BOOST_CHECK(SelectCoinsBnB(utxo_pool, target, Amount::zero(), selection, + value_ret, not_input_fees)); + + // 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 * SATOSHI, 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()