# LØ: An Accountable Mempool for MEV Resistance

Bulat Nasrulin  Delft University of TechnologyDelftThe Netherlands
<EMAIL_ADDRESS>,  Georgy Ishmaev  Delft University of
TechnologyDelftThe Netherlands<EMAIL_ADDRESS>,  Jérémie Decouchant
Delft University of TechnologyDelftThe Netherlands<EMAIL_ADDRESS>and
Johan Pouwelse  Delft University of TechnologyDelftThe Netherlands
<EMAIL_ADDRESS>
(2018)

###### Abstract.

Possible manipulation of user transactions by miners in a permissionless
blockchain systems is a growing concern. This problem is a pervasive and
systemic issue, known as Miner Extractable Value (MEV), incurs highs costs on
users of decentralised applications. Furthermore, transaction manipulations
create other issues in blockchain systems such as congestion, higher fees, and
system instability. Detecting transaction manipulations is difficult, even
though it is known that they originate from the pre-consensus phase of
transaction selection for a block building, at the base layer of blockchain
protocols. In this paper we summarize known transaction manipulation attacks.
We then present LØ, an accountable base layer protocol specifically designed
to detect and mitigate transaction manipulations. LØ is built around accurate
detection of transaction manipulations and assignment of blame at the
granularity of a single mining node. LØ forces miners to log all the
transactions they receive into a secure mempool data structure and to process
them in a verifiable manner. Overall, LØ quickly and efficiently detects
reordering, injection or censorship attempts. Our performance evaluation shows
that LØ is also practical and only introduces a marginal performance overhead.

††copyright: acmcopyright††journalyear: 2018††doi:
XXXXXXX.XXXXXXX††conference: Make sure to enter the correct conference title
from your rights confirmation emai; June 03–05, 2018; Woodstock, NY

##  1\. Introduction

Enabled by blockchain technologies, Decentralised Finance (DeFi) tools and
mechanisms have generated a lot of interest as building blocks for novel
digital markets, both in terms of practical applications amounting to over 80
billion USD total value locked at the moment of writing, and in terms of
significant research interest (Xu et al., 2023). Furthermore, these tools
enable monetization mechanisms for the new paradigm of Web3 development,
providing alternatives to monopolistic centralised digital platforms.
Decentralised exchanges, lending markets, derivatives, and other products
built on permissionless blockchains are just some examples of these novel
financial applications. However, these developments, are undermined by
unresolved issues of transaction manipulations, such as _censorship,
injection_ , and _re-ordering_ of transactions, at the expense of application
users at underlying layers of blockchain protocols.

This problem led to the notion of Miner Extractable Value (MEV)111Sometimes
also referred to as Blockchain Extractable Value, or Maximum Extractable
Value., which refers to the maximum revenue a miner can obtain from benign or
manipulative transaction selection for block production (Daian et al., 2019;
Qin et al., 2022). This problem is a pervasive and systemic issue at large
scale as exemplified by the Ethereum blockchain, where MEV transaction
manipulations have generated over 320 USD million of revenue for bots and
miners (Wahrstätter et al., 2023). Furthermore, over 90% of the blocks
produced on Ethereum contain MEV transactions (Qin et al., 2022). Such
manipulations not only undermine users’ trust, but also induce systemic issues
like congestion, inflated fees, and system instability (Mazorra et al., 2022).

We argue that the root cause of MEV is a lack of accountability at the base
layer of permissionless blockchain protocols, sometimes referred to as ’dark
forest’ (Qin et al., 2022). By base layer, we refer to the processing steps
that happen before consensus has to be reached on a block, such as sharing
pending transactions (recorded in the mempool) with other miners and
assembling them into blocks. In contrast to what happens at the consensus
layer, at the base layer miners are expected to act as trusted parties. As
such, a miner that creates a new block can arbitrarily select the transactions
from its mempool. In practice, miners can therefore arbitrarily censor, inject
or reorder transactions (Gervais et al., 2015).

While this problem has received certain attention in the context of MEV
mitigation tools, there are no comprehensive solutions preventing these types
of transaction manipulations (Piet et al., 2022). Most of the proposed
solutions in this category focus on the application layer and on consensus
layer mitigation tools (Yang et al., 2022). Many of these tools do not prevent
MEV attacks but rather aim to mitigate them. The most well known approach,
Proposer Builder Separation (PBS) (fla, [n. d.]), is implemented with the
Flashbots middleware on Ethereum and does not prevent MEV, but only the
redistribution of its associated revenues. Some proposed theoretical
solutions, such as fair ordering consensus protocols (Kelkar et al., 2021),
prevent transaction manipulations. However, these algorithms assume
permissioned settings and small network sizes, and require important
modifications of the blockchain consensus layer.

As transaction manipulations arise from the lack of accountability at the base
layer of blockchain protocols, we argue that comprehensive mitigation of MEV
requires addressing trust assumptions at this particular layer. To address
them, we design LØ, an accountable mempool protocol.

In LØ miners become accountable for the process of transaction selection and
ordering. As new transactions are propagated among miners, they exchange and
record commitments on the content of their mempools with each other. New
transactions are shared in bundles, and commitment is recorded on a whole
transaction bundle. This provides a local partial ordering of transactions.
Our system is based on _pairwise commitments_ that are exchanged during a
mempool reconciliation phase, which is executed before the consensus protocol.
This allows miners to witness each others’ transaction selection and commit to
a particular order and set of transaction that they will use for block
generation. Therefore, LØ ensures that any transaction manipulation, such as
transaction censorship, injection and reordering, can be detected and proven
by a correct node.

Our system is agnostic to a specific type of consensus protocol in a
permissionless blockchain system. It can be seamlessly integrated with
existing blockchain solutions, as a relatively simple modification of a Peer-
to-Peer (P2P) protocols that propagates transactions and blocks. In addition,
it does not require any additional cryptographic setups, and it does not
impose a significant performance overhead. We leverage Minisketch data
structure for the reconciliation of mempools to implement bandwidth-efficient
commitments (Naumenko et al., 2019).

This paper makes the following contributions:

$\bullet$ We identify key types of transaction manipulation attack primitives
at the base layer. We propose a new taxonomy based on these attack primitives
that can grasp all potential MEV attacks. We discuss the stages of the
transaction processing pipeline that allow for these manipulations by miners.
(§2).

$\bullet$ After describing our system model (§3), we provide an overview of
LØ, an accountable base layer protocol specifically designed to prevent
transaction manipulations. LØ is built around accurate detection of
transaction manipulations and assignment of blame at the granularity of a
single mining node. We discuss specific policies targeted at the detection of
different MEV manipulations in (§4).

$\bullet$ We detail how LØ detects transaction manipulation attacks and
potential mechanisms for the enforcement of these policies (§5). We further
discuss possible attacks against accountability in LØ.

$\bullet$ We present our performance evaluation, which demonstrates that LØ is
practical. It is both bandwidth and memory efficient. For example, it only
requires up to 10 MB of additional storage for a network of 10,000 nodes and a
workload of 20 transactions per second. At the same time, it is at least four
times more efficient than the classical flooding-based mempool exchanges (§6).

##  2\. Transaction Manipulations at the Base Layer

We distinguish the _base layer_ of a blockchain system from its consensus
layer. In the complete life-cycle of a transaction from its creation to its
inclusion in a blockchain, the base layer corresponds to the steps that
precedes the block consensus phase as illustrated in Fig. 1. These steps
include the creation of the transaction and its initial sharing, its inclusion
in the mempools, the reconciliation of the mempools between miners, and the
inclusion of the transaction in a candidate block.

We emphasize that the block-building phase, where a miner selects transactions
that it includes in a candidate block, is a pre-consensus phase. Indeed, while
sometimes block building is described as part of blockchain protocols, it is
strictly speaking not a part of the consensus mechanism as blocks can be
produced offline, as illustrated by PBS in Ethereum and selfish mining in
Bitcoin (Eyal and Sirer, 2018). We further distinguish the base layer from the
network layer of blockchain protocols, as the latter is required in all
transaction processing phases, including during consensus.

The base layer typically provides much lower guarantees against misbehaving
nodes than the consensus layer. Miners only conduct checks on the validity and
priority of transactions (which is related to miners fee) and add it to a
local pool of unconfirmed transactions referred to as the ’mempool’ (Wang et
al., 2021). However, miners are considered to be trusted parties with regard
to the selection, withholding, and ordering of transactions (Gervais et al.,
2015). Therefore, all phases of the transaction life-cycle that precede
consensus allow transaction manipulations.

Figure 1. Functional modules of a permissionless Blockchain divided into two
layers (base and consensus) and four stages.

###  2.1. Transaction Manipulation Primitives

We consider practical attacks that include reordering of transactions by
miners. These attacks have been observed in practical settings and described
in academic works that relate to MEV (Yang et al., 2022). In practice, these
attacks combine different types of transaction ordering manipulations. A
common taxonomy of MEV attacks is application-specific and depends on the
source of attack revenue. Well known attack types include _sandwich-attacks,
front running, back running_ , which are associated with decentralized
exchanges, _sniping_ , which is associated with Non Fungible Token auctions,
and _liquidations_ , which are associated with collateralized loan protocols.
This taxonomy evolves as new MEV attacks rapidly emerge with new applications.

In this paper we consider a different taxonomy focusing on specific attack
primitives on the base layer. These primitives allow a broad range of MEV,
either on their own or in combination. Namely: _censorship, injection_ , and
_re-ordering_ of transactions.

Censorship. Censorship is the ability of a miner to delay or ignore new
transactions. Censorship can enable different financially motivated MEV
attacks, such as _sniping_ , executed alone or in combination with other
primitives. For example, when receiving transactions for a bid in Non Fungible
Token auctions, a faulty miner can censor competing transactions to become the
auction winner. This censorship mechanism can take place either during the
mempool inclusion phase, or during the block inclusion phase.

Mempool Censorship. Faulty miners can ignore transactions received from some
other nodes, and exclude their valid transactions from their mempool. We
assume that a faulty miner either provides a fake transaction reception
acknowledgment, or does not acknowledge it at all. This type of attack enables
censorship at the level of a mempool (Yang et al., 2022), and facilitates
transaction manipulation based on front-running.

Blockspace censorship. Faulty miners can exclude valid transactions from
blocks, even after acknowledging their reception and including it in the
mempool. This enables transaction censorship at the level of blockspace.

Injections. We assume that honest miners include transactions received from
other nodes in new blocks in a deterministic order. Honest miners can also add
their own new transactions, under the assumption that updated mempool
commitment is shared with other nodes and acknowledged. Faulty miners inject
new transactions in blocks in an arbitrary manner, without prior sharing of
the updated mempool and without acknowledgements. This type of attack can
result in certain types of transaction manipulations such as front-running,
sandwich, back-running (Daian et al., 2019).

Reordering. Faulty miners can reorder transactions in a mempool and in a block
in a way that deviates from a protocol and violates expectations of other
nodes. Reordering is different from an injection attack, since a faulty miner
does not add new transactions itself, but manipulates the order of transaction
received from other nodes.

###  2.2. Transaction Processing Stages

Attacks can happen at different stages of the transaction life-cycle. We model
the processing of a transaction in a generic blockchain system in Fig. 1. This
processing happens in four stages: (I) initial transaction sharing, (II)
mempool reconciliation, (III) block building and (IV) block settlement. In the
following we describe each stage, and discuss the corresponding attacks that
enable transaction manipulations such as MEV.

