Mining: Skip recent transactions if fee difference is small

sdaftuar commented at 7:59 pm on April 12, 2017: member

After compact blocks (BIP 152), including recently received transactions in a block may lead to propagation delays relative to blocks without such transactions, because recently received transactions may not yet be in peers’ mempools.

Account for this in CreateNewBlock() by adding two new parameters:

-recenttxwindow defines a “recent transaction” as having been received less than this many milliseconds ago
-recenttxstalerate models the additional likelihood of a block being stale because it includes a recent transaction.

Briefly, if I_0 is the block income you’d receive using only non-recent transactions, and I_1 is the income including recently received transactions, and s is the value being used for -recenttxstalerate, then CreateNewBlock is now going to choose the block that doesn’t include recent transactions if I_0 >= (1-s) * I_1.

Notes for reviewers:

I struggled to name and explain these two parameters, so suggestions on alternate/less confusing parameter names and explanation would be appreciated! @ryanofsky suggested -recenttxblockdiscount or -recenttxminingpenalty to try to describe what I called the stale rate; I think those are reasonable suggestions as well.
Suggestions are also welcome for what the defaults should be (in particular, should this be enabled at all by default?)
In my most recent performance measurements of a slightly earlier version of this patch, I measured an approximately 3ms slowdown (~ 7ms -> ~ 10ms) in the transaction selection portion of CreateNewBlock(). I suspect we can optimize CreateNewBlock further, but I’d like to save that for a future PR as this is already a lengthy patch.
The idea in this PR is to produce two block candidates, one with recent transactions and one without, and then compare block income and pick a winner. The candidate which does not include recent transactions is not going to be as good in general as the regular ancestor-feerate-mining algorithm being called on a mempool that doesn’t contain any recent transactions, because for performance reasons we might continue to include low-fee ancestors of recent transactions (ie, we kick out recent transactions from the block, but not their ancestors). Despite this, I think for most reasonable parameters we will be overwhelmingly choosing the block that doesn’t include recent transactions, so I don’t think this is a big deal at the moment. We could try to improve this in the future, however (possibly by adding a smart caching layer on top).
This PR includes a (slow) functional test for the mining code, which I’ve added to the extended test suite.

Thanks @JeremyRubin and @ryanofsky for feedback on an earlier version of this patch.

fanquake added the label Mining on Apr 12, 2017

gmaxwell commented at 8:27 pm on April 14, 2017: contributor

Concept ACK.

luke-jr commented at 6:46 pm on April 19, 2017: member

Concept OK, not so sure about implementation. This seems to be all-or-nothing with regard to recent transactions - wouldn’t you want to evaluate it as a gradient (eg, maybe it makes sense to include 29-second-old txs, but not newer)?

in src/miner.h:35 in a986a97ed4 outdated

30+        block(tmpl.block), vTxFees(tmpl.vTxFees),
31+        vTxSigOpsCost(tmpl.vTxSigOpsCost),
32+        vchCoinbaseCommitment(tmpl.vchCoinbaseCommitment)
33+    {
34+        block.vtx = tmpl.block.vtx;
35+    }

luke-jr commented at 6:46 pm on April 19, 2017:

How does this differ from the default copy constructor?

sdaftuar commented at 4:41 pm on April 20, 2017:

Apparently it doesn’t (I was confused by whether a CBlock could be copy-constructed from another CBlock). Will remove.

Removed in dfd4e73c97818eb57bdf9e34a9085904a5250a92

gmaxwell commented at 0:42 am on April 20, 2017: contributor

@luke-jr You could go hog wild with multiple choices, >X, >Y, >Z second old.. but if its tuned right it should pretty much always be choosing to exclude recent transactions, and the other alternative is just so that you don’t regret your decisions when some bozo sends a very high fee transaction. The marginal gain from more options is going to be pretty small compared to the block creation delay from the CPU costs in considering more options– and what you’ll be mining on instead. E.g. spending another 10ms mining on an empty block is probably not worth whatever gain you could have in considering another recentness level.

