# Aegis: A Decentralized Expansion Blockchain

Yogev Bar-On‡${}^{\includegraphics[width=0.5em]{eoracleLogoSmallBlack.png}}$,
Roi Bar-Zur⋆${}^{\includegraphics[width=0.5em]{eoracleLogoSmallBlack.png}}$,
Omer Ben-Porat⋆,
Nimrod Cohen${}^{\includegraphics[width=0.5em]{eoracleLogoSmallBlack.png}}$,
Ittay Eyal⋆, Matan
Sitbon${}^{\includegraphics[width=0.5em]{eoracleLogoSmallBlack.png}}$
‡Tel Aviv University
${}^{\includegraphics[width=0.5em]{eoracleLogoSmallBlack.png}}$Eoracle
⋆Technion

###### Abstract

Blockchains implement monetary systems operated by _committees_ of _nodes_.
The robustness of established blockchains presents an opportunity to leverage
their infrastructure for creating _expansion chains_. Expansion chains can
provide additional functionality to the _primary_ chain they leverage or
implement separate functionalities, while benefiting from the primary chain’s
security and the stability of its tokens. Indeed, tools like Ethereum’s
EigenLayer enable nodes to stake (deposit collateral) on a primary chain to
form a committee responsible for operating an expansion chain.

But here is the rub. Classical protocols assume correct, well-behaved nodes
stay correct indefinitely. Yet in our case, the stake incentivizes
correctness—it will be slashed (revoked) if its owner deviates. Once a node
withdraws its stake, there is no basis to assume its correctness.

To address the new challenge, we present _Aegis_ , an expansion chain based on
primary-chain stake, assuming a bounded primary-chain write time. Aegis uses
references from Aegis blocks to primary blocks to define committees,
checkpoints on the primary chain to perpetuate decisions, and resets on the
primary chain to establish a new committee if the previous one becomes
obsolete. It ensures safety at all times and rapid progress when latency among
Aegis nodes is low.

##  1 Introduction

Blockchains like Ethereum [55] implement monetary systems and allow users to
deploy _smart contracts_ [51] with arbitrary logic. The users issue
_transactions_ to exchange assets and interact with smart contracts.
Blockchain  _nodes_ aggregate transactions into blocks, forming a chain that
determines the system’s state. But blockchains have limited throughput, often
high latency, and are limited to deterministic execution. Numerous systems
expand a _primary blockchain_ in various ways [31]: Some offload computation
to improve performance and reduce costs [49, 27]. Others aggregate exogenous
data from various sources to enable smart contracts to interact with real-
world information, also termed _oracles_ [15, 22]. Additionally, certain
systems focus on seeding verifiable randomness to support applications that
require unpredictable and tamper-proof random number generation [14].

In some cases, it is possible to implement an expansion as a separate _Proof
of Stake (PoS)_ blockchain. PoS protocols allow users to _stake_ —lock their
tokens as collateral [30, 17, 18]. Until they _unstake_ —withdraw the
collateral—they are _active_ nodes, allowed to create new blocks. If they
misbehave, they are penalized via _slashing_ [11], losing all or part of their
collateral. This approach works well for major blockchains that have reached a
critical mass of participants and assets [1]. However, smaller nascent systems
do not have sufficient reputation to rely on long-term participation of
established nodes. Such nodes help new nodes that join the system to overcome
long-range attacks [10, 19], where an adversary presents an alternative
history, indistinguishable from the true one. Additionally, in smaller
systems, the value of tokens and hence the collateral amounts are volatile,
leaving the system vulnerable to hijacking by a well-funded adversary.

To overcome this, stake can be managed on the primary blockchain, taking
advantage of its decentralization and reliability: The nodes maintaining the
expansion blockchain lock their stake on the primary chain. They agree on the
series of blocks using a consensus protocol [13]. Tools for such staking
already exist in prominent blockchains like EigenLayer [53] on Ethereum and
Subnets [32] on Avalanche [45]. If nodes misbehave, they are penalized by
losing their deposit on the primary chain. The underlying consensus protocol
guarantees safety and liveness assuming that a sufficient majority of nodes
are _correct_ , i.e., follow the protocol.

Prior work (§2) extensively explored _reconfiguration_ of nodes in Byzantine
Fault Tolerant (BFT) systems [37], assuming correct nodes remain correct
indefinitely. But, at least in our case, this does not hold. A user can
unstake on the primary chain at any time, removing their collateral and hence
their incentive to follow the expansion chain protocol. Therefore, a node that
is active when it is defined in a primary block might not be active by the
time an Aegis block is generated. Additionally, like the aforementioned PoS
protocols, such an expansion chain is vulnerable to long-range attacks.

To address both challenges, we first outline a model (§3). Nodes stake and
unstake using the primary chain. Unstaking does not immediately withdraw the
stake, but only after a delay $\Delta_{\textit{active}}$. A set of nodes that
have stake locked at the same time are called a _committee_. Until any of them
completed unstaking, the committee is _active_. As is standard [30, 43], we
assume that at all times a sufficient majority of the nodes in each active
committee are correct. Communication among the nodes is asynchronous until an
unknown time $t_{\textit{GST}}$, after which message propagation is bounded,
as in the partial synchrony model [21]. Nevertheless, at all times, a node can
read the current state of the primary chain (as when running an Ethereum node)
and write to it in bounded time (cf. [29]).

We present Aegis111Named after the powerful divine shield carried by Zeus and
Athena in Greek mythology, which first appears in Homer’s Iliad. (§4), an
expansion blockchain that derives its security from a primary chain. It could
be used to provide additional functionality to a primary chain or generally
for a blockchain unrelated to the primary chain, other than using its tokens
as collateral.

The protocol includes a primary-chain contract that allows nodes to checkpoint
the Aegis state. The nodes construct a blockchain in which each _Aegis block_
references both its predecessor and a corresponding _primary block_ (Figure
1). The committee defined by that primary block is the committee in charge of
generating the next Aegis block using a consensus protocol. While maintaining
the Aegis chain, its nodes occasionally checkpoint the latest block with the
primary-chain contract. In the happy flow, the checkpoints are less than
$\Delta_{\textit{active}}$ apart, so there is always an active committee.

Aegis chainPrimary
chain…$A1$$A2$$A3$$A4$$A5$$A6$$A7$…$//$…$P1$$P2$$P3$$P4$$P5$$P6$$P7$$P8$…$//$$\Delta_{\textit{active}}$$//$resetrefrefrefrefrefrefresetrefchkchkchk

Figure 1: Aegis and primary-chain blocks.

However, adding a block might take too long. Then, the next block’s creation
stretches beyond the $\Delta_{\textit{active}}$ window, and there is nothing
to checkpoint as there are no new blocks. In this case, any Aegis node can
issue a _reset_ on the primary chain to specify a new committee. At this
point, the committee is defined in the primary-chain reset, but not yet in any
Aegis block, until one is generated. The risk is that the committee defined by
the reset and the one defined by the previous block both generate a block at
the same height (distance from chain root), forming a so-called _fork_. To
prevent that, both the protocol and the primary-chain contract enforce timing
constraints, avoiding consensus decisions that cannot be checkpointed and
premature resets.

To prove the security of the protocol (§5) we show that correct Aegis nodes
never disagree on the blockchain content at any height. First, we use backward
induction to show that if a block is created by an active committee, then all
of its ancestors were created by active committees. This holds because this is
verified for every block either by its child’s committee or by the primary
blockchain in a checkpoint. Then, using forward induction, we show that if all
nodes agree up to some height, a classical consensus protocol guarantees the
necessary properties for the next block. Similar arguments show validity,
namely that if all nodes are correct and have the same input value, no other
value is logged. We then show that after $t_{\textit{GST}}$ the protocol
guarantees an active committee forms and extends the blockchain.
Straightforward indistinguishability arguments bridge the gap between the
static committee of the standard consensus protocol and the dynamic committees
of Aegis.

Aegis can be readily implemented to decentralize various services as expansion
chains. We conclude (§6) with practical considerations for performance and
security.

##  2 Related Work

To the best of our knowledge, previous work on dynamic committees and
reconfiguration in BFT systems did not consider nodes that stop being correct
after their tenure. Various work on expansion chains addressed the problem
under this assumption (§2.1) and overcoming long-range attacks with
checkpointing (§2.2). Others utilize multiple chains to form a new one (§2.3).
Aegis can be used by Layer-2 rollups that aggregate transactions (§2.4), but
it solves a distinct problem.

###  2.1 Expansion Chains

Expansion chains are blockchains that rely on a primary chain for security.
They can be implemented using EigenLayer [53], Avalanche subnets [32] and
Polygon 2.0 [36]. Compared to a new blockchain, an expansion chain is easier
to bootstrap, as it can rely on the security of the primary chain. Nodes can
be required to stake on the primary chain, using its tokens as collateral to
ensure their good behavior. Due to the established security of the primary
chain, the value of its tokens is more stable, and the nodes are more likely
to remain correct.

On the surface, securing an expansion chain seems like the classical State
Machine Replication (SMR) [38] with dynamic committee _reconfiguration_ [37].
Essentially, the committee for expansion block $k$ agrees not only on the
block but also on the committee for the subsequent expansion block $k+1$, as
defined in a primary block. However, this approach relies on an assumption
that does not hold in our case, namely, that a correct node remains correct
indefinitely. But the generation of expansion block $k+1$ could take
arbitrarily long; meanwhile, the members of its committee might unstake in the
primary chain, so they are no longer incentivized by collateral. The result is
either a deadlock (if we ignore blocks by a deprecated committee) or a block
generated by a committee that is no longer incentivized to follow the
protocol. Aegis addresses this issue by using references from the expansion
blocks to the primary blocks to define the committee for the next block, and
allowing for a reset if the committee becomes obsolete before it generates a
block.