Stage I. Initial transaction sharing. A transaction is first created at the
client side. The client signs the transaction with its private key. The
transaction contains all the required context to be processed by miners, such
as signature, UTxO address, execution commands, transaction fee, etc. The
client shares the transaction with a subset of peers that it personally knows
or whose identity is publicly known (step 1). The peers receive the
transaction and attempt to prevalidate it (step 2). Our system is agnostic in
respect to the choice of specific consensus protocol which will define the
requirements for transaction prevalidation. For example, successful
prevalidation of a transaction may require: valid signature from a client,
sufficient amount of in a client account, and inclusion of a sufficient
transaction processing fee.

Miners that successfully prevalidate a transaction insert it in their local
mempool storage. Optionally, miners might respond to the client with the
transaction status, to acknowledge inclusion of a transaction in a mempool
(step 3). Also optionally, client can query a miner to get an acknowledging of
transaction inclusion in a mempool. A malicious peer can censor the
transaction at the point of prevalidation, without adding it to the mempool
performing Exclusion From Mempool. For example, a peer can exclude a client
based on its id, e.g. all transaction originating from a specific address. At
the same time, client and peer can collude to include an invalid transaction
into a mempool.

Stage II. Mempool reconciliation. At this stage peers share their transaction
mempools (step 1). Typically, a mempool exchange is implemented to first share
the transaction ids, and only later selectively share the transaction content
of the corresponding ids. Once a miner receives the transaction content, it
prevalidates the transaction (step 2), similarly to stage I. In theory, this
stage allows miner to converge to the same transaction set for any peer-to-
peer network. Unfortunately, in practice, there is no guarantee that miners
will converge. Client can be partially or completely excluded from learning
particular transactions when communicating with malicious peers. Moreover,
miners can inconsistently exchange their mempools. Finally, without a
requirement for the mempool reconciliation, malicious miner can exclude or
include any transaction without being detected by other miners. Different
types of Injection attacks and Exclusion attacks can be performed by faulty
miners at that stage. For example, a malicious miner receiving a high-fee
transaction can withhold it from sharing with other nodes in order to include
it in own block later.

Stage III. Block building. Upon creating a block, a miner populates it based
on information stored in its local mempool data (step 1). For each block, the
miner selects a subset of transactions to fill up the blockspace (step 2). The
selected transactions are included in the block in a specific order chosen by
the miner (step 3). A final block contains additional metadata, like
signature, nonce, or timestamp (step 4). Most of the reported MEV is happening
at the stage of block building. Indeed, miners can freely select, exclude, or
order transactions to maximize their profit, performing Order manipulation and
Blockspace censorship.

Stage IV. Block settlement. LØ is agnostic to the specific consensus process
to finalize the blocks. We model miner selection as a random process, where a
selected miner build its block and sends it to other miners. The attacks on
this stage are extensively discussed in previous works. The most discussed
manipulations include block withholding, block reordering and equivocation
attacks. We consider the accountability on this stage out of scope. Our
solution can be combined with other solutions addressing the manipulations on
this stage, such as Polygraph (Civit et al., 2021).

##  3\. System Model

This section describes our system model, which is the classical one for
blockchain protocols .

The mining nodes (miners) belong in a set $\Pi=\\{p_{1},p_{2},\dots\\}$ and
communicate with each other by exchanging messages over the network. We assume
that each miner is equipped with a cryptographic key pair, and is uniquely
identified by its public key. Nodes have access to a cryptographic signature
scheme and messages are authenticated.

Communication Overlay. Nodes form an undirected communication graph that is
not assumed to be fully connected. Nodes are free to unilaterally add or drop
local connections. Nodes are able to leave and later rejoin the network. Nodes
share messages to their overlay neighbors through their direct connections. We
use notation $N_{i}$ to refer to the neighbors of a node $p_{i}$, i.e., the
nodes that are currently directly connected with it.

Bootstrap and Peer Discovery. We assume that nodes that join the system are
able to contact bootstrap nodes that facilitate node discovery. When
(re)joining the network, each correct node requests a set of known active
nodes from the bootstrap nodes. The bootstrap nodes are correct, i.e., they
serve all nodes and unbiasedly propose a node from a set of locally known. As
a result the nodes operate in one network.

Continuous sampling. Correct nodes continuously sample the network through a
discovery procedure. LØ is build on top of Byzantine resilient uniform
sampling algorithm (Bortnikov et al., 2009). Malicious nodes can delay the
discovery, however, it is guaranteed that correct node will eventually be able
to communicate.

Types of Nodes. In different consensus protocols nodes participating in block
creation can be called validators, proposers, builders, etc. Here we only
consider the role of block creator and refer to the nodes that create blocks
as miners. For the sake of simplicity we do not consider light clients, which
our model can trivially cover without modifications.

Miners can create new transactions, and they can also propose new blocks with
ordered transaction to be included in the blockchain. All nodes maintain a
list of unconfirmed transactions (mempool) and exchange it with other nodes in
the network through messages.

###  3.1. Attacker Model

In our network, each node is either correct or faulty. Correct nodes adhere to
the reference protocol without data tampering and generate valid messages.
Faulty nodes, on the other hand, can deviate arbitrarily from the reference
protocol.

We assume that a faulty miner can execute any of the transaction manipulations
we previously described: censoring transactions, injecting new transactions
out-of-order, or deviating from the canonical transaction order (Zhou et al.,
2022). These attacks can be carried out by a faulty miner in a naive way by
sending the same message (e.g., a reordered set of transactions) to all
neighboring nodes, or they can attempt to evade detection of manipulations by
equivocating, i.e., sending conflicting messages to different nodes.

###  3.2. Accountability

We consider the standard accountability property for distributed systems and
protocols (Haeberlen et al., 2007). We define accountability as the ability to
detect transaction manipulations and assign blame at the granularity of a
single mining node.

In asynchronous environments, an adversary can try to evade detection as it is
challenging to distinguish between a misbehaving node that deliberately
ignores requests and a slow node. To circumvent this difficulty, we divide
blames into two types: _suspicions_ and _exposures_. An exposure is a
verifiable proof of misbehavior, while a suspicion is a lack of response to a
request.

We consider two desirable properties of accountability:

Accuracy: (1) Temporal. No correct node is perpetually suspected by a correct
node, and (2) No false-positives. No correct node is exposed as misbehaving by
other nodes.

Completeness: (1) Suspicion completeness. Every misbehaving node that ignores
requests is perpetually suspected by all correct nodes. (2) Exposure
completeness. Given an exposure message on node $p_{i}$, every correct node
exposes node $p_{i}$ as misbehaving.

##  4\. LØ: Accountable Base Layer

In this section we present LØ which achieves accountability at the base layer.
Specifically, LØ is implemented as a modification of mempool reconcilation and
block building stages.

###  4.1. New Explicit Policies at the Base Layer

Addressed Manipulation | Current implicit policies | New explicit policies
---|---|---
Censorship | Unreliable Transaction Gossip | Inclusion of All Transactions
Injection | Out-Of-Order Transaction Selection | Transaction Selection in Received Order
Reordering | Arbitrary Order in a Block | Verifiable Canonical Order in a Block
Table 1. Implicit policies in the base layer of typical permissonless
blockchain and the new explicit policies we replace them with to detect
transaction manipulations.

This section introduces LØ, our accountable base layer protocol for
permissionless blockchains. LØ improves over the ‘vanilla’ mempool
reconciliation and block building protocols of permissionless blockchains
(stages 2 and 3 of Fig. 1).

To enable accountability we require to modify some currently implicit or ill-
defined polices at the base layer. Our observation is that current
implementations of blockchain systems use implicit policies that significantly
complicate the detection of transaction manipulations. First, a transaction
censorship is not possible to attribute to a miner given an unreliable
transaction relay. Every miner has its own relaying policy, and even perfectly
correctly behaving nodes may choose not to relay anything at all. Second,
miners can build a block with any transactions from the mempool, or even
inject new transactions during the block creation. Third, there is no
‘canonical order’ inside a block, allowing for any type of reordering.

Instead of these ill-defined policies we propose three alternative explicit
policies to enable the detection of any transaction manipulations, as
presented in Table 1. In a nutshell, LØ introduces three new explicit
policies: _Inclusion of All Transactions_ , _Transaction Selection in Received
Order_ , and _Verifiable Canonical Order in a Block_. Transaction
manipulations are detected as violations of our explicit policies during the
mempool reconciliation, or when inspecting the content of a block.

Inclusion of All Transactions. Each miner includes all valid transactions it
encountered during the system run in its locally maintained append-only
transactions set. Once two nodes are connected they directly exchange their
known transactions. The transaction exchange is implemented as a sequence of
set reconcilations. The miners exchange multiple transactions in one
transaction bundle. This allows two nodes to efficiently obtain the
transactions they are missing and as a result end up with the same transaction
sets.

The key ability of LØ is that after a successful round of reconciliation both
correct nodes are ensured to have a common set of observed transactions. To
ensure that none of the transactions is censored and all processed in the same
way miners keep all valid transactions they encounter. Miners commit to be
able to reveal all transactions they know about, if necessary.

Transaction Selection in Received Order. During the reconciliation process,
each miner commits on the order it received a transaction bundle from another
miner. To mitigate any out-of-order injections, the miners are required to
process the transactions following their insertion order in their mempool. As
miners learn and commit on their mempool transactions, the transactions are
then naturally ordered according to the order with which they were received.

Verifiable Canonical Order in a Block. Transactions that are inserted into a
newly created block are selected according to a deterministic process. In more
details, committed transaction bundles are first assembled following
sequential order. The order inside a bundle is then pseudo-random:
transactions are shuffled using a known shuffling algorithm and an _order
seed_ value. The order seed value is based on the hash of the last created
block.

###  4.2. Mempool Reconciliation

The mempool reconciliation process (cf. §2.2) forces miners to correctly share
the transactions they accepted into their mempool. In practice, LØ’s mempool
reconciliation uses two techniques: (i) anti-entropy gossip reconciliations
(Eppstein et al., 2011; Van Renesse et al., 2008); and (ii) signed commitments
(Arakala et al., 2007; Naumenko et al., 2019).

Algorithm 1 LØ on miner $p_{i}$.

1:$\widehat{\mathzapf{C}_{1}},\ldots,\widehat{\mathzapf{C}_{N}}\leftarrow\emptyset,\ldots,\emptyset$
$\triangleright$ Last observed commitments

2:$\mathzapf{E}\leftarrow\emptyset$ $\triangleright$ Set of exposed miners

3:$\mathzapf{S}\leftarrow\emptyset$ $\triangleright$ Set of suspected miners

4:procedure $\mathtt{NeighborsSync}$

5: for $p_{j}\in Neighbors(i)$ do

6: if $\mathzapf{C}_{i}\setminus\widehat{\mathzapf{C}_{j}}\neq\emptyset$ then
$\triangleright$ Peer j is outdated

7: $\mathzapf{S}\leftarrow\mathzapf{S}\cup\\{p_{j}\\}$

8:  _request_ $\mathzapf{C}_{j}\supseteq\mathzapf{C}_{i}$ from $p_{j}$

9: else

10: $\mathzapf{S}\leftarrow\mathzapf{S}\setminus\\{p_{j}\\}$

11:on $\mathtt{Receive}$ $\mathzapf{C}_{j}$

12: if $\widehat{\mathzapf{C}_{j}}\subset\mathzapf{C}_{j}$ then

13: $\widehat{\mathzapf{C}_{j}}\leftarrow\mathzapf{C}_{j}$

14:
$\Delta\mathzapf{C}_{ji}\leftarrow\mathzapf{C}_{j}\setminus\mathzapf{C}_{i}$

15: if $\Delta\mathzapf{C}_{ji}\neq\emptyset$ then

