#15681 Allow one extra single-ancestor transaction per package (mempool)

https://github.com/bitcoin/bitcoin/15681

Host: harding

Notes

  • A child transaction is a transaction that spends one or more of the UTXOs from another transaction, called its parent transaction. More generally, a descendant transaction spends a UTXO from a transaction that derives from one or more previous transactions, called ancestor transactions.

  • In a valid Bitcoin block chain, parent transactions must appear before child transactions. This makes sense: if a child transaction appeared first it’d be spending a UTXO that doesn’t exist and so the child would be invalid. As a corollary, all ancestor transactions must appear in the chain before any descendant.

  • These ancestor rules make mining more complicated. You can’t just add any transaction to your block proposal—if you want to add a child transaction, you must first add any of its unconfirmed ancestors. Prior to PR #7600, this meant Bitcoin Core would only consider a child transaction for inclusion in a block if all of its parents were either part of the block chain (confirmed) or already paid high-enough feerates to be included in the block proposal on their own.

  • That old mining strategy doesn’t maximize profits for miners: if a child transaction pays enough fees, the average feerate of mining both transactions can be higher than the feerate of the parent alone. In other words, the Child Pays For [its] Parent (CPFP). This applies to longer sequences of ancestors as well. CPFP is not only profit-maximizing for miners but it provides a method of fee bumping to users—users can create high-fee descendants in order to get low-feerate ancestors confirmed.

  • To implement this profit-maximizing strategy, Bitcoin Core tracks transaction packages, which is the set of transactions that needs to be added to a block for any particular transaction to be confirmed, plus the overall size and average feerate of those packages. You can see package information for your current mempool by running the following commend (warning: it’ll take a while if your mempool has lots of transactions in it): bitcoin-cli getrawmempool true

  • Calculating package information requires CPU and storing it requires memory. Although the amounts of each resource used per transaction don’t seem significant, it’s worth noting that Bitcoin Core currently defaults to keeping up to about 100 blocks worth transactions in memory (several hundred thousand transactions), any of which might need to be updated when a new descendant arrives.

  • To bound these costs, when CPFP mining (ancestor feerate mining) was implemented in PR #7600, it came with limits on the maximum number and size of related transactions that would be allowed into a package-using mempool. The current limits are:

    $ bitcoind -help-debug | grep -A3 -- -limit
      -limitancestorcount=<n>
           Do not accept transactions if number of in-mempool ancestors is <n> or
           more (default: 25)
    
      -limitancestorsize=<n>
           Do not accept transactions whose size with all in-mempool ancestors
           exceeds <n> kilobytes (default: 101)
    
      -limitdescendantcount=<n>
           Do not accept transactions if any ancestor would have <n> or more
           in-mempool descendants (default: 25)
    
      -limitdescendantsize=<n>
           Do not accept transactions if any ancestor would have more than <n>
           kilobytes of in-mempool descendants (default: 101).
    
  • Because many transactions pay more than one person (even just by returning change back to the spender), the limits above are shared between users—which creates an opportunity for an DoS attack called transaction pinning. Imagine Bob and Mallory each receive an output from a low-feerate transaction. Mallory can create a child transaction that will get close enough to the limitdescendantsize limit that no further descendants will be accepted.

  • As an attack, all transaction pinning does is prevent fee bumping—prevent anyone from accelerating the confirmation of a transaction. For many transactions, blocking fee bumping doesn’t matter much—Bitcoin users and businesses are very used to transactions going through slowly. But for time-dependent contract protocols such as Lightning Network (LN) payment channels, a fee-bumping system that’s not guaranteed to work in adversarial conditions is not safe enough to rely upon.

  • This unsuitability of CPFP for fee bumping in adversarial conditions (and replace-by-fee, RBF, for its own self-imposed limits) is discouraging to LN developers because they encounter a special problem with fee management. When an offchain LN transaction is created, the feerate necessary to ensure that transaction confirms within a reasonable number of blocks may be x; but if that transaction does actually need to be broadcast for onchain inclusion later, the feerate may then be y. If y is greater than x, the transaction may not confirm in time—making theft possible. If x is greater than y, then the users are overpaying fees. The ideal case for LN users would be that they could create their offchain transactions paying a minimal fee and then use some sort of fee-bumping technique at the time the transaction was broadcast to set an appropriate fee then.

  • The PR under discussion this week, which was also suggested by its author to the Bitcoin-Dev mailing list and discussed there, is to allow the last transaction in a package to exceed the limits by a small amount if it has only one unconfirmed ancestor (an unconfirmed parent). Given a proposed structure of LN transactions, this could make CPFP a reliable fee-bumping technique for LN.