BMS [50] is a mechanism for secure reconfiguration of blockchains via a
trusted platform that manages reconfiguration process. However, it requires
expansion chains to approve each reconfiguration, which is not always
possible: If a node wishes to withdraw their stake, it is not generally
acceptable to wait for such an approval, particularly if the expansion chain
is asynchronous and the time is unbounded. Aegis does not require such
approval, and nodes can independently withdraw without affects its security.

Avalanche subnets [32] are blockchains whose validators are defined, added and
removed by transactions on a primary chain. Avalanche proposes this mechanism
and facilitates open participation in its so-called elastic subnets.
EigenLayer [53] allows Ethereum validators to _restake_ their Ethereum-
protocol deposits, committing to validating a secondary system with the same
stake used for Ethereum, meaning that the same deposit can be slashed due to
misbehavior in either system. Both mechanisms provide a new tool for creating
expansion protocols, but leave open the question of securing the protocol,
which Aegis addresses as mentioned above.

Polygon 2.0 [36] secures a secondary blockchain using Ethereum as primary
blockchain. It uses staking on Ethereum to define the nodes maintaining
separate blockchains. However, it encounters the aforementioned issue of SMRs
with dynamic reconfiguration, meaning its security implicitly relies on either
synchronous communication among Polygon nodes or that correct nodes remain
correct indefinitely. This is because node set changes are events on Ethereum
[34] and are voted in Polygon [35]. Therefore, if it can take arbitrarily long
to reach consensus and members are not indefinitely correct, by the time they
reach consensus they might not be correct. In contrast, Aegis does not rely on
either assumption, while always ensuring safety and ensuring progress after
$t_{\textit{GST}}$.

Merge-mining is another approach to secure expansion blockchains [8]. It is a
technique for Proof-of-Work (PoW) systems [39, 48], where nodes are called
_miners_ and they generate blocks by guessing hash preimages. In merge-mining,
a Proof of Work miner mines on two PoW blockchains with the same computational
power: each hash it calculates can result in a block for either chain. This
allows the computational power securing a major PoW chain to also secure an
expansion chain. However, if a miner misbehaves when generating an expansion
chain block, it suffers no penalty on the main chain, which remains oblivious.
In Aegis such misbehavior is penalized, so nodes are strongly incentivized to
follow the protocol.

###  2.2 Long-Range Attacks and Checkpoints

Long-range attacks are a type of attack where an adversary presents an
alternative history, indistinguishable from the true one, to the network. This
can be used to double-spend coins, or to prevent the network from reaching
consensus. Newcomers to the network are vulnerable to these attacks, as they
do not have the full history of the blockchain.

Long-range attacks are possible in both PoW and PoS blockchains. In PoW, an
adversary performing a long-range attack is required to hold a majority of the
computational power, and use it to mine a longer chain than the honest chain.
However, this form of attack is more severe in PoS, as it doesn’t require
significant computational power, only a majority of the stake at a given time.
This is exacerbated by the fact that old nodes, who have already withdrawn
their stake, are no longer at risk of being slashed.

Previous work has explored  _checkpoints_ to prevent long-range attacks. Every
several blocks, a block is checkpointed by nodes, in order for newcomers to
later retrieve the latest checkpoint to be able to distinguish between the
current chain and a long-range attack. Earlier work considered social
consensus [6, 10, 17], where a committee of participants, independent of the
blockchain, agrees on the current state of the blockchain and communicates it
to others via some external medium. Later, some works utilized a BFT consensus
protocol to perform the checkpointing [44, 46]. Afterward, the idea of using a
separate proof-of-work blockchain to timestamp checkpoints was introduced [28,
4, 52]. These works suggested injecting a digest of the checkpoint into a
secure PoW blockchain as a transaction, thus timestamping the checkpoint.
Another related work is Winkle [3], which suggests weighing checkpoints based
on the volume of transactions which were place in blocks following the
checkpoint.

Similarly, Aegis enjoys protection from long-range attacks due to its
checkpoints. But unlike them, even if the expansion chain is stalled,
reconfiguration occurs in the primary chain, and Aegis ensures that this will
be reflected in the expansion chain. None of the aforementioned solutions can
guarantee this property, as they all implement reconfiguration within the
expansion chain.

###  2.3 Chain Combining

Fitzi et al. [23] and Wang et al. [54] combine multiple ledgers to create a
ledger with better properties. However, unlike Aegis, all steps are taken
within the ledgers, unlike Aegis, whose expansion chain can progress by
expansion-chain consensus steps that are not immediately checkpointed.

###  2.4 Layer-2 Blockchains

Various systems utilize a trusted primary blockchain to validate and secure
second-level applications. This includes rollups that increase the primary
chain’s throughput, and offer lower latency and cost using _optimistic_ [27,
2, 40] and _zero-knowledge_ [49, 33] methodologies. Gudgeon et al. [26]
provide a comprehensive systemization of knowledge. However, while the
validity of the operations of those systems is guaranteed by the underlying
blockchain, their content is, by and large, approved by centralized services
[33, 40]. In contrast to those solutions, Aegis implements a decentralized
sequencing mechanism, which can be used by any of those rollups together with
their on-chain validation mechanisms.

Other solutions include so-called _sidechains_ and _payment channels_.
Sidechains (e.g., [41, 25]) are independent blockchains with mechanisms to
transact with a primary chain, but their security is independent of the
primary chain, unlike the expansion chain in Aegis. Payment channels are
point-to-point channels [42, 20], which can aggregate several payments between
two parties. These can also be used to form a payment network, allowing
payments between any two parties in the network, without the need for a direct
channel between them. But, as each channel is exclusively controlled by its
two counterparties, payment channels are not decentralized, like Aegis.

##  3 Model

The system (§3.1) includes a primary blockchain and a set of nodes. We assume
a generic consensus algorithm (§3.2) that the nodes use aiming to form a
secondary blockchain (§3.3). Appendix A summarizes the notation.

###  3.1 Principals and Network

The system comprises an unbounded set of nodes (as in [30, 43]) and a _primary
blockchain_ (or simply _primary_) denoted by $\underline{\mathcal{L}}$. Time
progresses in steps. In each step a node receives messages from previous
steps, executes local computations, updates its state, and sends messages.

The primary chain is implemented by a trusted party that maintains a state
including token balance for each node and a so-called _staked amount_ for each
node. Initially, each node has some initial token balance and zero staked
tokens. The primary also maintains node-defined _smart contracts_ implementing
arbitrary automatons. Nodes interact with the primary by issuing transactions
that update its state and interact with smart contracts. The primary chain
aggregates transactions into _blocks_ and extends the blockchain at set
intervals. Its state is the result of parsing the series of all transactions.
A node cannot guess the hash of a future block except with negligible
probability.

A node can issue a transaction to _stake_ , i.e., deposit some of their
tokens, or _unstake_ , i.e., order the withdrawal of tokens she had previously
staked. Unstaking completes $\Delta_{\textit{active}}$ steps after the order
transaction is placed in the chain. While a node’s tokens are staked, the node
is considered _active_. During this period, a node can either follow the
protocol (and be considered _correct_) or misbehave arbitrarily. Correct nodes
adhere to the protocol while they are staked, if misbehavior could result in
losing their stake. However, once they unstake, they are no longer bound by
the protocol and can behave arbitrarily without risk of losing their stake.

The set of nodes that have staked but not yet unstaked after a specific block
is called a _committee_ ; until the time any of them completed unstaking, the
committee is _active_. In all committees, the ratio of stake held by correct
nodes is assumed to be greater than a constant threshold, denoted by $\alpha$.

Communication among nodes is reliable and partially synchronous: There exists
a time $t_{\textit{GST}}$, unknown to the nodes, and message delivery is only
bounded after it. That is, if a message is sent at time $t$ then it arrives at
all nodes by time ${\max(t,t_{\textit{GST}})+\Delta_{\textit{prop}}}$. In
particular, blocks published by the nodes are delivered to all nodes, even
those that join much later.222In practice [7], this network is implemented by
the nodes’ peer-to-peer network, where nodes keep all published blocks
available.

After $t_{\textit{GST}}$ the set of active nodes stabilizes, no one stakes or
unstakes.

Communication with the primary chain is synchronous: All nodes observe the
current state of the network and can issue transactions that are added to the
blockchain within a bound $\Delta_{\underline{\mathcal{L}}\textit{-write}}$.
In practice, this assumption is achieved by choosing conservative bounds for
primary-chain writes.

###  3.2 Consensus Algorithm

We assume we are given an asynchronous (single-instance) Byzantine fault
tolerant consensus protocol (e.g., [9, 12]) implemented in a function
consensusStep. Called by a process, consensusStep takes steps in the protocol,
maintaining a local state as necessary. It is executed by a weighted set of
nodes $\mathcal{N}$, given as a parameter. (We will later use the staked
amount as the weight, thus $\mathcal{N}$ will constitute a committee.) It
takes a consensus instance ID, which is a pair of the set of nodes
$\mathcal{N}$ and a nonce id to distinguish different instances. It also takes
a block $b$ the caller wishes to propose. It returns either a block if it
reached a decision or $\bot$ otherwise:
$\textit{consensusStep}(b;\mathcal{N},\textit{id})\rightarrow\textit{block}\textup{
or }\bot$.

