IMDEA Software Institute, Spain and Universidad Politécnica de
Madridmargarita.capretto@imdea.orghttps://orcid.org/0000-0003-2329-3769 IMDEA
Software Institute,
Spainmartin.ceresa@imdea.org@imdea.orghttps://orcid.org/0000-0003-4691-5831
IMDEA Networks Institute, Spain
antonio.fernandez@imdea.orghttps://orcid.org/0000-0001-6501-2377 IMDEA
Software Institute, Spain and VISA Research,
Spainpedro.moreno@imdea.org@imdea.orghttps://orcid.org/0000-0003-2315-7839
IMDEA Software Institute,
Spaincesar.sanchez@imdea.org@imdea.orghttps://orcid.org/0000-0003-3927-4773
Jane Open Access and Joan R. Public [100]Information
systems$\rightarrow$Distributed systems organizing principles; Systems
organizing principles: Blockchain technology; Software and its
engineering$\rightarrow$Distributed systems organizing principles; Distributed
ledgers Rainer Böhme and Lucianna Kiffer 2 Advances in Financial Technologies
(AFT 2024) AFT 2024 AFT 2024 September 23–25, 2024 Vienna, Austria VV NN <-←
==≡ ++++ >>⟩ ∼  epoch,current,history,theset[the_set],proposal,valid
add,get,Init,Add,Get,BAdd,EpochInc,Broadcast,Deliver,GetEpoch,Propose,Inform,SetDeliver,
SuperSetDeliver, DoStuff[Start],Consensus translate, Translate
DPO,BAB,BRB,SBC,DSO ArrangerApi[Arranger], SequencerApi[Sequencer], DCsApi[DC
members], DCApi[DC member] call,ack,drop,return,assert,wait, post, inform,
trigger, logger send,receive,sendbrb[send_brb],sendsbc[send_sbc],
BLSAggregate[Aggr] madd[add],mepochinc[epinc]
apiBAdd,apiAdd,apiGet,apiEpochInc,apiTheSet[the_set],apiHistory S,C,B,M,DAC
history,epoch,theset[the_set],add,get,epochinc[epoch_inc],getepoch[get_epoch],tobroadcast[to_broadcast],
knowledge, pending, sent, received,proposal,Valid add, translate, allTxs,
pendingTxs, maxTime, maxSize, signReq, signResp, hashes, setchain,
localsetchain[Setchain], invalidId, invalidHash, notContacted[left],
signatures prop,propset,h,tx,id,sigs,hash, batchId[id] myturn[my_turn],
newepoch[new_epoch],added, timetopost[time_to_post],tobatch[to_batch],
nextBatch[next_batch_id] reptheorem[1] replemma[1] repprop[1]

#  Fast and Secure Decentralized Optimistic Rollups Using Setchain

Margarita Capretto  Martín Ceresa  Antonio Fernández Anta  Pedro Moreno-
Sánchez  César Sánchez

###### Abstract

Modern blockchains face a scalability challenge due to the intrinsic
throughput limitations of consensus protocols. Layer 2 optimistic rollups (L2)
are a faster alternative that offer the same interface in terms of smart
contract development and user interaction. Optimistic rollups perform most
computations offchain and make light use of an underlying blockchain (L1) to
guarantee correct behavior, implementing a cheaper blockchain on a blockchain
solution. With optimistic rollups, a _sequencer_ calculates offchain batches
of L2 transactions and commits batches (compressed or hashed) to the L1
blockchain. The use of hashes requires a data service to translate hashes into
their corresponding batches. Current L2 implementations consist of a
centralized sequencer (central authority) and an optional data availability
committee (DAC).

In this paper, we propose a decentralized L2 optimistic rollup based on
_Setchain_ , a decentralized Byzantine-tolerant implementation of sets. The
main contribution is a _fully decentralized “arranger”_ where arrangers are a
formal definition combining sequencers and DACs. We prove our implementation
correct and show empirical evidence that our solution scales. A final
contribution is a system of incentives (payments) for servers that implement
the sequencer and data availability committee protocols correctly, and a
fraud-proof mechanism to detect violations of the protocol.

###### keywords:

Blockchain, Layer Two, Data Availability Committee

###### category:

##  1 Introduction

Layer 2 (L2) rollups provide a faster alternative to blockchains, like
Ethereum [wood2014ethereum], while offering the same interface in terms of
smart contract programming and user interaction. Rollups perform as much
computation as possible offchain with minimal blockchain interaction, in terms
of the number and size of invocations, while guaranteeing a correct and
trusted operation. L2 solutions work in two phases: users inject transaction
requests through a _sequencer_ , and then, their effects are computed
_offchain_ and published in L1. The sequencer orders the received
transactions, packs them into batches, compresses batches and injects the
result in L1. State Transition Functions (SFTs) is the set of independent
parties in charge of computing transition effects offchain and publishing the
resulting effects in L1 encoded as L2 blocks.

There are two main categories of rollups:

  * •

_ZK-Rollups:_ STFs provide Zero-Knowledge proofs used to verify in L1 the
correctness of the effects claimed.

  * •

_Optimistic Rollups:_ L2 blocks posted are optimistically assumed to be
correct delegating block correctness on a fraud-proof mechanism.

Optimistic rollups include an arbitration process to solve disputes. STFs
place a stake along their fresh L2 block when posting the block to L1. Since
blocks can be incorrect, there is a fixed interval during which third parties
(competing STFs) can challenge blocks, by placing a stake. The arbitration
process is a two-player game played between a claimer and a challenger, which
is governed by an L1 smart contract. The arbitration process satisfies that a
single honest participant can always win. If the claimer loses, the block in
dispute is removed and the claimer’s stake is lost; if the claimer wins, the
challenger loses the stake. The winning party receives part of the opponent’s
stake as a compensation.

The most prominent Optimistic Rollups based on their market share [l2beat] are
Arbitrum One [ArbitrumNitro], Optimism mainnet [optimism] and Base [base],
while popular ZK-Rollups include Starknet [starknet], zkSync Era [zksyncera]
and Linea [linea].

In most rollups, a single computing node acts as sequencer, receiving user
transaction requests and posting compressed batches of transaction requests to
L1. The centralized nature of these sequencers makes these rollups a _non-
decentralized_ L2 blockchain, where the sequencer is a central authority. To
increase scalability further, other rollups implement sequencers posting
hashes of batches, instead of compressed batches, dramatically reducing the
size of the blockchain interaction. Working with hashes posted to L1 requires
an additional data service, called _data availability committee_ (DAC), to
translate hashes into the corresponding batches. If either the sequencer or
the DAC are centralized111We refer here as centralized solutions even if there
is a fixed collection of servers picked by the owners of the system., the
solution is still a non-decentralized L2 blockchain.

ZK-rollups that rely on DAC are known as _Validiums_. Current validiums
include Immutable X [immutablex], Astar zkEVM [astar], and X Layer [xlayer].
Optimistic rollups that use DAC are called _Optimiums_ , which include Mantle
[mantle], Metis [metis] and Fraxtal [fraxtal]. A list of various Ethereum
scaling solutions and their current state of decentralization can be found in
Appendix LABEL:app:decentralizationL2Eth. To simplify notation, in the rest of
the paper we use simply L2 to refer to optimistic rollups that post hashes and
have a DAC, that is Optimiums. We also use the term _arranger_ to refer to the
combined service formed by the sequencer and the DAC.

The Problem. Our goal is to reduce the control power of centralized
sequencers.222However, we do not attempt to solve more complex problems such
as order-fairness [kelkar2020orderfairness].

The Solution. We describe how to implement a _fully decentralized_ arranger.
We rely on algorithms whose trust is in the combined power of a collection of
distributed servers where correctness requires more than two thirds of the
servers run a correct version of the protocol. Our main building block is
Setchain [capretto22setchain], a Byzantine resilient distributed
implementation of grow-only sets. Using setchain, users can inject transaction
requests through any server node where they remain unordered until a
“barrier”, named epoch, is injected. Setchain is reported in
[capretto22setchain] to be three orders of magnitude faster than consensus, by
exploiting the lack of order between barriers to use a more efficient
distributed protocol to disseminate transactions requests. We build in this
paper a decentralized arranger using setchain, by using epochs to determine
batches. Since all correct arranger nodes include a correct setchain node,
they agree on each batch and can locally compute the hash of a batch, and
reverse hashes into batches. It is well known that Byzantine distributed
algorithms do not compose well in terms of correctness and scalability
[capretto22setchain], partly because the different components need to build
defensive mechanisms to guarantee correctness. Here we implement an arranger
by combining in each distributed node the role of a sequencer and a DAC
member, so a correct server node includes a correct implementation of a
setchain, and a correct participant in the sequencer and DAC services.
Setchain (and in consequence the decentralized arranger) is a permissioned
protocol, so servers participating are fixed and known to all other
participants. Protocols to elect and replace arranger nodes are out of the
scope of this paper.

Servers can also post hashes to L1 with the guarantee that all correct servers
know the reverse translation. Agents, like STFs, can contact any setchain
server to obtain the batch of a given hash.

Finally, we introduce _incentives_ for servers forming the arranger to behave
properly, for example, including payments for generating and signing hashes,
posting correct batches into L1, and performing reverse translations. These
servers place stakes when posting batch hashes and are rewarded for batches
that consolidate. If a batch or hash is proven incorrect all servers involved
lose their stake. To the best of our knowledge, this is the first paper to
introduce incentives for arrangers (sequencer and DACs) of decentralized L2.
Our incentives are general and do not depend on the concrete implementation of
the sequencer or DAC (they do not depend on the use of setchain to implement
and arranger presented in this paper).

Contributions. In summary, the contributions of this paper are:

  * •

A formal definition of L2 arrangers;

  * •

A fully decentralized arranger based on setchain and a proof of its
correctness;

  * •

Economic incentives including payments and fraud-proof mechanisms to detect
protocol violations and punishments for incorrect servers;

  * •

An analysis of two adversary models and their impact on the correctness of our
solution;

  * •

Implementations of all building blocks to empirically assess that they can be
used to implement an efficient scalable decentralized arranger.

##  2 Preliminaries

In this section, we briefly present our assumptions about the underlying
execution system, Optimistic Rollups and Optimiums, and Setchain.

##### Assumptions of the Model of Computation.

Distributed systems consist of processes (clients and servers) with an
underlying network that they use to communicate, using message passing.
Processes compute independently, at their speed, and their internal states
remain unknown to other processes. Message transfer delays are arbitrary but
finite and remain unknown to processes. Servers communicate among themselves
to implement distributed data-types with certain guarantees and clients can
communicate with servers to exercise such data-types.

Processes can fail and behave arbitrarily. We bound the number of Byzantine
failing servers $f$ by a fraction of the total number of servers. In Section 5
we introduce _economic incentives and deferrals_ that motivate servers to be
honest. All processes (including clients) have pairs of public and private
keys, and public keys are known to all processes. The set of servers is fixed
and known to all participants. We assume reliable channels between non-
Byzantine processes, messages are not lost, duplicated or modified, and are
authenticated. Messages corrupted or fabricated by Byzantine processes are
detected and discarded by correct processes [Cristin1996AtomicBroadcast].
Since each message is authenticated, communication between correct processes
is reliable. Additionally, we assume that the distributed system is partially
synchronous [Crain2021RedBelly, Fischer1985Impossibility]. Finally, we assume
clients create valid elements and servers can locally check their validity. In
the context of blockchains, this is implemented using public-key cryptography.

|
---|---
Fig. 1: Optimistic Rollups (left) and Optimiums (right).

###  2.1 Optimistic Rollups and Optimiums

The main principle of Optimistic Rollups is to split transaction sequencing
from transaction execution whose effects are delayed to allow arbitration.
Optimistic Rollups are implemented as two components (see Fig. 1 (left)): a
_sequencer_ , in charge of ordering transactions, and a _state transition
function_ (STF), responsible for executing transactions (this terminology was
introduced by Arbitrum [Kalodner2018Arbitrum]). The sequencer collects
transaction requests from users, packs them into batches, and posts compressed
batches—using a reversible compression algorithm [Alakuijala18brotli]—as a
_single_ invocation into L1 (Ethereum). Once posted, compressed batches of
transactions are immutable and visible to anyone.

STFs compute the effects of transaction batches which are completely
determined by the sequence of transactions and the previous state of the L2
blockchain. STFs are independent processes that can propose new L2 states as
L2 block _assertions_ into L1. L2 blocks are optimistically assumed to be
correct. STF processes can challenge L2 blocks posted by other STFs during a
challenge period (typically more than one day). If an STF challenges an
assertion, a bisection protocol—which guarantees that an honest players can
win—is played between the STFs involved. If the challenger wins, the L2 block
is discarded; otherwise it continues on hold until the challenge period ends.
L2 blocks that survive the challenge period consolidate and the L2 blockchain
evolves.

In Optimistic Rollups, the sequencer is a centralized process and does not
offer any guarantee regarding transaction orders or whether transaction
requests can be discarded. To prevent censorship from the sequencer, some
rollups allow users to post transaction requests directly to L1.

Even though batches are compressed in Optimistic Rollups, the L1 gas
associated with posting batches is still significant. To mitigate this cost,
Optimiums introduce a _Data Availability Committee_ (DAC) storing batches and
providing them upon request (see Fig. 1 (right)). In current Optimiums, the
sequencer posts a hash of a batch—which is much smaller than the compressed
batch—along with evidence that the batch is available from at least one honest
DAC server. Some implementations, to guarantee progress, provide a fallback
mechanism, such that the sequencer either collects enough signatures within a
specified time frame or posts the compressed batch into L1. STFs then check
that hashes posted have enough valid signatures and request the corresponding
batch to DAC members. Recall that in the rest of the paper we will use “L2” to
refer to the Optimium extension of Layer 2 Optimistic Rollups that post hashes
to L1 and implements a DAC.

###  2.2 Setchain

