Episode 19: Mempools, Child Pays for Parent, and Package Relay

Aaron van Wirdum Live from Utrecht, this is the Van Wirdum Sjorsnado.

Sjors Provoost Hello.

Aaron van Wirdum Hey, Sjors.

Sjors Provoost What's up?

Aaron van Wirdum Happy all-time high.

Sjors Provoost Yeah, again. Oh, we talked about the market cap high.

Aaron van Wirdum Yeah, well, that one you weren't celebrating because it didn't affect you individually enough. So I guess this time was party. Party time for Sjors.

Sjors Provoost But again, we don't know what the dollar did in the meantime. I mean, can I still buy a bagel for less than $15 in San Francisco?

Aaron van Wirdum Yeah, it's definitely not an all-time high in purchasing power, is it?

Sjors Provoost No.

Aaron van Wirdum So we skipped a week. Last week was Halloween.

Sjors Provoost Yes.

Aaron van Wirdum Apparently.

Sjors Provoost And Thanksgiving.

Aaron van Wirdum Oh, that's what… that's what was up. Yeah, it was Thanksgiving. When is Halloween? That was a month ago.

Sjors Provoost I think it was earlier, yeah.

Aaron van Wirdum Yeah, never mind. All these American holidays. I have no idea. Last week was Halloween.

Sjors Provoost We don't have holidays. Holidays are socialist.

Aaron van Wirdum So we just have a boring life over here in the rain. Sjors, do you know what Brink is?

Sjors Provoost Yes. No, but I've heard of it. Yeah. It's a new initiative by John Newbery, but you're going to tell me all about it.

Aaron van Wirdum No, that covers it. I'll tell you one extra detail. One of the things they're doing, well, they're doing two things. So they're issuing grants to developers. Or two projects that are working on Bitcoin stuff, open source projects. And the other thing which is pretty unique well… what… is which is entirely unique is they are… they have a fellowship program. So aspiring Bitcoin developers, Bitcoin Core developers, perhaps Lightning developers, whatever it is, they can join the fellowship at Brink and they'll enjoy a year of training by John Newbery.

Sjors Provoost So that's like the Chaincode Labs summer, but all year.

Aaron van Wirdum All year.

Sjors Provoost In the rain, in London.

Aaron van Wirdum Yes, in London. That's the downside, I guess, compared to the Chaincode Labs one. Well, the Chaincode, that's in New York. It's not much better. It's not like it's LA.

Sjors Provoost I would pick London over New York in terms of the weather because it's never really cold in London. It's never really hot in London. The sun doesn't shine so it's comfortable.

Aaron van Wirdum Fair enough. Well so this week they announced their first fellow which is Gloria Zhao.

Sjors Provoost Congratulations.

Aaron van Wirdum Congratulations Gloria. She's gonna work on something pretty specific which is called package relay.

Sjors Provoost Oh no.

Aaron van Wirdum Why do you say oh no?

Sjors Provoost Because it's a can of worms.

Aaron van Wirdum Yeah, you mentioned that before. Let's explain what it is and then after our explanation, you can get into why it's a can of worms. Does that sound good?

Sjors Provoost That sounds excellent.

Aaron van Wirdum Okay. So it is an upgrade, a proposed upgrade to basically to Bitcoin's mempool policy.

Sjors Provoost And peer-to-peer network.

Aaron van Wirdum Yes. Yeah, but it all comes down to improving how mempools work, I guess, right? And the relay policy is in support of that. But what's a mempool? I was just going to ask you, Sjors, what's a mempool?

Sjors Provoost I thought you were going to answer that.

Aaron van Wirdum I can answer it.

Sjors Provoost So the mempool is basically a bunch of memory on your node that is dedicated to keeping track of transactions that are not yet in a block.

Aaron van Wirdum Yeah, so transactions are transmitted over Bitcoin's peer-to-peer network before they are included in a block. Just whenever you send a transaction, it's forwarded from node to node, from peer to peer. And all of these nodes keep a collection of these transactions. And if you're a miner, you use this collection of transactions to form a block. That's right. So how big is a mempool?

