Merge pull request #6722

58254aa Fix stale comment in CTxMemPool::TrimToSize. (Matt Corallo)
2bc5018 Fix comment formatting tabs (Matt Corallo)
8abe0f5 Undo GetMinFee-requires-extra-call-to-hit-0 (Matt Corallo)
9e93640 Drop minRelayTxFee to 1000 (Matt Corallo)
074cb15 Add reasonable test case for mempool trimming (Matt Corallo)
d355cf4 Only call TrimToSize once per reorg/blocks disconnect (Matt Corallo)
794a8ce Implement on-the-fly mempool size limitation. (Matt Corallo)
e6c7b36 Print mempool size in KB when adding txn (Matt Corallo)
241d607 Add CFeeRate += operator (Matt Corallo)
e8bcdce Track (and define) ::minRelayTxFee in CTxMemPool (Matt Corallo)
9c9b66f Fix calling mempool directly, instead of pool, in ATMP (Matt Corallo)
49b6fd5 Add Mempool Expire function to remove old transactions (Pieter Wuille)
78b82f4 Reverse the sort on the mempool's feerate index (Suhas Daftuar)

10 files changed, 361 insertions, 57 deletions

diff --git a/src/amount.h b/src/amount.h
index 90e6b5aa8e..a4c7764cda 100644
--- a/src/amount.h
+++ b/src/amount.h
@@ -51,6 +51,7 @@ public:
     friend bool operator==(const CFeeRate& a, const CFeeRate& b) { return a.nSatoshisPerK == b.nSatoshisPerK; }
     friend bool operator<=(const CFeeRate& a, const CFeeRate& b) { return a.nSatoshisPerK <= b.nSatoshisPerK; }
     friend bool operator>=(const CFeeRate& a, const CFeeRate& b) { return a.nSatoshisPerK >= b.nSatoshisPerK; }
+    CFeeRate& operator+=(const CFeeRate& a) { nSatoshisPerK += a.nSatoshisPerK; return *this; }
     std::string ToString() const;
 
     ADD_SERIALIZE_METHODS;
diff --git a/src/init.cpp b/src/init.cpp
index 75c76e3258..5c961a3ad9 100644
--- a/src/init.cpp
+++ b/src/init.cpp
@@ -320,6 +320,8 @@ std::string HelpMessage(HelpMessageMode mode)
     strUsage += HelpMessageOpt("-dbcache=<n>", strprintf(_("Set database cache size in megabytes (%d to %d, default: %d)"), nMinDbCache, nMaxDbCache, nDefaultDbCache));
     strUsage += HelpMessageOpt("-loadblock=<file>", _("Imports blocks from external blk000??.dat file") + " " + _("on startup"));
     strUsage += HelpMessageOpt("-maxorphantx=<n>", strprintf(_("Keep at most <n> unconnectable transactions in memory (default: %u)"), DEFAULT_MAX_ORPHAN_TRANSACTIONS));
+    strUsage += HelpMessageOpt("-maxmempool=<n>", strprintf(_("Keep the transaction memory pool below <n> megabytes (default: %u)"), DEFAULT_MAX_MEMPOOL_SIZE));
+    strUsage += HelpMessageOpt("-mempoolexpiry=<n>", strprintf(_("Do not keep transactions in the mempool longer than <n> hours (default: %u)"), DEFAULT_MEMPOOL_EXPIRY));
     strUsage += HelpMessageOpt("-par=<n>", strprintf(_("Set the number of script verification threads (%u to %d, 0 = auto, <0 = leave that many cores free, default: %d)"),
         -GetNumCores(), MAX_SCRIPTCHECK_THREADS, DEFAULT_SCRIPTCHECK_THREADS));
 #ifndef WIN32
@@ -840,6 +842,12 @@ bool AppInit2(boost::thread_group& threadGroup, CScheduler& scheduler)
     fCheckBlockIndex = GetBoolArg("-checkblockindex", chainparams.DefaultConsistencyChecks());
     fCheckpointsEnabled = GetBoolArg("-checkpoints", true);
 
+    // -mempoollimit limits
+    int64_t nMempoolSizeLimit = GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000;
+    int64_t nMempoolDescendantSizeLimit = GetArg("-limitdescendantsize", DEFAULT_DESCENDANT_SIZE_LIMIT) * 1000;
+    if (nMempoolSizeLimit < 0 || nMempoolSizeLimit < nMempoolDescendantSizeLimit * 40)
+        return InitError(strprintf(_("Error: -maxmempool must be at least %d MB"), GetArg("-limitdescendantsize", DEFAULT_DESCENDANT_SIZE_LIMIT) / 25));
+
     // -par=0 means autodetect, but nScriptCheckThreads==0 means no concurrency
     nScriptCheckThreads = GetArg("-par", DEFAULT_SCRIPTCHECK_THREADS);
     if (nScriptCheckThreads <= 0)
diff --git a/src/main.cpp b/src/main.cpp
index e931d40c94..d870280e99 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -75,7 +75,7 @@ uint64_t nPruneTarget = 0;
 bool fAlerts = DEFAULT_ALERTS;
 
 /** Fees smaller than this (in satoshi) are considered zero fee (for relaying and mining) */
-CFeeRate minRelayTxFee = CFeeRate(5000);
+CFeeRate minRelayTxFee = CFeeRate(1000);
 
 CTxMemPool mempool(::minRelayTxFee);
 