Setchain [capretto22setchain] is a Byzantine-fault tolerant distributed data-
structure that implements grow-only sets with synchronization barriers called
epochs. Clients can add elements to any server and servers disseminate new
elements to the other servers. When barriers are introduced, a set consensus
protocol [Crain2021RedBelly] is run and all correct servers agree on the
content of the new epoch after which elements can be deterministically
ordered. Setchain efficiently exploits the lack of order between barriers.
Empirical evaluation suggests that setchain is three orders of magnitude
faster than conventional blockchains [capretto22setchain].

|
---|---
Fig. 2: Applying $\<add>(e)$ after epoch $3$ (left) and increasing to epoch
$4$ (right).

##### API.

Setchain server nodes store locally the following information: (1) a set of
added transaction requests: $\<theset>$; (2) the current epoch number:
$\<epoch>$; (3) the current mapping from natural numbers to sets of
transaction requests describing each epoch: $\<history>$. Servers support two
operations, always available to any client process: operation $\<add>$ adds
elements to $\<theset>$; operation $\<get>$ returns the local values of
$\<theset>$, $\<history>$, and $\<epoch>$, as perceived by the server.333We
present this API for simplicity but Setchain supports membership queries to
get individual epochs. We assume epoch changes happen regularly as this can be
forced by the participant servers using a local time-out.

Fig. 2 shows the local view of a Setchain server node $v$. Set $v.\<pending>$
contains those elements that $v$ knows but that have not been assigned an
epoch yet: $v.\<pending>=v.\<theset>\setminus v.\<history>$. To insert a new
element $e$ in the setchain, clients can invoke $v.\<add>(e)$. Server $v$
checks the validity of $e$, propagates it and adds it to $v.\<pending>$. When
an epoch increment is triggered, servers propose their elements in
$\<pending>$ and collaboratively decide which of those elements form the new
epoch, see Fig. 2 (right). Servers also sign the hash of each epoch and
disseminate this signature, for example as a Setchain element. Clients can
contact a single server and authenticate the response by counting the amount
of signatures provided.

##### Relevant Properties of Setchain.

We list here the properties of setchain relevant for arrangers in Section 4.2.
See [capretto22setchain] for a more exhaustive list of properties and proofs.

  * •

Setchain-GetGlobal: Adding an element $e$ to a correct server eventually
results in $e$ being in $\<theset>$ returned by $\<get>$ invocations on every
correct server.

  * •

Setchain-GetAfterAdd: Adding a valid element $e$ to a correct server
eventually results in $e$ being in $\<history>$ returned by a $\<get>$ on
correct servers.

  * •

Setchain-UniqueEpoch: Every element is in at most one epoch.

  * •

Setchain-ConsistentGets: All correct servers agree on the content of each
epoch.

  * •

Setchain-ValidGet: Each element $e$ returned by a $\<get>$ operation in
correct servers is a valid element.

##  3 Arranger

In this section, we formally define the notion of L2 arranger (or _arranger_
for short) as the service in charge of receiving and serializing transaction
requests, packing them into batches, efficiently posting them into L1, and
making the data available.

An arranger encompasses both the sequencer and DAC of a L2 solution. We
propose an integrated decentralized implementation that aims to replace both
sequencers and DAC. Arrangers have two kinds of clients: external users
injecting L2 transaction requests and STFs computing L2 blocks. STF agents
need to determine which transaction belongs to a given batch to compute L2
blocks and to decide if they should dispute L2 blocks proposed by other STF
agents. We say “the arranger posts to L1” to refer to the action of some
arranger server process posting to L1.

###  3.1 Arranger API

Arrangers use Merkle Trees [Merkle88] as hash function $\mathcal{H}$ to hash
batches where the leaves are the transactions in the batch. Merkle trees
provide an efficient (logarithmic) membership authenticated check. We rely on
this method to create an arbitration mechanism to dispute membership where an
honest participant can prove the validity of hashes and prevent the
confirmation of invalid hashes (see Section 5.4).

Arranger servers order transactions, pack them into batches and create the
hashes of each batch, also assigning consecutive identifiers to consecutive
batches. Periodically, batch identifiers with their hashes and signatures are
posted to L1 invoking a smart contract called logger>.

Arrangers export two operations to all clients: operation add>(tx>) to send
transaction request tx> to the arranger so tx> is added to a future batch; and
operation translate>($\<id>,\<h>$) which requests the batch of transactions
corresponding to hash $\<h>$ with identifier $\<id>$. If $\<id>$ does not
match any batch, the arranger returns error invalidId>. If there is a batch
$b$ with identifier id>, the arranger returns $b$ if it hashes to $\<h>$ or an
error invalidHash> otherwise.

When the arranger receives enough transactions (or a timeout is reached), all
correct servers decide a new batch $b$, order transactions in $b$, assign an
identifier $\<id>$ to $b$, compute $h=\mathcal{H}(b)$, and create a “ _batch
tag_ ” $(\<id>,h)$. Each correct server signs the new tag and propagates the
signature. When enough signatures are collected, a combined signature
$\sigma=\<sigs>(\<id>,\<h>)$ is attached to the tag to form a “ _signed batch
tag_ ” $(\<id>,\<h>,\<sigs>(\<id>,\<h>))$, which is posted to L1. The logger
contract (in L1) accepts the signed batch tag but _does not_ perform any
validation check, optimistically assuming that the batch is legal. An
arbitration protocol, described in Section 5.4, guarantees correctness of the
batches (this is similar to L2 block claims in Optimistic Rollups). Finally,
STFs observe the signed batch tags in L1, contact the arranger invoking
$\<translate>$ to obtain the batch of transactions and compute the next L2
block or check the validity of posted L2 blocks.

Arranger processes can post multiple batch tags with the same identifier and
the logger contract will accept them all. However, for each identifier, the
STF agents only process the first valid signed batch tag, discarding the rest.

###  3.2 Desired Arranger Properties

We formally define the properties of _correct_ arrangers. These properties
include all _basic properties_ and some safety properties of ideal arrangers
presented in [motepalli2023sok].

Signed batch tags are _legal_ if they satisfy the following properties:

  * •

Certified: have at least $f+1$ arranger server signatures (see Section 2)
guaranteeing at least one correct server signed the batch tag.

  * •

Validity: Every transaction in the batch is a valid transaction added by a
client.444A transaction is valid when is properly formed and signed by the
originating client.

  * •

$\bf\textit{{Integrity}}_{1}$: No transaction appears twice in its batch.

A batch tag is legal if it appears in a legally signed batch tag. A legal
batch tag can be part of two legal signed batch tags when signed by a
different subset of arranger processes. However, all legal batch tags with the
same identifier have the same batch of transactions because all correct
servers agree on the batch content. This ensures a deterministic evolution of
the blockchain. Formally, let $(\<id>,\<h>_{1},\sigma_{1})$ and
$(\<id>,\<h>_{2},\sigma_{2})$ be two legally signed batch tags posted by the
arranger, such taht $\sigma_{1}=\<sigs>(\<id>,\<h>_{1})$ and
$\sigma_{2}=\<sigs>(\<id>,\<h>_{2})$ are signed by at least $f+1$ nodes, then
$\<h>_{1}=\<h>_{2}$.

######  Property 1.

Unique Batch: all legal batch tags with the same identifier correspond to the
same batch of transactions.

The following property prevents transaction duplication, censorship and
guarantees data availability.

######  Property 2.

Correct arrangers satisfy:

  * •

Termination: all added valid transactions eventually appear in a legal batch
tag.

  * •

$\bf\textit{{Integrity}}_{2}$: no transactions appears in more than one legal
batch tag.

  * •

Availability: every legal batch tag posted can be translated into its batch.

Availability is expressed formally as follows. Let $(\<id>,\<h>,\sigma)$ be a
legal batch tag posted by the arranger, s.t. $\<h>=\mathcal{H}(b)$. Then the
arranger, upon request $\<translate>(\<id>,\<h>)$, returns $b$. This prevents
halting the L2 blockchain by failing to provide batches of transactions from
hashes.

Validity, $\bf\textit{{Integrity}}_{1}$, $\bf\textit{{Integrity}}_{2}$, Unique
Batch and Availability are safety properties and Termination is a liveness
property, together they define correct arrangers. However, the properties
listed above do not guarantee any order of transactions posted by clients.

##  4 A Fully Decentralized Arranger Implementation

Implementing a fully centralized arranger is straightforward. Similarly, an
arranger that consists of a sequencer and a decentralized DAC is also
straightforward from the point of view of arranger. The central sequencer
handles transaction ordering, batch creation, hashing, and communicates with
each DAC member to share batches and obtain their signatures (see Appendix A
for a more detailed description). The real challenge resides in implementing a
correct arranger where both the sequencer and the DAC are decentralized.

We present now a _fully decentralized_ arranger implementation using Setchain
satisfying all correctness properties listed in Section 3.2. Both add> and
translate> are implemented in a completely decentralized fashion.

For simplicity, we assume that our implementation (see the figure above) uses
Setchain epochs as batches. In our fully decentralized arranger, all servers
perform both the roles of sequencers and DAC members, and take turns to post
data to L1.

###  4.1 Implementation

Algorithm 1 shows the pseudo-code of correct servers of decentralized
arrangers. Arranger processes _extend_ Setchain servers [capretto22setchain,
Alg. 6] (see Appendix B). Here, all servers cryptographically sign each epoch
hash and insert the signature back into the Setchain as an element. This
allows servers to locally provide cryptographic guarantees to clients about
the correctness of an epoch simply by exhibiting $f+1$ signatures. Servers
running Algorithm 1 maintain a local map hashes> storing inverse translations
of hashes and a local set $\<signatures>$ to store cryptographically signed
epochs.

Algorithm 1 Server implementation of decentralized Arranger extending Setchain

1:extends  Setchain

2:init:
$\<hashes>\leftarrow\emptyset,\<signatures>\leftarrow\emptyset,\<localsetchain>.init$

3:function add>($t$)

4: $\<localsetchain>.\<Add>(t)$

5: return>

6:function translate>($\textit{id},h$)

7: if $(\<id>,\\_)\notin\<hashes>$ then return> invalidId>

8: else

9: if $(\<id>,h)\notin\<hashes>$ then return> invalidHash>

10: else return> $\<hashes>(\<id>,h)$

11:upon ($\<newepoch>(\<id>,E)$) do

12: $b\leftarrow\<tobatch>(E)$

13: $h\leftarrow\mathcal{H}(b)$

14: $\<hashes>\leftarrow\<hashes>\cup\\{(\<id>,h),b\\}$

15:upon ($\<added>(epoch\\_signature(id,h,sig_{j}(\<id>,h)))$) do

16: $\<signatures>\leftarrow\<signatures>\cup\\{(id,h,sig_{j}(id,h))\\}$

17:upon ($\<myturn>$) do

18: $id\leftarrow\<nextBatch>()$

19: wait> for $f+1$ signatures $(id,h,sig_{j}(id,h))$ in signatures>

20: logger>.post>$(id,h,\<BLSAggregate>(\bigcup_{i}sig_{i}(id,h)))$

Distributed arranger processes implement add> by adding transaction requests
as elements into the Setchain which, in turn, triggers communication with
other processes maintaining the Setchain. When a new epoch is decided by the
Setchain internal set consensus, each process locally receives a $\<newepoch>$
event with the epoch number and its content, and $\<tobatch>$ is invoked. This
function separates transactions contained in epochs from elements serving as
“metadata” (for example, server signatures of previous epochs). The resulting
transactions are ordered and packed into a new batch and hashes> is updated.
For simplicity in the explanation, we associate hashing epochs in
[capretto22setchain, Alg. 6] with hashing batches, that is, for each epoch $e$
with hash $h_{s}$, as used in Setchain, we assume that
$h_{s}=\mathcal{H}(\<tobatch>(e))$. Hence, when a new epoch is created, each
server cryptographically signs the batch hash and inserts the signature as an
element in the Setchain. Each server receives an $\<added>$ event informing
the arranger about cryptographically signed batch hashes and the arranger sub-
process stores the signatures received in the local set $\<signatures>$.

Arranger servers take turns posting legal signed batch tags into the logger
contract in L1, slicing time and distribute time slices between them, which is
feasible because we assumed the system to be partially synchronous (and slices
can be reasonably long intervals, like minutes). Event myturn> tells processes
when it is their turn to post a new batch tag to L1. This is a simple way to
guarantee eventual progress. Even if Byzantine processes do not post legal
batch tags in their turns, the rounds will continue to advance until the turn
of a correct process arrives to post legal batch tags (see Lemma 4.3 below).
Function $\<nextBatch>$ returns the next batch identifier to be posted to the
logger contract which is the minimum identifier for which there is no legal
batch tag in L1. When it is the turn of arranger server $P$ to post and $P$
has received enough signatures for the batch, $P$ computes a combined
signature $\sigma$ and posts the legally signed batch tag
$(\<batchId>,h,\sigma)$ into the logger L1 contract.

###  4.2 Proof of Correctness

Algorithm 1 implements a correct arranger. We inherit the assumptions from
Setchain, so for $N$ total servers, the maximum number of Byzantine processes
is $f$ such that $f<N/3$.

We first prove that each legally signed batch tag corresponds with a Setchain
epoch. Let $(\<batchId>,\mathcal{H}(b),\sigma))$ be a legally signed batch tag
posted into L1, then $\<tobatch>(e)=b$ in the Setchain where epoch $e$
corresponds to epoch number $\<batchId>$.

######  Lemma 4.1.

Batches of transactions in legal batch tags correspond to transactions in
Setchain epochs.

######  Proof 4.2.

Legal batch tags require at least one correct server signature and correct
servers only sign epoch hashes.

Property Unique Batch follows directly from the previous lemma, as the batch
of transactions of each legal batch tag with identifier $\<batchId>$
corresponds to epoch $e$. Moreover, due to property Setchain-UniqueEpoch, no
transaction in a legal batch appears twice in the same batch or appears in
another legal batch, satisfying properties $\bf\textit{{Integrity}}_{1}$ and
$\bf\textit{{Integrity}}_{2}$.