Sjors Provoost Well, that's up to you, up to the node runner. You can allocate as little or as much memory as you want to. Keeping track of those transactions, but by default it is 300 megabytes,

Aaron van Wirdum In Bitcoin Core.

Sjors Provoost It's 300 megabytes or 300,000 kilobytes if you're nitpicky.

Aaron van Wirdum Yeah so apparently that's actually not 300 megabytes of transactions it's much less than that, I learned while writing this article about Brink's first fellowship.

Sjors Provoost Oh, that could very well be true. Yeah, there's a lot of database overhead in there.

Aaron van Wirdum Yeah, a lot, apparently, because Gloria told me it's like 75… 75 megabytes of transactions for a 300 megabyte mempool. That seems like a big difference to me. So that's like 100,000 to 140,000 transactions.

Sjors Provoost Yeah, it wouldn't surprise me. For one thing, a transaction, I think a raw transaction might be 140 bytes or something or 200 bytes. And then the hash of a transaction is… Is it 64 bytes or 32 bytes?

Aaron van Wirdum You're looking at me as if I know this stuff.

Sjors Provoost Oh, you know that. I think it's 32. But then the transaction is pointing to other transactions. So it has to, inside the database, next to the raw transaction, it has to have all these pointers to the other transactions that probably take up space.

Aaron van Wirdum Right. Lots of overhead.

Sjors Provoost And then some way to quickly find them. Yeah, yeah, I mean, this thing was designed, I don't know when the 300 megabyte was chosen, but probably when blocks were tiny.

Aaron van Wirdum I remember being that… I remember when that was chosen, I think, I think that was included in one of my Bitcoin Core release articles. I just don't remember which one. It was probably a while ago, but I remember that it was… included at some point, I think.

Sjors Provoost But as far as I know, the last time the mempool was that full was in 2017.

Aaron van Wirdum Yeah, but it happened.

Sjors Provoost Yeah, it did. It overflowed.

Aaron van Wirdum And that creates some really weird things. That's my next question, Sjors. So we're all happily forwarding transactions to one another on the peer-to-peer network. And then at some point, some mempools get full. But there are even more transactions coming in. What happens then?

Sjors Provoost Well… Basically, nodes don't want to waste too much of their own resources and too much of the network resources. So they try to reason, okay, which transactions are the most viable. So it's like a triage. And basically, well, the transactions with the highest fees are probably going to be mined by miners because they care about high fees. So the nodes do the same thing. They look at the new transaction and say, hey, is this higher than any of the other transactions I have in my pool? And they kick out the transactions with the lowest fees and put the higher fee in there. And if the transaction arrives as a lower fee than anything they already have, like, well, come back later.

Aaron van Wirdum Right. Well, Sjors, you say that, but there is a subtle difference in how miners actually pick their transactions, isn't it? That's what we're getting to.

Sjors Provoost Well, at least how they could pick it, because, yeah, it would be very naive, or at least a little bit naive, to only sort them by fee.

Aaron van Wirdum You mean when miners pick their transactions to include in a block?

Sjors Provoost Yeah.

Aaron van Wirdum Yeah. So what do they do instead?

Sjors Provoost Well, the problem is there could be multiple transactions that depend on each other. And so…

Aaron van Wirdum What does that mean exactly?

Sjors Provoost So one transaction is me paying to Bob, and then Bob paying to Alice, and Alice paying to John. Those could all be unconfirmed transactions in a chain. And now maybe when I paid you, I was super stingy and I used one Satoshi per byte. So if the miner sees that transaction, they might think, well, it's just one Satoshi per byte. I'm going to put that in the back of the line. But when you paid to Alice, you were paying 1,000 Satoshi per byte. It was very generous. But that transaction cannot get into the… would not get into the block if the miner was this naive. So if the miner is a little bit smarter, they'll look at your transaction and say, hey, this is a very profitable transaction. Okay, but I also need to include this very stingy transaction. And so the miner might include very stingy transactions in order to get the very profitable ones if their algorithm is smart enough. I don't know if that's actually the case, but we care about the longer term game theory here.