@@ -740,17 +740,14 @@ bool CheckTransaction(const CTransaction& tx, CValidationState &state)
     return true;
 }
 
-CAmount GetMinRelayFee(const CTransaction& tx, unsigned int nBytes, bool fAllowFree)
+CAmount GetMinRelayFee(const CTransaction& tx, const CTxMemPool& pool, unsigned int nBytes, bool fAllowFree)
 {
-    {
-        LOCK(mempool.cs);
-        uint256 hash = tx.GetHash();
-        double dPriorityDelta = 0;
-        CAmount nFeeDelta = 0;
-        mempool.ApplyDeltas(hash, dPriorityDelta, nFeeDelta);
-        if (dPriorityDelta > 0 || nFeeDelta > 0)
-            return 0;
-    }
+    uint256 hash = tx.GetHash();
+    double dPriorityDelta = 0;
+    CAmount nFeeDelta = 0;
+    pool.ApplyDeltas(hash, dPriorityDelta, nFeeDelta);
+    if (dPriorityDelta > 0 || nFeeDelta > 0)
+        return 0;
 
     CAmount nMinFee = ::minRelayTxFee.GetFee(nBytes);
 
@@ -779,7 +776,7 @@ static std::string FormatStateMessage(const CValidationState &state)
 }
 
 bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransaction &tx, bool fLimitFree,
-                        bool* pfMissingInputs, bool fRejectAbsurdFee)
+                        bool* pfMissingInputs, bool fOverrideMempoolLimit, bool fRejectAbsurdFee)
 {
     AssertLockHeld(cs_main);
     if (pfMissingInputs)
@@ -879,17 +876,20 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
         CAmount nFees = nValueIn-nValueOut;
         double dPriority = view.GetPriority(tx, chainActive.Height());
 
-        CTxMemPoolEntry entry(tx, nFees, GetTime(), dPriority, chainActive.Height(), mempool.HasNoInputsOf(tx));
+        CTxMemPoolEntry entry(tx, nFees, GetTime(), dPriority, chainActive.Height(), pool.HasNoInputsOf(tx));
         unsigned int nSize = entry.GetTxSize();
 
         // Don't accept it if it can't get into a block
-        CAmount txMinFee = GetMinRelayFee(tx, nSize, true);
+        CAmount txMinFee = GetMinRelayFee(tx, pool, nSize, true);
         if (fLimitFree && nFees < txMinFee)
             return state.DoS(0, false, REJECT_INSUFFICIENTFEE, "insufficient fee", false,
                 strprintf("%d < %d", nFees, txMinFee));
 
-        // Require that free transactions have sufficient priority to be mined in the next block.
-        if (GetBoolArg("-relaypriority", true) && nFees < ::minRelayTxFee.GetFee(nSize) && !AllowFree(view.GetPriority(tx, chainActive.Height() + 1))) {
+        CAmount mempoolRejectFee = pool.GetMinFee(GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000).GetFee(nSize);
+        if (mempoolRejectFee > 0 && nFees < mempoolRejectFee) {
+            return state.DoS(0, false, REJECT_INSUFFICIENTFEE, "mempool min fee not met", false, strprintf("%d < %d", nFees, mempoolRejectFee));
+        } else if (GetBoolArg("-relaypriority", true) && nFees < ::minRelayTxFee.GetFee(nSize) && !AllowFree(view.GetPriority(tx, chainActive.Height() + 1))) {
+            // Require that free transactions have sufficient priority to be mined in the next block.
             return state.DoS(0, false, REJECT_INSUFFICIENTFEE, "insufficient priority");
         }
 
@@ -954,6 +954,17 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
 
         // Store transaction in memory
         pool.addUnchecked(hash, entry, setAncestors, !IsInitialBlockDownload());
+
+        // trim mempool and check if tx was trimmed
+        if (!fOverrideMempoolLimit) {
+            int expired = pool.Expire(GetTime() - GetArg("-mempoolexpiry", DEFAULT_MEMPOOL_EXPIRY) * 60 * 60);
+            if (expired != 0)
+                LogPrint("mempool", "Expired %i transactions from the memory pool\n", expired);
+
+            pool.TrimToSize(GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000);
+            if (!pool.exists(tx.GetHash()))
+                return state.DoS(0, false, REJECT_INSUFFICIENTFEE, "mempool full");
+        }
     }
 
     SyncWithWallets(tx, NULL);
@@ -2020,7 +2031,7 @@ void static UpdateTip(CBlockIndex *pindexNew) {
     }
 }
 
