Status: Passes unit tests
Consider parent transactions in the "cost" of child transactions until confirmed, and confirm them together
This is the part of #1240 that @gavinandresen left out of #1590 since he felt it belonged in a separate commit/pullreq.
Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/27b24244c4d1f97690d5908e3412ac5306920281 for binaries and test log.
Gavin, any thoughts on this?
@mikehearn : needs unit tests, in my humble opinion. It is a very good candidate for "needs 100% code coverage from tests", because transaction selection is such a key piece of the Bitcoin infrastructure.
Also needs thorough code review, with an eye towards "Could I construct a series of transactions that made the selection algorithm take O(N^2) time ?"
@gavinandresen What kind of unit tests would you like for this? I already dealt with the O(N^2) problem a while back on Eligius, though of course more reviews are always welcome.
My suggestion would be start with a bunch of "random" mempools and them making sure that the selections it makes are valid (no mistaken dependencies) and actually get the most fees possible (e.g. by externally precomputing the correct answers). I'd also include cases designed to trigger complexity attacks (mempool with a 2 groups of 100 long chains or whatever).
After that I'd run lcov with the test and look and make sure every conceivably reachable branch (e.g. all except the invisible boost added heap allocation failure tests) is hit by the tests. If not, add tests that trigger them.
After that the code should be intentionally broken (e.g. by randomly removing some statements and/or turning some if() to if(!())) and make sure the tests fail. I volunteer to do this kind of testing (plus some basic smoke tests) once regular unit tests for this are written.
Thanks @gmaxwell , those are exactly the types of tests I think this needs!
Update: It seems since rebasing this, new performance problems have cropped up. :(
Update: False alarm, I debugged the performance problem and it was a result of a poorly thought-out merge of this with #1648 (which elevated priority of transactions that benefit the miner directly). This seems to still perform well without that change (or with it done once).
Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/56c7ea61d70d4a6699f1a53b9d03eb803a9c58c7 for binaries and test log.
Fixed a bug triggered by today's onslaught of !IsFinal transactions...
Rebase needed.
Although I think this needs a re-think/rewrite:
When we have a memory-limited mempool (needed for anti-DoS), we'll run into a chicken-and-egg problem: parent transaction may be evicted from mempool, child will get stuck (and eventually evicted) from the orphan pool. Seems to me what is needed is a new protocol message that is "here is a bundle of dependent transactions, with children that pay for their parents."
Rebased. I agree it isn't perfect, but this is 1) better than nothing, and 2) well-tested. If anyone wants to put the effort into a rewrite, I'd be glad to defer and give it testing.. but I think everyone's busy enough already.
Thank you for your work on this, it would be good to see it in a 0.9 release, am curious if tests are completed.
I'm not sure if I'm going to have time to do tests before 0.9 - hopefully someone else can help out with that. :(
If the tests for this need any funding support from some bounty fund and if there is not support or priority, it's possible the tests may be able to be bountyfied (ok, not a word) as part of something I'm working on, it's probably 60 days out though before any funds would be available.
#3753 also just had merge conflicts on testing (failed merge).
Rebased, but the changes were significant enough that IMO this needs re-review and re-testing :(
Automatic sanity-testing: FAILED MERGE, see http://jenkins.bluematt.me/pull-tester/p1647_200f8abb943e5acd3bf599b4bfa8e9beccd53d1f/ for test log.
This pull does not merge cleanly onto current master This test script verifies pulls every time they are updated. It, however, dies sometimes and fails to test properly. If you are waiting on a test, please check timestamps to verify that the test.log is moving at http://jenkins.bluematt.me/pull-tester/current/ Contact BlueMatt on freenode if something looks broken.
How much mining actually occurs using miner.cpp? Is it basically example code at this point? Since CPFP makes economic sense for miners, wouldn't they have implemented it already? I admit to cluelessness about the mining landscape.
Well "the internal miner" is example code. It's slow and useless.
However miner.cppalso contains code for transaction selection from the mempool, which is used for getblocktemplate, which is used by many miners.
Labeling this for 0.11. This is the oldest pull request open, let's finally get it in by then.
Would love to see this get in. Have a situation right now where a new user received 0.01btc tx with no fee and then spent their entire balance, 17btc, which is stuck. It would be a real improvement for user experience if wallet software could just include a fee to cover unconfirmed input tx in addition to itself instead of trying to explain to users why they can't spend those funds yet.
Needs tests, as suggested by gmaxwell. A regression test making sure that this would actually fix the situation described by @voisine would be excellent (although non-trivial-- do you assume that the 0.01btc tx with no fee got relayed and is still in memory pools, or not?)
And needs a good review from somebody who is good at spotting potential DoS weaknesses (like Sergio).
Yes, thanks to those who have worked on this so far. This being the oldest open pull request, and having merits for inclusion in 0.11, it needs and deserves both a thoughtful review and merge.
ACK - light test at branch's current tip
291 | const CTransaction& tx = mi->second.GetTx(); 292 | + 293 | + const uint256& hash = tx.GetHash(); 294 | + CTxInfo& txinfo = mapInfoById[hash]; 295 | + txinfo.hash = hash; 296 | + txinfo.pmapInfoById = &mapInfoById;
This cyclic dependency is pretty ugly. Can't you just pass the mapInfoById to the methods in txindo that need it?
That's basically everything... :/
It's easier to not put the logic in the data structure, I think. The fact that you need a pointer from the low-level data structure to the container is just a symptom of that.
Has anyone done benchmarks on the impact on block creation time?
436 | + 437 | + ptxinfo->fInvalid = true; 438 | + if (!ptxinfo->setDependents.empty()) 439 | { 440 | - if (!porphan->setDependsOn.empty()) 441 | + fResort = true;
Aren't this !empty check and flag to resort redundant given the foreach loop below?
Probably better to just set fResort here and not in the foreach... (done)
429 | + BOOST_FOREACH(CTxInfo* ptxinfo, vAdded) 430 | { 431 | - BOOST_FOREACH(COrphan* porphan, mapDependers[hash]) 432 | + pblock->vtx.push_back(*ptxinfo->ptx); 433 | + pblocktemplate->vTxFees.push_back(ptxinfo->nTxFee); 434 | + pblocktemplate->vTxSigOps.push_back(ptxinfo->nTxSigOps);
I think that ptxinfo->nTxSigOps is just that transaction's GetP2SHSigOpCount and doesn't include its GetLegacySigOpCount.
Good catch, fixed.
I've done a code review on this and it looks good to me. I've also done some performance testing in manufactured RPC tests as well as under more typical load. It can cause CreateNewBlock to take multiples as long if there are chains of transactions in the mempool, so I do think it would be useful to test deliberately extreme chains as mentioned above. Under typical mempool activity though it seems to be about a 40% hit, making CreateNewBlock take on average 200ms instead of 140ms. Before and after this change the maximum time on a typical mempool is about 1 second.
EDIT: see later comment, has some issues.
@luke-jr Feel free to take a look at this, https://github.com/morcos/bitcoin/commits/CPFP. I'd rebased and then added 2 commits to do some timing. Its not really something to include as it doesn't test anything, but its just what I was using to stress the code. I'm not quite sure why it takes so long, but I didn't look into. See the commit text for the most recent commit.
361 | + { 362 | + // We don't know where the input is 363 | + // In this case, it's impossible to include this transaction in a block, so mark it invalid and move on 364 | + txinfo.fInvalid = true; 365 | + LogPrintf("priority %s invalid input %s\n", txinfo.hash.ToString().substr(0,10).c_str(), txin.prevout.hash.ToString().substr(0,10).c_str()); 366 | + goto nexttxn;
What about replacing this part
txinfo.fInvalid = true;
goto nexttxn;
}
nTotalIn += nValueIn;
}
nTxFee = nTotalIn - tx.GetValueOut();
mempool.ApplyDeltas(hash, dPriority, nTotalIn);
vecPriority.push_back(&txinfo);
nexttxn: (void)1;
with the following?
txinfo.fInvalid = true;
}
if (!txinfo.fInvalid)
nTotalIn += nValueIn;
}
if (!txinfo.fInvalid) {
nTxFee = nTotalIn - tx.GetValueOut();
mempool.ApplyDeltas(hash, dPriority, nTotalIn);
vecPriority.push_back(&txinfo);
}
Or just have a separate function:
if (NewFunction(...)) {
nTotalIn += nValueIn;
nTxFee = nTotalIn - tx.GetValueOut();
mempool.ApplyDeltas(hash, dPriority, nTotalIn);
vecPriority.push_back(&txinfo);
}
Does it work?
I think I missed a few things on my first review of this. It seems like if B and C are both children of A, and D depends on both B and C, then the effectiveSize() of D will double count the size of A?
Also, it doesn't look like the fees of A, B, or C are counted, only the fees of the final child (D in this case).
Or am I missing something now...
I leave this pull request open in the hope that it's current status of "98% there" will get the final way there. @luke-jr has faithfully updated it and addressed feedback over time, and consensus is that it's merge worthy.
It seems like it just needs a reviewer or two to expend a day or two of focused analysis and testing.
I absolutely gree on the concept of CPFP, but I believe there are various hard to analyse edge cases with this approach.
With the work that @sdaftuar is doing for the mempool refactor (particular the dependency tracking and limiting), we'll have a framework that is very close to actually having a mempool indexed by dependency-inclusive feerates, resulting a much cleaner way to implement actual CPFP mining, by simply putting dependency packages one by one in a block, following that sort order.
Its actually a fair amount of code that will still need to be written to do CPFP even after #6654, but I agree that it'll provide the right framework for implementing it. I think the approach of starting from the dependent tracking framework and adding ancestor tracking is likely to get us to functional CPFP quicker than starting from this pull.
I agree the long-term implementation is likely to be different, but given the extreme maturity of this code (especially as opposed to the immaturity of #6654 and similar proposals), I do think it would be best to merge it now/soon, with the understanding that it may be replaced by an improved implementation later. Don't let the perfect be the enemy of the good etc.
I think I missed a few things on my first review of this. It seems like if B and C are both children of A, and D depends on both B and C, then the effectiveSize() of D will double count the size of A?
Yes, probably. But it's still an improvement over not considering the dependency at all.
Also, it doesn't look like the fees of A, B, or C are counted, only the fees of the final child (D in this case).
IIRC this is intentional.
Closing this for now. Should be reopened (or implemented otherwise) after the mempool refactor work.
After 2 or 3 failed attempts to rewrite/port CPFP to 0.12, I am abandoning CPFP for the time being. Nobody seems to use it, and it's too complex.
Pretty sure the older versions also have a bug that they don't update grandchildren priority/feerate when their grandparents get mined. (Not a big deal.)
@luke-jr Bitcoin Wallet users use it quite a bit. Current problem is only a few miners have implemented it.
Hmm, good to know. It's not going to make Knots 0.12.0 though - maybe I'll reconsider it later.
Sorry if I'm being thick, I can see how this patch allows the recipient of a transaction to effectively pay the fee, but how often is this actually needed?
@rebroad Especially in times like this week, with the network being very unreliable, CPFP is used a lot. Based on my logs, I'd say several thousand times a day.
Just wanted to add that we use CPFP in breadwallet as well, when spending unconfirmed inputs that don't come from the wallet's own change outputs. It's needed to get transactions unstuck if a user tries to spend their entire wallet balance including recent unconfirmed low/no-fee inputs.
@voisine I assume in this case, the CPFP transaction is the same as the (presumably big) transaction that empties the wallet? Or are you somehow splitting it up into txns that act as CPFP and a transaction that empties the wallet?
this is if the user tries to spend more funds in a single tx than they have confirmed utxos that can satisfy, typically when emptying the wallet shortly after a receive