Mining: Select transactions using feerate-with-ancestors #7600

sdaftuar · 2016-02-25T20:48:01Z

This implements "Child-pays-for-parent" transaction selection in CreateNewBlock, where we sort the mempool using (modified) feerate with ancestors and consider transactions in that order during block creation. As transactions are selected, a separate map is used to track the new feerate-with-ancestors value to use for in-mempool descendants that haven't yet been selected.

This is almost strictly better (ie, results in higher-fee blocks) than the existing mining algorithm, with some small variance due to edge cases around which transactions might get selected as the new block's size approaches the maximum allowed. Moreover the performance impact on CreateNewBlock is minimal -- I observed that the total run time of the function actually slightly improved, apparently due to TestBlockValidity being on average slightly faster (a somewhat surprising result).

The actual fee improvements observed were fairly low in the time period I looked at (October 2015), roughly a 1% fee improvement overall. I think that is driven first and foremost by blocks not really being full for a large bulk of the time period, so on a large number of data points the results were identical. Additionally, my guess is that user behavior may not have adapted to this type of transaction selection being widely deployed, and so in the future perhaps we might expect to see larger differences. I did note a handful of instances where the implementation here notably outperformed the existing algorithm, in some instances more than 20% better, but those were the exception and not the rule.

For comparison, I found no examples where the old algorithm produced a block with 0.5% or more in fees than the new algorithm (and few examples where the old algorithm's block had more fees at all, around 1% of samples).

I've labeled this PR as a work-in-progress for now, as it builds off two other open PR's (#7594 and #7598). Once those are reviewed and merged, I'll rebase this and remove the WIP label. I opened this now to help motivate the work in those two PRs.

One open question I have is whether it's worth keeping around the old transaction selection algorithm. The refactor in #7598 that this builds on makes it easy to leave it around, and I don't think it would be hard to add command line arguments for policy configuration that would enable using the older algorithm. But I don't know if that's of interest to anyone, so for now I figure we can let people mull it over and decide what to do in a future PR.

A related question to that is whether to get rid of the existing mempool "score" index. The ancestor tracking pull adds a new ancestor feerate index without removing the old feerate index, but if we decide to get rid of the mining algorithm that uses that index, then perhaps we could also eliminate this mempool index as well.

To do:

Review/merge Mempool: Add tracking of ancestor packages #7594
Review/merge Refactor CreateNewBlock to be a method of the BlockAssembler class #7598

dgenr8 · 2016-03-03T20:19:46Z

Does this algorithm claim to select the optimum descendant subtree for a given independent transaction?

sdaftuar · 2016-03-03T21:04:47Z

This algorithm is by no means guaranteed to produce maximum fee blocks for a given mempool, if that's what you're trying to ask.

The algorithm this PR is trying to implement is straightforward:

Look at highest ancestor-feerate tx in mempool:
 - Add tx's package (tx + unconfirmed ancestors) to block
 - Remove tx's package from the mempool and re-sort (so that descendants of tx and its now in-block ancestors are treated as confirmed, and remaining in-mempool descendant's ancestor feerate is updated).

The implementation is complicated because we can't actually remove things from the mempool. To deal with that, I added a new multi_index that CreateNewBlock uses to keep track of the effective ancestor feerate/size/sigops for transactions whose in-mempool ancestors have been selected for inclusion in the block. (The only other complication is that a package might not be includable, say because it's too big or has too many sigops, but that's easy to handle.)

Anyway, getting back to the algorithm -- I think this algorithm is superior to the existing one (which iterates based on each tx's individual feerate, not looking at ancestors) for optimizing block fees, and it has the property that (what I expect to be) typical uses of CPFP should generally be captured -- namely those situations where a single child is paying a large fee for its parents.

However if there are multiple medium fee children that are chained below some low-fee parent, then the algorithm might easily fill the block without those transactions because they may not be considered until the block is full. For now though I suspect this algorithm is adequate for the current usage patterns, and perhaps we can come up with ways to monitor what's in the mempool to look for patterns of usage that would motivate further improvements to CreateNewBlock.

sipa · 2016-03-04T21:57:04Z

Would it be possible to have a CTxMempool::check that accurately checks the ancestor-based statistics, rather than just lower bounding them to 1 level up?

sdaftuar · 2016-03-17T15:11:41Z

Updated now that #7594 has been merged.

btcdrak · 2016-03-17T17:28:42Z

Is this still WIP?

sdaftuar · 2016-03-17T17:32:14Z

@btcdrak: I was thinking I'd leave this marked as WIP until the other dependent PR (#7598) is merged, since I'll have to rebase this on top of whatever the final version of the refactor ends up being.

I should add -- if you want to start reviewing now, please do!

btcdrak · 2016-03-17T17:43:06Z

@sdaftuar Github tasklists are maybe better for this kind of thing, and they show up as tasks even on ticket lists. https://github.com/blog/1375-task-lists-in-gfm-issues-pulls-comments

sdaftuar · 2016-05-18T18:39:14Z

Rebased on the latest #7598

sdaftuar · 2016-06-09T14:37:57Z

Rebased again and built off the latest version of #7598.

seweso · 2016-06-10T08:19:08Z

Very nice!

Additionally, my guess is that user behavior may not have adapted to this type of transaction selection being widely deployed, and so in the future perhaps we might expect to see larger differences.

Yes you would definitely expect bigger difference as this becomes available. As entities will be able to underpay transactions without risking getting dropped from the mempool. (for entities who continuously create transactions)

One of the dangers of the blocksize limit is that fees would go up, but have almost no reason/force to get it down. Things like this and RBF could really help with that. 👍

Is this algorithm also used to determine which transactions to drop?

sdaftuar · 2016-06-11T15:43:14Z

Is this algorithm also used to determine which transactions to drop?

@seweso The algorithm for eviction of transactions from the mempool is unchanged. In a sense, the transaction eviction algorithm for the mempool is already assuming we're doing something like what this PR implements for transaction selection, in that a transaction is less likely to be evicted from the mempool if its feerate with descendants is high. But more fundamentally, mempool eviction is just a different problem than transaction selection: when selecting transactions for a block, a candidate transaction's ancestors must be included (so it's natural to sort by feerate-with-ancestors), but when considering a transaction for mempool eviction, a candidate transaction's descendants must also be removed as well (so we use max(feerate, feerate with descendants) as our sort order for removal).

maflcko · 2016-06-13T09:52:02Z

Needs rebase

sdaftuar · 2016-06-13T14:08:30Z

Rebased after #7598 has been merged. This PR is ready for review!

maflcko · 2016-06-14T11:36:19Z

Concept ACK

JeremyRubin · 2016-06-14T17:04:35Z

src/miner.cpp

+            iit++;
+        }
+    }
+}


