From 5891f870d68d90408aa5ce5b597fb574f2d2cbca Mon Sep 17 00:00:00 2001 From: Peter Todd Date: Thu, 22 Oct 2015 14:13:18 -0400 Subject: Add opt-in full-RBF to mempool Replaces transactions already in the mempool if a new transaction seen with a higher fee, specifically both a higher fee per KB and a higher absolute fee. Children are evaluateed for replacement as well, using the mempool package tracking to calculate replaced fees/size. Transactions can opt-out of transaction replacement by setting nSequence >= maxint-1 on all inputs. (which all wallets do already) --- src/main.cpp | 126 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 121 insertions(+), 5 deletions(-) (limited to 'src') diff --git a/src/main.cpp b/src/main.cpp index b8abcff596..274a336ee2 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -831,15 +831,42 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa return state.Invalid(false, REJECT_ALREADY_KNOWN, "txn-already-in-mempool"); // Check for conflicts with in-memory transactions + set setConflicts; { LOCK(pool.cs); // protect pool.mapNextTx - for (unsigned int i = 0; i < tx.vin.size(); i++) + BOOST_FOREACH(const CTxIn &txin, tx.vin) { - COutPoint outpoint = tx.vin[i].prevout; - if (pool.mapNextTx.count(outpoint)) + if (pool.mapNextTx.count(txin.prevout)) { - // Disable replacement feature for now - return state.Invalid(false, REJECT_CONFLICT, "txn-mempool-conflict"); + const CTransaction *ptxConflicting = pool.mapNextTx[txin.prevout].ptx; + if (!setConflicts.count(ptxConflicting->GetHash())) + { + // Allow opt-out of transaction replacement by setting + // nSequence >= maxint-1 on all inputs. + // + // maxint-1 is picked to still allow use of nLockTime by + // non-replacable transactions. All inputs rather than just one + // is for the sake of multi-party protocols, where we don't + // want a single party to be able to disable replacement. + // + // The opt-out ignores descendants as anyone relying on + // first-seen mempool behavior should be checking all + // unconfirmed ancestors anyway; doing otherwise is hopelessly + // insecure. + bool fReplacementOptOut = true; + BOOST_FOREACH(const CTxIn &txin, ptxConflicting->vin) + { + if (txin.nSequence < std::numeric_limits::max()-1) + { + fReplacementOptOut = false; + break; + } + } + if (fReplacementOptOut) + return state.Invalid(false, REJECT_CONFLICT, "txn-mempool-conflict"); + + setConflicts.insert(ptxConflicting->GetHash()); + } } } } @@ -957,6 +984,82 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa return state.DoS(0, false, REJECT_NONSTANDARD, "too-long-mempool-chain", false, errString); } + // A transaction that spends outputs that would be replaced by it is invalid. Now + // that we have the set of all ancestors we can detect this + // pathological case by making sure setConflicts and setAncestors don't + // intersect. + BOOST_FOREACH(CTxMemPool::txiter ancestorIt, setAncestors) + { + const uint256 &hashAncestor = ancestorIt->GetTx().GetHash(); + if (setConflicts.count(hashAncestor)) + { + return state.DoS(10, error("AcceptToMemoryPool: %s spends conflicting transaction %s", + hash.ToString(), + hashAncestor.ToString()), + REJECT_INVALID, "bad-txns-spends-conflicting-tx"); + } + } + + // Check if it's economically rational to mine this transaction rather + // than the ones it replaces. + CAmount nConflictingFees = 0; + size_t nConflictingSize = 0; + if (setConflicts.size()) + { + LOCK(pool.cs); + + // For efficiency we simply sum up the pre-calculated + // fees/size-with-descendants values from the mempool package + // tracking; this does mean the pathological case of diamond tx + // graphs will be overcounted. + BOOST_FOREACH(const uint256 hashConflicting, setConflicts) + { + CTxMemPool::txiter mi = pool.mapTx.find(hashConflicting); + if (mi == pool.mapTx.end()) + continue; + nConflictingFees += mi->GetFeesWithDescendants(); + nConflictingSize += mi->GetSizeWithDescendants(); + } + + // First of all we can't allow a replacement unless it pays greater + // fees than the transactions it conflicts with - if we did the + // bandwidth used by those conflicting transactions would not be + // paid for + if (nFees < nConflictingFees) + { + return state.DoS(0, error("AcceptToMemoryPool: rejecting replacement %s, less fees than conflicting txs; %s < %s", + hash.ToString(), FormatMoney(nFees), FormatMoney(nConflictingFees)), + REJECT_INSUFFICIENTFEE, "insufficient fee"); + } + + // Secondly in addition to paying more fees than the conflicts the + // new transaction must additionally pay for its own bandwidth. + CAmount nDeltaFees = nFees - nConflictingFees; + if (nDeltaFees < ::minRelayTxFee.GetFee(nSize)) + { + return state.DoS(0, + error("AcceptToMemoryPool: rejecting replacement %s, not enough additional fees to relay; %s < %s", + hash.ToString(), + FormatMoney(nDeltaFees), + FormatMoney(::minRelayTxFee.GetFee(nSize))), + REJECT_INSUFFICIENTFEE, "insufficient fee"); + } + + // Finally replace only if we end up with a larger fees-per-kb than + // the replacements. + CFeeRate oldFeeRate(nConflictingFees, nConflictingSize); + CFeeRate newFeeRate(nFees, nSize); + if (newFeeRate <= oldFeeRate) + { + return state.DoS(0, + error("AcceptToMemoryPool: rejecting replacement %s; new feerate %s <= old feerate %s", + hash.ToString(), + newFeeRate.ToString(), + oldFeeRate.ToString()), + REJECT_INSUFFICIENTFEE, "insufficient fee"); + } + } + // Check against previous transactions // This is done last to help prevent CPU exhaustion denial-of-service attacks. if (!CheckInputs(tx, state, view, true, STANDARD_SCRIPT_VERIFY_FLAGS, true)) @@ -977,6 +1080,19 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa __func__, hash.ToString(), FormatStateMessage(state)); } + // Remove conflicting transactions from the mempool + list ltxConflicted; + pool.removeConflicts(tx, ltxConflicted); + + BOOST_FOREACH(const CTransaction &txConflicted, ltxConflicted) + { + LogPrint("mempool", "replacing tx %s with %s for %s BTC additional fees, %d delta bytes\n", + txConflicted.GetHash().ToString(), + hash.ToString(), + FormatMoney(nFees - nConflictingFees), + (int)nSize - (int)nConflictingSize); + } + // Store transaction in memory pool.addUnchecked(hash, entry, setAncestors, !IsInitialBlockDownload()); -- cgit v1.2.3 From fc8c19a07c20ab63f6a69f7494f486204d8f2b7a Mon Sep 17 00:00:00 2001 From: Peter Todd Date: Thu, 29 Oct 2015 22:55:48 -0400 Subject: Prevent low feerate txs from (directly) replacing high feerate txs Previously all conflicting transactions were evaluated as a whole to determine if the feerate was being increased. This meant that low feerate children pulled the feerate down, potentially allowing a high transaction with a high feerate to be replaced by one with a lower feerate. --- src/main.cpp | 62 +++++++++++++++++++++++++++++++++++++----------------------- 1 file changed, 38 insertions(+), 24 deletions(-) (limited to 'src') diff --git a/src/main.cpp b/src/main.cpp index 274a336ee2..10d661b2a8 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -1008,23 +1008,51 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa { LOCK(pool.cs); - // For efficiency we simply sum up the pre-calculated - // fees/size-with-descendants values from the mempool package - // tracking; this does mean the pathological case of diamond tx - // graphs will be overcounted. + CFeeRate newFeeRate(nFees, nSize); BOOST_FOREACH(const uint256 hashConflicting, setConflicts) { CTxMemPool::txiter mi = pool.mapTx.find(hashConflicting); if (mi == pool.mapTx.end()) continue; + + // Don't allow the replacement to reduce the feerate of the + // mempool. + // + // We usually don't want to accept replacements with lower + // feerates than what they replaced as that would lower the + // feerate of the next block. Requiring that the feerate always + // be increased is also an easy-to-reason about way to prevent + // DoS attacks via replacements. + // + // The mining code doesn't (currently) take children into + // account (CPFP) so we only consider the feerates of + // transactions being directly replaced, not their indirect + // descendants. While that does mean high feerate children are + // ignored when deciding whether or not to replace, we do + // require the replacement to pay more overall fees too, + // mitigating most cases. + CFeeRate oldFeeRate(mi->GetFee(), mi->GetTxSize()); + if (newFeeRate <= oldFeeRate) + { + return state.DoS(0, + error("AcceptToMemoryPool: rejecting replacement %s; new feerate %s <= old feerate %s", + hash.ToString(), + newFeeRate.ToString(), + oldFeeRate.ToString()), + REJECT_INSUFFICIENTFEE, "insufficient fee"); + } + + // For efficiency we simply sum up the pre-calculated + // fees/size-with-descendants values from the mempool package + // tracking; this does mean the pathological case of diamond tx + // graphs will be overcounted. nConflictingFees += mi->GetFeesWithDescendants(); nConflictingSize += mi->GetSizeWithDescendants(); } - // First of all we can't allow a replacement unless it pays greater - // fees than the transactions it conflicts with - if we did the - // bandwidth used by those conflicting transactions would not be - // paid for + // The replacement must pay greater fees than the transactions it + // replaces - if we did the bandwidth used by those conflicting + // transactions would not be paid for. if (nFees < nConflictingFees) { return state.DoS(0, error("AcceptToMemoryPool: rejecting replacement %s, less fees than conflicting txs; %s < %s", @@ -1032,8 +1060,8 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa REJECT_INSUFFICIENTFEE, "insufficient fee"); } - // Secondly in addition to paying more fees than the conflicts the - // new transaction must additionally pay for its own bandwidth. + // Finally in addition to paying more fees than the conflicts the + // new transaction must pay for its own bandwidth. CAmount nDeltaFees = nFees - nConflictingFees; if (nDeltaFees < ::minRelayTxFee.GetFee(nSize)) { @@ -1044,20 +1072,6 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa FormatMoney(::minRelayTxFee.GetFee(nSize))), REJECT_INSUFFICIENTFEE, "insufficient fee"); } - - // Finally replace only if we end up with a larger fees-per-kb than - // the replacements. - CFeeRate oldFeeRate(nConflictingFees, nConflictingSize); - CFeeRate newFeeRate(nFees, nSize); - if (newFeeRate <= oldFeeRate) - { - return state.DoS(0, - error("AcceptToMemoryPool: rejecting replacement %s; new feerate %s <= old feerate %s", - hash.ToString(), - newFeeRate.ToString(), - oldFeeRate.ToString()), - REJECT_INSUFFICIENTFEE, "insufficient fee"); - } } // Check against previous transactions -- cgit v1.2.3 From b272ecfdb39f976dd61e35bacb22047da02b3416 Mon Sep 17 00:00:00 2001 From: Peter Todd Date: Fri, 30 Oct 2015 00:04:00 -0400 Subject: Reject replacements that add new unconfirmed inputs --- src/main.cpp | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) (limited to 'src') diff --git a/src/main.cpp b/src/main.cpp index 10d661b2a8..6e238f552e 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -1009,6 +1009,7 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa LOCK(pool.cs); CFeeRate newFeeRate(nFees, nSize); + set setConflictsParents; BOOST_FOREACH(const uint256 hashConflicting, setConflicts) { CTxMemPool::txiter mi = pool.mapTx.find(hashConflicting); @@ -1042,6 +1043,11 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa REJECT_INSUFFICIENTFEE, "insufficient fee"); } + BOOST_FOREACH(const CTxIn &txin, mi->GetTx().vin) + { + setConflictsParents.insert(txin.prevout.hash); + } + // For efficiency we simply sum up the pre-calculated // fees/size-with-descendants values from the mempool package // tracking; this does mean the pathological case of diamond tx @@ -1050,6 +1056,24 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa nConflictingSize += mi->GetSizeWithDescendants(); } + for (unsigned int j = 0; j < tx.vin.size(); j++) + { + // We don't want to accept replacements that require low + // feerate junk to be mined first. Ideally we'd keep track of + // the ancestor feerates and make the decision based on that, + // but for now requiring all new inputs to be confirmed works. + if (!setConflictsParents.count(tx.vin[j].prevout.hash)) + { + // Rather than check the UTXO set - potentially expensive - + // it's cheaper to just check if the new input refers to a + // tx that's in the mempool. + if (pool.mapTx.find(tx.vin[j].prevout.hash) != pool.mapTx.end()) + return state.DoS(0, error("AcceptToMemoryPool: replacement %s adds unconfirmed input, idx %d", + hash.ToString(), j), + REJECT_NONSTANDARD, "replacement-adds-unconfirmed"); + } + } + // The replacement must pay greater fees than the transactions it // replaces - if we did the bandwidth used by those conflicting // transactions would not be paid for. -- cgit v1.2.3 From 73d904009dc25ddfe5d6c4a91a13673c8f5cf87a Mon Sep 17 00:00:00 2001 From: Suhas Daftuar Date: Thu, 29 Oct 2015 22:49:00 -0400 Subject: Improve RBF replacement criteria Fix the calculation of conflicting size/conflicting fees. --- src/main.cpp | 59 +++++++++++++++++++++++++++++++++++++++++++++------------ src/txmempool.h | 9 +++++---- 2 files changed, 52 insertions(+), 16 deletions(-) (limited to 'src') diff --git a/src/main.cpp b/src/main.cpp index 6e238f552e..79d4c91b77 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -1004,18 +1004,39 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa // than the ones it replaces. CAmount nConflictingFees = 0; size_t nConflictingSize = 0; + uint64_t nConflictingCount = 0; + CTxMemPool::setEntries allConflicting; if (setConflicts.size()) { LOCK(pool.cs); CFeeRate newFeeRate(nFees, nSize); set setConflictsParents; - BOOST_FOREACH(const uint256 hashConflicting, setConflicts) + const int maxDescendantsToVisit = 100; + CTxMemPool::setEntries setIterConflicting; + BOOST_FOREACH(const uint256 &hashConflicting, setConflicts) { CTxMemPool::txiter mi = pool.mapTx.find(hashConflicting); if (mi == pool.mapTx.end()) continue; + // Save these to avoid repeated lookups + setIterConflicting.insert(mi); + + // If this entry is "dirty", then we don't have descendant + // state for this transaction, which means we probably have + // lots of in-mempool descendants. + // Don't allow replacements of dirty transactions, to ensure + // that we don't spend too much time walking descendants. + // This should be rare. + if (mi->IsDirty()) { + return state.DoS(0, + error("AcceptToMemoryPool: rejecting replacement %s; cannot replace tx %s with untracked descendants", + hash.ToString(), + mi->GetTx().GetHash().ToString()), + REJECT_NONSTANDARD, "too many potential replacements"); + } + // Don't allow the replacement to reduce the feerate of the // mempool. // @@ -1048,12 +1069,28 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa setConflictsParents.insert(txin.prevout.hash); } - // For efficiency we simply sum up the pre-calculated - // fees/size-with-descendants values from the mempool package - // tracking; this does mean the pathological case of diamond tx - // graphs will be overcounted. - nConflictingFees += mi->GetFeesWithDescendants(); - nConflictingSize += mi->GetSizeWithDescendants(); + nConflictingCount += mi->GetCountWithDescendants(); + } + // This potentially overestimates the number of actual descendants + // but we just want to be conservative to avoid doing too much + // work. + if (nConflictingCount <= maxDescendantsToVisit) { + // If not too many to replace, then calculate the set of + // transactions that would have to be evicted + BOOST_FOREACH(CTxMemPool::txiter it, setIterConflicting) { + pool.CalculateDescendants(it, allConflicting); + } + BOOST_FOREACH(CTxMemPool::txiter it, allConflicting) { + nConflictingFees += it->GetFee(); + nConflictingSize += it->GetTxSize(); + } + } else { + return state.DoS(0, + error("AcceptToMemoryPool: rejecting replacement %s; too many potential replacements (%d > %d)\n", + hash.ToString(), + nConflictingCount, + maxDescendantsToVisit), + REJECT_NONSTANDARD, "too many potential replacements"); } for (unsigned int j = 0; j < tx.vin.size(); j++) @@ -1119,17 +1156,15 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa } // Remove conflicting transactions from the mempool - list ltxConflicted; - pool.removeConflicts(tx, ltxConflicted); - - BOOST_FOREACH(const CTransaction &txConflicted, ltxConflicted) + BOOST_FOREACH(const CTxMemPool::txiter it, allConflicting) { LogPrint("mempool", "replacing tx %s with %s for %s BTC additional fees, %d delta bytes\n", - txConflicted.GetHash().ToString(), + it->GetTx().GetHash().ToString(), hash.ToString(), FormatMoney(nFees - nConflictingFees), (int)nSize - (int)nConflictingSize); } + pool.RemoveStaged(allConflicting); // Store transaction in memory pool.addUnchecked(hash, entry, setAncestors, !IsInitialBlockDownload()); diff --git a/src/txmempool.h b/src/txmempool.h index 7b5843a8d0..3d8ac435f5 100644 --- a/src/txmempool.h +++ b/src/txmempool.h @@ -420,6 +420,11 @@ public: */ bool CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntries &setAncestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString, bool fSearchForParents = true); + /** Populate setDescendants with all in-mempool descendants of hash. + * Assumes that setDescendants includes all in-mempool descendants of anything + * already in it. */ + void CalculateDescendants(txiter it, setEntries &setDescendants); + /** The minimum fee to get into the mempool, which may itself not be enough * for larger-sized transactions. * The minReasonableRelayFee constructor arg is used to bound the time it @@ -493,10 +498,6 @@ private: void UpdateForRemoveFromMempool(const setEntries &entriesToRemove); /** Sever link between specified transaction and direct children. */ void UpdateChildrenForRemoval(txiter entry); - /** Populate setDescendants with all in-mempool descendants of hash. - * Assumes that setDescendants includes all in-mempool descendants of anything - * already in it. */ - void CalculateDescendants(txiter it, setEntries &setDescendants); /** Before calling removeUnchecked for a given transaction, * UpdateForRemoveFromMempool must be called on the entire (dependent) set -- cgit v1.2.3 From 16a2f93629f75d182871f288f0396afe6cdc8504 Mon Sep 17 00:00:00 2001 From: Peter Todd Date: Tue, 10 Nov 2015 17:58:06 -0500 Subject: Fix incorrect locking of mempool during RBF replacement Previously RemoveStaged() was called without pool.cs held. --- src/main.cpp | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) (limited to 'src') diff --git a/src/main.cpp b/src/main.cpp index 79d4c91b77..e3527a83d1 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -1006,10 +1006,13 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa size_t nConflictingSize = 0; uint64_t nConflictingCount = 0; CTxMemPool::setEntries allConflicting; + + // If we don't hold the lock allConflicting might be incomplete; the + // subsequent RemoveStaged() and addUnchecked() calls don't guarantee + // mempool consistency for us. + LOCK(pool.cs); if (setConflicts.size()) { - LOCK(pool.cs); - CFeeRate newFeeRate(nFees, nSize); set setConflictsParents; const int maxDescendantsToVisit = 100; -- cgit v1.2.3