Questions

  • Did the mailing list discussion reach a conclusive decision about this proposal? Should we wait for it to do so before investing time reviewing the PR?

  • Is it proper to be customizing mempool and relay logic for what seems to be a specific application? How do we know that this doesn’t hurt other applications? Are we even sure that LN software will use CPFP if this change is adopted? More generally, how do we go about answering these questions?

  • What can we learn about creating good tests from this part of the discussion?

  • Does this PR actually implement the same logic discussed on the mailing list? If not, how does it differ and were those differences discussed anywhere public?

Meeting Log

12:59 < sosthene> Hi everyone
13:00 < harding> Hi everyone.  John Newbery is off today, so I'll be hosting this week's meeting.  Let's get started by everyone saying hi and letting us know if you did any homework---read this week's PR, tried building it, read the notes at https://bitcoin-core-review-club.github.io/15681.html, read the mailing list discussion related to the PR, or did any other reviewing before the meeting (it's ok if
13:00 < harding> you didn't).
13:00 < michaelfolkson> Hey
13:00 < lightlike> hi
13:01 < schmidty> hola! did my reading homework but no building
13:01 < ccdle12> hi everyone
13:01 < cidercider88> didnt read it
13:01 < michaelfolkson> Same as <schmidty> for me. Only seen your notes <harding> though when you posted them here
13:02 < ccdle12> read and built it
13:02 < van> I did the readings.
13:02 < lightlike> built it, read some of the discussion
13:03 < harding> So that's a pretty good amount of people investigating it, great!
13:04 < harding> lightlike: what seemed to be the motivation for this PR?
13:04 < sosthene> Read it, didn't build
13:04 < harding> Did anyone spot anything you thought was a substantial problem?
13:04 < cidercider88> to include children txs i guess
13:05 < lightlike> harding: I would say to make it easier to get the CPFP transaction in case of a non-mutual consent Lightning network channel closing, where otherwise certain attacks would be possible.
13:05 < harding> lightlike: precisely.
13:06 < lightlike> I must say though that I didn't completely understand though why this exact change achieves it.
13:06 < harding> The certain attack is that your channel counterparty could make it impossible for you to fee bump a channel-closing transaction.
13:07 < harding> Does anyone know why this change seems to address the problem?
13:07 < michaelfolkson> But how do they make it impossible? I didn't quite get that. Why can't you just submit another child transaction with a bigger fee?
13:08 < sosthene> Isn't it particularly in the case of the counterparty trying to cheat on you by broadcasting an outdated commitment tx?
13:09 < sosthene> michaelfolkson: if I get it right since the tx has 1 output controled by each party, Mallory could do a large, low fee child tx that would prevent the honnest party to bump fees
13:09 < harding> michaelfolkson: good question.  The reason is that Bitcoin Core has limits on how many descendents a transaction can have; this prevents CPU and memory wasting attacks against a node.  Unfortunately, your counterparty can create spam transactions that meet these limits and prevent you from adding any more children to the mempool.
13:09 < harding> sosthene: that and delaying an HTLC output until it expires.
13:11 < harding> So what this PR is supposed to enable is a CPFP fee bump that can exceed the limits if it has only one unconfirmed parent in the mempool.
13:11 < michaelfolkson> I get you don't want loads of child transactions with low fees sitting in mempools but if it had a large fee Bitcoin Core should allow it to be added to the mempool?
13:12 < ccdle12> harding: ahh thats what the check for clearing the ancestors set? meaning this new fee bump is the potential +1 the limit as long as the next check passes (only on unconfirmed parent)
13:13 < harding> In an LN case, there will only be two outputs that can be spent, so Mallory can spend one output enough that it hits the limits but this rules allows Bob to still exceed the limits (by a small amount) in order to CPFP.
13:14 < harding> michaelfolkson: we actually don't mind loads of low-fee transactions in the mempool.  The problem with child transactions is that week need to keep track of and update their dependency set, which can become (I believe) a combinatorial problem.  For that reason, the number of related transactions is limited.
13:15 < michaelfolkson> Ah ok, thanks
13:16 < lightlike> harding: For this change to kick in, isn't it necessary that at least 24 descendants must exist (meaning that there will still be a bidding war)?
13:16 < harding> ccdle12: so you only get to use this special trick once per ancestor, so the worst case is that 1/3 of txes in the mempool are parents, 1/3 txes are spam, and 1/3 txes are these extras.  On a simple analysis, that doesn't seem like it should be a problem---but during a review, we'd want to check that logic to make sure it's sound.
13:17 < harding> lightlike: the limits are 25 (24 children, as you suggest) or 101,000 vbytes.  See the bitcoind -help-debug for -limitdescendantsize
13:18 < harding> lightlike: also, it's not just childred but any descendents.  So Mallory could create parent->child1->child2->childN->child24, filling up all the slots herself without giving Bob a chance.
13:19 < michaelfolkson> Parent -> Child -> Grandchild -> Great grandchild right?
13:19 < harding> I think we're getting good questions; did anyone else have any other questions, including things about the PR contents (coding style, tests, notes from building it, etc?)
13:19 < harding> michaelfolkson: yeah.  I should've said it that way.
13:19 < michaelfolkson> Not Parent -> Child 1, Parent -> Child 2, Parent -> Child 3 etc
13:21 < sosthene> regarding the test, I see Matt created a brand new test, wouldn't it make more sense to test this case in the existing mempool_packages.py test?
13:22 < harding> sosthene: hah, you did more research on it than me there; I didn't know there was a mempool_packages.py test.  Without investigating, I'd suggest that would probably be a better home for the test than a new file.  However, I don't believe new files add much overhead and the PR author (bluematt) is more familar with the project and its guidelines than I am.
13:23 < sosthene> harding: just watched the header files in the commit :)
13:24 < wumpus> I think every separate functional test does add a few seconds to spin up / spin down nodes, so if you see an oppertunity to merge it with another (without creating a confusing/non-deterministic mess) then it's good to suggest that, I think
13:25 < harding> wumpus: good info, thanks!
13:26 < harding> Any other questions?
13:26 < b10c> Hi
13:26 < michaelfolkson> So Matt's solution of allocating two small value outputs that are immediately spendable only by the two parties in the channel. How many times do you get a broadcast a spend from your output?
13:27 < harding> When changing relay logic, one thing we want to be really careful about is ensuring we don't break anyone's legitimate application unnecessarily.  Does anyone see how that could happen using this PR?
13:28 < harding> michaelfolkson: each output can only be spent once, as a consensus rule.
13:28 < michaelfolkson> Ah. So you really need to get the fee estimate right if you only get one chance?
13:29 < harding> Can anyone answer michaelfolkson's last question?  (I can; I want to give y'all a chance.)
13:30 < sosthene> michaelfolkson: since it's meant to be use in emergency situation, I think most people won't take any chance with the fees and aim very high
13:30 < sosthene> I mean, one chance should be enough
13:30 < harding> Consider: do you actually only get one chance?
13:31 < sosthene> mmmhhh if you get pinned by Mallory, I guess you only have one chance, or I am missing something?
13:31 < schmidty> RBF the CPFP?
13:32 < harding> schmidty: yes!
13:32 < michaelfolkson> ooooh
13:32 < sosthene> ok
13:32 < michaelfolkson> 25 chances again?
13:33 < sosthene> michaelfolkson: I don't know the rules wrt RBF, but I think the 25 child policy is for CPFP
13:33 < harding> It's worth noting that I don't believe that LN folks want this feature just for emergencies, they want to be able to use it in all cases of non-cooperative closes (which can be innocent "Alice went offline" kind of situations).  They just need to ensure it works in adversarial cases.  That means they might want to start with small fees and increase them as deadlines appreach.
13:34 < michaelfolkson> <sosthene> sorry yes, ignore that
13:34 < lightlike> do you think that miners might choose not to implement this change to the mempool policy in order to keep the LN small?
13:35 < sosthene> lightlike: but it's not in their interest since they will earn more fees by accepting it
13:35 < harding> lightlike: miner censorship is always possible.  The question we want to answer as reviewers is: "will miners implementing this policy earn more money than miners not implementing this policy, under reasonable conditions".  If the answer is yes, then we've done all we can do with regard to mempool policy.
13:36 < digi_james> Does the high-fee child-tx which takes advantage of the carve-out not constitute a new tx package, with new limits?
13:36 < harding> Of course, the thing that counteracts miners censorship is that they exist in what can be an perfectly anonymous market, so cartelization is very difficult up to the selfish-mining threshold.
13:38 < harding> digi_james: any children of the carve-out transaction would have two ancestors and so would not qualify for the exemption themselves.  It might be good to make sure those limits are tested in the test code, though.
13:39 < digi_james> Oh I see, so the tx_package(carve-out tx + child) have different limits than a normal tx package?
13:40 < harding> digi_james: the carve_out_tx must be the child of a parent_tx that has no unconfirmed ancestors itself.
13:41 < michaelfolkson> Matt also talks about an alternative proposal at the bottom of that mailing list post. A "likely to be RBF-ed" transaction marking. Pros and cons of that approach versus this one?
13:41 < harding> So parent_tx->carve_out_tx would be exempt from the limit (under its other conditions).  A parent_tx->carve_out_tx->grandchild_tx would not be exempt.
13:43 < harding> michaelfolkson: Rusty Russell so followed that up with a proposal based on Corallo's idea: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-June/016998.html  I replied in that thread and Russell is planning to revise his proposal.
13:46 < harding> So I thought this was an interesting part of the discussion on the PR: https://github.com/bitcoin/bitcoin/pull/15681#discussion_r270087859
13:47 < harding> It looks like the code that was originally PR'd allowed an unlimited sequence of replacements, sort of what digi_james was suggesting, but the tests didn't catch that problem.  If you were just looking at the tests, what would you be looking for to ensure that didn't happen?
13:47 < harding> Sorry: unlimited series of children*
13:47 < sosthene> I have to go unfortunately, thanks harding !
13:47 < harding> sosthene: thank you!
13:50 < harding> Hmm.  Any more questions then?  Any comments?
13:51 < lightlike> harding: i guess that a test that a large transaction >10k which would otherwise be fine, is not allowed would have caught that.
13:55 < harding> lightlike: yeah.  I was thinking, in this case, maybe what should've been done is look at the existing tests for CPFP and make sure they're extended to cover all of the new cases being added.
13:57 < harding> E.g. the previous tests assumed that if you hit 101,000 vbytes, a failure was expected.  The new rule made those not always failures depending on the ancestry of the transaction being spent, so it'd be important to make sure that if the (1) old 101,000 vbyte condition was met, (2) the new carve-out condition was met, that (3) the old test failed any addition new transactions again.
13:58 < harding> Anyway, that seems to be it for this topic.  Thank you all for coming!  Next week's topic is "#15443 Add getdescriptorinfo functional test (tests)", https://bitcoin-core-review-club.github.io/15443.html