Byzantine servers can re-post existing legally signed batch tags, but they can
not forge fake batches or fabricate legally signed batch tags because this
requires collecting $f+1$ signatures. Hence, all Byzantine servers can do is
to post the same batch tag several times (perhaps with different collections
of $f+1$ signatures). Since STFs process one legal batch tag per identifier,
no transaction is executed twice and repeated batches are discarded. In
Section 5.4 we introduce arbitration mechanisms penalizing arranger servers
for posting illegal batches.

Combining property Setchain-ValidGet (see Section 2.2) with Lemma 4.1, legal
batch tags only contain valid transactions, so Validity holds.

######  Lemma 4.3.

All Setchain epochs become legal batch tags.

######  Proof 4.4.

Let $\<batchId>$ be the minimum epoch number for which there is no legal batch
tag posted and let $e$ be $\<batchId>$-th epoch. Property Setchain-
ConsistentGets ensures all correct servers agree on the content of $e$.
Setchain servers cryptographically sign epoch hashes and insert their
signature in the Setchain as elements. By Setchain-GetGlobal, all servers
eventually receive the signatures injected. Let $s$ be the first correct
server in charge of posting batch tags to the logger after receiving at least
$f+1$ signatures of epoch $e$. There are two cases: either $\<nextBatch>$
returns $\<batchId>$ or a larger identifier. In the former case, $s$ has
enough signatures to generate a legal batch tag for $e$ and posts it in the
logger contract (lines 17-20). In the latter case, a legal batch tag with
identifier $\<batchId>$ has already been posted corresponding to epoch
$e^{\prime}$ (see Lemma 4.1). By Setchain-ConsistentGets, we have that
$e^{\prime}=e$.

Transactions added to at least one correct server eventually appear in a legal
batch tag, which follows from the previous lemma and property Setchain-
GetAfterAdd. Therefore, clients contacting one correct server are guaranteed
Termination. Clients can make sure that they contact at least on good server
contacting $f+1$ servers. Alternatively, they can contact one server and check
that the answer is correct by checking the cryptographic signatures of the
epochs reported (and contact another server if the check fails).

Finally, we prove that every hash in a legal batch tag posted by the arranger
can be resolved by at least one correct arranger server, satisfying Property
Availability.

######  Lemma 4.5.

For every legal batch tag posted by the arranger, at least one correct server
$A$ signed it and therefore $A$ can resolve its hash.

######  Proof 4.6.

Since legal batch tags have $f+1$ signatures, at least one signature comes
from a correct server. By Lemma 4.1, all legal batch tags correspond to
Setchain epochs. When Setchain computes an epoch, it triggers an event
$\<newepoch>$ signaling the arranger to add the hash to its local map
$\<hashes>$. Upon request, function $\<translate>$ uses $\<hashes>$ to obtain
the batch that corresponds to a given hash. Correct servers never delete
information from $\<hashes>$, so for every legal batch tag posted at least one
of the correct servers that signed the batch tag can resolve its hash.

Lemma 4.5 guarantees that when posting legally signed batch tags to the logger
contract, at least one correct server signed the batch, so the same correct
server is capable of performing the translation. Eventually, _all_ correct
servers will know the contents of every epoch so they will be able to
translate as well.

Through this section, we assumed $f<N/3$. In the next section, (1) we explore
incentives that motivate rational servers to behave correctly, (2) we present
a protocol based on zero-knowledge contingent payments for clients to pay
servers for correctly translating hashes, and (3) we present fraud-proof
mechanisms to detect violations of the protocol. Then, in Section 6 we study
adversaries that control the number $f$ Byzantine servers and can potentially
bribe the remaining honest servers and the consequences.

##  5 Fraud-proof Mechanisms and Incentives

So far we assumed a bound number of Byzantine servers $f$ without reasoning
why would servers should be honest, in this section, we incentive servers to
be honest. We provide incentives based on (1) evidence of work with payments
and (2) evidence of malicious behavior with penalties. We present fraud-proof
mechanisms to detect malicious behavior where a single _honest agent_ with
enough tokens to participate in the challenge can uncover malicious behavior.
We perform a simple analysis based on the assumption that rational agents tend
to engage in actions that directly enhance their profit and refrain from
activities that incur in losses. A more detailed quantitative study including
expected utility is left as future work.

We assume participating processes have public L2 and L1 accounts where they
can receive their rewards and—depending on the protocol—provide stakes that
can be removed as a penalty.

###  5.1 Batch Staking and Confirmation

Malicious arrangers can post illegal batches in L1 as optimistically no check
is performed by the logger contract. To discourage this behavior, arranger
processes stake on the batches they post. When an STF posts an L2 block, it
places a stake in the L2 block and implicitly on the batch from which the
transactions are extracted to compute the block. Processes regain their stake
when signed batch tags are _confirmed_ , that is, when the corresponding L2
block is confirmed, after a confirmation delay as in Optimistic Rollups and
Optimiums. When a signed batch tag is confirmed, all other batch tags with the
same identifier are discarded and stakes are returned as well. Before
confirmation, signed batch tags can be challenged, and staking processes that
fail to defend their correctness lose their stake. If a signed batch tag has
no stake, it is discarded, along with all L2 blocks executing its
transactions.

In Section 5.4 below, we present fraud-proof mechanisms to unilaterally prove
that signed batch tags are illegal and force staking processes to reveal the
transactions within a given batch. A challenger that plays properly the
challenging protocols always wins against a defender posting an illegal batch
tag, even if the challenger does not know the batch content.

###  5.2 Incentives to Generate and Post Batches

The confirmation of batches generates rewards as follows. For each confirmed
batch posted:

  * •

Each participating arranger process receives a constant amount of $k_{1}$ L2
tokens.

  * •

Each process that signs a batch receives $k_{2}$ L2 tokens determined by a
monotone function $g$ on the number of processes signing $\sigma$ (the more
signatures, the higher the reward for all signers) and of transactions in
batch $b$.555 Function $g$ is monotone if for all $x,x^{\prime},y,y^{\prime}$,
if $(x\leq x^{\prime}$ and $y<y^{\prime})$ or $(x<x^{\prime}$ and $y\leq
y^{\prime})$ then $g(x,y)<g(x^{\prime},y^{\prime})$. This function is fixed
and known a priori. Processes signing batches receive $k_{1}+k_{2}$ L2 tokens
for each confirmed batch.

  * •

The process posting the batch in L1 receives an additional payment $k_{3}$ L2
tokens to cover the cost of posting transactions in L1. This process receives
$k_{1}+k_{2}+k_{3}$ L2 tokens.

This mechanism creates incentives to (1) participate in the decentralized
protocol maintaining the arranger, (2) sign batches, communicate and collect
signatures, and (3) include as many transactions as possible in a batch to be
posted in L1.

All payments are charged to the external users posting transactions and made
effective by the STFs when computing the effects of a batch, including these
effects as part of a new L2 block. Additional L2 tokens can be minted by the
L1 contract governing the L2 blockchain.

###  5.3 Incentive to Translate Hashes into Batches

We present now an additional protocol for servers to translate hashes and get
paid using zero-knowledge contingent payments [campanelli2017zkcontingent,
fuchsbauer2019WIIsNotEnough, nguyen2020WIIsAlmostEnough]. When a client C
requests the translation of a hash $h$ contacting directly server S, if S
knows the inverse translation $b$, S does not respond with $b$. Instead, S
encrypts $b$ using a secret key $k$, such that $w=\texttt{Enc}_{k}(b)$ and
computes $y$ such that $\texttt{SHA256}(k)=y$. Then, S sends $w$ and $y$ to C
along with a zero-knowledge proof that $w$ is an encryption of $b$ under key
$k$ and that $\texttt{SHA256}(k)=y$. Client C verifies the proof and, if it is
correct, C generates a contingent payment where S is the only beneficiary.
Server S can only collect the payment by revealing the secret $k$. When S
reveals $k$, C learns $k$ (so it can decipher $w$ to obtain $b$) and S
receives the payment. Appendix C shows the pseudo-code implementing a payment
system based on hashed-timelock contracts. All communication between S and C
is offchain and one-to-one, and thus, batch $b$ is never posted in L1.

Byzantine servers can participate in the first part of the protocol and then
refuse to reveal $k$ causing client C to incur in unnecessary costs. To
prevent this, servers must also sign $y$ and send the signature to C, so C has
evidence identifying the specific server from which S obtained $y$. If the
server fails to disclose $k$ after some L1 blocks has passed, C can use this
evidence to accuse server S, have server S stake removed and receive some
compensation.

###  5.4 Fraud-proof Mechanisms to Prevent Illegal Batches

We now present fraud-proof mechanisms to deter servers from posting illegal
batch tags. These mechanisms are similar to the one used in Optimistic Rollups
to arbitrate L2 blocks. The main difference is that here the arbitration is
over concrete algorithms and not over the execution of arbitrary smart
contracts translated to WASM [wasm].

A signed batch tag $t:(\<batchId>,h,\sigma)$ for a batch $b$ is legal if:

  1. B1.

The combined signature $\sigma$ contains at least $f+1$ arranger process
signatures.

  2. B2.

Batch $b$ only contains valid transactions.

  3. B3.

No transaction in $b$ is duplicated.

  4. B4.

No transaction in $b$ appears in a previously consolidated batch.

####  5.4.1 Data Availability Challenge.

To check a signed batch tag $t$ is _legal_ , processes need to know the
transactions in the batch, but only the batch hash $h$ is posted as part of
$t$. As a safeguard, we introduce first a data availability challenge, which
enables any agent A to challenge any staking server S to publish the batch
transactions in L1. The data availability challenge is implemented as a game
governed by an L1 smart contract (see Alg. 5 in Appendix D for details). Both
player take turns with a predetermined time for each move. The game is played
over the Merkle tree generated by batch $b$.

During its turn, A can challenge a specific node $n$ in the Merkle tree. The
node hash, $h_{n}$, is available in the L1 contract but A does not know the
corresponding batch of transactions. Initially, only the root hash is known,
as it is included in the batch tag. When posting a challenge, A puts a stake
large enough to cover part of S potential answering expenses.

Server S has two options for responding to a challenge on a node. If $n$ is a
leaf, S posts the transaction $e$ that $n$ represents. The L1 contract
verifies that $e$ hashes to $h_{n}$. Otherwise, S posts the hashes, $h_{l}$
and $h_{r}$, of the challenged node left and right children, along with their
corresponding compressed batches $b_{l}$ and $b_{r}$. In this case, the L1
contract simply verifies that $h_{n}$ is obtained by hashing the concatenation
of $h_{l}$ and $h_{r}$, ensuring that both hashes effectively belong to the
Merkle tree. The decompression of the both batches is done offchain by A. If
decompressing $b_{l}$ results in a batch hashing to $h_{l}$, and $b_{r}$
results in a batch hashing to $h_{r}$, A just learned all transactions hashing
to $h_{n}$. Conversely, if a compressed batch does not match its hash, A can
challenge the corresponding node.

If S does not respond in time or the provided information fails the L1
contract verification, A wins the game and S loses it stake. Otherwise, A will
ultimately learn all transaction in $b$.

DAC For each unconfirmed signed batch tag posted in L1, any honest agent can
force to either learn its transaction or get the batch tag removed.

In the worst case, every node in the Merkle tree is challenged
once.666Information is public in L1, so it makes no sense to challenge the
same node twice. That is, the maximum number of turns in this game is linear
in the size of batch $b$.

A crucial difference between this mechanism and the offchain protocol
described in Section 5.3 is that this mechanism provides evidence if a staker
does not translate a hash leading to the removal of its stake as a punishment.
However, this mechanism requires posting the compressed batch onchain. Posting
onchain is more expensive for clients and there is no rewarding for servers.
Therefore, under normal circumstances, only the offchain protocol is used to
translate hashes (see Section 5.4.3).

####  5.4.2 Fraud-proof Mechanisms to Challenge Batch Legality

Once A obtains the data, it can verify locally the legality of the batch tag.
The mechanisms are governed by L1 smart contracts that arbitrate the
challenges (see Appendix D for their pseudo-codes). If a tag is illegal,
depending on which condition B1, B2, B3 or B4 is violated, agent A can play
one of the following challenging games:

  * •

Signature Challenge (violation of B1). We use one L1 contract to check whether
$t$ has enough signatures. Another L1 contract computes the aggregated public
key of the claimed signers and checks that the signature provided in $t$ is
correct.777Alternatively, a fraud-proof mechanism, arbitrated by an L1
contract, can be implemented to arbitrate that the algorithm that checks
multi-signatures accepts the signature provided. If A invokes these contracts
and it is revealed that the signature is incorrect, then the signed batch tag
$t$ is discarded, all staking processes lose their stake and A gains part of
the stakes placed on $t$.

  * •

Validity Challenge (violation of B2). Agent A knows there is an invalid
transaction $e$ in batch $t$. In this case, A challenges a staking server S to
play a game in L1 similar to data availability challenge. This time the game
is played bottom-up over the path from the leaf where A claims that $e$ is. In
its first turn, A presents $e$, and its hash $h_{e}$, its position in the
batch, and the hash of the node in the middle of the path from the leaf to the
root, bisecting the path. An L1 smart contract (called the Validity Challenge
contract) first verifies the validity of transaction $e$ and checks that its
hash is $h_{e}$. This contract is also used to arbitrate a bisection game over
the path. In the subsequent turns, players alternately perform the following
operation: S selects one subpath and challenges it. If the subpath is longer
than two, then in its next turn A must provide the hash of the middle node in
that subpath. Otherwise, the bisection is over and A must provide evidence
that the subpath is correct. For a subpath that has only two nodes with hashes
$h_{p}$ and $h_{c}$, where the node with hash $h_{p}$ is the parent of the
node with hash $h_{c}$, A must post a hash $h$. The Validity Challenge
contract verifies that hashing the concatenation of $h$ with $h_{c}$ results
in $h_{p}$. If the hash provided is correct A wins the game. If A wins the
game then S lose its stake and A receives part of it. Otherwise, S keeps its
stake. It is important to note that the L1 smart contract verifies hashes only
during A’s first turn and when a subpath reaches two nodes. Since the path
length is halved at each turn, the maximum number of turn in the game is
logarithmic in the path length which itself is logarithmic in the batch size.

  * •

