[tm2] Improved Mempool Logic

[zivkovicmilos]

Description

This effort covers expanding the capabilities of the Mempool module to be more in line with how stable blockchains should work.

The major problems currently present in the Mempool implementation of Gno are:

Transactions are unordered by account sequence

The current implementation of the mempool module does not take into account the account sequence ordering when returning “ready” transactions for block building.

The mempool currently returns transactions only ordered by their gas, and not by account sequence first, and gas second.

This leads to a scenario where the mempool can return transactions for block building that are not in the correct order of sending for an account. For example:

1. TX 1 sends a balance to account X, initializing it in the process (the account was uninitialized)
2. TX 2, by account X, deploys a Realm
3. These 2 transactions are prepared offline, and sent to the node for processing
4. The mempool is asked to return ready transactions in the block building process of the node, returns [TX2, TX1], since they are ordered by gas
5. TX 2 fails because the account is uninitialized
6. TX 1 succeeds
7. The user now has to send TX2 again, in order to get the desired state

Realm deploys cost more gas, so TX2 will be executed before TX1, since the mempool returns this transaction first (orders by gas). TX 2 will fail, because the account is uninitialized. Account balance transfers cost less gas, so they will be executed first in the mempool implementation.

Block building does not take into account actual gas used by a TX

The current implementation of the block building process does not take into account the actual gas used by a transaction when trying to figure out if it can fit into a block. Instead, the block building process simply reads the (user defined) gas limit, and sees if the block gas enough space to fit the transaction, even though the transaction actually uses less gas than what was specified.

The optimal flow for the block building process would be:

• get ready transactions from the mempool
• execute each transaction to see how much gas it would utilize (and whether the tx is valid at all)
  • if the tx is valid, but cannot fit into the block, return it to the mempool

This way, the mempool always has ready transactions that are executable, given the previous point about transaction ordering.

If this is not patched, there is a DDoS vector where a user can spam valid high gas limit transactions and take up all the block space (ex. with a single transaction), leaving no room for the transactions of other users.

Successful outcome of this effort:

• transactions are ordered in the mempool by [account sequence, gas]
• block generation takes into account the actual gas used, not the user defined gas used when deciding if a transaction can fit into a block

[ltzmaxwell]

in this case, the first transaction would be processed priorly because it has a lower account sequence, even it costs less gas? is this reasonable?

Account_0 send tokens to another account; (less gas cost)
Account_1 deploys realm; (more gas cost)

[zivkovicmilos]

in this case, the first transaction would be processed priorly because it has a lower account sequence, even it costs less gas? is this reasonable?

Account_0 send tokens to another account; (less gas cost)
Account_1 deploys realm; (more gas cost)

Yes, transactions should be ordered by 2 sort params:

• account sequence (nonce), ascending
• gas price, descending

[thehowl]

The optimal flow for the block building process would be:

* get ready transactions from the mempool

* execute each transaction to see how much gas it would utilize (and whether the tx is valid at all)

  * if the tx is valid, but cannot fit into the block, return it to the mempool

Is this what's done on cometbft / ethereum?

[zivkovicmilos]

The optimal flow for the block building process would be:

* get ready transactions from the mempool

* execute each transaction to see how much gas it would utilize (and whether the tx is valid at all)

  * if the tx is valid, but cannot fit into the block, return it to the mempool

Is this what's done on cometbft / ethereum?

Yes. This is how most mempool implementations work

[zivkovicmilos]

@Kouteki I'm taking this up after #2852