Defend against MEV or PEV (Primary Extracted Value) attacks

[Jim8y]

Summary or problem description
As is mentioned by many people from the community, I think it is time that we start to consider the threat of MEV attack and start to discuss and come up with a solution to address it.

Do you have any solution you want to propose?
I think the key to the solution should be removing the right of deciding the transaction list from the primary. Therefore, we can ask all consensus node to send their own version of the transaction list to the primary, then we add one extra step to the consensus to collect the transaction list from other consensus nodes. Since we assume the number of dishonest nodes no more than N/3, therefore we only need to collect N/3 +1 transaction lists. The consensus node calculates the final transaction list from the lists it receives. And in the preparerequest message, the primary also attaches the transaction lists it collects as proof.

Please also share your solution to MEV here if you have one.

Neo Version

• Neo 3

Where in the software does this update applies to?

• Consensus
• Plugins

[Jim8y]

@doubiliu @roman-khimov I believe this solution will also solve your concerns about #2456.

[igormcoelho]

@Liaojinghui that's an interesting discussion.
It occurred to me that, perhaps, the best way to solve this is to attach the list of proposed tx hashes together with definitive block signature (in Commit Phase). This guarantees that 2f+1 lists are always received. Also, no time is lost: all transactions that were received/validated during the consensus process will be considered for next block.
What do you think? @vncoelho

From implementation perspective, as long as this information is attached together with Block signature witness, it could be removed/pruned in the future.
Finally, it could perhaps work as some real witness Script, such as:

• List of tx hashes L
• assert( L in GetTransactionList(BlockIndex+1))
  This "future" call to next block transaction hashes could return "true", if future block doesn't exist, but could also be executed only when next block proposal is made... this allows us to easily extend consensus "future block agreement" logic in the future (as a smart contract).

[UPDATE]
In fact, since f nodes can be byzantine, thus are able to propose inexisting transactions, some minimal support of f+1 over the subset of 2f+1 tx lists is enough to enforce the necessity of that tx to be included in next block by any honest primary.

Example with N=4 f=1:

• N1[honest]: proposes hashes of [tx1, tx2, tx3, tx4] for next block
• N2[honest]: proposes hashes of [tx2, tx3, tx4, tx5] for next block
• N3[byzantine]: proposes hashes of [tx7, tx8, tx9] for next block (hashes of tx7, tx8 and tx9 dont exist on network)
• N4[honest but delayed] : did not participate on previous consensus

In this example, next primary would need to include tx2, tx3 and tx4, all with support f+1=2. Bad transactions tx7, tx8 and tx9 (support <f+1) are not required for next block. Valid transactions tx1 and tx5 (support <f+1) may or may not be included, depending on which node is next primary (N1 or N2). Finally, transactions would be required for inclusion in lexicographic hash order, meaning that few arbitrary tx order manipulation would be possible at this point.

[Jim8y]

@igormcoelho a good one, but we can not take all txs from lists, we have to consider the block size to make sure we can reach consensus in time. If too many txs are added, it would be a DOS attack.

[igormcoelho]

Fully agree @Liaojinghui , given size of B transactions per block, every node list proposal should be limited to B, or even to less than B... it depends on the pressure we want to make on primary node.
And note that I only propose to send Transaction Hashes, not real transactions... the mechanism of gathering tx from p2p or perhaps already present in consensus node mempool (due to nice distribution) is already enough.. we just need to secure the hashes and guarantee a transparent block proposal from elements in supported list.

[igormcoelho]

Another possibility, if we are "feeling luck" and want to avoid p2p pressure, is to send not the Transaction Hash list, but some Bloom Filter mapping of the block proposal. This way, information is highly compressed, with possible false positives (but No false negative), and the work of the primary is to propose transactions that match the bloom filters of f+1 other nodes. This way, we can send a heavy list of whitelisted transactions, just spending few bytes each.

This approach is nice, because False Positive just implies that next primary node was lucky to have some random tx that "happened to be supported by others", but bad scenario is when next primary has only transactions that fall as Negatives... in this scenario, next primary will be unable to guess which transaction it needs to require from network. But think about, if Next Primary is so poorly provided in its mempool, its really better to just skip turn and view change anyway.
Byzantine node could then provide a block proposal that doesn't match any of the proposals from others, but it could be monitored that some given node is behaving strangely regarding tx proposals. It also depends on the pressure we want to put to prevent MEV and resources we want to spend from P2P.

Bloom filter size could be adaptive too, if mempool is crowded, it increases size (more bits) to match more tx, if not too crowded, vector gets smaller (less bits) to get more and more faster.

I would vote for some proposal like this, but if people prefer clean lists and stronger p2p/MEV pressure that's fine too.

[Qiao-Jin]

Furthermore, we can add some more logic to prevent mev attack, such as executing txs in an order which is determined by Block.Nonce. This is to prevent cheating activities by controlling tx execution order by delicately set tx fee.
Current nonce might not be enough, but after BLS added into consensus it should work well.

