CreateNewBlock: Child-pays-for-parent / Add transaction fee later #1647
Conversation
|
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 |
|
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. |
|
@dgenr8 It's supposed to be example code, but unfortunately a lot of miners still end up using it as-is today. :( |
|
Well "the internal miner" is example code. It's slow and useless. However |
|
Labeling this for 0.11. This is the oldest pull request open, let's finally get it in by then. |
…ransactions until confirmed, and confirm them together
|
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. |
|
@morcos If you want to push those RPC tests as a branch somewhere, I can include them when I rebase this. |
|
@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. |
There was a problem hiding this comment.
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);
}
https://xkcd.com/292/
There was a problem hiding this comment.
Or just have a separate function:
if (NewFunction(...)) {
nTotalIn += nValueIn;
nTxFee = nTotalIn - tx.GetValueOut();
mempool.ApplyDeltas(hash, dPriority, nTotalIn);
vecPriority.push_back(&txinfo);
}
|
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. |
Yes, probably. But it's still an improvement over not considering the dependency at all.
IIRC this is intentional. |
|
Closing this for now. Should be reopened (or implemented otherwise) after the mempool refactor work. |
|
Maybe @laanwj tag it as blocked and keep it open? |
|
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? |
|
See #7600 for another implementation.
|
|
@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 |
This reverts commit d3829e5. Reverting and postponing the fix till later. Probably should write a DIP and explore different options first.
16 participants
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.