If starting at $t_{0}$, the nodes in $\mathcal{N}$ call consensusStep in every
step $t\geq t_{0}$ with the same $(\mathcal{N},\textit{id})$ and the aggregate
weight of correct nodes (those who follow the protocol) is greater than
$\alpha$, then the following guarantees hold.

Agreement

For all correct nodes ${i,j}$ (maybe $i=j$) and times $t,t^{\prime}$ (maybe
${t=t^{\prime}}$), if node $i$’s consensusStep call at step $t>t_{0}$ with ID
$(\mathcal{N},\textit{id})$ returns $b\neq\bot$ and node $j$’s consensusStep
call at step $t^{\prime}>t_{0}$ with ID $(\mathcal{N},\textit{id})$ returns
$b^{\prime}\neq\bot$, then $b=b^{\prime}$.

Validity

If all nodes in $\mathcal{N}$ are correct and they all execute consensusStep
with the same ID and the same proposal $b$, then their consensusStep call
never returns a non-$\bot$ value $b^{\prime}\neq b$.

Termination

For all correct nodes $i$ and times
$t>\max\\{t_{0},t_{\textit{GST}}\\}+\Delta_{\textit{consensus}}$, node $i$’s
consensusStep call with ID $(\mathcal{N},\textit{id})$ returns a non-$\bot$
value.

The protocol includes two additional functions. The function consensusValidate
takes a block and an ID (including the set $\mathcal{N}$) and returns True if
and only if the block is the result of those nodes, with a correct ratio above
$\alpha$, running consensusStep. (In practice this can be implemented with
cryptographic signatures.)

Finally, the protocol supports _forensics_ , that is, it allows identifying
misbehavior of the nodes [47, 16]. Specifically, if the number of Byzantine
nodes is larger than the bound, they can cause an agreement violation. In such
a case, the correct nodes can publish data allowing them to identify
misbehaving parties.

###  3.3 Goal

The goal of the system is to form an expansion blockchain, denoted by
$\mathcal{L}$. Each node $i$ has an input value $v_{i}$ for each position in
the ledger. We do not consider the content of this blockchain, which could
serve as a decentralized sequencer, oracle, etc. (see §2). We only consider
its blocks, which are maintained by the nodes as local vectors. If a node
stores a block in a position $k$ in its local vector we say it _logs_ this
block. Note that this is a chain, not a single-instance consensus as in
Section 3.2. The expansion blockchain should achieve the following (referring
to expansion-chain blocks and positions):

Agreement

If a correct node $i$ logs a block $b$ in position $k$ at time $t$ and a
correct node $j$ logs block $b^{\prime}$ in position $k$ at time $t^{\prime}$
(maybe $i=j$ and maybe $t=t^{\prime}$) then $b=b^{\prime}$.

Validity

If all nodes are correct and their inputs for all positions
${v_{1},v_{2},\dots}$ are the same, then in all positions $k$ no node logs a
block with a different value $u_{k}\neq v_{k}$.

Progress

There exists a time $t>t_{\textit{GST}}$ such that after $t$, each correct
node logs new blocks at a rate of at least
$1/(\Delta_{\textit{consensus}}+\Delta_{\textit{prop}})$.

When it is not clear from context, we refer to the blockchain properties as
blockchain-agreement etc., and the consensus properties as consensus-agreement
etc.

##  4 Aegis

We overview the protocol design (§4.1), then present the Aegis blockchain
structure (§4.2) and the primary-chain contract (§4.3). We then describe the
peer-to-peer protocol Aegis nodes execute to form the blockchain (§4.4), and
discuss the execution of the forensics procedure to identify and penalize
misbehaving nodes (§4.5).

###  4.1 Protocol Outline

Aegis includes two components: A protocol that Aegis nodes execute and a smart
contract that the primary chain does. Roughly, the protocol executes a series
of consensus instances logging blocks consecutively. Each block $b$ contains a
reference (hash) to its _parent_. The blocks thus form a tree, rooted at an
agreed-upon _Genesis_ block, with each having a height $\textit{height}(b)$:
the number of edges on the path from $b$ to the Genesis block.

Each block also contains a reference to a primary block $B$. The primary block
implicitly specifies a committee—the set of nodes with staked tokens at the
state of block $B$, weighted by the staked amounts. (Nodes must include
contact information in the staking transaction; we omit this detail to
simplify the presentation.) This committee is, in the good case, the committee
that chooses the block following $b$. For example, in Figure 1, Aegis block
$A2$ references primary block $P4$, so the committee defined by block $P4$
chooses the subsequent Aegis block $A3$.

Occasionally, Aegis nodes _checkpoint_ blocks by sending them to the Aegis
smart contract on the primary chain. The contract receives the checkpointed
block and _accepts_ the checkpoint only if its committee is active.

If Aegis could not produce a block for a duration of
$\Delta_{\textit{active}}$—that is, in the bad case—the previous committee
might not be active. In this situation, a new committee must be selected to
extend the chain. For this, some node issues a _reset_ in the primary-chain
Aegis contract. The contract would accept the reset only if there were no
checkpoints or resets in the last $\Delta_{\textit{active}}$ steps. This
initiates a new committee, specified by the block in which the reset occurs.
This committee can produce a new block following the previous checkpointed
Aegis block using the committee specified by the reset.

Figure 1 illustrates the topology of the Aegis chain ($A1,A2,\dots$) and the
primary chain ($P1,P2,\dots$). Most Aegis blocks ($A2$–$A6$) are generated by
the committee referenced by their ancestor signified by the same color. Some
are checkpointed in primary blocks ($P3,P5,P6$). If a checkpoint cannot be
placed in time (and before the first Aegis block), a reset is issued
($P1,P7)$, and the subsequent Aegis block is generated by the committee of the
reset block ($A1,A7$).

We proceed to describe the algorithm in detail.

###  4.2 Chain Structure

Aegis’s data structure includes the Aegis chain and relevant updates in the
primary chain.

All nodes start with a single Genesis Aegis block (Algorithm 4.3 line 3). All
Aegis blocks $b$ (apart from Genesis) have a parent Aegis block
$\textit{parent}(b)$ and an Aegis-to-Primary reference to a primary block
$\textit{ref}_{A\to P}(b)$. (For genesis only:
$\textit{parent}(b_{\textit{genesis}})=\bot$ and $\textit{ref}_{A\to
P}(b_{\textit{genesis}})=\bot$.)

Each Aegis block $b$ should be generated by consensus among the committee it
specifies. The committee is specified in one of two ways. First, an aegis
block can have a reference to a reset in a primary block, denoted
$\textit{ref}_{A\to P}^{\>\textit{reset}}(b)$. If $\textit{ref}_{A\to
P}^{\>\textit{reset}}(b)\neq\bot$, the committee is the one specified by the
reset. Otherwise, the committee is the one specified in the primary block
referenced by $b$’s parent, i.e., $\textit{ref}_{A\to P}(\textit{parent}(b))$.
The function $\textit{stakers}(B)$ returns the committee specified by a
primary block $B$. The block should thus be valid according to the
consensusValidate function with the appropriate committee. The consensus
instance ID is the pair consisting of its parent and reset references.

The function isValid (Algorithm 1) validates all this—Note that this is only a
data structure validation that does not take into account committee activity.
The protocol ignores blocks that are invalid as checked by isValid.

1 function isValid ($b,\underline{\mathcal{L}},\mathcal{B}$)

2 if  _$b$ is Genesis_ then return True

3 if  _A checkpoint in $\underline{\mathcal{L}}$ conflicts with $b$_ then
return False

4 if  _$\textit{parent}(b)\not\in\mathcal{B}$_ then return False

5 if  _$\textit{ref}_{A\to P}(b)\not\in\underline{\mathcal{L}}$_ then return
False

6 if  _$\textit{ref}_{A\to P}(b)$ is not a descendant of $\textit{ref}_{A\to
P}(\textit{parent}(b))$_ then return False

7 if
_$\lnot\textit{isValid}(\textit{parent}(b),\underline{\mathcal{L}},\mathcal{B})$_
then return False

8 (Recursively validate parents) if  _$\textit{ref}_{A\to P}^{\
>\textit{reset}}(b)\neq\bot$_ then

9 if  _$\textit{ref}_{A\to P}^{\
>\textit{reset}}(b)\not\in\underline{\mathcal{L}}$_ then return False

10 if  _$\textit{ref}_{A\to P}^{\ >\textit{reset}}(b)$ is not a descendant of
$\textit{ref}_{A\to P}(\textit{parent}(b))$_ then return False

11 $\mathcal{N}\leftarrow\textit{stakers}(\textit{ref}_{A\to
P}^{\>\textit{reset}}(b)$ )

12

13 else

14 $\mathcal{N}\leftarrow\textit{stakers}(\textit{ref}_{A\to P}(b)$ )

15

16 if
_$\lnot\textit{consensusValidate}(b,\bigl{(}\textit{parent}(b),\textit{ref}_{A\to
P}^{\ >\textit{reset}}(b)\bigr{)},\mathcal{N})$_ then return False

17 return True

18

Algorithm 1 Valid block predicate

1 on Receive at time $t$ entry $e$ with pointed-to block $b$ and its parent
$b^{\prime}$

2 if  _$e$ is a reset_ then

assert no entries later than $t-\Delta_{\textit{active}}$

(First entry or previous stale)

3

4 else (checkpoint)

5 assert $\textit{ref}_{P\to A}(e)=b$

6 assert $\textit{parent}(b)=b^{\prime}$

7 assert $\textit{ref}_{A\to P}(b)\in\underline{\mathcal{L}}$