-/** Disconnect chainActive's tip. */
+/** Disconnect chainActive's tip. You want to manually re-limit mempool size after this */
 bool static DisconnectTip(CValidationState &state) {
     CBlockIndex *pindexDelete = chainActive.Tip();
     assert(pindexDelete);
@@ -2047,7 +2058,7 @@ bool static DisconnectTip(CValidationState &state) {
         // ignore validation errors in resurrected transactions
         list<CTransaction> removed;
         CValidationState stateDummy;
-        if (tx.IsCoinBase() || !AcceptToMemoryPool(mempool, stateDummy, tx, false, NULL)) {
+        if (tx.IsCoinBase() || !AcceptToMemoryPool(mempool, stateDummy, tx, false, NULL, true)) {
             mempool.remove(tx, removed, true);
         } else if (mempool.exists(tx.GetHash())) {
             vHashUpdate.push_back(tx.GetHash());
@@ -2220,9 +2231,11 @@ static bool ActivateBestChainStep(CValidationState &state, CBlockIndex *pindexMo
     const CBlockIndex *pindexFork = chainActive.FindFork(pindexMostWork);
 
     // Disconnect active blocks which are no longer in the best chain.
+    bool fBlocksDisconnected = false;
     while (chainActive.Tip() && chainActive.Tip() != pindexFork) {
         if (!DisconnectTip(state))
             return false;
+        fBlocksDisconnected = true;
     }
 
     // Build list of new blocks to connect.
@@ -2268,6 +2281,9 @@ static bool ActivateBestChainStep(CValidationState &state, CBlockIndex *pindexMo
     }
     }
 
+    if (fBlocksDisconnected)
+        mempool.TrimToSize(GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000);
+
     // Callbacks/notifications for a new best chain.
     if (fInvalidFound)
         CheckForkWarningConditionsOnNewFork(vpindexToConnect.back());
@@ -2354,6 +2370,8 @@ bool InvalidateBlock(CValidationState& state, CBlockIndex *pindex) {
         }
     }
 
+    mempool.TrimToSize(GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000);
+
     // The resulting new best tip may not be in setBlockIndexCandidates anymore, so
     // add it again.
     BlockMap::iterator it = mapBlockIndex.begin();
@@ -4290,10 +4308,10 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv,
             RelayTransaction(tx);
             vWorkQueue.push_back(inv.hash);
 
-            LogPrint("mempool", "AcceptToMemoryPool: peer=%d: accepted %s (poolsz %u)\n",
+            LogPrint("mempool", "AcceptToMemoryPool: peer=%d: accepted %s (poolsz %u txn, %u kB)\n",
                 pfrom->id,
                 tx.GetHash().ToString(),
-                mempool.size());
+                mempool.size(), mempool.DynamicMemoryUsage() / 1000);
 
             // Recursively process any orphan transactions that depended on this one
             set<NodeId> setMisbehaving;
diff --git a/src/main.h b/src/main.h
index a6001eed8f..202d2c772b 100644
--- a/src/main.h
+++ b/src/main.h
@@ -51,6 +51,10 @@ static const unsigned int DEFAULT_ANCESTOR_SIZE_LIMIT = 900;
 static const unsigned int DEFAULT_DESCENDANT_LIMIT = 1000;
 /** Default for -limitdescendantsize, maximum kilobytes of in-mempool descendants */
 static const unsigned int DEFAULT_DESCENDANT_SIZE_LIMIT = 2500;
+/** Default for -maxmempool, maximum megabytes of mempool memory usage */
+static const unsigned int DEFAULT_MAX_MEMPOOL_SIZE = 300;
+/** Default for -mempoolexpiry, expiration time for mempool transactions in hours */
+static const unsigned int DEFAULT_MEMPOOL_EXPIRY = 72;
 /** The maximum size of a blk?????.dat file (since 0.8) */
 static const unsigned int MAX_BLOCKFILE_SIZE = 0x8000000; // 128 MiB
 /** The pre-allocation chunk size for blk?????.dat files (since 0.8) */
@@ -225,7 +229,7 @@ void PruneAndFlush();
 
 /** (try to) add transaction to memory pool **/
 bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransaction &tx, bool fLimitFree,
-                        bool* pfMissingInputs, bool fRejectAbsurdFee=false);
+                        bool* pfMissingInputs, bool fOverrideMempoolLimit=false, bool fRejectAbsurdFee=false);
 
 
 struct CNodeStateStats {
diff --git a/src/rpcrawtransaction.cpp b/src/rpcrawtransaction.cpp
index 4dec53396d..4b96473504 100644
--- a/src/rpcrawtransaction.cpp
+++ b/src/rpcrawtransaction.cpp
@@ -809,7 +809,7 @@ UniValue sendrawtransaction(const UniValue& params, bool fHelp)
         // push to local node and sync with wallets
         CValidationState state;
         bool fMissingInputs;
-        if (!AcceptToMemoryPool(mempool, state, tx, false, &fMissingInputs, !fOverrideFees)) {
+        if (!AcceptToMemoryPool(mempool, state, tx, false, &fMissingInputs, false, !fOverrideFees)) {
             if (state.IsInvalid()) {
                 throw JSONRPCError(RPC_TRANSACTION_REJECTED, strprintf("%i: %s", state.GetRejectCode(), state.GetRejectReason()));
             } else {
diff --git a/src/test/mempool_tests.cpp b/src/test/mempool_tests.cpp
index 5bf1e98e8f..0cf906a259 100644
--- a/src/test/mempool_tests.cpp
+++ b/src/test/mempool_tests.cpp
@@ -153,11 +153,11 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
 
     std::vector<std::string> sortedOrder;
     sortedOrder.resize(5);
-    sortedOrder[0] = tx2.GetHash().ToString(); // 20000
-    sortedOrder[1] = tx4.GetHash().ToString(); // 15000
+    sortedOrder[0] = tx3.GetHash().ToString(); // 0
+    sortedOrder[1] = tx5.GetHash().ToString(); // 10000
     sortedOrder[2] = tx1.GetHash().ToString(); // 10000
-    sortedOrder[3] = tx5.GetHash().ToString(); // 10000
-    sortedOrder[4] = tx3.GetHash().ToString(); // 0
+    sortedOrder[3] = tx4.GetHash().ToString(); // 15000
+    sortedOrder[4] = tx2.GetHash().ToString(); // 20000
     CheckSort(pool, sortedOrder);
 
     /* low fee but with high fee child */
@@ -169,7 +169,7 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
     pool.addUnchecked(tx6.GetHash(), CTxMemPoolEntry(tx6, 0LL, 1, 10.0, 1, true));
     BOOST_CHECK_EQUAL(pool.size(), 6);
     // Check that at this point, tx6 is sorted low
-    sortedOrder.push_back(tx6.GetHash().ToString());
+    sortedOrder.insert(sortedOrder.begin(), tx6.GetHash().ToString());
     CheckSort(pool, sortedOrder);
 
     CTxMemPool::setEntries setAncestors;
@@ -194,9 +194,9 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
     BOOST_CHECK_EQUAL(pool.size(), 7);
 
     // Now tx6 should be sorted higher (high fee child): tx7, tx6, tx2, ...
-    sortedOrder.erase(sortedOrder.end()-1);
-    sortedOrder.insert(sortedOrder.begin(), tx6.GetHash().ToString());
-    sortedOrder.insert(sortedOrder.begin(), tx7.GetHash().ToString());
+    sortedOrder.erase(sortedOrder.begin());
+    sortedOrder.push_back(tx6.GetHash().ToString());
+    sortedOrder.push_back(tx7.GetHash().ToString());
     CheckSort(pool, sortedOrder);
 
     /* low fee child of tx7 */
@@ -211,7 +211,7 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
     pool.addUnchecked(tx8.GetHash(), CTxMemPoolEntry(tx8, 0LL, 2, 10.0, 1, true), setAncestors);
 
     // Now tx8 should be sorted low, but tx6/tx both high
-    sortedOrder.push_back(tx8.GetHash().ToString());
+    sortedOrder.insert(sortedOrder.begin(), tx8.GetHash().ToString());
     CheckSort(pool, sortedOrder);
 
     /* low fee child of tx7 */
@@ -226,7 +226,7 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
 
     // tx9 should be sorted low
     BOOST_CHECK_EQUAL(pool.size(), 9);
-    sortedOrder.push_back(tx9.GetHash().ToString());
+    sortedOrder.insert(sortedOrder.begin(), tx9.GetHash().ToString());
     CheckSort(pool, sortedOrder);
 
     std::vector<std::string> snapshotOrder = sortedOrder;
@@ -255,21 +255,21 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
      *  tx8 and tx9 should both now be sorted higher
      *  Final order after tx10 is added:
      *
-     *  tx7 = 2.2M (4 txs)
-     *  tx6 = 2.2M (5 txs)
-     *  tx10 = 200k (1 tx)
-     *  tx8 = 200k (2 txs)
-     *  tx9 = 200k (2 txs)
-     *  tx2 = 20000 (1)
-     *  tx4 = 15000 (1)
-     *  tx1 = 10000 (1)
-     *  tx5 = 10000 (1)
      *  tx3 = 0 (1)
+     *  tx5 = 10000 (1)
+     *  tx1 = 10000 (1)
+     *  tx4 = 15000 (1)
+     *  tx2 = 20000 (1)
+     *  tx9 = 200k (2 txs)
+     *  tx8 = 200k (2 txs)
+     *  tx10 = 200k (1 tx)
+     *  tx6 = 2.2M (5 txs)
+     *  tx7 = 2.2M (4 txs)
      */
-    sortedOrder.erase(sortedOrder.end()-2, sortedOrder.end()); // take out tx8, tx9 from the end
-    sortedOrder.insert(sortedOrder.begin()+2, tx10.GetHash().ToString()); // tx10 is after tx6
-    sortedOrder.insert(sortedOrder.begin()+3, tx9.GetHash().ToString());
-    sortedOrder.insert(sortedOrder.begin()+3, tx8.GetHash().ToString());
+    sortedOrder.erase(sortedOrder.begin(), sortedOrder.begin()+2); // take out tx9, tx8 from the beginning
+    sortedOrder.insert(sortedOrder.begin()+5, tx9.GetHash().ToString());
+    sortedOrder.insert(sortedOrder.begin()+6, tx8.GetHash().ToString());
+    sortedOrder.insert(sortedOrder.begin()+7, tx10.GetHash().ToString()); // tx10 is just before tx6
     CheckSort(pool, sortedOrder);
 
     // there should be 10 transactions in the mempool
@@ -281,4 +281,157 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
     CheckSort(pool, snapshotOrder);
 }
 
+BOOST_AUTO_TEST_CASE(MempoolSizeLimitTest)
+{
+    CTxMemPool pool(CFeeRate(1000));
+
+    CMutableTransaction tx1 = CMutableTransaction();
+    tx1.vin.resize(1);
+    tx1.vin[0].scriptSig = CScript() << OP_1;
+    tx1.vout.resize(1);
+    tx1.vout[0].scriptPubKey = CScript() << OP_1 << OP_EQUAL;
+    tx1.vout[0].nValue = 10 * COIN;
+    pool.addUnchecked(tx1.GetHash(), CTxMemPoolEntry(tx1, 10000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx1)));
+
+    CMutableTransaction tx2 = CMutableTransaction();
+    tx2.vin.resize(1);
+    tx2.vin[0].scriptSig = CScript() << OP_2;
+    tx2.vout.resize(1);
+    tx2.vout[0].scriptPubKey = CScript() << OP_2 << OP_EQUAL;
+    tx2.vout[0].nValue = 10 * COIN;
+    pool.addUnchecked(tx2.GetHash(), CTxMemPoolEntry(tx2, 5000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx2)));
+
+    pool.TrimToSize(pool.DynamicMemoryUsage()); // should do nothing
+    BOOST_CHECK(pool.exists(tx1.GetHash()));
+    BOOST_CHECK(pool.exists(tx2.GetHash()));
+
+    pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // should remove the lower-feerate transaction
+    BOOST_CHECK(pool.exists(tx1.GetHash()));
+    BOOST_CHECK(!pool.exists(tx2.GetHash()));
+
+    pool.addUnchecked(tx2.GetHash(), CTxMemPoolEntry(tx2, 5000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx2)));
+    CMutableTransaction tx3 = CMutableTransaction();
+    tx3.vin.resize(1);
+    tx3.vin[0].prevout = COutPoint(tx2.GetHash(), 0);
+    tx3.vin[0].scriptSig = CScript() << OP_2;
+    tx3.vout.resize(1);
+    tx3.vout[0].scriptPubKey = CScript() << OP_3 << OP_EQUAL;
+    tx3.vout[0].nValue = 10 * COIN;
+    pool.addUnchecked(tx3.GetHash(), CTxMemPoolEntry(tx3, 20000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx3)));
+
+    pool.TrimToSize(pool.DynamicMemoryUsage() * 3 / 4); // tx3 should pay for tx2 (CPFP)
+    BOOST_CHECK(!pool.exists(tx1.GetHash()));
+    BOOST_CHECK(pool.exists(tx2.GetHash()));
+    BOOST_CHECK(pool.exists(tx3.GetHash()));
+
+    pool.TrimToSize(::GetSerializeSize(CTransaction(tx1), SER_NETWORK, PROTOCOL_VERSION)); // mempool is limited to tx1's size in memory usage, so nothing fits
+    BOOST_CHECK(!pool.exists(tx1.GetHash()));
+    BOOST_CHECK(!pool.exists(tx2.GetHash()));
+    BOOST_CHECK(!pool.exists(tx3.GetHash()));
+
+    CFeeRate maxFeeRateRemoved(25000, ::GetSerializeSize(CTransaction(tx3), SER_NETWORK, PROTOCOL_VERSION) + ::GetSerializeSize(CTransaction(tx2), SER_NETWORK, PROTOCOL_VERSION));
+    BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + 1000);
+
+    CMutableTransaction tx4 = CMutableTransaction();
+    tx4.vin.resize(2);
+    tx4.vin[0].prevout.SetNull();
+    tx4.vin[0].scriptSig = CScript() << OP_4;
+    tx4.vin[1].prevout.SetNull();
+    tx4.vin[1].scriptSig = CScript() << OP_4;
+    tx4.vout.resize(2);
+    tx4.vout[0].scriptPubKey = CScript() << OP_4 << OP_EQUAL;
+    tx4.vout[0].nValue = 10 * COIN;
+    tx4.vout[1].scriptPubKey = CScript() << OP_4 << OP_EQUAL;
+    tx4.vout[1].nValue = 10 * COIN;
+
+    CMutableTransaction tx5 = CMutableTransaction();
+    tx5.vin.resize(2);
+    tx5.vin[0].prevout = COutPoint(tx4.GetHash(), 0);
+    tx5.vin[0].scriptSig = CScript() << OP_4;
+    tx5.vin[1].prevout.SetNull();
+    tx5.vin[1].scriptSig = CScript() << OP_5;
+    tx5.vout.resize(2);
+    tx5.vout[0].scriptPubKey = CScript() << OP_5 << OP_EQUAL;
+    tx5.vout[0].nValue = 10 * COIN;
+    tx5.vout[1].scriptPubKey = CScript() << OP_5 << OP_EQUAL;
+    tx5.vout[1].nValue = 10 * COIN;
+
+    CMutableTransaction tx6 = CMutableTransaction();
+    tx6.vin.resize(2);
+    tx6.vin[0].prevout = COutPoint(tx4.GetHash(), 1);
+    tx6.vin[0].scriptSig = CScript() << OP_4;
+    tx6.vin[1].prevout.SetNull();
+    tx6.vin[1].scriptSig = CScript() << OP_6;
+    tx6.vout.resize(2);
+    tx6.vout[0].scriptPubKey = CScript() << OP_6 << OP_EQUAL;
+    tx6.vout[0].nValue = 10 * COIN;
+    tx6.vout[1].scriptPubKey = CScript() << OP_6 << OP_EQUAL;
+    tx6.vout[1].nValue = 10 * COIN;
+
+    CMutableTransaction tx7 = CMutableTransaction();
+    tx7.vin.resize(2);
+    tx7.vin[0].prevout = COutPoint(tx5.GetHash(), 0);
+    tx7.vin[0].scriptSig = CScript() << OP_5;
+    tx7.vin[1].prevout = COutPoint(tx6.GetHash(), 0);
+    tx7.vin[1].scriptSig = CScript() << OP_6;
+    tx7.vout.resize(2);
+    tx7.vout[0].scriptPubKey = CScript() << OP_7 << OP_EQUAL;
+    tx7.vout[0].nValue = 10 * COIN;
+    tx7.vout[0].scriptPubKey = CScript() << OP_7 << OP_EQUAL;
+    tx7.vout[0].nValue = 10 * COIN;
+
+    pool.addUnchecked(tx4.GetHash(), CTxMemPoolEntry(tx4, 7000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx4)));
+    pool.addUnchecked(tx5.GetHash(), CTxMemPoolEntry(tx5, 1000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx5)));
+    pool.addUnchecked(tx6.GetHash(), CTxMemPoolEntry(tx6, 1100LL, 0, 10.0, 1, pool.HasNoInputsOf(tx6)));
+    pool.addUnchecked(tx7.GetHash(), CTxMemPoolEntry(tx7, 9000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx7)));
+
+    // we only require this remove, at max, 2 txn, because its not clear what we're really optimizing for aside from that
+    pool.TrimToSize(pool.DynamicMemoryUsage() - 1);
+    BOOST_CHECK(pool.exists(tx4.GetHash()));
+    BOOST_CHECK(pool.exists(tx6.GetHash()));
+    BOOST_CHECK(!pool.exists(tx7.GetHash()));
+
+    if (!pool.exists(tx5.GetHash()))
+        pool.addUnchecked(tx5.GetHash(), CTxMemPoolEntry(tx5, 1000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx5)));
+    pool.addUnchecked(tx7.GetHash(), CTxMemPoolEntry(tx7, 9000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx7)));
+
+    pool.TrimToSize(pool.DynamicMemoryUsage() / 2); // should maximize mempool size by only removing 5/7
+    BOOST_CHECK(pool.exists(tx4.GetHash()));
+    BOOST_CHECK(!pool.exists(tx5.GetHash()));
+    BOOST_CHECK(pool.exists(tx6.GetHash()));
+    BOOST_CHECK(!pool.exists(tx7.GetHash()));
+
+    pool.addUnchecked(tx5.GetHash(), CTxMemPoolEntry(tx5, 1000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx5)));
+    pool.addUnchecked(tx7.GetHash(), CTxMemPoolEntry(tx7, 9000LL, 0, 10.0, 1, pool.HasNoInputsOf(tx7)));
+
+    std::vector<CTransaction> vtx;
+    std::list<CTransaction> conflicts;
+    SetMockTime(42);
+    SetMockTime(42 + CTxMemPool::ROLLING_FEE_HALFLIFE);
+    BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), maxFeeRateRemoved.GetFeePerK() + 1000);
+    // ... we should keep the same min fee until we get a block
+    pool.removeForBlock(vtx, 1, conflicts);
+    SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE);
+    BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), (maxFeeRateRemoved.GetFeePerK() + 1000)/2);
+    // ... then feerate should drop 1/2 each halflife
+
+    SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2);
+    BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 5 / 2).GetFeePerK(), (maxFeeRateRemoved.GetFeePerK() + 1000)/4);
+    // ... with a 1/2 halflife when mempool is < 1/2 its target size
+
+    SetMockTime(42 + 2*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4);
+    BOOST_CHECK_EQUAL(pool.GetMinFee(pool.DynamicMemoryUsage() * 9 / 2).GetFeePerK(), (maxFeeRateRemoved.GetFeePerK() + 1000)/8);
+    // ... with a 1/4 halflife when mempool is < 1/4 its target size
+
+    SetMockTime(42 + 7*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4);
+    BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), 1000);
+    // ... but feerate should never drop below 1000
+
+    SetMockTime(42 + 8*CTxMemPool::ROLLING_FEE_HALFLIFE + CTxMemPool::ROLLING_FEE_HALFLIFE/2 + CTxMemPool::ROLLING_FEE_HALFLIFE/4);
+    BOOST_CHECK_EQUAL(pool.GetMinFee(1).GetFeePerK(), 0);
+    // ... unless it has gone all the way to 0 (after getting past 1000/2)
+
+    SetMockTime(0);
+}
+
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/test/txvalidationcache_tests.cpp b/src/test/txvalidationcache_tests.cpp
index edad18644e..9b8e1c088b 100644
--- a/src/test/txvalidationcache_tests.cpp
+++ b/src/test/txvalidationcache_tests.cpp
@@ -23,7 +23,7 @@ ToMemPool(CMutableTransaction& tx)
     LOCK(cs_main);
 
     CValidationState state;