16:  _send_ $H(C_{j}),C_{i}$ to $p_{j}$ $\triangleright$ Commit

17: else

18:  _send_ $C_{i}$ to $p_{j}$

19: if
$\mathzapf{C}_{j}\setminus\widehat{\mathzapf{C}_{j}}\neq\emptyset\And\widehat{\mathzapf{C}_{j}}\setminus\mathzapf{C}_{j}\neq\emptyset)$
then

20: $\mathzapf{E}\leftarrow\mathzapf{E}\cup\\{p_{j}\\}$

21:  _Broadcast_ $\mathzapf{C}_{j},\widehat{\mathzapf{C}_{j}}$

22:

23:on $\mathtt{Receive}$ $H(C_{i}),C_{j}$

24:  _send_ $txs\in\Delta C_{ij}$ to $p_{j}$

25: $\widehat{\mathzapf{C}_{j}}\leftarrow\mathzapf{C}_{j}\cup C_{i}$

26:

Figure 2. Example of a mempool reconciliation in LØ between node $B$ and nodes
$A$, $C$. Node $B$ preserves the transaction order for the block it eventually
creates.

Nodes maintain a mempool of all pending transactions and keep a record of all
valid transactions they have ever received. Nodes reconcile their mempools to
disseminate transactions throughout the system and generate commitments that
are exchanged during mempool reconciliations. These commitments cover not only
the transactions in the current mempool, but all valid transactions ever
received by a node at the time of reconciliation.

Mempool reconciliation serves two purposes: (1) it allows miners to learn
about new transactions from their neighbors; and (2) it ensures that miners
commit to a specific transaction partial order during reconciliation. This
partial order must be maintained during block creation. Miners mutually commit
to the order by first exchanging a commitment. Miners are inherently motivated
to receive transactions from other miners. However, they only disclose the
transactions after their counterpart has committed to a specific order of
transactions.

Reconciliation Algorithm. In Algorithm 1 we provide LØ’s pseudocode for a
miner $p_{i}\in\Pi$.

Periodically, miners require their neighbours to commit for new transactions
by sending them a request for a new commitment (line 4-10). While the request
is pending, the node is suspected. We refer to $C_{i}$ as a commitment for the
set of transactions included by miner $p_{i}$. At the same time, the
commitment serves as a cryptographic checksum of included mempool
transactions.

During the reconciliation process, nodes first exchange a signed commitment
$C$. After receiving the commitments of their neighbours, nodes calculate
their transaction set differences with them (line 14). Since the commitment is
signed, it can later be used as a proof of inclusion of transactions—any
receiver can use the commitment $C_{j}$ as verifiable evidence that node
$p_{j}$ should have included transactions in its mempool.

Our mempool reconciliation between a miner $p_{i}$ and miner $p_{j}$ works in
two phases. In the first phase, miner $p_{i}$ sends to miner $p_{j}$ a request
to commit to new set of transactions (line 8). A peer $p_{j}$ receives the
request and responds either with its new $C_{j}$ that already includes all
transactions (line 18), or with a new commitment fixing locally the order of
transactions $\Delta C_{ij}$, i.e., a promise to apply them immediately after
all known local transactions $C_{j}$ (line 16). In the second phase, miner
$p_{i}$ sends all the transactions corresponding to the $\Delta C_{ij}$ to
peer $p_{j}$ (lines 23-25).

All miners store at least the last received commitments from their overlay
neighbors (line 13). On receiving a checksum ${C}$ it is first validated
against previously received set $\widehat{{C}}$ (line 19-21). The set
$\widehat{{C}}$ is grow-only and keeps all the transactions committed by the
node. If ${C}$ is inconsistent against the previously reported messages
$\widehat{{C}}$, the evidence of the faulty behavior is shared with other
nodes (line 21). This inconsistency could happen for example when a faulty
node is trying to hide a previously reported message or does not report a
message received from other nodes.

Example. Fig. 2 illustrates a possible mempool reconciliation. Nodes $A$, $B$,
and $C$ first exchange transaction commitments. Note that commitments can also
be received indirectly, but this scenario is not included in Fig. 2 for
simplicity. Node $A$ sends a request, along with the mempool commitment
$C_{A}$, to node $B$. Node $B$ reconciles commitment $C_{A}$ with its own
$C_{B}$ and promises to include node $A$’s missing transactions immediately
after all transactions $C_{B}$. Node $A$ promptly sends the missing
transaction 2 to node $B$. Shortly afterward, node $C$ reconciles with node
$B$ in a similar manner. However, this time, node $B$ promises to include
transactions of node $C$ only after the transactions 1,3,4,2. Let’s assume
that later, node $B$ creates a new block, possibly because it is elected as a
consensus leader. Node $B$ must then select all transactions in the order of
the commitment it made, which is 1,3,4,2,5,6.

Implementation Details. LØ employs Minisketch and Bloom Clocks to implement
the mempool reconciliation protocol efficiently. A commitment in this context
includes both the miner’s Bloom Clock and Minisketch. These data structures
serve two primary purposes: (1) they identify inconsistencies with the digests
shared in previous rounds, and (2) they facilitate set reconciliation to
identify a miner’s unknown transactions.

A Minisketch is a data structure proposed for the bandwidth-optimized exchange
of transaction sets between nodes in the Bitcoin network (Naumenko et al.,
2019). Initially proposed for the reconciliation of mempool data, it can also
be used to optimize block propagation. In this protocol, a sketch serves as a
”set checksum”. The primary advantage of Minisketch is its ability to
reconcile quickly and accurately. However, it has a downside: the requirement
to decode the reconciled Minisketch, which can fail. In such cases, we repeat
the process by dividing the set in half and sending two sketches.

A Bloom Clock is a space-efficient, probabilistic data structure used for the
partial ordering of events in distributed systems (Ramabaja, 2019). LØ uses
Bloom Clocks to swiftly detect inconsistencies between two sets. In rare
cases, when a Bloom Clock fails to detect an inconsistency due to collisions,
we resort to a hash checksum. We employ Bloom Clocks to speed up the
verification of inconsistencies between two sets.

###### Summary 0.

The pairwise commitment scheme ensures that miners are committed to all
transactions they discover according to the order with which they are
received.

###  4.3. Block Building

Figure 3. Block building and inspection in LØ.

To avoid manipulations during the block building stage, we slightly modify the
‘vanilla’ block building process with our new policies. The modified block-
building process is shown in Fig. 3.

Transaction Selection. Peers select all transactions they encounter during the
mempool reconcilation phase and that are included in the mempool (step 1).
Miners must verify these transactions. The transactions that are not valid are
not included in the block. The transactions that have fees lower than some
threshold are not included in the block, and are rejected (step 2).

Transaction Ordering. The selected transactions are ordered in a verifiable
canonical way (step 3). Recall from the mempool reconciliation process that
transactions are partially ordered with the commitments order as the
commitments define the order between transaction bundles. We also define a
deterministic pseudo-random order function inside each of the bundle. We use a
hash of previous block as a seed for the intra-bundle order function.

Block Inspection. Next, a block is created (step 4) and shared with the
network. Given the mempool commitments, any node can verify the produced block
by inspecting its content with respect to the LØ reference protocol (step 5).
Note that block inspection is a separate process than block validation, and
does not affect the block inclusion into the chain. Any violation exposes the
block creator (step 6), by comparing the block content with the known
commitments. Our protocol is agnostic to the specific punishment mechanisms,
but we discuss some options in Section 5.3.

###### Summary 0.

During the block building process, miners select and order transactions
deterministically.

##  5\. Dealing with Attacks

This section presents an analysis of various attacks and discusses how the
integration of detection mechanisms and a broad spectrum of enforcement tools
can counter them.

###  5.1. Detection of Transaction Manipulations

Every node utilizes a block inspection module to detect violations. Nodes are
required to disclose all their known transactions and they must consistently
disclose each commitment or they run the risk of being identified as faulty.
An inconsistency is detected when comparing two commitments, provided both
sets contain at least one transaction.

Nodes are obligated to respond to commitment requests. Failure to do so
results in an eventual fault suspicion by every correct miner in the network.
Reconciliation messages and proposed blocks are validated against the protocol
rules. Violations, such as censorship of particular transactions, commitment
inconsistencies, or message tampering, can then be identified. Evidence of
faulty behavior is disseminated across the network by correct miners.

Countering Attacks during Mempool Reconciliation. Every node involved in a
mempool reconciliation retains a signed commitment acquired from other nodes,
which can be used to identify faulty nodes. Sufficient interaction with
correct nodes in the network makes it virtually impossible for a node to
manipulate its mempool and not be detected. The mempool reconciliation process
thus ensures reliable detection of injection and mempool censorship attacks. A
misbehaving miner attempting a front-running attack, for example, may inject a
new transaction out-of-order. However, this attack is swiftly detected as the
injected transaction would be inconsistent with previous commitments.

Enhancing Detection Resilience. After a mempool reconciliation between two
miners, they can mutually detect each other’s violations. Throughout the
operation of the system, miners collect commitments from all their overlay
neighbors. Consequently, an overlay neighbor can detect a violation. However,
if an overlay neighbor is offline, it cannot broadcast the exposure message to
other miners. To enhance resilience, miners share between each other a sample
of the last commitments they received. This allows other non-neighbouring
miners to also detect violations.

Countering Attacks during Block Building. The order function ensures that
order manipulation attacks can be detected, as any block where the transaction
order deviates from the canonical one will be detected. Similarly, a block-
space censorship attack is detected as a deviation from the selection function
rules.

###  5.2. Suspicion and Misbehavior Sharing

LØ provides guarantees that violation of block production rules can be
reliably detected by other nodes in the block inspection process and that
misbehaving node will be exposed. Our accountability mechanism provided in LØ
that consists of suspicions, equivocation detection, and exposure.

Figure 4. Consistency check and suspicion mechanisms.

Suspicions. The Accountability Mechanism incorporates liveness checks and
propagates transaction commitments between nodes through indirect paths. If a
node does not respond to transaction requests before a timeout, it is
suspected by the requester. The requester may resend the request multiple
times before suspecting the node. Correct nodes retain all pending requests.
If a node is suspected, the requester broadcasts the suspected requestee’s
identity to other nodes, along with information on pending requests and the
requestee’s last known commitments. A node may retrieve pending requests after
a partition or a crash. Once it publicly responds to all pending requests, no
correct node will suspect it.

In Fig. 4, node $B$ has an earlier commitment $(C_{A,n})$ from node $A$. Node
$C$ has the latest commitment $(C_{A,n+1})$ from node $A$. Node $B$ sends a
request for a commitment on a particular transaction $\tau$ from node $A$, but
does not receive a response. After a timeout, node $B$ suspects node $A$ and
broadcasts a suspect status along with the latest commitment $(C_{A,n})$ from
$A$ that is available to $B$ to its neighbors, in this case, to node $C$.

Equivocation Detection. A consistency check occurs when a node is suspected.
Commitments are append-only sets and thus follow chronological order. When a
node has two commitments from a neighbor, it can easily detect any
inconsistency between the previous commitment $n$ and the latest commitment
$n+1$ using its bloom clock. Nodes can receive commitments from other nodes
both directly and indirectly. Consider an example of suspicion and consistency
check in Fig. 4. Node $C$ receives two commitments originating from node $A$,
i.e., commitment $(C_{A},n+1)$ from node $B$, and $(C_{A},n+1)$ from node $A$.
Node $B$ has tried to get a commitment on transaction $\tau$ from A and
suspects A because of the high response delay. Node $C$ will check whether
$(C_{A},n)$ and $(C_{A},n+1)$ are consistent with each other.

  * •