Integrity Challenge 1 (violation of B3): Agent A knows a transaction $e$ that
appears twice in $t$. In this case, A challenges a staking server S to play a
game in L1 (controlled by the Integrity Challenge 1 contract) similar to the
validity challenge, but A provides two paths in $t$ where $e$ is a leaf. The
smart contract does not perform any check in this step. For each path A
presents the batch tag, the hash of $e$, the position of $e$ in the
corresponding batch, and the hash of the middle node on the path from $e$ to
the root. After that, the game continues exactly as in the validity challenge.

  * •

Integrity Challenge 2 (violation of B4): Agent A knows a transaction $e$ in
$t$ that appears in a previously confirmed batch tag $t^{\prime}$. In this
case, A challenges a staking server S to play a game in L1 similar to
integrity challenge 1, but in its first turn A provides not only paths in $t$
where $e$ is a leaf, but also $t^{\prime}$ identifier and the path in
$t^{\prime}$ where $e$ is a leaf. After that, the game continues exactly as in
the integrity challenge 1.

In all previous challenges an honest agent A that knows the transactions
associated with an illegal batch tag can win the corresponding challenge
resulting in the batch tag being discarded.

correctness Let $t$ be an illegal batch tag that is not yet confirmed in L1,
and A be an honest agent that knows all transactions in $t$ and all
transactions in already confirmed batches. Agent A can prevent the
confirmation of $t$.

By combining Propositions 5.4.1 and 5.4.2 illegal batch tags can be removed by
a single honest agent.

######  Corollary 5.1.

Any honest agent can ensure that all confirmed batches are legal.

An honest agent that knows the transactions in a legal batch tag can guarantee
its confirmation if no other valid batch tag with the same identifier was
posted in L1. This confirmation process involves computing the transactions
effects, posting them to L1, and successfully responding to any challenge.

correctness2 Let $t$ be a legal batch tag still unconfirmed in L1 for which
there is no previous legal batch tag posted in L1 with the same identifier. An
honest agent, A, that knows all transactions in $t$ and all transactions in
already confirmed batches, can guarantee its confirmation.

######  Proof 5.2.

(sketch) Since A knows all transactions in $t$, A can compute their effect and
post it as an L2 block. If the L2 block is challenged, A can win the challenge
by correctly playing the fraud proof mechanism of the L2 blockchain. We need
to prove that A can keep its stake in $t$ until the corresponding L2 block is
confirmed, that is, that A can win each challenge. For the data challenge A
computes the Merkle tree $mt$ associated with the transactions in $t$ and uses
$mt$ to answer all challenges correctly. Since $t$ is correctly signed by at
least $f+1$ arranger processes the L1 smart contract directly passes the
signature challenge. The remaining challenges are the validity and integrity
challenges. In those cases, the challenger tries to prove that an element that
does not belong to a given Merkle tree $mt$ is actually in $mt$. To win the
challenge, A maintains the invariant that after its turn in the challenged
subpath the top node belongs to $mt$ while the bottom node does not. When the
challenged subpath has two nodes with hashes $h_{p}$ and $h_{c}$, where the
node with hash $h_{p}$ is the parent of the node with hash $h_{c}$, the
challenger needs to post a hash $h$ such that the concatenation of $h$ with
$h_{c}$ hashes to $h_{p}$. However, the challenger cannot provide such an $h$
as, by the invariant, $h_{p}$ belongs to $mt$ but $h_{c}$ does not.

Combining the previous proposition with Properties Unique Batch and
Termination of correct arrangers, the following holds:

######  Corollary 5.3.

All valid transactions added to correct arrangers are eventually executed.

Propositions 5.4.1, 5.4.2 and 5.1, and Corollary 5.1 hold even when the number
of Byzantine servers in the arranger is not bounded by $f$. In other words, it
does not matter the amount of Byzantine nodes, an honest agent can guarantee
the properties mentioned above.

Current rollups do not provide any mechanism to guarantee that batches posted
by their arranger are correct, because their arranger is a centralized
sequencer which is _assumed_ to be correct. The centralized sequencer in
Optimistic Rollups can post data that does not correspond to a compressed
batch of valid transaction requests. Similarly, the sequencer of Optimiums can
post a hash that is not signed by enough members of the DAC or whose inverse
does not represent a batch of new valid transactions. The implications of
these actions are significant, as malicious STFs could post illegal new L2
states that cannot be disputed by other STF processes as they do not know the
transactions to play the challenging game. Hence, a malicious sequencer in
current rollups can block the L2 blockchain or, even worse, create
indisputable incorrect blocks. This is not possible in our solution.

####  5.4.3 Challenge Mechanisms Cost Analysis

We perform a simple analysis between costs and rewards for each challenge
mechanism and the translation protocol to determine the minimum budget
required by honest agents. We start by defining the following variables:

  * •

variable $s$ is the minimum amount of tokens needed to stake in a batch tag.

  * •

variable $cc_{\mathit{translate}}$ is the client cost for translating a hash
using the offchain protocol.

  * •

variable $sc_{\mathit{translate}}$ is the server cost for translating a hash
using the offchain protocol.

  * •

variable $sr_{\mathit{translate}}$ is the server reward for translating a hash
using the offchain protocol.

  * •

variable $cc_{\mathit{x}}$ is the client cost for playing challenge of type
$x$.

  * •

variable $cr_{\mathit{x}}$ is the client reward for winning the challenge of
type $x$.

  * •

variable $sc_{\mathit{x}}$ is the staker cost for playing the challenge of
type $x$.

Where $x$ can be $\mathit{data}$, $\mathit{signature}$, $\mathit{validity}$ or
$\mathit{integrity}$.

Stakers do not receive any reward for winning challenges, as their motivation
for playing is to not lose their stake and eventually collect their reward
from consolidated blocks. However, they do receive a reward for translating a
hash using the offchain protocol as there is no stake at risk.

The following relations must hold:

  * •

The cost for clients to play any challenge $x$ is significantly less than the
reward for winning it, $cc_{\mathit{x}}\ll cr_{\mathit{x}}$. The cost for
servers to translate hashes using the offchain protocol is significantly less
than its reward $sc_{\mathit{translate}}\ll sr_{\mathit{x}}$. This motivates
rational agents to participate to gain a profit with a large margin.

  * •

For any challenge $x$, clients cover the costs of the challenged staker,
$cc_{\mathit{x}}>sc_{\mathit{x}}$. In particular, no staker plays the
signature challenge, therefore $sc_{\mathit{signature}}=0$.

  * •

For the data, validity and integrity challenges, the client reward for winning
the challenge is less than the challenged agent stake, $cr_{\mathit{x}}<s$.
For the signature challenge, the client reward is bounded by the sum of all
stakes in the batch, $cr_{\mathit{signature}}<\sum s$. For the offchain
translation protocol, clients cover the costs of servers reward,
$cc_{\mathit{translate}}>sr_{\mathit{translate}}$ This ensures rewards can be
covered by the stake taken from the losing player.

  * •

The client cost for using the offchain translation protocol is significant
less than playing the data challenge, $cc_{\mathit{translate}}\ll
cc_{\mathit{data}}$. This motivates clients to use the offchain protocol when
translating hashes.

We now determine the minimum budget a single honest agent needs to guarantee
that an illegal batch tag does not get confirmed. cost An agent A with
$max(cc_{\mathit{signature}},cc_{\mathit{data}}+max(cc_{\mathit{validity}},cc_{\mathit{integrity}}))$
tokens knowing the transactions in all confirmed batches can discard illegal
signed batch tags.

Finally, rational agents are likely to use the offchain protocol to translate
hashes, because this protocol is cheaper for clients and more rewarding for
servers than data challenging.

######  Proposition 5.4.

Let A be a rational agent seeking to translate a hash $h$, and S be a rational
arranger process that knows the batch hashing to $h$. The translation of $h$
will occur through the offchain protocol.

The proof of all the propositions can be found in Appendix E.

##  6 Threat Models

In this section, we describe two different adversaries controlling more than
$f$ arranger servers, violating the correctness assumptions in Section 4, and
study the impact on our L2 blockchain.

##### Adversary #1: Limited Power.

Lets consider an adversary controlling between $f+1$ and $N-f-1$ arranger
processes without compromising the Setchain. In other words, there are at
least $f+1$ correct arranger processes which agree on the Setchain epochs.

If adversary arranger processes post illegal batch tags in L1, an honest agent
can detect these tags and prevent their consolidation (see Corollary 5.1). If
they post a legal batch tag not following the batch reached by Setchain
consensus, a correct arranger process can post an incompatible legal batch tag
with the same identifier violating the Property Unique Batch. This collective
arranger behavior is incorrect and detected upon inspection of the L1
blockchain, i.e. two incompatible signed batch tags are posted to L1. In this
case, we need a mechanism to replace arranger processes, but it is out of the
scope of this paper.

##### Adversary #2: Fully Powerful.

We consider now a more powerful adversary controlling between $f+1$ and $N$
arranger proccesses including compromising the Setchain. In this case, even if
there are correct arranger processes, they may not agree on Setchain epochs.

Even if the adversary controls all processes, an honest agent can prevent the
execution of invalid transactions or the execution of a transaction twice
(corollary 5.1).

However, the adversary decides which transactions appear in legal batch tags
and detecting that the arranger is controlled by an adversary is impossible.
This gives the adversary the power to censor transactions, but to provide
censorship resistance, users can post their transactions directly in L1
although at a higher cost.

##  7 Empirical Evaluation

We provide now an empirical evaluation to asses whether the decentralized
arranger from Section 4 can scale to handle the current demand of L2.

Setchain has been reported to be three orders of magnitude faster than
consensus [capretto22setchain]. While Ethereum offers a throughput of
approximately $12$ Transactions Per Second (TPS), Setchain can handle $12,000$
TPS. In comparison, the cumulative throughput of all Ethereum L2 systems
amounts to $100$ TPS.888Data obtained on May 2024 from l2beat
https://l2beat.com/scaling/activity. Although Ethereum is operating close to
its maximum capacity, the L2 throughput mentioned above represents their
_current demand_.999The available documentation of the L2 systems does not
present theoretical or empirical limitations. Our approach extends Setchain,
and thus, we focus on assessing the efficiency of each new component forming
the decentralized arranger. We aim to evaluate empirically that these
components impose a negligible computational overhead on top of the intrinsic
set-consensus algorithm employed in Setchains. The empirical evaluation
reported in [capretto22setchain] does not involve compressing, hashing or
signing setchain epochs, nor verification or aggregation of signatures.

###  7.1 Hypothesis and Experiments

All experiments were carried out on a Linux machine with $256$ GB of RAM and
$72$ virtual 3GHz-cores (Xeon Gold 6154) running Ubuntu 20.04. We employed
$40,000$ existing transactions from Arbitrum One history as our data set.

Our hypothesis is that setchain performance is not affected by:

  * •

(H.Hash) hashing batches of transactions,

  * •

(H.Compress) compressing batches of transactions,

  * •

(H.Sign) signing hashes of batches,

  * •

(H.Agg) aggregating signatures,

  * •

(H.Ver) verifying signatures,

  * •

(H.Trans) translating hashes into batches.

Additionally, signed batch tags size is significantly smaller than their
corresponding compressed batch (hypothesis H.Size).

##### Hypothesis H.Size.

We measured the size of both compressed batches and batch tags ranging from
$400$ to $4,400$ transactions per batch.101010As of August 2023, Arbitrum
Nitro batches typically contain around $800$ transactions, while in Arbitrum
AnyTrust, batches contain approximately $4,000$ transactions. For each batch
size, we shuffled transactions from our data set, split them into 10 batches
of equal size, and assigned them unique identifiers. We compressed each batch
using the Brotli compression algorithm [Alakuijala18brotli], currently used in
Arbitrum Nitro [ArbitrumNitro]. Additionally, for each batch, we computed its
Merkle Tree [Merkle88] with their transactions as leaves. To create batch
tags, we signed each batch Merkle Tree root along with an identifier using a
BLS Signature scheme [Boneh2001Short] implemented in [ArbitrumNitroGithub].
Our experiments show there is a ratio of _more than two orders_ of magnitude
between compressed batches and batch tags with the same number of
transactions. Fig. 3(a) shows the average size of compressed batches of 400
transactions is approximately 80,000 Bytes, whereas the average size for 4,400
transactions is around 780,000 Bytes. In contrast, the average size of signed
batch tags remained around $480$ Bytes independently of the number of
transactions within the batch. Hypothesis H.Size holds, hashes are
significantly smaller than compressed batches.

|
---|---
(a) | (b)
Fig. 3: (a) Average size of compressed batches and batch tags for varying
numbers of transactions per batch. (b) Signature aggregations per second, in
terms of the number of signature aggregated per procedure.

For the rest of the experiments, we loaded all the required information into
local memory and applied each procedure for a duration of $1$ second, cycling
over the input as much as necessary. We ran each experiment $10$ times and
report the average performance. Fig. 4(a), Fig. 3(b) and Fig. 4(b) summarize
the results.

##### Hypotheses H.Hash and H.Compress.

To test compressing and hashing procedures, we use the full data set of
$40,000$ transactions. We employed Brotli [Alakuijala18brotli] as compression
algorithm and the root of Merkle trees of batches as hash function. We again
ranged from $400$ to $4,400$ transactions per batch.