-    return AcceptToMemoryPool(mempool, state, tx, false, NULL, false);
+    return AcceptToMemoryPool(mempool, state, tx, false, NULL, true, false);
 }
 
 BOOST_FIXTURE_TEST_CASE(tx_mempool_block_doublespend, TestChain100Setup)
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index 1370cab0c0..bb148005cd 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -13,6 +13,7 @@
 #include "streams.h"
 #include "util.h"
 #include "utilmoneystr.h"
+#include "utiltime.h"
 #include "version.h"
 
 using namespace std;
@@ -305,15 +306,18 @@ void CTxMemPoolEntry::UpdateState(int64_t modifySize, CAmount modifyFee, int64_t
     }
 }
 
-CTxMemPool::CTxMemPool(const CFeeRate& _minRelayFee) :
+CTxMemPool::CTxMemPool(const CFeeRate& _minReasonableRelayFee) :
     nTransactionsUpdated(0)
 {
+    clear();
+
     // Sanity checks off by default for performance, because otherwise
     // accepting transactions becomes O(N^2) where N is the number
     // of transactions in the pool
     fSanityCheck = false;
 
-    minerPolicyEstimator = new CBlockPolicyEstimator(_minRelayFee);
+    minerPolicyEstimator = new CBlockPolicyEstimator(_minReasonableRelayFee);
+    minReasonableRelayFee = _minReasonableRelayFee;
 }
 
 CTxMemPool::~CTxMemPool()
