Validators in permissionless, large-scale blockchains (, Ethereum) are typically payoff-maximizing, rational actors. Ethereum relies on in-protocol incentives, like rewards for validators delivering correct and timely votes, to induce honest behavior and secure the blockchain. However, external incentives, such as the block proposer's opportunity to capture maximal extractable value (MEV), may tempt validators to deviate from honest protocol participation.

We show a series of commitment attacks on LMD GHOST, a core part of Ethereum's consensus mechanism. We demonstrate how a single adversarial block proposer can orchestrate long-range chain reorganizations by manipulating Ethereum's reward system for timely votes. These attacks disrupt the intended balance of power between proposers and voters: by leveraging credible threats, the adversarial proposer can coerce voters from previous slots into supporting blocks that conflict with the honest chain, enabling a chain reorganization at no cost to the adversary.
In response, we introduce a novel reward mechanism that restores the voters' role as a check against proposer power. Our proposed mitigation is fairer and more decentralized – not only in the context of these attacks – but also practical for implementation in Ethereum.

§ INTRODUCTION

§.§ Ethereum Consensus Security

Blockchains have emerged as one of the most prominent applications of distributed consensus, a field over $40$ years old.
The largest proof-of-stake (PoS) blockchain by market capitalization is Ethereum, secured by a PoS Byzantine fault tolerant (BFT) consensus protocol (Gasper [31]).
Ethereum's consensus is run by a set of validators, which output two ledgers: the available ledger and the finalized ledger.
Requirements for these ledgers were formally captured by the ebb-and-flow property [52]: (i) The available ledger must remain secure (, safe and live) under a synchronous network despite unexpected and large drops in the number of active validators (this is also known as the sleepy network model [56], or dynamic availability [25]).
(ii) The finalized ledger must satisfy accountable safety[Namely, if safety is ever violated, the honest validators can identify the adversarial parties responsible for the violation (Appendix <ref>).] under a partially synchronous network and must stay live if sufficiently many validators are active.
Finally, (iii) the finalized ledger must always be a prefix of the available ledger.
To achieve the ebb-and-flow property, Ethereum employs two sub-protocols: LMD GHOST (Latest Message Driven
Greedy Heaviest Observed Sub-Tree) that outputs a canonical chain as the available ledger, and Casper FFG (the Friendly Finality Gadget) that checkpoints blocks on this canonical chain.
These checkpointed blocks constitute the finalized ledger.

Ethereum's consensus has been subjected to much scrutiny, as evidenced by attacks on the security of both LMD GHOST [52, 58, 49, 51, 53] and Casper FFG [47, 48] as well as various protocol patches in response to the attacks ( [65] for a comprehensive history).
Without the safety of the canonical chain (available ledger), Casper FFG would fail to checkpoint blocks, causing the finalized ledger to stall indefinitely [32].
Similarly, without the liveness of the canonical chain, Casper FFG cannot ensure the liveness of the finalized ledger.
Thus, the security of LMD GHOST that outputs the canonical chain is crucial for the security of both ledgers and Ethereum consensus overall.

Many Ethereum users today act on time-sensitive transactions as soon as they enter the canonical chain, without waiting the $12.8$ minutes required for their finalization by Casper FFG, or any other notion of confirmation by LMD GHOST.

This makes them susceptible to instability on the chain tip.
Making matters worse, validators are incentivized to reorganize (reorg) the blocks at the end of the canonical chain by proposing new blocks on top of the older blocks rather than the chain tip.
The main reason for this is the magnitude of maximal extractable value (MEV) [18], , the payoff of a block proposer due to its control over the inclusion, exclusion, and ordering of transactions (, the proposer can frontrun arbitrage transactions in trades, backrun liquidation events to buy the liquidated assets) [35].
Once the blocks at the chain tip are replaced (, reorged), the new blocks can re-include the transactions of the reorged blocks, and capture the associated MEV.
Therefore, besides security, preventing reorgs emerged as a goal of Ethereum consensus, leading to new reorg-resilient proposals to replace LMD GHOST (, Goldfish [36], RLMD-GHOST [37]).

§.§ Incentives in Ethereum

LMD GHOST proceeds in slots of $12$ seconds, each with a unique block proposer (hereafter called the leader) asked to propose a new block extending the tip of the canonical chain.
Each slot is also assigned a committee of attestors that are asked to send a head vote for the block at the tip of the canonical chain in their view[The committee of each slot consists of different validators within an Ethereum epoch.].
To deter future leaders from reorging blocks, these attestors must be incentivized to vote for the proposal at the canonical chain tip before the next slot; so that the proposed block gathers enough support against any future competitor.
This makes incentivizing the timeliness of the head votes crucial for mitigating reorg attempts and achieving a notion of reorg-resilience in the presence of payoff-maximizing (, rational) validators, which might otherwise find it profitable to delay their votes or vote for old blocks.
Thus, Ethereum uses a head vote reward mechanism: a vote sent at a slot $t$ is rewarded on the canonical chain only if the vote is included in some block $B$ proposed at slot $t+1$ (, timely) and if the vote is for a block on the canonical chain (, correct).

Ethereum also implements an inclusion reward mechanism: a slot $t+1$ leader is rewarded for including the (timely) slot $t$ votes in its block.
Despite the rewards for honest execution, MEV reorgs remain a strong force for future leaders to explore ways to incentivize previous slots' attestors to not vote for their slot's block.

The tension between the opposing incentives has so far resisted any resolution in the form of a security proof considering rational validators, not only in LMD GHOST but also in other proposed consensus protocols.

§.§ Commitment Attacks on LMD GHOST

In this work, we present a series of attacks on the reorg-resilience and security of the latest version of LMD GHOST [65].
Their scope ranges from reorging a single block to violating the security of LMD GHOST (, the available ledger), which in turn causes a liveness violation for the finalized ledger.
The attacks exploit the head vote reward mechanism in the presence of rational attestors.
Recall that the attestor sending a slot $t$ head vote is rewarded only if the vote is included in a block of slot $t+1$.

The core idea behind our attacks is that an adversarial leader can abuse its power over the head vote reward of the previous slot's attestors to incentivize them to vote for blocks favorable to the adversary.

The attacks do not require the adversary to own a large share of the stake, control the communication network or any validator, or bribe rational validators.
The adversarial strategy involves only committing to a credible threat, which the attestors must be aware of to react rationally (Section <ref> for different commitment methods to ensure credibility).
In today's Ethereum, over 90% of the validators run an out-of-protocol software, `mev boost', in which block proposers outsource the building of their block content to specialized third parties [63, 20].
It is easily imaginable to extend this widely distributed software to also facilitate the game communication between the adversarial leaders and attestors in our attacks.
Then, as long as the majority of the attestors are rational (and the remaining ones can be honest, altruistic), the attacks are guaranteed to be successful.

§.§.§  Simple attack (Section <ref>, Figs. <ref> and <ref>)

Suppose the leader of some slot $t+1$ is adversarial and aims

to reorg the block $B$ proposed at slot $t$.
Before slot $t$ starts, it informs the slot $t$ attestors that it is the leader of slot $t+1$,

and asks them to

vote for the parent of block $B$ instead of $B$ itself.
The adversary commits to including in its block only the votes that comply with its instruction.
The slot $t$ attestors are incentivized to comply as otherwise, they do not receive the head vote reward[Head vote reward constitutes $1/4$ of the total attestation reward [9], which could be the difference between making a profit vs. loss while validating new blocks.].
We show

a Nash equilibrium in which the attack is successful and the adversary receives the attestation inclusion reward, given both non-colluding (solo) validators and staking pools of colluding validators.

Unsuccessful attack

Successful attack

The simple game in the presence of non-colluding (solo) validators. As the adversary is committed to excluding the non-compliant votes, even when the attack is unsuccessful, non-compliant votes are not rewarded.

§.§.§  Extended attack (Section <ref>, Fig. <ref>)

In the extended attack, the adversary reorgs a sequence of consecutive blocks