Aaron van Wirdum Why do you say… this is what happens now, isn't it?

Sjors Provoost I don't know. Have you checked?

Aaron van Wirdum Yes. Well, I mean, I haven't checked the code, but…

Sjors Provoost Have you checked in 2017 when the mempool was actually full or that high fee transactions were included that were building on top of low fee transactions?

Aaron van Wirdum Sure. So we're just talking about… We're not talking about the mempool yet. We're just talking about the miner policy. Yes.

Sjors Provoost I don't know. I haven't checked. So I don't know if miners actually do this, what I just proposed.

Aaron van Wirdum Oh, I'm sure they do. I mean, I haven't checked the code, like I said, but I'm sure this is what they do.

Sjors Provoost I don't know. It sounds like you have to write a lot of code to do that. Or you could just be lazy.

Aaron van Wirdum No, I'm sure this is in Bitcoin Core.

Sjors Provoost Is it?

Aaron van Wirdum Yes, for sure.

Sjors Provoost And when you make a block with Bitcoin Core, you mean?

Aaron van Wirdum Yes.

Sjors Provoost So that's the… Okay. But I don't know if miners used Bitcoin Core in order to create blocks. So there is some logic in Bitcoin Core that can help you generate blocks, but I'm not sure if miners actually used it.

Aaron van Wirdum I'm fairly sure. Okay. I think so. I'm pretty confident that they use this.

Sjors Provoost Well, either way, either they do or they don't. They should or they should not. You know, it makes sense to, as we just described, not consider individual transactions, but consider them as a package.

Aaron van Wirdum Yeah. So one of the nice things about this logic is that you can actually use it yourself. So for example, you're sending me a payment. I don't want to wait until it confirms, even though you included a very low fee. So what I can do is… take the coin from the payment, just take the output, spend it to myself in a new transaction, which includes a higher fee, and therefore a miner will pick them up both and I'll have a faster confirmation.

Sjors Provoost Yeah.

Aaron van Wirdum This is especially important in some scenarios, most notably something like Lightning, right?

Sjors Provoost Yes.

Aaron van Wirdum Because in Lightning, your channel partner can cheat on you by transmitting an older… version of the channel, an older balance, which issues that channel partner more funds than the latest channel balance should actually grant him, right? So he can try to cheat on you. The way to solve that in Lightning is that you have something called a penalty transaction or a justice transaction which you've created with your channel partner earlier which allows you to claim all of the funds from the channel. It's built on the cheating transaction, basically. You now get to claim all the funds. However, this penalty transaction needs to confirm within a certain amount of time after this cheating transaction was transmitted. The channel partner can't spend the coins in the meantime, so he will have to wait, let's say, a day or whatever it is. But then it is very important that you actually get your penalty transaction included within a day, because otherwise your channel partner runs off with the funds.

Sjors Provoost Yeah.

Aaron van Wirdum So in this case, if you're transmitting this penalty transaction or justice transaction, and it has a low fee, which is very possible because you created a transaction, who knows, weeks ago, possibly, it has a low fee, it's not confirming, then you can actually use this trick to get a penalty transaction confirmed faster.

Sjors Provoost Yeah.

Aaron van Wirdum Right? This is called Child Pays for Parent. Did we mention that?

Sjors Provoost I'm not sure, but that's what it's called.

Aaron van Wirdum That's what it's called. Okay, now we get to the problem.

Sjors Provoost Yes. I received a memo from my time machine. And it was a note from the future that I recorded after the podcast or something. And it basically says that Child Pays for Parent has been in Bitcoin Core mining support since 0.13. So a while. Basically around the time when SegWit was introduced in the code.

Aaron van Wirdum Yeah, that sounds about right to me. Yeah, I remember that. Okay. Oh, before we move on, I gave the Lightning example. It's not just useful for Lightning. It's for any sort of these smart contracts setups where you need to have a transaction confirmed before some sort of time lock expires. There are several of these kinds of things, but Lightning is the best known one, I would say. Okay, moving on. Ready to move on?

