Algorithm for selecting a low-fee transaction from the mempool

[entebah]

The 10tx-11sat/byte vs. 11tx-10.1sat/byte makes some sense.

I didn't "blame" anyone, I am asking what is the algorithm they use to create a block.

then maybe that algorithm is correct because they are choosing all the highest fees to mine and then the lowest fees. Right now if you check mempool you will see a total of over 122.17 MvB for transactions under 10 sat/vByte which is need over 120 blocks to mine all of that and if you want to get your transaction got confirmation faster then use a high fee for your transaction or wait until your turn to get in a block.

[1714621907]

1714621907

[1714621907]

1714621907

[Plaguedeath]

I didn't say that the miners are "greedy". I was asking if they are adopting a "greedy algorithm" to choose transcations.

Please all read first https://en.wikipedia.org/wiki/Greedy_algorithm

You're force someone to say Bitcoin is using greedy algorithm, alright I will say miners are choose to include the next transaction because they adopt a greedy algorithm.

Greedy algorithm only work when there are more than 2 next factors.

The miners are choose the transaction based on the fee rate, this is only one factor.

If there's another consensus e.g. it must be Bitcoin transaction, not BRC-20 token transaction, then it's right if the current miners are greedy since they only focus to choose the high transaction fee and don't care if it's Bitcoin or BRC-20 token.

[o_e_l_e_o]

I didn't say that the miners are "greedy". I was asking if they are adopting a "greedy algorithm" to choose transcations.

Miners are free to use any algorithm they like in order to choose which transactions to include in their candidate blocks.

In general however, then yes, miners simply prioritize the transactions in their mempool which have the highest fee rate. There are a few exceptions to this - for example mining pools will also include their own transactions with very low fees, Binance pool includes transactions made by the Binance exchange with low fees, they may include transactions they have been paid privately to include, and so on. However, these types of transactions usually only make a small handful of the total number in the block, with the vast majority of transactions simply being prioritized based on their fee rate.

[bomberb17]

The 10tx-11sat/byte vs. 11tx-10.1sat/byte makes some sense.

I didn't "blame" anyone, I am asking what is the algorithm they use to create a block.

then maybe that algorithm is correct because they are choosing all the highest fees to mine and then the lowest fees. Right now if you check mempool you will see a total of over 122.17 MvB for transactions under 10 sat/vByte which is need over 120 blocks to mine all of that and if you want to get your transaction got confirmation faster then use a high fee for your transaction or wait until your turn to get in a block.

There is no "correct" or "wrong" algorithm for this problem, rather an "optimal" algorithm. I think we can just assume that miners want to maximize their profit, but a greedy algorithm might not be optimal. E.g. see example posted before with the 10.1sat/byte example and https://en.wikipedia.org/wiki/Greedy_algorithm#Cases_of_failure

"wait until your turn" -> not sure what you mean here. That's exactly what I asked in my original post, i.e. if transaction age is a factor. If age is not a factor (which makes sense, since miners don't care and just prioritize higher fee transactions) then there's no notion of a "turn".

I didn't say that the miners are "greedy". I was asking if they are adopting a "greedy algorithm" to choose transcations.

Miners are free to use any algorithm they like in order to choose which transactions to include in their candidate blocks.

In general however, then yes, miners simply prioritize the transactions in their mempool which have the highest fee rate. There are a few exceptions to this - for example mining pools will also include their own transactions with very low fees, Binance pool includes transactions made by the Binance exchange with low fees, they may include transactions they have been paid privately to include, and so on. However, these types of transactions usually only make a small handful of the total number in the block, with the vast majority of transactions simply being prioritized based on their fee rate.

So currently according to https://twitter.com/CoreFeeHelper, a 11.7sat/byte transaction should get confirmed between 3days-1week. But if miners simply choose those transaction with the higher fee (and assuming than mempool size remains the same), then this transaction should never get confirmed as the higher fee transactions will always get priority over it. So maybe we're missing something here.

[o_e_l_e_o]

If age is not a factor

It isn't.

So currently according to https://twitter.com/CoreFeeHelper, a 11.7sat/byte transaction should get confirmed between 3days-1week. But if miners simply choose those transaction with the higher fee (and assuming than mempool size remains the same), then this transaction should never get confirmed as the higher fee transactions will always get priority over it. So maybe we're missing something here.

What you are missing is that you are making the assumption the mempool size remains the same.

We cannot predict what the mempool will do. We cannot predict how many new transactions are going to be broadcast, how large those transactions are going to be, or what fee those transaction will pay. We also cannot predict whether we will find 10 blocks in the next hour or 0 blocks in the next hour. As such, every fee estimation is exactly that - an estimation.