It’s also the case that block propagation performance between miners is probably pretty consistent and narrowly spread… meaning that either you made a block that could get everywhere with 0-rtt or you didn’t– and there probably isn’t a lot of space in-between. So I think thats what this is modeling: the no-recent alternative will make it ~everywhere with no round trips, and the other one is going to take a round trip– so you only want it if it pays enough more to justify the increased orphan risk.

luke-jr commented at 0:45 am on April 20, 2017: member

I didn’t mean more options, just that the algorithm could evaluate the age-cost/value initially when building the template rather than building the entire template twice. :)

sdaftuar commented at 3:29 pm on April 21, 2017: member

I didn’t mean more options, just that the algorithm could evaluate the age-cost/value initially when building the template rather than building the entire template twice. :) @luke-jr Well note that this implementation doesn’t build the entire template twice; it copies the template, and throws out the recent transactions and rebuilds from there.

If I understand it right, I think it’s hard to make your suggestion work: the fee adjustment based on time-received is not independent of the other choices you make when selecting transactions (in modeling the binary “0 vs >=1” round trips to relay a block), and trying to model it with an implementation that makes a single pass, where some transactions are evaluated with only local information, is hard to get right. Either you’ll include recent transactions too often because your criteria is too loose, or if your criteria is tighter, you risk giving up too much fee income if network conditions change.

sdaftuar force-pushed on May 6, 2017

sdaftuar commented at 9:59 am on May 6, 2017: member

Rebased

sdaftuar force-pushed on May 6, 2017

in src/miner.cpp:356 in 9ae85a6965 outdated