Sjors Provoost Yeah, I'm ready.

Aaron van Wirdum Okay, so here's the problem. The problem, Sjors, is that child pays for parent works very well as long as the mempool isn't full. There's a problem if the mempools are filling up and transactions are being rejected because they have too low of a fee. Because in that scenario, you might send this child pays for parents transaction, which has a high fee to compensate for the previous low fee. But if the mempools are filling up and the low fee transaction was actually rejected from the mempool or ejected from the mempool, then the high fee child pays for parents follow up won't actually be accepted in the mempool either because it's not referring to any previous transaction. Yeah. So your child pays for parent trick to save your money from being stolen on Lightning network, for example, is not going to work if mempools are filling up, potentially.

Sjors Provoost Right, and that you know assumes that there's a big difference in fees in general between the punishment transaction and you spending it.

Aaron van Wirdum Yeah, I guess there's several scenarios where something like this could happen, Either a difference in fees or maybe the attacker in the channel is actually a miner, him or herself, that includes the attack transaction at first, or they know a miner, or there's an out-of-band payment, or I don't know. There's a couple of scenarios, I guess, where this attack on Lightning network would work if child pays for parent isn't working as intended on the base layer.

Sjors Provoost Yeah, and even outside Lightning, it's very annoying if child pays for parent doesn't work when fees are really high, because that's exactly when you need it.

Aaron van Wirdum Yeah, I mean, there is also, of course, RBF replace by fee, but that's only something the sender can use. While child pays for parents is also something the recipients can use. Okay. So, we're getting to the solution. The solution is package relay. This is what Gloria is going to be working on.

Sjors Provoost Yes. Well, the solution is called package relay.

Aaron van Wirdum Yes.

Sjors Provoost Whatever the solution is going to be, but it's not really solved yet. But whatever it will be, it's going to be called package relay.

Aaron van Wirdum Yeah. Okay. So do you want to explain package relay? I think you can probably explain it a little bit better than I can.

Sjors Provoost Well, I think you've done a good job, too. It's relaying transactions in a package. So rather than saying, here is one transaction, and then a little bit while later, here is one transaction, at… which, you know, if the second transaction pays more fee, but you don't really explain the relation with the first transaction, then you're going to have the problems we just described. But if you say, look, here's two transactions, one is not paying a lot of fees, but wait, there's more. This other one does pay enough fees. Please consider them both in your mempool. Don't just eject the first one. Then the mempool will say, oh, well, yeah, collectively they pay enough. I'm going to collectively keep track of this thing.

Aaron van Wirdum Yeah. So I think here we get into… just to clarify this, so yeah, instead of sending individual transactions, now we're sending packages of transactions that bundle transactions together that are dependent on each other, right?

Sjors Provoost Yeah.

Aaron van Wirdum But I think, Sjors, is this where we get into the can of worms?

Sjors Provoost Well, we can, yeah, slowly enter this can of worms, yes.

Aaron van Wirdum Let's get into the kind of worms. What are the challenges here? What are the problems that need to be solved for this to actually become reality?

Sjors Provoost Well, as with everything, you need to think about the ways this could be abused. So it depends on how you would do it, right? So one proposal is by Suhas, which I think is that the recipient… if you receive a transaction, so you consider it for your mempool, but you don't know anything about its parents, so to you it looks like… this standalone transaction, then you can call the peer that sent it to you and say, hey, do you have, you know, a package for me that you know, gives me all the transactions that precede this thing so that I can consider it as a whole? Because if I just look at this one transaction, it doesn't look very appealing to me, but maybe you can convince me otherwise. And then the original node can say, okay, here's a whole package. But that could lend itself to abuse because you could send me a transaction and say, yeah, you know, there's more. And I ask you for more and you sent me a whole bunch of junk. And I'm like, no, this is nonsense. Try again. And you sent me a whole bunch of junk again. So there's all this back and forth. But perhaps that's not a big deal because [unclear] misbehaving that way, you just disconnect it. And you could have some limits, like, okay, give me everything that leads to this transaction. You could send me two gigabytes of unconfirmed transactions and say, here's two gigabytes, go consider them all. And they're like super complicated transactions and I have to consider them all. And then the last one is like, nope, sorry, it's invalid, try again. So these kind of things you need to worry about and also where to store all it. And then I guess the other part of the can of worms is now they are in the mempool. When are you going to evict transactions? Because when you want to kick them out of the mempool, you also need to consider the package. So that probably means you need to refactor the way this mempool works right now in Bitcoin Core.