If these commitments are inconsistent, node $C$ exposes $A$ as a misbehaving
node.

  * •

If $(C_{A},n)$ and $(C_{A},n+1)$ are consistent and $(C_{A},n+1)$ already
includes a commitment on a transaction $\tau$, then node $C$ will share the
latest commitment $(C_{A},n+1)$ with $B$.

  * •

If $(C_{A},n)$ and $(C_{A},n+1)$ are consistent but $(C_{A},n+1)$ does not
include a commitment on $\tau$, then $C$ will send a request for commitment on
$\tau$ to $C$ and suspect $C$.

###### Summary 0.

Any mempool counterpart can submit a proof of misbehavior showing
inconsistency between a mempool commitment and a produced block.

###  5.3. Possible MEV Prevention Mechanisms

Reliable detection and blame assignment allow for MEV mitigation through the
enforcement of policies. The choice of specific enforcement mechanisms depends
on the consensus protocol. Given that LØ is agnostic to the particular
consensus algorithm used, a detailed analysis of specific enforcement
mechanisms is beyond the scope of this paper.

For instance, in Proof-of-Stake (PoS) consensus algorithms, various slashing
strategies can be applied to misbehaving nodes (Buterin and Griffith, 2017).
Since validating nodes in PoS must invest a certain amount of funds to become
validators, slashing of stake incurs a financial loss. For consensus
algorithms based on the reputation of validating nodes, slashing of reputation
can equivalently serve as a penalization mechanism (Yu et al., 2019).
Misbehaving nodes can also be penalized at the network layer level, such as
temporary disconnection from the network (Gervais et al., 2015). In addition
to penalizing misbehaving miners, detection allows the implementation of
mechanisms for the rejection of blocks that deviate from the canonical
transaction order (Sheng et al., 2021). However, this latter approach imposes
significant trade-offs on the modification of the consensus protocol.

###  5.4. Addressing Accountability Attacks

In our model, we assume that miners are incentivized to learn about more
transactions. This assumption aligns with empirical observations, as miner
profitability correlates with their ability to discover new transactions (Piet
et al., 2022).

Figure 5. Illustration of colluding malicious miners communicating off-channel
to evade detection.

In our system, miners only discover transaction content after exchanging
commitments. Hence, by learning about new transactions, miners commit
themselves to mempool commitments. However, a potential loophole exists for
malicious miners. A miner could conspire with an accomplice who does not
interact with correct nodes to create a block for them using a manipulated
transaction order. This attack is depicted in Fig.5. A malicious miner can
transfer a transaction, denoted as _Tx_ , to another colluding miner or to a
Sybil miner under their control. Since a colluding miner has not exchanged
commitments with the originator of _Tx_ , it can attempt to reorder or inject
transactions, and propose an alternative block. However, this type of attack
is impractical due to several reasons:

  * •

Colluding miners can only front-run or back-run an entire original transaction
bundle. Any attempt to inject, censor, or reorder transactions within a
transaction bundle is eventually detectable by correct miners. This
significantly restricts the attack granularity, a crucial factor for MEV
profitability.

  * •

Colluding miners or Sybils cannot respond to queries from honest miners to
evade commitments. They can only learn about new transactions via malicious
nodes acting as a bridge. However, such a non-responding set of colluding
miners is eventually detected and suspected.

  * •

Colluding miners or Sybil miners must have a high probability of becoming the
consensus leader to include a specific transaction. To increase this success
rate, a substantial set of colluding miners or Sybils is required, which is
costly considering the initial investment and the absence of profits from
honest protocol participation.

Finally, to further mitigate the attack, one option is to require sufficient
Proof-of-Interaction during block creation. Specifically, the block creator
must also include signatures from a sufficient number of miners (based on
mining power or stake), thereby proving recent interaction with them.

##  6\. Evaluation

This section presents our evaluation of LØ focusing on its resilience against
malicious nodes and the impact of such nodes on detection. We also discuss the
overhead associated with LØ.

###  6.1. Experimental setup

LØ was evaluated experimentally on a national research cluster (Bal et al.,
2016). Each server in the cluster is equipped with an Intel Xeon E5-2630 CPU
with 24 physical cores operating at 2.4 GHz, hyper-threading enabled, and 128
GiB of main memory. The servers are interconnected via a Gigabit Ethernet
network. LØ was implemented in Python. We emulated realistic network latencies
using netem222See https://www.linux.org/docs/man8/tc-netem.html and
incorporated ping statistics from 32 cities worldwide from the WonderNetwork
dataset (WonderNetwork, [n. d.]). Each miner was assigned to a city in a
round-robin manner.

Unless otherwise stated, the parameters for the reported experiment were set
as follows: The experiment was conducted with $10,000$ nodes, generating a
workload of 20 transactions per second, with each transaction being 250 bytes
in size. The transactions were injected into our system based on a realistic
dataset of Ethereum transactions (Pierro and Rocha, 2019). Each experiment was
repeated 10 times, and the average result of these runs is reported.

We constructed a connected topology where each node had eight outgoing
connections and up to 125 incoming connections, in line with the default
Bitcoin parameters. Every node attempted to reconcile with three random
neighbors every second. The request timeout was set to 1 second. If a request
was not fulfilled within this time, it was resent three times, after which the
node was suspected of being faulty. The Minisketch size was set to 1,000
bytes, sufficient to reconcile a set difference of up to 100 transactions,
allowing the Minisketch to fit into a single UDP packet. If reconciliation
failed, all transactions were divided into two subsets, and the process was
repeated with two sketches. The size of Bloom-Clocks was fixed at 32 cells
(i.e., 68 bytes in total).

###  6.2. Resilience

Figure 6. Time necessary to suspect or expose a faulty miner depending on the
proportion of colluding censoring miners in the system.

We assess the impact of colluding censoring miners on the network,
specifically focusing on their effect on the convergence of correct nodes. In
this scenario, malicious miners attempt to prevent correct nodes from learning
about transactions, commitments, exposure, and suspicion messages. All
malicious miners are assumed to be interconnected. For these experiments, we
ensure that the correct nodes remain connected via some path in the network by
initially running an unbiased sampling algorithm (Bortnikov et al., 2009;
Auvolat et al., 2021).

Fig. 6 illustrates the time required for all correct nodes to converge,
depending on the number of faulty nodes in the network. The presence of faulty
nodes marginally increases the time needed for all correct nodes to learn
about the exposure message, extending it to 6-7 seconds after the first miner
detects and creates the message.

We also demonstrate how our system can detect faulty nodes that ignore
requests. We report the time until every correct node suspects all faulty
nodes (Fig. 6, ‘Suspicion’). As expected, the time until all faulty nodes are
suspected is longer than the time required for nodes to discover an exposure
message, as the nodes need to submit a request and wait for it to timeout.

###  6.3. Transaction Latency

We report the time necessary for miners to discover a transaction and include
it in their mempool. The latency distribution is reported in Fig. 7. It
appears that all nodes learn about the transaction after contacting 5 to 6
nodes. On average, a transaction is discovered by a node in 1.14 s.

Figure 7. Distribution of the time (s) required for a miner to insert a
transaction into its mempool.

To demonstrate the effects of our new policies on block building, i.e.,
selecting transactions in order, we simulate a block creation process at
randomly selected miners with an average block time of 12 s, which is the
block time in Ethereum. We report the average time it takes for a transaction
to be included in a block in Fig.8. We compare the policy for block creation
described in Section 4.3 (‘Natural’ ordering) with the policy that is
currently widely used in public blockchains, i.e., creating a block with the
highest-fee transactions of the mempool (referred to as Highest Fee’).

Figure 8. (Left) Average time for a transaction to be included in a block for
the vanilla algorithm used in Ethereum and for LØ (i.e., ’Natural’ ordering),
and (Right) time for a transaction to be included in a block with LØ depending
on the system’s size.

The average transaction latency for the ’Natural’ ordering is 3 seconds, while
it is around 7-8 seconds for the ’Highest Fee’ strategy. Furthermore, we
observe that the ’Highest Fee’ strategy exhibits a wide spread along the axes,
with many low-fee transactions experiencing very high latency. LØ’s orders
transactions according to the order with which they have been received by
miners, which leads to transactions being processed sequentially and increases
fairness.

###  6.4. Protocol Overhead

#### Bandwidth

We benchmark our protocol against two baseline protocols: ’Flood’ and
’PeerReview’. ’Flood’ is a traditional mempool exchange protocol where miners
initially send a ’Mempool’ message containing a list of hashes of the
transactions currently in their mempool. The receiving miner compares these
hashes against its known transaction IDs and requests any missing
transactions.

We also compare LØ to ’PeerReview’, a generic accountability protocol that
could be used to monitor censorship attempts by miners (Haeberlen et al.,
2007). Every miner maintains an additional log for each received message. For
each miner, we assign 8 witnesses. Periodically, each miner fetches the log
from the miners and checks for any injection (commission) or censorship
(omission).

The comparison is reported in Fig. 9. Note that we omit the bandwidth overhead
for sharing transactions, as it is the same for all three protocols. Our
protocol is the most bandwidth-efficient compared to the other two protocols,
incurring 20 times less bandwidth overhead than PeerReview.

Figure 9. Bandwidth overhead measured in KB per minute.

#### Memory and CPU Overhead

The overhead for encoding and decoding Minisketch scales linearly with the
size of the set difference (Gong et al., 2020). Minisketch computes a set
difference with $1,000$ items in 10 seconds. To optimize the usage of the
sketch, we hash-partition the mempool space into subsets, as described in
(Gong et al., 2020). Each time reconciliation fails, the node divides the
mempool in half and sends an additional Minisketch for each partition. As a
result of this optimization, we encode and decode all sketches required for a
set difference of $1,000$ items in less than 100 ms. We report the average
number of sketch reconciliations per minute per node depending on the workload
in Fig. 10.

Figure 10. Average number of reconciliations per minute depending on the
workload (new transactions per minute).

LØ only requires a small additional memory overhead to store the commitments
of all its neighbors. The size of the commitment depends on the workload. For
example, for a workload of 120 transactions per minute, the commitment size is
1.17 KB, while for a workload of 24,000 transactions per minute, the total
size of commitments can reach up to 9.36 KB. Even if the miner stores the
commitments of all 10,000 nodes, it would only require 87 MB.

##  7\. Related Work

The problem of MEV has attracted a considerable amount of research (Qin et
al., 2022; Zhou et al., 2022; Yang et al., 2022). Different MEV mitigation
mechanisms can be categorized according to implementation at different layers:
_application, consensus, base_.

###  7.1. MEV Mitigation at the Application Layer

Decentralized Exchanges aggregators such as Cowswap implement Batch Auctions
where orders are placed off-chain and not immediately executed, but rather,
collected and aggregated to be settled in batches (cow, [n. d.]).The
applications of this approach is tied to a specific application, and thus
limited to specific types of MEV attacks (front running and sandwich).

A2MM is a DEX design that atomically performs optimal routing and arbitrage
among the considered AMM, minimizing subsequent arbitrage transactions (Zhou
et al., 2021).

###  7.2. MEV Mitigation at the Consensus Layer

Proposer-builder separation (PBS) is a proposal aiming at MEV minimization
(Buterin, 2021).The latest iteration of this mechanism, MEV-Boost, is
implemented as a middleware. It enables private communication channels between
clients creating new transactions and validating nodes. However, this approach
has significant trust assumptions, such as relays not reordering or censoring
transactions, which empirically do not hold (Yang et al., 2022).