348@@ -349,10 +349,6 @@ void BlockAssembler::addPackageTxs(int &nPackagesSelected, int &nDescendantsUpda
349     // Keep track of entries that failed inclusion, to avoid duplicate work
350     CTxMemPool::setEntries failedTx;
351 
352-    // Start by adding all descendants of previously added txs to mapModifiedTx
353-    // and modifying them for their already included ancestors
354-    UpdatePackagesForAdded(inBlock, mapModifiedTx);

ryanofsky commented at 6:11 pm on June 9, 2017:

In commit “Eliminate unnecessary call to UpdatePackagesForAdded”

Note: reason this call is not needed is that resetBlock is called right before addPackageTxs, so inBlock will be empty.

in src/miner.cpp:193 in 1d1191ddbd outdated

165@@ -166,9 +166,13 @@ std::unique_ptr<CBlockTemplate> BlockAssembler::CreateNewBlock(const CScript& sc
166     // transaction (which in most cases can be a no-op).
167     fIncludeWitness = IsWitnessEnabled(pindexPrev, chainparams.GetConsensus()) && fMineWitnessTx;
168 
169+    // mapModifiedTx will store sorted packages after they are modified
170+    // because some of their txs are already in the block
171+    indexed_modified_transaction_set mapModifiedTx;

ryanofsky commented at 6:13 pm on June 9, 2017:

In commit “Move mapModifiedTx outside of addPackageTxs”

Note: Reason for the move is to be able to reuse mapModifiedTx when a second addPackageTxs call is added later (to refill the block after removing recent transactions).

in src/miner.h:150 in 1cfa4a9740 outdated

133@@ -134,25 +134,30 @@ struct update_for_parent_inclusion
134 class BlockAssembler
135 {
136 private:
137-    // The constructed block template
138-    std::unique_ptr<CBlockTemplate> pblocktemplate;
139-    // A convenience pointer that always refers to the CBlock in pblocktemplate
140-    CBlock* pblock;
141+    struct WorkingState {

ryanofsky commented at 6:15 pm on June 9, 2017:

In commit “Encapsulate working state for a single call to CNB”

Note: Reason for moving state to this struct is to be able to make a second addPackageTxs() call in a later commit without losing the state of the first call.

in src/miner.cpp:352 in 47c933cd05 outdated

348@@ -348,7 +349,7 @@ void BlockAssembler::addPackageTxs(WorkingState &workState, int &nPackagesSelect
349     {
350         // First try to find a new transaction in mapTx to evaluate.
351         if (mi != mempool.mapTx.get<ancestor_score>().end() &&
352-                SkipMapTxEntry(workState, mempool.mapTx.project<0>(mi), mapModifiedTx, failedTx)) {
353+                SkipMapTxEntry(workState, mempool.mapTx.project<0>(mi), mapModifiedTx, failedTx, nTimeCutoff)) {

ryanofsky commented at 6:36 pm on June 9, 2017:

In commit “Mining: Add not-yet-used option to avoid recent transactions”

I think it might be slightly better to do || mi->GetTime() > nTimeCutoff here instead of modifying SkipMapTxEntry, both for consistency with the mapModifiedTx check below, and because SkipMapTxEntry is already a pretty overloaded function with a paragraph of text describing it, so it’s not like it needs another job.

(Update: done in new version of PR)

in src/miner.cpp:292 in 65af6c9860 outdated

287+            vTxSigOpsCostCopy.push_back(workState.pblocktemplate->vTxSigOpsCost[0]);
288+            continue;
289+        }
290+        CTxMemPool::txiter it = mempool.mapTx.find(ptx->GetHash());
291+        assert(it != mempool.mapTx.end());
292+        if (it->GetTime() < timeCutoff && descendantTransactions.count(it) == 0) {

ryanofsky commented at 6:46 pm on June 9, 2017:

In commit “Add helper to remove transactions from block”

Strictly speaking < should probably be <= to be consistent with the addPackageTxs and SkipMapTxEntry code also applying the cutoff.

(Update: fixed in new version of PR)

in src/miner.cpp:279 in 65af6c9860 outdated

274+    std::vector<CAmount> vTxFeesCopy;
275+    vTxFeesCopy.reserve(vtxCopy.size());
276+    std::vector<int64_t> vTxSigOpsCostCopy;
277+    vTxSigOpsCostCopy.reserve(vtxCopy.size());
278+
279+    CTxMemPool::setEntries skippedTransactions;

ryanofsky commented at 6:56 pm on June 9, 2017:

In commit “Add helper to remove transactions from block

Maybe should be called “removed” rather than “skipped” for consistency with the function name (especially since this gets exposed in the next commit).

(Update: variable is removed in new version of PR)

in src/miner.cpp:376 in c392582000 outdated

371+{
372+    for (const CTxMemPool::txiter it : removed) {
373+        CTxMemPool::setEntries descendants;
374+        mempool.CalculateDescendants(it, descendants);
375+        for(CTxMemPool::txiter desc : descendants) {
376+            if (removed.count(desc)) {

ryanofsky commented at 7:13 pm on June 9, 2017:

In commit “Skip recent transactions in CNB if fee difference is small”

Could you add a comment explaining why this skips updating mapModifiedTx entries of transactions that were removed? I’m probably misunderstanding something, but It seems like if you skip those, you won’t be updating any mapModifiedTx entries at all, because RemoveRecentTransactionsFromBlock also removes descendants.

sdaftuar commented at 8:57 pm on August 15, 2017:

FYI I’ve reworked this code in the latest version, combining the removal of transactions and updating mapModifiedTx, as this was needlessly inefficient (with an extra call to CalculateDescendants).

But to answer your question: mapModifiedTx contains transactions that are not in the constructed block which have ancestors that are in the block. When we remove a transaction from the block, we need to remove any in-block descendants (which won’t be in mapModifiedTx), but we need to update the ancestor feerate score for the entries in mapModifiedTx, so that the packages are properly sorted.

Since we generally should never select those transactions on the next call to addPackageTxs (outside of reorg situations, the arrival time of a descendant should be later than the arrival time of the parent), it might be better to just remove those descendants from mapModifiedTx rather than correct the package information, but I think its simpler to reason about the code if mapModifiedTx is always sorted correctly.

in src/miner.cpp:253 in c392582000 outdated

229+    if (!TestBlockValidity(state, chainparams, *winner->pblock, pindexPrev, false, false)) {
230         throw std::runtime_error(strprintf("%s: TestBlockValidity failed: %s", __func__, FormatStateMessage(state)));
231     }
232     int64_t nTime2 = GetTimeMicros();
233 
234     LogPrint(BCLog::BENCH, "CreateNewBlock() packages: %.2fms (%d packages, %d updated descendants), validity: %.2fms (total %.2fms)\n", 0.001 * (nTime1 - nTimeStart), nPackagesSelected, nDescendantsUpdated, 0.001 * (nTime2 - nTime1), 0.001 * (nTime2 - nTimeStart));

ryanofsky commented at 7:20 pm on June 9, 2017:

In commit “Skip recent transactions in CNB if fee difference is small”

It seems like this will always log information about the noRecent block even if it wasn’t the winner. Maybe move nPackagesSelected and nDescendantsUpdated variables into the state struct to keep separate copies of them and print them here. (This would also cut down on the number of arguments you need to pass to addPackageTxs.)

sdaftuar commented at 7:11 pm on August 16, 2017:

My thought was that nPackagesSelected and nDescendantsUpdated are mostly here to help parameterize the runtime, as we expect this to be slower the more packages are looked at and the more descendants that have to be walked to update scores.

I guess it can be a little confusing if someone might try to interpret this as the actual number of packages in the block, because that will be incorrect after this PR…

in src/init.cpp:500 in 73eaf01453 outdated

488@@ -489,6 +489,8 @@ std::string HelpMessage(HelpMessageMode mode)
489     strUsage += HelpMessageOpt("-blockmaxweight=<n>", strprintf(_("Set maximum BIP141 block weight (default: %d)"), DEFAULT_BLOCK_MAX_WEIGHT));
490     strUsage += HelpMessageOpt("-blockmaxsize=<n>", strprintf(_("Set maximum block size in bytes (default: %d)"), DEFAULT_BLOCK_MAX_SIZE));
491     strUsage += HelpMessageOpt("-blockmintxfee=<amt>", strprintf(_("Set lowest fee rate (in %s/kB) for transactions to be included in block creation. (default: %s)"), CURRENCY_UNIT, FormatMoney(DEFAULT_BLOCK_MIN_TX_FEE)));
492+    strUsage += HelpMessageOpt("-recenttxwindow=<n>", strprintf(_("Set window size in milliseconds for defining transactions as 'recently received' (default: %d)"), DEFAULT_RECENT_TX_WINDOW));
493+    strUsage += HelpMessageOpt("-recenttxstalerate=<n>", strprintf(_("Set stale (orphan) rate for blocks that contain 'recently received' transactions. This is the probability that block income will be lost given that a recently received transaction was included; transaction selection skips over recently received transactions (defined by -recenttxwindow) unless doing so would result in a decrease of block income exceeding this rate (default: %f)"), DEFAULT_RECENT_TX_STALE_RATE));

ryanofsky commented at 7:35 pm on June 9, 2017:

In commit “Mining: configure ‘recency’ and ‘stale rate’ from command line”

I would maybe say “if a recently received transaction were included” instead of “given that a recently received transaction was included.” It doesn’t seem like “given” is right here in the probabilistic sense.

sdaftuar commented at 8:59 pm on August 15, 2017:

I think “given” is right in the probabilistic sense here; I think I do mean P(stale block | block has recent tx).

ryanofsky commented at 3:56 pm on August 30, 2017:

Makes sense. I don’t actually remember what I meant in that comment.

in test/functional/mining.py:40 in 5d07339a06 outdated

35+                          { 'window': 50000, 'stalerate': 0.001}
36+                        ]
37+
38+        extra_args = [["-debug", "-blockmaxweight=400000", "-minrelaytxfee=0"]
39+                      for i in range(self.num_nodes)]
40+        for i in range(3):

ryanofsky commented at 7:49 pm on June 9, 2017: