owned this note
owned this note
Published
Linked with GitHub
# From Centralized to Distributed Block Builders
MEV and PBS tends towards builder centralization, where a small cartel of builders control what transactions make it into a block. This threatens Ethereum's goals of credible neutrality and decentralization, given transaction censorship is way cheaper in a PBS regime. This motivates the need for distributed (and decentralized) block builders.
We explore how a block builder could be trustlessly distributed among $n$ mutually distrusting builders (who may or may not also be MEV searchers). Following that, we answer whether any practical constructions of such distributed block builders can remain competitive against existing centralized builders.
Recall that proposers passively choose the most profitable block to include in the chain. *It's important that distributed builders remain competitive in regards to building profitable blocks.*
Note that we abstract the block building problem by reducing it to solving a knapsack problem in a distributed fashion among mutually distrusting parties. This is relevant because it means block building is *at least* weakly NP-Hard, which has implications for what kind of tractable mechanisms we can build.
## Privacy is a must
The current standard of originators sending their transactions to a public mempool has resulted in numerous backruns and sandwiches against user transactions (some at users' expense). Orderflow auctions promise to return some of that value back to tx originators, but those cannot be safely implemented without some form of privacy in the auction.
Regardless of whether a user consents to giving their orderflow to searchers or not, it's clear that privacy tech is required to ensure users don't get rekt onchain.
Privacy preserving protocols can be used to facilitate private block building, taking encrypted transactions as inputs and outputting an encrypted block and a plain text `execution_payload_header` (for the proposer to sign). The only caveat being the block contents can only be decrypted *after* the payload header has been signed by the current proposer. If the block contents were to be revealed at any point before that, builders may have their MEV and private orderflow stolen. This implies a protocol that outputs an "encrypted" block that can be decrypted with the proposer's signature.
To reviw, a distributed block builder (DBB) must run an algorithm $\mathcal{F}_{builder}$ that:
1. given a set of $m$ encrypted items, *somehow* computes a knapsack packing of these items
2. encrypts this packing *somehow*
3. returns `(encrypted_block, execution_payload_header)`
If selected by the proposer, the DBB will obtain a signature of the `execution_payload_header` which it can then use to decrypt and publish the`encrypted_block`.
We make no assumptions as to which cryptographic schemes a distributed builder could use to start with. First we will look at what a block builder *needs* to remain competitive, and work backwards from there.
## How Block Builders Compete
Briefly, being a competitive block builder means:
1. Solving knapsack instances as close to optimal as time permits. There is a limited amount of time between blocks, and accounting for network latency means exact algorithms for knapsack problems aren't feasible. Luckily, there is a wealth of literature on approximate knapsack algorithms.
2. Being adaptive enough to play [Timing Games](https://arxiv.org/abs/2305.09032). New transactions are continuously coming in, and being able to reconstruct a better block in the least amount time is in a block builder's best interest.
3. Resistance to [DoS and censorship attacks](https://eprint.iacr.org/2023/956) that target block builders. Current block building methods, like effective gas, are vulnerable to DoS attacks by virtue of greedily ordering and packing transactions. DoS attacks, on top of censoring transactions, also prevent a block builder from earning a higher profit. Finding countermeasures would go a long way to benefit all builders, centralized or not.
Block building firms that also run searcher strategies can also profit from picking up leftover MEV in a block.
## Distributed Building, One Step at a Time
We want a distributed builder to be as adaptive as its centralized counterparts while operating on private inputs. This immediately implies some sort of non-interactive protocol for $\mathcal{F}_{builder}$ since an interactive one tacks on additonal communication complexity, and would require participants to remain online for the duration of block construction.
Furthermore, we like to make as few assumptions about parties involved in block building and would like to retain the current paradigm of originators simply broadcasting their txs before going offline.
An additional cryptographic building block is required to output an "encrypted" block that can be decrypted with a proposer's signature of the corresponding execution payload header. This can be achieved with adaptor signatures, and [witness encryption](https://eprint.iacr.org/2022/1510.pdf) more generally.
Lastly, distributed builders must not censor transactions. Thus some notion of *integrity* is required in any distributed block building scheme. If originators hand off their transactions to a set of builders, how can they be sure some of their transactions aren't being censored (recall no one is supposed to know the block contents until that block gets chosen by the proposer). Builders executing $\mathcal{F}_{builder}$ will know what program does and may also manipulate it to build blocks that censor transactions.
we don't want builders to censor transactions, from that we can either force all builders to work on the same circuit or allow builders to build blocks how they want with an extra zkp check that they're not censoring transactions.
## Putting It All Together
In an earlier section, we covered how builders must compete on 3 fronts. The first front is something all builders must work against, since the knapsack problem is generally NP-hard. Resistance to attacks on builders depend entirely on which heuristic and approximation algorithms they use to solve the knapsack instance, some approaches are more vulnerable than others. A recent paper on [Speculative DoS attacks](https://eprint.iacr.org/2023/956) on block builders shows that the popular effective gas heuristic pioneered by Flashbots is vulnerable to a slew of attacks. Fortunately, this issue affects all builders, centralized and distributed, so we can exclude this later on in our analysis for how DBBs fare against CBBs.
Adaptivity on the other hand is a more complex issue since it is fundamentally at odds with current privacy mechanisms. When playing Timing Games, a block builder wants to be able to recompute a new optimal block as it receives new inputs. Non-interactive MPC and FHE schemes help, but may not be practical at scale and way slower than computation on plaintext. Online algorithms also cannot be transformed into the kind of circuit used by MPC/FHE protocols, meaning even further latency optimizations are unaccesible to private distributed builders. As such, DBBs will lag behind their centralized counterparts, in a game where every latency must be minimized in order to win.
The added privacy requirement of distributed builders is a fundamental impediment to DBBs remaining competitive with CBBs.
## Incentive Compatibility (A Way Forward?)
After making the case that distributed building techniques can't outperform centralized methods, it's clear that the only way distributed building can compete is by attracting more orderflow than centralized builders. Only by doing so, will they have the opportunity to build more profitable blocks.
---
## Notes/Desiderata
- multi-key FHE (or non-interactive MPC) block builder that ensures partial integrity of the circuit (for witness encryption at the end). verifiable FHE already exists, where you can verify an encrypted computation was done on a particular circuit C. can we verify that the circuit C is composed of C_1 * C_2 where C_2 is a witness encryption circuit (C_1 is arbitrary)? this is helpful for ensuring block content privacy while keeping block building algorithms private.
- what is the minimal *thing* required to prevent censorship? is distributing the builder all that's needed? do we *need* to enforce the use of a fixed circuit or can we allow builders to build privately?
- multiplicity works because builders *cannot sidestep* an MPC protocol to build a block. the caveat being that this would require protocol consensus changes. can we obtain a *blinded* proposer signature at the start of the protocol in order to bind the proposer to the protocol? maybe adaptor signatures can help to that effect.
- multiplicity has the benefit of having a cost of censorship $kt$ for all txs with tip $t$.
- is there an *objective* measure of censorship? can we obtain a double signature when censorship is detected.