Pre-ordering solutions aim to separate transaction ordering from execution to
ensure ’fair’ ordering. The Helix consensus protocol (Yakira et al., 2021)
guarantees random selection and ordering of transactions in blocks, relying on
a randomness beacon within the consensus protocol. Aequitas (Kelkar et al.,
2020) provides guarantees on transaction ordering within a block, but assumes
a permissioned environment and introduces significant communication overhead.
Pompe (Zhang et al., 2020) is a Byzantine ordered consensus (BOC) protocol
that outputs a transaction $t$ and a sequence number $s$ for ordering $t$.
Wendy (Kursawe, 2020, 2021) describes ordering protocols for permissioned
systems. Enforcing relative order requires building a dependency graph to
prevent transactions from being included in a block before their dependencies
(Kelkar et al., 2020, 2021; Cachin et al., 2022). Enforcing fair-ordering is
more resource-intensive than enforcing our accountability properties and not
practical in a permissionless setting.

Heimbach and Wattenhoffer propose encrypting transaction content, ordering it,
and revealing its content only after it has been ordered (Heimbach and
Wattenhofer, 2022). This approach is implemented by Fino, which integrates MEV
protection into a BFT protocol in the partial synchrony model with a DAG
transport protocol (Malkhi and Szalachowski, 2022). Lyra (Zarbafian and
Gramoli, 2023), a Byzantine ordered consensus protocol, also uses a commit-
reveal scheme and relies on Verifiable Secret Sharing (VSS). The encrypt-
commit-reveal scheme is more resource-intensive than our accountable approach
and requires additional trust assumptions to ensure that encrypted
transactions are always revealed.

###  7.3. MEV Mitigation at the Base Layer

Secret Mempools hide the content of a transaction so that it cannot be
censored, reordered, etc. F3B is a generic approach for online transaction
encryption based on a commit-and-reveal architecture (Zhang et al., 2022).
Ferveo is a protocol for Mempool Privacy on BFT consensus blockchains (Bebel
and Ojha, 2022). Both of these solutions assume permissioned settings.

ZeroMEV is an existing MEV mitigation solution implemented on the base layer
(pmcgoohan, [n. d.]). This solution is Ethereum-specific and implemented on
the basis of Geth software fork as a validator execution client. It orders
transactions based on timestamps with local FIFO order. However, this solution
does not provide any accountability and requires strong trust assumption as it
relies on the altruism of a validator.

##  8\. Conclusion

We introduced LØ, an accountable base layer for permissionless blockchains. It
is consensus-protocol agnostic and provides detection guarantees for various
MEV attacks. LØ mandates that both correct and faulty miners log all received
transactions into a secure mempool data structure and exchange and record
commitments on their mempool content. Any inconsistency, such as transaction
withholding or equivocation, is exposed during a mempool reconciliation
process with a correct miner. To ensure the exposure of faulty miners, LØ
simply requires correct miners to be interconnected through a network path.

We outlined the transaction manipulation attacks associated with MEV that
miners might execute and mapped different attack types to the relevant stages
of a transaction’s lifecycle within the protocol. Our performance evaluation
demonstrates the practicality of LØ. It is bandwidth and memory efficient,
using only 10 MB with 10,000 miners and a workload of 20 transactions per
second. Moreover, it is at least four times more bandwidth efficient than
classical flooding-based mempool exchanges and processes transactions with
higher fairness.

## References

  * (1)
  * cow ([n. d.]) [n. d.].  Cowswap.  https://cowswap.exchange.
  * fla ([n. d.]) [n. d.].  Flashbots Blockspace Auction.  https://docs.flashbots.net/flashbots-auction/overview.
  * Arakala et al. (2007) Arathi Arakala, Jason Jeffers, and Kathy J Horadam. 2007\.  Fuzzy extractors for minutiae-based fingerprint authentication. In _International conference on biometrics_. Springer, 760–769.
  * Auvolat et al. (2021) Alex Auvolat, Yérom-David Bromberg, Davide Frey, and François Taïani. 2021\.  BASALT: A rock-solid foundation for epidemic consensus algorithms in very large, very open networks.  _arXiv preprint arXiv:2102.04063_ (2021).
  * Bal et al. (2016) Henri Bal, Dick Epema, Cees de Laat, Rob van Nieuwpoort, John Romein, Frank Seinstra, Cees Snoek, and Harry Wijshoff. 2016\.  A medium-scale distributed system for computer science research: Infrastructure for the long term.  _Computer_ 49, 5 (2016), 54–63.
  * Bebel and Ojha (2022) Joseph Bebel and Dev Ojha. 2022.  Ferveo: Threshold Decryption for Mempool Privacy in BFT networks.  Cryptology ePrint Archive, Paper 2022/898.  https://eprint.iacr.org/2022/898 https://eprint.iacr.org/2022/898.
  * Bortnikov et al. (2009) Edward Bortnikov et al. 2009\.  Brahms: Byzantine resilient random membership sampling.  _Computer Networks_ 53, 13 (2009), 2340–2359.
  * Buterin (2021) Vitalik Buterin. 2021\.  _State of research: increasing censorship resistance of transactions under proposer/builder separation (PBS)_.
  * Buterin and Griffith (2017) Vitalik Buterin and Virgil Griffith. 2017.  Casper the friendly finality gadget.  _arXiv:1710.09437_ (2017).
  * Cachin et al. (2022) Christian Cachin, Jovana Mićić, Nathalie Steinhauer, and Luca Zanolini. 2022.  Quick order fairness. In _Financial Cryptography and Data Security: 26th International Conference, FC 2022, Grenada, May 2–6, 2022, Revised Selected Papers_. Springer, 316–333.
  * Civit et al. (2021) Pierre Civit, Seth Gilbert, and Vincent Gramoli. 2021\.  Polygraph: Accountable byzantine agreement. In _ICDCS_. IEEE, 403–413.
  * Daian et al. (2019) Philip Daian, Steven Goldfeder, Tyler Kell, Yunqi Li, Xueyuan Zhao, Iddo Bentov, Lorenz Breidenbach, and Ari Juels. 2019\.  Flash Boys 2.0: Frontrunning, Transaction Reordering, and Consensus Instability in Decentralized Exchanges.  _arXiv preprint arXiv:1904.05234_ (2019).
  * Eppstein et al. (2011) David Eppstein, Michael T Goodrich, Frank Uyeda, and George Varghese. 2011.  What’s the difference? Efficient set reconciliation without prior context.  _ACM SIGCOMM CCR_ 41, 4 (2011), 218–229.
  * Eyal and Sirer (2018) Ittay Eyal and Emin Gün Sirer. 2018.  Majority is not enough: Bitcoin mining is vulnerable.  _Commun. ACM_ 61, 7 (2018), 95–102.
  * Gervais et al. (2015) Arthur Gervais, Hubert Ritzdorf, Ghassan O. Karame, and Srdjan Capkun. 2015.  Tampering with the Delivery of Blocks and Transactions in Bitcoin. In _CCS_. ACM, Denver Colorado USA, 692–705.  https://doi.org/10.1145/2810103.2813655
  * Gong et al. (2020) Long Gong et al. 2020\.  Space-and computationally-efficient set reconciliation via parity bitmap sketch (PBS).  _arXiv preprint arXiv:2007.14569_ (2020).
  * Haeberlen et al. (2007) Andreas Haeberlen et al. 2007\.  PeerReview: Practical accountability for distributed systems.  _ACM SIGOPS operating systems review_ 41, 6 (2007), 175–188.
  * Heimbach and Wattenhofer (2022) Lioba Heimbach and Roger Wattenhofer. 2022.  SoK: Preventing Transaction Reordering Manipulations in Decentralized Finance.  _arXiv preprint arXiv:2203.11520_ (2022).
  * Kelkar et al. (2021) Mahimna Kelkar, Soubhik Deb, Sishan Long, Ari Juels, and Sreeram Kannan. 2021.  Themis: Fast, strong order-fairness in byzantine consensus.  _Cryptology ePrint Archive_ (2021).
  * Kelkar et al. (2020) Mahimna Kelkar, Fan Zhang, Steven Goldfeder, and Ari Juels. 2020.  Order-Fairness for Byzantine Consensus.  In _CRYPTO_. Vol. 12172. Springer International Publishing, Cham.  https://doi.org/10.1007/978-3-030-56877-1_16
  * Kursawe (2020) Klaus Kursawe. 2020\.  Wendy, the good little fairness widget: Achieving order fairness for blockchains. In _Proceedings of the 2nd ACM Conference on Advances in Financial Technologies_. 25–36.
  * Kursawe (2021) Klaus Kursawe. 2021\.  Wendy grows up: More order fairness. In _Financial Cryptography and Data Security. FC 2021 International Workshops: CoDecFin, DeFi, VOTING, and WTSC, Virtual Event, March 5, 2021, Revised Selected Papers 25_. Springer, 191–196.
  * Malkhi and Szalachowski (2022) Dahlia Malkhi and Pawel Szalachowski. 2022.  Maximal Extractable Value (MEV) Protection on a DAG.  _arXiv:2208.00940_ (2022).
  * Mazorra et al. (2022) Bruno Mazorra, Michael Reynolds, and Vanesa Daza. 2022\.  Price of MEV: Towards a Game Theoretical Approach to MEV. In _ACM DeFi_. ACM, Los Angeles CA USA, 15–22.  https://doi.org/10.1145/3560832.3563433
  * Naumenko et al. (2019) Gleb Naumenko, Gregory Maxwell, Pieter Wuille, Alexandra Fedorova, and Ivan Beschastnikh. 2019\.  Bandwidth-efficient transaction relay for bitcoin.  _arXiv:1905.10518_ (2019).
  * Pierro and Rocha (2019) Giuseppe Antonio Pierro and Henrique Rocha. 2019.  The influence factors on ethereum transaction fees. In _2019 IEEE/ACM 2nd International Workshop on Emerging Trends in Software Engineering for Blockchain (WETSEB)_. IEEE, 24–31.
  * Piet et al. (2022) Julien Piet, Jaiden Fairoze, and Nicholas Weaver. 2022\.  Extracting godl [sic] from the salt mines: Ethereum miners extracting value.  _arXiv preprint arXiv:2203.15930_ (2022).
  * pmcgoohan ([n. d.]) pmcgoohan. [n. d.].  zeromev-geth.  https://github.com/zeromev/zeromev-geth/blob/master/README.md.  Accessed: 2023-01-12.
  * Qin et al. (2022) Kaihua Qin, Liyi Zhou, and Arthur Gervais. 2022.  Quantifying Blockchain Extractable Value: How dark is the forest?. In _SP_. IEEE, San Francisco, CA, USA, 198–214.  https://doi.org/10.1109/SP46214.2022.9833734
  * Ramabaja (2019) Lum Ramabaja. 2019\.  The bloom clock.  _arXiv preprint arXiv:1905.13064_ (2019).
  * Sheng et al. (2021) Peiyao Sheng, Gerui Wang, Kartik Nayak, Sreeram Kannan, and Pramod Viswanath. 2021.  BFT protocol forensics. In _CCS_. 1722–1743.
  * Van Renesse et al. (2008) Robbert Van Renesse, Dan Dumitriu, Valient Gough, and Chris Thomas. 2008.  Efficient reconciliation and flow control for anti-entropy protocols. In _LADIS_. 1–7.
  * Wahrstätter et al. (2023) Anton Wahrstätter, Liyi Zhou, Kaihua Qin, Davor Svetinovic, and Arthur Gervais. 2023.  Time to Bribe: Measuring Block Construction Market.  arXiv:2305.16468 [cs.NI]
  * Wang et al. (2021) Taotao Wang et al. 2021\.  Ethna: Analyzing the Underlying Peer-to-Peer Network of Ethereum Blockchain.  _IEEE TNSE_ 8, 3 (2021), 2131–2146.  https://doi.org/10.1109/TNSE.2021.3078181
  * WonderNetwork ([n. d.]) WonderNetwork. [n. d.].  Global Ping Statistics.  https://wondernetwork.com/pings.  Accessed: 2023-01-12.
  * Xu et al. (2023) Jiahua Xu, Krzysztof Paruch, Simon Cousaert, and Yebo Feng. 2023.  Sok: Decentralized exchanges (dex) with automated market maker (amm) protocols.  _Comput. Surveys_ 55, 11 (2023), 1–50.
  * Yakira et al. (2021) David Yakira et al. 2021\.  Helix: A Fair Blockchain Consensus Protocol Resistant to Ordering Manipulation.  _IEEE TNSM_ 18, 2 (2021), 1584–1597.  https://doi.org/10.1109/TNSM.2021.3052038
  * Yang et al. (2022) Sen Yang, Fan Zhang, Ken Huang, Xi Chen, Youwei Yang, and Feng Zhu. 2022\.  SoK: MEV Countermeasures: Theory and Practice.  _arXiv:2212.05111_ (2022).
  * Yu et al. (2019) Jiangshan Yu, David Kozhaya, Jeremie Decouchant, and Paulo Esteves-Verissimo. 2019.  Repucoin: Your reputation is your power.  _IEEE Trans. Comput._ 68, 8 (2019), 1225–1237.
  * Zarbafian and Gramoli (2023) Pouriya Zarbafian and Vincent Gramoli. 2023.  Lyra: Fast and Scalable Resilience to Reordering Attacks in Blockchains.  (2023).
  * Zhang et al. (2022) Haoqian Zhang et al. 2022\.  Flash freezing flash boys: Countering blockchain front-running. In _ICDCSW_. IEEE, 90–95.
  * Zhang et al. (2020) Yunhao Zhang, Srinath Setty, Qi Chen, Lidong Zhou, and Lorenzo Alvisi. 2020.  Byzantine ordered consensus without byzantine oligarchy. In _Proceedings of the 14th USENIX Conference on Operating Systems Design and Implementation_. 633–649.
  * Zhou et al. (2022) Liyi Zhou et al. 2022\.  SoK: Decentralized Finance (DeFi) Attacks.  _Cryptology ePrint Archive_ (2022).
  * Zhou et al. (2021) Liyi Zhou, Kaihua Qin, and Arthur Gervais. 2021.  A2mm: Mitigating frontrunning, transaction reordering and consensus instability in decentralized exchanges.  _arXiv preprint arXiv:2106.07371v2_ (2021).