Having said all that, an estimation of 11.7 sats/vbyte for 3 days is on the low side, since we've got over 90 MvB of unconfirmed transactions above this level already in the mempool, even without taking in to account any new transactions. For 3 days right now I would probably go somewhere around 16 sats/vybte which is about 20 MvB from the tip, but it's still just an educated guess.

The thing to do is to make sure you enable RBF on all your transactions. That way if it gets stuck, you can easily bump the fee higher.

[bomberb17]

What you are missing is that you are making the assumption the mempool size remains the same.

We cannot predict what the mempool will do. We cannot predict how many new transactions are going to be broadcast, how large those transactions are going to be, or what fee those transaction will pay. We also cannot predict whether we will find 10 blocks in the next hour or 0 blocks in the next hour. As such, every fee estimation is exactly that - an estimation.

Having said all that, an estimation of 11.7 sats/vbyte for 3 days is on the low side, since we've got over 90 MvB of unconfirmed transactions above this level already in the mempool, even without taking in to account any new transactions. For 3 days right now I would probably go somewhere around 16 sats/vybte which is about 20 MvB from the tip, but it's still just an educated guess.

Not sure how corefeehelper computes those estimates, but I don't think it makes those estimates with the "hope" of the mempool somehow magically clearing in the next days. After all, its estimates dynamically change as the mempool size fluctuates, so I think corefeehelper publishes those estimates periodically under the assumption that the mempool size remains the same at the time of those estimates are published.

Maybe someone from corefeehelper could shed some light.

Also some wallets e.g. electrum provide an estimate themselves based on mempool size and selected fee, so maybe someone pointing to their code on computing this estimate would be also interesting.

The thing to do is to make sure you enable RBF on all your transactions. That way if it gets stuck, you can easily bump the fee higher.

I know the basics, the discussion is about miner logic on selecting transactions and transaction processing estimates.

[franky1]

code is a great thing. code can create rules.. code did create rules..
blockchains and the network could and did enforce rules.. though less apparent recently
there used to be rules on tx selection. heck they even had code where 10% of blockspace had a priorty area whereby those with OLD coin-age can get priority with a low fee.

code can be used to deter spam instead of rejecting transactions for being too cheap
reject child transactions where parent is only 1 confirm deep unless the child pays 144x than someone with 144 confirms deep
that way it only punishes the spammers..that want to spam every block. but not punish those that only transact once a day.. unlike the 'make everyone pay more' current concept that bitcoin has been bastardised into by removing certain old fee mechanisms and refusing to implement spam busting mechanisms