~~Nit: may as well have ++iit in the for loop because it always occurs.~~

for (CTxMemPool::setEntries::iterator iit = testSet.begin(); iit != testSet.end(); ++iit) { // Only test txs not already in the block if (inBlock.count(*iit)) testSet.erase(iit); }

Edit: ignore, erasing an iterator invalidates iit.

JeremyRubin · 2016-06-14T18:24:56Z

utAck

mrbandrews · 2016-06-15T14:46:29Z

src/miner.cpp

+        assert (potentialBlockSigOps < MAX_BLOCK_SIGOPS);
+    }
+    return true;
+}


Nit: since block size and sigops have already been checked, it shouldn't be necessary to re-check and assert here.

I guess I left these asserts in to make the logic in addPackageTxs easier to review, in that if you weren't sure whether the mapModifiedTx calculations were correct, this assertion ensures that it doesn't underestimate. But I suppose this would be caught in TestBlockValidity anyway, so I'll remove.

sdaftuar · 2016-06-15T16:31:40Z

Pushed commits addressing @mrbandrews comments.

re: @JeremyRubin's nits, I'm leaving TestPackage alone, I think it's pretty readable in its current form, and the >= shouldn't matter for anything and is consistent with addScoreTx's behavior.

I'll do another round of testing locally, similar to what I did before when I opened the pull, with the current version of the code and report back.

