diff options
34 files changed, 468 insertions, 299 deletions
diff --git a/.travis.yml b/.travis.yml index 1e6fc0a518..19e7174475 100644 --- a/.travis.yml +++ b/.travis.yml @@ -34,13 +34,13 @@ env: # 32-bit + dash - HOST=i686-pc-linux-gnu PACKAGES="g++-multilib python3-zmq" DEP_OPTS="NO_QT=1" RUN_TESTS=true GOAL="install" BITCOIN_CONFIG="--enable-zmq --enable-glibc-back-compat --enable-reduce-exports LDFLAGS=-static-libstdc++" CONFIG_SHELL="/bin/dash" # x86_64 Linux (uses qt5 dev package instead of depends Qt to speed up build and avoid timeout) - - HOST=x86_64-unknown-linux-gnu PACKAGES="python3-zmq qtbase5-dev qttools5-dev-tools protobuf-compiler libdbus-1-dev libharfbuzz-dev libprotobuf-dev" DEP_OPTS="NO_QT=1 NO_UPNP=1 DEBUG=1 ALLOW_HOST_PACKAGES=1" RUN_TESTS=true GOAL="install" BITCOIN_CONFIG="--enable-zmq --with-gui=qt5 --enable-glibc-back-compat --enable-reduce-exports --enable-debug" + - HOST=x86_64-unknown-linux-gnu PACKAGES="python3-zmq qtbase5-dev qttools5-dev-tools protobuf-compiler libdbus-1-dev libharfbuzz-dev libprotobuf-dev" DEP_OPTS="NO_QT=1 NO_UPNP=1 DEBUG=1 ALLOW_HOST_PACKAGES=1" RUN_TESTS=true GOAL="install" BITCOIN_CONFIG="--enable-zmq --with-gui=qt5 --enable-glibc-back-compat --enable-reduce-exports --enable-debug CXXFLAGS=\"-g0 -O2\"" # x86_64 Linux (Qt5 & system libs) - HOST=x86_64-unknown-linux-gnu PACKAGES="python3-zmq qtbase5-dev qttools5-dev-tools libssl1.0-dev libevent-dev bsdmainutils libboost-system-dev libboost-filesystem-dev libboost-chrono-dev libboost-test-dev libboost-thread-dev libdb5.3++-dev libminiupnpc-dev libzmq3-dev libprotobuf-dev protobuf-compiler libqrencode-dev" NO_DEPENDS=1 RUN_TESTS=true GOAL="install" BITCOIN_CONFIG="--enable-zmq --with-incompatible-bdb --enable-glibc-back-compat --enable-reduce-exports --with-gui=qt5 CPPFLAGS=-DDEBUG_LOCKORDER" # x86_64 Linux, No wallet - HOST=x86_64-unknown-linux-gnu PACKAGES="python3" DEP_OPTS="NO_WALLET=1" RUN_TESTS=true GOAL="install" BITCOIN_CONFIG="--enable-glibc-back-compat --enable-reduce-exports" # Cross-Mac - - HOST=x86_64-apple-darwin11 PACKAGES="cmake imagemagick libcap-dev librsvg2-bin libz-dev libbz2-dev libtiff-tools python-dev python3-setuptools-git" BITCOIN_CONFIG="--enable-gui --enable-reduce-exports --enable-werror" OSX_SDK=10.11 GOAL="all deploy" + - HOST=x86_64-apple-darwin14 PACKAGES="cmake imagemagick libcap-dev librsvg2-bin libz-dev libbz2-dev libtiff-tools python-dev python3-setuptools-git" BITCOIN_CONFIG="--enable-gui --enable-reduce-exports --enable-werror" OSX_SDK=10.11 GOAL="all deploy" before_install: - export PATH=$(echo $PATH | tr ':' "\n" | sed '/\/opt\/python/d' | tr "\n" ":" | sed "s|::|:|g") diff --git a/contrib/gitian-descriptors/gitian-osx.yml b/contrib/gitian-descriptors/gitian-osx.yml index 7d4793b97d..e2695b6f7b 100644 --- a/contrib/gitian-descriptors/gitian-osx.yml +++ b/contrib/gitian-descriptors/gitian-osx.yml @@ -34,7 +34,7 @@ files: - "MacOSX10.11.sdk.tar.gz" script: | WRAP_DIR=$HOME/wrapped - HOSTS="x86_64-apple-darwin11" + HOSTS="x86_64-apple-darwin14" CONFIGFLAGS="--enable-reduce-exports --disable-bench --disable-gui-tests GENISOIMAGE=$WRAP_DIR/genisoimage" FAKETIME_HOST_PROGS="" FAKETIME_PROGS="ar ranlib date dmg genisoimage" diff --git a/depends/Makefile b/depends/Makefile index c73ea0f730..3686aaf1f8 100644 --- a/depends/Makefile +++ b/depends/Makefile @@ -178,7 +178,7 @@ install: check-packages $(host_prefix)/share/config.site download-one: check-sources $(all_sources) download-osx: - @$(MAKE) -s HOST=x86_64-apple-darwin11 download-one + @$(MAKE) -s HOST=x86_64-apple-darwin14 download-one download-linux: @$(MAKE) -s HOST=x86_64-unknown-linux-gnu download-one download-win: diff --git a/depends/README.md b/depends/README.md index 226a1cc935..fd343f7010 100644 --- a/depends/README.md +++ b/depends/README.md @@ -22,7 +22,7 @@ Common `host-platform-triplets` for cross compilation are: - `i686-w64-mingw32` for Win32 - `x86_64-w64-mingw32` for Win64 -- `x86_64-apple-darwin11` for macOS +- `x86_64-apple-darwin14` for macOS - `arm-linux-gnueabihf` for Linux ARM 32 bit - `aarch64-linux-gnu` for Linux ARM 64 bit - `riscv32-linux-gnu` for Linux RISC-V 32 bit diff --git a/depends/hosts/darwin.mk b/depends/hosts/darwin.mk index 4e58bec74e..a1c943d60b 100644 --- a/depends/hosts/darwin.mk +++ b/depends/hosts/darwin.mk @@ -1,4 +1,4 @@ -OSX_MIN_VERSION=10.8 +OSX_MIN_VERSION=10.10 OSX_SDK_VERSION=10.11 OSX_SDK=$(SDK_PATH)/MacOSX$(OSX_SDK_VERSION).sdk LD64_VERSION=253.9 diff --git a/doc/build-osx.md b/doc/build-osx.md index a07dbd1e1d..486a505b60 100644 --- a/doc/build-osx.md +++ b/doc/build-osx.md @@ -91,6 +91,6 @@ Other commands: Notes ----- -* Tested on OS X 10.8 Mountain Lion through macOS 10.13 High Sierra on 64-bit Intel processors only. +* Tested on OS X 10.10 Yosemite through macOS 10.13 High Sierra on 64-bit Intel processors only. * Building with downloaded Qt binaries is not officially supported. See the notes in [#7714](https://github.com/bitcoin/bitcoin/issues/7714) diff --git a/doc/release-notes-pr12257.md b/doc/release-notes-pr12257.md new file mode 100644 index 0000000000..293a00ad75 --- /dev/null +++ b/doc/release-notes-pr12257.md @@ -0,0 +1,9 @@ +Notable changes +=============== + +Coin selection +-------------- +- A new `-avoidpartialspends` flag has been added (default=false). If enabled, the wallet will try to spend UTXO's that point at the same destination + together. This is a privacy increase, as there will no longer be cases where a wallet will inadvertently spend only parts of the coins sent to + the same address (note that if someone were to send coins to that address after it was used, those coins will still be included in future + coin selections). diff --git a/doc/release-notes.md b/doc/release-notes.md index b7eaa6eaf4..ad0c42ab31 100644 --- a/doc/release-notes.md +++ b/doc/release-notes.md @@ -48,11 +48,14 @@ Compatibility ============== Bitcoin Core is extensively tested on multiple operating systems using -the Linux kernel, macOS 10.8+, and Windows 7 and newer (Windows XP is not supported). +the Linux kernel, macOS 10.10+, and Windows 7 and newer (Windows XP is not supported). Bitcoin Core should also work on most other Unix-like systems but is not frequently tested on them. +From 0.17.0 onwards macOS <10.10 is no longer supported. 0.17.0 is built using Qt 5.9.x, which doesn't +support versions of macOS older than 10.10. + Notable changes =============== diff --git a/share/qt/Info.plist.in b/share/qt/Info.plist.in index 5ca6d9d015..17b4ee47de 100644 --- a/share/qt/Info.plist.in +++ b/share/qt/Info.plist.in @@ -3,7 +3,7 @@ <plist version="0.9"> <dict> <key>LSMinimumSystemVersion</key> - <string>10.8.0</string> + <string>10.10.0</string> <key>LSArchitecturePriority</key> <array> diff --git a/src/Makefile.am b/src/Makefile.am index 2603dbae56..60ecf07a59 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -274,6 +274,7 @@ libbitcoin_wallet_a_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) libbitcoin_wallet_a_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) libbitcoin_wallet_a_SOURCES = \ interfaces/wallet.cpp \ + wallet/coincontrol.cpp \ wallet/crypter.cpp \ wallet/db.cpp \ wallet/feebumper.cpp \ diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp index f3180809b5..7510d53c88 100644 --- a/src/bench/coin_selection.cpp +++ b/src/bench/coin_selection.cpp @@ -8,7 +8,7 @@ #include <set> -static void addCoin(const CAmount& nValue, const CWallet& wallet, std::vector<COutput>& vCoins) +static void addCoin(const CAmount& nValue, const CWallet& wallet, std::vector<OutputGroup>& groups) { int nInput = 0; @@ -21,7 +21,7 @@ static void addCoin(const CAmount& nValue, const CWallet& wallet, std::vector<CO int nAge = 6 * 24; COutput output(wtx, nInput, nAge, true /* spendable */, true /* solvable */, true /* safe */); - vCoins.push_back(output); + groups.emplace_back(output.GetInputCoin(), 0, false, 0, 0); } // Simple benchmark for wallet coin selection. Note that it maybe be necessary @@ -37,11 +37,11 @@ static void CoinSelection(benchmark::State& state) LOCK(wallet.cs_wallet); // Add coins. - std::vector<COutput> vCoins; + std::vector<OutputGroup> groups; for (int i = 0; i < 1000; ++i) { - addCoin(1000 * COIN, wallet, vCoins); + addCoin(1000 * COIN, wallet, groups); } - addCoin(3 * COIN, wallet, vCoins); + addCoin(3 * COIN, wallet, groups); const CoinEligibilityFilter filter_standard(1, 6, 0); const CoinSelectionParams coin_selection_params(true, 34, 148, CFeeRate(0), 0); @@ -49,7 +49,7 @@ static void CoinSelection(benchmark::State& state) std::set<CInputCoin> setCoinsRet; CAmount nValueRet; bool bnb_used; - bool success = wallet.SelectCoinsMinConf(1003 * COIN, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used); + bool success = wallet.SelectCoinsMinConf(1003 * COIN, filter_standard, groups, setCoinsRet, nValueRet, coin_selection_params, bnb_used); assert(success); assert(nValueRet == 1003 * COIN); assert(setCoinsRet.size() == 2); @@ -57,17 +57,21 @@ static void CoinSelection(benchmark::State& state) } typedef std::set<CInputCoin> CoinSet; +static const CWallet testWallet("dummy", WalletDatabase::CreateDummy()); +std::vector<std::unique_ptr<CWalletTx>> wtxn; // Copied from src/wallet/test/coinselector_tests.cpp -static void add_coin(const CAmount& nValue, int nInput, std::vector<CInputCoin>& set) +static void add_coin(const CAmount& nValue, int nInput, std::vector<OutputGroup>& set) { CMutableTransaction tx; tx.vout.resize(nInput + 1); tx.vout[nInput].nValue = nValue; - set.emplace_back(MakeTransactionRef(tx), nInput); + std::unique_ptr<CWalletTx> wtx(new CWalletTx(&testWallet, MakeTransactionRef(std::move(tx)))); + set.emplace_back(COutput(wtx.get(), nInput, 0, true, true, true).GetInputCoin(), 0, true, 0, 0); + wtxn.emplace_back(std::move(wtx)); } // Copied from src/wallet/test/coinselector_tests.cpp -static CAmount make_hard_case(int utxos, std::vector<CInputCoin>& utxo_pool) +static CAmount make_hard_case(int utxos, std::vector<OutputGroup>& utxo_pool) { utxo_pool.clear(); CAmount target = 0; @@ -82,7 +86,7 @@ static CAmount make_hard_case(int utxos, std::vector<CInputCoin>& utxo_pool) static void BnBExhaustion(benchmark::State& state) { // Setup - std::vector<CInputCoin> utxo_pool; + std::vector<OutputGroup> utxo_pool; CoinSet selection; CAmount value_ret = 0; CAmount not_input_fees = 0; diff --git a/src/compat/byteswap.h b/src/compat/byteswap.h index c331af2b5e..bfb80bd632 100644 --- a/src/compat/byteswap.h +++ b/src/compat/byteswap.h @@ -15,7 +15,7 @@ #include <byteswap.h> #endif -#if defined(__APPLE__) +#if defined(MAC_OSX) #if !defined(bswap_16) @@ -61,6 +61,6 @@ inline uint64_t bswap_64(uint64_t x) } #endif // HAVE_DECL_BSWAP64 == 0 -#endif // defined(__APPLE__) +#endif // defined(MAC_OSX) #endif // BITCOIN_COMPAT_BYTESWAP_H diff --git a/src/core_read.cpp b/src/core_read.cpp index 067e1b91bd..7225ecc4bb 100644 --- a/src/core_read.cpp +++ b/src/core_read.cpp @@ -16,10 +16,11 @@ #include <version.h> #include <boost/algorithm/string/classification.hpp> -#include <boost/algorithm/string/predicate.hpp> #include <boost/algorithm/string/replace.hpp> #include <boost/algorithm/string/split.hpp> +#include <algorithm> + CScript ParseScript(const std::string& s) { CScript result; @@ -54,20 +55,20 @@ CScript ParseScript(const std::string& s) { // Empty string, ignore. (boost::split given '' will return one word) } - else if (all(*w, boost::algorithm::is_digit()) || - (boost::algorithm::starts_with(*w, "-") && all(std::string(w->begin()+1, w->end()), boost::algorithm::is_digit()))) + else if (std::all_of(w->begin(), w->end(), ::IsDigit) || + (w->front() == '-' && w->size() > 1 && std::all_of(w->begin()+1, w->end(), ::IsDigit))) { // Number int64_t n = atoi64(*w); result << n; } - else if (boost::algorithm::starts_with(*w, "0x") && (w->begin()+2 != w->end()) && IsHex(std::string(w->begin()+2, w->end()))) + else if (w->substr(0,2) == "0x" && w->size() > 2 && IsHex(std::string(w->begin()+2, w->end()))) { // Raw hex data, inserted NOT pushed onto stack: std::vector<unsigned char> raw = ParseHex(std::string(w->begin()+2, w->end())); result.insert(result.end(), raw.begin(), raw.end()); } - else if (w->size() >= 2 && boost::algorithm::starts_with(*w, "'") && boost::algorithm::ends_with(*w, "'")) + else if (w->size() >= 2 && w->front() == '\'' && w->back() == '\'') { // Single-quoted string, pushed as data. NOTE: this is poor-man's // parsing, spaces/tabs/newlines in single-quoted strings won't work. diff --git a/src/netbase.cpp b/src/netbase.cpp index 4ce63cb0ec..607eb89573 100644 --- a/src/netbase.cpp +++ b/src/netbase.cpp @@ -20,7 +20,6 @@ #endif #include <boost/algorithm/string/case_conv.hpp> // for to_lower() -#include <boost/algorithm/string/predicate.hpp> // for startswith() and endswith() #if !defined(MSG_NOSIGNAL) #define MSG_NOSIGNAL 0 @@ -121,8 +120,7 @@ bool LookupHost(const char *pszName, std::vector<CNetAddr>& vIP, unsigned int nM std::string strHost(pszName); if (strHost.empty()) return false; - if (boost::algorithm::starts_with(strHost, "[") && boost::algorithm::ends_with(strHost, "]")) - { + if (strHost.front() == '[' && strHost.back() == ']') { strHost = strHost.substr(1, strHost.size() - 2); } diff --git a/src/qt/bitcoin.cpp b/src/qt/bitcoin.cpp index 3454d3421e..5d0e384cf8 100644 --- a/src/qt/bitcoin.cpp +++ b/src/qt/bitcoin.cpp @@ -614,7 +614,6 @@ int main(int argc, char *argv[]) QApplication::setOrganizationName(QAPP_ORG_NAME); QApplication::setOrganizationDomain(QAPP_ORG_DOMAIN); QApplication::setApplicationName(QAPP_APP_NAME_DEFAULT); - GUIUtil::SubstituteFonts(GetLangTerritory()); /// 4. Initialization of translations, so that intro dialog is in user's language // Now that QSettings are accessible, initialize translations diff --git a/src/qt/guiutil.cpp b/src/qt/guiutil.cpp index acd9f7b35c..3ec8c340be 100644 --- a/src/qt/guiutil.cpp +++ b/src/qt/guiutil.cpp @@ -63,16 +63,6 @@ static fs::detail::utf8_codecvt_facet utf8; -#if defined(Q_OS_MAC) -extern double NSAppKitVersionNumber; -#if !defined(NSAppKitVersionNumber10_8) -#define NSAppKitVersionNumber10_8 1187 -#endif -#if !defined(NSAppKitVersionNumber10_9) -#define NSAppKitVersionNumber10_9 1265 -#endif -#endif - namespace GUIUtil { QString dateTimeStr(const QDateTime &date) @@ -391,42 +381,6 @@ bool openBitcoinConf() return QDesktopServices::openUrl(QUrl::fromLocalFile(boostPathToQString(pathConfig))); } -void SubstituteFonts(const QString& language) -{ -#if defined(Q_OS_MAC) -// Background: -// OSX's default font changed in 10.9 and Qt is unable to find it with its -// usual fallback methods when building against the 10.7 sdk or lower. -// The 10.8 SDK added a function to let it find the correct fallback font. -// If this fallback is not properly loaded, some characters may fail to -// render correctly. -// -// The same thing happened with 10.10. .Helvetica Neue DeskInterface is now default. -// -// Solution: If building with the 10.7 SDK or lower and the user's platform -// is 10.9 or higher at runtime, substitute the correct font. This needs to -// happen before the QApplication is created. -#if defined(MAC_OS_X_VERSION_MAX_ALLOWED) && MAC_OS_X_VERSION_MAX_ALLOWED < MAC_OS_X_VERSION_10_8 - if (floor(NSAppKitVersionNumber) > NSAppKitVersionNumber10_8) - { - if (floor(NSAppKitVersionNumber) <= NSAppKitVersionNumber10_9) - /* On a 10.9 - 10.9.x system */ - QFont::insertSubstitution(".Lucida Grande UI", "Lucida Grande"); - else - { - /* 10.10 or later system */ - if (language == "zh_CN" || language == "zh_TW" || language == "zh_HK") // traditional or simplified Chinese - QFont::insertSubstitution(".Helvetica Neue DeskInterface", "Heiti SC"); - else if (language == "ja") // Japanese - QFont::insertSubstitution(".Helvetica Neue DeskInterface", "Songti SC"); - else - QFont::insertSubstitution(".Helvetica Neue DeskInterface", "Lucida Grande"); - } - } -#endif -#endif -} - ToolTipToRichTextFilter::ToolTipToRichTextFilter(int _size_threshold, QObject *parent) : QObject(parent), size_threshold(_size_threshold) diff --git a/src/qt/guiutil.h b/src/qt/guiutil.h index e965a91d18..199aa9474f 100644 --- a/src/qt/guiutil.h +++ b/src/qt/guiutil.h @@ -120,9 +120,6 @@ namespace GUIUtil // Open the config file bool openBitcoinConf(); - // Replace invalid default fonts with known good ones - void SubstituteFonts(const QString& language); - /** Qt event filter that intercepts ToolTipChange events, and replaces the tooltip with a rich text representation if needed. This assures that Qt can word-wrap long tooltip messages. Tooltips longer than the provided size threshold (in characters) are wrapped. @@ -233,19 +230,7 @@ namespace GUIUtil void mouseReleaseEvent(QMouseEvent *event); }; -#if defined(Q_OS_MAC) - // workaround for Qt OSX Bug: - // https://bugreports.qt-project.org/browse/QTBUG-15631 - // QProgressBar uses around 10% CPU even when app is in background - class ProgressBar : public ClickableProgressBar - { - bool event(QEvent *e) { - return (e->type() != QEvent::StyleAnimationUpdate) ? QProgressBar::event(e) : false; - } - }; -#else typedef ClickableProgressBar ProgressBar; -#endif } // namespace GUIUtil diff --git a/src/test/util_tests.cpp b/src/test/util_tests.cpp index d535f74e91..3661c762fc 100644 --- a/src/test/util_tests.cpp +++ b/src/test/util_tests.cpp @@ -806,6 +806,21 @@ BOOST_AUTO_TEST_CASE(gettime) BOOST_CHECK((GetTime() & ~0xFFFFFFFFLL) == 0); } +BOOST_AUTO_TEST_CASE(test_IsDigit) +{ + BOOST_CHECK_EQUAL(IsDigit('0'), true); + BOOST_CHECK_EQUAL(IsDigit('1'), true); + BOOST_CHECK_EQUAL(IsDigit('8'), true); + BOOST_CHECK_EQUAL(IsDigit('9'), true); + + BOOST_CHECK_EQUAL(IsDigit('0' - 1), false); + BOOST_CHECK_EQUAL(IsDigit('9' + 1), false); + BOOST_CHECK_EQUAL(IsDigit(0), false); + BOOST_CHECK_EQUAL(IsDigit(1), false); + BOOST_CHECK_EQUAL(IsDigit(8), false); + BOOST_CHECK_EQUAL(IsDigit(9), false); +} + BOOST_AUTO_TEST_CASE(test_ParseInt32) { int32_t n; diff --git a/src/util.cpp b/src/util.cpp index 8df23dd08f..2f81f50a71 100644 --- a/src/util.cpp +++ b/src/util.cpp @@ -1021,7 +1021,7 @@ bool FileCommit(FILE *file) LogPrintf("%s: fdatasync failed: %d\n", __func__, errno); return false; } - #elif defined(__APPLE__) && defined(F_FULLFSYNC) + #elif defined(MAC_OSX) && defined(F_FULLFSYNC) if (fcntl(fileno(file), F_FULLFSYNC, 0) == -1) { // Manpage says "value other than -1" is returned on success LogPrintf("%s: fcntl F_FULLFSYNC failed: %d\n", __func__, errno); return false; diff --git a/src/util.h b/src/util.h index 2c22720a6b..23b2a787e4 100644 --- a/src/util.h +++ b/src/util.h @@ -355,4 +355,18 @@ std::string CopyrightHolders(const std::string& strPrefix); */ int ScheduleBatchPriority(void); +namespace util { + +//! Simplification of std insertion +template <typename Tdst, typename Tsrc> +inline void insert(Tdst& dst, const Tsrc& src) { + dst.insert(dst.begin(), src.begin(), src.end()); +} +template <typename TsetT, typename Tsrc> +inline void insert(std::set<TsetT>& dst, const Tsrc& src) { + dst.insert(src.begin(), src.end()); +} + +} // namespace util + #endif // BITCOIN_UTIL_H diff --git a/src/utilstrencodings.cpp b/src/utilstrencodings.cpp index d1025fc7bf..c6927021cb 100644 --- a/src/utilstrencodings.cpp +++ b/src/utilstrencodings.cpp @@ -473,7 +473,7 @@ bool ParseFixedPoint(const std::string &val, int decimals, int64_t *amount_out) /* pass single 0 */ ++ptr; } else if (val[ptr] >= '1' && val[ptr] <= '9') { - while (ptr < end && val[ptr] >= '0' && val[ptr] <= '9') { + while (ptr < end && IsDigit(val[ptr])) { if (!ProcessMantissaDigit(val[ptr], mantissa, mantissa_tzeros)) return false; /* overflow */ ++ptr; @@ -483,9 +483,9 @@ bool ParseFixedPoint(const std::string &val, int decimals, int64_t *amount_out) if (ptr < end && val[ptr] == '.') { ++ptr; - if (ptr < end && val[ptr] >= '0' && val[ptr] <= '9') + if (ptr < end && IsDigit(val[ptr])) { - while (ptr < end && val[ptr] >= '0' && val[ptr] <= '9') { + while (ptr < end && IsDigit(val[ptr])) { if (!ProcessMantissaDigit(val[ptr], mantissa, mantissa_tzeros)) return false; /* overflow */ ++ptr; @@ -502,8 +502,8 @@ bool ParseFixedPoint(const std::string &val, int decimals, int64_t *amount_out) exponent_sign = true; ++ptr; } - if (ptr < end && val[ptr] >= '0' && val[ptr] <= '9') { - while (ptr < end && val[ptr] >= '0' && val[ptr] <= '9') { + if (ptr < end && IsDigit(val[ptr])) { + while (ptr < end && IsDigit(val[ptr])) { if (exponent > (UPPER_BOUND / 10LL)) return false; /* overflow */ exponent = exponent * 10 + val[ptr] - '0'; diff --git a/src/utilstrencodings.h b/src/utilstrencodings.h index 1c9cca90b2..47f9afba1c 100644 --- a/src/utilstrencodings.h +++ b/src/utilstrencodings.h @@ -62,6 +62,16 @@ int64_t atoi64(const std::string& str); int atoi(const std::string& str); /** + * Tests if the given character is a decimal digit. + * @param[in] c character to test + * @return true if the argument is a decimal digit; otherwise false. + */ +constexpr bool IsDigit(char c) +{ + return c >= '0' && c <= '9'; +} + +/** * Convert string to signed 32-bit integer with strict parse error feedback. * @returns true if the entire string could be parsed as valid integer, * false if not the entire string could be parsed or when overflow or underflow occurred. diff --git a/src/wallet/coincontrol.cpp b/src/wallet/coincontrol.cpp new file mode 100644 index 0000000000..645981faa4 --- /dev/null +++ b/src/wallet/coincontrol.cpp @@ -0,0 +1,23 @@ +// Copyright (c) 2018 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/coincontrol.h> + +#include <util.h> + +void CCoinControl::SetNull() +{ + destChange = CNoDestination(); + m_change_type.reset(); + fAllowOtherInputs = false; + fAllowWatchOnly = false; + m_avoid_partial_spends = gArgs.GetBoolArg("-avoidpartialspends", DEFAULT_AVOIDPARTIALSPENDS); + setSelected.clear(); + m_feerate.reset(); + fOverrideFeeRate = false; + m_confirm_target.reset(); + m_signal_bip125_rbf.reset(); + m_fee_mode = FeeEstimateMode::UNSET; +} + diff --git a/src/wallet/coincontrol.h b/src/wallet/coincontrol.h index 98b4298507..fbe6c43e24 100644 --- a/src/wallet/coincontrol.h +++ b/src/wallet/coincontrol.h @@ -32,6 +32,8 @@ public: boost::optional<unsigned int> m_confirm_target; //! Override the wallet's m_signal_rbf if set boost::optional<bool> m_signal_bip125_rbf; + //! Avoid partial use of funds sent to a given address + bool m_avoid_partial_spends; //! Fee estimation mode to control arguments to estimateSmartFee FeeEstimateMode m_fee_mode; @@ -40,19 +42,7 @@ public: SetNull(); } - void SetNull() - { - destChange = CNoDestination(); - m_change_type.reset(); - fAllowOtherInputs = false; - fAllowWatchOnly = false; - setSelected.clear(); - m_feerate.reset(); - fOverrideFeeRate = false; - m_confirm_target.reset(); - m_signal_bip125_rbf.reset(); - m_fee_mode = FeeEstimateMode::UNSET; - } + void SetNull(); bool HasSelected() const { diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index 78258cdec2..1a810e763f 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -8,7 +8,7 @@ // Descending order comparator struct { - bool operator()(const CInputCoin& a, const CInputCoin& b) const + bool operator()(const OutputGroup& a, const OutputGroup& b) const { return a.effective_value > b.effective_value; } @@ -59,7 +59,7 @@ struct { static const size_t TOTAL_TRIES = 100000; -bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount not_input_fees) +bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount not_input_fees) { out_set.clear(); CAmount curr_value = 0; @@ -70,7 +70,7 @@ bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_va // Calculate curr_available_value CAmount curr_available_value = 0; - for (const CInputCoin& utxo : utxo_pool) { + for (const OutputGroup& 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 > 0); curr_available_value += utxo.effective_value; @@ -123,11 +123,11 @@ bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_va // Output was included on previous iterations, try excluding now. curr_selection.back() = false; - CInputCoin& utxo = utxo_pool.at(curr_selection.size() - 1); + OutputGroup& utxo = utxo_pool.at(curr_selection.size() - 1); curr_value -= utxo.effective_value; curr_waste -= utxo.fee - utxo.long_term_fee; } else { // Moving forwards, continuing down this branch - CInputCoin& utxo = utxo_pool.at(curr_selection.size()); + OutputGroup& utxo = utxo_pool.at(curr_selection.size()); // Remove this utxo from the curr_available_value utxo amount curr_available_value -= utxo.effective_value; @@ -156,32 +156,32 @@ bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_va value_ret = 0; 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; + util::insert(out_set, utxo_pool.at(i).m_outputs); + value_ret += utxo_pool.at(i).m_value; } } return true; } -static void ApproximateBestSubset(const std::vector<CInputCoin>& vValue, const CAmount& nTotalLower, const CAmount& nTargetValue, +static void ApproximateBestSubset(const std::vector<OutputGroup>& groups, const CAmount& nTotalLower, const CAmount& nTargetValue, std::vector<char>& vfBest, CAmount& nBest, int iterations = 1000) { std::vector<char> vfIncluded; - vfBest.assign(vValue.size(), true); + vfBest.assign(groups.size(), true); nBest = nTotalLower; FastRandomContext insecure_rand; for (int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++) { - vfIncluded.assign(vValue.size(), false); + vfIncluded.assign(groups.size(), false); CAmount nTotal = 0; bool fReachedTarget = false; for (int nPass = 0; nPass < 2 && !fReachedTarget; nPass++) { - for (unsigned int i = 0; i < vValue.size(); i++) + for (unsigned int i = 0; i < groups.size(); i++) { //The solver here uses a randomized algorithm, //the randomness serves no real security purpose but is just @@ -191,7 +191,7 @@ static void ApproximateBestSubset(const std::vector<CInputCoin>& vValue, const C //the selection random. if (nPass == 0 ? insecure_rand.randbool() : !vfIncluded[i]) { - nTotal += vValue[i].txout.nValue; + nTotal += groups[i].m_value; vfIncluded[i] = true; if (nTotal >= nTargetValue) { @@ -201,7 +201,7 @@ static void ApproximateBestSubset(const std::vector<CInputCoin>& vValue, const C nBest = nTotal; vfBest = vfIncluded; } - nTotal -= vValue[i].txout.nValue; + nTotal -= groups[i].m_value; vfIncluded[i] = false; } } @@ -210,86 +210,75 @@ static void ApproximateBestSubset(const std::vector<CInputCoin>& vValue, const C } } -bool KnapsackSolver(const CAmount& nTargetValue, std::vector<CInputCoin>& vCoins, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet) +bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& groups, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet) { setCoinsRet.clear(); nValueRet = 0; // List of values less than target - boost::optional<CInputCoin> coinLowestLarger; - std::vector<CInputCoin> vValue; + boost::optional<OutputGroup> lowest_larger; + std::vector<OutputGroup> applicable_groups; CAmount nTotalLower = 0; - random_shuffle(vCoins.begin(), vCoins.end(), GetRandInt); + random_shuffle(groups.begin(), groups.end(), GetRandInt); - for (const CInputCoin &coin : vCoins) - { - if (coin.txout.nValue == nTargetValue) - { - setCoinsRet.insert(coin); - nValueRet += coin.txout.nValue; + for (const OutputGroup& group : groups) { + if (group.m_value == nTargetValue) { + util::insert(setCoinsRet, group.m_outputs); + nValueRet += group.m_value; return true; - } - else if (coin.txout.nValue < nTargetValue + MIN_CHANGE) - { - vValue.push_back(coin); - nTotalLower += coin.txout.nValue; - } - else if (!coinLowestLarger || coin.txout.nValue < coinLowestLarger->txout.nValue) - { - coinLowestLarger = coin; + } else if (group.m_value < nTargetValue + MIN_CHANGE) { + applicable_groups.push_back(group); + nTotalLower += group.m_value; + } else if (!lowest_larger || group.m_value < lowest_larger->m_value) { + lowest_larger = group; } } - if (nTotalLower == nTargetValue) - { - for (const auto& input : vValue) - { - setCoinsRet.insert(input); - nValueRet += input.txout.nValue; + if (nTotalLower == nTargetValue) { + for (const auto& group : applicable_groups) { + util::insert(setCoinsRet, group.m_outputs); + nValueRet += group.m_value; } return true; } - if (nTotalLower < nTargetValue) - { - if (!coinLowestLarger) - return false; - setCoinsRet.insert(coinLowestLarger.get()); - nValueRet += coinLowestLarger->txout.nValue; + if (nTotalLower < nTargetValue) { + if (!lowest_larger) return false; + util::insert(setCoinsRet, lowest_larger->m_outputs); + nValueRet += lowest_larger->m_value; return true; } // Solve subset sum by stochastic approximation - std::sort(vValue.begin(), vValue.end(), descending); + std::sort(applicable_groups.begin(), applicable_groups.end(), descending); std::vector<char> vfBest; CAmount nBest; - ApproximateBestSubset(vValue, nTotalLower, nTargetValue, vfBest, nBest); - if (nBest != nTargetValue && nTotalLower >= nTargetValue + MIN_CHANGE) - ApproximateBestSubset(vValue, nTotalLower, nTargetValue + MIN_CHANGE, vfBest, nBest); + ApproximateBestSubset(applicable_groups, nTotalLower, nTargetValue, vfBest, nBest); + if (nBest != nTargetValue && nTotalLower >= nTargetValue + MIN_CHANGE) { + ApproximateBestSubset(applicable_groups, nTotalLower, nTargetValue + MIN_CHANGE, vfBest, nBest); + } // If we have a bigger coin and (either the stochastic approximation didn't find a good solution, // or the next bigger coin is closer), return the bigger coin - if (coinLowestLarger && - ((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || coinLowestLarger->txout.nValue <= nBest)) - { - setCoinsRet.insert(coinLowestLarger.get()); - nValueRet += coinLowestLarger->txout.nValue; - } - else { - for (unsigned int i = 0; i < vValue.size(); i++) - if (vfBest[i]) - { - setCoinsRet.insert(vValue[i]); - nValueRet += vValue[i].txout.nValue; + if (lowest_larger && + ((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || lowest_larger->m_value <= nBest)) { + util::insert(setCoinsRet, lowest_larger->m_outputs); + nValueRet += lowest_larger->m_value; + } else { + for (unsigned int i = 0; i < applicable_groups.size(); i++) { + if (vfBest[i]) { + util::insert(setCoinsRet, applicable_groups[i].m_outputs); + nValueRet += applicable_groups[i].m_value; } + } if (LogAcceptCategory(BCLog::SELECTCOINS)) { LogPrint(BCLog::SELECTCOINS, "SelectCoins() best subset: "); /* Continued */ - for (unsigned int i = 0; i < vValue.size(); i++) { + for (unsigned int i = 0; i < applicable_groups.size(); i++) { if (vfBest[i]) { - LogPrint(BCLog::SELECTCOINS, "%s ", FormatMoney(vValue[i].txout.nValue)); /* Continued */ + LogPrint(BCLog::SELECTCOINS, "%s ", FormatMoney(applicable_groups[i].m_value)); /* Continued */ } } LogPrint(BCLog::SELECTCOINS, "total %s\n", FormatMoney(nBest)); @@ -298,3 +287,40 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<CInputCoin>& vCoins return true; } + +/****************************************************************************** + + OutputGroup + + ******************************************************************************/ + +void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants) { + m_outputs.push_back(output); + m_from_me &= from_me; + m_value += output.effective_value; + m_depth = std::min(m_depth, depth); + // m_ancestors is currently the max ancestor count for all coins in the group; however, this is + // not ideal, as a wallet will consider e.g. thirty 2-ancestor coins as having two ancestors, + // when in reality it has 60 ancestors. + m_ancestors = std::max(m_ancestors, ancestors); + // m_descendants is the count as seen from the top ancestor, not the descendants as seen from the + // coin itself; thus, this value is accurate + m_descendants = std::max(m_descendants, descendants); + effective_value = m_value; +} + +std::vector<CInputCoin>::iterator OutputGroup::Discard(const CInputCoin& output) { + auto it = m_outputs.begin(); + while (it != m_outputs.end() && it->outpoint != output.outpoint) ++it; + if (it == m_outputs.end()) return it; + m_value -= output.effective_value; + effective_value -= output.effective_value; + return m_outputs.erase(it); +} + +bool OutputGroup::EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const +{ + return m_depth >= (m_from_me ? eligibility_filter.conf_mine : eligibility_filter.conf_theirs) + && m_ancestors <= eligibility_filter.max_ancestors + && m_descendants <= eligibility_filter.max_descendants; +} diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h index 2b185879c6..1be776e695 100644 --- a/src/wallet/coinselection.h +++ b/src/wallet/coinselection.h @@ -28,11 +28,17 @@ public: effective_value = txout.nValue; } + CInputCoin(const CTransactionRef& tx, unsigned int i, int input_bytes) : CInputCoin(tx, i) + { + m_input_bytes = input_bytes; + } + COutPoint outpoint; CTxOut txout; CAmount effective_value; - CAmount fee = 0; - CAmount long_term_fee = 0; + + /** Pre-computed estimated size of this output as a fully-signed input in a transaction. Can be -1 if it could not be calculated */ + int m_input_bytes{-1}; bool operator<(const CInputCoin& rhs) const { return outpoint < rhs.outpoint; @@ -47,8 +53,49 @@ public: } }; -bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount not_input_fees); +struct CoinEligibilityFilter +{ + const int conf_mine; + const int conf_theirs; + const uint64_t max_ancestors; + const uint64_t max_descendants; + + CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_descendants(max_ancestors) {} + CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_descendants) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_descendants(max_descendants) {} +}; + +struct OutputGroup +{ + std::vector<CInputCoin> m_outputs; + bool m_from_me{true}; + CAmount m_value{0}; + int m_depth{999}; + size_t m_ancestors{0}; + size_t m_descendants{0}; + CAmount effective_value{0}; + CAmount fee{0}; + CAmount long_term_fee{0}; + + OutputGroup() {} + OutputGroup(std::vector<CInputCoin>&& outputs, bool from_me, CAmount value, int depth, size_t ancestors, size_t descendants) + : m_outputs(std::move(outputs)) + , m_from_me(from_me) + , m_value(value) + , m_depth(depth) + , m_ancestors(ancestors) + , m_descendants(descendants) + {} + OutputGroup(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants) : OutputGroup() { + Insert(output, depth, from_me, ancestors, descendants); + } + void Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants); + std::vector<CInputCoin>::iterator Discard(const CInputCoin& output); + bool EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const; +}; + +bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount not_input_fees); // Original coin selection algorithm as a fallback -bool KnapsackSolver(const CAmount& nTargetValue, std::vector<CInputCoin>& vCoins, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet); +bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& groups, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet); + #endif // BITCOIN_WALLET_COINSELECTION_H diff --git a/src/wallet/init.cpp b/src/wallet/init.cpp index 076134cdd1..52c7e6c70f 100644 --- a/src/wallet/init.cpp +++ b/src/wallet/init.cpp @@ -54,6 +54,7 @@ const WalletInitInterface& g_wallet_init_interface = WalletInit(); void WalletInit::AddWalletOptions() const { gArgs.AddArg("-addresstype", strprintf("What type of addresses to use (\"legacy\", \"p2sh-segwit\", or \"bech32\", default: \"%s\")", FormatOutputType(DEFAULT_ADDRESS_TYPE)), false, OptionsCategory::WALLET); + gArgs.AddArg("-avoidpartialspends", strprintf(_("Group outputs by address, selecting all or none, instead of selecting on a per-output basis. Privacy is improved as an address is only used once (unless someone sends to it after spending from it), but may result in slightly higher fees as suboptimal coin selection may result due to the added limitation (default: %u)"), DEFAULT_AVOIDPARTIALSPENDS), false, OptionsCategory::WALLET); gArgs.AddArg("-changetype", "What type of change to use (\"legacy\", \"p2sh-segwit\", or \"bech32\"). Default is same as -addresstype, except when -addresstype=p2sh-segwit a native segwit output is used when sending to a native segwit address)", false, OptionsCategory::WALLET); gArgs.AddArg("-disablewallet", "Do not load the wallet and disable wallet RPC calls", false, OptionsCategory::WALLET); gArgs.AddArg("-discardfee=<amt>", strprintf("The fee rate (in %s/kB) that indicates your tolerance for discarding change by adding it to the fee (default: %s). " diff --git a/src/wallet/rpcdump.cpp b/src/wallet/rpcdump.cpp index 71fd973581..4e1f6548df 100644 --- a/src/wallet/rpcdump.cpp +++ b/src/wallet/rpcdump.cpp @@ -585,13 +585,13 @@ UniValue importwallet(const JSONRPCRequest& request) std::string strLabel; bool fLabel = true; for (unsigned int nStr = 2; nStr < vstr.size(); nStr++) { - if (boost::algorithm::starts_with(vstr[nStr], "#")) + if (vstr[nStr].front() == '#') break; if (vstr[nStr] == "change=1") fLabel = false; if (vstr[nStr] == "reserve=1") fLabel = false; - if (boost::algorithm::starts_with(vstr[nStr], "label=")) { + if (vstr[nStr].substr(0,6) == "label=") { strLabel = DecodeDumpString(vstr[nStr].substr(6)); fLabel = true; } diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index d90be33000..1561760577 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -102,6 +102,22 @@ static CAmount make_hard_case(int utxos, std::vector<CInputCoin>& utxo_pool) return target; } +inline std::vector<OutputGroup>& GroupCoins(const std::vector<CInputCoin>& coins) +{ + static std::vector<OutputGroup> static_groups; + static_groups.clear(); + for (auto& coin : coins) static_groups.emplace_back(coin, 0, true, 0, 0); + return static_groups; +} + +inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& coins) +{ + static std::vector<OutputGroup> static_groups; + static_groups.clear(); + for (auto& coin : coins) static_groups.emplace_back(coin.GetInputCoin(), coin.nDepth, coin.tx->fDebitCached && coin.tx->nDebitCached == 1 /* HACK: we can't figure out the is_me flag so we use the conditions defined above; perhaps set safe to false for !fIsFromMe in add_coin() */, 0, 0); + return static_groups; +} + // Branch and bound coin selection tests BOOST_AUTO_TEST_CASE(bnb_search_test) { @@ -121,7 +137,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) 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)); + BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees)); selection.clear(); // Add utxos @@ -132,14 +148,14 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) // 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(SelectCoinsBnB(GroupCoins(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(SelectCoinsBnB(GroupCoins(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(); @@ -147,13 +163,13 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) // 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(SelectCoinsBnB(GroupCoins(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)); + BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 11 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees)); actual_selection.clear(); selection.clear(); @@ -163,7 +179,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) 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(SelectCoinsBnB(GroupCoins(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(); @@ -173,18 +189,18 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) 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)); + BOOST_CHECK(SelectCoinsBnB(GroupCoins(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)); + BOOST_CHECK(!SelectCoinsBnB(GroupCoins(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 + BOOST_CHECK(!SelectCoinsBnB(GroupCoins(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 + BOOST_CHECK(SelectCoinsBnB(GroupCoins(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); @@ -200,7 +216,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) 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)); + BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 30 * CENT, 5000, selection, value_ret, not_input_fees)); //////////////////// // Behavior tests // @@ -212,7 +228,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) } // 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_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 2 * CENT, selection, value_ret, not_input_fees)); } // Make sure that effective value is working in SelectCoinsMinConf when BnB is used @@ -223,7 +239,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) empty_wallet(); add_coin(1); vCoins.at(0).nInputBytes = 40; // Make sure that it has a negative effective value. The next check should assert if this somehow got through. Otherwise it will fail - BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params_bnb, bnb_used)); + BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params_bnb, bnb_used)); // Make sure that we aren't using BnB when there are preset inputs empty_wallet(); @@ -252,24 +268,24 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) empty_wallet(); // with an empty wallet we can't even pay one cent - BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); add_coin(1*CENT, 4); // add a new 1 cent coin // with a new 1 cent coin, we still can't find a mature 1 cent - BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); // but we can find a new 1 cent - BOOST_CHECK( testWallet.SelectCoinsMinConf( 1 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf( 1 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, 1 * CENT); add_coin(2*CENT); // add a mature 2 cent coin // we can't make 3 cents of mature coins - BOOST_CHECK(!testWallet.SelectCoinsMinConf( 3 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(!testWallet.SelectCoinsMinConf( 3 * CENT, filter_standard, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); // we can make 3 cents of new coins - BOOST_CHECK( testWallet.SelectCoinsMinConf( 3 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf( 3 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, 3 * CENT); add_coin(5*CENT); // add a mature 5 cent coin, @@ -279,33 +295,33 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) // now we have new: 1+10=11 (of which 10 was self-sent), and mature: 2+5+20=27. total = 38 // we can't make 38 cents only if we disallow new coins: - BOOST_CHECK(!testWallet.SelectCoinsMinConf(38 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(!testWallet.SelectCoinsMinConf(38 * CENT, filter_standard, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); // we can't even make 37 cents if we don't allow new coins even if they're from us - BOOST_CHECK(!testWallet.SelectCoinsMinConf(38 * CENT, filter_standard_extra, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(!testWallet.SelectCoinsMinConf(38 * CENT, filter_standard_extra, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); // but we can make 37 cents if we accept new coins from ourself - BOOST_CHECK( testWallet.SelectCoinsMinConf(37 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(37 * CENT, filter_standard, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, 37 * CENT); // and we can make 38 cents if we accept all new coins - BOOST_CHECK( testWallet.SelectCoinsMinConf(38 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(38 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, 38 * CENT); // try making 34 cents from 1,2,5,10,20 - we can't do it exactly - BOOST_CHECK( testWallet.SelectCoinsMinConf(34 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(34 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, 35 * CENT); // but 35 cents is closest BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U); // the best should be 20+10+5. it's incredibly unlikely the 1 or 2 got included (but possible) // when we try making 7 cents, the smaller coins (1,2,5) are enough. We should see just 2+5 - BOOST_CHECK( testWallet.SelectCoinsMinConf( 7 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf( 7 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, 7 * CENT); BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U); // when we try making 8 cents, the smaller coins (1,2,5) are exactly enough. - BOOST_CHECK( testWallet.SelectCoinsMinConf( 8 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf( 8 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK(nValueRet == 8 * CENT); BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U); // when we try making 9 cents, no subset of smaller coins is enough, and we get the next bigger coin (10) - BOOST_CHECK( testWallet.SelectCoinsMinConf( 9 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf( 9 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, 10 * CENT); BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U); @@ -319,30 +335,30 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) add_coin(30*CENT); // now we have 6+7+8+20+30 = 71 cents total // check that we have 71 and not 72 - BOOST_CHECK( testWallet.SelectCoinsMinConf(71 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); - BOOST_CHECK(!testWallet.SelectCoinsMinConf(72 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(71 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(!testWallet.SelectCoinsMinConf(72 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); // now try making 16 cents. the best smaller coins can do is 6+7+8 = 21; not as good at the next biggest coin, 20 - BOOST_CHECK( testWallet.SelectCoinsMinConf(16 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(16 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, 20 * CENT); // we should get 20 in one coin BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U); add_coin( 5*CENT); // now we have 5+6+7+8+20+30 = 75 cents total // now if we try making 16 cents again, the smaller coins can make 5+6+7 = 18 cents, better than the next biggest coin, 20 - BOOST_CHECK( testWallet.SelectCoinsMinConf(16 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(16 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, 18 * CENT); // we should get 18 in 3 coins BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U); add_coin( 18*CENT); // now we have 5+6+7+8+18+20+30 // and now if we try making 16 cents again, the smaller coins can make 5+6+7 = 18 cents, the same as the next biggest coin, 18 - BOOST_CHECK( testWallet.SelectCoinsMinConf(16 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(16 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, 18 * CENT); // we should get 18 in 1 coin BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U); // because in the event of a tie, the biggest coin wins // now try making 11 cents. we should get 5+6 - BOOST_CHECK( testWallet.SelectCoinsMinConf(11 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(11 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, 11 * CENT); BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U); @@ -351,11 +367,11 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) add_coin( 2*COIN); add_coin( 3*COIN); add_coin( 4*COIN); // now we have 5+6+7+8+18+20+30+100+200+300+400 = 1094 cents - BOOST_CHECK( testWallet.SelectCoinsMinConf(95 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(95 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, 1 * COIN); // we should get 1 BTC in 1 coin BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U); - BOOST_CHECK( testWallet.SelectCoinsMinConf(195 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(195 * CENT, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, 2 * COIN); // we should get 2 BTC in 1 coin BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U); @@ -370,14 +386,14 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) // try making 1 * MIN_CHANGE from the 1.5 * MIN_CHANGE // we'll get change smaller than MIN_CHANGE whatever happens, so can expect MIN_CHANGE exactly - BOOST_CHECK( testWallet.SelectCoinsMinConf(MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(MIN_CHANGE, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, MIN_CHANGE); // but if we add a bigger coin, small change is avoided add_coin(1111*MIN_CHANGE); // try making 1 from 0.1 + 0.2 + 0.3 + 0.4 + 0.5 + 1111 = 1112.5 - BOOST_CHECK( testWallet.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, 1 * MIN_CHANGE); // we should get the exact amount // if we add more small coins: @@ -385,7 +401,7 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) add_coin(MIN_CHANGE * 7 / 10); // and try again to make 1.0 * MIN_CHANGE - BOOST_CHECK( testWallet.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, 1 * MIN_CHANGE); // we should get the exact amount // run the 'mtgox' test (see http://blockexplorer.com/tx/29a3efd3ef04f9153d47a990bd7b048a4b2d213daaa5fb8ed670fb85f13bdbcf) @@ -394,7 +410,7 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) for (int j = 0; j < 20; j++) add_coin(50000 * COIN); - BOOST_CHECK( testWallet.SelectCoinsMinConf(500000 * COIN, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(500000 * COIN, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, 500000 * COIN); // we should get the exact amount BOOST_CHECK_EQUAL(setCoinsRet.size(), 10U); // in ten coins @@ -407,7 +423,7 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) add_coin(MIN_CHANGE * 6 / 10); add_coin(MIN_CHANGE * 7 / 10); add_coin(1111 * MIN_CHANGE); - BOOST_CHECK( testWallet.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, 1111 * MIN_CHANGE); // we get the bigger coin BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U); @@ -417,7 +433,7 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) add_coin(MIN_CHANGE * 6 / 10); add_coin(MIN_CHANGE * 8 / 10); add_coin(1111 * MIN_CHANGE); - BOOST_CHECK( testWallet.SelectCoinsMinConf(MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(MIN_CHANGE, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, MIN_CHANGE); // we should get the exact amount BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U); // in two coins 0.4+0.6 @@ -428,12 +444,12 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) add_coin(MIN_CHANGE * 100); // trying to make 100.01 from these three coins - BOOST_CHECK(testWallet.SelectCoinsMinConf(MIN_CHANGE * 10001 / 100, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(testWallet.SelectCoinsMinConf(MIN_CHANGE * 10001 / 100, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, MIN_CHANGE * 10105 / 100); // we should get all coins BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U); // but if we try to make 99.9, we should take the bigger of the two small coins to avoid small change - BOOST_CHECK(testWallet.SelectCoinsMinConf(MIN_CHANGE * 9990 / 100, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(testWallet.SelectCoinsMinConf(MIN_CHANGE * 9990 / 100, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, 101 * MIN_CHANGE); BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U); @@ -443,7 +459,7 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) // Create 676 inputs (= (old MAX_STANDARD_TX_SIZE == 100000) / 148 bytes per input) for (uint16_t j = 0; j < 676; j++) add_coin(amt); - BOOST_CHECK(testWallet.SelectCoinsMinConf(2000, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(testWallet.SelectCoinsMinConf(2000, filter_confirmed, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); if (amt - 2000 < MIN_CHANGE) { // needs more than one input: uint16_t returnSize = std::ceil((2000.0 + MIN_CHANGE)/amt); @@ -465,8 +481,8 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) // picking 50 from 100 coins doesn't depend on the shuffle, // but does depend on randomness in the stochastic approximation code - BOOST_CHECK(testWallet.SelectCoinsMinConf(50 * COIN, filter_standard, vCoins, setCoinsRet , nValueRet, coin_selection_params, bnb_used)); - BOOST_CHECK(testWallet.SelectCoinsMinConf(50 * COIN, filter_standard, vCoins, setCoinsRet2, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(testWallet.SelectCoinsMinConf(50 * COIN, filter_standard, GroupCoins(vCoins), setCoinsRet , nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(testWallet.SelectCoinsMinConf(50 * COIN, filter_standard, GroupCoins(vCoins), setCoinsRet2, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK(!equal_sets(setCoinsRet, setCoinsRet2)); int fails = 0; @@ -474,8 +490,8 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) { // selecting 1 from 100 identical coins depends on the shuffle; this test will fail 1% of the time // run the test RANDOM_REPEATS times and only complain if all of them fail - BOOST_CHECK(testWallet.SelectCoinsMinConf(COIN, filter_standard, vCoins, setCoinsRet , nValueRet, coin_selection_params, bnb_used)); - BOOST_CHECK(testWallet.SelectCoinsMinConf(COIN, filter_standard, vCoins, setCoinsRet2, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(testWallet.SelectCoinsMinConf(COIN, filter_standard, GroupCoins(vCoins), setCoinsRet , nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(testWallet.SelectCoinsMinConf(COIN, filter_standard, GroupCoins(vCoins), setCoinsRet2, nValueRet, coin_selection_params, bnb_used)); if (equal_sets(setCoinsRet, setCoinsRet2)) fails++; } @@ -495,8 +511,8 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) { // selecting 1 from 100 identical coins depends on the shuffle; this test will fail 1% of the time // run the test RANDOM_REPEATS times and only complain if all of them fail - BOOST_CHECK(testWallet.SelectCoinsMinConf(90*CENT, filter_standard, vCoins, setCoinsRet , nValueRet, coin_selection_params, bnb_used)); - BOOST_CHECK(testWallet.SelectCoinsMinConf(90*CENT, filter_standard, vCoins, setCoinsRet2, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(testWallet.SelectCoinsMinConf(90*CENT, filter_standard, GroupCoins(vCoins), setCoinsRet , nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(testWallet.SelectCoinsMinConf(90*CENT, filter_standard, GroupCoins(vCoins), setCoinsRet2, nValueRet, coin_selection_params, bnb_used)); if (equal_sets(setCoinsRet, setCoinsRet2)) fails++; } @@ -521,7 +537,7 @@ BOOST_AUTO_TEST_CASE(ApproximateBestSubset) add_coin(1000 * COIN); add_coin(3 * COIN); - BOOST_CHECK(testWallet.SelectCoinsMinConf(1003 * COIN, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(testWallet.SelectCoinsMinConf(1003 * COIN, filter_standard, GroupCoins(vCoins), setCoinsRet, nValueRet, coin_selection_params, bnb_used)); BOOST_CHECK_EQUAL(nValueRet, 1003 * COIN); BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U); @@ -559,8 +575,8 @@ BOOST_AUTO_TEST_CASE(SelectCoins_test) CoinSet out_set; CAmount out_value = 0; bool bnb_used = false; - BOOST_CHECK(testWallet.SelectCoinsMinConf(target, filter_standard, vCoins, out_set, out_value, coin_selection_params_bnb, bnb_used) || - testWallet.SelectCoinsMinConf(target, filter_standard, vCoins, out_set, out_value, coin_selection_params_knapsack, bnb_used)); + BOOST_CHECK(testWallet.SelectCoinsMinConf(target, filter_standard, GroupCoins(vCoins), out_set, out_value, coin_selection_params_bnb, bnb_used) || + testWallet.SelectCoinsMinConf(target, filter_standard, GroupCoins(vCoins), out_set, out_value, coin_selection_params_knapsack, bnb_used)); BOOST_CHECK_GE(out_value, target); } } diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index d38f943558..3ec6aefaec 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -2415,32 +2415,14 @@ const CTxOut& CWallet::FindNonChangeParentOutput(const CTransaction& tx, int out return ptx->vout[n]; } -bool CWallet::OutputEligibleForSpending(const COutput& output, const CoinEligibilityFilter& eligibility_filter) const -{ - if (!output.fSpendable) - return false; - - if (output.nDepth < (output.tx->IsFromMe(ISMINE_ALL) ? eligibility_filter.conf_mine : eligibility_filter.conf_theirs)) - return false; - - size_t ancestors, descendants; - mempool.GetTransactionAncestry(output.tx->GetHash(), ancestors, descendants); - if (ancestors > eligibility_filter.max_ancestors || descendants > eligibility_filter.max_descendants) { - return false; - } - - return true; -} - -bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<COutput> vCoins, +bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<OutputGroup> groups, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CoinSelectionParams& coin_selection_params, bool& bnb_used) const { setCoinsRet.clear(); nValueRet = 0; - std::vector<CInputCoin> utxo_pool; + std::vector<OutputGroup> utxo_pool; if (coin_selection_params.use_bnb) { - // Get long term estimate FeeCalculation feeCalc; CCoinControl temp; @@ -2451,19 +2433,26 @@ bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibil CAmount cost_of_change = GetDiscardRate(*this, ::feeEstimator).GetFee(coin_selection_params.change_spend_size) + coin_selection_params.effective_fee.GetFee(coin_selection_params.change_output_size); // Filter by the min conf specs and add to utxo_pool and calculate effective value - for (const COutput &output : vCoins) - { - if (!OutputEligibleForSpending(output, eligibility_filter)) - continue; - - CInputCoin coin(output.tx->tx, output.i); - coin.effective_value = coin.txout.nValue - (output.nInputBytes < 0 ? 0 : coin_selection_params.effective_fee.GetFee(output.nInputBytes)); - // Only include outputs that are positive effective value (i.e. not dust) - if (coin.effective_value > 0) { - coin.fee = output.nInputBytes < 0 ? 0 : coin_selection_params.effective_fee.GetFee(output.nInputBytes); - coin.long_term_fee = output.nInputBytes < 0 ? 0 : long_term_feerate.GetFee(output.nInputBytes); - utxo_pool.push_back(coin); + for (OutputGroup& group : groups) { + if (!group.EligibleForSpending(eligibility_filter)) continue; + + group.fee = 0; + group.long_term_fee = 0; + group.effective_value = 0; + for (auto it = group.m_outputs.begin(); it != group.m_outputs.end(); ) { + const CInputCoin& coin = *it; + CAmount effective_value = coin.txout.nValue - (coin.m_input_bytes < 0 ? 0 : coin_selection_params.effective_fee.GetFee(coin.m_input_bytes)); + // Only include outputs that are positive effective value (i.e. not dust) + if (effective_value > 0) { + group.fee += coin.m_input_bytes < 0 ? 0 : coin_selection_params.effective_fee.GetFee(coin.m_input_bytes); + group.long_term_fee += coin.m_input_bytes < 0 ? 0 : long_term_feerate.GetFee(coin.m_input_bytes); + group.effective_value += effective_value; + ++it; + } else { + it = group.Discard(coin); + } } + if (group.effective_value > 0) utxo_pool.push_back(group); } // Calculate the fees for things that aren't inputs CAmount not_input_fees = coin_selection_params.effective_fee.GetFee(coin_selection_params.tx_noinputs_size); @@ -2471,13 +2460,9 @@ bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibil return SelectCoinsBnB(utxo_pool, nTargetValue, cost_of_change, setCoinsRet, nValueRet, not_input_fees); } else { // Filter by the min conf specs and add to utxo_pool - for (const COutput &output : vCoins) - { - if (!OutputEligibleForSpending(output, eligibility_filter)) - continue; - - CInputCoin coin = CInputCoin(output.tx->tx, output.i); - utxo_pool.push_back(coin); + for (const OutputGroup& group : groups) { + if (!group.EligibleForSpending(eligibility_filter)) continue; + utxo_pool.push_back(group); } bnb_used = false; return KnapsackSolver(nTargetValue, utxo_pool, setCoinsRet, nValueRet); @@ -2499,7 +2484,7 @@ bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAm if (!out.fSpendable) continue; nValueRet += out.tx->tx->vout[out.i].nValue; - setCoinsRet.insert(CInputCoin(out.tx->tx, out.i)); + setCoinsRet.insert(out.GetInputCoin()); } return (nValueRet >= nTargetValue); } @@ -2533,27 +2518,31 @@ bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAm // remove preset inputs from vCoins for (std::vector<COutput>::iterator it = vCoins.begin(); it != vCoins.end() && coin_control.HasSelected();) { - if (setPresetCoins.count(CInputCoin(it->tx->tx, it->i))) + if (setPresetCoins.count(it->GetInputCoin())) it = vCoins.erase(it); else ++it; } + // form groups from remaining coins; note that preset coins will not + // automatically have their associated (same address) coins included + std::vector<OutputGroup> groups = GroupOutputs(vCoins, !coin_control.m_avoid_partial_spends); + size_t max_ancestors = (size_t)std::max<int64_t>(1, gArgs.GetArg("-limitancestorcount", DEFAULT_ANCESTOR_LIMIT)); size_t max_descendants = (size_t)std::max<int64_t>(1, gArgs.GetArg("-limitdescendantcount", DEFAULT_DESCENDANT_LIMIT)); bool fRejectLongChains = gArgs.GetBoolArg("-walletrejectlongchains", DEFAULT_WALLET_REJECT_LONG_CHAINS); bool res = nTargetValue <= nValueFromPresetInputs || - SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(1, 6, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used) || - SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(1, 1, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used) || - (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, 2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) || - (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, std::min((size_t)4, max_ancestors/3), std::min((size_t)4, max_descendants/3)), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) || - (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) || - (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) || - (m_spend_zero_conf_change && !fRejectLongChains && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, std::numeric_limits<uint64_t>::max()), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(1, 6, 0), groups, setCoinsRet, nValueRet, coin_selection_params, bnb_used) || + SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(1, 1, 0), groups, setCoinsRet, nValueRet, coin_selection_params, bnb_used) || + (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, 2), groups, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) || + (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, std::min((size_t)4, max_ancestors/3), std::min((size_t)4, max_descendants/3)), groups, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) || + (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2), groups, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) || + (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1), groups, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) || + (m_spend_zero_conf_change && !fRejectLongChains && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, std::numeric_limits<uint64_t>::max()), groups, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); // because SelectCoinsMinConf clears the setCoinsRet, we now add the possible inputs to the coinset - setCoinsRet.insert(setPresetCoins.begin(), setPresetCoins.end()); + util::insert(setCoinsRet, setPresetCoins); // add preset inputs to the total value selected nValueRet += nValueFromPresetInputs; @@ -2667,7 +2656,7 @@ OutputType CWallet::TransactionChangeType(OutputType change_type, const std::vec } bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CTransactionRef& tx, CReserveKey& reservekey, CAmount& nFeeRet, - int& nChangePosInOut, std::string& strFailReason, const CCoinControl& coin_control, bool sign) + int& nChangePosInOut, std::string& strFailReason, const CCoinControl& coin_control, bool sign) { CAmount nValue = 0; int nChangePosRequest = nChangePosInOut; @@ -4439,3 +4428,29 @@ void CWallet::LearnAllRelatedScripts(const CPubKey& key) LearnRelatedScripts(key, OutputType::P2SH_SEGWIT); } +std::vector<OutputGroup> CWallet::GroupOutputs(const std::vector<COutput>& outputs, bool single_coin) const { + std::vector<OutputGroup> groups; + std::map<CTxDestination, OutputGroup> gmap; + CTxDestination dst; + for (const auto& output : outputs) { + if (output.fSpendable) { + CInputCoin input_coin = output.GetInputCoin(); + + size_t ancestors, descendants; + mempool.GetTransactionAncestry(output.tx->GetHash(), ancestors, descendants); + if (!single_coin && ExtractDestination(output.tx->tx->vout[output.i].scriptPubKey, dst)) { + if (gmap.count(dst) == 10) { + groups.push_back(gmap[dst]); + gmap.erase(dst); + } + gmap[dst].Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants); + } else { + groups.emplace_back(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants); + } + } + } + if (!single_coin) { + for (const auto& it : gmap) groups.push_back(it.second); + } + return groups; +} diff --git a/src/wallet/wallet.h b/src/wallet/wallet.h index 85d7209a1d..122649d575 100644 --- a/src/wallet/wallet.h +++ b/src/wallet/wallet.h @@ -55,6 +55,8 @@ static const CAmount WALLET_INCREMENTAL_RELAY_FEE = 5000; static const bool DEFAULT_SPEND_ZEROCONF_CHANGE = true; //! Default for -walletrejectlongchains static const bool DEFAULT_WALLET_REJECT_LONG_CHAINS = false; +//! Default for -avoidpartialspends +static const bool DEFAULT_AVOIDPARTIALSPENDS = false; //! -txconfirmtarget default static const unsigned int DEFAULT_TX_CONFIRM_TARGET = 6; //! -walletrbf default @@ -525,10 +527,12 @@ public: } std::string ToString() const; -}; - - + inline CInputCoin GetInputCoin() const + { + return CInputCoin(tx->tx, i, nInputBytes); + } +}; /** Private key that includes an expiration date in case it never gets used. */ class CWalletKey @@ -652,17 +656,6 @@ struct CoinSelectionParams CoinSelectionParams() {} }; -struct CoinEligibilityFilter -{ - const int conf_mine; - const int conf_theirs; - const uint64_t max_ancestors; - const uint64_t max_descendants; - - CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_descendants(max_ancestors) {} - CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_descendants) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_descendants(max_descendants) {} -}; - class WalletRescanReserver; //forward declarations for ScanForWalletTransactions/RescanFromTime /** * A CWallet is an extension of a keystore, which also maintains a set of transactions and balances, @@ -864,10 +857,11 @@ public: * completion the coin set and corresponding actual target value is * assembled */ - bool SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<COutput> vCoins, + bool SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<OutputGroup> groups, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CoinSelectionParams& coin_selection_params, bool& bnb_used) const; bool IsSpent(const uint256& hash, unsigned int n) const; + std::vector<OutputGroup> GroupOutputs(const std::vector<COutput>& outputs, bool single_coin) const; bool IsLockedCoin(uint256 hash, unsigned int n) const EXCLUSIVE_LOCKS_REQUIRED(cs_wallet); void LockCoin(const COutPoint& output) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet); @@ -1194,9 +1188,6 @@ public: */ void LearnAllRelatedScripts(const CPubKey& key); - /** Whether a given output is spendable by this wallet */ - bool OutputEligibleForSpending(const COutput& output, const CoinEligibilityFilter& eligibility_filter) const; - /** set a single wallet flag */ void SetWalletFlag(uint64_t flags); diff --git a/test/functional/test_runner.py b/test/functional/test_runner.py index 4c5acf69a9..d324cd9bba 100755 --- a/test/functional/test_runner.py +++ b/test/functional/test_runner.py @@ -105,6 +105,7 @@ BASE_SCRIPTS = [ 'rpc_users.py', 'feature_proxy.py', 'rpc_signrawtransaction.py', + 'wallet_groups.py', 'p2p_disconnect_ban.py', 'rpc_decodescript.py', 'rpc_blockchain.py', diff --git a/test/functional/wallet_groups.py b/test/functional/wallet_groups.py new file mode 100755 index 0000000000..0d27815da0 --- /dev/null +++ b/test/functional/wallet_groups.py @@ -0,0 +1,67 @@ +#!/usr/bin/env python3 +# Copyright (c) 2018 The Bitcoin Core developers +# Distributed under the MIT software license, see the accompanying +# file COPYING or http://www.opensource.org/licenses/mit-license.php. +"""Test wallet group functionality.""" + +from test_framework.test_framework import BitcoinTestFramework +from test_framework.util import ( + assert_equal, +) + +def assert_approx(v, vexp, vspan=0.00001): + if v < vexp - vspan: + raise AssertionError("%s < [%s..%s]" % (str(v), str(vexp - vspan), str(vexp + vspan))) + if v > vexp + vspan: + raise AssertionError("%s > [%s..%s]" % (str(v), str(vexp - vspan), str(vexp + vspan))) + +class WalletGroupTest(BitcoinTestFramework): + def set_test_params(self): + self.setup_clean_chain = True + self.num_nodes = 3 + self.extra_args = [[], [], ['-avoidpartialspends']] + + def run_test (self): + # Mine some coins + self.nodes[0].generate(110) + + # Get some addresses from the two nodes + addr1 = [self.nodes[1].getnewaddress() for i in range(3)] + addr2 = [self.nodes[2].getnewaddress() for i in range(3)] + addrs = addr1 + addr2 + + # Send 1 + 0.5 coin to each address + [self.nodes[0].sendtoaddress(addr, 1.0) for addr in addrs] + [self.nodes[0].sendtoaddress(addr, 0.5) for addr in addrs] + + self.nodes[0].generate(1) + self.sync_all() + + # For each node, send 0.2 coins back to 0; + # - node[1] should pick one 0.5 UTXO and leave the rest + # - node[2] should pick one (1.0 + 0.5) UTXO group corresponding to a + # given address, and leave the rest + txid1 = self.nodes[1].sendtoaddress(self.nodes[0].getnewaddress(), 0.2) + tx1 = self.nodes[1].getrawtransaction(txid1, True) + # txid1 should have 1 input and 2 outputs + assert_equal(1, len(tx1["vin"])) + assert_equal(2, len(tx1["vout"])) + # one output should be 0.2, the other should be ~0.3 + v = [vout["value"] for vout in tx1["vout"]] + v.sort() + assert_approx(v[0], 0.2) + assert_approx(v[1], 0.3, 0.0001) + + txid2 = self.nodes[2].sendtoaddress(self.nodes[0].getnewaddress(), 0.2) + tx2 = self.nodes[2].getrawtransaction(txid2, True) + # txid2 should have 2 inputs and 2 outputs + assert_equal(2, len(tx2["vin"])) + assert_equal(2, len(tx2["vout"])) + # one output should be 0.2, the other should be ~1.3 + v = [vout["value"] for vout in tx2["vout"]] + v.sort() + assert_approx(v[0], 0.2) + assert_approx(v[1], 1.3, 0.0001) + +if __name__ == '__main__': + WalletGroupTest().main () diff --git a/test/lint/lint-includes.sh b/test/lint/lint-includes.sh index 2faaef8954..8f7a1fd76b 100755 --- a/test/lint/lint-includes.sh +++ b/test/lint/lint-includes.sh @@ -49,7 +49,6 @@ EXPECTED_BOOST_INCLUDES=( boost/algorithm/string.hpp boost/algorithm/string/case_conv.hpp boost/algorithm/string/classification.hpp - boost/algorithm/string/predicate.hpp boost/algorithm/string/replace.hpp boost/algorithm/string/split.hpp boost/bind.hpp |