8 if  _$\textit{ref}_{A\to P}^{\ >\textit{reset}}(b)\neq\bot$_ then ($b$’s
committee specified by reset)

9 assert $\textit{ref}_{A\to
P}^{\>\textit{reset}}(b)\in\underline{\mathcal{L}}$

$B_{\textit{reset}}\leftarrow\underline{\mathcal{L}}(\textit{ref}_{A\to
P}^{\>\textit{reset}}(b)$)

(Primary-chain reset entry)

10 $\mathcal{N}\leftarrow\textit{stakers}(B_{\textit{reset}})$

11 $t_{0}\leftarrow t_{\textit{gen}}(B_{\textit{reset}})$

12

13 else ($b$’s committee specified by previous block)

14 $B_{\textit{reset}}\leftarrow\bot$

assert $\textit{ref}_{A\to P}(b^{\prime})\in\underline{\mathcal{L}}$

(Parent’s reference exists)

$\mathcal{N}\leftarrow$
$\textit{stakers}(\underline{\mathcal{L}}(\textit{ref}_{A\to P}(b^{\prime})))$

(Specified by parent)

15 $t_{0}\leftarrow
t_{\textit{gen}}(\underline{\mathcal{L}}(\textit{ref}_{A\to P}(b^{\prime})))$

16

17 assert $t<t_{0}+\Delta_{\textit{active}}$

18 assert
$\textit{consensusValidate}(b,\bigl{(}b^{\prime},B_{\textit{reset}}\bigr{)},\mathcal{N})$

19 assert $\textit{height}(b)>\textit{height}(\textit{ref}_{P\to
A}(\textup{previous checkpoint}))$

20

accept $e$

(All asserts passed, register checkpoint/reset)

21

22

Algorithm 2 Aegis primary-ledger contract.

###  4.3 Primary-Chain Contract

The primary-chain contract (Algorithm 2) allows checkpointing Aegis blocks and
initiating resets. It receives _entries_ submitted by Aegis nodes asking to
register either a checkpoint or a reset.

It registers a reset if there are no entries in the last
$\Delta_{\textit{active}}$ steps, indicating one is indeed necessary; no other
checks are required.

For a checkpoint, the contract receives an Aegis block to checkpoint along
with its parent. It verifies that the block correctly references a primary
block earlier than this checkpoint. Similarly, if the Aegis block has a reset
reference, the contract verifies it points to a previous primary block. It
also verifies that the block’s Aegis parent references a previous primary
block. The contract then verifies that the committee that created the block is
still active by comparing the current time (known to the contract) to the time
of the committee’s referenced block. It validates the block is the result of
the committee’s consensus by using the function consensusValidate . Finally,
it verifies that the block is higher (farther from the Aegis Genesis) than the
last checkpointed block. Having passed all these checks, the contract accepts
the checkpoint and registers it.

######  Note 1.

For a practical implementation, to reduce primary-chain overhead, the
checkpoint can include only the hash of the Aegis block $b$, and the following
elements with proof they are included in the block: reference from $b$ to the
primary block, reference from $b$ to a reset (could be $\bot$), reference from
$b$ to its parent $b^{\prime}$. Similarly, for $b^{\prime}$ we have its
reference to a primary block.

######  Note 2.

Theoretically, neglecting slashing enforcement, a protocol-agnostic append-
only log would suffice instead of a smart contract, with the nodes reading it
and locally applying the contract logic.

Initialization:

1 $\mathcal{B}_{i}$: A mapping, initially
$\mathcal{B}_{i}(\textit{id}(b_{\textit{genesis}}))=b_{\textit{genesis}}$,
$\forall\textit{id}\neq\textit{id}(b_{\textit{genesis}}):\mathcal{B}_{i}(\textit{id})=\bot$.

2 $\mathcal{L}_{i}$: A vector, initially
$\mathcal{L}_{i}(0)=b_{\textit{genesis}}$, $\forall
k>0:\mathcal{L}_{i}(k)=\bot$

Execution at step $t$: (return immediately if a referenced block is missing)

3 $\mathcal{B}_{i}\leftarrow\mathcal{B}_{i}\cup\textup{blocks received}$

4
$\underline{\mathcal{L}}_{i}\leftarrow\underline{\mathcal{L}}_{i}\|\textup{Primary
chain extension receieved}$ (No conflicts by assumption)
$B_{\textit{last}}\leftarrow$ last contract entry in
$\underline{\mathcal{L}}_{i}$ or $\bot$ if none

5 if  _$B_{\textit{last}}$ is a reset _ then

6 if  _$t
<t_{\textit{gen}}(B_{\textit{last}})+\Delta_{\textit{active}}-\Delta_{\underline{\mathcal{L}}\textit{-write}}$
_ then

7 $B_{\textit{checkpoint}}\leftarrow$ latest checkpoint, $\bot$ if none

8 $\mathcal{N}\leftarrow\textit{stakers}(B_{\textit{last}})$

9 $t_{0}\leftarrow t_{\textit{gen}}(B_{\textit{last}})$

10

11 else if  _$t
>t_{\textit{gen}}(B_{\textit{last}})+\Delta_{\textit{active}}$_ then (Previous
reset stale)

12 issue reset and return

13 else (Too close to timeout)

14 return

15

16 else if  _$B_{\textit{last}}$ is a checkpoint _ then

17 $B_{\textit{checkpoint}}\leftarrow B_{\textit{last}}$

$\mathcal{N}\leftarrow\textit{stakers}(\underline{\mathcal{L}}(\textit{ref}_{A\to
P}(\mathcal{B}_{i}(\textit{ref}_{P\to A}(B_{\textit{checkpoint}})))))$

(Committee from checkpointed Aegis block)

$t_{0}\leftarrow t_{\textit{gen}}(\underline{\mathcal{L}}(\textit{ref}_{A\to
P}(\mathcal{B}_{i}(\textit{ref}_{P\to A}(B_{\textit{checkpoint}})))))$

(Its generation time)

18

19 else (No block found)

issue reset and return

(Initialize)

20

21

22 if  _$B_{\textit{checkpoint}}=\bot$_ then (First non-genesis block,
committee by reset)

23 $k\leftarrow 1$

24 $b_{\textit{checkpointed}}\leftarrow b_{\textit{genesis}}$

25 $b\leftarrow b_{\textit{genesis}}$

26

27 else

$b_{\textit{checkpointed}}\leftarrow\mathcal{B}_{i}(\textit{ref}_{P\to
A}(B_{\textit{checkpoint}}))$

(We have now found the last checkpoint)

28 forall  _$k$ from $|\mathcal{L}|+1$ to
$\textit{height}(b_{\textit{checkpointed}})$ _ (Log all blocks up to
checkpoint, inclusive)

29 if  _$\exists b\in\mathcal{B}_{i}$ s.t. $b$ is an ancestor of
$b_{\textit{checkpointed}}$ and $\textit{height}(b)=k$_ then

30 $\mathcal{L}_{i}(k)\leftarrow b$ (Already verified via contract)

31 else

32 return (We are missing an ancestor of the checkpoint)

33

34

35

Algorithm 3 Aegis algorithm for node $i$. (part 1/2)

36

$k\leftarrow|\mathcal{L}|$

(Equal to $\textit{height}(b_{\textit{checkpointed}})$)

37 $b\leftarrow b_{\textit{checkpointed}}$

38 if  _$t <t_{0}+\Delta_{\textit{active}}$ _ then (Committee for next block
still active)

39 Choose $b^{\prime}\in\mathcal{B}_{i}$ s.t.
$\textit{isValid}(b^{\prime},\mathcal{N},\underline{\mathcal{L}},\mathcal{B}_{i})$
and $\textit{parent}(b^{\prime})=b_{\textit{checkpointed}}$, $\bot$ if none

40 while  _ $b^{\prime}\neq\bot$ _ do (Add blocks by active committees)

41 $b\leftarrow b^{\prime}$

42 $\mathcal{L}(k)\leftarrow b$

43 $k\leftarrow k+1$

44 $\mathcal{N}\leftarrow\textit{stakers}(\textit{ref}_{A\to P}(b))$

45 Choose $b^{\prime}\in\mathcal{B}_{i}$ s.t.
$\textit{isValid}(b^{\prime},\mathcal{N},\underline{\mathcal{L}}_{i},\mathcal{B}_{i})$
and $\textit{parent}(b^{\prime})=b$, $\bot$ in none

46

47

48 if  _$t
<t_{0}+\Delta_{\textit{active}}-3\Delta_{\underline{\mathcal{L}}\textit{-write}}$_
then (Latest committee has enough time)

49 if  _$b=b_{\textit{checkpointed}}\land B_{\textit{last}}$ is reset_ then
(No blocks since last checkpoint and following a reset)

50 $b\leftarrow\textit{consensusStep}(\textup{propose a
block},\bigl{(}\mathcal{L}(|\mathcal{L}|-1),B_{\textit{last}}\bigr{)},\mathcal{N})$

51

52 else (Last checkpointed or subsequent block’s committee is active)

53 $b\leftarrow\textit{consensusStep}(\textup{propose a
block},\bigl{(}\mathcal{L}(|\mathcal{L}|-1),\bot\bigr{)},\mathcal{N})$

54

55 if  _$b\neq\bot$_ then $\mathcal{L}(|\mathcal{L}|)\leftarrow b$

56

57 if
_$t=t_{\textit{gen}}(B_{\textit{last}})+\Delta_{\textit{active}}-3\Delta_{\underline{\mathcal{L}}\textit{-write}}$
and $b\neq b_{\textit{checkpointed}}$ _ then (Deadline to issue checkpoint)

