DOST (Delayed Ordered Sequence of Transactions) — An onchain, probabilistic, transaction reordering proposal to mitigate MEV by reusing POW as a delay function
This is a Request for Comments for a proposal to mitigate MEV. All comments and feedback are very much appreciated.
Proposal
The basic idea is that the POW calculation is already a cheap, onchain probabilistic delay function — while theoretically not a Verifiable Delay Function (VDF), POW could be practically reused to create an unpredictable, probabilistic transaction ordering in the mined block to mitigate MEV.
The proposal is for the Block Proposer (aka Miner) to do the same POW calculation steps as today, but change a few steps after that to achieve at the final transaction ordering as follows:
Steps same as today:
 The Block Proposer chooses any sequence of transactions they wish to include in the block B
 The Block Proposer runs the proofofwork algorithm Ethash to come up with a block nonce H_n as usual
New Proposed Steps:

For each transaction t in the block B, compute Slot_t = KEC(H_n, TransactionHash) where KEC is the Keccak256() hash function, H_n is the Block Nonce calculated from POW in Step 2 and TransactionHash is the hash of the transaction t

Order the transactions in increasing order of Slot_t. Let’s call this new sequence of transactions as DOST (DelayedOrderedSequence of Transactions)

The mined block will be considered enshrined in the blockchain with the transactions in the new DOST order

Note that the state (“World State”, gasUsed, stateRoot etc.) in the block header and the various hashes now technically need to change because of the changed transaction ordering. The key observation is that all these can be deterministically calculated independently by anyone based on the above DOST ordering steps. There are a few choices we have regarding what to include in the mined block header:

Don’t change anything in the block  Other miners can recompute the changes required to the state and the block header deterministically using Nonce and the set of transactions. These don’t need to be stored on chain, just as many other deterministically computable things are not stored on the chain but are present as miner’s data structures

Let the block proposer recompute the block header based on the DOST transaction ordering. Store a single new hash H_DOST = KEC(new block header). Other miners can verify this hash H_DOST as part of their block verification process. This adds some data (32bytes at the most, though we can probably go with a truncated hash) but stores a commitment of the current state in the blockchain that all miners can verify

Note that because the transaction ordering anyway changed after POW, there is no point in computing some fields of the original block header that was input into the POW calculation (eg the original stateRoot, gasUsed etc. will all change after the DOST ordering). So an optimisation is that those fields are zeroed out (or we use BLOCKHASH) before POW, and then after POW and after the DOST ordering is known, those fields are populated based on the final DOST ordering. This saves the need to store any new data in the block header as well as saves the work of block proposer calculating the world state prePOW

Notes
(A) MEV fundamentally originates from the miner being able to dictate the exact sequence (ordered set) of transactions in the blockchain. The basic idea in this proposal is to remove this deterministic control. How to do so permissionlessly on L1 and unpredictably so that it can not be easily gamed by the miner? Luckily, POW itself presents a possible solution to the dilemma  we just use the Block Nonce H_n computed as part of the POW algorithm as the source of pseudorandomness.
(B) Another way to look at this proposal is that POW is already a cheap onchain probabilistic delay function — technically not identical to a Verifiable Delay Function (VDF) as VDFs are theoretically defined to be sequential and deterministic, while POW is parallelizable and probabilistic. But POW is good enough and practical for our purpose of introducing a nontrivial time delay in being able to predict the transaction ordering in a block, making the final ordering unpredictable and thus nongameable.
(C) At the same time, it is completely deterministic postfacto for any other miner or client to reconstruct the ordering steps and validate the block. Yet the ordering is nondeterministic from the miner POV at the time they are assembling the block. The block proposer could not easily (computationally) predict the final ordering of the transactions because of the effort required in doing POW in the first place. They an not simply try all combinations because trying out a single combination will need them to solve the POW first.
(D) It is reasonable to assume that the DOST mechanism (doing the Keccak hash based on Nonce and contenthash of the transaction) is effectively doing a random permutation of the order of transactions in the block. We can empirically check for this randomness historically.
(E) Gas Usage: Note that it is a very small amount of gas to do the extra DOST ordering work, so it is not much cost overhead. After the DOST ordering, recalculating the state and hashes does add extra work  where optimisation mentioned in Step 6.3) above will be useful.
(F) Block data usage: See choices under Step 6 above. The worst in terms of extra space used is Step (6.2) which still only adds a single 32B hash to the block. Other choices don’t add anything to the block.
How DOST helps mitigate MEV

The proposal brings unpredictability to the final ordering of transactions. Let’s say the miner wanted to frontrun a victim transaction Tv by inserting a new MEV transaction Tn in front of Tv. With DOST ordering, it is equiprobable whether Tv will end up in front of Tn or viceversa. There is no way for the miner to know upfront, only by running POW and finding the block nonce. Likewise for a backrunning transaction. (Note that the miner can try to play probability games  e.g. by inserting two MEV transactions to increase their chances. All of this increases their cost and lowers expected reward so should disincentivize reordering).

Similarly for a sandwich transaction where the outer transactions T1 and T2 are sandwiching a victim transaction Tv, the probability is ⅙ that the exact sequence of transactions T1>Tv>T2 happens in the final DOST ordering
Where DOST doesn’t help
MEV comes in various forms and DOST won’t help in some of them, for example:

This proposal only works on the ordering of transactions that have been already selected by the miner. The miner can still choose to censor (“delete”) a victim transaction and/or insert their own transaction.

The block proposer is free to not publish a block once they find that DOST ordering does not give them a favourable ordering. In that case, they might be forgoing the POW award which was theirs for the taking since they have already solved the POW puzzle for the block. If all miners do this, it could affect the overall effective hashrate of the network and block mining times. Mitigations could potentially include adjusting Difficulty to account for this system behaviour.