Scaling Bitcoin workshop : Stanford 2017

Optimizing fee estimation via mempool state

Optimizing fee estimation via the mempool state

Karl-Johan Alm (DG Lab)

I am a Bitcoin Core developer and I work at DG Lab. Today I would like to talk about fees. There's this weird gap between-- there are two things going on. People complain about high fees. But people are confused about why Bitcoin Core is giving high fees but if you set fees manually you can get a much lower fee and get a transaction mined pretty fast. I started to look into this in detail and did simulations and a bunch of stuff.

One of the ideas I had was to use the mempool state to optimize the fee rate and also very accurately determine how much time until a transaction is going to be mined in terms of cost. I think this kind of user interface guide is going to help a lot of people figure out what is going on with their transaction when it's not immediately confirmed. This might help a bunch of grief.

I want to start with the past. About 6 months ago, when I was looking, it was the most intensive, most backlogged period of Bitcoin's history and so what this is showing is the time to confirm within 1 hour and it's showing that the fee that you require at minimum to have a transaction be confirmed. This is the fee rate. So the worst case was around block 482,000 where you needed to pay 550 sat/byte to get into a block within 1 hour. This not block count, it's in time, I'm abstracting the concept of block away and mining at various speeds. I was just looking at itme of the block. The average fee was lower. As you can see, there were lots of dips in this graph. Depending on which point of time you are trying to get the transaction into the blockchain, the minimum fee varies drastically and there are big jumps to the 400s or 500s but a lot of them are down to 0s. This is different from what people are envisioning when they see an enormous mempool, it's all a matter of timing it seems. If you go a little further to two hours, here's what it looks like. It might seem high, but the average fee drops a lot as well, and if we go to 3 hours to confirm, or 24 hours to confirm here's what it looks like. If you are fine waiting a day, even in this worst peirod in bitcoin's history, you could get away with any fee you wanted, except for a few points, that you can see, the fee was about 60 sat/byte or something like that.

So I will talk a little bit about fee estimation methods used in Bitcoin Core now. In v0.15, there was an upgrade to fee estimation. There are now two modes. The default is conservative, there's also an economic non-conservative mode. I am not going to go into details of how this works. But you say a target, and you want your tx confirmed in the next n blocks, and then it gives you a fee rate based on success rates and just looking at mempool transactions that come in and later they are mined and they are in these buckets for fee rates and it's using this to determine the values. This is working really well. But it completely ignores the state of the mempool- if the mempool is completely empty and the last block had transactions with 100s of sats/byte, then it will tell you to pay 100 sats/byte. We can do better than that though. We could use it to react faster to sudden changes. We see this a lot. Sometimes the mempool just falls down to 0 and the fee estimation still says 100 sat/byte. So we create an imaginary block and we look at the 5% at the bottom and if we put our transaction in it, will we be fine? This is dependent on when the next block arrives. If you estimate that your transaction gets out there and it will probably be about 5% of the bottom part of tha tblock, but if the next block comes out 6 minutes later or something you miht have underestimated the fee on new transactions coming into the mempool.

But even if you underestimate, youcan use replace-by-fee to just fix it. It's interesting, but the mempool optimization can be gamed. We can say look at hte mempool, look at the weight, just divide by 4 million and then we know how many blocks until our transaction can be confirmed. Your tx will be mined in about 60 minutes... which is a lot better than just saying hey it's still not mined yet. If the amount of time to wait is higher than we want to wait, then we might as well use replace-by-fee immediately.

These results are not showing the fee, but the amount of fee rate overpaid to get into the block. The results are showing that there's-- there's four modes. Conservative, non-conservative economic, those are the blue lines here. And then there's the optimized version with mempool optimization for both of those modes. You can see that the mempool ... is consistently below in some situations. The idea is zero for this chart by the way, because you don't want to overestimate. There are some areas where the optimized version is doing a lot better estimation in terms of overpayment than the other two. And this other chart is showing.. it's a little less clear.

When you underestimate and you make a tx where you want the time to be 1 block, and you need about 100,000 estimations for a number of blocks. So there's.. conservative and non-conservative will underestimate in like 1.1% and 1.6% of the time. Even in just case, just waiting 1 extra block, you drop down to, conservative and non-conservative are both already mined already. You are down to like 400,000 and oyu can keep going into the blocks and by 10 blocks you have about 11 tx left, it's maybe time to do replace-by-fee bumping. You should be using replace-by-fee, especially if you are using this kind of optimization.

Replace-by-fee has been around since v0.12 in Bitcoin Core. It has become easier with v0.14 where you can use bumpfee to increase your fee. You use RBF and say you want to use RBF when you create the transaction. Later on you can bump the fee by increasing inputs or something with a higher fee rate, and the old transaction will be thrown out by everyone and the new one will replace it. You can estimate the fee delta for your optimized transaction using this method. You can bump your transaction as much as you want, there's no limit on how much you can do this. You take the sum of all the transactions aboe your fee rate and you subtract from it hte block weight and time. And then if you are below there, you're good. You could be bumped up still if someone is adding transactions, but at this time, you're still getting... probably. If you are 1 and 0 you most definitely hae to wait longer, s maybe just bump it immediately. We can figure out the exact fee we need, at least for this point in time, and this all changes as time goes on. We can take all the transactions in the mempool, the top is the most aluable highest fee rate, we order them on down, then we take 4 billion times our t and hten we go up a bit and then we hae a fee rate and we need to be below that, and we can find this delta for the fee very precisely for the current time point. We can do this repeatedly, like every second or something. We can either keep fee bumping, or we hae some threshold and we just wait longer than we wanted.

Assume that we hae a threshold and the bump estimator... we hae a block estimator, we set the threshold to what it gies us, and then we estimate the fee based on mempool, then we keep bumping it up and up until we hit a cap and at that cap we shouldn't go higher because the mempool stuff can be gamed. You're going to have a rebate period, it's more precise, we tell you exactly when your transaction is going to be mined. If it's 3 blocks later it will say about 30 minutes which I think will help new users tremendously. And it's cheaper, presumably you're not hitting the threshold you could get away with 80% less overpayment than Bitcoin Core does right now.