Skip to content

Commit f3fe836

Browse files
morcosmorcos
committed
Add a score index to the mempool.
The score index is meant to represent the order of priority for being included in a block for miners. Initially this is set to the transactions modified (by any feeDelta) fee rate. Index improvements and unit tests by sdaftuar.
1 parent c49d5bc commit f3fe836

File tree

4 files changed

+106
-12
lines changed

4 files changed

+106
-12
lines changed

‎src/rpcblockchain.cpp‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -190,6 +190,7 @@ UniValue mempoolToJSON(bool fVerbose = false)
190190
UniValue info(UniValue::VOBJ);
191191
info.push_back(Pair("size", (int)e.GetTxSize()));
192192
info.push_back(Pair("fee", ValueFromAmount(e.GetFee())));
193+
info.push_back(Pair("modifiedfee", ValueFromAmount(e.GetModifiedFee())));
193194
info.push_back(Pair("time", e.GetTime()));
194195
info.push_back(Pair("height", (int)e.GetHeight()));
195196
info.push_back(Pair("startingpriority", e.GetPriority(e.GetHeight())));
@@ -247,6 +248,7 @@ UniValue getrawmempool(const UniValue& params, bool fHelp)
247248
" \"transactionid\" : { (json object)\n"
248249
" \"size\" : n, (numeric) transaction size in bytes\n"
249250
" \"fee\" : n, (numeric) transaction fee in " + CURRENCY_UNIT + "\n"
251+
" \"modifiedfee\" : n, (numeric) transaction fee with fee deltas used for mining priority\n"
250252
" \"time\" : n, (numeric) local time transaction entered pool in seconds since 1 Jan 1970 GMT\n"
251253
" \"height\" : n, (numeric) block height when transaction entered pool\n"
252254
" \"startingpriority\" : n, (numeric) priority when transaction entered pool\n"

‎src/test/mempool_tests.cpp‎

Lines changed: 43 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -102,12 +102,13 @@ BOOST_AUTO_TEST_CASE(MempoolRemoveTest)
102102
removed.clear();
103103
}
104104

105+
template<int index>
105106
void CheckSort(CTxMemPool &pool, std::vector<std::string> &sortedOrder)
106107
{
107108
BOOST_CHECK_EQUAL(pool.size(), sortedOrder.size());
108-
CTxMemPool::indexed_transaction_set::nth_index<1>::type::iterator it = pool.mapTx.get<1>().begin();
109+
typename CTxMemPool::indexed_transaction_set::nth_index<index>::type::iterator it = pool.mapTx.get<index>().begin();
109110
int count=0;
110-
for (; it != pool.mapTx.get<1>().end(); ++it, ++count) {
111+
for (; it != pool.mapTx.get<index>().end(); ++it, ++count) {
111112
BOOST_CHECK_EQUAL(it->GetTx().GetHash().ToString(), sortedOrder[count]);
112113
}
113114
}
@@ -163,7 +164,7 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
163164
sortedOrder[2] = tx1.GetHash().ToString(); // 10000
164165
sortedOrder[3] = tx4.GetHash().ToString(); // 15000
165166
sortedOrder[4] = tx2.GetHash().ToString(); // 20000
166-
CheckSort(pool, sortedOrder);
167+
CheckSort<1>(pool, sortedOrder);
167168

168169
/* low fee but with high fee child */
169170
/* tx6 -> tx7 -> tx8, tx9 -> tx10 */
@@ -175,7 +176,7 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
175176
BOOST_CHECK_EQUAL(pool.size(), 6);
176177
// Check that at this point, tx6 is sorted low
177178
sortedOrder.insert(sortedOrder.begin(), tx6.GetHash().ToString());
178-
CheckSort(pool, sortedOrder);
179+
CheckSort<1>(pool, sortedOrder);
179180

180181
CTxMemPool::setEntries setAncestors;
181182
setAncestors.insert(pool.mapTx.find(tx6.GetHash()));
@@ -201,7 +202,7 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
201202
sortedOrder.erase(sortedOrder.begin());
202203
sortedOrder.push_back(tx6.GetHash().ToString());
203204
sortedOrder.push_back(tx7.GetHash().ToString());
204-
CheckSort(pool, sortedOrder);
205+
CheckSort<1>(pool, sortedOrder);
205206

206207
/* low fee child of tx7 */
207208
CMutableTransaction tx8 = CMutableTransaction();
@@ -216,7 +217,7 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
216217

217218
// Now tx8 should be sorted low, but tx6/tx both high
218219
sortedOrder.insert(sortedOrder.begin(), tx8.GetHash().ToString());
219-
CheckSort(pool, sortedOrder);
220+
CheckSort<1>(pool, sortedOrder);
220221

221222
/* low fee child of tx7 */
222223
CMutableTransaction tx9 = CMutableTransaction();
@@ -231,7 +232,7 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
231232
// tx9 should be sorted low
232233
BOOST_CHECK_EQUAL(pool.size(), 9);
233234
sortedOrder.insert(sortedOrder.begin(), tx9.GetHash().ToString());
234-
CheckSort(pool, sortedOrder);
235+
CheckSort<1>(pool, sortedOrder);
235236

236237
std::vector<std::string> snapshotOrder = sortedOrder;
237238

@@ -273,17 +274,50 @@ BOOST_AUTO_TEST_CASE(MempoolIndexingTest)
273274
sortedOrder.insert(sortedOrder.begin()+5, tx9.GetHash().ToString());
274275
sortedOrder.insert(sortedOrder.begin()+6, tx8.GetHash().ToString());
275276
sortedOrder.insert(sortedOrder.begin()+7, tx10.GetHash().ToString()); // tx10 is just before tx6
276-
CheckSort(pool, sortedOrder);
277+
CheckSort<1>(pool, sortedOrder);
277278

278279
// there should be 10 transactions in the mempool
279280
BOOST_CHECK_EQUAL(pool.size(), 10);
280281

281282
// Now try removing tx10 and verify the sort order returns to normal
282283
std::list<CTransaction> removed;
283284
pool.remove(pool.mapTx.find(tx10.GetHash())->GetTx(), removed, true);
284-
CheckSort(pool, snapshotOrder);
285+
CheckSort<1>(pool, snapshotOrder);
286+
287+
pool.remove(pool.mapTx.find(tx9.GetHash())->GetTx(), removed, true);
288+
pool.remove(pool.mapTx.find(tx8.GetHash())->GetTx(), removed, true);
289+
/* Now check the sort on the mining score index.
290+
* Final order should be:
291+
*
292+
* tx7 (2M)
293+
* tx2 (20k)
294+
* tx4 (15000)
295+
* tx1/tx5 (10000)
296+
* tx3/6 (0)
297+
* (Ties resolved by hash)
298+
*/
299+
sortedOrder.clear();
300+
sortedOrder.push_back(tx7.GetHash().ToString());
301+
sortedOrder.push_back(tx2.GetHash().ToString());
302+
sortedOrder.push_back(tx4.GetHash().ToString());
303+
if (tx1.GetHash() < tx5.GetHash()) {
304+
sortedOrder.push_back(tx5.GetHash().ToString());
305+
sortedOrder.push_back(tx1.GetHash().ToString());
306+
} else {
307+
sortedOrder.push_back(tx1.GetHash().ToString());
308+
sortedOrder.push_back(tx5.GetHash().ToString());
309+
}
310+
if (tx3.GetHash() < tx6.GetHash()) {
311+
sortedOrder.push_back(tx6.GetHash().ToString());
312+
sortedOrder.push_back(tx3.GetHash().ToString());
313+
} else {
314+
sortedOrder.push_back(tx3.GetHash().ToString());
315+
sortedOrder.push_back(tx6.GetHash().ToString());
316+
}
317+
CheckSort<3>(pool, sortedOrder);
285318
}
286319

