diff --git a/src/miner.h b/src/miner.h --- a/src/miner.h +++ b/src/miner.h @@ -300,6 +300,10 @@ * Increments nPackagesSelected / nDescendantsUpdated with corresponding * statistics from the package selection (for logging statistics). */ void addPackageTxs(int &nPackagesSelected, int &nDescendantsUpdated); + // Old version of addPackageTxs + // TODO: DELET THIS ONII-CHAN + void accuratelyAddPackageTxs(int &nPackagesSelected, + int &nDescendantsUpdated); /** Enum for the results from TestForBlock */ enum class TestForBlockResult : uint8_t { diff --git a/src/miner.cpp b/src/miner.cpp --- a/src/miner.cpp +++ b/src/miner.cpp @@ -461,6 +461,246 @@ */ void BlockAssembler::addPackageTxs(int &nPackagesSelected, int &nDescendantsUpdated) { + std::vector txPool; + txPool.reserve(txPool.size()); + + std::unordered_map txLocations; + // Fetch all the transactions in dependency order. + // Complexity: O(n) + txPool.reserve(mempool->mapTx.size()); + size_t idx = 0; + for (const auto &mempoolEntry : mempool->mapTx.get()) { + const CTransactionRef tx = mempoolEntry.GetSharedTx(); + txPool.emplace_back(mempoolEntry.GetSharedTx(), mempoolEntry.GetFee(), + mempoolEntry.GetModifiedFee(), + mempoolEntry.GetTxSize(), + mempoolEntry.GetSigOpCount()); + txLocations[tx->GetId()] = idx; + idx += 1; + } + + // Figure out how many parents transactions have. + // Complexity: O(n + m) where n is transactions, and m is edges. + // + // All the dependencies of a transaction are before the transaction. + // So we can iterate normally, and simply add all the parents to our + // package accumulators to our accumulator to our count. Note: If there + // is a diamond shaped inheritance, we will multi-count. We don't care, the + // extract coputation cost is not worth dealing with it. + std::unordered_set seen; + // Iterate in topographical order + for (auto &entry : txPool) { + // Clear out seen list, for the next transaction. + seen.clear(); + for (const auto &txIn : entry.tx->vin) { + const TxId &parentId = txIn.prevout.GetTxId(); + // Do not count a direct ancestor twice. + // We will count further ancestors twice though. + if (seen.count(parentId) != 0) { + continue; + } + seen.insert(parentId); + auto it = txLocations.find(parentId); + if (it == txLocations.end()) { + // Confirmed parent transaction + // (We know this because the mempool we have was guaranteed to + // be consistent) + continue; + } + // Add the parent data to this transaction + entry.AccountForParent(txPool[it->second]); + } + } + + // Now sort them by package feeRate. + // Complexity: O(n log n) + // + // Sort first by the order of the transaction. All order zero transactions + // can go in based on package fees. + std::sort(txPool.begin(), txPool.end(), + [](const CBlockTemplateEntry &a, const CBlockTemplateEntry &b) { + // We don't care about truncation of fees. If the client + // doesn't get a one sat of fees counted, oh well. The code + // for avoiding division is atrocious. + return a.GetOrder() == b.GetOrder() + ? a.FeeRate() > b.FeeRate() + : a.GetOrder() < b.GetOrder(); + }); + + // Update the locations of all the transactions so we can find them again + // later. Complexity: O(n + m) where n is transactions, and m is edges. + idx = 0; + for (const auto &blockEntry : txPool) { + const CTransactionRef tx = blockEntry.tx; + txLocations[tx->GetId()] = idx; + idx += 1; + } + + // Visit all the transactions in package feeRate order, adding them to the + // block in topological order. Complexity: O(n + m) (and some change for + // visiting diamond dependencies multiple times). + std::unordered_set txnsInvalid; + for (const auto &entry : txPool) { + TxId txId = entry.tx->GetId(); + // Don't reprocess transactions + if (inBlock.count(txId) != 0 || txnsInvalid.count(txId) != 0) { + continue; + } + + // We flag low-fee transactions as invalid, so that higher order + // transactions do not suck them into the block. We know from our + // ordering above that no higher-fee package exists or if it does, it's + // the tail of a higher feerate chain and we'll let it be mined in the + // next block. + if (entry.FeeRate() < blockMinFeeRate) { + txnsInvalid.insert(txId); + continue; + } + + // Visit and include all the parents in the block, checking if they are + // valid. + std::stack> + ancestorStack; + std::stack> addStack; + + // Check if package size would fit in the block. + // We won't need to check it for every ancestor below, because their + // values are included here already + auto blockSizeWithTx = nBlockSize + entry.packageSize; + auto maxBlockSigOps = GetMaxBlockSigOpsCount(blockSizeWithTx); + if (blockSizeWithTx >= nMaxGeneratedBlockSize) { + txnsInvalid.insert(txId); + goto invalid; + } + + // Check if package sigOps would fit in the block + if (nBlockSigOps + entry.packageSigOps >= maxBlockSigOps) { + txnsInvalid.insert(txId); + goto invalid; + } + + ancestorStack.push(entry); + // We do a DFS incase a transaction fails, and we add them to a stack + // for popping into the block. + while (!ancestorStack.empty()) { + const CBlockTemplateEntry &ancestor = ancestorStack.top(); + const TxId &ancestorId = ancestor.tx->GetId(); + + ancestorStack.pop(); + // Add it to the stack of items we will add once we have checked all + // the parents. + addStack.push(ancestor); + + // Must check that lock times are still valid. This can be removed + // once MTP is always enforced as long as reorgs keep the mempool + // consistent. + // + // Old code checks the transaction in context. It doesn't make + // sense to me though... + CValidationState state; + if (!ContextualCheckTransaction(*config, *ancestor.tx.get(), state, + nHeight, nLockTimeCutoff, + nMedianTimePast)) { + // A parent is invalid, we will need to skip the rest of the + // transactions So we don't include (now) invalid child. We will + // visit them later. So we can find all it's children during + // invalid handling. + txnsInvalid.insert(ancestorId); + goto invalid; + } + + // Push all the ancestors on our DFS stack. + for (const auto &txIn : ancestor.tx->vin) { + const TxId &parentId = txIn.prevout.GetTxId(); + bool hasBeenAdded = inBlock.count(parentId) != 0; + bool isInvalid = txnsInvalid.count(parentId) != 0; + if (isInvalid) { + // We must have visited one of the parents before when + // handling a different package. It was invalid, and we need + // to mark this invalid as well. + txnsInvalid.insert(ancestorId); + goto invalid; + } + if (hasBeenAdded) { + // Has already been added to the block. We can skip checking + // it. + continue; + } + // Don't yet mark the transaction as visited. We may need to + // visit it twice in this loop to ensure topological ordering + // when popping off the stack. + + auto it = txLocations.find(parentId); + if (it == txLocations.end()) { + // Confirmed parent transaction + // (We know this because the mempool we have was guaranteed + // to be consistent) + continue; + } + const CBlockTemplateEntry &ancestorParent = txPool[it->second]; + + // Record the parent so we can visit it later. + ancestorStack.push(ancestorParent); + } + } + // We know we can add the transaction here. + // Every item in the package has passed requirements. + while (!addStack.empty()) { + const CBlockTemplateEntry &entryToAdd = addStack.top(); + const TxId &addTxID = entryToAdd.tx->GetId(); + bool hasBeenAdded = inBlock.count(addTxID) != 0; + + addStack.pop(); + // The addStack can have duplicates, so we need to ensure we don't + // add the same transaction twice in this loop. + if (hasBeenAdded) { + continue; + } + inBlock.insert(addTxID); + pblocktemplate->entries.emplace_back( + entryToAdd.tx, entryToAdd.txFee, entryToAdd.txModFee, + entryToAdd.txSize, entryToAdd.txSigOps); + nBlockSize += entryToAdd.txSize; + ++nBlockTx; + nBlockSigOps += entryToAdd.txSigOps; + nFees += entryToAdd.txFee; + } + ++nPackagesSelected; + continue; + invalid: + // Mark all children of the invalid transaction as themselves invalid. + // Don't add anything in this package to a block. + while (!addStack.empty()) { + const CBlockTemplateEntry &child = addStack.top(); + addStack.pop(); + // If we are here, it means we marked one of the parents of an + // addStack item invalid. because the stack is in topological order, + // we can be sure we will mark invalid transactions in order going + // all the way back up to the root transaction. + for (const auto &txIn : child.tx->vin) { + const TxId &parentId = txIn.prevout.GetTxId(); + bool isInvalid = txnsInvalid.count(parentId) != 0; + if (isInvalid) { + txnsInvalid.insert(child.tx->GetId()); + // We can stop here, we only need to find one invalid parent + // to know this is invalid. + break; + } + } + } + continue; + } +} + +/** + * accuratelyAddPackageTxs includes transactions paying a fee by ensuring that + * the partial ordering of transactions is maintained. That is to say + * children come after parents, despite having a potentially larger fee. + * @param[out] nPackagesSelected How many packages were selected + * @param[out] nDescendantsUpdated Number of descendant transactions updated + */ +void BlockAssembler::accuratelyAddPackageTxs(int &nPackagesSelected, + int &nDescendantsUpdated) { // selection algorithm orders the mempool based on feerate of a // transaction including all unconfirmed ancestors. Since we don't remove diff --git a/src/test/miner_tests.cpp b/src/test/miner_tests.cpp --- a/src/test/miner_tests.cpp +++ b/src/test/miner_tests.cpp @@ -139,7 +139,7 @@ BOOST_CHECK(pblocktemplate->block.vtx[3]->GetId() == mediumFeeTxId); // Test that a package below the block min tx fee doesn't get included - tx.vin[0].prevout = COutPoint(highFeeTxId, 0); + tx.vin[0].prevout = COutPoint(txFirst[2]->GetId(), 0); // 0 fee. tx.vout[0].nValue = int64_t(5000000000LL - 1000 - 50000) * SATOSHI; TxId freeTxId = tx.GetId(); @@ -176,11 +176,10 @@ BlockAssembler(config, g_mempool).CreateNewBlock(scriptPubKey); BOOST_CHECK(pblocktemplate->block.vtx[4]->GetId() == freeTxId); BOOST_CHECK(pblocktemplate->block.vtx[5]->GetId() == lowFeeTxId); - // Test that transaction selection properly updates ancestor fee // calculations as ancestor transactions get included in a block. Add a // 0-fee transaction that has 2 outputs. - tx.vin[0].prevout = COutPoint(txFirst[2]->GetId(), 0); + tx.vin[0].prevout = COutPoint(txFirst[3]->GetId(), 0); tx.vout.resize(2); tx.vout[0].nValue = int64_t(5000000000LL - 100000000) * SATOSHI; // 1BCC output. @@ -192,7 +191,7 @@ // This tx can't be mined by itself. tx.vin[0].prevout = COutPoint(freeTxId2, 0); tx.vout.resize(1); - feeToUse = blockMinFeeRate.GetFee(freeTxSize); + feeToUse = blockMinFeeRate.GetFee(freeTxSize + 10); tx.vout[0].nValue = int64_t(5000000000LL - 100000000) * SATOSHI - feeToUse; TxId lowFeeTxId2 = tx.GetId(); g_mempool.addUnchecked( @@ -206,15 +205,20 @@ BOOST_CHECK(txn->GetId() != lowFeeTxId2); } - // This tx will be mineable, and should cause lowFeeTxId2 to be selected as - // well. + // This tx will be mineable, and could hypothetically cause lowFeeTxId2 to + // be selected but shouldn't since we don't continue to update packages, and + // have no way of knowing that its parent has been mined. tx.vin[0].prevout = COutPoint(freeTxId2, 1); // 10k satoshi fee. tx.vout[0].nValue = (100000000 - 10000) * SATOSHI; g_mempool.addUnchecked(tx.GetId(), entry.Fee(10000 * SATOSHI).FromTx(tx)); pblocktemplate = BlockAssembler(config, g_mempool).CreateNewBlock(scriptPubKey); - BOOST_CHECK(pblocktemplate->block.vtx[8]->GetId() == lowFeeTxId2); + // Verify lowFeeTxID still didn't make it in, because we don't update + // packages on the fly. + for (const auto &txn : pblocktemplate->block.vtx) { + BOOST_CHECK(txn->GetId() != lowFeeTxId2); + } } void TestCoinbaseMessageEB(uint64_t eb, std::string cbmsg) { diff --git a/src/txmempool.h b/src/txmempool.h --- a/src/txmempool.h +++ b/src/txmempool.h @@ -351,6 +351,8 @@ struct entry_time {}; struct mining_score {}; struct ancestor_score {}; +struct txid_index {}; +struct insertion_order {}; /** * Information about a mempool transaction. @@ -532,7 +534,9 @@ boost::multi_index::ordered_non_unique< boost::multi_index::tag, boost::multi_index::identity, - CompareTxMemPoolEntryByAncestorFee>>> + CompareTxMemPoolEntryByAncestorFee>, + boost::multi_index::sequenced< + boost::multi_index::tag>>> indexed_transaction_set; mutable CCriticalSection cs; @@ -840,9 +844,6 @@ * when (de)activating forks that result in in-mempool transactions becoming * invalid */ -// multi_index tag names -struct txid_index {}; -struct insertion_order {}; class DisconnectedBlockTransactions { private: