Relay Networks and Fee Markets in Eth 2.0
===

This post aims to summarize the research efforts around phase 2 of Ethereum 2.0, with specific focus on the relay network and fee market challenge. A number of proposals, each with varying trade-offs, have been made across various platforms, so this should serve as a reasonably comprehensive compilation to allow new researchers to get up to speed.

# Background

Before diving into relay networks, let's first take a detour to discuss one of the primary bottlenecks (if not _the_ primary bottleneck) on Ethereum since its inception: **state**.

Ethereum's state is the set of account balances, contract code, and contract storage. (In Bitcoin, state is the UTXO set.) Whenever transactions are executed, the state---[a ~45 GB data set in uncompressed form](https://twitter.com/peter_szilagyi/status/1166633058348556288)---must be both read from and written to. While there were [earlier concerns around the fundamental unscalable nature of Ethereum's computational model](https://old.reddit.com/r/Bitcoin/comments/4pdx6k/comparison_between_bitcoin_and_ethereums/d4k6n7d/), it turns out that these state accesses are by far the most expensive part of transaction execution, and indeed [disk I/O is the limiting factor for running an Ethereum full node](https://twitter.com/ercwl/status/1164200569474621440).

Note that, in order to guarantee being able to execute an arbitrary transaction in this _stateful paradigm_, a full node needs to keep the entire state in an accessible location (such as in-memory, or on swap space). While this is borderline acceptable in the single-blockchain case, it would not work with sharding with shuffled committees. If each time a validator was assigned to a new shard, they had to sync the entire state of that shard, the system would be equivalent to just having a single chain with blocks of size `shard_block_size * shard_count`. Enter: stateless clients.

## Sharding and the Stateless Client

The [_stateless client paradigm_]((https://ethresear.ch/t/the-stateless-client-concept/172)) (originally called "[storageless](https://bitcointalk.org/index.php?topic=314467.msg3371194#msg3371194)") vastly reduces the burden of executing transaction by enabling validators to only store a compressed representation of a chain's state, commonly referred to as an _accumulator_. Typically accumulators are constant-sized (_e.g._, a Merkle root of the state), though they may also be [logarithmically](https://eprint.iacr.org/2019/611)-sized.

The essence of the stateless client model is that each transaction includes a _witness_ against the current accumulator that contains all the required information to execute that transaction. In the case of Ethereum, with a Merkle accumulator like a [Sparse Merkle Tree](https://ethresear.ch/t/optimizing-sparse-merkle-trees/3751) (SMT), this would be Merkle branches to the state elements touched by the transaction during its execution.

Among other applications, this process can be used to greatly speed up initial sync times of Ethereum nodes, as seen with [Beam Sync]((https://medium.com/@jason.carver/intro-to-beam-sync-a0fd168be14a)).

_Side note: cryptographic accumulators, such as RSA accumulators, have better properties than Merkle accumulators, but rely on either a trusted setup or cutting-edge, un-audited cryptography. As such, it will take a while for them to be safely usable in production systems._

There is one challenge with stateless clients however: when using Merkle accumulators, witnesses become outdated after each atomic bundle of execution. If the execution model is that each transaction includes a witness and that transactions are executed in order, then the original witness of each subsequent transaction would become outdated and need to be updated. Fortunately, updating witnesses for Merkle accumulators involves [zero hashing overhead](https://twitter.com/tdryja/status/1136006419944222721). If the execution model is that witnesses are attached to a "package" of transactions, then individual witnesses don't need to be updated, but rather, _merged_ into a _[multiproof](https://www.wealdtech.com/articles/understanding-sparse-merkle-multiproofs/)_.

If we assume that all users [run full nodes, and can keep their witnesses to state elements up-to-date](https://twitter.com/tdryja/status/1136013713591455745), then the system mostly works out-of-the-box. However, in a sharded context this may be an unreasonable assumption, as this would require users to fully validate each shard their have state in; as mentioned above, this is exactly what we don't want, as it would be equivalent to just having a single chain with a larger block size.

To alleviate this issue, _relayers_ (also referred to as _state providers_) are introduced. Relayers are responsible for providing witnesses to users, and are paid for this service. Unlike users, they can limit their activities to a single shard trivially. As it would be unreasonable for relayers to know in advance what state elements their should keep witnesses for up-to-date, they must instead store state (hence, state provider), so as to be able to provide witnesses on the fly.

Introducing relayers, however, also introduces a whole host of other complex challenges, and remains one of the more significant open research questions for a full deployment of Eth 2.0. First, if not balanced properly, [block proposers (_i.e._, validators) will be incentivized to be relayers]((https://ethresear.ch/t/exploring-the-proposer-collator-split/1632)), with associated costs potentially being in large part inaccessible to the average user. Additionally, a way of collecting appropriate fee payments from both users and relayers (_i.e._, the fee market) without also introducing significant overhead isn't immediately apparent. In other words, while _validating_ stateless transactions is easy, _producing_ the necessary witnesses is non-trivial.

# Relay Network and Fee Market Proposals

The [phase 2 design space](https://www.youtube.com/watch?v=RW7K3JQOZOg&t=2090) is large and has seen a number of different proposals for handling execution. Each proposal also brings with it a potentially different way of paying fees, along with a different mechanism for transactions to be relayed from user to block proposer. This section will attempt to provide a concise but nonetheless comprehensive summary of the different proposals and analyze the behavior of the relay network and fee market for each.

## Collator-Proposer (Retired)

[Early proposals](https://ethresear.ch/t/sharding-phase-1-spec-retired/1407) that could lead to phase 2 saw the separation of shard chain block production into three distinct set of actors: _proposers_, _collators_, and _executors_. Proposers would be responsible for collecting transactions into blocks (collations), proposers would be responsible for proposing a particular collation extend the canonical \[shard\] chain, and finally executors would commit to a new state root based on the proposed collation.

This proposal was never fully fleshed out; as such, research into fee payment mechanisms was not conducted. It was retired as, among other things, the incentives of the system [encouraged actors to be proposers, collators, and executors at the same time in order to maximize their rewards](https://ethresear.ch/t/exploring-the-proposer-collator-split/1632).

## Phase 1 and Done

The turn of the year 2018 saw the rise of using [scalable blockchains as data availability layers](https://www.youtube.com/watch?v=mOm47gBMfg8), with a base layer providing high-throughput global data availability for [second-layer execution engines](https://vitalik.ca/general/2019/08/28/hybrid_layer_2.html), such as [zk-rollups](https://ethresear.ch/t/on-chain-scaling-to-potentially-500-tx-sec-through-mass-tx-validation/3477) (and later [optimistic rollups](https://ethresear.ch/t/minimal-viable-merged-consensus/5617)). Unfortunately, initial suggestions that [Phase 1](https://docs.ethhub.io/ethereum-roadmap/ethereum-2.0/eth-2.0-phases/) (sharding, with data blobs sans any execution) be useful as a data availability layer for _e.g._, Eth 1.x while waiting for Phase 2 to be deployed, turned out to fall short; a separate execution layer can't actually access the data (giving Eth 1.x oracle access to _all_ shard data would be equivalent to it having very large data-only extension blocks), and bridging it over would be no different than simply including it in the execution layer in the first place!

This was highlighted by [Casey Detrio](https://twitter.com/cdetrio/status/1114732776824160256) in his seminal post [Phase One and Done: eth2 as a data availability engine](https://ethresear.ch/t/phase-one-and-done-eth2-as-a-data-availability-engine/5269). The post notes that shards in phase 1 can be used for bridged data availability _without_ state sharding, by adding only minimal execution sharding. In this scheme, shards can 1) authenticate data (_i.e._, insert a list of transactions into an authenticated data structure such as a Merkle tree) and 2) perform simple stateless execution, such as verifying a zero-knowledge proof against authenticated data.

Defining the programs that would be used to process the data blobs is done by uploading _contracts_ (which would later become "precompiles" and then "execution environments") to the beacon chain. Contracts would presumably be client-interpretable bytecode, the exact choice of which is orthogonal to the whole of the proposal.

This "phase one and done" mostly sidestepped the fee payment challenge, as it was a challenge with previous proposals and remained a challenge for subsequent proposals, instead choosing to focus on laying out the minimal changes needed to make Eth 2.0 sustainably useful in as short a timeframe as possible. There was one suggestion in passing to [pay fees using a contract on Eth 1.x](https://ethresear.ch/t/phase-one-and-done-eth2-as-a-data-availability-engine/5269/12) (_i.e._, have the rollup contract pay shard block proposers on Eth 1.x for including a data blob on Eth 2.0 with bridged processed data availability). While certainly doable, this would inextricably tie Eth 2.0's usability to Eth 1.x's survival in perpetuity.

## Phase 2 Proposal 1

Following Detrio's "phase one and done" proposal, Vitalik Buterin revealed a new concrete proposal for phase 2 in his [phase 2 proposal 1](https://ethresear.ch/t/a-layer-1-minimizing-phase-2-state-execution-proposal/5397). In this proposal, _execution scripts_ (initially called "beacon chain contracts") live on the beacon chain. Ether never leaves the beacon chain, instead being deposited into execution scripts (in order to pay fees). Each shard has its own completely independent state and execution.

Note that contrary to what their name would suggest, execution scripts define the _virtual machine_ with which to execute transactions, and are not smart contracts as we've seen deployed on Ethereum to date. The data model and opcodes must be fully defined by the execution script in some client-interpretable, metered, code (_e.g._, ewasm).

For the purposes of fee payments, each execution script is essentially a layer-2 system, with their own internal fee-paying mechanisms that shard validators don't "understand." This obliviousness is Actually a Feature^TM, as _requiring_ shard validators to be able to parse and account for a different fee mechanism---and potentially a different currency---would lead to enormous implementation and economic complexity along with exploitation vectors, to the point of being unusable. In large part, the same arguments against economic abstraction hold against execution script-specific fees.

As validators can't collect fees from _within_ an execution script, they need to be paid externally to it. This is accomplished with a special (_i.e._, enshrined) execution script, in which anyone may post a transaction to the effect of "if this data blob for this execution script on this shard at this slot is included, I'll send the includer a payment." These actors are _relayers_ ([originally called "operators"](https://ethresear.ch/t/an-optimistic-generic-gas-market-executor-for-phase-2/5429/2)), and are responsible for collecting user-transactions for the non-enshrined execution scripts, each paying them an execution-script-specific fee, and paying shard block proposers (producers) for including this blob through the enshrined execution script.

An excellent summary of phase 2 proposals up to this point was compiled William Villanueva in his post: [A Journey Through Phase 2 of Ethereum 2.0](https://medium.com/@william.j.villanueva/a-journey-through-phase-2-of-ethereum-2-0-c7a2397a36cb).

## Phase 2 Proposal 2

Drawing inspiration by Detrio's earlier work, Buterin's [second proposal for phase 2](https://notes.ethereum.org/@vbuterin/Bkoaj4xpN) [further simplifies](https://ethresear.ch/t/proposed-further-simplifications-abstraction-for-phase-2/5445) the first proposal by removing state from shards and instead using the beacon chain to keep track of shard-specific, _execution environment_ (EE, previously execution script)-specific state roots.

This has the benefit of allowing EEs to specify their own accumulator format (_e.g._, a Sparse Merkle Tree, a red-black tree, a cryptographic accumulator, etc.), rather than needing to enshrine a specific accumulator format as with previous proposals.

The general transaction flow would now look like this: users craft transactions and send them to relayers. Relayers add witnesses (in the form of Merkle branches, if a Merkle accumulator is used) in exchange for fees from users in an unspecified manner, and package multiple transactions together. Relayers would send these packages to block proposers, paying them an in-protocol fee for including this package in the next \[shard\] block. This in-protocol fee, as with proposal 1, is paid through an enshrined EE that all validators are required to understand.

While this scheme is certainly a step up in terms of ease of being a validator, as only minimal shard state is required, the lack of an in-protocol fee payment mechanism from users to relayers does not alleviate the relay network issue. Firstly, [using an out-of-band payment scheme reduces users privacy](https://ethresear.ch/t/layer-2-state-schemes/5691/1). Second, it is not obvious how to create an entirely off-chain system (that does not rely on another, external, blockchain) that guarantees that users receive appropriate witnesses and relayers get paid for providing the required witnesses, atomically. Third, the potentially high friction of out-of-band payments and high computational requirements of being a relayer (as relayers must have all state for the EEs and shards they wish to serve, in order to be able to generate witnesses) can be a centralization concern---with only a few "gatekeeper" relayers between the users and the Eth 2.0 network in the worst case.

## Bring Back the Mempool

Rather than having relayers pay block proposers conditionally, which would require [non-trivial double-commit-reveals schemes to ensure atomicity](https://ethresear.ch/t/optimised-proposal-commitment-scheme/1314), a new proposal emerged by Buterin: [one fee market EE to rule them all](https://ethresear.ch/t/one-fee-market-ee-to-rule-them-all/5608). In this proposal, _EEs themselves would have balances_. When executing a package of user-transactions, the EE will output a receipt, which can then later be consumed by an enshrined fee-payment EE to transfer Ether balance _from the EE_ to the block proposer. The fee-paying EE would thus be able to "lookback" and previous receipts to process fee payments. Topping up the balance of the EE would presumably be the responsibility of the relayers (or some otherwise interested party).

This proposal has the benefit of not requiring a complex scheme to negotiate payments between relayers and block proposers. However it still does not address how users interact with relayers, instead opting to suggest [payment channels be used](https://ethresear.ch/t/one-fee-market-ee-to-rule-them-all/5608/5).

Building upon the original proposal, Villanueva then suggested [bringing back the mempool](https://ethresear.ch/t/state-providers-relayers-bring-back-the-mempool/5647). Here, relayers take on a reduced role as _state providers_, being responsible only for providing witnesses but not packaging user-transactions. Block proposers (or, more generally, shard validators) maintain a mempool and _merge_ witnesses to create their own packages. Given that each EE could use a different accumulator format, the EE will need to specify a `merge` method that block proposers can use to merge two or more witnesses together, _e.g._, multi Merkle branches into a Merkle multi-proof.

As state providers only need to provide witnesses (usually in the form of Merkle branches), there is a group of actors that are perfectly suited to provide this service already: _light client servers_. By encouraging more light client servers through better tooling and reduced costs, this does a long way towards preserving permissionlessness. However, the use of high-friction payment channels for users to pay state providers remained a pain point.

## Alternate Phase 2 Architecture

More recently, Buterin published an [alternate phase 2 architecture proposal](https://notes.ethereum.org/YNnC-fakRxixbMCTEnNDXQ), which makes shard completely stateless. The key different here is the additional of a full, stateful, expressive, state transition engine (_e.g._, the EVM) in the beacon chain. This engine acts as a "scheduler," keeping track of EE state roots. The scheduler also allows for multi-shard execution: it can inspect shards and slots in a deterministic order, ensuring that multiple transactions across multiple shards to the same EE are executed correctly (by weaving pre- and post-state roots, ignoring any shard blocks that are invalid or out of order).

The fee payment mechanism for this proposal is largely unchanged compared to the previous one, though a fee-paying EE is not needed as the scheduler has enough expressivity to handle managing EE balances and consuming receipts natively.

## Shard Chain Simplification Proposal

At DevCon 5, Buterin unveiled a [major refactoring](https://notes.ethereum.org/@vbuterin/HkiULaluS) of the Eth 2.0 sharding architecture, drawing inspiration from [Near's Nightshade "shard chunk" design](https://nearprotocol.com/downloads/Nightshade.pdf). In this new proposal, rather than each shard chain maintaining its own separate fork choice rule, with faster blocks and crosslinks being formed in a staggered manner, shard blocks are produced in lockstep with beacon chain block, and all shards are cross-linked every beacon block (in the normal case). To accommodate this increased number of shard crosslinks over the previous architecture, the number of shards was decreased to 64 from 1024 and the throughput of each shard was increased somewhat to keep the overall system throughput close to the same.

Fee markets are [made simpler](https://notes.ethereum.org/@vbuterin/HkiULaluS#Main-benefit-easier-fee-markets) by virtue of a fundamental change in mindset: thanks to the vastly reduced shard count, cross-shard communication is simpler, and it's no longer an issue for users to hold ether in each shard to pay transaction fees directly to block proposers (again through the scheme of EEs outputting receipts). By removing one half of the fee market issue, only the relayer network (_i.e._, state provider) challenge remains.

# Desiderata

A non-exhaustive list of desireable properties of a relayer network/fee market for Eth 2.0 is discussed here.

- Both users, relayers, and block proposers should be appropriately paid/serviced. Users should receive witnesses they pay for, relayers should be paid for providing witnesses, and block proposers should be paid for including transactions in a block. The payment from relayers (or, indirectly, EEs) to block proposers can be handled [in-protocol](https://ethresear.ch/t/optimised-proposal-commitment-scheme/1314), but the payments from users for both witnesses and block inclusion are not so straightforward.
- The user payment scheme should be low-friction, to allow them to easily switch relayers. Payment channels rooted in an external blockchain, with pre-collateralization and liveness requirements, are anything but. Ideally this should be handled in-protocol.
- Tying in to the previous point, it should be difficult to enforce a blacklist on users. Unfortunately, due to the fact that witnesses are effectively an implicit access list, this may be somewhat unavoidable.
- Validators should not need to "understand" how fees are paid internally to every EE, as that would be exceedingly complex to both implement and build an efficient market around.
- Users should not have to run a full node (_e.g._, to maintain their witnesses themselves). We want a protocol that is light-client friendly.
- Last but not least, Denial-of-Service (DoS) resistance is important. Depending on how witnesses are merged/refreshed, it may be possible to DoS validators. Care must be taken so as to not allow such an exploit.

# Conclusion

Research around a relayer network and fee market system that allows for a good user/light node experience while simultaneously not placing undue burden on validators, all while remaining as permissionless as possible, has gone through a number of design iterations over the past year. Looking forward, we should expect additional phase 2 proposals that further refine and improve this aspect of the Eth 2.0 system.