Fig. 4 shows hashing can scale from $260,000$ to $275,000$ TPS, depending on
the batch size, while the compression procedure achieves a throughput ranging
from $75,000$ TPS for batches of $400$ transactions to $50,000$ TPS for
batches of $4,400$ transactions. Both hashing and compression procedures
significantly outperform the Setchain throughput of $12,000$ TPS, and thus,
these procedures do not impact the overall throughput. Therefore, hypotheses
H.Hash and hypothesis H.Compress hold.

##### Hypothesis H.Sign.

To evaluate the signing procedure performance, we used a file containing $50$
pairs batch hash-identifier. We assess the performance of signing each pair
using the provided secret key with the BLS signature scheme implemented in
[ArbitrumNitroGithub].

Our results show our system can sign approximately $2300$ hash-identifier
pairs per second. Considering a throughput of $12,000$ TPS and batches of at
least $400$ transactions, no more than $30$ batches per second will be
generated. Thus, each arranger process can sign more than $75$ times the
number of batches required, empirically supporting hypothesis H.Sign.

|
---|---
(a) | (b)
Fig. 4: (a) Throughput of compressing, hashing and translating procedures for
varying number of transactions per batch. (b) Signature verification per
second. The dotted line represents the maximal number of signatures that each
arranger process must verify (for $12,000$ TPS, the batch size of $4\,400$ and
$128$ process). The dashed line represents the maximal number of signatures
that each arranger must verify (for 12,000 TPS, the batch size of $400$ and
$256$ process).

##### Hypothesis H.Agg.

The performance of the signature aggregation procedure depends on the number
of signatures aggregated is limited by the number $N$ of arranger servers. We
studied the performance of signature aggregation ranging from $8$ to $256$
servers111111As reference, currently, the DAC of Arbitrum AnyTrust comprises
$7$ members https://docs.arbitrum.foundation/state-of-progressive-
decentralization#data-availability-committee-members.. Our data set consists
of a directory with $N$ files. Each file contains $50$ signed hash-identifier
pairs signed by the same signer. The list of pairs hash-identifier is the same
across all files. We measured the performance of aggregating $N$ signatures of
the same hash-identifier pair using BLS [ArbitrumNitroGithub].

Fig. 3(b) shows an aggregation ratio ranging from $5,000$ procedures per
second, when aggregating $256$ signatures in each invocation, to $115,000$ per
second when aggregating $8$ signatures. Assuming at most $30$ batches per
second are generated, the aggregation procedure can easily handle its
workload, even for $N=256$ arranger processes, empirically validating
hypothesis H.Agg.

##### Hypothesis H.Ver.

To assess the performance of the signature verification procedure, we used a
file containing $50$ batch tags and the public key of the signer of all
hashes. We analyzed the performance of verifying that each signature was
generated by signing the corresponding hash-identifier pair using the
corresponding private keys. We employed again BLS [ArbitrumNitroGithub]. Fig.
4(b) shows that signature verification can be performed at a rate of
approximately $600$ signatures per second. This rate is sufficient to verify
all signatures generated by $N=128$ processes, considering a throughput of
$12,000$ TPS and batches containing $4,400$ transactions (dotted line in Fig.
4(b)). Servers must verify the highest number of signatures when the arranger
is maintained by $256$ processes and batches contain only $400$ transactions,
which amounts to verifying $7,680$ signatures per second, surpassing the
throughput of the signature verification procedure (dashed line in Fig. 4(b)).
However, verifying signatures can be done in parallel as the task is
completely independent for each signature.121212All other local procedures
described can use parallelism easily as well.

Our empirical evaluation suggests that using $16$ parallel processes to verify
signatures achieves a rate exceeding $8,500$ signature verified per second,
sufficiently for $N=256$ processes and batches containing $400$ transactions
at $12,000$ TPS. Consequently, the verifying procedure does not influence the
throughput, and hypothesis H.Ver holds.

##### Hypothesis H.Trans.

Finally, we implemented a _translation server_ that takes two input files and
generates a dictionary mapping hashes to their compressed data. One file
contains hashed batches together with identifiers while the other contains
compressed batches with identifiers. The translation server opens a local TCP
connection port to receive hash translation requests receiving an identifier
and returning a compressed batch according to the dictionary.

Our experiments involve making sequential requests to a single translation
server asking to translate input hashes for a duration of $1$ second. All
batches contained the same number of transactions, ranging from $400$ to
$4,400$ transactions.

Fig. 4(a) shows that the translation for batches of $400$ transactions can be
performed at a rate of about $1,300,000$ TPS. The translation throughput
increases as the number of transactions per batch increases, peaking at nearly
$2,900,000$ TPS for batches of $3,800$ transactions. However, the throughput
decreases slightly after that point, due to the increased size of compressed
batches. The translation procedure can easily handle two orders of magnitude
more transactions than the throughput of setchain, confirming hypothesis
H.Trans.

###  7.2 Experiment Conclusions

The results of our experiments are: (1) hashing and signing batches of
transactions take significantly less space than compressing batches of
transactions and (2) local procedures are very efficient and do not affect
Setchain throughput. The reduction in space, which remains constant as batch
size increases, contributes to L1 lower gas consumption. Since the overhead of
our procedures is negligible, our decentralized arranger does not introduce
any significant performance bottlenecks to Setchain, even if the workload of
L2 systems was increased by two orders of magnitude and there were 256
arranger servers.

##  8 Related Work

While the limitations of centralized sequencers in rollups are well known, the
development of decentralized sequencers is still in its early stages
[motepalli2023sok]. To the best of our knowledge, Metis [metisDecentralized]
is the only rollup that currently implements a decentralized arranger. Metis
uses Proof-of-Stake and Tendermint [buchman2016tendermint] to select a
rotating leader. The leader collects user transactions and generates batches.
Batches are signed using multi-party computation and, when enough signatures
are gathered, the leader posts a signed batch in L1. However, Metis
[metisDecentralized] does not provide a formal proof of correctness or
mechanisms to check or dispute leader (mis)behaviour.

Other attempts to implement arrangers include Radius [Radius], Espresso
[espressoSequencer] and Astria [Astria]. Radius also uses leader election,
based on the RAFT algorithm [ongaro2014raft]. Radius servers remain consistent
and can reach consensus even when the leader fails, but [Radius] does not
discuss what happens when servers refuse to disclose block contents to users.
Radius allows encryption of transactions to prevent MEV, but we do not address
this problem here. Both Espresso and Astria use one protocol for sequencing
transactions and a different protocol for data availability. In particular,
Espresso uses HotStuff2 [hotstuff] as consensus mechanism and its own Data
Availability layer known as _tiramisu_ , while Astria uses CometBFT [cometBFT]
for sequencing transactions and leverages Celestia Data Availability Service
[celestia]. We decided to tackle both challenges within a single protocol as
Byzantine-resilient solutions do not compose well (see e.g.
[capretto22setchain]) both in terms of correctness and efficiency.

Even though Metis, Expresso and Astria use staking to discourage misconduct
among participants, none of these systems provide any rewards for correct
behavior. Furthermore, to the best of our knowledge, our work is the first to
provide fraud-proof mechanisms usable on L1 to demonstrate the illegality of
batch tags posted by arranger servers. We also provide an onchain challenge
mechanism that can be used to translate hashes, which has been studied in
[boneh]. The main difference with [boneh] is that they assume that the
translation can be directly verified in an L1 smart contract using SNARK
proofs, while we provide an interactive game played over the Merkle tree
nodes.

An extended list of related work can be found in Appendix LABEL:app:ext-
related-work131313The list of references below include works cited in the main
body of the paper, and _additionally_ works cited in the extended related work
in Appendix LABEL:app:ext-related-work and LABEL:app:decentralizationL2Eth..

##  9 Conclusion

Rollups aim to improve the scalability of current smart-contract blockchains,
offering a much higher throughput without modifying the programming logic and
interaction of blockchains. The main element of rollups is an arranger formed
by a sequencer of transactions and a data committee translating hashes into
batches. Current implementations of arrangers in most rollups are based on
centralized sequencers, either posting compressed batches (ZK-Rollups and
Optimistic Rollups), or hashes of transactions with a fixed collection of
servers providing data translation (Validums and Optimiums). The resulting
systems are fully controlled by a centralized sequencer server that has full
power for transaction reordering and can post fake blocks without penalties.

In this paper, we formalized the correctness criteria for arranger services
and presented a fully decentralized arranger based on the efficient Setchain
distributed Byzantine tolerant data-type. We proved our solution correct and
reported an empirical evaluation of its building blocks showing that our
solution can scale far beyond the current demand of existing rollups.

We also described a collection of incentives for servers to behave correctly
when creating, signing and translating batches, and penalties for posting
incorrect information based on fraud-proof mechanisms. Using these mechanisms
a single honest agent can guarantee that only valid batches of transactions
are executed in L2, regardless of the number of Byzantine servers in the
arranger.

