[MEV] reordering of transactions by gas price

[lavindir]

in progress moves consensus index to the subdag instead of on each cert

next:

• [ ] update the ExecutionState handle_consensus_transaction to take the entire subdag instead of individual transactions, and in doing this creating the ExecutionIndices for the first time on the Sui side
• [ ] reorder all the transactions within each batch of the subdag at deserialization time

[sblackshear]

A thought: would it make sense to sort by something like (!tx.has_shared_objects, tx.gas_price) rather than tx.gas_price?

This is basically setting up two fee markets: one for single-owner txes and one for shared. At some point, we'll have an unbounded number of fee markets object-specific based on shared object hotness and will want to do something more nuanced than this. But in the short term, the scheme above will prioritize all single-writer txes (which are parallel execution friendly + on-chain MEV-free by construction) over all shared object ones, which is (I think) what we want for maximizing throughput/fee revenue.

[andll]

reorder all the transactions within each batch

I have high level question about this PR. It seems that what we do here is essentially two things (1) We significantly change nw executor interface to pass entire subdag to sui (2) We add MEV logic that only reorder transactions within the batch(according to PR description)

If we only care about order of transactions within the batch, do you think we could significantly reduce blast radius of this PR by simply passing Vec<Transaction> to sui handler from the notifier? It seems that we could achieve MEV goal this way and the PR would be 3x smaller and easier to review?

And then if at some point there will be some separate motivation to pass entire subdag perhaps we can make a separate PR for that?

[lavindir]

@andll The goal is reordering all the transactions in each subdag. This change does touch a lot of code, but ultimately allows a lot of major simplifications and optimizations which I am glad to take advantage of. Some interesting things to consider:

1. The ordering that was created before in consensus came from arbitrary enumeration, and so constructing execution indices there was arbitrary complexity. The execution indices can be simplified further, this is still in progress.
2. It removes the need for an entire NW component
3. This change also allows us to avoid needing to update execution indices to disk to the on every transaction execution, at the tradeoff of iterating through the subdag and checking each transaction's execution status on recovery.

[andll]

@laura-makdah just to clarify - are you planning to sort transactions by gas price only inside the batch (in which case I don't understand why do we need to bundle all those nice changes in one PR)? Or are you planning to sort them across entire subdag(in which case, perhaps PR description need an update, since it seem to state sorting is with the batch?)

[lavindir]

@andll description updated, we are taking all transaction in the commit, irrespective of the cert & batch, and reordering them all in one big pile

[vercel[bot]]

The latest updates on your projects. Learn more about Vercel for Git ↗︎

1 Ignored Deployment

Name	Status	Preview	Updated
explorer	⬜️ Ignored (Inspect)		Dec 6, 2022 at 5:49PM (UTC)

[lavindir]

@andll thank you for the extremely helpful review!