# Zero-Shot Policy Transferability for the Control of a Scale Autonomous
Vehicle

Harry Zhang1, Stefan Caldararu2, Sriram Ashokkumar3, Ishaan Mahajan2,
Aaron Young4, Alexis Ruiz1, Huzaifa Unjhawala1, Luning Bakke5 and Dan Negrut6
1PhD student with the Department of Mechanical Engineering, University of
Wisconsin - Madison, 1513 University Ave, Madison, WI, USA
<EMAIL_ADDRESS>Student with the Department of Computer
Science, University of Wisconsin - Madison, 1210 W Dayton St, Madison, WI, USA
<EMAIL_ADDRESS>Student with the Department of Computer Science,
University of Wisconsin - Madison, 1210 W Dayton St, Madison, WI, USA 4PhD
Student with the Department of Mechanical Engieering, Massachusetts Institute
of Technology, 33 Massachusetts Ave, Cambridge, MA, USA5Postdoc with the
Department of Mechanical Engineering, University of Wisconsin - Madison, 1513
University Ave, Madison, WI, USA6Professor with the Department of Mechanical
Engineering, University of Wisconsin - Madison, 1513 University Ave, Madison,
WI, USA

###### Abstract

We report on a study that employs an in-house developed simulation
infrastructure to accomplish zero shot policy transferability for a control
policy associated with a scale autonomous vehicle. We focus on implementing
policies that require no real world data to be trained (Zero-Shot Transfer),
and are developed in-house as opposed to being validated by previous works. We
do this by implementing a Neural Network (NN) controller that is trained only
on a family of circular reference trajectories. The sensors used are RTK-GPS
and IMU, the latter for providing heading. The NN controller is trained using
either a human driver (via human in the loop simulation), or a Model
Predictive Control (MPC) strategy. We demonstrate these two approaches in
conjunction with two operation scenarios: the vehicle follows a waypoint-
defined trajectory at constant speed; and the vehicle follows a speed profile
that changes along the vehicle’s waypoint-defined trajectory. The primary
contribution of this work is the demonstration of Zero-Shot Transfer in
conjunction with a novel feed-forward NN controller trained using a general
purpose, in-house developed simulation platform.

##  I INTRODUCTION

###  I-A Motivation

Simulation can be a powerful tool for designing better robots and autonomous
vehicles as it can reduce design costs, accelerate the design cycle, and
enable the testing of a larger pool of candidate designs in a diverse set of
scenarios difficult to reproduce in reality [1]. The idea of using simulation
in robot design is hindered by the so called simulation-to-reality, or
sim2real, gap [2]: in many cases, an algorithm that performs well in
simulation may display poor performance in reality due to hard to model
aspects present in the real system [3], e.g., slackness in the steering
mechanism, delays in actuation, complex sensor behavior. When Machine Learning
(ML) comes into play in designing control policies, ZST [4] is even more
elusive since one has to make do exclusively with synthetic data. Past
contributions that focused on ZST either came short of demonstrating
performance in the real world [5], or required a mixture of simulated and real
data, e.g. [6, 7].

###  I-B Contribution

We outline a general purpose approach that uses our Autonomy Research Testbed
(ART) platform [8] to synthesize an ML-based controller in simulation and
subsequently demonstrate it on a scale vehicle, thus achieving ZST. Our
contributions are threefold. (i) We propose the use of a physics-based high
fidelity simulator to synthesize control policies without resorting to domain
randomization or domain adaptation to achieve ZST. (ii) We do not resort to
off-the-shelf proven algorithms. Rather, we train a NN via imitation learning
on a low diversity dataset obtained by driving the vehicle along a small
family of circles of different radii. The model is trained to imitate either a
human driver or a Model Predictive Control (MPC) algorithm. Producing training
data in simulation and training the NN model takes minutes. (iii) We
demonstrate that our simulator, called Chrono [9, 10], used in conjunction
with ART can support autonomy stack development in simulation with good
sim2real transferability traits.

###  I-C Related Work

Our approach is similar to [11], except that perception is carried out
differently (GPS and IMU as opposed to camera), and we draw exclusively on
simulated data. In [5], the authors train an all-terrain-vehicle in simulation
to drive off-road while avoiding obstacles but their policy is only
demonstrated in simulation. In [12], the authors focus on automatic test
generation for AVs and propose “robustness values” for their Autonomy Stack
(A-Stack), but do not provide evidence for the translation of this robustness
value into real world results. AutoVRL, a platform similar to the ART one
discussed herein, is presented in [13], but its authors do not demonstrate
real-world operation of their A-Stack. Unlike these contributions that only
demonstrate performance in simulation, a body of literature shows performance
in reality by focusing on combining simulation and real-world data. Most of
these relate to autonomous agents that use camera and LiDAR sensors for end-
to-end solutions in which an ML model directly takes sensor inputs while it
outputs control commands. In [12, 14] the perception training is done purely
on real world datasets, i.e., KITTI [15] and YCB [16], respectively. Many
works focus on Domain Translation (DT) where a separate ML module is tasked
with changing the appearance of sensor outputs. For instance, in [17] the
authors use a Generative Adversarial Network (GAN) to learn a mapping function
from simulated images to a potential real world counterpart, highlighting
their use of unlabeled reality data. The A-Stack is then trained on this
enhanced simulation data. Similar to this, the VISTA simulator [7] uses a
data-driven approach to generate sensor data, integrating the process
described above into the simulator. In [18], the authors do the inverse of the
operation described above. They train their A-Stack in simulation, and then
generate ”VR-Goggles” for their vehicle. When driving in reality, the sensor
data is first processed by the VR-Goggles to look more like simulated data,
and then passed to the A-Stack. This also requires reality data for training
the goggles. While all of these approaches achieve simulation based A-Stack
training with transfer to reality, they still require preprocessing of real
world data for their testing, stopping short of ZST.

Domain Randomization (DR) has been widely used to impart robustness to a
control policy synthesized in simulation. This is commonly done for robotic-
arm control policies, see, for instance, [19]. In [4], the authors discuss the
effectiveness of different DR techniques. In our work, we choose to not employ
DR for ZST and instead emphasize the role that an accurate simulator and model
can play in accomplishing ZST. Agasint this backdrop, our effort is motivated
by two observations. Firstly, the DR technique often lacks clarity on why it
succeeds or fails. Secondly, DR can serve as a reliable option for enhancing
robustness provided one already achieved ZST with a good simulator and model.

Finally, in this study, we showcase the integration of the Chrono simulation
engine and the ART platform, both of which are being collaboratively developed
with input from this group. Looking beyond Chrono, commonly used simulators
include CARLA [20], Isaac Sim [21], MuJoCo [22], webots [23], Coppelia
Robotics [24], Gazebo [25] and PyBullet [26]. Several of these solutions
highlight photorealism and fast computation times, producing results that are
plausible but not necessarily physically meaningful since they draw on game
engines [27]. This revokes some of the benefits of simulation based training,
as one is no longer guaranteed to be able to exactly replicate physical
scenarios/tests, and may make determining failure causes difficult. Finally,
in addition to embracing a physics-based approach to simulation, one aspect
that sets apart Chrono is its ability to embed humans in the loop and either
allow them to guide the data generation process for training (as done in this
contribution), or synthesize and test autonomy solutions that come into play
in human-robot interaction applications.

##  II BACKGROUND

The multi-physics simulator used used in this study is called Chrono [9]. Two
modules, Chrono::Vehicle [28] and Chrono::Sensor [29], provide high-fidelity,
physics-based vehicle and sensor simulation, respectively, and can be
leveraged for synthesizing control policies. While this work focuses on a
scaled on-road car equipped with GPS and IMU sensors, Chrono allows for the
combination of various wheeled and tracked vehicles, and proprioceptive and
exteroceptive sensor types, e.g., camera, LiDAR [8, 5]. It has good
terramechanics support for off-road mobility fidelity, the user having the
ability to choose several terrain models [30, 31]. Furthermore, the platform
supports human-in-the-loop simulation, and the interaction of multiple
autonomous agents, whether in intricate traffic scenarios or convoy operations
utilizing Synchrono [32, 33]. ART/ATK provides a ROS 2 framework that
leverages the Chrono simulation engine to enable autonomy algorithm synthesis
in simulation followed by demonstration in the real world. A more detailed
description is provided in Sec. III-A

##  III PRELIMINARIES

###  III-A ART/ATK and Chrono

The control synthesis takes place in simulation in line with ZST expectations.
The Chrono simulator is used to produce the time evolution of the scale
vehicle. The ART in “ART/ATK” provides a ROS2-based basic autonomy stack. It
is implemented in Python and is Docker-containerized so that the same autonomy
stack, running on the same processor (NVIDIA Jetson AGX card) is used both in
simulation and the real world. The autonomy stack is deployed on the SAV
vehicle (from “scaled Autonomous Vehicle”), which has in dtSAV a Chrono
digital twin. Finally, the ATK component is a utility that produces the Docker
container infrastructure required to accommodate the ART autonomy stack, be it
in simulation or in real world testing [8]. An IMU sensor provides heading
information, and an RTK GPS delivers centimeter-scale accuracy for
localization. An Extended Kalman Filter (EKF) is used for velocity estimation,
utilizing the 4-DOF model described in sec. III-B. In simulation, Chrono
provides dtSAV with ground truth information for the position and heading; the
same EKF is used for velocity estimation.