with empty (`transaction-less') blocks.[On a funny note, one can think of the extended attack as the simple attack combined with the $5$ pirate puzzle question [14].]

Suppose the leader of some slot $t+p+1$ is adversarial and aims to reorg the $p$ blocks proposed at slots $t-p+1, \ldots, t$ using a fork of $p$ empty blocks proposed at slots $t+1, \ldots, t+p$.

To give insight, we describe a sketch, where $p=2$, $t=0$, and the adversary aims to reorg the two consecutive blocks $B_{-1}$ and $B_{0}$ from slots $-1$ and $0$

with a fork of empty blocks $B_1$ and $B_2$ proposed on top of block $B_{-2}$.

The extended attack with $p=2$. $B_i$ and $V_i$ represent the block and attestations proposed in slot $i$, respectively. The attestations and blocks in green are compliant.

Using its block $B_{3}$, the adversary can incentivize not only the slot $2$ attestors but also the leaders and attestors of previous slots to follow its instructions; since the slot $2$ votes affect the confirmation status of the slot $2$ block,

which in turn influences the head vote rewards of the slot $1$ attestors.

Formally, the adversary devises a set of instructions for the leaders and attestors of slots $1$ and $2$ to propose and vote for a fork of empty blocks extending $B_{-2}$ rather than the tip $B_{0}$ of the canonical chain.
Such blocks and votes that comply with the adversary's instructions are called compliant.
The adversary stipulates the slot $1$ leader to propose an empty block $B_{1}$ on top of $B_{-2}$, and the slot $1$ attestors to either vote for $B_{1}$ if it is empty and extends $B_{-2}$, or to vote for $B_{-1}$ otherwise.
Now, if $B_{1}$ is compliant and gathers sufficiently many votes, the adversary demands the slot $2$ leader to propose an empty block $B_{2}$, including the compliant slot $1$ votes, on top of $B_{1}$.
It then asks the slot $2$ attestors to either vote for $B_{2}$ if it is empty, includes the compliant slot $1$ votes and extends $B_{1}$, or to vote for $B_{1}$ otherwise (if $B_{1}$ is compliant).

Finally, the adversary commits to including only the compliant slot $2$ votes in its block $B_{3}$.
Note that no rational attestor is obliged to comply with the instructions apriori, but as we show next, they are all incentivized to do so.

Due to the adversary's commitment, to receive head vote rewards, the slot $2$ attestors vote for $B_{2}$ only if $B_{2}$ is compliant, , is empty and contains only the compliant slot $1$ votes.
Therefore, to ensure that $B_{2}$ receives enough votes and thus cannot be reorged by $B_{3}$, the slot $2$ leader proposes a compliant block $B_{2}$, thus receiving the vote inclusion reward.

Since a compliant $B_{2}$ includes only the compliant slot $1$ votes, to receive head vote rewards, the slot $1$ attestors vote for $B_{1}$ only if $B_{1}$ is compliant, , is empty and extends $B_{-2}$.
Then, to ensure that $B_{1}$ receives enough votes and thus cannot be reorged by $B_{2}$ or $B_{3}$, the slot $1$ leader proposes a compliant block $B_{1}$.
Consequently, all slot $1$ and $2$ leaders and attestors vote for a chain of empty blocks ($B_{1}$ and $B_{2}$) conflicting with $B_{-1}$ and $B_{0}$, enabling the adversary to reorg $B_{-1}$ and $B_{0}$.

As shown in Section <ref>, the extended attack results in a subgame perfect Nash equilibrium with arbitrarily long reorgs.

§.§.§  Selfish mining-inspired attack (Appendix <ref>, Fig. <ref>)

The extended attack fails in the presence of a staking pool that controls attestors in every slot and worries more about losing the head vote rewards for its votes within the blocks $B_{-1}$ and $B_0$ than for its slot $2$ votes that might not be included in $B_3$.

Therefore, we present a new, `selfish mining-inspired' attack, where the staking pool is incentivized to follow the adversary's instructions.
Although the attack cannot violate safety or liveness permanently when the adversary's stake is $<1/3$, over short periods with more adversarial slots than honest,

it enables the reorg of non-adversarial blocks as in the original selfish-mining attack.
Thus, it is an attack on reorg-resilience.

We consider a colluding set of validators (, a staking pool) that controls attestors in every slot.
Indeed, a large staking pool will control a share of attestors close to their share of the total stake in any given slot.
Akin to the selfish-mining attack, this attack succeeds in a slot range $T$, where the number of adversarial slots

is greater than or equal to the number of non-adversarial slots.
Let $s_i$ and $B^\mathcal{A}_i$, $i \in \{1, \ldots, N_\mathcal{A}\}$, denote the $i^\text{th}$ adversarial slot and its corresponding adversarial block in $T$, respectively. Let $B$ denote the canonical chain tip prior to the slots in $T$.
Before the start of slot range $T$, the adversary sends a proof asserting its leadership in the adversarial slots to the attestors of the slots ($s_i-1$) preceding the adversarial ones.

It also requests them to withhold their votes

until the end of $T$,
when the slot $s_i-1$, $i \in \{1, \ldots, N_\mathcal{A}\}$, attestors should broadcast votes for block $B_{i-1}$, which will be published by the adversary at the end of $T$.
The adversary pledges to exclude the non-compliant slot $s_i-1$ votes from its slot $s_i$ blocks.

At the end of $T$, the adversary generates an adversarial fork consisting of blocks $\{B_i| \, i \in \{1, \ldots, N_\mathcal{A}\}\}$ on top of block $B$.

The attestors of slots $s_i-1$ for $i \in \{1, \ldots, N_\mathcal{A}\}$ are incentivized to publish compliant votes as non-compliant votes lose the head vote reward.
Since the number of adversarial slots in $T$ is greater than or equal to the number of non-adversarial slots, given rational validators, the adversarial fork extending block $B$ gains greater or equal weight at the end of $T$ compared to the honest fork extending block $B$.
This implies an equilibrium, where the honest fork extending block $B$ gets reorged by the adversarial fork.

The selfish mining-inspired attack, where $|T|-1 = p = 5$ and $N_\mathcal{A}=N_\mathcal{NA}=3$. The upper and the lower forks are non-adversarial and adversarial, respectively. The attestors in slots 1, 4, and 5 are incentivized to vote for the adversarial fork as their subsequent slots are adversarial. At the start of slot $6$, the weights of the non-adversarial and adversarial forks are $2W$ and $2W+\Wp$, respectively, resulting in the adversarial fork winning.

In Appendix <ref>, we analyze the impact of potential future changes in the Ethereum protocol (, block-slot voting [3], secret leader election [10], proposer-builder separation [8] and single-slot finality [13]) on the three attacks above, and observe that none of these modifications can mitigate them.
As our attacks exploit the payoff-maximizing nature of the rational validators to incentivize protocol deviations, they also work on PBFT-style protocols that are secure in the honest-adversary paradigm, under rational validators.

§.§ A New Reward Mechanism:

The reward mechanism. $V^t_i$ represents the $i^\text{th}$ head vote (by the $i^\text{th}$ attestor) in slot $t$. Vote $V^t_1$ has received signatures from more than half of the slot $t+1$ attestors, , it is timely. Vote $V^t_3$ has not received any signature from slot $t+1$ attestors and is not timely.

The attacks above are due to the monopoly power of a slot leader over which votes get included and subsequently rewarded by the canonical chain.

As is usual in distributed systems, the protocol can be reinforced against the leaders' abuse of power by decentralizing the reward mechanism [43].
We thus propose a new, decentralized head vote reward mechanism for LMD GHOST (Fig. <ref>, Section <ref>) called , reflecting the directed acyclic graph (DAG) topology of vote connections.
replaces the leader of slot $t+1$ with the slot $t+1$'s committee of attestors as the beacon of truth to determine whether slot $t$ votes were timely.
It requires each slot $t+1$ attestor to sign the slot $t$ votes in its view.
Then, an attestor is rewarded for its slot $t$ vote if there are sufficiently many slot $t+1$ attestors that have signed the

vote, whenever these signatures are included on-chain[The inclusion reward mechanism used by Ethereum can be extended to incentivize the inclusion of the slot $t+1$ attestors' signatures on the slot $t$ votes.].
The adversary must now control a large fraction of the attestor committees to affect the head vote rewards.

not only mitigates the attacks above,

but also

guarantees a fairer reward distribution.
Currently, if a slot leader does not propose any block, the attestors of the previous slot lose their head vote rewards,

which is particularly discouraging for solo validators selected as attestors once per epoch.
The new mechanism protects the attestors' rewards even when the leader or a minority of attestors are offline.

We estimate the overhead of a practical version of our solution that is backward compatible with the Ethereum infrastructure on a consumer laptop (Sections <ref> and <ref>).

In the practical version, only a subset of the slot $t+1$ attestors, referred to as aggregators, become responsible for signing the slot $t$ votes.
Under synchrony, these signatures can be quickly aggregated into a single one, resulting in only a slight increase in the required block space.

§ RELATED WORK

§.§ Attacks on Ethereum Consensus

The LMD GHOST protocol as introduced in [31] lacks security due to the balancing attacks [52, 58, 49, 51], where the adversary causes two equally-sized sets of honest validators to vote for conflicting blocks indefinitely under synchrony by carefully timing the release of a few withheld adversarial votes.
The protocol was subsequently changed to bestow the latest block proposals with a temporary extra weight called the proposer boost, so as to push the validators towards the latest proposal [65].
However, proposer-boosting failed to prevent a resurgence of the balancing attack due to a feature of the LMD rule that requires each validator to consider only the first slot $t$ vote it receives from an equivocating validator.
The absence of this rule in turn enabled a so-called avalanche attack that showed the incompatibility of the proof-of-stake Sybil resistance mechanism with the GHOST fork-choice rule [53].
Finally, these attacks were addressed with another patch called equivocation discounting that stipulates the removal of equivocating votes for the same slot but different blocks from the views of the validators [65].
A confirmation rule and the associated security proof for LMD GHOST are provided in [24].

In our work, we investigate the effect of the reward mechanism on the protocol's security in the presence of rational validators.
Our attacks do not require the adversary to violate any slashing condition or control more than a single block proposer, making the bar for the attack much lower than the earlier consensus attacks.
In fact, when the attack is successful, the adversary does not even have to violate the protocol.

§.§ Timing Games

Our model of validators shares some similarities with the honest-but-rational validators of [59, 54].
These validators do not strictly violate the protocol rules but delay their blocks to the maximum extent possible to capture more MEV, while ensuring their timely inclusion in the canonical chain.
The advantage of well-connected validators and the resulting higher profit in MEV has serious potential to hurt fairness and decentralization by incentivizing collusions for more connectivity.
Like these works, our model also assumes rational, payoff-maximizing validators, and just like delaying blocks, protocol deviations by our rational validators are not accountably identifiable or slashable.
However, unlike honest-but-rational proposers, our validators can explicitly disobey the protocol rules that are not enforceable via slashing, , by refusing to propose on the tip of the canonical LMD GHOST chain.

§.§ Game Theory and Consensus Protocols

Behavior of distributed protocols with payoff-maximizing participants has been studied for secret sharing and multi-party computation, which were shown to have Nash equilibria with desirable properties under bounded collusions [22].
The authors in [44] have introduced the concept of coalition-safe equilibria to investigate the potential increase in participant payoff through protocol deviation in Bitcoin and Fruitchain [55].
In our modelling of validators, we follow the BAR (Byzantine, altruistic, rational) model of protocol participants introduced by [23], which we respectively call adversarial, honest and rational.
The same work [23] provided the first safe and live asynchronous state machine replication protocol in the presence of both adversarial (Byzantine) and rational participants.
For a taxonomy of the incentive mechanisms of major blockchain protocols, we refer the reader to [41].

§ PRELIMINARIES

§.§ Model

Let $\lambda \in \mathbb{N}$ be the security parameter.
An event has negligible probability if its probability is $o(1/\mathsf{poly}(\lambda))$.
Given any event $A$, let $NA$ denote the complement of the event $A$ such that $A \cap NA = \emptyset$ and $\Pr[A \cup NA] = 1$.
Let $[n]$, $n \in \mathbb{N}$, denote the set $\{1, \ldots, n\}$.

§.§.§  State machine replication (SMR)

In state machine replication consensus protocols (total order broadcast), a set of nodes called the validators agree on a growing sequence of transactions (or blocks) called the ledger (or chain) and denoted by $\ch$.
Each validator can thus obtain the same end state upon executing these transactions in the order determined by $\ch$.
Transactions are input to the validators by the environment and become confirmed in a validator's view upon entering its ledger.

§.§.§  Blocks and chains

There is a publicly known genesis block $B_0$.
Each block except $B_0$ refers to its parent through its hash.
A block $B$ extends $B'$, denoted by $B' \preceq B$, if $B = B'$ or $B'$ lies on the path from $B$ to $B_0$.
All valid blocks extend $B_0$.
For each $B$, the path from $B$ to $B_0$ determines a unique chain $\ch$.

The confirmed chain held by a validator $\val$ at time $t$ is denoted by $\ch^{\val}_t$.

§.§.§  Adversary

The adversary $\Adv$ is an efficient algorithm that controls a subset of the validators called adversarial.
These validators can violate the consensus rules in an arbitrary fashion coordinated by $\Adv$ (Byzantine faults).
The remaining validators are either honest, , follow the prescribed protocol, or rational, , take the action providing the largest expected payoff in any specified game.

In later sections, we will first consider a model with adversarial and solo validators, which are rational and do not collude.
Afterward, we will analyze the interaction between the adversarial validators and

colluding sets of rational validators.

§.§.§  Network

In a synchronous network, the adversary can control the delivery time of the messages sent by the rational and honest validators up to a known delay upper bound $\Delta$.
We hereafter normalize $\Delta$ to be $1$ and adopt a lock-step communication model, where messages can only be sent at discrete intervals, and a message sent at some time $t$ (, wall clock time $\Delta t$) is delivered by time $t+1$, (, $\Delta t+ \Delta$).
Since our attacks do not require the adversary to delay the honest messages in arbitrary ways, we assume that the views of all validators and the adversary are the same at all `lock-step' times.
For a stronger security analysis, we will come back to the synchronous network in Section <ref>.

A validator is said to broadcast a message if its recipients include all validators.

§.§.§  Security

An SMR protocol is secure with latency $\Tconfirm$ if:

Safety: For any times $t,t'$ and validators $\val,\val'$, either $\ch_{t}^{\val} \preceq \ch_{t'}^{\val'}$ or vice versa.
For any $t' \geq t$, $\ch^{\val}_{t} \preceq \ch^{\val}_{t'}$.

$\mathbf{\Tconfirm}$-Liveness: If a transaction $\tx$ is input to a rational or honest validator at some time $t$, then $\tx \in \ch_{t'}^{\val}$ for all $t' \geq t+\Tconfirm$ and any $\val$.

§.§ The LMD GHOST Protocol

The LMD GHOST

protocol proceeds in epochs with $32$ slots, each with duration $3\Delta = 3$.
Before an epoch $e$, a randomness beacon called RANDAO divides the validator set of epoch $e$ into $32$ disjoint committees of size $W$ assigned to unique slots within the epoch [11].
It also selects a validator from each committee as the unique leader for its slot.
A slot with an adversarial (rational, honest) leader is called an adversarial (rational, honest) slot.
The adversary knows which slots are adversarial before the epoch starts[In RANDAO, slot leaders know their slots before the epoch. However, this is not necessary for our attacks to work, see Appendix <ref>.].

Validators use the LMD GHOST fork-choice rule to identify a canonical (beacon) chain of blocks.
As we assume that all validators have the same view of the protocol, we hereafter omit the mention of views.
At the beginning of a slot $s$, the leader $L$ signs and proposes a new block $B = \langle e, s, \txs \rangle_L$ with transactions $\txs$, that extends the canonical chain tip.
After $\Delta$ time, each slot $s$ attestor $\val$ signs and broadcasts a head vote $\langle e, s, B \rangle_\val$ for the block at the tip of the canonical chain.
Within $\Delta$ time, these votes are received and aggregated by a special subset of attestors,

who in turn broadcast the aggregated votes to be included by the next slot's block [1].
A slot $s$ vote is valid only if it is for a block with slot $s' \geq s$, and the vote was sent by a slot $s$ attestor.

When invoked at slot $s$, the fork-choice rule obtains the canonical chain iteratively starting at $B_0$.
At each block $B$, it inspects the subtrees rooted at $B$'s children.
It then selects the child block, whose tree has the largest weight, ties broken by the adversary.
The weight is equal to the number of unique head votes by the validators for the blocks in the tree, plus a proposal boost $\Wp$ (currently $\Wp/W = 40\%$) if the tree contains a block proposed for the current slot $s$[The original GHOST rule counted blocks rather than votes [61]].
If there are multiple valid votes by the same validator within a tree, the rule ignores all but one of the votes for the latest slot, thus the name `latest message driven (LMD)'.
In future sections, we will consider slots from the same epoch, with distinct attestor committees, unless stated otherwise.

§.§.§  Reorgs

Suppose a block $B$ proposed at some time $t'$ is not in the canonical chain for the first time at some $t \geq t'$.
Then, $B$ is said to be reorged at time $t$.

Reorg of a few honestly proposed blocks need not imply a liveness violation; however, reorgs of arbitrarily long block sequences would be a violation of LMD GHOST's safety and liveness.

( Appendix <ref>).

§.§ The Ethereum Reward Mechanism

A complete overview of the Ethereum reward mechanism is presented in Appendix <ref>. Here, we review two main sources of the validator's consensus layer reward: the inclusion (proposing) and the attestation rewards.
The inclusion reward is the reward that a slot leader receives for including attestations in its proposed block.
The attestation reward is the reward that a validator receives for attesting to its view of the canonical chain.
Each attestation consists of $3$ different votes: the source checkpoint, the target checkpoint, and the head vote (Section <ref>).
An attestation is eligible to receive the attestation reward if it is included in the canonical chain and is correct and timely [9].
Here, we only elaborate on the correctness and timeliness of the head vote reward, moving the discussion of these attributes for other votes to Appendix <ref>.

A slot $s$ head vote for a block is correct if that block is the last block within the canonical chain from slots $s' \in [0,s]$.

If the tip of the canonical chain in the view of an attestor is extended by a block $B_t$ at slot $t$, the attestor should vote for block $B_t$.
However, if the slot block is missing, the attestor can vote for the previous block in the canonical chain, and the vote is still correct.
Since Ethereum's Altair upgrade [2],

a slot $t$ head vote must be included in the subsequent block of slot $t+1$ to be considered timely.

§ THE SIMPLE ATTACK IN THE PRESENCE OF SOLO VALIDATORS

We first present the simple

in the presence of solo validators (Figs. <ref> and <ref>).
The attack exploits Ethereum's reward mechanism to incentivize the validators to submit votes favorable to the adversary.
Towards this goal, the adversary communicates a credible threat that can lead to a financial loss for the non-compliant validators.

§.§ The Simple Game

Each attack induces a `game' between the rational validators and a Byzantine adversary.

The actions available to the rational validators are as follows:

* A slot $s$ leader can build a single new block for slot $s$, denoted by $B_{s}$, extending any block in its view at any time.

* A slot $s$ attestor can send a single slot $s$ vote for any block in its view at any time.

* Adversarial leaders and attestors can deviate from the protocol arbitrarily.

* The adversary can send arbitrary messages to any validator on behalf of the adversarial validators.
It is the only player that can commit to an action and communicate this commitment to the other validators.

We assume that a rational validator never proposes two different blocks for the same slot or sends two or more head votes with the same slot number for distinct blocks.
This is because these violations are provably detectable, causing the slashing of the validator's stake.

Although the honest actions for the slot $s$ leader and attestors are to respectively send their block and votes at times $3s$ and $3s+1$, the rational validators can delay their messages or withhold them altogether if that gives them a higher payoff.

The validator payoffs come from the inclusion and attestation rewards (, Section <ref>).
For simplicity, the source checkpoint and target checkpoint rewards are excluded from the payoff calculation, making the head vote reward the only source of attestation reward.

The simple game starts at the beginning of some slot $t$ at time $3t$ such that the leader of slot $t+1$ is adversarial.
It has the adversary (the slot $t+1$ leader) and the slot $t$ attestors

as its players.

All slot $t$ attestors are rational solo validators.

The initial payoff of the players is $0$ in all games and the players are risk-neutral with utility function $U(x) = x$.

Let $B_{t-1}$ denote the block at the tip of the canonical chain at the end of slot $t-1$.
The adversary succeeds if less than $\Wp$ slot $t$ attestors vote for $B_{t}$ by time $3t+3$.
It fails if over $\Wp$ slot $t$ attestors vote for $B_{t}$ by time $3t+3$.
The game ends, and the payoffs are realized at the end of slot $t$, at time $3t+3$.

§.§ The Adversary's Action

We next describe the adversary's action.

At the start of slot $t$, the adversary $\mathcal{A}$ performs the following steps:

* Generates a proof asserting its leadership in slot $t+1$.

* Sets the instructions for the validators (called the game rule)

as follows: The attestors of slot $t$ should vote for the block $B_{t-1}$

by the end of slot $t$.

* Commits to the following action: Head votes of the attestors that do not vote for $B_{t-1}$ will not be included in the adversary's block in slot $t+1$.

* Broadcasts the leadership proof, the game rule and its commitment

to all slot $t$ attestors.

The slot $t$ attestors who follow (do not follow) the game rule above are called compliant (non-compliant).
At the start of slot $t+1$, adversary $\mathcal{A}$ takes the following action:

* The adversary includes the head votes of only the compliant attestors in $B_A$

* If $\Wp$ or more slot $t$ attestors have voted for $B_{t}$, it proposes its block $B_A$ on top of block $B_{t}$[In this case, the compliant attestations included in $B_A$ only receive the source and target checkpoint rewards and do not receive the head vote reward. This is because the compliant head votes are for $B_{t-1}$ and do not satisfy the correctness property, as they are not for $B_A$'s parent $B_t$.].

In this scenario (Fig. <ref>), $\mathcal{A}$ is unsuccessful.

* If less than $\Wp$ attestors have voted for $B_{t}$, it proposes its block on top of $B_{t-1}$

In this scenario (Fig. <ref>), $\mathcal{A}$ is successful.

§.§ Analysis

There exists a Nash equilibrium of the simple game in the presence of solo validators, where the adversary succeeds.

The proof is presented in Appendix <ref> and its main idea is captured by Table <ref>.

Pay-off matrix of a solo slot $t$ attestor in the simple game. Let $V_\val$ denote the event that the validator $\val$ votes for $B_{t-1}$ (, $\val$ is compliant).
Let $A$ denote the event that less than $\Wp$ slot $t$ attestors vote for $B_{t}$.

$V_\val$     $NV_\val$

$A$     $r$     $0$

$NA$     $0$     $0$

There are many Nash equilibria, where the adversary $\mathcal{A}$ is not successful.
Suppose over $\Wp+1$ slot $t$ attestors vote for $B_t$ (the $NA$ row).
Then, $\mathcal{A}$ cannot reorg $B_t$ with $B_A$, and no vote for a block other than $B_t$ can be both correct and timely.
As $\mathcal{A}$ also commits to excluding votes for $B_t$, no solo slot $t$ attestor receives a positive payoff for any action.

voting for $B_t$ weakly dominates any other action for the slot $t$ committee, making this a Nash equilibrium.

For any $\epsilon>0$, the adversary with budget $\epsilon$ can ensure its success in all Nash equilibria by offering an $\epsilon/W$ amount of bribe to each slot $t$ attestor to vote for $B_{t-1}$; since this makes the payoff of the $V_\val$-$NA$ corner $\epsilon/W>0$.
These bribes can be paid out using smart bribery contracts on Ethereum.

Even under an honest minority assumption (, $<\Wp$ honest attestors per slot), LMD GHOST is still susceptible to the simple attack, , there is a Nash equilibrium where the adversary succeeds; since the number of honest validators would not be enough to overcome the proposer boost exploited by the adversary's block.
Appendix <ref> describes a modified simple attack that works under honest minority, even when the proposer boost is $0$.

When the attack is successful,

by reorging $B_{t}$, the adversary can include a more valuable set of transactions in its block $B_A$,

resulting in an increase in $B_A$'s execution layer reward.
The adversary can also include the slot $t-1$ attestations, even by non-compliant attestors, in $B_A$ to obtain the inclusion reward for the slot $t-1$ source and target checkpoint votes.

§.§ Credibility

Since a slot leader profits from including all correct votes due to the inclusion reward, on the surface, the adversary's threat about including only the compliant votes does not sound credible.

However, credibility can be enforced in multiple ways.
The adversary can commit to its strategy by executing it in a trusted execution environment (TEEs, , SGX [19]) and using the TEE's signatures for the verification of its block.

Then, the only way the adversary can deviate from its commitment would be stopping the TEE, which is not profitable; since it would then lose the ability to propose new blocks and get the inclusion reward.
Alternatively, $\mathcal{A}$ can place a collateral, larger than the inclusion reward of the non-compliant votes, in a public contract, which burns the money if it deviates from the committed strategy.

Using restaking protocols such as EigenLayer, $\mathcal{A}$ can also reuse its Ethereum stake as collateral in the public contract [16] instead of putting up new deposit.
It can also ensure the burning of the rewards for a block including non-compliant votes by setting the withdrawal address for these rewards to be a contract complying with the restaking protocol, and then specifying the inclusion of non-compliant votes as an additional slashing condition.

We hereafter assume that a rational adversary can commit to any strategy to reorg blocks, as long as its payoff is non-negative in all outcomes.
Although committing to certain actions could imply a drop in payoff in the short run, in practice, successfully reorging a block and capturing its MEV would offset any such loss.

This ability to commit enables us to model a rational adversary engaging in for-profit reorgs as a Byzantine adversary.

In the attack, we assumed that the adversarial leader of slot $t+1$ is the first to commit to any strategy and communicate a credible threat to the other validators.
Indeed, validators do not necessarily commit to strategies during normal execution and might not foresee an attack.
Nevertheless, the simple attack and the credibility analysis above could be extended to a rational slot $t+2$ leader who wants to reorg $B_{t+1}$, or to a rational slot $t$ attestor that commits to voting for $B_t$.
The equilibria that emerge when multiple leaders engage in such attacks are discussed in Section <ref>.

§ THE EXTENDED ATTACK IN THE PRESENCE OF SOLO VALIDATORS

We next describe the extended attack (Figs. <ref>, <ref>, <ref> and <ref>, in Appendix <ref>), where the adversary engages with the validators of multiple consecutive slots to reorg multiple blocks.

§.§ The Extended Game

The extended game starts at the beginning of some slot $t+p$ at time $3(t+p)$, where the leader of slot $t+2p+1$ is adversarial.
We normalize $t+p = 0$.
Let $B_i, i \in \{-p,\ldots, 0\}$ denote the block from slot $i$ (the non-normalized slot $t+i$).
Suppose at the end of slot $0$, the canonical chain ends with the block sequence $B_{-p}, \ldots, B_0$, each block with $W$ votes.

The game has the adversary, attestors of the slots in $[p]$

and the leaders of the slots in $[p+1]$ as its players.
All players, including the slot leaders, are rational solo validators.
The actions available to the solo attestors, leaders, and the adversary are as in Section <ref>.

The adversary succeeds if the canonical chain at the end of slot $p$ is a sequence of empty blocks extending $B_{-p}$, , if the chain consisting of the blocks $B_{-p+1}, \ldots, B_0$ has been reorged by a chain of empty blocks $B^e_{1}, \ldots, B^e_p$ from slots $1, \ldots, p$ (Fig. <ref>).
It fails otherwise.
The game ends, and the payoffs are realized at the end of slot $p$.

§.§ The Adversary's Action

Before describing the adversary's action, we define compliant blocks and votes (Fig. <ref>, Def. <ref>).
To this end, we first define the concept of compliant tip at slot $i$ ( Alg. <ref> in the Appendix).

Consider the leader $L_i$ of a slot $i \in [p]$ that wishes to propose a compliant block at time $3i$.
To identify the compliant tip at time $3i$, $L_i$

iterates over all blocks $B$ in the block tree of $B_{-p}$ and its descendants at time $3i$ (Alg. <ref>, Line <ref>).
For each block $B$, it envisions the hypothetical canonical chain $\chain_B$ that would be returned by the LMD-GHOST fork-choice rule at the start of slot $p+1$, if all the attestors of slots $i, \ldots, p$ (in total $(p-i+1) W$) were to vote for $B$'s descendants (but not $B$), and $\mathcal{A}$'s block $B_A$ were to extend the tip of the chain descended from $B$ (Alg. <ref>, Lines <ref> and <ref>).
It subsequently checks if $B$ would be part of this canonical chain $\chain_B$ (Alg. <ref>, Line <ref>).
If so, $L_i$ records the slot number of the non-compliant block with the largest slot in the prefix of $B$ and including $B$ in a dictionary $S$ indexed by blocks (Alg. <ref>, Line <ref>).
After repeating this procedure for all blocks in the block tree of $B_{-p}$, $L_i$ identifies the block $B^*$ such that $B^*$ is in $\chain_{B^*}$ and the slot number of the last non-compliant block in $B^*$'s prefix is smallest among all blocks considered by Alg. <ref> (ties are broken deterministically).
We call block $B^*$ the compliant tip at slot $i$.
The same steps are used by the slot $i$ attestors to identify the compliant tip.

Compliant blocks and votes in the extended game. The extended game is successful if the chain of blocks $B_{-p+1}, \ldots, B_0$ gets reorged by the chain of empty blocks $B^e_{1}, \ldots, B^e_p$.

A compliant slot $i \in [p]$ block is denoted by $B^e_i$ ($B^e_0 = B_{-p}$).

* A compliant slot $1$ block (i) is empty and (ii) is proposed on top of block $B_{-p}$.

* A slot $i$ vote is compliant if it is for the compliant tip returned by Alg. <ref> at time $3i + 1$.

* For slots $i = 2,\ldots,p$, a slot $i$ block is compliant if it (i) is empty, (ii) is proposed on top of the compliant tip returned by Alg. <ref> at time $3i$ and (iii) contains only the compliant slot $i-1$ votes for its parent.

Validators observe the protocol throughout the slots in $[p]$ and iteratively judge whether a block or vote is compliant according to the compliant tip of the slots in $[p]$ as time proceeds.

Before slot $1$ starts, the adversary $\mathcal{A}$ generates a proof asserting its leadership in slot $p+1$ and

sets the game rule as follows:

Proposal rule: For each $i \in [p]$, the slot $i$ leader should propose a compliant block.

Voting rule: For each $i \in [p]$, the slot $i$ attestors should send compliant votes.

Commitment: $\mathcal{A}$ commits to excluding non-compliant slot $p$ votes from its block $B_A$.

At the start of slot $p+1$, $\mathcal{A}$ takes the following action:

* It proposes its block $B_A$ on top of the compliant tip returned by Alg. <ref> at time $3p$.

* It includes only the compliant slot $p$ votes in $B_A$.

Before slot $1$, $\mathcal{A}$ sends the leadership proof and the game rule to all validators

of slots in $[p]$.

§.§ Analysis

As the extended game lasts multiple slots and the future players observe the past actions, we show a subgame perfect Nash equilibrium (SPNE), where solo players follow the game rule.

There exists a SPNE of the extended game in the presence of solo validators, where the adversary succeeds

and violates the security of LMD GHOST.

Proof of Theorem <ref> is provided in Appendix <ref>.
It shows that all solo players are incentivized to follow the adversary's game rule rather than the honest protocol at each subgame corresponding to a slot in $[p]$.

As in Notes <ref>, <ref> and <ref>, (i) there are many SPNE, where the adversary $\mathcal{A}$ is not successful, (ii) the adversary with budget $\epsilon>0$ can ensure its success in all Nash equilibria by offering an $\epsilon/pW$ amount of bribe to each slot $i \in [p]$ attestor, and (iii) when the number of honest validators per slot is $W_h<(W/2)$ (honest minority), LMD GHOST is still susceptible to the extended attack (Notes <ref>, <ref> and <ref> in Appendix <ref>).

§ ATTACKS IN THE PRESENCE OF A FIXED ATTESTOR SET

In Sections <ref> and <ref>, we have analyzed the simple and the extended attacks under 2 assumptions: i) all attestors are solo validators, and ii) the attestor set is different in each slot.
This matches the current version of Ethereum, where

the validators are divided into $32$ attestor committees, each for a different slot.

In this section, we analyze the simple and the extended attacks assuming the same set of attestors across slots.

This analysis serves a dual purpose.
First, it shows that our attacks apply to Ethereum with single-slot finality [13], where all attestors send votes in each slot, and to other similar protocols featuring a fixed attestor set.

Second, it demonstrates the success of the attacks

in the presence of staking pools.

A fixed validator set can influence the strategy of a rational attestor against the attack.

for analyzing the simple game under rotating attestors, we only had to consider the head vote reward of a solo validator for its vote in slot $t$.
However, under a fixed attestor set, we should consider the reward an attestor receives in both slots $t-1$ and $t$.
This is because if the adversary reorgs the block of slot $t$, the slot $t-1$ reward is affected as well.

§.§ The Simple Game

The simple game and the adversarial action are the same as in Section <ref> except that a solo validator $\val$'s payoff depends on its votes in each of the slots $t-1$ and $t$.

There exists a Nash equilibrium of the simple game

under the fixed validator set model, where the adversary succeeds.

Proof of Theorem <ref> for a fixed set of solo validators is presented in Appendix <ref>. Fig. <ref> illustrates the intuition behind the proof.

$NA$, $NV_P$. The payoff of staking pool $P$ is equal to $mr$.

$NA$, $V_P$. The payoff of staking pool $P$ is equal to $mr$.

$A$, $NV_P$. The payoff of staking pool $P$ is equal to $0$.

$A$, $V_P$. The payoff of staking pool $P$ is equal to $mr$.

The payoff of a staking pool $P$ with a total stake share less than $\Wp$ in the simple game under the fixed validator set model. The staking pool $P$ controls $m$ votes in each slot, where $m$ can be either 1 (representing a solo validator) or greater than 1 (representing a coalition of solo validators). $r$ represents the reward for a single correct and timely head vote. Let $V_P$ and $NV_P$ denote the events that the staking pool $P$ votes and does not vote for $B_{t-1}$ (acts compliantly and non-compliantly), respectively. Let $A$ denote the event that less than $\Wp$ slot $t$ attestors vote for $B_t$, and $NA$ the event that $\Wp$ or more slot $t$ attestors vote for $B_t$. The green tick and the red cross represent whether a head vote receives or does not receive a reward, respectively. $V_P$ (compliance) weakly dominates $NV_P$ (non-compliance).

There are Nash equilibria, similar to those in Note <ref>, where the adversary $\mathcal{A}$ is not successful.
As in Notes <ref> and <ref>, $\mathcal{A}$ can ensure its success in all Nash equilibria by offering an $\epsilon/W$ amount of bribe to each slot $t$ attestor to vote for $B_{t-1}$, and given an honest minority, there is a Nash equilibrium where the adversary succeeds.

§.§ The Extended Game

The extended game and the adversarial action are the same as in Section <ref> except that a solo validator's payoff depends on its votes in each of the slots.

There exists a SPNE of the extended game

under the fixed validator set model, where the adversary succeeds

and violates the security of LMD GHOST.

Proof of Theorem <ref> is in Appendix <ref> and has a similar outline as the proof of Theorem <ref>.

There are SPNE, similar to those in Note <ref>, where the adversary $\mathcal{A}$ is not successful.
However, unlike in Note <ref>, $\mathcal{A}$ cannot ensure its success in all SPNE by offering a small bribe to the attestors to send compliant votes.
Suppose all leaders and attestors of slots $1, \ldots, p$ extend a chain from block $B_0$ instead of attempting to reorg the blocks from slots $-p+1, \ldots, 0$.
This is a SPNE, where the attestors' total payoff during the $2p+1$ slots within $[-p,p]$ is $2pr > pr$, and the adversary cannot convince any attestor to deviate if its total budget is less than $r$.

As in Note <ref>, under an honest minority assumption, there is still a SPNE where the adversary succeeds.

The existence of equilibria as in Note <ref>, where the attestors achieve greater payoffs compared to the SPNE of the attack

incentivizes them to

collude as a single entity (, a staking pool) to mitigate the attack.

An adversary faced with colluding attestors may refer to the selfish mining-inspired attack in Appendix <ref>, where even colluding validators are incentivized to comply with the adversary.

However, this attack requires a larger stake share.

§.§ Attacks in the Presence of Staking Pools

A staking pool is modelled as a single entity controlling a fixed number of votes in each slot.
If a staking pool $P$ controls less than $\Wp$ attestors per slot, acting compliantly (voting for $B_{t-1}$) weakly dominates any other action in the simple game as shown on Fig. <ref>.
On the other hand, if $P$ controls over $\Wp$ attestors[As of May 20, 2024, the largest staking pool is LIDO, holding $28\%<\Wp = \%40$ of the total Ethereum stake [17].] per slot, acting non-compliantly (voting for $B_{t}$) weakly dominates any other action in the simple game, even though following the adversarial action (voting for $B_{t-1}$) still remains weakly dominant.
Therefore, using the same analysis employed in the fixed validator set model (Section <ref>,

and Appendix <ref>), we can establish the existence of Nash equilibria of the simple and selfish mining-inspired games in the presence of a staking pool with any size, where the adversary succeeds.

This shows that the attacks could succeed even when the rational attestors collude.

§ MECHANISM PROPOSED FOR ETHEREUM

The mechanism (Fig. <ref>) requires each slot $t+1$ attestor to sign all slot $t$ head votes in its view at the beginning of slot $t+1$.
A signature of a slot $t+1$ attestor on a slot $t$ vote is called a slot $t$ evidence.
A slot $t$ attestor gains an attestation reward for its vote if the vote is included in any slot $t'>t$ block $B$ within the canonical chain, and the vote is correct and timely with respect to $B$.
Correctness and timeliness are re-defined as follows:

The slot $t$ vote is correct if it is for the highest block from slots $\leq t$ in the prefix of $B$ (let $B_\ell$ denote this block).

The slot $t$ vote is timely if either $B'$ is of slot $t+1$, or there are over $W/2$ unique slot $t$ evidences for the slot $t$ vote in the prefix of $B'$ after block $B_\ell$.

As the mechanism relies on slot $t+1$'s committee to infer whether a slot $t$ vote is timely, it reduces the adversary's influence over the attestation rewards, unless it controls half of the committee.
An adversary with bounded stake cannot delay the inclusion of evidences in the chain indefinitely, implying that its previous attacks fail (Sections <ref>, <ref> and <ref>).
The mechanism also allows rewarding the slot $t+1$ committee for generating slot $t$ evidences and the leaders for including the past votes and evidences.

§.§ Made Practical

We now present a practical version of and compare its performance with Ethereum's current reward mechanism.
Recall that an attestation is composed of a signature on the head vote, source checkpoint, and target checkpoint votes.

§.§.§  Current version of Ethereum

Let $N$ denote the total number of validators[As of May 20, 2024, there are 1,005,228 active Ethereum validators [21].]. Each slot has $N/32$ attestors,

which are divided into $64$ sub-committees, each with $\frac{N}{32*64}$ attestors.

A subset of the sub-committee is selected to be the aggregators of the sub-committee[The average number of aggregators in each sub-committee is set to 16.].
These aggregators are responsible for aggregating the attestations (signatures) of their sub-committee.
Ethereum uses the BLS signature for attestations due to its key-homomorphism [26].
In the ideal scenario, where all attestations of the sub-committee members are the same, these attestations can be aggregated into a single aggregated attestation (aggregate for short).
Each aggregate contains an aggregated signature and an aggregation list.
The $i^\text{th}$ element in the aggregation list is $1$ if the signature of the $i^\text{th}$ attestor in the corresponding sub-committee is included in the aggregated signature, and $0$ otherwise.
In the ideal scenario, there exist $64$ aggregates per slot in total, and each block can include up to $128$ aggregates.

The slack between $64$ and $128$ is to cover attestations for different blocks or the missing attestations from the previous slots[These attestations may be eligible to receive the source/target rewards.].

§.§.§  Practical version of

In our solution above, all the attestors in each slot are responsible for generating evidences.
This can increase the communication and storage overheads drastically.
To address this issue, we propose a practical version of .
In this version, a subset of attestors is sampled in each slot to serve as the aggregators responsible for generating the evidence. In contrast to the main version, only the aggregators produce the evidences in the practical version.

Let sub-committee $(t,i)$ represent the $i^\text{th}$ sub-committee of slot $t$, $N^\text{att}$ denote the number of attestors per sub-committee, $N^\text{agg}$ denote the number of aggregators per sub-committee. An attestation must gather over $N^\text{limit}$ evidences to be considered timely.

Each attestor in sub-committee $(t+1,i)$ sends an attestation at time $3(t+1)+1$.
Then, the aggregator $j \in [N^\text{agg}]$ in sub-committee $(t+1,i)$ takes the following actions at time $3(t+1)+2$:

* Collect the individual attestations of sub-committee $(t+1,i)$ members and aggregate them into a single aggregated attestation (called aggregate) denoted by $\mathsf{Ag}^j_{t+1,i}$.

* Generate an evidence for slot $t$ attestations if the block of slot $t+1$ is not published or excludes some of the slot $t$ attestations.

Collect the

aggregates by the aggregators of sub-committee $(t,i)$, , $\mathsf{Ag}^k_{t,i}$ for $k \in [N^\text{agg}]$, select and sign the one with the greatest number of signatures.

to generate the $j^\text{th}$ sub-committee $(t,i)$ evidence denoted by $E^j_{t,i}$.

* Broadcast slot $t+1$ aggregate $\mathsf{Ag}^j_{t+1,i}$ and slot $t$ evidence $E^j_{t,i}$.

If slot $t$ attestations are not included in the slot $t+1$ block, any block proposed at slots $t'>t+1$ can include the slot $t$ evidences.

Each evidence is composed of 3 parts: the signature of the evidence generator, the aggregated attestation signature, and an aggregation list,

specifying which validators' attestations are included in the aggregated signature.

The parameters $N^\text{agg}$ and $N^\text{limit}$

should be configured to ensure that each sub-committee has more than $N^\text{limit}$ non-adversarial available aggregators with high probability.
This is crucial to guarantee that the adversary cannot prevent the timeliness verification of attestations and cannot prove delayed votes as timely by publishing their evidences late.

§.§ Performance Comparison

In this section, we estimate the storage, computation, and communication overheads of our solution and compare them with the overheads of the current Ethereum version.
We analyze the practical version of our solution under three scenarios: i) the ideal scenario, where all slot $t$ attestations are included in the slot $t+1$ block; ii) the optimistic scenario, where the majority of slot $t+1$ aggregators sign the same slot $t$ aggregate; and iii) the worst-case scenario, where the slot $t+1$ aggregators sign different slot $t$ aggregates.

§.§.§  The ideal scenario

In the ideal scenario, the performance of our solution is the same as the current Ethereum version. This is because,

slot $t+1$ aggregators are not required to generate any slot $t$ evidences as they are already included in the slot $t+1$ block (if the slot $t+1$ block is later reorged, they can later generate evidences in retrospect).

§.§.§  The optimistic scenario

If the slot $t+1$ block is missing or has excluded attestations, the slot $t+1$ aggregators are required to generate evidences.
Then, the optimistic scenario is typical under synchrony.
In the optimistic scenario, as the majority of slot $t+1$ aggregators sign the same aggregated attestation, their evidences can be aggregated into a single aggregated evidence. The aggregated evidence needs to contain an evidence aggregation list to specify which aggregators' individual evidences are included in the aggregated one.
In the following, we present the main results of our analysis of the overhead incurred by our solution in the optimistic scenario.

More details are provided in Appendix <ref>.

Block space: Suppose the adversarial stake share is less than or equal to $1/3$. In this case, assigning $N^\text{agg}=128$ and $N^\text{limit}=64$ ensures that the probability of the number of non-adversarial aggregators in a sub-committee falling below $N^\text{limit}$ is less than $10^{-4}$. With $N^\text{agg}=128$ and $N^\text{limit}=64$, the total size of evidences per block would be 33.712 kilobytes, resulting in an 8.43% increase in the block size.

Computational overhead: We assess the computational overhead under the optimistic scenario from the perspective of various parties. We assume $N^\text{att}=443$ and $N^\text{agg}=16$. Let $C^\text{add}$, $C^\text{mul}$, and $C^\text{pair}$ denote the computational cost of an addition, a scalar multiplication, and a pairing operation over the BLS12-381 elliptic curve, respectively.

Aggregators: An aggregator's computational cost in our practical version is $2(N^\text{att}+1) C^\text{pair} + 2(N^\text{att}-1)C^\text{add}+ 2C^\text{mul}$, which takes 0.59 seconds based on our implementation results[Implementation device: a laptop equipped with an Intel Core i7 CPU with base frequency of 2.70GHz.].

Block proposers: A block proposer in total incurs an additional computational cost of $128N^\text{agg}C^\text{pair}+64(N^\text{agg}-1)C^\text{add}$ in our practical version. Based on our implementation results, this additional computation takes $1.36$ seconds.

Verifiers: A verifier incurs the computational cost of $64(2N^\text{att}+N^\text{agg}-3)C^\text{add} + 384C^\text{pair}$ in the practical version. Based on our implementation, this computation takes $0.38$ seconds.

Communication overhead: Under the optimistic scenario, each aggregator needs to send an additional pair of messages: the aggregated attestation  ($96$ bytes) from the previous slot and its signature on that attestation  ($96$ bytes). This implies that each aggregator has to send $192$ extra bytes compared to the current Ethereum version.

§.§.§  The worst-case scenario

With an adversarial stake share $\leq 0.1$, evidence size per block is $506.624$ KB, and computational overhead increases to $256 N^\text{agg}$ signature verifications.
The communication overhead is the same as the optimistic scenario.
A detailed analysis is in Appendix <ref>.

§ CONCLUSION

As our attacks show, the ability for adversaries to commit to conditional courses of action presents challenges for the design of protocol mechanisms.
This holds more so given the availability of commitment devices within the protocol's enclosure, the devices possibly executing the protocol itself. Recent literature has uncovered such attacks on fee market mechanisms, a core function of blockchains [45], naming the deployment of a smart contract committing the author to certain actions a “Stackelberg attack”, after the classic model of leader-followers games [62]. Indeed, the order of commitments is known to be important: players will often gain significant advantage from the ability to commit first [57, 27].

The attacks presented in this paper offer a better response compared to the honest protocol specifications for some protocol participants, in the presence of commitment devices. We leave for future work deciding whether these attacks constitute best responses for rational attackers;  which equilibria exist if any, when all participants benefit from the commitment ability (, proposers attempting to reorg one another in the spirit of undercutting attacks [33]); and the importance of the sequence of play to the determination of outcomes.

[1]
Aggregator selection, 2023.
URL: <https://eth2book.info/capella/part2/building_blocks/aggregator/>.

[2]
Altair, 2023.
URL: <https://github.com/ethereum/consensus-specs/blob/dev/specs/altair/beacon-chain.md>.

[3]
[block, slot] voting, 2023.
URL: <https://github.com/ethereum/consensus-specs/pull/2197>.

[4]
Enshrine PBS, 2023.
URL: <https://ethresear.ch/t/why-enshrine-proposer-builder-separation-a-viable-path-to-epbs/15710>.

[5]
Ethereum average block size chart, 2023.
URL: <https://etherscan.io/chart/blocksize>.

[6]
Ethereum roadmap, 2023.
URL: <https://ethereum.org/fil/roadmap/>.

[7]
Proof-of-stake rewards and penalties, 2023.
URL: <https://ethereum.org/en/developers/docs/consensus-mechanisms/pos/rewards-and-penalties/#slashing>.

[8]
Proposer-builder seperation, 2023.
URL: <https://ethereum.org/fil/roadmap/pbs/>.

[9]
Reward of the consensus layer, 2023.
URL: <https://eth2book.info/capella/part2/incentives/rewards/>.

[10]
Secret leader election, 2023.
URL: <https://ethereum.org/fil/roadmap/secret-leader-election/>.

[11]
Shuffling, 2023.
URL: <https://eth2book.info/capella/part2/building_blocks/shuffling/>.

[12]
Simple single-slot finality, 2023.
URL: <https://ethresear.ch/t/a-simple-single-slot-finality-protocol/14920>.

[13]
Single-slot finality, 2023.
URL: <https://ethereum.org/fil/roadmap/single-slot-finality/>.

[14]
5 Pirate Puzzle Question, 2024.
URL: <https://puzzling.stackexchange.com/questions/54800/5-pirate-puzzle-question>.

[15]
[AMA] We are EF Research (Pt. 11: 10 January, 2024), 2024.
URL: <https://www.reddit.com/r/ethereum/comments/191kke6/comment/kh7j3ig/>.

[16]
Eigenlayer, 2024.
URL: <https://www.eigenlayer.xyz/>.

[17]
Ethereum staking, 2024.
Last accessed: January, 19, 2024.
URL: <https://dune.com/hildobby/eth2-staking>.

[18]
Flashbots transparency dashboard, 2024.
URL: <https://transparency.flashbots.net/>.

[19]
Intel Software Guard Extensions (Intel SGX), 2024.
URL: <https://www.intel.com/content/www/us/en/products/docs/accelerator-engines/software-guard-extensions.html>.

[20]
Mev-boost, 2024.
URL: <https://github.com/flashbots/mev-boost>.

[21]
Open source ethereum explorer, 2024.
URL: <https://beaconcha.in/>.

[22]
Ittai Abraham, Danny Dolev, Rica Gonen, and Joseph Y. Halpern.
Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation.
In PODC, pages 53–62. ACM, 2006.

[23]
Amitanand S. Aiyer, Lorenzo Alvisi, Allen Clement, Michael Dahlin, Jean-Philippe Martin, and Carl Porth.
BAR fault tolerance for cooperative services.
In SOSP, pages 45–58. ACM, 2005.

[24]
Aditya Asgaonkar, Francesco D'Amato, Roberto Saltini, Luca Zanolini, and Chenyi Zhang.
A confirmation rule for the ethereum consensus protocol.
CoRR, abs/2405.00549, 2024.

[25]
Christian Badertscher, Peter Gazi, Aggelos Kiayias, Alexander Russell, and Vassilis Zikas.
Ouroboros genesis: Composable proof-of-stake blockchains with dynamic availability.
In CCS, pages 913–930. ACM, 2018.

[26]
Dan Boneh, Ben Lynn, and Hovav Shacham.
Short signatures from the weil pairing.
J. Cryptol., 17(4):297–319, 2004.

[27]
James W Bono and David H Wolpert.
Game mining: How to make money from those about to play a game.
In Entangled Political Economy, pages 179–211. Emerald Group Publishing Limited, 2014.

[28]
Ethan Buchman, Rachid Guerraoui, Jovan Komatovic, Zarko Milosevic, Dragos-Adrian Seredinschi, and Josef Widder.
Revisiting tendermint: Design tradeoffs, accountability, and practical use.
In DSN (Supplements), pages 11–14. IEEE, 2022.

[29]
Ethan Buchman, Jae Kwon, and Zarko Milosevic.
The latest gossip on BFT consensus.
CoRR, abs/1807.04938, 2018.

[30]
Vitalik Buterin and Virgil Griffith.
Casper the friendly finality gadget.
CoRR, abs/1710.09437, 2017.

[31]
Vitalik Buterin, Diego Hernandez, Thor Kamphefner, Khiem Pham, Zhi Qiao, Danny Ryan, Juhyeok Sin, Ying Wang, and Yan X. Zhang.
Combining GHOST and casper.
CoRR, abs/2003.03052, 2020.

[32]
Vitalik Buterin and Alistair Stewart.
Beacon chain Casper mini-spec (comments #17, #19), 2018.
URL: <https://ethresear.ch/t/beacon-chain-casper-mini-spec/2760/17>.

[33]
Miles Carlsten, Harry A. Kalodner, S. Matthew Weinberg, and Arvind Narayanan.
On the instability of bitcoin without the block reward.
In CCS, pages 154–167. ACM, 2016.

[34]
Miguel Castro and Barbara Liskov.
Practical byzantine fault tolerance.
In OSDI, pages 173–186. USENIX Association, 1999.

[35]
Philip Daian, Steven Goldfeder, Tyler Kell, Yunqi Li, Xueyuan Zhao, Iddo Bentov, Lorenz Breidenbach, and Ari Juels.
Flash boys 2.0: Frontrunning, transaction reordering, and consensus instability in decentralized exchanges.
CoRR, abs/1904.05234, 2019.

[36]
Francesco D'Amato, Joachim Neu, Ertem Nusret Tas, and David Tse.
No more attacks on proof-of-stake ethereum?
CoRR, abs/2209.03255, 2022.
In FC'24.

[37]
Francesco D'Amato and Luca Zanolini.
Recent latest message driven GHOST: balancing dynamic availability with asynchrony resilience.
IACR Cryptol. ePrint Arch., page 279, 2023.
In CSF 2024.

[38]
Francesco D'Amato and Luca Zanolini.
A simple single slot finality protocol for ethereum.
In ESORICS Workshops (1), volume 14398 of Lecture Notes in Computer Science, pages 376–393. Springer, 2023.

[39]
Ittay Eyal and Emin Gün Sirer.
Majority is not enough: Bitcoin mining is vulnerable.
In Financial Cryptography, volume 8437 of Lecture Notes in Computer Science, pages 436–454. Springer, 2014.

[40]
Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos.
The bitcoin backbone protocol: Analysis and applications.
In EUROCRYPT (2), volume 9057 of Lecture Notes in Computer Science, pages 281–310. Springer, 2015.

[41]
Rong Han, Zheng Yan, Xueqin Liang, and Laurence T. Yang.
How can incentive mechanisms and blockchain benefit with each other? A survey.
ACM Comput. Surv., 55(7):136:1–136:38, 2023.

[42]
Lioba Heimbach, Lucianna Kiffer, Christof Ferreira Torres, and Roger Wattenhofer.
Ethereum's proposer-builder separation: Promises and realities.
In IMC, pages 406–420. ACM, 2023.

[43]
Dimitris Karakostas, Aggelos Kiayias, and Christina Ovezik.
Sok: A stratified approach to blockchain decentralization.
CoRR, abs/2211.01291, 2022.

[44]
Aggelos Kiayias and Aikaterini-Panagiota Stouka.
Coalition-safe equilibria with virtual payoffs.
In AFT, pages 71–85. ACM, 2021.

[45]
Daji Landis and Nikolaj I Schwartzbach.
Stackelberg attacks on auctions and blockchain transaction fee mechanisms.
CoRR, abs/2305.02178, 2023.

[46]
Satoshi Nakamoto.
Bitcoin: A peer-to-peer electronic cash system.
URL: <https://bitcoin.org/bitcoin.pdf>.

[47]
Ryuya Nakamura.
Analysis of bouncing attack on FFG, 2019.
URL: <https://ethresear.ch/t/analysis-of-bouncing-attack-on-ffg/6113>.

[48]
Ryuya Nakamura.
Prevention of bouncing attack on FFG, 2019.
URL: <https://ethresear.ch/t/prevention-of-bouncing-attack-on-ffg/6114>.

[49]
Joachim Neu, Ertem Nusret Tas, and David Tse.
A balancing attack on Gasper, the current candidate for Eth2’s beacon chain, 2020.
URL: <https://ethresear.ch/t/a-balancing-attack-on-gasper-the-current-candidate-for-eth2s-beacon-chain/8079>.

[50]
Joachim Neu, Ertem Nusret Tas, and David Tse.
Snap-and-chat protocols: System aspects.
CoRR, abs/2010.10447, 2020.

[51]
Joachim Neu, Ertem Nusret Tas, and David Tse.
Attacking Gasper without adversarial network delay, 2021.
URL: <https://ethresear.ch/t/attacking-gasper-without-adversarial-network-delay/10187>.

[52]
Joachim Neu, Ertem Nusret Tas, and David Tse.
Ebb-and-Flow protocols: A resolution of the availability-finality dilemma.
In SP, pages 446–465. IEEE, 2021.

[53]
Joachim Neu, Ertem Nusret Tas, and David Tse.
Two more attacks on proof-of-stake ghost/ethereum.
In ConsensusDay@CCS, pages 43–52. ACM, 2022.

[54]
Burak Öz, Benjamin Kraner, Nicoló Vallarano, Bingle Stegmann Kruger, Florian Matthes, and Claudio Juan Tessone.
Time moves faster when there is nothing you anticipate: The role of time in MEV rewards.
In DeFi@CCS, pages 1–8. ACM, 2023.

[55]
Rafael Pass and Elaine Shi.
Fruitchains: A fair blockchain.
In PODC, pages 315–324. ACM, 2017.

[56]
Rafael Pass and Elaine Shi.
The sleepy model of consensus.
In ASIACRYPT (2), volume 10625 of Lecture Notes in Computer Science, pages 380–409. Springer, 2017.

[57]
Thomas C Schelling.
The strategy of conflict.

[58]
Caspar Schwarz-Schilling, Joachim Neu, Barnabé Monnot, Aditya Asgaonkar, Ertem Nusret Tas, and David Tse.
Three attacks on proof-of-stake Ethereum.
In Financial Cryptography, volume 13411 of LNCS, pages 560–576. Springer, 2022.

[59]
Caspar Schwarz-Schilling, Fahad Saleh, Thomas Thiery, Jennifer Pan, Nihar Shah, and Barnabé Monnot.
Time is money: Strategic timing games in proof-of-stake protocols.
In AFT, volume 282 of LIPIcs, pages 30:1–30:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.

[60]
Peiyao Sheng, Gerui Wang, Kartik Nayak, Sreeram Kannan, and Pramod Viswanath.
BFT protocol forensics.
In CCS, pages 1722–1743. ACM, 2021.

[61]
Yonatan Sompolinsky and Aviv Zohar.
Secure high-rate transaction processing in bitcoin.
In Financial Cryptography, volume 8975 of Lecture Notes in Computer Science, pages 507–527. Springer, 2015.

[62]
Heinrich Von Stackelberg.
The theory of the market economy.
William Hodge, 1952.

[63]
Toni Wahrstätter.
mevboost.pics, 2024.
URL: <https://mevboost.pics/>.

[64]
Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan-Gueta, and Ittai Abraham.
Hotstuff: BFT consensus with linearity and responsiveness.
In PODC, pages 347–356. ACM, 2019.

[65]
Luca Zanolini.
Evolution of the ethereum proof-of-stake consensus protocol, 2022.
URL: <https://github.com/ethereum/pos-evolution/blob/master/pos-evolution.md>.

§ EXTENDED PRELIMINARIES

§.§ The Ethereum Reward Mechanism

Validator rewards in Ethereum originate from two sources: the execution layer reward and the consensus layer reward.
The execution layer reward refers to the total reward of a slot leader for including transactions in his block.
This can be either the sum of all priority fees included in the block or the amount that a block builder pays for buying the leader's block space in a proposer-builder-separation auction [42].
The consensus layer reward includes the incentivization reward

paid out to the validators for their participation in the consensus protocol execution.

In this paper,

we focus on the impact of consensus layer reward on the validators' behavior.
Therefore, we

describe the consensus layer reward mechanism below.

According to the Altair upgrade [2] of the beacon chain, a validator's consensus layer reward is made up of three sub-rewards [9]:

Attestation reward: A validator receives this for attesting to its view of the chain.
Let validator $\val$ be a member of the committee assigned to slot $s$.

It sends an attestation consisting of 3 different votes:

(i) the vote for a source checkpoint specified by Casper FFG,

(ii) the vote for a target checkpoint specified by Casper FFG, and

(iii) the head vote for the block specified by LMD GHOST ( Section <ref>).

Proposing reward: A slot leader receives this for proposing a block if the proposed block gets included in the beacon chain.

Sync committee reward: Every 256 epochs, a group of 512 validators is randomly selected as the members of the sync committee.
They sign every beacon chain block header published during the assigned 256 epochs to help light clients track the beacon chain.
Sync committee members receive a reward for every slot in which they sign a block.

The attestation rewards constitute the largest part, , $84.4\%$, of the consensus layer rewards [9].

For a validator to receive the attestation reward,
the attestation should be included in the beacon chain and be correct and timely as defined below [9].

Correctness implies that the attestation should agree with the view of the block proposer that includes the attestation in its block. Let an attestation belong to slot $s$ in epoch $e$. Then, formally,

The source checkpoint vote is correct if the source checkpoint vote matches the justified checkpoint of epoch $e$ (, the block root of the starting slot in epoch $e-1$ if epoch $e-1$ was justified).

The target checkpoint vote is correct if the source checkpoint vote is correct and the target checkpoint vote matches the target checkpoint of epoch $e$, , the block root of the starting slot in epoch $e$.

The head vote is correct if the target checkpoint vote is correct and the head vote matches the head of the beacon chain at slot $s$, namely the block root of slot $s$ [2].

The head vote correctness rule implies that if assuming block $B_{t+1}$ is the finalized block of slot $t+1$ in the beacon chain, then a head vote of slot $t$ is correct if and only if the head vote matches the parent root of block $B_{t+1}$.

Timeliness means that the attestation belonging to slot $s$ should get included in the beacon chain within a pre-defined slot range after slot $s$.
This range differs for the three votes included in the attestation.
Let $t_1$ represent the slot of an attestation (by a validator assigned to the slot $t_1$ committee),

and $t_2$ represent the slot at which the attestation gets included in the beacon chain.

* Head vote is timely if $t_2=t_1+1$.

* Source checkpoint vote is timely if $t_1+1 \le t_2 \le t_1+5$.

* Target checkpoint vote is timely if $t_1+1 \le t_2 \le t_1+32$ [2].

The tightest slot range belongs to the head vote timeliness: if an attestation does not get included in the next slot’s block, the validator loses the head vote reward.

To incentivize leaders to include attestations in their blocks, the proposing reward is made proportional to the total reward of the attestations and the total reward of the sync committee outputs included in the block.

As the inclusion of attestations and sync committee outputs is the only source for the proposing reward, we will use the terms "inclusion reward" and "proposing reward" interchangeably.
As we focus on head votes in the subsequent sections, we will refer to these as just votes.

§.§ Slashing

Ethereum imposes financial punishments for certain detectable protocol violations [30, 7].
If a validator is observed to have

* proposed two different blocks for the same slot, or

* sent two or more head votes with the same slot number for distinct blocks, or

* sent two pairs of votes for source and target checkpoints such that one pair surrounds the other,

then, the validator is slashed: it is removed from the validator set, and its stake is partially burned.
Slashing rules are typically used to enforce a notion of safety called accountable safety [30, 50, 60]:

A consensus protocol satisfies accountable safety with resilience $f$, if when there is a safety violation, (i) at least $f$ adversarial validators can be identified as protocol violators with the help of a cryptographic proof, and (ii) no honest validator is identified except with negligible probability.

Examples of consensus protocols with accountable safety include Ethereum, PBFT [34], Tendermint [29, 28] and HotStuff [64].
They remain safe if there are fewer than $f$ adversarial validators (as in traditional safety); since then it would not be possible to detect $f$ adversarial validators.
These protocols come with a set of slashing rules as in Ethereum; such that if a validator violates them, then it is identified as a protocol violator and slashed.
In the following sections, we assume that the rational (as well as honest) validators never satisfy any of the slashing rules of their protocols.

§.§ Reorgs

Suppose an Ethereum block $B$ proposed at some time $t'$ is no longer part of the canonical chain for the first time at some time $t \geq t'$.
Then, we say that the block $B$ is reorged at time $t$.
If $B$ proposed at some time $t'$ never becomes part of the canonical chain, it is said to be reorged at time $t'$.
Reorging of a single honestly proposed block need not imply a liveness violation.
For instance, Nakamoto consensus [46, 40] is prone to reorgs as shown by the selfish mining attack [39].
Yet, in every sufficiently large period, an honest block enters and stays in the longest chain indefinitely implying liveness under an honest majority.
Conversely, any attack that can reorg all blocks proposed during an arbitrarily long period $T$ results in a liveness violation.
If these blocks are reorged after the period $T$,

the attack would also violate safety under any reasonable confirmation rule.
Note that this does not imply a safety violation for the Ethereum blocks finalized by Casper FFG. However, the safety of LMD GHOST is necessary for the stability of the chain and liveness of Casper FFG.

Ethereum is said to satisfy reorg resilience if an honest or rational leader's block enters and stays in the canonical chain at all times.

Reorg resilience implies safety and liveness of the protocol assuming that there are frequent honest or rational leaders (as is the case in RANDAO) and their blocks are not empty.

§ PROOF OF THEOREM <REF>

Let $r$ represent the reward that an attestor receives for a correct and timely head vote included in the canonical chain. The pay-off matrix of a solo slot $t$ attestor $\val$ is presented in Table <ref>.
If over $W_p$ slot $t$ attestors vote for $B_t$, then $B_A$ extends $B_t$ and does not include any of the votes by the non-compliant attestors ($NA$-$NV_\val$ corner).
In this case, none of the votes by the compliant attestors included in $B_A$ can be correct either, as they would be for the parent of $B_t$ rather than $B_t$ itself ($NA$-$V_\val$ corner).
Thus, the payoff is $0$ for both actions $V_\val$ and $NV_\val$ when $NA$ happens.
In contrast, if less than $W_p$ slot $t$ attestors vote for $B_t$, $B_A$ extends $B_{t-1}$ and stays in the canonical chain after slot $t$.
Therefore, the compliant attestors, whose votes within $B_A$ would be correct and timely, receive a payoff of $r$ ($A$-$V_\val$ corner), whereas no votes by the non-compliant attestors are included in $B_A$, making their payoff $0$ ($A$-$NV_\val$ corner).
Hence, voting for $B_{t-1}$ weakly dominates voting for $B_{t}$ or other blocks, and the case where solo validators follow the game rule is a Nash equilibrium.

§ PROOF OF THEOREM <REF>

Suppose all solo leaders and attestors follow the adversary's game rule and propose and vote for compliant blocks in slots $1, \ldots, p$.
We show that this is a subgame perfect Nash equilibrium by backward induction.
The extended game consists of subgames played by the leaders and attestors of the slots $i \in [p]$, denoted by $\texttt{G}^L_i$ and $\texttt{G}^\val_i$ respectively.

Subgame $\texttt{G}^\val_p$: $V^\val_p$ or $NV^\val_p$?

Subgame $\texttt{G}^L_p$: $V^L_p$ or $NV^L_p$?

Subgame $\texttt{G}^\val_i$: $V^\val_i$ or $NV^\val_i$?

Subgame $\texttt{G}^L_i$: $V^L_i$ or $NV^L_i$?

Subgame perfect Nash equilibrium

The payoff matrix of a solo slot $p$ attestor $\val$ in $\texttt{G}^\val_p$ is presented in Table <ref> (Fig. <ref>).

Payoff matrix of a solo slot $p$ validator $\val$ in the extended game.
Let $V^\val_p$ denote the event that $\val$ sends a compliant vote.
Let $A^\val_p$ denote the event that all slot $p$ attestors send compliant votes.

$V^\val_p$     $NV^\val_p$

$A^\val_p$     $r$     $0$

$NA^\val_p$     $\leq r$     $0$

A non-compliant vote is never included in $B_A$ and cannot be timely, which implies a payoff of $0$ ($NV^\val_p$ column).
If $\val$ sends a compliant vote for some block $B^*$ ($V^\val_p$ column) and all slot $p$ attestors send compliant votes[In practice, the adversary can use the $\Wp$ boost of its block. Moreover, the blocks $\mathcal{A}$ tries to reorg will not all have the maximum $W$ votes, implying that not all of the $W$ slot $p$ votes will be needed.], which must be for $B^*$ as ties are broken deterministically ($A^\val_p$ row), then upon running Alg. <ref>, $\mathcal{A}$ obtains the same block $B^*$ as its compliant tip and extends it with its block $B_A$.
In this case, $\val$ gains a payoff of $r$ ($A^\val_p$-$V^\val_p$ corner).
Hence, for $\val$, sending a compliant vote weakly dominates any other action, and it follows the game rule.

Suppose the slot $p$ attestors send compliant votes.
Then, the slot $p$ leader $L$'s payoff matrix in $\texttt{G}^L_p$ is presented in Table <ref> (Fig. <ref>).
Let $R$ represent the inclusion reward that a slot leader receives for proposing a block in the canonical chain.
If $L$ proposes a compliant block $B^e_p$, all slot $p$ attestors vote for it.
Then, the compliant tip obtained by $\mathcal{A}$ includes $B^e_p$ in its prefix, which implies a payoff of $R$ for $L$ ($V^L_p$ corner).
However, if $L$ proposes a non-compliant block, the block does not gather any slot $p$ votes.
In this case, the compliant tip obtained by $\mathcal{A}$ does not include $L$'s block in its prefix, implying a payoff of $0$ for $L$ ($NV^L_p$ corner).
Thus, proposing a compliant block $B^e_p$ weakly dominates proposing any other block, and $L$ follows the adversary's game rule.

Suppose all leaders and attestors of the slots $i+1, \ldots, p$ follow the adversary's game rule, , cast compliant votes and propose compliant blocks.
Then, the payoff matrix of a solo slot $i$ attestor $\val$ in $\texttt{G}^\val_{i}$ is presented in Table <ref> (Fig. <ref>).
Since the slot $i+1$ block is compliant, a non-compliant vote would not be included in the block of slot $i+1$, and thus cannot be timely, which implies a payoff of $0$ ($NV^\val_i$ column).

When all leaders and attestors of the slots $i+1, \ldots, p$ follow the adversary's game rule, if $\val$ sends a compliant vote for some block $B^*$, ($V^\val_i$ row) and all slot $i$ attestors send compliant votes (for $B^*$, $A^\val_i$ row), all of the blocks $B^e_{j}$, $j \in \{i+1,\ldots,p\}$ and $B_A$ extend $B^*$, which implies a payoff of $r$ ($V^\val_i$-$A^\val_i$ corner).
Hence, for $\val$, sending a compliant vote weakly dominates any other action, and it follows the game rule.

Payoff matrix of the slot $p$ leader $L$ in the extended game. Let $V^L_p$ denote the event that $L$ proposes a compliant block.

$V^L_p$     $NV^L_p$

$R$     $0$

Payoff matrix of a solo slot $i$ validator $\val$ in the extended game.
Let $V^\val_i$ denote the event that $\val$ sends a compliant vote.
Let $A^\val_i$ denote the event that all slot $i$ attestors send compliant votes.

$V^\val_i$     $NV^\val_i$

$A^\val_i$     $r$     $0$

$NA^\val_i$     $\leq r$     $0$

Suppose all leaders of the slots $i+1, \ldots, p$, and all attestors of the slots $i, \ldots, p$, follow the adversary's game rule, , cast compliant votes and propose compliant blocks.
Then, the slot $i$ leader $L$'s payoff matrix in $\texttt{G}^L_i$ is presented in Table <ref> (Fig. <ref>).
If $L$ proposes a compliant block $B^e_i$, all slot $i$ attestors vote for it.
When all leaders and attestors of the slots $i, i+1, \ldots, p$ follow the adversary's game rule, all of the blocks $B^e_{j}$, $j \in \{i+1,\ldots,p\}$ and $B_A$ extend $B^e_i$, which implies a payoff of $R$ ($V^L_i$ corner).
However, if $L$ proposes a non-compliant block, the block does not gather any slot $p$ votes.
In this case, the compliant tip obtained by any subsequent leader, including $\mathcal{A}$, does not include $L$'s block in its prefix by Alg. <ref>, implying a payoff of $0$ for $L$ ($NV^L_i$ corner).
Thus, proposing a compliant block $B^e_i$ weakly dominates proposing any other block, and $L$ follows the adversary's game rule.

Payoff matrix of the slot $i$ leader $L$ in the extended game. Let $V^L_i$ denote the event that $L$ proposes a compliant block.

$V^L_i$     $NV^L_i$

$R$     $0$

Therefore, there exists a subgame perfect Nash equilibrium, where all solo leaders and attestors follow the adversary's game.
Then, the chain ending at the sequence of blocks $B^e_1, \ldots, B^e_p, B_A$ becomes the canonical chain after the end of slot $p$, and the adversary wins the game.
In this case, safety and liveness are violated since the blocks $B_{-p+1}, \ldots, B_{0}$ are reorged.

There are many subgame perfect Nash equilibria, where the adversary $\mathcal{A}$ is not successful.
Suppose the slot $i \in [p]$ leaders propose non-empty blocks $B_i$ extending the blocks $B_0, \ldots, B_{i-1}$, and over $1+W/2$ slot $i$ attestors vote for $B_{i}$.

Then, $\mathcal{A}$ is unsuccessful, and no slot $i$ vote for a block other than $B_i$ can be both correct and timely, whereas due to the adversary's commitment, no slot $p$ vote can receive a positive payoff for any action.
Thus, at each subgame,

voting for $B_i$ weakly dominates any other action for the slot $i$ committee, and

proposing a non-empty block $B_i$ extending $B_{i-1}$ weakly dominates any other action for the slot $i$ leader.
Therefore, the situation above is a SPNE.

For any $\epsilon>0$, the adversary with budget $\epsilon$ can ensure its success in all Nash equilibria by offering an $\epsilon/pW$ amount of bribe to each slot $i \in [p]$ attestor to vote for a compliant block.
This follows from a similar argument to Note <ref> applied to each subgame.

These bribes can be paid out using smart (bribery) contracts on Ethereum.

Under an honest minority assumption (, number of honest validators per slot $W_h<(W/2)$), LMD GHOST is still susceptible to the extended attack, , there might be a SPNE where the adversary succeeds.
In the extended game, the adversary can run the game for $p'=pW/(W-2W_h)$ blocks, gathering enough votes on a conflicting chain of $p'$ blocks from slots $1, \ldots, p'$ to reorg the $p$ blocks from slots $-p+1, \ldots, 0$.

§ PROOF OF THEOREM <REF>

To analyze the simple game under the fixed validator set model, we calculate the payoff matrix of a solo validator $\val$.

Recall that $r$ represents the reward of an attestor for a correct and timely head vote included in the canonical chain.

The payoff matrix of $\val$ is presented in Table <ref>.
Each entry in the table is calculated as the sum of two components: The left component represents the head vote reward of slot $t-1$, while the right component represents the head vote reward of slot $t$.
Overall, 4 different scenarios can occur:

$\mathbf{NA-NV_\val}$ corner (Fig. <ref>): $\Wp$ or more slot $t$ attestors and the validator $\val$ vote for $B_t$.
In this case, $B_t$ cannot be reorged by $B_{t+1}$, and $\val$'s vote for slot $t-1$ is included in $B_t$.
Thus, $\val$ receives a payoff of $r$ for slot $t-1$.
However, since the $\val$'s vote for slot $t$ is non-compliant,

the adversary $\mathcal{A}$ excludes $\val$'s vote from its slot $t+1$ block $B_A$.
Therefore, $\val$'s reward for slot $t$ is equal to $0$.

$\mathbf{NA-V_\val}$ corner (Fig. <ref>): $\Wp$ or more slot $t$ attestors vote for $B_t$, but the validator $\val$ does not vote for $B_t$, instead voting for $B_t$'s parent.
In this case, $B_t$ does not get reorged, and $\val$ receives a payoff of $r$ for slot $t-1$.
As over $\Wp$ slot $t$ attestors have voted for $B_t$, $\mathcal{A}$ proposes its block on top of $B_t$.
Therefore, $\val$ does not receive any payoff for its slot $t$ vote for $B_{t-1}$, as it is not correct.

$\mathbf{A-NV_\val}$ corner (Fig. <ref>): $\Wp$ or less slot $t$ attestors vote for $B_t$, but $\val$ votes for $B_t$.
Then, the attack is successful, and $B_t$ gets reorged. As a result, $\val$'s slot $t-1$ head vote reward, , payoff, is equal to $0$.
Since $\val$'s slot $t$ vote is non-compliant, its payoff for slot $t$ is also equal to $0$.

$\mathbf{A-V_\val}$ corner (Fig. <ref>): $\Wp$ or less slot $t$ attestors vote for $B_t$, and $\val$ does not vote for $B_t$.
Then, the attack is successful, and $\mathcal{A}$ reorgs $B_t$ with its block.
Since block $B_t$ gets reorged, $\val$'s payoff for slot $t-1$ is equal to $0$, but it receives a payoff of $r$ for its compliant slot $t$ vote.

Payoff matrix of a solo validator $\val$ in the simple game under the fixed validator set model. Let $V_\val$ denote the event that the solo validator $\val$ votes for $B_{t-1}$ (, $\val$ is compliant). Let $A$ denote the event that less than $\Wp$ slot $t$ attestors vote for $B_t$.

$V_\val$     $NV_\val$

$A$     $0+r$     $0+0$

$NA$     $r+0$     $r+0$

As can be seen in Table <ref>, similar to the rotating validator set model, voting for the parent block $B_{t-1}$ is a weakly dominant strategy for a solo validator under the fixed validator set model. This indicates that if rational validators constitute over $W-\Wp$ of the committees, the simple attack would be successful even under the fixed validator set model.

§ PROOF OF THEOREM <REF>

Suppose all slot $1, \ldots, p$ leaders propose compliant blocks and all slot $1, \ldots, p$ attestors vote for compliant blocks, resulting in the reorg of the blocks from slots $-p+1, \ldots, 0$.
We show that this is a subgame perfect Nash equilibrium by backward induction.

Consider the branch of actions taken by the players, in which slot $1, \ldots, p$ leaders propose compliant blocks and all slot $1, \ldots, p$ attestors except $\val$ vote for compliant blocks.
Let $B^e_p$ denote the compliant block voted upon by the slot $p$ attestors.
Then upon running Alg. <ref>, $\mathcal{A}$ obtains the same block $B^e_p$ as its compliant tip and extends it with its block $B_A$.
Now, if $\val$ sends a compliant vote, which must be for $B^e_p$ as ties are broken deterministically, then the vote is included by $B_A$, and $\val$ achieves a total payoff of $pr$.
If $\val$ does not send a compliant vote, its total payoff becomes $(p-1)r$ as $B_A$ would not include the vote.
Hence, $\val$ also sends a compliant vote for block $B^e_p$.

Since slot $p$ attestors send compliant votes, the slot $p$ leader $L$'s block becomes part of the canonical chain only if it proposes a compliant block $B^e_p$, in which case it attains a reward of $R$.
Otherwise, its reward is $0$.
Thus, it proposes a compliant block, , $B^e_p$.

Next, consider the branch of actions taken by the players, in which slot $1, \ldots, i$ leaders propose compliant blocks and all slot $1, \ldots, i$ attestors except $\val$ vote for compliant blocks.
In this case, let $B^e_i$ denote the compliant block voted upon by the slot $i$ attestors.
Then, the canonical chain at the start of slot $p+1$ contains $B^e_i$ and all the compliant blocks extending $B^e_i$ by backward induction.
Now, if $\val$ sends a compliant vote, which must be for $B^e_i$ as ties are broken deterministically, then the vote is included by the compliant block $B^e_{i+1}$ extending $B^e_i$ in the canonical chain, and $\val$ achieves a total payoff of $pr$.
If $\val$ does not send a compliant vote, its total payoff becomes $(p-1)r$ as $B^e_{i+1}$ would not include the vote.
Hence, $\val$ also sends a compliant vote for block $B^e_i$.

Since slot $i$ attestors send compliant votes, the slot $i$ leader $L$'s block becomes part of the canonical chain only if it proposes a compliant block $B^e_i$, in which case it attains a reward of $R$.
Otherwise, its reward is $0$.
Thus, it proposes a compliant block, , $B^e_i$.
This concludes the proof.

§ THE SELFISH MINING-INSPIRED ATTACK

In this section, we present an attack

that resembles the selfish mining attack [39] in Nakamoto consensus and analyze it under the fixed validator set model.
The selfish mining-inspired attack (Fig. <ref>) starts at the beginning of some slot $t$, where the number of adversarial slots in the interval $t, \ldots, t+p$ is greater than or equal to the number of its non-adversarial slots, and slot $t+p$ is adversarial.
We normalize slot $t-1$ to slot $0$.
The game has the adversary and the attestors of those slots preceding the adversarial slots in $[p]$ as its players.

Let $N_\mathcal{A}$ and $N_\mathcal{NA}$ denote the number of adversarial and non-adversarial slots within the slot range $[p+1]$.
Let $B_0$ denote the block at the tip of the canonical LMD GHOST chain at the end of slot $0$.
Let $s_i$ and $B^\mathcal{A}_i$, $i \in \{1, \ldots, N_\mathcal{A}\}$, denote the $i^\text{th}$ adversarial slot within the range $[p+1]$ and its corresponding block, respectively.
We have $N_\mathcal{A} \ge N_\mathcal{NA}$.
The attack succeeds if the canonical chain at the end of slot $p+1$ is the sequence of adversarial blocks $(B^\mathcal{A}_{1}, \ldots, B^\mathcal{A}_{N_{\mathcal{A}}})$ proposed on top of block $B_0$.
The attack fails otherwise.
The game ends, and the payoffs are realized at the end of slot $p$ at time $3p+3$.

§.§ Adversary's Action

Before slot $1$ starts, the adversary $\mathcal{A}$ generates a proof asserting its leadership in the adversarial slots within the range $[p+1]$.
Then, for the slots $s_i-1$, $i \in \{1, \ldots, N_\mathcal{A}\}$, it sets the suggested game rule $\texttt{Game}_i$ as follows:
The attestors of slot $s_i-1$ should refrain from publishing their votes at time $3(s_i-1)+1$.
They should later vote for block $B^\mathcal{A}_{i-1}$ that will be published by the adversary at a point in the time range $[3p, 3(p+1)+1]$[The time range is after all the non-adversarial blocks within $[p]$ have been published and before the voting time of slot $p+1$ starts.].

The adversary does not specify any rules for the attestors of the remaining slots.

At the start of slot $p$, when all the non-adversarial blocks within $[p]$ have been published, the adversary $\mathcal{A}$ takes the following action for $i \in \{1, \ldots, N_\mathcal{A}\}$:

* It publishes block $B^\mathcal{A}_{i-1}$ for the attestors of slot $s_i-1$ ($B^\mathcal{A}_0$ is defined to be $B_0$).

* It collects the votes submitted by the attestors of slot $s_i-1$ for block $B^\mathcal{A}_{i-1}$ and inserts them into the block $B^\mathcal{A}_{i}$ as compliant votes.

Before time $3(p+1)+1$, the adversary publishes the sequence of adversarial blocks $B^\mathcal{A}_{i}$, $i \in [N_\mathcal{A}]$ proposed on top of block $B_0$ for all the validators. The adversary delays publishing the adversarial fork until the end of the interval because if the adversary publishes its fork anywhere in the middle of the interval, the remaining slot leaders may propose their blocks on top of the adversarial chain and avoid getting reorged.

§.§ Analysis

Let the non-adversarial fork be the fork containing blocks published by the non-adversarial validators by the end of slot $p$, and the adversarial fork be the sequence $(B^\mathcal{A}_{1}, \ldots, B^\mathcal{A}_{N_{\mathcal{A}}})$.
If the attestors of all slots $s_i-1$, $i \in [N_\mathcal{A}]$ are incentivized to follow the adversary's game rule rather than the honest protocol, the weights of the non-adversarial fork and the adversarial fork at time $3(p+1)+1$ will be equal to $N_\mathcal{NA}W$ and $N_\mathcal{A}W+\Wp$, respectively.
Then, if $N_\mathcal{A}\ge N_\mathcal{NA}$, the weight of the adversarial fork will be higher, and the attack will succeed.
In the following theorem, we show that a solo validator is incentivized to follow the game rule.

There exists a Nash equilibrium of the selfish mining-inspired game

under the fixed validator set model, where the adversary succeeds.

The payoff matrix of a solo validator $\val$ in the selfish mining-inspired game under the fixed validator set model is presented in Table <ref>.

Payoff matrix of a solo validator $\val$ in the selfish mining-inspired game under the fixed validator set model.

Let $V_\val$ denote the events that the validator $\val$ follows the adversarial game rule.
Let $A$ denote that the adversarial fork at time $3(p+1)+1$ outweighs the non-adversarial fork.

$V_\val$     $NV_\val$

$A$     $N_\mathcal{A}r$     $0$

$NA$     $N_\mathcal{NA}r$     $N_\mathcal{NA}r$

Following the game rule weakly dominates following the honest protocol. Therefore, a solo validator follows the game rule under the fixed validator set model, resulting in the adversary's success.

There are Nash equilibria, where the adversary $\mathcal{A}$ is not successful.
However, if in a slot interval, the number of adversarial slots is strictly greater than the number of non-adversarial ones, the selfish mining-inspired attack gives a higher payoff to the attestors in the equilibria it succeeds.

This implies that unlike in the extended attack, even coordination of strategies and forming stake pools might not be sufficient to disincentivize validators from following the game rules.
Furthermore, given an honest minority, Ethereum is still susceptible to the simple attack in the fixed validator set model assuming that there are sufficiently more adversarial slots within the slot range.

The existence of a Nash equilibrium of the selfish mining-inspired game implies that under the current Ethereum reward mechanism, none of the provably secure alternatives to LMD GHOST that retain its slot-based structure and heaviest-tree-based fork-choice rule can offer greater security than the predictable longest-chain fork choice rule of Nakamoto consensus.

§ PERFORMANCE COMPARISON: THE OPTIMISTIC SCENARIO

Block space: As of January 23, 2024, each block of Ethereum contains 128 aggregated attestation signatures as well as 128 aggregation lists, where the size of each signature and each aggregation list is equal to 96 bytes and $N^\text{att}=443$ bits, respectively. Therefore, the total size of an aggregate

in a single block is 19.376 kilobytes.
The average Ethereum block size for the last 30 days ending on January 23, 2024 is around 170 kilobytes [5].

Under the optimistic scenario, each block includes $128$ aggregated evidences for an earlier slot (one per sub-committee in the earlier slot). Each piece of aggregated evidence comprises 4 parts: the aggregated evidence signature ($96$ bytes), the evidence aggregation list ($N^\text{agg}$ bits), the aggregated attestation signature ($96$ bytes), and the attestation aggregation list ($N^\text{att}$ bits).
Assuming that $N^\text{att}=443$, the total size of aggregated evidences in each block is equal to $31.664+ 0.016*N^\text{agg}$ kilobytes.
Suppose the parameters $N^\text{agg}$ and $N^\text{limit}$ are set such that the probability that the number of non-adversarial aggregators in a sub-committee becomes less than or equal to $N^\text{limit}$ is less than $10^{-4}$.

* Assuming the adversarial stake share is less than or equal to $0.1$, $N^\text{agg}$ and $N^\text{limit}$ can be set to 16 and 8, respectively. In this case, the total size of evidences in a single block would be equal to $31.92$ kilobytes. This results in a 7.37% increase in the block size.

* Assuming the adversarial stake share is less than or equal to $1/3$, $N^\text{agg}$ and $N^\text{limit}$ can be set to 128 and 64, respectively. In this case, the total size of evidences per block would be equal to $33.712$ kilobytes, resulting in an 8.43% increase in the block size.

Computational overhead: We assume $N^\text{att}=443$ and $N^\text{agg}=16$. Let $C^\text{add}$, $C^\text{mul}$, and $C^\text{pair}$ denote the computational cost of an addition, a scalar multiplication, and a pairing operation over the elliptic curve, respectively.

Aggregators: In the current Ethereum version, an aggregator must first verify the $N^\text{att}$ single attestation signatures of the corresponding sub-committee, where each signature verification requires $2$ pairing operations.
Then, the aggregator has to perform $N^\text{att}-1$ additions over the elliptic curve to aggregate attestations and $1$ scalar multiplication over the elliptic curve to sign the aggregated attestation. Therefore, its computational cost becomes $2N^\text{att}C^\text{pair}+(N^\text{att}-1)C^\text{add} + C^\text{mul}$.
In the practical version of our solution, in addition to these operations, a slot $t$ aggregator must verify and sign $1$ aggregated attestation (the one that includes the greatest number of attestations) from slot $t-1$ to generate an evidence.
The aggregated attestation can be verified by checking its aggregated signature that contains the signatures of the attestors in the corresponding sub-committee from slot $t-1$.

To check this signature combining $N^\text{att}$ individual signatures, a verifier needs to perform $N^\text{att}-1$ additions over the elliptic curve to calculate the aggregated public key of the participating attestors, along with 2 pairing operations. Thus, an aggregator's computational cost in our practical version becomes $2(N^\text{att}+1) C^\text{pair} + 2(N^\text{att}-1)C^\text{add}+ 2C^\text{mul}$. Based on our implementation results[These results were achieved through implementation on a laptop equipped with an Intel Core i7 CPU operating at a processor base frequency of 2.70GHz.], this computation takes 0.59 seconds.

Block proposers: In our practical version, each block proposer needs to verify and aggregate $N^\text{agg}$ evidences per each sub-committee to generate an aggregated evidence, in addition to standard operations of the current Ethereum. The computational costs of verification and aggregation of evidences per sub-committee are equal to $2N^\text{agg}C^\text{pair}$ and $(N^\text{agg}-1)C^\text{add}$, respectively. As the number of sub-committees per slot is $64$, a block proposer in total incurs an additional computational cost of $128N^\text{agg}C^\text{pair}+64(N^\text{agg}-1)C^\text{add}$. Based on our implementation results, this additional computation takes $1.36$ seconds.

Verifiers: To verify the consensus layer-related data of a block in the current Ethereum version, a verifier must check $64$ aggregated signatures, each belonging to one of the sub-committees. This results in a total computational cost of $64(N^\text{att}-1)C^\text{add} + 128C^\text{pair}$. In our practical version, in addition to this verification, a verifier must verify $1$ aggregated evidence per each sub-committee, where each aggregated evidence contains $N^\text{agg}$ evidences. All the evidences of a sub-committe are created over the same aggregated attestation that includes $N^\text{att}$ attestations. This implies that the evidence verification cost per sub-committee is equal to $(N^\text{att}+N^\text{aagg}-2)C^\text{add} + 4C^\text{pair}$. Therefore, and a verifier incurs the computational cost of $64(2N^\text{att}+N^\text{agg}-3)C^\text{add} + 384C^\text{pair}$ in the practical version. Based on our implementation, this computation takes $0.38$ seconds.

§ PERFORMANCE COMPARISON: THE WORST CASE SCENARIO

The worst-case scenario happens if the slot $t+1$ block is missing or has excluded the attestations, and the slot $t+1$ aggregators sign different aggregates.
Processing these diverse evidences can impose additional overheads on the blockchain network.
In the following, we present the analysis of the overheads incurred by our solution in the worst-case scenario:

Block space:
In the worst-case scenario, each block includes $128*N^\text{agg}$ individual evidences ($N^\text{agg}$ evidences per each sub-committee). Each piece of individual evidence comprises 3 parts: the evidence signature ($96$ bytes), the aggregated attestation signature ($96$ bytes), and the attestation aggregation list ($N^\text{att}$ bits).
Assuming that $N^\text{att}=443$, the total size of evidences in each block is equal to $31.664*N^\text{agg}$ kilobytes.
Suppose the parameters $N^\text{agg}$ and $N^\text{limit}$ are set such that the probability that the number of non-adversarial aggregators in a sub-committee becomes less than or equal to $N^\text{limit}$ is less than $10^{-4}$.

* Assuming the adversarial stake share is less than or equal to $0.1$, $N^\text{agg}$ and $N^\text{limit}$ can be set to 16 and 8, respectively. In this case, the total size of evidences in a single block would be equal to 506.624 kilobytes.

* Assuming the adversarial stake share is less than or equal to $1/3$, $N^\text{agg}$ and $N^\text{limit}$ can be set to 128 and 64, respectively. In this case, the total size of evidences in a single block would be equal to $4.053$ megabytes.

Computational overhead: We assess the computational overhead under the worst-case scenario from the perspective of the following parties:

* Aggregators: It is similar to the optimistic scenario.

* Block proposers: In the worst-case scenario, each block proposer needs to verify $N^\text{agg}$ evidences per each sub-committee to generate an aggregated evidence, in addition to standard operations in the current Ethereum version. The computational cost of evidence verification per sub-committee is equal to $2N^\text{agg}C^\text{pair}$. As the number of sub-committees per slot is equal to $64$, a block proposer in total incurs an additional computational cost of $128N^\text{agg}C^\text{pair}$.

* Verifiers: Under the worst-case scenario, in addition to the existing verification process in the current Ethereum version, a verifier needs to verify $N^\text{agg}$ single evidences per each sub-committee, where each single evidence is created over an aggregated attestation that includes $N^\text{att}$ attestations. This implies that the evidence verification cost per sub-committee is equal to $(N^\text{att}-1)N^\text{agg}C^\text{add} + 4N^\text{agg}C^\text{pair}$. Therefore, a verifier incurs the computational cost of $64(N^\text{att}-1)(N^\text{agg}+1)C^\text{add} + 64(2+4N^\text{agg})C^\text{pair}$ in the worst-case scenario.

Communication overhead is the same as the optimistic case.

§ SIMPLE ATTACK WITHOUT PROPOSER BOOST

Assume $\Wp=0$. The attack applies to some slot $t$ where slots $t-1$ and $t+1$ are adversarial. Let $B_0$ denote the latest block within the canonical chain before the start of slot $t-1$. In this attack, the adversary does not publish block $B^\mathcal{A}_{t-1}$ at slot $t-1$ and delays publishing it to the next slot. At the beginning of slot $t$, when the leader of slot $t$ proposes block $B_t$ on top of block $B_0$, the attacker simultaneously publishes its block $B^\mathcal{A}_{t-1}$ proposed on top of $B_0$. The adversary sets the game rule for the attestors of slot $t$ as follows: "The attestors of slot $t$ should vote for the block $B^\mathcal{A}_{t-1}$. Otherwise, their head votes will not be included in the block of slot $t+1$". At the start of slot $t+1$, adversary $\mathcal{A}$ takes the following action:

* If over half of slot $t$ attestors vote for $B_{t}$, it proposes its block $B^\mathcal{A}_{t+1}$ on top of block $B_{t}$ and refrains from including the non-compliant votes. In this scenario, $\mathcal{A}$ is unsuccessful.

* If over half of slot $t$ attestors vote for $B^\mathcal{A}_{t-1}$, it proposes its block $B^\mathcal{A}_{t+1}$ on top of block $B^\mathcal{A}_{t-1}$ and includes the compliant votes. Then, $\mathcal{A}$ is successful.

Using the same analysis as presented in Section <ref>, one can show as long as more than half of slot $t$ attestors are rational, the adversary can succeed in the simple attack without proposer boost. If $\Wp>0$, this attack can succeed even with fewer than 50% rational attestors.

§ IMPACT OF FUTURE ETHEREUM CHANGES

In this section, we analyze the impact of potential future changes in the Ethereum protocol [6] on our attacks.
None of these modifications can mitigate the attack.
The attack can even become more destructive with certain changes, such as single-slot finality.

§.§ [block, slot]-voting [3]

In the current Ethereum, if no block is proposed during a slot, the slot's assigned committee votes for the previous slot's block as the head block.
In the [block, slot]-voting mechanism, the attestors of a slot with no block vote on an empty slot.
The [block, slot]-voting might be adopted by the Ethereum protocol in the future as it

facilitates the implementation of an in-protocol proposer-builder-separation mechanism.

A slightly modified version of our attack is still applicable to the protocol with the [block, slot]-voting mechanism.
For instance, in the simple game of Section <ref>, the game rule only needs to specify “the attestors of slot $t$ to vote for the empty slot" rather than the previous block.
Similarly, the extended game would stipulate the attestors to vote for empty slots during slots in $[p]$.

§.§ Secret Leader Election (SLE) [10]

Currently, the list of upcoming block proposers in Ethereum is public, meaning that a validator can predict future slot leaders.
SLE can ensure that only the selected slot leader knows its role as a block proposer in one of the upcoming slots.
SLE can improve the resistance of Ethereum against the denial-of-service (DOS) attack.

SLE cannot mitigate our attack as the attacker only needs to be aware of the future time slots in which they themselves are selected as the slot leader, which is feasible even with the adoption of SLE.
Moreover, the attack could still be modified to work under protocol changes where leaders themselves do not know their slots until the slot starts.
For instance, the adversary could deploy a contract that commits to rewarding a slot $t$ attestor, whenever the attestor can prove that the adversary is the leader of some slot $t+1$ and that the attestor satisfies the compliance conditions with its slot $t$ votes.
The contract can also be permissionlessly triggered to slash the adversary if it happens to exclude compliant votes.

§.§ In-protocol Proposer–Builder Separation (ePBS) [8]

Currently, Ethereum proposers (slot leaders) are responsible for creating a bundle of transactions and including them in the proposed block.
They may decide to outsource the responsibility of bundle building to builders operating outside of the Ethereum protocol.
In this context, ePBS is a prominent direction (among many [15]) considered for the future of MEV allocation.
It splits the task of building a transaction bundle and proposing a block between two validators: a block builder and a block proposer.
Block builders become responsible for creating transaction bundles and offering them to block proposers.
Block proposers become responsible only for proposing and sending out the blocks to peers on the network without knowing the content of the included transaction bundle.
ePBS can offer a fairer distribution of MEV opportunities [4].

Our attack can also threaten the ePBS version of Ethereum.
A malicious slot $t$ leader can incentivize the attestors of slot $t-1$ to vote on an unrevealed transaction bundle.
By doing so, the victim block builder of slot $t-1$, who has published his transaction bundle honestly, may get penalized, and the included MEV in the victim transaction bundle can be stolen.

§.§ Single-Slot Finality [13]

In present-day Ethereum, which uses Casper FFG as finality gadget, a block has to wait for 2 epochs to get finalized.
The concept of single-slot finality aims to achieve the goal of finalizing blocks within the same slot they were proposed.
It can thus significantly reduce the transaction confirmation time.

The security of protocols with single-slot finality [38] can be proven based on the honest majority assumption for online validators [12].
In our attacks, the adversary need not control any majority.

Thus, the attacks would succeed in creating equilibria, where liveness can be violated for arbitrarily long slot sequences, on Ethereum with single-slot finality as long as the majority of the validators are profit-maximizing (rational) agents.
Even though the attacks would not be able to reorg a long sequence of finalized blocks (recall that in the case of LMD GHOST, a long sequence could be reorged before the Casper FFG finalizations catch up, , Section <ref>),
if the adversary is only interested in violating liveness but not safety, with an $\epsilon>0$ bribe, it can ensure that in all subgame perfect equilibria, a long sequence of empty blocks are finalized.

§ ECONOMICS OF

Although enables timely votes to be rewarded eventually, it does not prevent an adversary controlling multiple blocks from delaying the inclusion of the slot $t$ evidences in the canonical chain, and in turn the reward allocated to the slot $t$ attestors.
In this case, the reward might have to be discounted over time, giving the adversary some power to influence attestation rewards.
However, we ignore this factor as Ethereum blocks are frequent (every $12$ seconds), and the discount factor derived for current interest rates is not large over short time scales.
Moreover, such an adversary can prevent information about votes from being included in the blocks in any given reward mechanism, making this a problem of leader-based protocols with a single leader, rather than the reward mechanism per se.