[2024] Correctly pricing blockspace in a causally parallel world

    title={Correctly pricing blockspace in a causally parallel world}, 
    publisher={20 Squares}, 
    author={Genovese, Fabrizio AND Palombi, Daniele}, 

My highlights:

Parallel execution: you can split a given computation between different threads that happen at the same time.

Incentivize blocks that are ‘as parallel as possible’.

Pair the computation layer with the economic layer via transaction fees.

  • As transaction fees, users specify gas for the ‘worst case scenario’, when the transaction is not parallelizable at all;
  • At block simulation, a certain degree of parallelization is established as a function of the block;
  • The users receive a discount on their fee based on this;
  • The block builder instead receives the whole value of the user transaction, maybe plus a small bonus;
  • The delta between what the user pays and what the builder receives is simply created, as block rewards are created now.

It may require to sequentially simulate the block to calculate the improvement coefficient.
Vast literature on topics such as cloud infrastructure pricing that we can borrow from

You do not need parallelized execution layers to run parallelized MEV auctions. “If state is disjoint, auctions can be run in parallel.” Tarun.

Causality: what does it mean for different events to be related. Characterize in a way that is completely independent from ‘time’.

Category: where only sequential composition is possible.

Monoidal category: ‘two processes modifying non overlapping threads have no causal relation’. Generated by hypergraphs, the underlying topologies of Petri nets.

You can fire t and u independently, they are causally independent. you can decide if you want v to use the state that was already in p2 or if you want it to use the one generated by t.

In the (currently) non-parallel EVM we could split the block not only horizontally - as in the top of the block/bottom of the block - but also vertically, allowing for multiple transactions to be top of the block and by running multiple auctions in parallel.

This split only exists at ‘MEV time’ and the block will be fully sequentialized at ‘executon time’.

You don’t want block builders to cherry pick transactions in a way that reduces the usage of computational parallelism.

Teleportation in Petri nets: state borrowing and error correction.
The transition ν needs a state that hasn’t been created yet. To proceed, it creates this state together with a ‘debt’ (represented by the red token). Now ν and τ can be computed in parallel. The consistency of the whole system is restored when μ is fired, providing the state ν requested and ‘annihilating’ the debt.