diff --git a/src/test/mempool_tests.cpp b/src/test/mempool_tests.cpp --- a/src/test/mempool_tests.cpp +++ b/src/test/mempool_tests.cpp @@ -872,4 +872,191 @@ } } +inline CTransactionRef +make_tx(std::vector &&output_values, + std::vector &&inputs = std::vector(), + std::vector &&input_indices = std::vector()) { + 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 = + COutPoint(inputs[i]->GetId(), + 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 { amounts } +#define MK_INPUTS(txs...) \ + std::vector { txs } +#define MK_INPUT_IDX(idxes...) \ + std::vector { 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->GetId(), entry.Fee(10000 * SATOSHI).FromTx(tx1)); + + // Ancestors / descendants should be 1 / 1 (itself / itself) + pool.GetTransactionAncestry(tx1->GetId(), 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->GetId(), entry.Fee(10000 * SATOSHI).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->GetId(), ancestors, descendants); + BOOST_CHECK_EQUAL(ancestors, 1ULL); + BOOST_CHECK_EQUAL(descendants, 2ULL); + pool.GetTransactionAncestry(tx2->GetId(), 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->GetId(), entry.Fee(10000 * SATOSHI).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->GetId(), ancestors, descendants); + BOOST_CHECK_EQUAL(ancestors, 1ULL); + BOOST_CHECK_EQUAL(descendants, 3ULL); + pool.GetTransactionAncestry(tx2->GetId(), ancestors, descendants); + BOOST_CHECK_EQUAL(ancestors, 2ULL); + BOOST_CHECK_EQUAL(descendants, 3ULL); + pool.GetTransactionAncestry(tx3->GetId(), 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->GetId(), entry.Fee(10000 * SATOSHI).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->GetId(), ancestors, descendants); + BOOST_CHECK_EQUAL(ancestors, 1ULL); + BOOST_CHECK_EQUAL(descendants, 4ULL); + pool.GetTransactionAncestry(tx2->GetId(), ancestors, descendants); + BOOST_CHECK_EQUAL(ancestors, 2ULL); + BOOST_CHECK_EQUAL(descendants, 4ULL); + pool.GetTransactionAncestry(tx3->GetId(), ancestors, descendants); + BOOST_CHECK_EQUAL(ancestors, 3ULL); + BOOST_CHECK_EQUAL(descendants, 4ULL); + pool.GetTransactionAncestry(tx4->GetId(), 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}; + Amount 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()); + v -= 50 * CENT; + pool.addUnchecked(tyi->GetId(), entry.Fee(10000 * SATOSHI).FromTx(tyi)); + pool.GetTransactionAncestry(tyi->GetId(), 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->GetId(), entry.Fee(10000 * SATOSHI).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->GetId(), ancestors, descendants); + BOOST_CHECK_EQUAL(ancestors, 1ULL); + BOOST_CHECK_EQUAL(descendants, 5ULL); + pool.GetTransactionAncestry(tx2->GetId(), ancestors, descendants); + BOOST_CHECK_EQUAL(ancestors, 2ULL); + BOOST_CHECK_EQUAL(descendants, 5ULL); + pool.GetTransactionAncestry(tx3->GetId(), ancestors, descendants); + BOOST_CHECK_EQUAL(ancestors, 3ULL); + BOOST_CHECK_EQUAL(descendants, 5ULL); + pool.GetTransactionAncestry(tx4->GetId(), ancestors, descendants); + BOOST_CHECK_EQUAL(ancestors, 3ULL); + BOOST_CHECK_EQUAL(descendants, 5ULL); + pool.GetTransactionAncestry(ty1->GetId(), ancestors, descendants); + BOOST_CHECK_EQUAL(ancestors, 1ULL); + BOOST_CHECK_EQUAL(descendants, 6ULL); + pool.GetTransactionAncestry(ty2->GetId(), ancestors, descendants); + BOOST_CHECK_EQUAL(ancestors, 2ULL); + BOOST_CHECK_EQUAL(descendants, 6ULL); + pool.GetTransactionAncestry(ty3->GetId(), ancestors, descendants); + BOOST_CHECK_EQUAL(ancestors, 3ULL); + BOOST_CHECK_EQUAL(descendants, 6ULL); + pool.GetTransactionAncestry(ty4->GetId(), ancestors, descendants); + BOOST_CHECK_EQUAL(ancestors, 4ULL); + BOOST_CHECK_EQUAL(descendants, 6ULL); + pool.GetTransactionAncestry(ty5->GetId(), ancestors, descendants); + BOOST_CHECK_EQUAL(ancestors, 5ULL); + BOOST_CHECK_EQUAL(descendants, 6ULL); + pool.GetTransactionAncestry(ty6->GetId(), ancestors, descendants); + BOOST_CHECK_EQUAL(ancestors, 9ULL); + BOOST_CHECK_EQUAL(descendants, 6ULL); +} + BOOST_AUTO_TEST_SUITE_END() diff --git a/src/txmempool.h b/src/txmempool.h --- a/src/txmempool.h +++ b/src/txmempool.h @@ -701,11 +701,11 @@ void LimitSize(size_t limit, unsigned long age); /** - * Returns false if the transaction is in the mempool and not within the - * chain limit specified. + * Calculate the ancestor and descendant count for the given transaction. + * The counts include the transaction itself. */ - bool TransactionWithinChainLimit(const uint256 &txid, size_t ancestor_limit, - size_t descendant_limit) const; + void GetTransactionAncestry(const uint256 &txid, size_t &ancestors, + size_t &descendants) const; unsigned long size() { LOCK(cs); diff --git a/src/txmempool.cpp b/src/txmempool.cpp --- a/src/txmempool.cpp +++ b/src/txmempool.cpp @@ -1241,14 +1241,15 @@ return maximum; } -bool CTxMemPool::TransactionWithinChainLimit(const uint256 &txid, - size_t ancestor_limit, - size_t descendant_limit) const { +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() < ancestor_limit && - CalculateDescendantMaximum(it) < descendant_limit); + ancestors = descendants = 0; + if (it != mapTx.end()) { + ancestors = it->GetCountWithAncestors(); + descendants = CalculateDescendantMaximum(it); + } } SaltedTxidHasher::SaltedTxidHasher() diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -2601,9 +2601,11 @@ return false; } - if (!g_mempool.TransactionWithinChainLimit( - output.tx->GetId(), eligibility_filter.max_ancestors, - eligibility_filter.max_descendants)) { + size_t ancestors, descendants; + g_mempool.GetTransactionAncestry(output.tx->GetId(), ancestors, + descendants); + if (ancestors > eligibility_filter.max_ancestors || + descendants > eligibility_filter.max_descendants) { return false; } @@ -2746,9 +2748,10 @@ } } - size_t nMaxChainLength = std::min( - gArgs.GetArg("-limitancestorcount", DEFAULT_ANCESTOR_LIMIT), - gArgs.GetArg("-limitdescendantcount", DEFAULT_DESCENDANT_LIMIT)); + size_t max_ancestors = std::max( + 1, gArgs.GetArg("-limitancestorcount", DEFAULT_ANCESTOR_LIMIT)); + size_t max_descendants = std::max( + 1, gArgs.GetArg("-limitdescendantcount", DEFAULT_DESCENDANT_LIMIT)); bool fRejectLongChains = gArgs.GetBoolArg( "-walletrejectlongchains", DEFAULT_WALLET_REJECT_LONG_CHAINS); @@ -2765,19 +2768,22 @@ CoinEligibilityFilter(0, 1, 2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) || (bSpendZeroConfChange && - SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, - CoinEligibilityFilter( - 0, 1, std::min((size_t)4, nMaxChainLength / 3)), - vCoins, setCoinsRet, nValueRet, - coin_selection_params, bnb_used)) || + SelectCoinsMinConf( + nTargetValue - nValueFromPresetInputs, + CoinEligibilityFilter(0, 1, std::min(4, max_ancestors / 3), + std::min(4, max_descendants / 3)), + vCoins, setCoinsRet, nValueRet, coin_selection_params, + bnb_used)) || (bSpendZeroConfChange && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, - CoinEligibilityFilter(0, 1, nMaxChainLength / 2), + CoinEligibilityFilter(0, 1, max_ancestors / 2, + max_descendants / 2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) || (bSpendZeroConfChange && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, - CoinEligibilityFilter(0, 1, nMaxChainLength), + CoinEligibilityFilter(0, 1, max_ancestors - 1, + max_descendants - 1), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) || (bSpendZeroConfChange && !fRejectLongChains &&