@@ -538,6 +542,8 @@ void CTxMemPool::removeForBlock(const std::vector<CTransaction>& vtx, unsigned i
     }
     // After the txs in the new block have been removed from the mempool, update policy estimates
     minerPolicyEstimator->processBlock(nBlockHeight, entries, fCurrentEstimate);
+    lastRollingFeeUpdate = GetTime();
+    blockSinceLastRollingFeeBump = true;
 }
 
 void CTxMemPool::clear()
@@ -548,6 +554,9 @@ void CTxMemPool::clear()
     mapNextTx.clear();
     totalTxSize = 0;
     cachedInnerUsage = 0;
+    lastRollingFeeUpdate = GetTime();
+    blockSinceLastRollingFeeBump = false;
+    rollingMinimumFeeRate = 0;
     ++nTransactionsUpdated;
 }
 
@@ -735,10 +744,10 @@ void CTxMemPool::PrioritiseTransaction(const uint256 hash, const string strHash,
     LogPrintf("PrioritiseTransaction: %s priority += %f, fee += %d\n", strHash, dPriorityDelta, FormatMoney(nFeeDelta));
 }
 
-void CTxMemPool::ApplyDeltas(const uint256 hash, double &dPriorityDelta, CAmount &nFeeDelta)
+void CTxMemPool::ApplyDeltas(const uint256 hash, double &dPriorityDelta, CAmount &nFeeDelta) const
 {
     LOCK(cs);
-    std::map<uint256, std::pair<double, CAmount> >::iterator pos = mapDeltas.find(hash);
+    std::map<uint256, std::pair<double, CAmount> >::const_iterator pos = mapDeltas.find(hash);
     if (pos == mapDeltas.end())
         return;
     const std::pair<double, CAmount> &deltas = pos->second;
@@ -792,6 +801,22 @@ void CTxMemPool::RemoveStaged(setEntries &stage) {
     }
 }
 