320+
287321
BOOST_AUTO_TEST_CASE(MempoolSizeLimitTest)
288322
{
289323
CTxMemPool pool(CFeeRate(1000));

‎src/txmempool.cpp‎

Lines changed: 22 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,8 @@ CTxMemPoolEntry::CTxMemPoolEntry(const CTransaction& _tx, const CAmount& _nFee,
3636
nFeesWithDescendants = nFee;
3737
CAmount nValueIn = tx.GetValueOut()+nFee;
3838
assert(inChainInputValue <= nValueIn);
39+
40+
feeDelta = 0;
3941
}
4042

4143
CTxMemPoolEntry::CTxMemPoolEntry(const CTxMemPoolEntry& other)
@@ -53,6 +55,11 @@ CTxMemPoolEntry::GetPriority(unsigned int currentHeight) const
5355
return dResult;
5456
}
5557

58+
void CTxMemPoolEntry::UpdateFeeDelta(int64_t newFeeDelta)
59+
{
60+
feeDelta = newFeeDelta;
61+
}
62+
5663
// Update the given tx for any in-mempool descendants.
5764
// Assumes that setMemPoolChildren is correct for the given tx and all
5865
// descendants.
@@ -392,6 +399,15 @@ bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry,
392399
}
393400
UpdateAncestorsOf(true, newit, setAncestors);
394401