## References

  * [1] A Consensys Formation.  Linea.  https://linea.build/, Accessed: 2024-05-21.
  * [2] Aevo.  https://www.aevo.xyz/, Accessed: 2024-05-21.
  * [3] Mustafa Al-Bassam, Alberto Sonnino, and Vitalik Buterin.  Fraud and data availability proofs: Maximising light client security and scaling blockchains with dishonest majorities, 2019.  arXiv:1809.09044.
  * [4] Jyrki Alakuijala, Andrea Farruggia, Paolo Ferragina, Eugene Kliuchnikov, Robert Obryk, Zoltan Szabadka, and Lode Vandevenne.  Brotli: A general-purpose data compressor.  ACM Transactions on Information Systems, 37(1):1–30, 2018.
  * [5] Maher Alharby, Roben Castagna Lunardi, Amjad Aldweesh, and Aad Van Moorsel.  Data-driven model-based analysis of the ethereum verifier’s dilemma.  In 2020 50th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pages 209–220. IEEE, 2020.
  * [6] Ancient8 Foundation.  Ancient8.  https://ancient8.gg/, Accessed: 2024-05-22.
  * [7] ApeX.  https://apex-pro.gitbook.io/apex-pro?lang=en-US, Accessed: 2024-05-21.
  * [8] Astar Network.  Astar zkEVM.  https://astar.network/astar2, Accessed: 2024-05-21.
  * [9] Iddo Bentov, Ranjit Kumaresan, and Andrew Miller.  Instantaneous decentralized poker.  In Advances in Cryptology–ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part II 23, pages 410–440. Springer, 2017.
  * [10] Blast.  https://blast.io/en, Accessed: 2024-05-21.
  * [11] BOB.  https://www.gobob.xyz/, Accessed: 2024-05-21.
  * [12] Boba Network.  https://boba.network/, Accessed: 2024-05-21.
  * [13] Dan Boneh, Ben Lynn, and Hovav Shacham.  Short signatures from the weil pairing.  Journal of Cryptology, 17:297–319, 2001.
  * [14] L. Bousfield, R. Bousfield, C. Buckland, B. Burgess, J. Colvin, E. Felten, S. Goldfeder, D. Goldman, B. Huddleston, H. Kalonder, F. Lacs, H. Ng, A. Sanghi, T. Wilson, V. Yermakova, and T. Zidenberg.  Arbitrum nitro: A second-generation optimistic rollup, 2022.  https://github.com/OffchainLabs/nitro/blob/master/docs/Nitro-whitepaper.pdf.
  * [15] Marcus Brandenburger, Christian Cachin, Rüdiger Kapitza, and Alessandro Sorniotti.  Blockchain and trusted computing: Problems, pitfalls, and a solution for hyperledger fabric.  arXiv preprint arXiv:1805.08541, 2018.
  * [16] Ethan Buchman.  Tendermint: Byzantine fault tolerance in the age of blockchains.  Master’s thesis, The University of Guelph, 2016.
  * [17] Zhongteng Cai, Junyuan Liang, Wuhui Chen, Zicong Hong, Hong-Ning Dai, Jianting Zhang, and Zibin Zheng.  Benzene: Scaling blockchain with cooperation-based sharding.  IEEE Transactions on Parallel and Distributed Systems, 34(2):639–654, 2022.
  * [18] Matteo Campanelli, Rosario Gennaro, Steven Goldfeder, and Luca Nizzardo.  Zero-knowledge contingent payments revisited: Attacks and payments for services.  In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS ’17, page 229–243, New York, NY, USA, 2017. Association for Computing Machinery.  doi:10.1145/3133956.3134060.
  * [19] Ran Canetti, Ben Riva, and Guy N Rothblum.  Practical delegation of computation using multiple servers.  In Proceedings of the 18th ACM conference on Computer and communications security, pages 445–454, 2011.
  * [20] Ran Canetti, Ben Riva, and Guy N Rothblum.  Refereed delegation of computation.  Information and Computation, 226:16–36, 2013.
  * [21] Margarita Capretto, Martín Ceresa, Antonio Fernández Anta, Antonio Russo, and César Sánchez.  Setchain: Improving Blockchain scalability with Byzantine distributed sets and barriers.  In Proc. of the 2022 IEEE International Conference on Blockchain, pages 87–96. IEEE, 2022.  doi:10.1109/Blockchain55522.2022.00022.
  * [22] Raymond Cheng, Fan Zhang, Jernej Kos, Warren He, Nicholas Hynes, Noah Johnson, Ari Juels, Andrew Miller, and Dawn Song.  Ekiden: A platform for confidentiality-preserving, trustworthy, and performant smart contracts.  In 2019 IEEE European Symposium on Security and Privacy (EuroS&P), pages 185–200. IEEE, 2019.
  * [23] Coinbase.  base.  https://base.org/, Accessed: 2024-05-21.
  * [24] Jeff Coleman.  State channels, 2015.  https://www.jeffcoleman.ca/state-channels/.
  * [25] CometBFT.  What is CometBFT.  https://docs.cometbft.com/v0.37/introduction/, Accessed: 2024-05-21.
  * [26] Tyler Crain, Christopher Natoli, and Vincent Gramoli.  Red belly: A secure, fair and scalable open blockchain.  In Proc. of S&P’21, pages 466–483, 2021.  doi:10.1109/SP40001.2021.00087.
  * [27] F. Cristian, H. Aghili, R. Strong, and D. Volev.  Atomic broadcast: from simple message diffusion to byzantine agreement.  In 25th Int’l Symp. on Fault-Tolerant Computing, pages 431–, 1995\.  doi:10.1109/FTCSH.1995.532668.
  * [28] Kyle Croman, Christian Decker, Ittay Eyal, Adem Efe Gencer, Ari Juels, Ahmed Kosba, Andrew Miller, Prateek Saxena, Elaine Shi, Emin Gün Sirer, et al.  On scaling decentralized blockchains: (a position paper).  In International conference on financial cryptography and data security, pages 106–125. Springer, 2016.
  * [29] Cyber.  https://cyber.co/, Accessed: 2024-05-22.
  * [30] Hung Dang, Tien Tuan Anh Dinh, Dumitrel Loghin, Ee-Chien Chang, Qian Lin, and Beng Chin Ooi.  Towards scaling blockchain systems via sharding.  In Proc. of SIGMOD’19, pages 123––140. ACM, 2019.  doi:10.1145/3299869.3319889.
  * [31] Poulami Das, Lisa Eckey, Tommaso Frassetto, David Gens, Kristina Hostáková, Patrick Jauernig, Sebastian Faust, and Ahmad-Reza Sadeghi.  Fastkitten: Practical smart contracts on bitcoin.  In 28th USENIX Security Symposium (USENIX Security 19), pages 801–818, 2019.
  * [32] Sourav Das, Vinith Krishnan, and Ling Ren.  Efficient cross-shard transaction execution in sharded blockchains.  arXiv preprint arXiv:2007.14521, 2020.
  * [33] Sourav Das, Vinay Joseph Ribeiro, and Abhijeet Anand.  Yoda: Enabling computationally intensive contracts on blockchains with byzantine and selfish nodes.  arXiv preprint arXiv:1811.03265, 2018.
  * [34] DeGate Home DAO.  DeGate V1.  https://degate.com/, Accessed: 2024-05-21.
  * [35] Metis Developer Documentation.  Decentralized sequencer.  https://docs.metis.io/dev/decentralized-sequencer/overview, Accessed: 2024-05-21.
  * [36] Cynthia Dwork and Moni Naor.  Pricing via processing or combatting junk mail.  In Annual international cryptology conference, pages 139–147. Springer, 1992.
  * [37] dYdX.  https://dydx.exchange/, Accessed: 2024-05-21.
  * [38] Stefan Dziembowski, Lisa Eckey, Sebastian Faust, and Daniel Malinowski.  Perun: Virtual payment channels over cryptographic currencies.  IACR Cryptol. ePrint Arch., 2017:635, 2017.  URL: https://api.semanticscholar.org/CorpusID:26535415.
  * [39] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson.  Impossibility of distributed consensus with one faulty process.  JACM, 32(2):374–382, 1985.  doi:10.1145/3149.214121.
  * [40] Tommaso Frassetto, Patrick Jauernig, David Koisser, David Kretzler, Benjamin Schlosser, Sebastian Faust, and Ahmad-Reza Sadeghi.  Pose: Practical off-chain smart contract execution.  arXiv preprint arXiv:2210.07110, 2022.
  * [41] Fraxtal.  Frax Finance.  https://www.frax.com/, Accessed: 2024-05-21.
  * [42] Fuel Labs.  Fuel V1.  https://fuel.network/, Accessed: 2024-05-22.
  * [43] Shafi Goldwasser, Yael Tauman Kalai, and Guy N Rothblum.  Delegating computation: interactive proofs for muggles.  Journal of the ACM (JACM), 62(4):1–64, 2015.
  * [44] Lewis Gudgeon, Pedro Moreno-Sanchez, Stefanie Roos, Patrick McCorry, and Arthur Gervais.  Sok: Layer-two blockchain protocols.  In Financial Cryptography and Data Security: 24th International Conference, FC 2020, Kota Kinabalu, Malaysia, February 10–14, 2020 Revised Selected Papers 24, pages 201–226. Springer, 2020.
  * [45] Abdelatif Hafid, Abdelhakim Senhaji Hafid, and Mustapha Samih.  Scaling blockchains: A comprehensive survey.  IEEE access, 8:125244–125262, 2020.
  * [46] Tharaka Hewa, Mika Ylianttila, and Madhusanka Liyanage.  Survey on blockchain based smart contracts: Applications, opportunities and challenges.  Journal of network and computer applications, 177:102857, 2021.
  * [47] Hypr Network.  Hypr.  https://www.hypr.network/, Accessed: 2024-05-22.
  * [48] Immutable X.  https://www.immutable.com/, Accessed: 2024-05-21.
  * [49] Markus Jakobsson and Ari Juels.  Proofs of work and bread pudding protocols.  In Secure Information Networks: Communications and Multimedia Security IFIP TC6/TC11 Joint Working Conference on Communications and Multimedia Security (CMS’99) September 20–21, 1999, Leuven, Belgium, pages 258–272. Springer, 1999.
  * [50] Linpeng Jia, Keyuan Wang, Xin Wang, Lei Yu, Zhongcheng Li, and Yi Sun.  Themis: An equal, unpredictable, and scalable consensus for consortium blockchain.  In 2022 IEEE 42nd International Conference on Distributed Computing Systems (ICDCS), pages 235–245. IEEE, 2022.
  * [51] Harry Kalodner, Steven Goldfeder, Xiaoqi Chen, S. Matthew Weinberg, and Edward W. Felten.  Arbitrum: Scalable, private smart contracts.  In 27th USENIX Security Symposium, pages 1353–1370. USENIX Assoc., 2018.  URL: https://www.usenix.org/conference/usenixsecurity18/presentation/kalodner.
  * [52] Karak.  https://karak.network/, Accessed: 2024-05-21.
  * [53] Mahimna Kelkar, Fan Zhang, Steven Goldfeder, and Ari Juels.  Order-fairness for byzantine consensus.  Cryptology ePrint Archive, Paper 2020/269, 2020.  https://eprint.iacr.org/2020/269.  URL: https://eprint.iacr.org/2020/269.
  * [54] Kinto.  https://www.kinto.xyz/, Accessed: 2024-05-21.
  * [55] Eleftherios Kokoris-Kogias, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, Ewa Syta, and Bryan Ford.  Omniledger: A secure, scale-out, decentralized ledger via sharding.  In 2018 IEEE symposium on security and privacy (SP), pages 583–598. IEEE, 2018.
  * [56] Jae Kwon and Ethan Buchman.  Cosmos whitepaper, 2019.  https://cosmos.network/resources/whitepaper.
  * [57] Celestia Labs.  Celestia.  https://celestia.org, Accessed: 2024-05-21.
  * [58] Offchain Labs.  Arbitrum nitro, 2022.  https://github.com/OffchainLabs/nitro.
  * [59] Lattice.  Redstone.  https://redstone.xyz/, Accessed: 2024-05-22.
  * [60] Lightscale Holdings.  Kroma.  https://kroma.network/, Accessed: 2024-05-21.
  * [61] Joshua Lind, Ittay Eyal, Florian Kelbert, Oded Naor, Peter R. Pietzuch, and Emin Gün Sirer.  Teechain: Scalable blockchain payments using trusted execution environments.  CoRR, abs/1707.05454, 2017.  URL: http://arxiv.org/abs/1707.05454, arXiv:1707.05454.
  * [62] Jian Liu, Peilun Li, Raymond Cheng, N Asokan, and Dawn Song.  Parallel and asynchronous smart contract execution.  IEEE Transactions on Parallel and Distributed Systems, 33(5):1097–1108, 2021.
  * [63] Pinglan Liu and Wensheng Zhang.  Game theoretic approach for secure and efficient heavy-duty smart contracts.  In 2020 IEEE Conference on Communications and Network Security (CNS), pages 1–9. IEEE, 2020.
  * [64] Loopring Project Ltd.  Loopring.  https://loopring.org, Accessed: 2024-05-21.
  * [65] James Lovejoy, Anders Brownworth, Madars Virza, and Neha Narula.  Parsec: Executing smart contracts in parallel.  https://www.media.mit.edu/projects/parsec/overview/.
  * [66] Lyra Mobile.  Lyra.  https://lyra.finance/, Accessed: 2024-05-21.
  * [67] Zamani Mahdi, Mahnush Movahedi, and Mariana Raykova.  Rapidchain: Scaling blockchain via full sharding.  In Proc. of CSS’18, pages 931––948. ACM, 2018.  doi:10.1145/3243734.3243853.
  * [68] Dahlia Malkhi and Kartik Nayak.  Extended abstract: Hotstuff-2: Optimal two-phase responsive bft.  Cryptology ePrint Archive, Paper 2023/397, 2023.  https://eprint.iacr.org/2023/397.  URL: https://eprint.iacr.org/2023/397.
  * [69] Mahdi Mallaki, Babak Majidi, Amirhossein Peyvandi, and Ali Movaghar.  Off-chain management and state-tracking of smart programs on blockchain for secure and efficient decentralized computation.  International Journal of Computers and Applications, 44(9):822–829, 2022.
  * [70] Mantle.  https://www.mantle.xyz/, Accessed: 2024-05-21.
  * [71] Matter Labs.  zkSync.  https://zksync.io/, Accessed: 2024-05-21.
  * [72] Matter Labs.  zkSync Lite.  https://zksync.io/, Accessed: 2024-05-21.
  * [73] Ralph C. Merkle.  A digital signature based on a conventional encryption function.  In Carl Pomerance, editor, Advances in Cryptology — CRYPTO ’87, pages 369–378, Berlin, Heidelberg, 1988. Springer Berlin Heidelberg.
  * [74] Metallicus.  Metal L2.  https://metall2.com/, Accessed: 2024-05-22.
  * [75] Metis.  Metis Andromeda.  https://www.metis.io/, Accessed: 2024-05-21.
  * [76] Andrew Miller, Iddo Bentov, Ranjit Kumaresan, and Patrick McCorry.  Sprites: Payment channels that go faster than lightning.  CoRR, abs/1702.05812, 2017.  URL: http://arxiv.org/abs/1702.05812, arXiv:1702.05812.
  * [77] Mode Network.  https://www.mode.network/, Accessed: 2024-05-21.
  * [78] Shashank Motepalli, Luciano Freitas, and Benjamin Livshits.  Sok: Decentralized sequencers for rollups, 2023.  arXiv:2310.03616.
  * [79] Myria.  https://myria.com/, Accessed: 2024-05-22.
  * [80] Eshita Nandini.  Introducing the astria development cluster.  https://www.astria.org/blog/introducing-the-astria-development-cluster, Accessed: 2024-05-21.
  * [81] Muhammad Hassan Nasir, Junaid Arshad, Muhammad Mubashir Khan, Mahawish Fatima, Khaled Salah, and Raja Jayaraman.  Scalable blockchains—a systematic review.  Future generation computer systems, 126:136–162, 2022.
  * [82] Diego Nehab and Augusto Teixeira.  Permissionless refereed tournaments, 2022.  arXiv:2212.12439.
  * [83] Ky Nguyen, Miguel Ambrona, and Masayuki Abe.  Wi is almost enough: Contingent payment all over again.  In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, CCS ’20, page 641–656, New York, NY, USA, 2020. Association for Computing Machinery.  doi:10.1145/3372297.3417888.
  * [84] Jonas Nick, Andrew Poelstra, and Gregory Sanders.  Liquid: A bitcoin sidechain.  Liquid white paper. URL https://blockstream. com/assets/downloads/pdf/liquid-whitepaper. pdf, 2020.
  * [85] OKX.  X Layer.  https://www.okx.com/xlayer, Accessed: 2024-05-21.
  * [86] Diego Ongaro and John Ousterhout.  In search of an understandable consensus algorithm.  In 2014 USENIX Annual Technical Conference (USENIX ATC 14), pages 305–319, Philadelphia, PA, June 2014. USENIX Association.  URL: https://www.usenix.org/conference/atc14/technical-sessions/presentation/ongaro.
  * [87] Optimism Foundation.  Optimism.  https://www.optimism.io/, Accessed: 2024-05-21.
  * [88] Orderly Network.  https://orderly.network/, Accessed: 2024-05-22.
  * [89] p0x Labs.  Manta Pacific.  https://pacific.manta.network/, Accessed: 2024-05-21.
  * [90] Paradex.  https://www.paradex.trade/, Accessed: 2024-05-21.
  * [91] Parallel.  https://parallel.fi/, Accessed: 2024-05-22.
  * [92] Public Goods Network.  https://publicgoods.network/, Accessed: 2024-05-22.
  * [93] Polygon Labs UI.  Polygon PoS.  https://polygon.technology/polygon-pos.
  * [94] Polygon Labs UI.  Polygon zkEVM.  https://polygon.technology/polygon-zkevm, Accessed: 2024-05-21.
  * [95] Joseph Poon and Vitalik Buterin.  Plasma: Scalable autonomous smart contracts, 2017.  https://plasma.io/.
  * [96] Joseph Poon and Thaddeus Dryja.  The bitcoin lightning network: Scalable off-chain instant payments, 2016\.  https://lightning.network/lightning-network-paper.pdf.
  * [97] Radius.  Introduction to radius.  https://docs.theradius.xyz/overview/introduction-to-radius, Accessed: 2024-05-21.
  * [98] Ranvir Rana, Sreeram Kannan, David Tse, and Pramod Viswanath.  Free2shard: Adversary-resistant distributed resource allocation for blockchains.  Proceedings of the ACM on Measurement and Analysis of Computing Systems, 6(1):1–38, 2022.
  * [99] Reddio.  https://www.reddio.com/, Accessed: 2024-05-22.
  * [100] L2BEAT research team.  L2beat.  Accessed: 2024-05-21.  URL: https://l2beat.com/scaling/summary.
  * [101] Reya.  https://reya.network/, Accessed: 2024-05-21.
  * [102] rhino.fi.  https://rhino.fi/, Accessed: 2024-05-21.
  * [103] RSS3.  https://rss3.io/, Accessed: 2024-05-21.
  * [104] Fahad Saleh.  Blockchain without waste: Proof-of-stake.  The Review of financial studies, 34(3):1156–1190, 2021.
  * [105] Abdurrashid Ibrahim Sanka and Ray CC Cheung.  A systematic review of blockchain scalability: Issues, solutions, analysis and future research.  Journal of Network and Computer Applications, 195:103232, 2021.
  * [106] Scroll Ltd.  Scroll.  https://scroll.io/, Accessed: 2024-05-21.
  * [107] Espresso Sequencer.  The espresso sequencer: Hotshot consensus and tiramisu data availability.  https://webassembly.org/, Accessed: 2024-05-21.  URL: https://github.com/EspressoSystems/HotShot/blob/main/docs/espresso-sequencer-paper.pdf.
  * [108] Tao Shen, Tianyu Li, Zhuo Yu, Fenhua Bai, and Chi Zhang.  Gt-nrsm: efficient and scalable sharding consensus mechanism for consortium blockchain.  The Journal of Supercomputing, pages 1–35, 2023.
  * [109] Daria Smuseva, Ivan Malakhov, Andrea Marin, Aad van Moorsel, and Sabina Rossi.  Verifier’s dilemma in ethereum blockchain: A quantitative analysis.  In International Conference on Quantitative Evaluation of Systems, pages 317–336. Springer, 2022.
  * [110] Sorare, SAS.  Sorare.  https://sorare.com/es/, Accessed: 2024-05-21.
  * [111] Starknet.  https://www.starknet.io/en, Accessed: 2024-05-21.
  * [112] tanX.  https://tanx.fi/, Accessed: 2024-05-22.
  * [113] Ertem Nusret Tas and Dan Boneh.  Cryptoeconomic security for data availability committees.  In Foteini Baldimtsi and Christian Cachin, editors, Financial Cryptography and Data Security, pages 310–326, Cham, 2024. Springer Nature Switzerland.
  * [114] Jason Teutsch and Christian Reitwießner.  A scalable verification solution for blockchains.  CoRR, abs/1908.04756, 2019.  URL: http://arxiv.org/abs/1908.04756, arXiv:1908.04756.
  * [115] The Cartesi Foundation.  Cartesi.  https://cartesi.io/, Accessed: 2024-05-22.
  * [116] Louis Tremblay Thibault, Tom Sarry, and Abdelhakim Senhaji Hafid.  Blockchain scaling using rollups: A comprehensive survey.  IEEE Access, 2022.
  * [117] KN Unnikrishnan and P Victer Paul.  A survey on layer 2 solutions to achieve scalability in blockchain.  In Advances in Distributed Computing and Machine Learning: Proceedings of ICADCML 2022, pages 205–216. Springer, 2022.
  * [118] Georg Fuchsbauer https://www.fuel.network/.  Wi is not enough: Zero-knowledge contingent (service) payments revisited.  Cryptology ePrint Archive, Paper 2019/964, 2019.  https://eprint.iacr.org/2019/964.  URL: https://eprint.iacr.org/2019/964, doi:10.1145/3319535.3354234.
  * [119] Eric Wagner, Achim Völker, Frederik Fuhrmann, Roman Matzutt, and Klaus Wehrle.  Dispute resolution for smart contract-based two-party protocols.  In 2019 IEEE International Conference on Blockchain and Cryptocurrency (ICBC), pages 422–430. IEEE, 2019.
  * [120] Gerui Wang, Shuo Wang, Vivek Bagaria, David Tse, and Pramod Viswanath.  Prism removes consensus bottleneck for smart contracts.  In 2020 Crypto Valley Conference on Blockchain Technology (CVCBT), pages 68–77. IEEE, 2020.
  * [121] Ke Wang and Hyong S. Kim.  Fastchain: Scaling blockchain system with informed neighbor selection.  In Proc. of IEEE Blockchain’19, pages 376–383, 2019.  doi:10.1109/Blockchain.2019.00058.
  * [122] WebAssembly Working Group.  WebAssembly.  https://webassembly.org/.
  * [123] Gavin Wood.  Ethereum: A secure decentralised generalised transaction ledger.  Ethereum project yellow paper, 151:1–32, 2014.
  * [124] Gavin Wood.  Polkadot: Vision for a heterogeneous multi-chain framework.  White Paper, 21, 2016.
  * [125] Yang Xiao, Ning Zhang, Jin Li, Wenjing Lou, and Y Thomas Hou.  Privacyguard: Enforcing private data usage control with blockchain and attested off-chain contract execution.  In Computer Security–ESORICS 2020: 25th European Symposium on Research in Computer Security, ESORICS 2020, Guildford, UK, September 14–18, 2020, Proceedings, Part II 25, pages 610–629. Springer, 2020.
  * [126] Alexei Zamyatin, Dominik Harz, Joshua Lind, Panayiotis Panayiotou, Arthur Gervais, and William Knottenbelt.  Xclaim: Trustless, interoperable, cryptocurrency-backed assets.  In 2019 IEEE Symposium on Security and Privacy (SP), pages 193–210. IEEE, 2019.
  * [127] Fan Zhang, Philip Daian, Iddo Bentov, Ian Miers, and Ari Juels.  Paralysis proofs: Secure dynamic access structures for cryptocurrency custody and more.  In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, pages 1–15, 2019.
  * [128] Qiheng Zhou, Huawei Huang, Zibin Zheng, and Jing Bian.  Solutions to scalability of blockchain: A survey.  IEEE Access, 8:16440–16455, 2020.
  * [129] Qiheng Zhou, Huawei Huang, Zibin Zheng, and Jing Bian.  Overview to blockchain scalability challenges and solutions.  In Blockchain Scalability, pages 51–80. Springer, 2023.
  * [130] ZKFair Team.  ZKFair.  https://zkfair.io/, Accessed: 2024-05-21.
  * [131] ZKSpace Team.  ZKSpace.  https://en.wiki.zks.org/, Accessed: 2024-05-22.
  * [132] Zora Labs.  Zora.  https://docs.zora.co/docs/zora-network/intro, Accessed: 2024-05-21.