###  III-B 4-DOF VEHICLE MODEL AND ERROR STATE

State estimation and MPC, the latter used in generating training data, call
for a simple vehicle model. This model is not the Chrono dtSAV vehicle (which
is highly nonlinear and complex), but a low fidelity replica that captures
well enough dtSAV’s dynamics. In other words, when estimating state in
simulation or producing a command via MPC, one uses a Chrono simulation,
inside which we run a second simulation of the 4-DOF vehicle described in this
subsection. The states of the 4-DOF vehicle model are
$\mathbf{q}=[x,y,\theta,v]^{T}$, with $x$ and $y$ representing the position in
the Cartesian coordinates, respectively, heading angle $\theta$, and
longitudinal velocity $v$. The commands $\mathbf{u}$ consist of a steering
value $\delta$ in the range of $[-1,1]$, and a throttle input $\alpha$ in the
range of $[0,1]$. The dynamics of the 4-DOF vehicle model is captured by the
following differential equations:

$\displaystyle cos(\theta)\cdot v,$ (1a) $\displaystyle sin(\theta)\cdot v,$
(1b) $\displaystyle{v\cdot tan(\beta\delta)}/{l},$ (1c)
$\displaystyle{T(\alpha,v)\cdot\gamma}R_{w}/{I_{w}}.$ (1d)

Equations (1a), (1b), and (1c) describe a simplified bicycle model [34], where
$\beta$ maps the steering command $\delta$ to the wheel steering angle, and
$l$ is the wheel base of the vehicle. Assuming that the wheel has no slip, Eq.
(1d) approximates the longitudinal acceleration $\dot{v}$ based on motor
torque $T(\alpha,v)$, gear ratio $\gamma$, and wheel radius and moment of
inertia, $R_{w}$ and $I_{w}$. See [35] for more details.

Figure 1: Error state relative to target reference trajectory.

As illustrated in Fig. 1, given a reference trajectory, the error state,
$\mathbf{e}=[e_{1},e_{2},e_{3},e_{4}]^{T}$, with respect to the reference one,
$\mathbf{q}_{r}=[x_{r},y_{r},\theta_{r},v_{r}]^{T}$, can be computed using Eq.
(2) [36].

$\mathbf{e}=\begin{pmatrix}\cos\theta&\sin\theta&0&0\\\
-\sin\theta&\cos\theta&0&0\\\ 0&0&1&0\\\
0&0&0&1\end{pmatrix}\begin{pmatrix}x_{r}-x\\\ y_{r}-y\\\ \theta_{r}-\theta\\\
v_{r}-v\end{pmatrix}.\;$ (2)

###  III-C MPC DETAILS

The MPC solution embraced is described in [35]. This control policy has
already been tuned in simulation and tested in reality, providing insight into
sim2real transferability [3]. Therein, the salient conclusion was that the MPC
solution was not robust, which is not an issue since it is used only to
generate training data for the NN controller. The MPC is posed as

$e_{t+1}=A_{t}\cdot e_{t}+B_{t}\cdot u_{t}$ (3)

$\displaystyle J_{t}^{*}(e_{t})$
$\displaystyle=\min_{u_{k}}\;\;e_{N}^{T}Qe_{N}+\sum_{k=0}^{N-1}e_{k}^{T}Qe_{k}$
(4) $\displaystyle+(u_{k}-u_{r})^{T}R(u_{k}-u_{r})\;.$

In Eq. (3), we linearized the error dynamics, using Eqs. (1) and (2) [35].
Equation (4) describes the optimization problem used to generate the next
optimal command. For more details, please see [3, 37].

##  IV METHOD

###  IV-A TRAINING DATA

Figure 2: Training Process Demonstration: upper half is the pipeline for
collecting HIL (manual control) training data; lower half shows data
collection using MPC.

####  IV-A1 Human-in-the-loop produced training data

This approach is schematically captured in Fig. 2. Since Chrono supports human
in the loop (HIL) simulation, a human drives dtSAV in the virtual world
(manual driving) to collect data that registers what the driver does when
dtSAV strays away from a given trajectory. We record the error state and
corresponding control commands at each time step of the simulation. Seven
reference trajectories are used one at a time for the training process. They
are circular paths with radius 2m, 5m, 25m, both clockwise and counter-
clockwise, plus a 30m straight line path, which can be thought of as a circle
with infinite radius. For the multispeed control, we used seven trajectories
with the same geometric shapes but different target velocities – half of the
course had a 1 m/s velocity prescribed for the vehicle, the other half had a 2
m/s reference velocity, with a transition velocity in between. The data helped
the NN model how changes in speed elicit changes in the throttle position.
Collecting training data in simulation was both simple and fast (took minutes
to generate).

####  IV-A2 MPC Training

An alternative to having a human drive dtSAV in simulation is to use an
existing MPC controller, see Sec. III-C, and record the input commands issued
by the MPC while it works to maintain a predefined trajectory. The MPC issued
commands to dtSAV to make it follow the same reference trajectories used in
the HIL data collection. The training data contains the error state and
corresponding MPC command issued in each time step. The reason why our MPC
policy was not useful in reality was that it was not robust – SAV in reality
did much worse than dtSAV in simulation, a prime manifestation of the sim2real
gap.

###  IV-B IMITATION LEARNING BASED CONTROLLER

Figure 3: Feed Forward Layers Setup.

We employ a feed forward Neural Network (NN) that upon training will drive
dtSAV and subsequently SAV, thus accomplishing ZST. Figure 3 depicts the two-
hidden-layer NN that engages in supervised learning. Training data is
generated via HIL only, or via MPC only, see Sec. IV-A. For NN training, the
input data $\mathbf{E}\in\mathbb{R}^{4\times n}$ is the set of error states
$\mathbf{e}\in\mathbb{R}^{4\times 1}$. This data
$\mathbf{U}\in\mathbb{R}^{2\times n}$ is matched with the control commands
$\mathbf{u}\in\mathbb{R}^{2\times 1}$. The NN is trained to produce a mapping
between the error state and control command,
$\mathbf{f}:\mathbf{e}\rightarrow\mathbf{u}$. The NN training and inference is
carried out in Keras Core [38], using PyTorch as a backend [39]. The training
converges fast since the input and output spaces are small, as are the NN’s
depth and width.

##  V EXPERIMENTAL RESULTS

###  V-A EXPERIMENTAL SETUP

Figure 4: Experiment Setup: NN was trained using dtSAV-generated data and
subsequently tested in a parking lot using SAV. The red dashed line in the
right-most image represents the parking lot reference trajectory.

This section reports on experimental work done to assess the extent to which
the control policy synthesized in simulation transferred to the real world. We
established in simulation four NN policies: one trained by using a human
driver, the other one using MPC-produced data; and, for each of these two
scenarios we had two sub-cases: the velocity along the course was kept
constant, or it changed based on the location of the SAV vehicle along its
trajectory. The assessment of the four NNs took place on the top of a parking
lot. SAV was given waypoints, and the NN controller used the IMU heading and
RTK-GPS information to pass through the waypoints while following the
prescribed speed regimen. The waypoints selection was mindful of the topology
of the parking lot, and yielded a path that was roughly rectangular with a
width by length of approximately 34 $\times$ 72 []m, see Fig. 4. There were
sinusoidal portions and regions where the speed changed along the way. For
more experiment details, see uploaded movie.

(a)

(b)

Figure 5: Results for simulation and reality testing: (a) NN controller
trained by MPC; (b) NN controller trained by manual driving.

###  V-B EXPERIMENTAL RESULTS

####  V-B1 Constant Velocity Tracking

The reference trajectory is first followed using constant velocity along the
entire path. The loop around the parking lot shown in Fig. 4 has a sinusoidal
segment along one width, and an arc on the opposite one. Sample simulation and
reality results are displayed in Fig. 5. The control profiles for throttle and
steering are shown in Fig. 6.

(a)

(b)

Figure 6: Control Profiles comparing SAV and dtSAV: (a) NN controller trained
via MPC; (b) NN trained via HIL.

We ran five additional tests for each controller in each scenario. For each
GPS output reading, we found the closest point on the reference trajectory,
and computed the distance between the vehicle and this reference point. We
then averaged these across the five tests for each reference point, and
displayed them as a plot with respect to the reference location used. These
absolute errors are shown in Fig. 7.

(a)

(b)

Figure 7: Absolute sime2real errors: (a) NN controller trained by MPC; (b) NN
controller trained by HIL.

####  V-B2 Tracking a Complex Speed Profile

We used the same reference trajectory, but had a speed profile that changed
along the vehicle trajectory: it was 1 m/s around the four corners, and
climbed to 2 m/s in between. Figure 8 displays results for the two NN
controllers. Heat maps show the speed of the vehicle along the trajectory,
both in simulation and reality.

(a)

(b)

(c)

(d)

Figure 8: Simulation vs. Reality Testing, variable-speed case: Fig. 8(a)–SAV
using MPC-trained NN controller; Fig. 8(b)–dtSAV using MPC-trained NN
controller; Fig. 8(c)–SAV using HIL-trained NN controller; Fig. 8(d)–dtSAV
using HIL-trained NN controller.

##  VI DISCUSSION

The results in Fig. 5 indicate that the feed-forward NN used in this study
accomplishes ZST regardless of whether the synthetic training data was
produced via MPC or HIL. The sim2real gap is small as demonstrated in Fig. 7.
A notable difference between simulation and reality can be noted in the
commands issued, see Fig. 6. We hypothesize that is likely due to: a steady
slant of the road for parking lot drainage purposes, which is present in
reality but not in simulation; and, an unavoidable slack in the steering
mechanism (with zero steering command input, the vehicle still tries to steer
in the direction that the terrain is slanted towards). As shown in Fig. 6, for
the straight line portion the reality steering has negative steering values
(to compensate for the tilted road) while in simulation zero steering is
maintained. Another observation from Fig. 6 is that there is a qualitative
difference between the NN trained with HIL data or MPC data. The HIL training
data displays smoother changes for steering commands and prefers to merge back
to the referenced trajectory slowly. Conversely, the MPC-generated training
data has higher transients since it solves an optimization problem that was
not instructed to account for smoothness of the ensuing maneuver. This
explains why the MPC-data trained NN controller follows trajectories more
precisely.

Finally, for the case when the prescribed velocity changes along the
trajectory, dtSAV achieves a wider range of speeds compared to SAV. Likewise,
MPC-data training leads to a more responsive controller than when using HIL
data since the MPC training takes the vehicle’s powertrain model into
consideration. Indeed, results in Fig. 8(b) look sharper than the ones in Fig.
8(d). Correspondingly, when transferring the control policies into reality,
the multi-speeds control is more precise for the controller trained with MPC
(in Fig. 8(a)) than the one trained with HIL data (in Fig. 8(c)).

Given the complexity of real-world environments, expecting exact matches
between simulated and real results is exceedingly difficult to achieve.
However, it is desirable to quantify this gap in safety critical applications
[40], and at a minimum to see traits that manifest in simulation carry over to
the real world. In Figure 8, we illustrate this with multi-speed training: the
HIL driver (while generating training data in the simulation) is unable to
match desired speeds as precisely as the MPC. This trait is learned by the NN
and appears in the real-world scenario where the NN trained on HIL doesn’t
match desired speeds accurately. Additionally, the HIL driver prioritizes
smoother steering inputs, while the MPC prioritizes error mitigation over
smoothness, as evident in the steering control inputs in Fig. 6.