sdaftuar · 2016-06-15T21:15:37Z

I re-tested my code by simulating on data from 2016-02-23 -to 2016-02-29, comparing the default mining code in master against the mining code introduced here, by calling CreateNewBlock every 100 transactions.

I looked at the fees produced in the last call to CNB before each block found by the network, and the code in this PR produced higher fee blocks in each instance (894 data points).

I was also benchmarking the runtime of CNB over all invocations, and this code was negligibly faster than the old code (summing over all invocations).

gmaxwell · 2016-06-15T21:28:52Z

ACK.

Beyond review, I tested this on several mining nodes for about a week (in addition to prior testing I did months back); I also took nodes running this and a tight getblocktemplate loop through a number of reorg tests with debugging turned up. Finally, rather than using sdaftuar record and replay framework, I scraped all the recent transactions out of recent blocks, reorged the chain back and put all the still-valid transactions into the mempool and confirmed it gave a valid gbt result with higher total fees than the before the patch, I tried this at a dozen different points.

mrbandrews · 2016-06-16T15:37:30Z

ACK.
Code review ACK and in my testing, though not nearly as comprehensive as sdaftuar and gmaxwell's testing, the new code yields higher fees by 1% to 15%.

sipa · 2016-06-16T15:50:25Z

src/miner.cpp

+{
+    // Start by adding all descendants of previously added txs to mapModifiedTx
+    // and modifiying them for their already included ancestors
+    UpdatePackagesForAdded(inBlock);


If I understand it correctly, this means you can't call addPackageTxs() twice (or have another add*Tx() that also calls UpdatePackagesForAdded(inBlock);. That could be solved by keeping a set of things in inBlock that have already been counted for package updates, but I guess it's sufficient to just document that this must not be called twice.

Calling it twice doesn't really make sense, as addPackageTx's would fill up your block the first time. I think if you wanted to implement custom transaction selection, you'd implement it in a function that is called before you'd call addPackageTx's to fill the rest of the block (like how priority tx's are done).

I can add a comment though to make this clearer.

Oh I forgot to mention: this function no longer changes global state, after I addressed @mrbandrews comments in a later commit and moved mapModifiedTx to be a local variable in addPackageTxs. So this can be reused, though it's pretty tied to the package selection.

ACK, fixed by the later commit.

sipa · 2016-06-16T16:34:20Z

ACK f3c6551 (with tree 66fb31f4aaaf3c49ef03c93b3b8155b531359e05).

Update: ACK b428fb2656b3cdf3021faf508eb78e6831e5a276 (with tree 2e6a8674a4e7179aea0041931d68076a442d0132).

Can you squash the fixups?

Includes changes by Pieter Wuille

sdaftuar · 2016-06-16T16:38:48Z

Thanks, squashed.

sipa · 2016-06-16T16:41:08Z

ReACK 29fac19 (tree 2e6a8674a4e7179aea0041931d68076a442d0132).

29fac19 Add unit tests for ancestor feerate mining (Suhas Daftuar) c82a4e9 Use ancestor-feerate based transaction selection for mining (Suhas Daftuar)

…cestors 29fac19 Add unit tests for ancestor feerate mining (Suhas Daftuar) c82a4e9 Use ancestor-feerate based transaction selection for mining (Suhas Daftuar)