+int CTxMemPool::Expire(int64_t time) {
+    LOCK(cs);
+    indexed_transaction_set::nth_index<2>::type::iterator it = mapTx.get<2>().begin();
+    setEntries toremove;
+    while (it != mapTx.get<2>().end() && it->GetTime() < time) {
+        toremove.insert(mapTx.project<0>(it));
+        it++;
+    }
+    setEntries stage;
+    BOOST_FOREACH(txiter removeit, toremove) {
+        CalculateDescendants(removeit, stage);
+    }
+    RemoveStaged(stage);
+    return stage.size();
+}
+
 bool CTxMemPool::addUnchecked(const uint256&hash, const CTxMemPoolEntry &entry, bool fCurrentEstimate)
 {
     LOCK(cs);
@@ -837,3 +862,62 @@ const CTxMemPool::setEntries & CTxMemPool::GetMemPoolChildren(txiter entry) cons
     assert(it != mapLinks.end());
     return it->second.children;
 }
+
+CFeeRate CTxMemPool::GetMinFee(size_t sizelimit) const {
+    LOCK(cs);
+    if (!blockSinceLastRollingFeeBump || rollingMinimumFeeRate == 0)
+        return CFeeRate(rollingMinimumFeeRate);
+
+    int64_t time = GetTime();
+    if (time > lastRollingFeeUpdate + 10) {
+        double halflife = ROLLING_FEE_HALFLIFE;
+        if (DynamicMemoryUsage() < sizelimit / 4)
+            halflife /= 4;
+        else if (DynamicMemoryUsage() < sizelimit / 2)
+            halflife /= 2;
+
+        rollingMinimumFeeRate = rollingMinimumFeeRate / pow(2.0, (time - lastRollingFeeUpdate) / halflife);
+        lastRollingFeeUpdate = time;
+
+        if (rollingMinimumFeeRate < minReasonableRelayFee.GetFeePerK() / 2) {
+            rollingMinimumFeeRate = 0;
+            return CFeeRate(0);
+        }
+    }
+    return std::max(CFeeRate(rollingMinimumFeeRate), minReasonableRelayFee);
+}
+
+void CTxMemPool::trackPackageRemoved(const CFeeRate& rate) {
+    AssertLockHeld(cs);
+    if (rate.GetFeePerK() > rollingMinimumFeeRate) {
+        rollingMinimumFeeRate = rate.GetFeePerK();
+        blockSinceLastRollingFeeBump = false;
+    }
+}
+
+void CTxMemPool::TrimToSize(size_t sizelimit) {
+    LOCK(cs);
+
+    unsigned nTxnRemoved = 0;
+    CFeeRate maxFeeRateRemoved(0);
+    while (DynamicMemoryUsage() > sizelimit) {
+        indexed_transaction_set::nth_index<1>::type::iterator it = mapTx.get<1>().begin();
+
+        // We set the new mempool min fee to the feerate of the removed set, plus the
+        // "minimum reasonable fee rate" (ie some value under which we consider txn
+        // to have 0 fee). This way, we don't allow txn to enter mempool with feerate
+        // equal to txn which were removed with no block in between.
+        CFeeRate removed(it->GetFeesWithDescendants(), it->GetSizeWithDescendants());
+        removed += minReasonableRelayFee;
+        trackPackageRemoved(removed);
+        maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed);
+
+        setEntries stage;
+        CalculateDescendants(mapTx.project<0>(it), stage);
+        RemoveStaged(stage);
+        nTxnRemoved += stage.size();
+    }
+
+    if (maxFeeRateRemoved > CFeeRate(0))
+        LogPrint("mempool", "Removed %u txn, rolling minimum fee bumped to %s\n", nTxnRemoved, maxFeeRateRemoved.ToString());
+}
diff --git a/src/txmempool.h b/src/txmempool.h
index c0eef0dd22..d44995eefe 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -83,7 +83,7 @@ public:
 
     const CTransaction& GetTx() const { return this->tx; }
     double GetPriority(unsigned int currentHeight) const;