##  Appendix A Semi-decentralized Arranger

In this section, we describe a _semi-decentralized_ distributed implementation
of arrangers consisting of a single process sequencer and a decentralized DAC
(see Fig. 5). The centralized sequencer implements add> locally, create
batches and their hash, inform DAC servers and collect their signatures. DAC
servers implement translate> mapping the hash into its batch.

Fig. 5: Centralized Sequencer + decentralized DAC.

###  A.1 Implementation

We provide the pseudo-code implementing sequencers and DAC members in Alg. 2
and Alg. 3, respectively. The logger contract is invoked only by the sequencer
to store batch tags. For simplicity, the sequencer uses a multicast service,
to send messages to all DAC servers (which can be implemented with unicast
channels). DAC servers answer directly to the sequencer.

Alg. 2 shows the sequencer pseudo-code. This algorithm maintains a set allTxs>
to store all valid added transactions, a sequence of transactions pendingTxs>
for transactions added but not posted, and a natural number batchId> as the
identifier of the next batch. Function add> adds new valid transactions into
pendingTxs> and allTxs>. When there are enough transactions in pendingTxs> or
a timeout is reached, a timetopost> event is triggered (line 7) and Alg. 2
generates a new batch with all transactions in pendingTxs> (line 8). Then, the
sequencer sends the batch with its identifier and hash to all DAC servers
(line 10) and waits to receive $f+1$ signatures. Then, Alg. 2 aggregates all
signatures received, generates a batch tag and posts it (line 12). Finally,
Alg. 2 increments batchId> and cleans pendingTxs> (lines 13 and 14).

Algorithm 2 Sequencer.

1:init: $\<allTxs>\leftarrow\emptyset$, $\<pendingTxs>\leftarrow\epsilon$,
$\<batchId>\leftarrow 0$

2:function add>($t$)

3: assert> $\<valid>(t)$ and $t\notin\<allTxs>$

4: $\<pendingTxs>\leftarrow\langle\<pendingTxs>,t\rangle$

5: $\<allTxs>\leftarrow\<allTxs>\cup\\{t\\}$

6: return

7:upon (timetopost>) do

8: $b\leftarrow\<pendingTxs>$

9: $h\leftarrow\mathcal{H}(b)$

10: DC.Multicast$(\<signReq>(b,\<batchId>,h))$

11: $\<wait>$ for $f+1$: $\<signResp>(\<batchId>,h,i,sig_{i}(\<batchId>,h))$

12:
logger>.post>$(\<batchId>,h,\<BLSAggregate>(\bigcup_{i}sig_{i}(\<batchId>,h)))$

13: $\<batchId>\leftarrow\<batchId>+1$

14: $\<pendingTxs>\leftarrow\epsilon$

Algorithm 3 Correct DAC server $i$.

1:init: $\<hashes>\leftarrow\emptyset$

2:function translate>($\textit{id},h$)

3: if $(\<id>,\\_)\notin\<hashes>$ then return> invalidId>

4: else

5: if $(\<id>,h)\notin\<hashes>$ then return> invalidHash>

6: else return> $\<hashes>(\<id>,h)$

7:receive ($\<signReq>(b,\<id>,h)$ from Sequencer) do

8: assert> $h==\mathcal{H}(b)$ and $(\<id>,\\_)\notin\<hashes>$

9: $\<hashes>\leftarrow\<hashes>\cup\\{((\<id>,h),b)\\}$

10: send $\<signResp>(\<id>,h,i,sig_{i}(\<id>,h))$ to Sequencer

Alg. 3 shows the pseudo-code of DAC servers, which maintain a map hashes>
mapping pairs of identifiers and hashes $(\<batchId>,h)$ into batches $b$,
such that $\mathcal{H}(b)=h$. When the sequencer sends requests to sign a
batch tag $(b,\<batchId>,h)$, correct DAC servers check that $h$ corresponds
to $b$ (line 8), add the new triplet to hashes>, sign it and send the
signature back. When clients invoke $\<translate>(\<batchId>,h)$, a correct
DAC server returns the value stored in $\<hashes>(\<batchId>,h)$.

Clients solve inverse hash resolution by contacting DAC servers and checking
that the batch obtained corresponds to hash $h$, guaranteed to be provided by
a legal server.

###  A.2 Proof of Correctness

We show now that Alg. 2 and Alg. 3 form a correct arranger. We use S> for the
single sequential server running Alg. 2 and DAC> to a distributed set of
servers implementing Alg. 3. We assume at most $f<\frac{n}{2}$ DAC> servers
are Byzantine to provide Termination.

The arranger satisfies Validity and Integrity, because the sequencer S> is the
only process that posts batch tags and we assume it to be correct.

######  Lemma A.1.

Sequencer S> generates legal batch tags of valid transactions added by
clients. S> adds each transaction to at most one batch tag.

######  Proof A.2.

Following Alg. 2, S> generates batches taking transactions from
$\<pendingTxs>$, and thus, transactions come from clients invocations to add>.
Function add> guarantees that each transaction in $\<pendingTxs>$ is valid and
that no transaction is added to $\<pendingTxs>$ twice. Moreover,
$\<pendingTxs>$ is emptied after generating batches so transactions are posted
only once. Before posting batch tags, S> gathers at least $f+1$ signatures,
and thus, S> posts only legal batch tags.

The following lemma implies Termination when the majority of the DAC> members
are correct. Note that the sequencer S> waits for $f+1$ answers with
signatures. Since there are at least $f+1$ correct DAC> servers S> will
eventually collect enough signatures.

######  Lemma A.3.

If less than half of the DAC> servers are Byzantine then valid transactions
added through add> eventually appear in a legal batch tag.

######  Proof A.4.

Let $t$ be a valid transaction. As a result of add>$(t)$, S> appends $t$ to
$\<pendingTxs>$ where $t$ remains until it is added to a batch. At some point
after $t$ was added, event $\<timetopost>$ is triggered so S> generates a new
batch of transactions using $\<pendingTxs>$. Then, S> sends to all DAC>
members the batch (lines 7-10) and waits for $f+1$ responses (line 11). Since
$f<n/2$, there are at least $f+1$ correct DAC> servers executing Alg. 3, all
of which sign the hash and send it back to S> (lines 7-10). Therefore, S>
eventually receives enough signatures and posts the legal batch tag containing
$t$ (line 12).

Finally, correct DAC> members resolve signed hashes as they only sign hashes
received from S> and store their corresponding batches. Since all legal batch
tags are signed by at least one correct DAC server, it follows that S> and
DAC> satisfy Availability when used by correct clients.

######  Lemma A.5.

Correct DAC> members resolve signed hashes.

######  Proof A.6.

Let $m$ be a correct DAC> member. Following Alg. 3, $m$ only signs hashes
answering requests from S>. Upon receiving a request from S> to sign
$(h,b,\<batchId>)$, after checking that $h$ is correct and $\<batchId>$ has
not been used, $m$ saves the data received, signs the request and answers to
S>. As no entry in $\<hashes>$ is ever deleted, whenever
$m.$translate>$(\<batchId>,h)$ is invoked, $m$ uses map $\<hashes>$ to find
batch $b$ and returns it.

From the previous lemmas, we have Alg. 2 plus Alg. 3 guarantee that S> and
DAC> form a correct arranger.

######  Theorem A.7.

Clients contacting S> to add transactions and a DAC> member running Alg. 3
signing batches satisfy all correct arranger properties.

##  Appendix B Setchain Server Implementation

An overview of a setchain server implementation can be found below.

Algorithm 4 Server implementation of Setchain.

1:Init: $\<epoch>\leftarrow 0,$ $\<history>\leftarrow\emptyset$

2:Init: $\<theset>\leftarrow\emptyset$

3:function Get>( )

4: return> $(\<theset>,\<history>,\<epoch>)$

5:function Add>($e$)

6: assert> $valid(e)$ and $e\notin\<theset>$

