aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/test/mempool_tests.cpp178
-rw-r--r--src/txmempool.cpp31
-rw-r--r--src/txmempool.h8
-rw-r--r--src/wallet/wallet.cpp14
-rw-r--r--src/wallet/wallet.h4
5 files changed, 224 insertions, 11 deletions
diff --git a/src/test/mempool_tests.cpp b/src/test/mempool_tests.cpp
index 5ca243f42e..4070642537 100644
--- a/src/test/mempool_tests.cpp
+++ b/src/test/mempool_tests.cpp
@@ -571,4 +571,182 @@ BOOST_AUTO_TEST_CASE(MempoolSizeLimitTest)
SetMockTime(0);
}
+inline CTransactionRef make_tx(std::vector<CAmount>&& output_values, std::vector<CTransactionRef>&& inputs=std::vector<CTransactionRef>(), std::vector<uint32_t>&& input_indices=std::vector<uint32_t>())
+{
+ CMutableTransaction tx = CMutableTransaction();
+ tx.vin.resize(inputs.size());
+ tx.vout.resize(output_values.size());
+ for (size_t i = 0; i < inputs.size(); ++i) {
+ tx.vin[i].prevout.hash = inputs[i]->GetHash();
+ tx.vin[i].prevout.n = input_indices.size() > i ? input_indices[i] : 0;
+ }
+ for (size_t i = 0; i < output_values.size(); ++i) {
+ tx.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL;
+ tx.vout[i].nValue = output_values[i];
+ }
+ return MakeTransactionRef(tx);
+}
+
+#define MK_OUTPUTS(amounts...) std::vector<CAmount>{amounts}
+#define MK_INPUTS(txs...) std::vector<CTransactionRef>{txs}
+#define MK_INPUT_IDX(idxes...) std::vector<uint32_t>{idxes}
+
+BOOST_AUTO_TEST_CASE(MempoolAncestryTests)
+{
+ size_t ancestors, descendants;
+
+ CTxMemPool pool;
+ TestMemPoolEntryHelper entry;
+
+ /* Base transaction */
+ //
+ // [tx1]
+ //
+ CTransactionRef tx1 = make_tx(MK_OUTPUTS(10 * COIN));
+ pool.addUnchecked(tx1->GetHash(), entry.Fee(10000LL).FromTx(tx1));
+
+ // Ancestors / descendants should be 1 / 1 (itself / itself)
+ pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, 1ULL);
+ BOOST_CHECK_EQUAL(descendants, 1ULL);
+
+ /* Child transaction */
+ //
+ // [tx1].0 <- [tx2]
+ //
+ CTransactionRef tx2 = make_tx(MK_OUTPUTS(495 * CENT, 5 * COIN), MK_INPUTS(tx1));
+ pool.addUnchecked(tx2->GetHash(), entry.Fee(10000LL).FromTx(tx2));
+
+ // Ancestors / descendants should be:
+ // transaction ancestors descendants
+ // ============ =========== ===========
+ // tx1 1 (tx1) 2 (tx1,2)
+ // tx2 2 (tx1,2) 2 (tx1,2)
+ pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, 1ULL);
+ BOOST_CHECK_EQUAL(descendants, 2ULL);
+ pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, 2ULL);
+ BOOST_CHECK_EQUAL(descendants, 2ULL);
+
+ /* Grand-child 1 */
+ //
+ // [tx1].0 <- [tx2].0 <- [tx3]
+ //
+ CTransactionRef tx3 = make_tx(MK_OUTPUTS(290 * CENT, 200 * CENT), MK_INPUTS(tx2));
+ pool.addUnchecked(tx3->GetHash(), entry.Fee(10000LL).FromTx(tx3));
+
+ // Ancestors / descendants should be:
+ // transaction ancestors descendants
+ // ============ =========== ===========
+ // tx1 1 (tx1) 3 (tx1,2,3)
+ // tx2 2 (tx1,2) 3 (tx1,2,3)
+ // tx3 3 (tx1,2,3) 3 (tx1,2,3)
+ pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, 1ULL);
+ BOOST_CHECK_EQUAL(descendants, 3ULL);
+ pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, 2ULL);
+ BOOST_CHECK_EQUAL(descendants, 3ULL);
+ pool.GetTransactionAncestry(tx3->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, 3ULL);
+ BOOST_CHECK_EQUAL(descendants, 3ULL);
+
+ /* Grand-child 2 */
+ //
+ // [tx1].0 <- [tx2].0 <- [tx3]
+ // |
+ // \---1 <- [tx4]
+ //
+ CTransactionRef tx4 = make_tx(MK_OUTPUTS(290 * CENT, 250 * CENT), MK_INPUTS(tx2), MK_INPUT_IDX(1));
+ pool.addUnchecked(tx4->GetHash(), entry.Fee(10000LL).FromTx(tx4));
+
+ // Ancestors / descendants should be:
+ // transaction ancestors descendants
+ // ============ =========== ===========
+ // tx1 1 (tx1) 4 (tx1,2,3,4)
+ // tx2 2 (tx1,2) 4 (tx1,2,3,4)
+ // tx3 3 (tx1,2,3) 4 (tx1,2,3,4)
+ // tx4 3 (tx1,2,4) 4 (tx1,2,3,4)
+ pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, 1ULL);
+ BOOST_CHECK_EQUAL(descendants, 4ULL);
+ pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, 2ULL);
+ BOOST_CHECK_EQUAL(descendants, 4ULL);
+ pool.GetTransactionAncestry(tx3->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, 3ULL);
+ BOOST_CHECK_EQUAL(descendants, 4ULL);
+ pool.GetTransactionAncestry(tx4->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, 3ULL);
+ BOOST_CHECK_EQUAL(descendants, 4ULL);
+
+ /* Make an alternate branch that is longer and connect it to tx3 */
+ //
+ // [ty1].0 <- [ty2].0 <- [ty3].0 <- [ty4].0 <- [ty5].0
+ // |
+ // [tx1].0 <- [tx2].0 <- [tx3].0 <- [ty6] --->--/
+ // |
+ // \---1 <- [tx4]
+ //
+ CTransactionRef ty1, ty2, ty3, ty4, ty5;
+ CTransactionRef* ty[5] = {&ty1, &ty2, &ty3, &ty4, &ty5};
+ CAmount v = 5 * COIN;
+ for (uint64_t i = 0; i < 5; i++) {
+ CTransactionRef& tyi = *ty[i];
+ tyi = make_tx(MK_OUTPUTS(v), i > 0 ? MK_INPUTS(*ty[i-1]) : std::vector<CTransactionRef>());
+ v -= 50 * CENT;
+ pool.addUnchecked(tyi->GetHash(), entry.Fee(10000LL).FromTx(tyi));
+ pool.GetTransactionAncestry(tyi->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, i+1);
+ BOOST_CHECK_EQUAL(descendants, i+1);
+ }
+ CTransactionRef ty6 = make_tx(MK_OUTPUTS(5 * COIN), MK_INPUTS(tx3, ty5));
+ pool.addUnchecked(ty6->GetHash(), entry.Fee(10000LL).FromTx(ty6));
+
+ // Ancestors / descendants should be:
+ // transaction ancestors descendants
+ // ============ =================== ===========
+ // tx1 1 (tx1) 5 (tx1,2,3,4, ty6)
+ // tx2 2 (tx1,2) 5 (tx1,2,3,4, ty6)
+ // tx3 3 (tx1,2,3) 5 (tx1,2,3,4, ty6)
+ // tx4 3 (tx1,2,4) 5 (tx1,2,3,4, ty6)
+ // ty1 1 (ty1) 6 (ty1,2,3,4,5,6)
+ // ty2 2 (ty1,2) 6 (ty1,2,3,4,5,6)
+ // ty3 3 (ty1,2,3) 6 (ty1,2,3,4,5,6)
+ // ty4 4 (y1234) 6 (ty1,2,3,4,5,6)
+ // ty5 5 (y12345) 6 (ty1,2,3,4,5,6)
+ // ty6 9 (tx123, ty123456) 6 (ty1,2,3,4,5,6)
+ pool.GetTransactionAncestry(tx1->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, 1ULL);
+ BOOST_CHECK_EQUAL(descendants, 5ULL);
+ pool.GetTransactionAncestry(tx2->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, 2ULL);
+ BOOST_CHECK_EQUAL(descendants, 5ULL);
+ pool.GetTransactionAncestry(tx3->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, 3ULL);
+ BOOST_CHECK_EQUAL(descendants, 5ULL);
+ pool.GetTransactionAncestry(tx4->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, 3ULL);
+ BOOST_CHECK_EQUAL(descendants, 5ULL);
+ pool.GetTransactionAncestry(ty1->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, 1ULL);
+ BOOST_CHECK_EQUAL(descendants, 6ULL);
+ pool.GetTransactionAncestry(ty2->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, 2ULL);
+ BOOST_CHECK_EQUAL(descendants, 6ULL);
+ pool.GetTransactionAncestry(ty3->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, 3ULL);
+ BOOST_CHECK_EQUAL(descendants, 6ULL);
+ pool.GetTransactionAncestry(ty4->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, 4ULL);
+ BOOST_CHECK_EQUAL(descendants, 6ULL);
+ pool.GetTransactionAncestry(ty5->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, 5ULL);
+ BOOST_CHECK_EQUAL(descendants, 6ULL);
+ pool.GetTransactionAncestry(ty6->GetHash(), ancestors, descendants);
+ BOOST_CHECK_EQUAL(ancestors, 9ULL);
+ BOOST_CHECK_EQUAL(descendants, 6ULL);
+}
+
BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index 6f1fd8ce61..1c6dba0c9c 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -1055,11 +1055,36 @@ void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpends
}
}
-bool CTxMemPool::TransactionWithinChainLimit(const uint256& txid, size_t chainLimit) const {
+uint64_t CTxMemPool::CalculateDescendantMaximum(txiter entry) const {
+ // find parent with highest descendant count
+ std::vector<txiter> candidates;
+ setEntries counted;
+ candidates.push_back(entry);
+ uint64_t maximum = 0;
+ while (candidates.size()) {
+ txiter candidate = candidates.back();
+ candidates.pop_back();
+ if (!counted.insert(candidate).second) continue;
+ const setEntries& parents = GetMemPoolParents(candidate);
+ if (parents.size() == 0) {
+ maximum = std::max(maximum, candidate->GetCountWithDescendants());
+ } else {
+ for (txiter i : parents) {
+ candidates.push_back(i);
+ }
+ }
+ }
+ return maximum;
+}
+
+void CTxMemPool::GetTransactionAncestry(const uint256& txid, size_t& ancestors, size_t& descendants) const {
LOCK(cs);
auto it = mapTx.find(txid);
- return it == mapTx.end() || (it->GetCountWithAncestors() < chainLimit &&
- it->GetCountWithDescendants() < chainLimit);
+ ancestors = descendants = 0;
+ if (it != mapTx.end()) {
+ ancestors = it->GetCountWithAncestors();
+ descendants = CalculateDescendantMaximum(it);
+ }
}
SaltedTxidHasher::SaltedTxidHasher() : k0(GetRand(std::numeric_limits<uint64_t>::max())), k1(GetRand(std::numeric_limits<uint64_t>::max())) {}
diff --git a/src/txmempool.h b/src/txmempool.h
index ca7b1cd4be..bda812b42f 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -498,6 +498,7 @@ public:
const setEntries & GetMemPoolParents(txiter entry) const EXCLUSIVE_LOCKS_REQUIRED(cs);
const setEntries & GetMemPoolChildren(txiter entry) const EXCLUSIVE_LOCKS_REQUIRED(cs);
+ uint64_t CalculateDescendantMaximum(txiter entry) const EXCLUSIVE_LOCKS_REQUIRED(cs);
private:
typedef std::map<txiter, setEntries, CompareIteratorByHash> cacheMap;
@@ -619,8 +620,11 @@ public:
/** Expire all transaction (and their dependencies) in the mempool older than time. Return the number of removed transactions. */
int Expire(int64_t time);
- /** Returns false if the transaction is in the mempool and not within the chain limit specified. */
- bool TransactionWithinChainLimit(const uint256& txid, size_t chainLimit) const;
+ /**
+ * Calculate the ancestor and descendant count for the given transaction.
+ * The counts include the transaction itself.
+ */
+ void GetTransactionAncestry(const uint256& txid, size_t& ancestors, size_t& descendants) const;
unsigned long size()
{
diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
index c3597aace8..78cacc0206 100644
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -2469,8 +2469,11 @@ bool CWallet::OutputEligibleForSpending(const COutput& output, const CoinEligibi
if (output.nDepth < (output.tx->IsFromMe(ISMINE_ALL) ? eligibility_filter.conf_mine : eligibility_filter.conf_theirs))
return false;
- if (!mempool.TransactionWithinChainLimit(output.tx->GetHash(), eligibility_filter.max_ancestors))
+ 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;
}
@@ -2582,16 +2585,17 @@ bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAm
++it;
}
- size_t nMaxChainLength = std::min(gArgs.GetArg("-limitancestorcount", DEFAULT_ANCESTOR_LIMIT), gArgs.GetArg("-limitdescendantcount", DEFAULT_DESCENDANT_LIMIT));
+ 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, nMaxChainLength/3)), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
- (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, nMaxChainLength/2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
- (m_spend_zero_conf_change && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, CoinEligibilityFilter(0, 1, nMaxChainLength), 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));
// because SelectCoinsMinConf clears the setCoinsRet, we now add the possible inputs to the coinset
diff --git a/src/wallet/wallet.h b/src/wallet/wallet.h
index f1761b0fcf..1ec2a9e771 100644
--- a/src/wallet/wallet.h
+++ b/src/wallet/wallet.h
@@ -662,8 +662,10 @@ 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) {}
+ 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