I know that the yellow paper does not specify how transactions are to be ordered in a block and this is up to the miner to decide. But I am interested in how this is practically handled (I assume not calling some rand function to get ordering). This answer to a related question suggests that gas price plays a role. How does, e.g. geth order transactions during the mining process?
Edit: 23 June 2017 - Added Parity details (see below)
//approach 2 transactions := self.eth.TxPool().GetTransactions() <--- fetch from pool types.SortByPriceAndNonce(transactions) <---------- order
i.e. Sorts by gas price and nonce value (and by owner account - see below).
There are two other approaches in the code which are both commented out, but may give a clue as to previous ideas (or give examples to miners who want to use their own implementation). They are:
- approach 1: sort by nonce only
- approach 3: sort by owner (treating single- and multi-owner transactions differently), then by price and nonce
// This method first sorts the separates the list of transactions into individual // sender accounts and sorts them by nonce. After the account nonce ordering is // satisfied, the results are merged back together by price, always comparing only // the head transaction from each account. This is done via a heap to keep it fast
Once sorted, the transactions are further screened in
commitTransactions() to remove any with "low gas".
For Parity things are a little easier: there's a CLI option. This will, at least, allow ordering to be changed in some basic ways.
--tx-queue-strategy S Prioritization strategy used to order transactions in the queue. S may be: gas - Prioritize txs with low gas limit; gas_price - Prioritize txs with high gas price; gas_factor - Prioritize txs using gas price and gas limit ratio (default: gas_price).
To add on the excellent answer by Richard Horrocks:
I studied the last 1000 blocks:
- ~85% of blocks seem to be ordered by High gas price first (respecting nonce order for a single sender address) (The default setting for both Parity and Geth)
- ~9% of blocks seem to be ordered by Low Gas first (Parity's "gas" tx-queue-strategy)
- I couldn't figure out the ordering for the last 6%. I suspect they might just be in the order the miner heard about them.
- No blocks seem to be ordered by Nonce only.
The source code for the different transaction ordering strategies can be found here.
Here is the default ordering logic:
- Transactions that take more than a certain time to run are penalized, and will be put to the end of the list. If a sender sends 16 offending transactions, he is banned.
- Transactions that origin from the miner node will be put first.
- The "nonce height" is checked. I assume this guarantees nonces are in the right order for a given user.
- Then the selected strategy is applied.
- If all equal, they are ordered in the order they came in.
In the end, keep in mind this is open source software, and there is no rules on how transactions must be ordered. Each miner is free to send transactions in the order he wishes, so there is no way to guarantee the transaction order, but it looks like a high gas price and a reasonable gas limit should secure you a good spot in most cases.
I think Horrock's answer is a little hard to understand, and the "sorting" is a weird type of sorting that needs a bit more explanation.
Say you're the miner, and you have 100 transactions to sort through. Say 80 unique people sent 80 unique transactions. Then say 10 unique people each sent 2 transactions. That's 10 "first" transactions, and 10 "second" transactions, for those 10 people. 100 total.
The idea is, group the 80 unique transactions and the 10 "first" transactions, into a group G.
while gasLimitNotReached: T = highestGasPrice(G) G.remove(T) if T was some Account."first": G.append(Account."second") Commit(T)
I think you can see how this extends into some accounts having three transactions or four transactions. The idea is that only let G have transactions from unique accounts. If the same account has many txs, then only consider the smallest nonce, regardless of the gas price of those larger nonces. Then, loop over G, poping in order of gas price. Everytime you get rid of a transaction, check if that account has any more transactions of higher nonce, and then add that tx back into G if it exists.
Source: https://github.com/ethereum/go-ethereum/blob/290e851f57f5d27a1d5f0f7ad784c836e017c337/core/types/transaction.go#L372, from Horrick's answer.