402+
// Update transaction's score for any feeDelta created by PrioritiseTransaction
403+
std::map<uint256, std::pair<double, CAmount> >::const_iterator pos = mapDeltas.find(hash);
404+
if (pos != mapDeltas.end()) {
405+
const std::pair<double, CAmount> &deltas = pos->second;
406+
if (deltas.second) {
407+
mapTx.modify(newit, update_fee_delta(deltas.second));
408+
}
409+
}
410+
395411
nTransactionsUpdated++;
396412
totalTxSize += entry.GetTxSize();
397413
minerPolicyEstimator->processTransaction(entry, fCurrentEstimate);
@@ -769,6 +785,10 @@ void CTxMemPool::PrioritiseTransaction(const uint256 hash, const string strHash,
769785
std::pair<double, CAmount> &deltas = mapDeltas[hash];
770786
deltas.first += dPriorityDelta;
771787
deltas.second += nFeeDelta;
788+
txiter it = mapTx.find(hash);
789+
if (it != mapTx.end()) {
790+
mapTx.modify(it, update_fee_delta(deltas.second));
791+
}
772792
}
773793
LogPrintf("PrioritiseTransaction: %s priority += %f, fee += %d\n", strHash, dPriorityDelta, FormatMoney(nFeeDelta));
774794
}
@@ -818,8 +838,8 @@ bool CCoinsViewMemPool::HaveCoins(const uint256 &txid) const {
818838

819839
size_t CTxMemPool::DynamicMemoryUsage() const {
820840
LOCK(cs);
821-
// Estimate the overhead of mapTx to be 9 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
822-
return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 9 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(mapLinks) + cachedInnerUsage;
841+
// Estimate the overhead of mapTx to be 12 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
842+
return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 12 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(mapLinks) + cachedInnerUsage;
823843
}
824844

825845
void CTxMemPool::RemoveStaged(setEntries &stage) {

‎src/txmempool.h‎

Lines changed: 39 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -69,6 +69,7 @@ class CTxMemPoolEntry
6969
CAmount inChainInputValue; //! Sum of all txin values that are already in blockchain
7070
bool spendsCoinbase; //! keep track of transactions that spend a coinbase
7171
unsigned int sigOpCount; //! Legacy sig ops plus P2SH sig op count
72+
int64_t feeDelta; //! Used for determining the priority of the transaction for mining in a block
7273

7374
// Information about descendants of this transaction that are in the
7475
// mempool; if we remove this transaction we must remove all of these
@@ -98,10 +99,13 @@ class CTxMemPoolEntry
9899
unsigned int GetHeight() const { return entryHeight; }
99100
bool WasClearAtEntry() const { return hadNoDependencies; }
100101
unsigned int GetSigOpCount() const { return sigOpCount; }
102+
int64_t GetModifiedFee() const { return nFee + feeDelta; }
101103
size_t DynamicMemoryUsage() const { return nUsageSize; }
102104

103105
// Adjusts the descendant state, if this entry is not dirty.
104106
void UpdateState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount);
107+
// Updates the fee delta used for mining priority score
108+
void UpdateFeeDelta(int64_t feeDelta);
105109

106110
/** We can set the entry to be dirty if doing the full calculation of in-
107111
* mempool descendants will be too expensive, which can potentially happen
@@ -139,6 +143,16 @@ struct set_dirty
139143
{ e.SetDirty(); }
140144
};
141145

146+
struct update_fee_delta
147+
{
148+
update_fee_delta(int64_t _feeDelta) : feeDelta(_feeDelta) { }
149+
150+
void operator() (CTxMemPoolEntry &e) { e.UpdateFeeDelta(feeDelta); }
151+
152+
private:
153+
int64_t feeDelta;
154+
};
155+
142156
// extracts a TxMemPoolEntry's transaction hash
143157
struct mempoolentry_txid
144158
{
@@ -186,6 +200,24 @@ class CompareTxMemPoolEntryByFee
186200
}
187201
};
188202

203+
/** \class CompareTxMemPoolEntryByScore
204+
*
205+
* Sort by score of entry ((fee+delta)/size) in descending order
206+
*/
207+
class CompareTxMemPoolEntryByScore
208+
{
209+
public:
210+
bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b)
211+
{
212+
double f1 = (double)a.GetModifiedFee() * b.GetTxSize();
213+
double f2 = (double)b.GetModifiedFee() * a.GetTxSize();
214+
if (f1 == f2) {
215+
return b.GetTx().GetHash() < a.GetTx().GetHash();
216+
}
217+
return f1 > f2;
218+
}
219+
};
220+
189221
class CompareTxMemPoolEntryByEntryTime
190222
{
191223
public:
@@ -223,10 +255,11 @@ class CInPoint
223255
*
224256
* CTxMemPool::mapTx, and CTxMemPoolEntry bookkeeping:
225257
*
226-
* mapTx is a boost::multi_index that sorts the mempool on 3 criteria:
258+
* mapTx is a boost::multi_index that sorts the mempool on 4 criteria:
227259
* - transaction hash
228260
* - feerate [we use max(feerate of tx, feerate of tx with all descendants)]
229261
* - time in mempool
262+
* - mining score (feerate modified by any fee deltas from PrioritiseTransaction)
230263
*
231264
* Note: the term "descendant" refers to in-mempool transactions that depend on
232265
* this one, while "ancestor" refers to in-mempool transactions that a given
@@ -323,6 +356,11 @@ class CTxMemPool
323356
boost::multi_index::ordered_non_unique<
324357
boost::multi_index::identity<CTxMemPoolEntry>,
325358
CompareTxMemPoolEntryByEntryTime
359+
>,
360+
// sorted by score (for mining prioritization)
361+
boost::multi_index::ordered_unique<
362+
boost::multi_index::identity<CTxMemPoolEntry>,
363+
CompareTxMemPoolEntryByScore
326364
>
327365
>
328366
> indexed_transaction_set;

0 commit comments

Comments
 (0)