Aaron van Wirdum Well, it would probably be similar to how miners select transactions now, right? That would basically be the same logic, I would assume. It's just on a bigger scale.

Sjors Provoost It could be, but it's not a trivial problem. I think the way miners do this selection is… I don't know if it's NP-hard, but it's hard. There's lots of different ways you can do it. And you're not making money running a node, so you don't want to waste a whole bunch of CPU power trying to optimize the mempool and have your computer boil just because it's trying to optimize the mempool.

Aaron van Wirdum Right. So I think you took a quick look at Gloria's proposal work so far?

Sjors Provoost Yeah, so she's taking one little step at a time because one of the problems with this is we look at the problem, we as Core developers, I haven't actually personally looked at the problem, and… we say, yeah, this is really hard. And there's so many things we need to change. Oh man, there's all these possible things that could go wrong. Let's just take this can down the road and not think about it. So it's good that some people say, no, you know what? Let's just take the absolute minimum first step that we can take. And I believe what Gloria is doing as the very first step, and she has a whole year to work on this stuff, is to say, okay, what if you have your own node and you can talk to it through RPC? So not through the peer-to-peer network, but just directly to it. And instead of giving it one transaction to consider, not even to broadcast, just to consider, because there's a special method that says testmempoolaccept that just says, hey, is this transaction valid based on the mempool? And it says yes or no or something complicated. And instead of giving it one transaction, let's be able to give it more than one transaction. So you can actually now give your own node a package of transactions. And from what I just glanced at, I think the first version of that is is very simple. It just takes that package and considers them one by one, so it doesn't do any overarching considerations. That gives you an idea of the little baby steps we try to take to get this thing underway.

Aaron van Wirdum Yeah, and then the next step would be?

Sjors Provoost Well, the next step would be, I would guess, to say, okay, is this package as a whole acceptable? So instead of considering them one by one, you would look at the whole package. And I think one of the steps there is to sort the package so that they come in in order of whose parent is who. And I guess then you have to look at the total fees for it and see if it's still acceptable. Then once you've done that, I think the next step is to say, okay, let's actually put that package into the mempool, which might, I don't know, require rewriting the whole mempool. I don't know. And then if that works, then at least your own node understands packages. Now the question is, can we add this to the peer-to-peer protocol? And that's really where the DoS vulnerabilities are the most important to think about. Because what you do with your own node, you can't really break it. But once you start chatting over the network, you want to be careful. And if your rules are too complicated, you might accidentally get nodes banned, even though they didn't do anything wrong intentionally, and that might split the network. So it just gets hairy from there.

Aaron van Wirdum Well, Gloria, if you're listening, good luck with that.

Sjors Provoost Yeah, have fun.

Aaron van Wirdum I think this is our episode. Is it not, Sjors?

Sjors Provoost Yeah, I think so. We can do a quick shout out to the Chaincode guys for their podcast. They did one with Murch talking about deterministic builds, which is a huge can of worms.

Aaron van Wirdum Okay.

Sjors Provoost If you're into can of worms, deterministic builds.

Aaron van Wirdum Speaking of shout outs, Gloria's fellowship is going to be sponsored by Square Crypto and the Human Rights Foundation. That's probably worth a mention, right?

Sjors Provoost Yeah, it's pretty cool that they're doing that.

Aaron van Wirdum Yep.

Sjors Provoost All right. I think that's it. So thank you for listening to the Van Wirdum Sjorsnado.

Aaron van Wirdum There you go.