##  VII CONCLUSIONS

Our contributions are threefold. We demonstrated ZST for a scale vehicle using
RTK-GPS and IMU sensor fusion. We established a feed-forward NN controller
trained to imitate a human driver or the behavior of an MPC controller.
Finally, anchored by Chrono and ART/ATK, we established an open source
platform that enables the synthesis of autonomy algorithms in simulation and
their demonstration in reality. The salient strength of the Chrono-ART/ATK
platform is that the same ROS2 ART autonomy stack, running on the same
hardware, is exercised both in simulation and reality. Since Chrono supports
HIL, it enables a driver to operate a digital twin, and the data generated be
subsequently used to synthesize ML-based control policies. Ongoing work
focuses on increasing the determinism of the ART/ATK autonomy stack;
investigating the ZST problem for a rover-like vehicle with four steerable
wheels; and using simulation to synthesize autonomy stacks for ground vehicles
operating on deformable terrains.

## References

  * [1] H. Choi, C. Crump, C. Duriez, A. Elmquist, G. Hager, D. Han, F. Hearl, J. Hodgins, A. Jain, F. Leve, C. Li, F. Meier, D. Negrut, L. Righetti, A. Rodriguez, J. Tan, and J. Trinkle, “On the use of simulation in robotics: Opportunities, challenges, and suggestions for moving forward,” _Proceedings of the National Academy of Sciences_ , vol. 118, no. 1, 2021\. [Online]. Available: https://www.pnas.org/content/118/1/e1907856118
  * [2] N. Jakobi, P. Husbands, and I. Harvey, “Noise and the reality gap: The use of simulation in evolutionary robotics,” in _European Conference on Artificial Life_. Springer, 1995, pp. 704–720.
  * [3] H. Zhang, S. Caldararu, I. Mahajan, S. Chatterjee, T. Hansen, A. Dashora, S. Ashokkumar, L. Fang, X. Xu, S. He, and D. Negrut, “Using simulation to design an mpc policy for field navigation using gps sensing,” 2023.
  * [4] E. Valassakis, Z. Ding, and E. Johns, “Crossing the gap: A deep dive into zero-shot sim-to-real transfer for dynamics,” 2020.
  * [5] S. Benatti, A. Young, A. Elmquist, J. Taves, A. Tasora, R. Serban, and D. Negrut, “End-to-end learning for off-road terrain navigation using the chrono open-source simulation platform,” _Multibody System Dynamics_ , vol.  , no. https://doi.org/10.1007/s11044-022-09816-1, 2022. [Online]. Available: https://doi.org/10.1007/s11044-022-09816-1
  * [6] B. Osiński, A. Jakubowski, P. Ziȩcina, P. Miłoś, C. Galias, S. Homoceanu, and H. Michalewski, “Simulation-based reinforcement learning for real-world autonomous driving,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , 2020, pp. 6411–6418.
  * [7] A. Amini, I. Gilitschenski, J. Phillips, J. Moseyko, R. Banerjee, S. Karaman, and D. Rus, “Learning robust control policies for end-to-end autonomous driving from data-driven simulation,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 2, pp. 1143–1150, 2020.
  * [8] A. Elmquist, A. Young, I. Mahajan, K. Fahey, A. Dashora, S. Ashokkumar, S. Caldararu, V. Freire, X. Xu, R. Serban, and D. Negrut, “A software toolkit and hardware platform for investigating and comparing robot autonomy algorithms in simulation and reality,” _arXiv preprint arXiv:2206.06537_ , 2022.
  * [9] A. Tasora, R. Serban, H. Mazhar, A. Pazouki, D. Melanz, J. Fleischmann, M. Taylor, H. Sugiyama, and D. Negrut, “Chrono: An open source multi-physics dynamics engine,” in _High Performance Computing in Science and Engineering – Lecture Notes in Computer Science_ , T. Kozubek, Ed. Springer International Publishing, 2016, pp. 19–49.
  * [10] Project Chrono, “Chrono: An open source framework for the physics-based simulation of dynamic systems,” http://projectchrono.org, 2020, accessed: 2020-03-03.
  * [11] M. Bojarski, D. Del Testa, D. Dworakowski, B. Firner, B. Flepp, P. Goyal, L. D. Jackel, M. Monfort, U. Muller, J. Zhang, X. Zhang, J. Zhao, and K. Zieba, “End to end learning for self-driving cars,” _arXiv preprint arXiv:1604.07316_ , 2016.
  * [12] C. E. Tuncali, G. Fainekos, H. Ito, and J. Kapinski, “Simulation-based adversarial test generation for autonomous vehicles with machine learning components,” in _2018 IEEE Intelligent Vehicles Symposium (IV)_ , 2018, pp. 1555–1562.
  * [13] S. Sivashangaran, A. Khairnar, and A. Eskandarian, “Autovrl: A high fidelity autonomous ground vehicle simulator for sim-to-real deep reinforcement learning,” 2023.
  * [14] K. Ellis, H. Zhang, D. Stoyanov, and D. Kanoulas, “Navigation among movable obstacles with object localization using photorealistic simulation,” in _2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2022, pp. 1711–1716.
  * [15] A. Geiger, P. Lenz, and R. Urtasun, “Are we ready for autonomous driving? the kitti vision benchmark suite,” in _2012 IEEE Conference on Computer Vision and Pattern Recognition_ , 2012, pp. 3354–3361.
  * [16] B. Calli, A. Walsman, A. Singh, S. Srinivasa, P. Abbeel, and A. M. Dollar, “Benchmarking in manipulation research: Using the yale-cmu-berkeley object and model set,” _IEEE Robotics & Automation Magazine_, vol. 22, no. 3, pp. 36–52, 2015.
  * [17] G. J. Stein and N. Roy, “Genesis-rt: Generating synthetic images for training secondary real-world tasks,” 2017.
  * [18] J. Zhang, L. Tai, P. Yun, Y. Xiong, M. Liu, J. Boedecker, and W. Burgard, “Vr-goggles for robots: Real-to-sim domain adaptation for visual control,” 2019\.
  * [19] X. B. Peng, M. Andrychowicz, W. Zaremba, and P. Abbeel, “Sim-to-real transfer of robotic control with dynamics randomization,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_ , 2018, pp. 3803–3810.
  * [20] A. Dosovitskiy, G. Ros, F. Codevilla, A. Lopez, and V. Koltun, “CARLA: An open urban driving simulator,” in _Proceedings of the 1st Annual Conference on Robot Learning_ , 2017, pp. 1–16.
  * [21] J. Liang, V. Makoviychuk, A. Handa, N. Chentanez, M. Macklin, and D. Fox, “Gpu-accelerated robotic simulation for distributed reinforcement learning,” 2018.
  * [22] E. Todorov, T. Erez, and Y. Tassa, “MuJoCo: A physics engine for model-based control,” in _2012 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 2012, pp. 5026–5033.
  * [23] O. Michel, “Cyberbotics ltd. webots: professional mobile robot simulation,” _International Journal of Advanced Robotic Systems_ , vol. 1, no. 1, p. 5, 2004.
  * [24] Coppelis Robotics, “http://www.coppeliarobotics.com/,” 2023.
  * [25] N. P. Koenig and A. Howard, “Design and use paradigms for Gazebo, an open-source multi-robot simulator.” in _2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , vol. 4. Citeseer, 2004, pp. 2149–2154.
  * [26] E. Coumans and Y. Bai, “PyBullet, a Python module for physics simulation for games, robotics and machine learning,” http://pybullet.org, 2016–2019.
  * [27] G. Chance, A. Ghobrial, K. McAreavey, S. Lemaignan, T. Pipe, and K. Eder, “On determinism of game engines used for simulation-based autonomous vehicle verification,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 23, no. 11, pp. 20 538–20 552, 2022.
  * [28] R. Serban, M. Taylor, D. Negrut, and A. Tasora, “Chrono::Vehicle template-based ground vehicle modeling and simulation,” _Intl. J. Veh. Performance_ , vol. 5, no. 1, pp. 18–39, 2019.
  * [29] A. Elmquist and D. Negrut, “Methods and models for simulating autonomous vehicle sensors,” _IEEE Transactions on Intelligent Vehicles_ , vol. 5, pp. 684–692, 2020.
  * [30] A. Tasora, D. Mangoni, D. Negrut, R. Serban, and P. Jayakumar, “Deformable soil with adaptive level of detail for tracked and wheeled vehicles,” _International Journal of Vehicle Performance_ , vol. 5, no. 1, pp. 60–76, 2019.
  * [31] W. Hu, Z. Zhou, S. Chandler, D. Apostolopoulos, K. Kamrin, R. Serban, and D. Negrut, “Traction control design for off-road mobility using an SPH-DAE co-simulation framework,” _Multibody System Dynamics_ , vol. 55, pp. 165–188, 2022.
  * [32] D. Negrut, R. Serban, A. Elmquist, and D. Hatch, “Synchrono: An open-source framework for physics-based simulation of collaborating robots,” in _2018 IEEE International Conference on Simulation, Modeling, and Programming for Autonomous Robots (SIMPAR)_. IEEE, 2018, pp. 101–107.
  * [33] J. Taves, A. Elmquist, A. Young, R. Serban, and D. Negrut, “Synchrono: A scalable, physics-based simulation platform for testing groups of autonomous vehicles and/or robots,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2020, pp. 2251–2256.
  * [34] H. Guo, D. Cao, H. Chen, C. Lv, H. Wang, and S. Yang, “Vehicle dynamic state estimation: State of the art schemes and perspectives,” _IEEE/CAA Journal of Automatica Sinica_ , vol. 5, no. 2, pp. 418–431, 2018.
  * [35] H. Zhang, H. Unjhawala, S. Caldararu, I. Mahajan, L. Bakke, R. Serban, and D. Negrut, “Simplified 4dof bicycle model for robotics applications,” Simulation-Based Engineering Laboratory, University of Wisconsin-Madison, Tech. Rep., 2023, https://sbel.wisc.edu/wp-content/uploads/sites/569/2023/06/TR-2023-06.pdf.
  * [36] G. Klančar and I. Škrjanc, “Tracking-error model-based predictive control for mobile robots in real time,” _Robotics and autonomous systems_ , vol. 55, no. 6, pp. 460–469, 2007.
  * [37] H. Zhang, S. Chatterjee, T. Hansen, S. Caldararu, I. Mahajan, N. Batagoda, L. Fang, R. Serban, and D. Negrut, “Formulating model predictive control (mpc) strategies in conjunction with error dynamics based waypoint-seeking to model robust vehicle control,” Simulation-Based Engineering Laboratory, University of Wisconsin-Madison, Tech. Rep., 2023, https://sbel.wisc.edu/wp-content/uploads/sites/569/2023/03/TR-2023-01.pdf.
  * [38] F. Chollet _et al._ , “Keras,” https://keras.io, 2015.
  * [39] A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. DeVito, Z. Lin, A. Desmaison, L. Antiga, and A. Lerer, “Automatic differentiation in PyTorch,” in _NIPS 2017 Workshop Autodiff_ , 2017, Conference Proceedings.
  * [40] P. Akella, W. Ubellacker, and A. D. Ames, “Safety-critical controller verification via sim2real gap quantification,” in _2023 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2023, pp. 10 539–10 545.