…priority removal f5b2e54 Fix comparisons for integer expressions of different signedness (random-zebra) 784d8b4 [Doc] Add Mempool priority changes to release notes (random-zebra) 6163d4b Remove -blockminsize option (Suhas Daftuar) b304fb9 Allow setting minrelaytxfee to 0 (Alex Morcos) 006136e Make boost::multi_index comparators const (Suhas Daftuar) 5858fb5 [Tests] Remove priority check for sapling txes (random-zebra) e267d02 [Cleanup] Remove coin age priority completely (random-zebra) 4298938 [RPC] Remove priorityDelta from prioritisetransaction (random-zebra) cd1535a [rpc] Remove priority information from mempool RPC calls (Alex Morcos) 3b4d207 [Refactor][RPC] entryToJSON/EntryDescriptionString out of mempoolToJSON (random-zebra) 142415e Fix edge case with stale fee estimates (Alex Morcos) 9f47b0f Add clarifying comments to fee estimation (Alex Morcos) 57b7922 Add extra logging to processBlock in fee estimation. (Alex Morcos) 59486ef Add IsCurrentForFeeEstimatation (Alex Morcos) d23ebfd Pass pointers to existing CTxMemPoolEntries to fee estimation (Alex Morcos) be5982e Always update fee estimates on new blocks. (Alex Morcos) aa97809 rename bool to validFeeEstimate (Alex Morcos) 82aba64 Remove member variable hadNoDependencies from CTxMemPoolEntry (random-zebra) c3758e1 Don't track transactions at all during IBD. (Alex Morcos) 9ca59ae [rpc] rawtx: Prepare fLimitFree to make it an option (MarcoFalke) f682e75 [wallet] Set fLimitFree = true (MarcoFalke) 0221d5a [QA] Fix random failure in wallet_abandonconflict.py (random-zebra) 33c9aa1 [Trivial] Pass hash by const ref to CBlockPolicyEstimator::removeTx (random-zebra) 7be33e0 Remove extraneous LogPrint from fee estimation (Alex Morcos) 7b6e8a3 [test] Remove priority from tests (Alex Morcos) c2ecf27 No longer allow "free" transactions (Alex Morcos) 5c577c5 [Cleanup] Remove feature_nulldummy.py unused functional test (random-zebra) 3097847 [cleanup] Remove estimatePriority and estimateSmartPriority (random-zebra) f283e8a [debug] Change -printpriority option (Alex Morcos) dcddcaf [Cleanup] Remove unused (always false) fAllowFree arg in GetMinRelayFee (random-zebra) 03d2ee9 [mining] Remove -blockprioritysize. (Alex Morcos) cfaeb97 [BUG] Don't add priority txes (random-zebra) 01882da Add unit tests for ancestor feerate mining (Suhas Daftuar) 49b1a9b [Policy] Limit total SHIELD size and check spork 20 in addPackageTxs (random-zebra) cc473ed Use ancestor-feerate based transaction selection for mining (random-zebra) dfaf4e7 [Wallet] Remove sendfree (random-zebra) Pull request description: This PR implements CPFP transaction selection mechanism, which is the simplest "fee bumping technique" (we might want to consider implementing RBF too later on). The algorithm in `CreateNewBlock` now selects transactions based on their feerate, inclusive of unconfirmed ancestor transactions. This means that a low-fee transaction can become more likely to be selected if a high-fee transaction that spends its outputs is relayed: the fee burned in the "child" transaction, actually pays for the parent tx too (hence the name). This PR also removes completely the (already deprecated) notion of coinage-based priority and "free transactions area". Changes backported / adapted from: - bitcoin#7600 [Suhas Daftuar] - bitcoin#8287 [MarcoFalke] - bitcoin#8295 [Suhas Daftuar] - bitcoin#9138 [Alex Morcos] - bitcoin#9602 [Alex Morcos] - bitcoin#11847 [Suhas Daftuar] ACKs for top commit: Fuzzbawls: utACK f5b2e54 furszy: re-ACK f5b2e54 after rebase and last commit. Tree-SHA512: aef64628008699c81735660fcbe51789b7dc9d2a670d0c695399a2821f01f5d72e46d72b5f57d7b28c0e0028b60b4d6294ee101b8038ea46d237c7b8729a79da

jonasschnelli added the Mining label Feb 25, 2016

sipa mentioned this pull request Mar 1, 2016

CreateNewBlock: Child-pays-for-parent / Add transaction fee later #1647

Closed

sdaftuar mentioned this pull request Mar 5, 2016

Mempool: Add tracking of ancestor packages #7594

Merged

sdaftuar force-pushed the ancestor-mining branch from e2865a2 to ef35d94 Compare March 17, 2016 15:11

sdaftuar force-pushed the ancestor-mining branch from ef35d94 to 40a711a Compare May 18, 2016 18:38