58 issue checkpoint for $b$ and return

59

60 if  _$t >t_{0}+\Delta_{\textit{active}}$_ then

61 issue reset and return

62

(No-op if
$t_{0}+\Delta_{\textit{active}}-\Delta_{\underline{\mathcal{L}}\textit{-write}}<t<t_{0}+\Delta_{\textit{active}}$)

Algorithm 4 Aegis algorithm for node $i$. (part 2/2)

###  4.4 Node Protocol

We are now ready to present the protocol executed by each node (Algorithm
4.3). All nodes start with a single Aegis Genesis block (line 3) and in each
time step proceed in three phases, as follows.

####  4.4.1 Sync to Latest Checkpoint

At the beginning of a step a node first reads the states of the primary and
expansion blockchains (lines 3–3). Then, it finds the latest checkpointed
block as follows. If the latest primary-chain entry is a checkpoint, it takes
this checkpoint; the committee for the next block to log is expected to be the
one defined by the checkpointed block, i.e., according to the primary block it
references (line 3). Otherwise, if the latest entry is a reset and the
committee defined by the reset is still active (line 3), it takes the most
recent checkpoint with the reset’s committee for the subsequent block. If the
reset’s committee is inactive, the node issues a new reset and returns,
waiting for it to take place. Finally, if there is no primary block entry then
this is the first execution of the protocol, so the node issues a reset and
returns, waiting for it to take place.

If the only entry was a reset, namely, there are no checkpointed blocks, then
this is the first block after Genesis (lines 3–3). Otherwise, the node goes
from the latest block it had confirmed in previous steps (maybe starting from
Genesis), logging in its local Aegis chain all ancestors up to the
checkpointed block (lines 3–3). If the node is yet to receive any of those,
the algorithm stops; the node will wait to receive them in subsequent steps.

####  4.4.2 Sync Past Checkpoint

Having caught up to the latest checkpoint, the node proceeds to log Aegis
blocks finalized by consensus that are yet to be checkpointed. This is only
done if the latest checkpointed block’s committee is still active (line 4),
implying all subsequent committees are still active.

For each block, it adds it to the ledger and updates the next block’s
committee (lines 4–4). This is done for all Aegis blocks that were generated
with currently active committees. Recall that the committee of the first block
after the checkpoint is defined by the primary block its parent points to
(lines 3–3), or by a reset block if it was produced that way (lines 3–3).

Once this is done, the node is up-to-date, having logged all previous blocks
before the last checkpoint and after the checkpoint (with active committees).

####  4.4.3 Extend the log

If the latest Aegis block specified committee has enough time remaining
active, the node tries to extend the chain by taking a consensus protocol
step. Specifically, there should be enough time to checkpoint a new block and
complete the forensics procedure (line 4). The consensus is identified by the
parent and reset blocks (line 4 or 4). If the committee is no longer active,
it issues a reset (line 4) to enable progress in future steps. Because the
committee defined by the checkpoint is inactive, the contract will accept the
reset.

Aegis nodes issue a checkpoint before the committee expires (line 4), which is
sufficient for correctness. Note that it could be that just one correct node
got the block (line 4 or 4) before the committee expires—the consensus
protocol does not guarantee more. Then the perpetuation of this block relies
entirely on this node issuing the checkpoint. But this is guaranteed since
this node is correct.

######  Note 3.

The consensus ID for each Aegis block $b$ includes both its ancestor
$\textit{ref}_{A\to P}(b)$ and its reset reference $\textit{ref}_{A\to
P}^{\>\textit{reset}}(b)$, the latter might be $\bot$ if the block’s committee
is specified by its ancestor. This guarantees that the committee could only
start the consensus instance when it was active. Without the reset reference,
a committee $C$ could be specified by a primary block, later become stale,
create a block $b$ while being inactive, then a reset reinstates the same
committee, which is now active, allowing it to present $b$ as the result of an
active committee.

###  4.5 Forensics

Aegis takes advantage of the consensus protocol’s forensics support [47, 16]
to penalize Byzantine nodes if their number is greater than its threshold and
they successfully violate agreement. The forensics procedure encompasses both
the contract and the peer-to-peer protocol, we describe it only here for
pseudocode readability.

A correct node identifies a violation if it observes two conflicting decided
values (by a consensus step, receiving a block, or a checkpoint). In this
case, it issues a transaction notifying the contract, which initiates the
consensus protocol’s forensics procedure. Once the other correct nodes observe
the notification in the primary chain, they participate in the procedure,
sending the necessary data to the contract. The contract then identifies the
Byzantine nodes and penalizes them by slashing (revoking) their stake. The
forensics procedure depends on the consensus algorithm’s details, and
optimization for reducing the primary-chain overhead is outside our scope.

##  5 Security

After showing that the ancestors of a block generated by an active committee
were also generated by active committees (§5.1), we prove Aegis achieves
agreement (§5.2), validity (§5.3) and progress (§5.4), and that it penalizes
misbehaving nodes (§5.5). The security guarantees follow (§5.6).

###  5.1 Active Committee Follows Active Committees

We call a committee active if its nodes’ collateral was locked recently enough
so it could not be withdrawn yet.

######  Definition 1 (Active committee).

A weighted set of nodes $\mathcal{N}$ is an _active committee at time $t$_ if
there exists a primary-chain block published in the interval
$[t-\Delta_{\textit{active}},t]$ and those nodes staked collateral up to that
block and did not unstake by that block.

We show that if a block is generated by an active committee then its ancestors
were approved by active committees. This is enforced for each block by the
committee that generated the block, whether it is defined by a reset or by a
previous block whose committee is active.

######  Lemma 1.

If at time $t$, a node observes (i.e., receives or generates) a block $b$ such
that block $b$’s committee is active at $t$, then a node (perhaps the same
node) receives the parent of $b$, $\textit{parent}(b)$, at time $t^{\prime}$,
and $\textit{parent}(b)$’s committee is active at $t^{\prime}$.

###### Proof.

If a node observes a valid block $b$, approved by the committee defined by it,
there are two options: If the committee is defined by its parent
$\textit{ref}_{A\to P}(\textit{parent}(b))$, then the committee is active
between $t_{\textit{gen}}(\textit{ref}_{A\to P}(\textit{parent}(b)))$ and
$t\geq t_{\textit{gen}}(b)$. If the committee is defined by a reset pointed by
$\textit{ref}_{A\to P}^{\>\textit{reset}}(b)$, then the committee is active
between $t_{\textit{gen}}(\textit{ref}_{A\to P}^{\>\textit{reset}}(b))$ and
$t\geq t_{\textit{gen}}(b)$. In both cases, a quorum of the committee nodes
approved block $b$ during this interval—recall the block hashes are
unpredictable, so the consensus ID is generated on the generation of the
primary-ledger block. By the lemma assumption, during this time (up to $t$)
the committee is active; therefore, there is a time $\tilde{t}$ where a
correct committee node $i$ confirmed the correctness of $\textit{parent}(b)$:
A node only participates in block generation (lines 4 or 4) after approving
its predecessor. Node $i$ logged the parent block $b^{\prime}$ and validated
its consensus in one of three ways: (1) It is the genesis block (line 3),
which needs no validation; (2) the parent is checkpointed (line 3), either
following a series of resets or not; then $b^{\prime}$ was approved by an
active committee by the time it was checkpointed, as verified by the contract
(Algorithm 2 line 2); or (3) the parent is not checkpointed; in this case the
node $i$ that logged $b$ only logged $b^{\prime}$ because the committee of
$b^{\prime}$ is active at $\tilde{t}$ (Algorithm 4.3 line 4) and the block is
valid (lines 4, 4).

In conclusion, the parent block $b^{\prime}$ was approved by an active
committee. ∎

We next deduce that the ancestors of a block approved by an active committee
are all approved by active committees. The proof follows by induction.

######  Lemma 2.

If at time $t$ a node observes a block $b$ such that block $b$’s committee is
active at $t$ then for all ancestors $b^{\prime}$ of $b$, there exist a node
(perhaps the same node) and time $t^{\prime}$ such that the node receives
$b^{\prime}$ at $t^{\prime}$ and the committee of $b^{\prime}$ is active at
$t^{\prime}$.

###  5.2 Agreement

For agreement we need two more lemmas. First, we ensure steps taken by the
nodes are reflected in the primary chain. We show that if the nodes agree on
the ledger up to some height, then a subsequent block will be accepted by the
primary-chain contract.

######  Lemma 3.

If there are no two correct nodes that log different blocks at the same height
for all indices up to $k-1$ and a node receives a valid block with index $k$
at time $t$, then a block of height at least $k$ is checkpointed by step
$t+\Delta_{\textit{active}}$ and no resets are registered between $t$ and
$t+\Delta_{\textit{active}}$.

Note that the lemma does not state that the registered checkpoint is for a
descendant of the valid block at height $k$ received.

###### Proof.

The block’s committee is specified by the primary block its parent points to
or by a reset on $\underline{\mathcal{L}}$. Denote that
$\underline{\mathcal{L}}$ block by $B$. In both cases, some correct node $i$
in that committee observes block $b$. If within $\Delta_{\textit{active}}$
steps of $B$ there is no checkpoint, then node $i$ issues a checkpoint
(Algorithm 4.3 line 4). We should show the checkpoint is accepted by the
contract. There cannot be a reset before $\Delta_{\textit{active}}$ has
passed, enforced by the contract (line 2). If the contract accepts checkpoints
for ancestors of $b$ then $b$’s checkpoint will still be accepted when it
arrives. Suppose the contract accepted checkpoints of blocks at height $k-1$
or earlier that are not ancestors of $b$. The contract only accepts blocks
approved by an active committee (Algorithm 2 line 2). So a correct node in a
quorum of an active committee approved a block at a height smaller than $k$,
contradicting the lemma assumption.