-    CAmount GetFee() const { return nFee; }
+    const CAmount& GetFee() const { return nFee; }
     size_t GetTxSize() const { return nTxSize; }
     int64_t GetTime() const { return nTime; }
     unsigned int GetHeight() const { return nHeight; }
@@ -160,9 +160,9 @@ public:
         double f2 = aSize * bFees;
 
         if (f1 == f2) {
-            return a.GetTime() < b.GetTime();
+            return a.GetTime() >= b.GetTime();
         }
-        return f1 > f2;
+        return f1 < f2;
     }
 
     // Calculate which feerate to use for an entry (avoiding division).
@@ -211,9 +211,10 @@ public:
  *
  * CTxMemPool::mapTx, and CTxMemPoolEntry bookkeeping:
  *
- * mapTx is a boost::multi_index that sorts the mempool on 2 criteria:
+ * mapTx is a boost::multi_index that sorts the mempool on 3 criteria:
  * - transaction hash
  * - feerate [we use max(feerate of tx, feerate of tx with all descendants)]
+ * - time in mempool
  *
  * Note: the term "descendant" refers to in-mempool transactions that depend on
  * this one, while "ancestor" refers to in-mempool transactions that a given
@@ -284,7 +285,18 @@ private:
     uint64_t totalTxSize; //! sum of all mempool tx' byte sizes
     uint64_t cachedInnerUsage; //! sum of dynamic memory usage of all the map elements (NOT the maps themselves)
 