sdaftuar changed the title ~~[WIP] Mining: Select transactions using feerate-with-ancestors~~ Mining: Select transactions using feerate-with-ancestors May 18, 2016

sdaftuar force-pushed the ancestor-mining branch 2 times, most recently from fc8b425 to 48e0620 Compare June 9, 2016 14:37

sdaftuar force-pushed the ancestor-mining branch from 48e0620 to 157d24e Compare June 13, 2016 14:07

JeremyRubin reviewed Jun 14, 2016
View reviewed changes

mrbandrews reviewed Jun 15, 2016
View reviewed changes

sipa reviewed Jun 16, 2016
View reviewed changes

sdaftuar added 2 commits June 16, 2016 12:35

Use ancestor-feerate based transaction selection for mining

c82a4e9

Includes changes by Pieter Wuille

Add unit tests for ancestor feerate mining

29fac19

sdaftuar force-pushed the ancestor-mining branch from b428fb2 to 29fac19 Compare June 16, 2016 16:38

sipa merged commit 29fac19 into bitcoin:master Jun 16, 2016

sipa mentioned this pull request Jun 16, 2016

Segregated witness #7910

Closed

7 tasks

jnewbery mentioned this pull request Dec 3, 2019

Topics: November update and new topics bitcoinops/bitcoinops.github.io#286

Merged

random-zebra mentioned this pull request May 10, 2021

[Policy] Child-pays-for-parent Implementation + CoinAge priority removal PIVX-Project/PIVX#2378

Merged

jarolrod mentioned this pull request Jul 27, 2021

Blocks are not including transactions with a fee below 1 Satoshi per byte #22540

Closed

bitcoin locked as resolved and limited conversation to collaborators Sep 8, 2021

Mining: Select transactions using feerate-with-ancestors #7600

Mining: Select transactions using feerate-with-ancestors #7600

Uh oh!

Conversation

sdaftuar commented Feb 25, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

dgenr8 commented Mar 3, 2016

Uh oh!

sdaftuar commented Mar 3, 2016

Uh oh!

sipa commented Mar 4, 2016

Uh oh!

sdaftuar commented Mar 17, 2016

Uh oh!

btcdrak commented Mar 17, 2016

Uh oh!

sdaftuar commented Mar 17, 2016

Uh oh!

btcdrak commented Mar 17, 2016

Uh oh!

sdaftuar commented May 18, 2016

Uh oh!

sdaftuar commented Jun 9, 2016

Uh oh!

seweso commented Jun 10, 2016

Uh oh!

sdaftuar commented Jun 11, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

maflcko commented Jun 13, 2016

Uh oh!

sdaftuar commented Jun 13, 2016

Uh oh!

maflcko commented Jun 14, 2016

Uh oh!

JeremyRubin Jun 14, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

JeremyRubin commented Jun 14, 2016

Uh oh!

mrbandrews Jun 15, 2016

Choose a reason for hiding this comment

Uh oh!

sdaftuar Jun 15, 2016

Choose a reason for hiding this comment

Uh oh!

sdaftuar commented Jun 15, 2016

Uh oh!

sdaftuar commented Jun 15, 2016

Uh oh!

gmaxwell commented Jun 15, 2016

Uh oh!

mrbandrews commented Jun 16, 2016

Uh oh!

sipa Jun 16, 2016

Choose a reason for hiding this comment

Uh oh!

sdaftuar Jun 16, 2016

Choose a reason for hiding this comment

Uh oh!

sdaftuar Jun 16, 2016

Choose a reason for hiding this comment

Uh oh!

sipa Jun 16, 2016

Choose a reason for hiding this comment

Uh oh!

sipa commented Jun 16, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sdaftuar commented Jun 16, 2016

Uh oh!

sipa commented Jun 16, 2016

Uh oh!

Uh oh!

sdaftuar commented Feb 25, 2016 •

edited

Loading

sdaftuar commented Jun 11, 2016 •

edited

Loading

JeremyRubin Jun 14, 2016 •

edited

Loading

sipa commented Jun 16, 2016 •

edited

Loading