Thus, the only case where the checkpoint for $b$ is not accepted is if a
checkpoint for a block at height $k$ or more was already accepted, completing
the proof. ∎

We also show that consensus agreement applies to decisions taken by active
committees.

######  Lemma 4 (Active committee agreement).

In an execution of Aegis, an active committee does not decide different values
for the same consensus instance.

###### Proof.

Consider an execution $\sigma$ of Aegis where two correct nodes in a committee
active in the time range ${[t_{0},t_{f}]}$ decide in steps ${t_{0}\leq
t_{1},t_{2},\leq t_{f}}$ two values $v_{1}$ and $v_{2}$ (one each) for the
same consensus instance.

Let $\sigma^{\prime}$ be an execution with the same prefix as Aegis up to
$t_{1}$, and extended such that the committee remains active forever (its
nodes never unstake), as in the consensus protocol assumptions. By the
agreement property of the consensus protocol, the two nodes cannot decide
distinct values.

Since at $t_{1}$ the nodes cannot distinguish between $\sigma$ and
$\sigma^{\prime}$, the nodes take the same steps in $\sigma$ up to $t_{1}$, so
${v_{1}=v_{2}}$. ∎

We are now ready to prove agreement.

######  Proposition 1 (Agreement).

Two correct nodes do not log different blocks at the same height.

###### Proof.

We prove by induction on the block number $k$.

Base.  For $k=0$ all correct nodes at all times log the Genesis block
(Algorithm 4.3 line 3; $\mathcal{L}(0)$ is never updated elsewhere). The
contract initially has no checkpoints.

Assumption.  For $k>0$, assume that the claim holds for ${k-1}$. That is, for
all nodes $i$ and $j$ (maybe $i=j$) and times $t_{1}\leq t_{2}$, if node $i$
logs a block $b$ at height $k^{\prime}\leq k-1$ at time $t_{1}$
($\mathcal{L}_{i}^{t_{1}}(k^{\prime})\neq\bot$) and node $j$ logs block
$b^{\prime}$ at height $k^{\prime}$ at time $t_{2}$
($\mathcal{L}_{j}^{t_{2}}(k^{\prime})\neq\bot$), then
$\mathcal{L}_{i}^{t_{1}}(k^{\prime})=\mathcal{L}_{j}^{t_{2}}(k^{\prime})$.
Also assume there is no checkpoint for a block $b$ at a height $k^{\prime}\leq
k-1$ and a node $i$ that logs a block $b^{\prime}\neq b$ at height
$k^{\prime}$.

Step.  Now we prove for $k$. Assume for contradiction that there exist nodes
$i$ and $j$ (maybe ${i=j}$) and times $t_{1}\leq t_{2}$ such that node $i$
logs a block $b$ in position $k$ at time $t_{1}$ and a node $j$ logs block
$b^{\prime}\neq b$ in position $k$ at time $t_{2}$:
$\mathcal{L}_{i}^{t_{1}}(k)=b\neq b^{\prime}=\mathcal{L}_{j}^{t_{2}}(k)$.

The content of the ledger in positive positions is determined due to
checkpoints (line 3) or consensus (lines 4 and 4).

If a node logs a block $b$ in position $k$ due to consensus (lines 4 or 4),
then it is because it received active committee consensus message for $b$
(activity period verified in line 4). The committee is defined by $b$’s parent
or specified by a reset.

If a node logs a block $b$ in position $k$ due to a checkpoint (line 3), then
it is because $b$ is an ancestor of a checkpointed block $\hat{b}$. The
checkpointed block $\hat{b}$ is due to an active committee verified by the
contract (Algorithm 2 line 2). Therefore (Lemma 2), all ancestors of $\hat{b}$
are also approved by active committees. In particular, block $b$ is approved
by an active committee. That committee is either the one defined by the
previous block, or specified by a reset.

In summary, both blocks $b$ and $b^{\prime}$ are created by active committees,
each either defined by a reset or by the committee referenced by the previous
block.

We now consider each of the possible cases. By the induction assumption, both
$i$ and $j$ agree on the previous block. If the committees of both blocks are
specified by the previous Aegis block, since by assumption they agree on this
prior block, that committee decided conflicting values, contradicting the
consensus protocol agreement property (Lemma 4).

Next, if the committees of both $b$ and $b^{\prime}$ are specified by reset
blocks, we show it is the same reset block. Assume for contradiction that
block $b$ (without loss of generality) is confirmed by the first reset and
that $b^{\prime}$ is confirmed by a later reset. Since block $b$ is approved
by the first reset committee (reset at time $t_{\textit{reset}}$), by Lemma 3
a block of height at least $k$ is issued a checkpoint before the reset
committee becomes stale, with the checkpoint being written by time
$t_{\textit{reset}}+\Delta_{\textit{active}}$ for a block of height at least
$k$. The contract will only accept another reset after
$t_{\textit{reset}}+\Delta_{\textit{active}}$ (Algorithm 2 line 2), so after
the checkpoint. A committee following a reset considers the latest checkpoint
(Algorithm 4.3 line 3), so a block $b^{\prime}$ confirmed by the committee
specified by the second reset cannot extend the chain earlier than $k+1$ and
cannot have the same height as $b$. A contradiction.

Finally, consider the case where the committee of $b$ (without loss of
generality) is specified by its parent and that of $b^{\prime}$ is specified
by a reset. There are two possible cases. In the first case,
$\textit{ref}_{A\to P}(b_{k-1})$ is before $\textit{ref}_{A\to
P}^{\>\textit{reset}}(b^{\prime})$ in the primary chain. All nodes agree on
all blocks up to $k-1$ and an active node observed block $b$ with height $k$,
therefore (Lemma 3) a block at height $k$ or more is checkpointed before the
contract accepts any reset. So a block at height $k$ is checkpointed before
the reset defining the committee of block $b^{\prime}$. An Aegis block
$b^{\prime}$ following such a subsequent reset cannot result in a block at
height $k$, a contradiction.

The alternative case is that $\textit{ref}_{A\to
P}^{\>\textit{reset}}(b^{\prime})before\textit{ref}_{A\to P}(b_{k-1})$. In
this case block $b^{\prime}$ is not valid due to the order of its parent
reference and reset (Algorithm 1 line 1), so no node would log it. Again, a
contradiction.

Having reviewed all cases and reached contradictions, we conclude that no two
nodes log different blocks at the same height. Since the contract will only
checkpoint a block at height $k$ if its committee is active, a checkpoint can
only be produced if an active committee decides a different block at height
$k$. We have shown this is impossible, thus a checkpointed block is not
different from a valid block received by a node at height $k$.

This completes the induction step and thus the proof. ∎

###  5.3 Validity

To prove validity, we require a similar lemma to Lemma 4; the proof is also
similar and deferred to Appendix B.

######  Proposition 2 (Validity).

Aegis achieves validity.

###  5.4 Progress

Finally, we show Aegis extends the ledger after $t_{\textit{GST}}$. To prove
progress, we first show that consensus termination applies to active Aegis
committees after $t_{\textit{GST}}$.

######  Lemma 5 (Active committee termination).

In an execution of Aegis, after $t_{\textit{GST}}$, a node in an active
committee decides within $\Delta_{\textit{consensus}}$ steps.

###### Proof.

Consider an execution $\sigma$ of Aegis where a node in an active committee
participates in a consensus instance in a step ${t\geq t_{\textit{GST}}}$.

Let $\sigma^{\prime}$ be an execution with the same prefix as Aegis up to
${t+\Delta_{\textit{consensus}}}$, and extended such that the committee
remains active forever (its nodes never unstake), as in the consensus protocol
assumptions. By the termination property of the consensus protocol, the node
decides by $t+\Delta_{\textit{consensus}}$.

Since at $t+\Delta_{\textit{consensus}}$ the nodes cannot distinguish between
$\sigma$ and $\sigma^{\prime}$, the nodes take the same steps in $\sigma$ up
to $t+\Delta_{\textit{consensus}}$, so the node decides in $\sigma$ by
$t+\Delta_{\textit{consensus}}$ in $\sigma$. ∎

######  Proposition 3 (Progress).

Aegis guarantees progress.

###### Proof.

A node adds a block to the Aegis ledger either since its descendant is
checkpointed (Algorithm 4.3 line 3) or since it is approved by an active
committee (Algorithm 4.3 line 4 or 4). In both cases, the result is that
within at most $\Delta_{\textit{active}}$ steps it is checkpointed in the
primary chain and seen by all correct nodes (Algorithm 4.3 line 4).

If at time $t$ the Aegis checkpoint is later than
$t-\Delta_{\textit{active}}+\Delta_{\underline{\mathcal{L}}\textit{-write}}$,
the nodes take consensus steps and decide within $\Delta_{\textit{consensus}}$
steps (Algorithm 4.3 line 4, Lemma 5). However, if the consensus runs for too
long, and its result might not be checkpointed in time, it is abandoned
(Algorithm 4.3 line 4). Then no progress can be made until
$\Delta_{\textit{active}}$ after the last checkpoint/reset and a new committee
is instated with a new reset (line 4). The reset is registered within
$\Delta_{\underline{\mathcal{L}}\textit{-write}}$ steps and a new committee
reaches consensus within $\Delta_{\textit{consensus}}$ (Lemma 5), guaranteed
after $t_{\textit{GST}}$ because
${\Delta_{\textit{consensus}}<\Delta_{\textit{active}}-\Delta_{\underline{\mathcal{L}}\textit{-write}}}$.