[Qiao-Jin]

It occurred to me that, perhaps, the best way to solve this is to attach the list of proposed tx hashes together with definitive block signature (in Commit Phase). This guarantees that 2f+1 lists are always received. Also, no time is lost: all transactions that were received/validated during the consensus process will be considered for next block.

In this model there might be still some tasks that speaker next round can perform MEV attack by excluding commits whose tx list contains txs he don't like. An optimization can be performed to prevent such behaviors to some extent like this:

1. Each commit payload's tx list contains hashes of the first 2 * MaxTransactionsPerBlock (or 3 * MaxTransactionsPerBlock, etc) transactions in its mempool.
2. Speaker next round needs to pick 3/2 N commits & get a transaction union where each of the transactions are voted by at least f + 1 consensus node. It then sorts the union by votes. It then gets a tx set for its PrepareRequest payload by picking transactions one by one from this union until MaxBlockSize or MaxTransactionsPerBlock is reached.

It will work well when traffic is busy and there are more than MaxTransactionsPerBlock transactions in each consensus node's mempool. In such cases a tx would need more than f + 1 votes or even 3/2N votes to get into next preparerequest. Hence whichever commits the speaker next round picks, the probability that it will come up with the same PrepareRequest will be rather high.

[Jim8y]

@Liaojinghui that's an interesting discussion.
It occurred to me that, perhaps, the best way to solve this is to attach the list of proposed tx hashes together with definitive block signature (in Commit Phase). This guarantees that 2f+1 lists are always received. Also, no time is lost: all transactions that were received/validated during the consensus process will be considered for next block.

@igormcoelho Don't you think your solution will make it 2X longer to confirm transactions?

[roman-khimov]

Transaction lists can be quite big to exchange from every CN and any kind of tx list synchronization between CNs will probably seriously affect performance for busy networks. We already have #2188 and I fear these changes will make the situation worse when CNs have slightly differing (legitimate) tx sets in their mempools.

Reordering transaction execution based on unknown to Primary nonce seems to be more viable (but conflicting with dependency idea from #1502 (comment) which I think ultimately will be useful). At least it allows to thwart front- and back-running that is quite trivial to do at the moment (with fee-based sorting) for ordinary network users, not involving any primaries. But it still allows Primary to add some transaction not known publicly into the list (it's risky on a big network though, other CNs have to get it anyway before timeout).

Maybe there is a set of problems actually that we can call a MEV attack:

• including non-public tx into the list
  Can we separate this case from Primary legitimately having slightly bigger tx set in its mempool compared to other CNs? Probably not.
• manipulating tx order
  This can be solved by removing control of execution order from Primary.
• not including publicly known tx into the list
  Can we separate this case from Primary honestly not knowing some tx? Probably not.

[igormcoelho]

@igormcoelho Don't you think your solution will make it 2X longer to confirm transactions?

@Liaojinghui if we are worried about computational time on p2p, and I agree on that, I propose that we follow the Bloom Filter strategy, and submit only a few bytes to represent the whole mempool. If we have lots of false positives, no problem, because we are just weakening the MEV protection (but making p2p faster). If we want to be more strict about MEV, and put more burden on P2P, we can increase the number of bytes (or send the whole list).

Checking a proposed Transaction Header against a list of 2f+1 bloom filters may be quite fast, as long as we use a fast hash for Bloom Filter.

@roman-khimov I agree with your worries about #2188 and the description of the MEV problem in three points. I also agree in using Nonce or something else to make tx list deterministic.

[Jim8y]

@igormcoelho It's not the computing workload. If I did not misunderstand, you need one consensus to add transactions to the commit (or whatever the message), and another consensus to package them into Block, therefore, you need two consensus periods to confirm a transaction.

[Jim8y]

• including non-public tx into the list
  Can we separate this case from Primary legitimately having slightly bigger tx set in its mempool compared to other CNs? Probably not.

@roman-khimov The primary decides the transaction order (No one but the primary knows), which will determine the transaction result, then he can generate tx accordingly. And if a primary has transactions that only exists in the primary mempool, I don't think that primary should be considered as honest, as it is supposed to relay that transaction to other CNs.

• manipulating tx order
  This can be solved by removing control of execution order from Primary.

The problem is how to safely decide the transaction order.

• not including publicly known tx into the list
  Can we separate this case from Primary honestly not knowing some tx? Probably not.

If a transaction is synchronized to all CN and pays the highest transaction fee (or publicly known), yet the primary chose not to include it, I don't think this primary is an honest node.

Here is how I assume an honest CN should be like:

• Relay all txs right after they verify them to other CNs.
• Being a primary, does not include any non-public tx to the tx list.
• Bing a primary, order transactions strictly based on the tx fee.
• Should has a highly similar mempool with other honest CNs.