+    CFeeRate minReasonableRelayFee;
+
+    mutable int64_t lastRollingFeeUpdate;
+    mutable bool blockSinceLastRollingFeeBump;
+    mutable double rollingMinimumFeeRate; //! minimum fee to get into the pool, decreases exponentially
+
+    void trackPackageRemoved(const CFeeRate& rate);
+
 public:
+
+    static const int ROLLING_FEE_HALFLIFE = 60 * 60 * 12; // public only for testing
+
     typedef boost::multi_index_container<
         CTxMemPoolEntry,
         boost::multi_index::indexed_by<
@@ -294,6 +306,11 @@ public:
             boost::multi_index::ordered_non_unique<
                 boost::multi_index::identity<CTxMemPoolEntry>,
                 CompareTxMemPoolEntryByFee
+            >,
+            // sorted by entry time
+            boost::multi_index::ordered_non_unique<
+                boost::multi_index::identity<CTxMemPoolEntry>,
+                CompareTxMemPoolEntryByEntryTime
             >
         >
     > indexed_transaction_set;
@@ -328,7 +345,12 @@ public:
     std::map<COutPoint, CInPoint> mapNextTx;
     std::map<uint256, std::pair<double, CAmount> > mapDeltas;
 
-    CTxMemPool(const CFeeRate& _minRelayFee);
+    /** Create a new CTxMemPool.
+     *  minReasonableRelayFee should be a feerate which is, roughly, somewhere
+     *  around what it "costs" to relay a transaction around the network and
+     *  below which we would reasonably say a transaction has 0-effective-fee.
+     */
+    CTxMemPool(const CFeeRate& _minReasonableRelayFee);
     ~CTxMemPool();
 
     /**
@@ -365,7 +387,7 @@ public:
 
     /** Affect CreateNewBlock prioritisation of transactions */
     void PrioritiseTransaction(const uint256 hash, const std::string strHash, double dPriorityDelta, const CAmount& nFeeDelta);
-    void ApplyDeltas(const uint256 hash, double &dPriorityDelta, CAmount &nFeeDelta);
+    void ApplyDeltas(const uint256 hash, double &dPriorityDelta, CAmount &nFeeDelta) const;
     void ClearPrioritisation(const uint256 hash);
 
 public:
@@ -397,6 +419,20 @@ 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);
 
+    /** 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
+      *  takes the fee rate to go back down all the way to 0. When the feerate
+      *  would otherwise be half of this, it is set to 0 instead.
+      */
+    CFeeRate GetMinFee(size_t sizelimit) const;
+
+    /** Remove transactions from the mempool until its dynamic size is <= sizelimit. */
+    void TrimToSize(size_t sizelimit);
+
+    /** Expire all transaction (and their dependencies) in the mempool older than time. Return the number of removed transactions. */
+    int Expire(int64_t time);
+
     unsigned long size()
     {
         LOCK(cs);
diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
index bd3004061b..3f2d5a05f6 100644
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -2863,6 +2863,6 @@ int CMerkleTx::GetBlocksToMaturity() const
 bool CMerkleTx::AcceptToMemoryPool(bool fLimitFree, bool fRejectAbsurdFee)
 {
     CValidationState state;
-    return ::AcceptToMemoryPool(mempool, state, *this, fLimitFree, NULL, fRejectAbsurdFee);
+    return ::AcceptToMemoryPool(mempool, state, *this, fLimitFree, NULL, false, fRejectAbsurdFee);
 }