From that point on, a new consensus is reached within
$\Delta_{\textit{consensus}}$ steps (Lemma 5) and propagated to all correct
nodes within $\Delta_{\textit{prop}}$, at which point a new consensus instance
is started. The extension rate is thus
${1/(\Delta_{\textit{consensus}}+\Delta_{\textit{prop}})}$. ∎

Note. Independent Proof-of-Stake chains are vulnerable to _long range attacks_
, where a deprecated committee forms an alternative history long after it
unstaked. Joining nodes cannot distinguish between real history and the forged
one. Aegis is not vulnerable to this attack due to the security of the primary
chain.

###  5.5 Slashing

Enforcing the desired behavior of correct nodes while they are active
necessitates penalizing them if they successfully violate safety (Agreement or
Validity). We show Aegis achieves this.

######  Proposition 4 (Penalty).

If a node $i$ belongs to an active committee that violates the consensus
safety, it will be penalized.

###### Proof.

With even a single Byzantine node in the committee, validity vacuously holds.
Thus, the only potential safety violation is for agreement, resulting in two
distinct nodes deciding different decisions. If a node decides a value at
height $k$, then this or another node will issue a checkpoint for a subsequent
block at height at least $k$ within
$\Delta_{\textit{active}}-3\Delta_{\underline{\mathcal{L}}\textit{-write}}$
steps (Algorithm 4.3 line 4). Thus, if a node $i$ decides a value $v_{i}^{k}$
and a node $j$ decides a value $v_{j}^{k}\neq v_{i}^{k}$, then one of them
will find out once the first checkpoint is written to the primary chain or
earlier through direct communication of a consensus step (line 4 or line 4) or
from received blocks (line 4). Once a node detects such an agreement
violation, it issues a forensics procedure by publishing the necessary
information to the blockchain. This process is completed within
$\Delta_{\underline{\mathcal{L}}\textit{-write}}$ steps, at which point its
counterpart does the same, completing the on-chain forensics process while the
committee of the violating nodes is still active. Thus, the contract can
penalize the stake, which is yet to be withdrawn. ∎

###  5.6 Aegis Security

The conclusion follows directly from propositions 1, 2, and 3, since nodes are
penalized (Lemma 4) for violating safety.

######  Theorem 1.

Aegis ensures Agreement, validity, and progress.

##  6 Conclusion

We present Aegis, a novel expansion blockchain protocol whose nodes can join
and leave in a permissionless fashion by staking in a primary chain. Aegis
guarantees safety at all times and progress after $t_{\textit{GST}}$ despite
asynchronous communication among its nodes (up to $t_{\textit{GST}}$), using
committees dynamically specified by a primary-chain smart contract with
synchronous access.

While Aegis can be deployed as-is on top of a primary blockchain, there are
two practical aspects to consider. Aegis requires primary-chain transactions
in intervals close to the time for unstaking $\Delta_{\textit{active}}$. This
implies a tradeoff between short unstaking time and low primary-chain
overhead. In terms of performance, Aegis can change committee membership at a
lower frequency than every block. This allows using contemporary BFT state
machine replication algorithms (e.g., [56, 24, 5]) that are more efficient
than running a one-shot consensus instance per block.

The tools to deploy staking for Aegis are ready at hand, e.g., Avalanche’s
elastic subnets [32]; direct implementation with a smart contract; and
Ethereum’s EigenLayer [53], which enables recycling of large stake amounts.
Thus, Aegis opens the door for a new generation of truly decentralized
expansion blockchains.

##  Appendix A Notation

Table 1 summarizes key notation used in this paper.

Table 1: Notation Symbol | Meaning
---|---
$\alpha$ | Minimum ratio of correct nodes in an active committee
$t_{\textit{GST}}$ | Global Stabilization Time
$\Delta_{\textit{prop}}$ | Network propagation bound after $t_{\textit{GST}}$
$\Delta_{\textit{active}}$ | Time between unstake order and funds withdrawal
$\Delta_{\underline{\mathcal{L}}\textit{-write}}$ | Time to write a block to the primary chain
$\Delta_{\textit{consensus}}$ | Time to reach consensus after $t_{\textit{GST}}$
$H(B)=\hat{B}$ | Hash of block $B$
$\underline{\mathcal{L}}$ | Primary ledger
$\underline{\mathcal{L}}(\hat{B})$ | Block $B$ if $B\in\underline{\mathcal{L}}$, otherwise $\bot$
$\mathcal{L}$ | Aegis ledger
$\mathcal{L}(k)$ | Aegis block at height $k$
$\textit{parent}(b)$ | Parent block of block $b$
$\mathcal{B}(\hat{b})$ | Block $b$ if $b$ is in block set $B$, otherwise $\bot$
$\textit{ref}_{A\to P}(b)$ | Reference from block $b$ to a primary block
$\textit{ref}_{A\to P}^{\>\textit{reset}}(b)$ | Reference from block $b$ to a reset in a primary block
$\textit{ref}_{P\to A}(B)$ | Checkpoint reference from primary block $b$ to an Aegis block
$\textit{stakers}(B)$ | Committee defined by primary block $B$
$t_{\textit{gen}}(b)$ | Generation time of block $b$

##  Appendix B Validity

To prove validity, we first note that the consensus protocol guarantees
validity of an active committee decision. The proof is similar to that of
Lemma 4.

######  Lemma 6 (Active committee validity).

In an execution of Aegis, if all committee members of an active committee have
the same input value, and Aegis executes the consensus protocol of this
committee, then no correct node outputs a different value.

We are now ready to prove validity (Proposition 2).

###### Proof.

We prove by induction on the block number $k$.

Base.  For $k=0$ all correct nodes at all times log the Genesis block
(Algorithm 4.3 line 3; $\mathcal{L}(0)$ is never updated elsewhere). The
contract initially has no checkpoints.

Assumption.  For $k>0$, assume that the claim holds for ${k-1}$. That is, for
all nodes $i$ and times $t$, if node $i$ logs a block $b$ at height
$k^{\prime}\leq k-1$ at time $t_{1}$
($\mathcal{L}_{i}^{t_{1}}(k^{\prime})\neq\bot$) and all nodes are correct with
input $v_{k^{\prime}}$ for height $k^{\prime}$, then
${\mathcal{L}_{i}^{t_{1}}(k^{\prime})=v_{k^{\prime}}}$. Also assume there is
no checkpoint for a block $b$ at a height $k^{\prime}\leq k-1$ with value
different from $v_{k^{\prime}}$.

Step.  Now we prove for $k$. Assume for contradiction that there exists a
nodes $i$ and time $t$ such that node $i$ logs a block $b$ in position $k$ at
time $t$ and $\mathcal{L}_{i}^{t_{1}}(k)=b\neq v_{k}$.

The content of the ledger in positive positions is determined due to
checkpoints (line 3) or consensus (lines 4 and 4).

If a node logs a block $b$ in position $k$ due to consensus (lines 4 or 4),
then it is because it received active committee consensus message for $b$
(activity period verified in line 4). The committee is defined by $b$’s parent
or specified by a reset.

If a node logs a block $b$ in position $k$ due to a checkpoint (line 3), then
it is because $b$ is an ancestor of a checkpointed block $\hat{b}$. The
checkpointed block $\hat{b}$ is due to an active committee verified by the
contract (Algorithm 2 line 2). Therefore (Lemma 2), all ancestors of $\hat{b}$
are also approved by active committees. In particular, block $b$ is approved
by an active committee. That committee is either the one defined by the
previous block, or specified by a reset.

In both cases, that committee decided on an invalid value, contradicting the
consensus protocol agreement property (Lemma 6).

This completes the induction step and thus the proof. ∎

