How transactions are selected by the miners?

Question

The deployment of transaction executions is bounded by the block gas limit that changes dynamically. If a block fits only one transaction, then the gas limit per transaction is, in theory, the same as block gas limit. As of 2020, this limit is around 10 million. There is also a minimum base cost for each transaction of 21,000 gas.


---

From answer for this question How are transactions stored in a block? @Richard Horrocks:

However, miners can order transactions however they like, as long as the order equates to a set of valid state transitions.

[Q] Hence, transaction order is decided based on the miners, but how the transactions to be included into blocks are decided?

As I know miners select the most profitable transactions based on gasPrice * gasLimit. Does using a very high gas limit somehow get your transactions executed slower? @iamdefinitelyahuman:

The reasoning: miners seek to maximize their profit within each block. Calls to eth_estimateGas can be computationally heavy, so miners typically do not determine the actual gas each tx will consume. Instead they calculate gasPrice * gasLimit for each given transaction and from that determine the most cost-effective set of transactions to mine.

---

=> For example, I submit a transaction with a very high gasPrice which has 10,000,000 gasLimit. It is selected and added into a block. Since it consumes all the gasLimit of a block no other transaction is included.

Afterwards, during execution, my transaction only consumed 21,000 of gas and remaining part is refunded back to me. There is still remaining 9,979,000 of gas to be consumed on the block. Can the miner dynamically add more transactions after selected transactions' executions are completed?

or all the transactions are decided statically and cannot be updated after their executions are completed. If it is the case, miners tend to prioritize a lot of smaller tx's over one large one and larger ones never be deployed.

=> Is there are common algorithm for miners to decide the transactions to be included into a block? Let's say, does all the combinations of pending transactions is generated in order to select the most profitable one using brute force or greedy algorithm? Since time is very important to solve the puzzle first, deciding the transactions to be included into block might consume additional time.

Answer 1

how the transactions to be included into blocks are decided?

Short answer

Any way they want.

It is not deterministic and it is not constrained by the protocol.

a transaction with a very high gasPrice which has 10,000,000 gasLimit.

Working from gasLimit alone would be a very inefficient miner because of the example you gave. Upon execution, the transaction used only a very small amount of gas, therefore paid only a very small fee.

From the miner's perspective, there is no difference between "actual" cost and estimated cost. This is because the miner is indeed determining the canonical transaction order. In case that is a little cryptic:

1. Transactions may have somewhat unpredictable cost because of unknown prior conditions (when mined) and conditional logic (e.g. loop around more times == more gas). So, senders will often pad gasLimit with sufficient gas to cover the worst case, knowing they will receive a refund anyway.
2. The miner is packing pending transactions into a proposed block in a determined order so they can rehearse the transaction and find out exactly what it will cost in that context - so gas burned is the better number and they should probably use it.

Can the miner dynamically add more transactions after selected transactions' executions are completed

Yes. That's what they do. They are playing Tetris with pending transactions and attempting to optimize gas * price packed into blocks. Everything they do is hypothetical. They can rehearse the transactions (actual gas cost) and pack the block but nothing is finalized until they find the elusive nonce and broadcast their block. There is no constraint on rearranging the configuration as new transactions arrive and new opportunities emerge.

Intuitively

To really see the optimizations and the algorithms, consider digging into the source code of the popular miners. I'm not sure this is how they do it because "any way they want" covers a lot of my concerns. Having said that ...

If I were approaching that problem, I think I would follow an algorithm like packing a shipping container where I want the maximum possible mass in a finite space.

A possibly naive way to do it, but simple, would be to order the boxes/transactions by density/gasPrice and stuff them in, in that order (descending). That would leave some cavities.

A block is a one-dimensional space so we don't have to worry about the shape of the extra space. So, just keep stuffing the highest gasPrice (any size/any gas burn), into all available space and keep going until there is no remaining gasLimit to utilize.

There would will opportunities for small, low gasPrice transactions to fit in near the end, since the algo will be looking for anything small enough to fill the last remaining space. It would favour the transaction with the highest gasPrice that actually fits.

I think the reality of it is a little more nuanced since a miner also has to optimize searching for the nonce and possibly shouldn't dedicate too much time to reorganizing as new transactions arrive. I have often wondered to myself how frequently they re-evaluate. It may indeed be more efficient overall to focus mainly on the search for the block reward rather than pausing to fully optimize for transaction fees. Also, the possibility of miners using different approaches has the effect of balancing the way the network does it overall. For example, if some miners ignore large or small transactions, that bias is balanced by other algos that approach it with other methods.

As a dApp developer or user, it usually suffices to understand that transactions are approximately prioritized by gasPrice, large transactions may take some time owing to the massive chunk of the block they need, and miners are permitted to do whatever they want within the protocol constraints, chiefly block gasLimit.

Hope it helps.

Hope it helps.