7: add element $e$ to $\<theset>$

8: propogate $e$

9: if $e=epoch\\_signature(h,E,sign(hash(E)))$ then

10: $\<trigger>$ $\<added>(epoch\\_signature(h,E,sign(hash(E))))$

11:function EpochInc>($h$)

12: assert> $h==\<epoch>+1$

13: collaboratively compute new epoch $E$ $\triangleright$ triggers event
$\<newepoch>(h,E)$

14: validate elements in $E$

15: add new valid elements in $E$ to theset>

16: add new epoch $E$ to history>

17: increment $\<epoch>$

18: sign the new epoch and add $epoch\\_signature(h,E,sign(hash(E))))$ to the
setchain

19: $\<trigger>$ $\<newepoch>(h,E)$

##  Appendix C Payment system

We present the pseudo-code implementing a payment system based on hashed-
timelock contract for clients described in Section 5.3.

⬇

contract Payment {

address owner, beneficiary;

bytes32 secret;

uint deadline;

constructor(address _beneficiary, bytes32 _secret, uint _deadline){

beneficiary = _beneficiary;

secret = _secret;

deadline = _deadline;

}

function claim(bytes k) public {

require(msg.sender == beneficiary);

require(SHA256(k) == secret);

beneficiary.transfer(balance);

}

function withdraw() public {

require(msg.sender == owner);

require(now > deadline);

owner.transfer(balance);

}

}

##  Appendix D Challenges pseudo-code

We present a pseudo-code for the L1 smart contract arbitrating the challenges
described in Section 5.4. These smart contracts are used during a challenge
game that implements the fraud-proof mechanisms described in Section 5.4. An
honest challenger A uses the methods of this contract to play the game
described in Section 5.4, with a guarantee that if A is correct A will win the
game. Absence of a move within a pre-defined interval results in the
corresponding player loosing the game. Note that none of this contracts has a
loop or invokes remotes contracts, so termination arguments (and gas
calculations) can be easily performed.

Algorithm 5 Data Availability Challenge.

1:function
InitDataChallenge($\mathit{id},\mathit{merkleRoot},\mathit{sigs},\mathit{staker},\mathit{value},\mathit{sender}$)

2: assert>
$(\mathit{id},\mathit{merkleRoot},\mathit{sigs})\in\mathit{proposedBatches}$

3: assert>
$\mathit{staker}\in\mathit{stakers}[(\mathit{id},\mathit{merkleRoot},\mathit{sigs})]$

4: assert> $\mathit{value}\geq cc_{\mathit{data}}$

5:
$\mathit{challengeId}\leftarrow\texttt{createChallenge}(\mathit{sender},\mathit{staker},\mathit{id},\mathit{merkleRoot},\mathit{sigs},\texttt{data})$

6:
$\mathit{challengedNodes}[challengeId][1]\leftarrow(\texttt{hash}(\mathit{merkleRoot}),\texttt{size}(\mathit{merkleRoot}))$

7: $\mathit{canBeChallenged}[\mathit{challengeId}]\leftarrow\emptyset$

8:function
PresentDataCompressed($\mathit{challengeId},n,b_{l},h_{l},b_{r},h_{r},\mathit{sender}$)

9: assert> $\mathit{sender}==\texttt{currentPlayer}(\mathit{challengeId})$

10: assert> $n\in\mathit{challengedNodes}[\mathit{challengeId}]$

11:
$(h_{n},size_{n})\leftarrow\mathit{challengedNodes}[\mathit{challengeId}][n]$

12: assert> $size_{n}>1$

13: if $\mathcal{H}(h_{l}++h_{r})\neq h_{n}$ then

14:
$\texttt{setWinner}(\mathit{challengeId},\texttt{nextPlayer}(\mathit{challengeId}))$

15: else

16:
$\mathit{canBeChallenged}[\mathit{challengeId}][\texttt{leftChild}(n)]\leftarrow
h_{l},\texttt{sizeLeftChild}(size_{n})$

17:
$\mathit{canBeChallenged}[\mathit{challengeId}][\texttt{rightChild}(n)]\leftarrow(h_{r},\texttt{sizeRightChild}(size_{n}))$

18:
$\mathit{challengedNodes}[\mathit{challengeId}]\leftarrow\texttt{remove}(challengedNodes[challengeId],n)$

19: if $\mathit{challengedNodes}[\mathit{challengeId}]==\emptyset$ then

20: $\texttt{changeTurn}(\mathit{challengeId})$

21:function PresentElement($\mathit{challengeId},n,e,\mathit{sender}$)

22: assert> $\mathit{sender}==\texttt{currentPlayer}(\mathit{challengeId})$

23: assert> $n\in\mathit{challengedNodes}[\mathit{challengeId}]$

24:
$(h_{n},size_{n})\leftarrow\mathit{challengedNodes}[\mathit{challengeId}][n]$

25: assert> $size_{n}==1$

26: if $\mathcal{H}(e)!=h_{n}$ then

27:
$\texttt{setWinner}(\mathit{challengeId},\texttt{nextPlayer}(\mathit{challengeId}))$

28: else

29:
$\mathit{challengedNodes}[\mathit{challengeId}]\leftarrow\texttt{remove}(\mathit{challengedNodes}[\mathit{challengeId}],n)$

30: if $\mathit{challengedNodes}[\mathit{challengeId}]==\emptyset$ then

31: $\texttt{changeTurn}(\mathit{challengeId})$

32:function
ChallengePosition($\mathit{challengeId},n,\mathit{moreChallenges},\mathit{sender}$)

33: assert> $\mathit{sender}==\texttt{currentPlayer}(\mathit{challengeId})$

34: assert> $n\in\mathit{canBeChallenged}[\mathit{challengeId}]$

35:
$\mathit{challengedNodes}[\mathit{challengeId}][n]=\mathit{canBeChallenged}[\mathit{challengeId}][n]$

36: $\mathit{canBeChallenged}[\mathit{challengeId}]\leftarrow
remove(canBeChallenged[\mathit{challengeId}],n)$

37: if $!moreChallenges$ then

38: $\texttt{changeTurn}(\mathit{challengeId})$

39:function Timeout($\mathit{challengeId}$)

40: if $\texttt{runoutOfTime}(\mathit{challengeId})$ then

41:
$\texttt{setWinner}(\mathit{challengeId},\texttt{nextPlayer}(\mathit{challengeId}))$

Algorithm 6 Signature Challenge.

1:function
SignatureChallengeSize($\mathit{id},h,\mathit{sigs},\mathit{value},\mathit{sender}$)

2: assert> $(\mathit{id},h,\mathit{sigs})\in\mathit{proposedBatches}$

3: assert> $\mathit{value}>=cc_{\mathit{singature}}$

4: if $|sigs|<f+1$ then

5: $\texttt{removeAllStakes}(id,h,sigs,sender,\texttt{signature})$

6:function
SignatureChallengeAggregation($\mathit{id},h,\mathit{sigs},\mathit{value},\mathit{sender}$)

7: assert> $(\mathit{id},h,\mathit{sigs})\in\mathit{proposedBatches}$

8: assert> $\mathit{value}>=cc_{\mathit{singature}}$

9: $\mathit{aggPKs}\leftarrow$

10: for $i\in\mathit{sigs}$ do

11:
$\mathit{aggPKs}\leftarrow\texttt{aggregatePK}(\mathit{aggPKs},\mathit{arrangerPK}[i])$

12: if $!validSignature(\mathit{aggPKs},(\mathit{id},h),\mathit{sigs})$ then

13: $\texttt{removeAllStakes}(id,h,sigs,sender,\texttt{signature})$

Algorithm 7 Validity Challenge.

1:function
InitValidityChallenge($id,h,sigs,e,h_{e},ePos,midH,staker,value,sender$)

2: assert> $(id,h,sigs)\in proposedBatches$

3: assert> $staker\in stakers[(id,h,sigs)]$

4: assert> $value>=cc_{validity}$

5: assert> $\mathcal{H}(e)==h_{e}$

6: assert> $\texttt{valid}(e)$

7:
$challengeId\leftarrow\texttt{createChallenge}(sender,staker,id,h,sigs,\texttt{validity})$

8: $challengeState[challengeId]\leftarrow\texttt{Bisection}$

9: $bottom[challengeId]\leftarrow(ePos,h_{e})$

10: $top[challengeId]\leftarrow(1,h)$

11: $mid[challengeId]\leftarrow(\texttt{midPos}(1,ePos),midH)$

12:function BisectionSelectSubpath($challengeId,top,sender$)

13: assert> $challengeState[challengeId]==\texttt{Bisection}$

14: assert> $sender==\texttt{currentPlayer}(challlengeId)$

15: if $top$ then

16: $bottom[challengeId]\leftarrow mid[challengeId]$

17: else

18: $top[challengeId]\leftarrow mid[challengeId]$

19: if $\texttt{dist}(bottom[challengeId].pos,top[challengeId].pos)==1$ then

20: $challengeState[challengeId]\leftarrow\texttt{OneStep}$

21: $\texttt{changeTurn}(challengeId)$

22:function BisectionMembershipProof($challengeId,h,sender$)

23: assert> $challengeState[challengeId]==\texttt{Bisection}$

24: assert> $sender==\texttt{currentPlayer}(challlengeId)$

25:
$mid[challengeId]=(\texttt{midPos}(top[challengeId].pos,bottom[challengeId].pos),h)$

26:function OneStepMembershipProof($challengeId,h,sender$)

27: assert> $challengeState[challengeId]==OneStep$

28: assert> $sender==\texttt{currentPlayer}(challlengeId)$

29:
$c\leftarrow\texttt{concatenate}(bottom[challengeId].hash,h,bottom[challengeId].pos)$

30: if $\mathcal{H}(c)==top[challengeId].hash$ then

31: $\texttt{setWinner}(challengeId,\texttt{currentPlayer}(challengeId))$

32: else

33: $\texttt{setWinner}(challengeId,\texttt{nextPlayer}(challengeId))$

34:function Timeout($challengeId,sender$) $\triangleright$ Same as in Alg. 5

Algorithm 8 Integrity Challenge.

1:function
InitIntegrityChallenge($id0,h0,sigs0,e,eH,ePos0,id1,ePos1,staker,value,sender$)

2: assert> $(id1,h1,sigs1)\in proposedBatches$

3: assert> $staker\in stakers[(id,h,sigs)]$

4: assert> $value>=cc_{integrity}$

5: assert> $\mathcal{H}(e)=eH$

6: if $id1==id0$ then

7: $h1\leftarrow h0$

8: else

9: assert> $id1\in\mathit{confirmedBatches}$

10: $h1\leftarrow\mathit{confirmedBatches}[id1].hash$

11:
$\mathit{challengeId}\leftarrow\texttt{createChalenge}(sender,staker,id0,h0,sigs0,\texttt{integrity})$

12: $challengeState[challengeId]\leftarrow\texttt{PathSelection}$

13: $Path[0][challengeId]\leftarrow(eH,ePos0,h0)$

14: $Path[1][challengeId]\leftarrow(eH,ePos1,h1)$

15:function SelectPath($challengeId,pathId,sender$)

16: assert> $challengeState[challengeId]==\texttt{PathSelection}$

17: assert> $sender==currentPlayer(challlengeId)$

18: $(bottomH,bottomPos,topH)\leftarrow Path[pathId][challengeId]$

19: $bottom[challengeId]\leftarrow(bottomPos,bottomH)$

20: $top[challengeId]\leftarrow(1,topH)$

21: $mid[challengeId]=(midPos(bottomPos,1),midH)$

22: $challengeState[challengeId]\leftarrow\texttt{Bisection}$

23: $\texttt{changeTurn}(challengeId)$

24:function BisectionSelectSubpath($challengeId$) $\triangleright$ Same as in
Alg. 7

25:function BisectionMembershipProof($challengeId$) $\triangleright$ Same as
in Alg. 7

26:function OneStepMembershipProof($challengeId$) $\triangleright$ Same as in
Alg. 7

27:function Timeout($challengeId$) $\triangleright$ Same as in Alg. 5

##  Appendix E Fraud-proof Mechanisms and Incentives - Proofs

We now provide the proof of the propositions presented in Section 5.

######  Proposition E.1.

######  Proof E.2.

Let A be an honest agent, $t$ an unconfirmed signed batch tag posted in L1, S
a staker in $t$, and $mt$ the Merkle Tree generated by the batch of
transaction in $t$. We will prove that if A and S play the data availability
challenge, then by its end either A learn all transactions in $t$ or S loses
its stake. Since A can challenge all $t$ stakers until either A learns all
transactions or there are no more stakers in $t$, the proposition follows.

We will prove by structural induction over the Merkle tree $mt$ that if a node
$n$ hash is posted in the L1 contract, then A can learn all transactions
corresponding to that node subtree, or S gets its stake removed.

The base case is when $n$ is a leaf. If A does not know the transaction
corresponding to $n$ yet, A challenges S to reveal it. S can either lose its
stake or answer the challenge correctly by posting the transaction in the L1
smart contract that checks that its hash matches $n$ hash.

For the inductive step, we consider that $n$ has a left child $l$ and a right
child $r$. The inductive hypothesis is that if the hash of $l$ and $r$ are
posted in the L1 smart contract, then A can learn all transactions
corresponding to each subtree, or S gets its stake removed. If A does not know
the transactions in $n$ subtree yet, A challenges S to reveal them. S can
either lose its stake or answer the challenge correctly by posting the nodes
$l$ and $r$ hashes in the L1 smart contract that checks that its concatenation
hashes to $n$ hash. S can also post the compressed version of the batches of
transactions corresponding to $l$ and $r$ subtrees, in which case A learns all
transaction in the $n$ subtree, by concatenating both batches. Otherwise,
since $l$ and $r$ hashes are posted in L1, A can challenge each of them and by
inductive hypothesis, either S gets its stake removed or A learns all
transactions in both subtrees, and therefore all transactions in $n$ subtree.