yep right now the core devs p[refer to allow a transaction ancestry to be included in a block that has 20 ancestors of 1 OR LESS confirms.

they should instead implement rules that deter spam being set 20 tx deep all in the timespam of 1 block confirm

[o_e_l_e_o]

Not sure how corefeehelper computes those estimates, but I don't think it makes those estimates with the "hope" of the mempool somehow magically clearing in the next days. After all, its estimates dynamically change as the mempool size fluctuates, so I think corefeehelper publishes those estimates periodically under the assumption that the mempool size remains the same at the time of those estimates are published.

I don't think either of those scenarios would be accurate. As I said above 11.7 sats/vbyte was 90 MvB from the tip. If the mempool stayed the same size as in no new transactions were broadcast, then you would hit that level in about 15 hours, which is far less than 3-7 days. Similarly, if the mempool stayed the same size as in every block which was found was replaced by the same weight of new transactions paying the same fee, then we would never hit 11.7 sats/vbyte because the mempool would never empty.

Every fee estimator has its own method. Some are better than others. Some simply place your transaction within x MvB from the tip, while others pay attention to recent trends, whether the mempool is filling or emptying, incoming transactions over the last x hours, variance in the hashrate, and so forth.

Also some wallets e.g. electrum provide an estimate themselves based on mempool size and selected fee, so maybe someone pointing to their code on computing this estimate would be also interesting.

The static and mempool fee from Electrum requires no estimation. You simply pick either a flat fee or the set number of MvB from the tip. The code for the ETA fee on the other hand can be found here: https://github.com/spesmilo/electrum/blob/fda408e4e47f3093cf8da6713174bfc1cb5bac63/electrum/simple_config.py#L423

[Findingnemo]

I broadcasted a low fee (11sat/vbyte) transaction last week, just at the time when they fees went up.
I knew that the fee was low and that the transaction would take a few days to confirm (according to https://twitter.com/CoreFeeHelper , it would take around 3 days) but it's been a week and my transaction is still in the mempool. Sometimes my wallet (electrum) shows it with a blue "unbroadcasted" icon and I have to rebroadcast it again. I also sometimes use "free" tx accelerator services which basically rebroadcast the transaction everywhere.

My question is what is the algorithm that a miner picks a transaction from the mempool to include it to a block?
Is it a greedy algorithm which just picks the ones with highest fees? Is the "age" of a transaction in the mempool also a factor? Or is it just a combination of fee and a random choice?

First of estimated time to confirmation is just based on the current status of network but its obsolete cause the network status keep changing every minute so even if you paid enough fee for the transaction to get included in the next block and all if a sudden the fee required doubled and it's pretty normal thing.

There were some free bitcoin transaction accelerators in the past but not sure still they are available but its not really a possible solution, if you can't wait just bumping the fee is the only option or the receiver can also pay the required transaction to get confirmation quicker.

[Synchronice]

Not sure how corefeehelper computes those estimates, but I don't think it makes those estimates with the "hope" of the mempool somehow magically clearing in the next days. After all, its estimates dynamically change as the mempool size fluctuates, so I think corefeehelper publishes those estimates periodically under the assumption that the mempool size remains the same at the time of those estimates are published.

Maybe someone from corefeehelper could shed some light.

Also some wallets e.g. electrum provide an estimate themselves based on mempool size and selected fee, so maybe someone pointing to their code on computing this estimate would be also interesting.

It definitely makes its estimation with the hope that mempool somehow magically clears in the next days, yes! It's very easy to abuse bitcoin transaction fees, even with some thousands of dollars you can significantly increase the fee for everyone for a while and you know, when fees go high, people start panic and everyone pays more and more fees in order to get transactions confirmed.
Right now, corefeehelper states that 21.0 sat/byte will get your transaction confirmed in 6 hours. If I make a lot of high fee transactions and increase the baseline fee for everyone, I can pretty much stuck your transaction for more than 6 hours or probably for days, NFT ordinals are perfect example to prove that bitcoin transaction estimation at some point depends on hope.

Their logic is simple, they analyze past transactions, upcoming transactions, certain timeframes and then make an estimation.

[worle1bm]

The transactions will be approved based on the fees only so best is to add average rate so that it's confirmed by the miners fast otherwise it would be stuck in memepool.But this is how miners make profits and this is what makes them indulged in the mining system making network secure so you can't say it's greedy algorithm.They are spending more without any guarantee of rewards so that profit goes to them.But at this time also fees are not that much if you see them.

[Little Mouse]

So currently according to https://twitter.com/CoreFeeHelper, a 11.7sat/byte transaction should get confirmed between 3days-1week. But if miners simply choose those transaction with the higher fee (and assuming than mempool size remains the same), then this transaction should never get confirmed as the higher fee transactions will always get priority over it. So maybe we're missing something here.

Transaction age shouldn't be a factor here to consider for adding into a block. It would minimize the number of people getting interested in mining Bitcoin, turning it into a less decentralized network. I'm not an expert when it comes to the technical aspects of Bitcoin so I can be wrong with my assumption.
When there's no greedy algorithm as per your point, miners will have an algorithm based on coin age, who will select the fees per byte? You can use 10 sats/byte or you can use 1 sats per byte. Of course, there will be fewer miners because the profitability will drop significantly because they will be forced to include all the transactions based the age. Fewer miners = Less decentralized.
If you fix a certain fee, say tx using less than 10 sats per byte, won't be included in a block, you are censoring the network. You can't fix a fee, you can't include all the tx regardless of the fee used in the tx. It's not going to work I think.

[o_e_l_e_o]

Transaction age shouldn't be a factor here to consider for adding into a block. It would minimize the number of people getting interested in mining Bitcoin, turning it into a less decentralized network. I'm not an expert when it comes to the technical aspects of Bitcoin so I can be wrong with my assumption.

Age used to be an important factor, back when the vast majority of transactions did not pay any fee. The more confirmations an input had before you spent it, then the higher the priority given to that transaction. The other factors taken in to account were the amount being spent (higher amounts had a higher priority), and the size of the transaction (smaller transactions had a higher priority).

But of course none of that is relevant any more, and miners prioritize transactions solely on the fee rate that they pay.

[franky1]

But of course none of that is relevant any more, and miners prioritize transactions solely on the fee rate that they pay.

MINERS dont choose transactions... stop reading scripts from 2010
pool managers choose transactions

most asic owners dont profit from fees because they only share the 6.25btc reward. pool managers however took the fee as their manager commission

pool managers did not remove the code of a fee formulae.. core devs did
so please stop trying to blame asic owners(miners) and instead take a modern look at whats actually occurred since 2010

i do find it funny how certain devs devoted cultists are shouting "pay more fees". then blaming asic owners for the fee rise

now take this scenario. imagine bitcoin was paypal/venmo
do you think users would be screaming "everyone should pay more fees".. no
so you have to ask who would be inclined to price themselves and others out of using bitcoin...
only those financially tied to paypal developers/paypal sponsors would
or those involved with a competing payment system like venmo


so when 'degenerate wannabe dev assistants/interns' are shouting everyone should pay more fees.. you got to look at their motives.. then you realise their idols(devs) have created other networks which they want people to move over to so the devs can syphon routing fees off users on the other networks
so then you realise why devs are trying to junk up bitcoin and annoy bitcoiners

[DeathAngel]

I really appreciate the effort, I never like to risk doing anything that may result in me waiting a long time to get a confirmation. I remember in the 2017 bull run & during the block size war sending bitcoin with a low fee & having to pay extortionate fees to a pool to get my transactions confirmed. I would rather not risk sending bitcoin & miscalculating the fee, trying to be a cheapskate & end up waiting.

I use this right now to ascertain the best fee to send - https://mempool.space/

I’d rather just pay the fee required to get a faster confirmation than save $1.50 or something so small & end up waiting hours or worse days for a confirmation.

[o_e_l_e_o]

I never like to risk doing anything that may result in me waiting a long time to get a confirmation.

Then just enable RBF on all your transactions.

There really is no reason not to. There is plenty of good wallet software out there which supports it. Given that opt in RBF has existed for 8 years, if your wallet software doesn't support it then it's time to find new wallet software. If you are in a hurry you don't have to massively overpay since you can just bump your fee if the mempool suddenly fills or there is a long delay to the next block. If you are not in hurry you can set a low fee and bump it at a later date if circumstances change and you still aren't confirmed.

With full RBF continuing to gain traction, if you are still using wallet software which does not allow you to replace transactions easily then you are going to be left behind.

[stompix]

most asic owners dont profit from fees because they only share the 6.25btc reward. pool managers however took the fee as their manager commission

Oh really?
And I'm sure with your infinite knowledge you can give a ton of examples where mining pools keep the fees, right?
Oh, and please don't quote Wikipedia unless you want to make a fool of yourself as the info out here is last century old!

Actually, let me make this easier for you:
https://support.antpool.com/hc/en-us/articles/5983010227993-Miners-Settings-Fees
https://f2pool.zendesk.com/hc/en-us/articles/360061042332-PPS-PPLNS-PPS-and-FPPS
https://www.binance.com/en/support/faq/how-to-calculate-mining-earnings-360040955392
https://support.viabtc.com/hc/en-us/articles/900001529626-How-are-profits-calculated-
https://help.braiins.com/en/support/solutions/articles/77000426262?_ga=2.1694257.1079338613.1660209602-111809037.1657870635

I didn't say that the miners are "greedy". I was asking if they are adopting a "greedy algorithm" to choose transcations.
Please all read first https://en.wikipedia.org/wiki/Greedy_algorithm

You should read it again.
The greedy algorithm doesn't apply here because the miners don't choose a path, so they don't pick up a block with high fees that would be followed by a block with smaller fees while the other path starting with a low fee block would have been followed by a billion blocks of high fees.
It's not a path game, it's a linear choice.

wait until your turn" -> not sure what you mean here. That's exactly what I asked in my original post, i.e. if transaction age is a factor. If age is not a factor (which makes sense, since miners don't care and just prioritize higher fee transactions) then there's no notion of a "turn".

Again, let's assume age would be a factor, some users could spend $300 with 1sat/b tx and fill a full block, or some attacker might decide to just throw 20 BTC out of the window by sending coins to himself and there you go, for 10 days everyone would have to wait for his turn to end.
Does it seem like a solution you would want that the greedy miners hate?

As for CoreFeeHelper every one of those algorithms works on past data and with the 10 min block time,  none is cable of anticipating Binance dumping 40 blocks of tx in a single minute, none is cable of predicting you will not have a block mined for an entire hour, just as how they can't predict you will have 6 blocks mined in under 13 minutes. So, for them is all past data and current time since the last block but it can take only 1 second for your tx that was supposed to be confirmed in the next block to end up 4 blocks away and then everyone will keep increasing their fee, estimators will rise the fee and your tx will get buried more and more and furthermore by the same estimators that told you an xx/sat/b  will be confirmed in 10 minutes.