## References

  * [1] Cryptocurrency prices, charts and market capitalizations — coinmarketcap.  https://coinmarketcap.com/, retrieved May 2024.
  * [2] Arbitrum.  Arbitrum nova.  https://arbitrum.io/anytrust, retrieved Sep. 2023.
  * [3] Sarah Azouvi, George Danezis, and Valeria Nikolaenko.  Winkle: Foiling long-range attacks in proof-of-stake systems.  In Proceedings of the 2nd ACM Conference on Advances in Financial Technologies, 2020.
  * [4] Sarah Azouvi and Marko Vukolić.  Pikachu: Securing PoS blockchains from long-range attacks by checkpointing into bitcoin PoW using taproot.  In Proceedings of the 2022 ACM Workshop on Developments in Consensus, pages 53–65, 2022.
  * [5] Kushal Babel, Andrey Chursin, George Danezis, Lefteris Kokoris-Kogias, and Alberto Sonnino.  Mysticeti: Low-latency DAG consensus with fast commit path.  arXiv preprint arXiv:2310.14821, 2023.
  * [6] Simon Barber, Xavier Boyen, Elaine Shi, and Ersin Uzun.  Bitter to better, how to make Bitcoin a better currency.  In Financial Cryptography and Data Security, pages 399–414. Springer, Bonaire, 2012.
  * [7] Bitcoin community.  Protocol specification.  https://en.bitcoin.it/wiki/Protocol_specification, retrieved Sep. 2013.
  * [8] Joseph Bonneau, Andrew Miller, Jeremy Clark, Arvind Narayanan, Joshua A. Kroll, and Edward W. Felten.  Research perspectives on Bitcoin and second-generation cryptocurrencies.  In Symposium on Security and Privacy, San Jose, CA, USA, 2015. IEEE.
  * [9] Gabriel Bracha and Sam Toueg.  Asynchronous consensus and broadcast protocols.  Journal of the ACM (JACM), 32(4):824–840, 1985.
  * [10] Vitalik Buterin.  Proof of stake: How I learned to love weak subjectivity.  https://blog.ethereum.org/2014/11/25/proof-stake-learned-love-weak-subjectivity, November 2014.
  * [11] Vitalik Buterin.  Slasher: A punitive proof-of-stake algorithm.  https://blog.ethereum.org/2014/01/15/slasher-a-punitive-proof-of-stake-algorithm/, January 2015.
  * [12] Ran Canetti and Tal Rabin.  Fast asynchronous byzantine agreement with optimal resilience.  In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 42–51, 1993.
  * [13] Miguel Castro, Barbara Liskov, et al.  Practical byzantine fault tolerance.  In OsDI, volume 99, pages 173–186, 1999.
  * [14] Amedeo Celletti.  Random number oracle.  https://www.random-oracle.com, retrieved Sep. 2023.
  * [15] Chainlink.  Chainlink 2.0 and the future of decentralized oracle networks.  https://research.chain.link/whitepaper-v2.pdf, April 2021.  Retrieved May 2024.
  * [16] Pierre Civit, Seth Gilbert, and Vincent Gramoli.  Polygraph: Accountable byzantine agreement.  In 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS), pages 403–413. IEEE, 2021.
  * [17] Phil Daian, Rafael Pass, and Elaine Shi.  Snow white: Robustly reconfigurable consensus and applications to provably secure proof of stake.  In Financial Cryptography and Data Security. Springer, 2019.
  * [18] Francesco D’Amato, Joachim Neu, Ertem Nusret Tas, and David Tse.  No more attacks on proof-of-stake ethereum?  arXiv preprint arXiv:2209.03255, 2022.
  * [19] Bernardo David, Peter Gaži, Aggelos Kiayias, and Alexander Russell.  Ouroboros praos: An adaptively-secure, semi-synchronous proof-of-stake blockchain.  In Advances in Cryptology–EUROCRYPT. Springer, 2018.
  * [20] Christian Decker and Roger Wattenhofer.  A fast and scalable payment network with bitcoin duplex micropayment channels.  In Stabilization, Safety, and Security of Distributed Systems. Springer, 2015.
  * [21] Cynthia Dwork, Nancy A. Lynch, and Larry J. Stockmeyer.  Consensus in the presence of partial synchrony.  J. ACM, 35(2):288–323, 1988.
  * [22] eoracle.  eoracle.  https://eoracle.gitbook.io/, retrieved May 2024.
  * [23] Matthias Fitzi, Peter Gaži, Aggelos Kiayias, and Alexander Russell.  Ledger combiners for fast settlement.  In Theory of Cryptography Conference, pages 322–352. Springer, 2020\.
  * [24] Rati Gelashvili, Lefteris Kokoris-Kogias, Alberto Sonnino, Alexander Spiegelman, and Zhuolun Xiang.  Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback.  In International conference on financial cryptography and data security. Springer, 2022.
  * [25] Gnosis.  Gnosis chain docs.  https://docs.gnosischain.com, retrieved Sep. 2023.
  * [26] Lewis Gudgeon, Pedro Moreno-Sanchez, Stefanie Roos, Patrick McCorry, and Arthur Gervais.  Sok: Layer-two blockchain protocols.  In Financial Cryptography and Data Security. Springer, 2020.
  * [27] Harry Kalodner, Steven Goldfeder, Xiaoqi Chen, S Matthew Weinberg, and Edward W Felten.  Arbitrum: Scalable, private smart contracts.  In 27th USENIX Security Symposium (USENIX Security 18), pages 1353–1370, 2018.
  * [28] Dimitris Karakostas and Aggelos Kiayias.  Securing proof-of-work ledgers via checkpointing.  In 2021 IEEE International Conference on Blockchain and Cryptocurrency (ICBC), pages 1–5. IEEE, 2021.
  * [29] Mahimna Kelkar, Fan Zhang, Steven Goldfeder, and Ari Juels.  Order-fairness for byzantine consensus.  In Advances in Cryptology–CRYPTO. Springer, August 2020.
  * [30] Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov.  Ouroboros: A provably secure proof-of-stake blockchain protocol.  In Annual international cryptology conference, pages 357–388. Springer, 2017.
  * [31] L2BEAT.  Value locked.  https://l2beat.com/scaling, retrieved May. 2024.
  * [32] Ava Labs.  Scale with subnets.  https://www.avax.network/subnets, retrieved Sep. 2023.
  * [33] Matter Labs.  How decentralized is zksync.  https://docs.zksync.io/userdocs/decentralization/#how-decentralized-is-zksync, retrieved Sep. 2023.
  * [34] Polygon Labs.  Change emit.  https://github.com/0xPolygon/core-contracts/blob/de71996fbd0b25fbedb630df6bc312e8175e9b7d/contracts/root/staking/CustomSupernetManager.sol#L149, retrieved Sep. 2023.
  * [35] Polygon Labs.  Change vote.  https://github.com/0xPolygon/polygon-edge/blob/f2b24e79912802b1b6c8fb3ba1abdbcc9eec94c0/consensus/polybft/state_sync_manager.go#L565, retrieved Sep. 2023.
  * [36] Polygon Labs.  Introducing polygon 2.0: The value layer of the internet.  https://polygon.technology/blog/introducing-polygon-2-0-the-value-layer-of-the-internet, retrieved Sep. 2023.
  * [37] Leslie Lamport, Dahlia Malkhi, and Lidong Zhou.  Reconfiguring a state machine.  ACM SIGACT News, 41(1), 2010.
  * [38] Nancy A Lynch.  Distributed algorithms.  Elsevier, 1996.
  * [39] Satoshi Nakamoto.  Bitcoin: A peer-to-peer electronic cash system.  http://www.bitcoin.org/bitcoin.pdf, 2008.
  * [40] Optimism.  Optimism block production.  https://community.optimism.io/docs/protocol/2-rollup-protocol/#block-production, retrieved Sep. 2023.
  * [41] Polygon.  Proven scalability on ethereum.  https://polygon.technology/polygon-pos, retrieved Sep. 2023.
  * [42] Joseph Poon and Thaddeus Dryja.  The Bitcoin Lightning Network, draft 0.5.  http://lightning.network/lightning-network.pdf, February 2015.  Retrieved May 2024.
  * [43] Youer Pu, Ali Farahbakhsh, Lorenzo Alvisi, and Ittay Eyal.  Gorilla: Safe permissionless byzantine consensus.  In 37th International Symposium on Distributed Computing, 2023.
  * [44] Ranvir Rana, Dimitris Karakostas, Sreeram Kannan, Aggelos Kiayias, and Pramod Viswanath.  Optimal bootstrapping of pow blockchains.  In Proceedings of the Twenty-Third International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, pages 231–240, 2022.
  * [45] Team Rocket, Maofan Yin, Kevin Sekniqi, Robbert van Renesse, and Emin Gün Sirer.  Scalable and probabilistic leaderless bft consensus through metastability.  arXiv preprint arXiv:1906.08936, 2019.
  * [46] Suryanarayana Sankagiri, Xuechao Wang, Sreeram Kannan, and Pramod Viswanath.  Blockchain cap theorem allows user-dependent adaptivity and finality.  In Financial Cryptography and Data Security. Springer, March 2021\.
  * [47] Peiyao Sheng, Gerui Wang, Kartik Nayak, Sreeram Kannan, and Pramod Viswanath.  BFT protocol forensics.  In Proceedings of the 2021 ACM SIGSAC conference on computer and communications security, pages 1722–1743, 2021.
  * [48] Yonatan Sompolinsky, Shai Wyborski, and Aviv Zohar.  Phantom ghostdag: a scalable generalization of nakamoto consensus.  In Proceedings of the 3rd ACM Conference on Advances in Financial Technologies, pages 57–70, 2021.
  * [49] Starkware.  StarkEx High-Level Overview.  https://docs.starkware.co/starkex/overview.html, retrieved Sep. 2023.
  * [50] Selma Steinhoff, Chrysoula Stathakopoulou, Matej Pavlovic, and Marko Vukolić.  Bms: Secure decentralized reconfiguration for blockchain and bft systems.  arXiv preprint arXiv:2109.03913, 2021.
  * [51] Nick Szabo.  Smart contracts: building blocks for digital markets.  EXTROPY: The Journal of Transhumanist Thought,(16), 18(2):28, 1996\.
  * [52] Ertem Nusret Tas, David Tse, Fangyu Gai, Sreeram Kannan, Mohammad Ali Maddah-Ali, and Fisher Yu.  Bitcoin-enhanced proof-of-stake security: Possibilities and impossibilities.  In 2023 IEEE Symposium on Security and Privacy (SP), pages 126–145. IEEE, 2023.
  * [53] EigenLayer Team.  Eigenlayer: The restaking collective.  https://docs.eigenlayer.xyz/overview/whitepaper, retrieved July. 2023.
  * [54] Xuechao Wang, Peiyao Sheng, Sreeram Kannan, Kartik Nayak, and Pramod Viswanath.  Trustboost: Boosting trust among interoperable blockchains.  arXiv preprint arXiv:2210.11571, 2022.
  * [55] Gavin Wood.  Ethereum yellow paper.  https://web.archive.org/web/20160820211734/http://gavwood.com/Paper.pdf, 2015\.
  * [56] Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abraham.  Hotstuff: Bft consensus with linearity and responsiveness.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 347–356, 2019.