# MOZARD: Multi-Modal Localization for Autonomous Vehicles in Urban Outdoor
Environments

Lukas Schaupp1, Patrick Pfreundschuh3, Mathias Bürki1,2, Cesar Cadena1,
Roland Siegwart1, and Juan Nieto1
1Autonomous Systems Lab, ETH Zürich<EMAIL_ADDRESS>
2Sevensense Robotics AG<EMAIL_ADDRESS>3ETH Zurich,
<EMAIL_ADDRESS>
###### Abstract

Visually poor scenarios are one of the main sources of failure in visual
localization systems in outdoor environments. To address this challenge, we
present MOZARD, a multi-modal localization system for urban outdoor
environments using vision and LiDAR. By extending our preexisting key-point
based visual multi-session local localization approach with the use of
semantic data, an improved localization recall can be achieved across vastly
different appearance conditions. In particular we focus on the use of
curbstone information because of their broad distribution and reliability
within urban environments. We present thorough experimental evaluations on
several driving kilometers in challenging urban outdoor environments, analyze
the recall and accuracy of our localization system and demonstrate in a case
study possible failure cases of each subsystem. We demonstrate that MOZARD is
able to bridge scenarios where our previous work VIZARD fails, hence yielding
an increased recall performance, while a similar localization accuracy of
0.2$m$ is achieved.

##  I Introduction

Due to increasing traffic in urban environments and changing customer demands,
self-driving vehicles are one of the most discussed and promising technologies
in the car and robotics industry. Still no system was presented yet, that
allows to localize robustly under all light, weather and environmental
conditions. However, precise localization is a vital feature for each
autonomous driving task, since a wrong pose estimate may lead to accidents.
Especially in urban environments, safety margins on the position of the car
are small due to crowded traffic and other traffic participants (e.g.
pedestrians, cyclists). Because of multi-path effects or satellite blockage,
GPS sensors cannot be used reliably under those urban conditions. Thus, other
sensors have to be used for localization. For this purpose, mainly LiDARs and
cameras have been used in the last years. Appearance changes in urban
environments challenge visual localization approaches. However, such driving
scenarios contain persistent structures even under those appearance changes.
Curbstones are one such feature. Curbstones are used to protect pedestrians
from cars and to separate the sidewalk from the street. As they delimit the
street, they also offer information of the area where the car is allowed to be
placed in. Detection of their position relative to the car can thus allow to
localize inside the lane. In contrast to other geometrical shapes such as
poles and road markings, curbstone measurements are found more frequently in
urban environments and yield a reliable, continuous lateral constraint for
pose refinement. Due to their shape and their contrasting color with respect
to the pavement in many cases, they can be detected both in camera images as
well as in LiDAR pointclouds.

Figure 1:  We aim at accurately localizing the UP-Drive vehicle in a map of
features extracted from vision and LiDAR data depicted on the right side. Our
proposed algorithm can be separated into two distinct steps. We extract
keypoint-based features from camera and additional 3D geometrical curbstone
information from a semantic vision-LiDAR pipeline. The features extracted from
images of the surround-view camera system (top-left corner) are matched
against $3D$ landmarks in the map while our raw curbstone measurements
(bottom-left corner) are matched to their corresponding landmarks. Inlier
matches, centered on the estimated $6DoF$ pose of the vehicle in the map, are
illustrated as dark yellow lines on the right side. Purple indicates our pre-
generated curbstone map data represented by splines. During runtime we
downsample the nearest splines spatially to match with the current raw
curbstone measurements indicated by the red and green color.

Therefore, our pipeline named MOZARD extends our previous visual localization
system - VIZARD[1] with the use of additional geometrical features from LiDAR
data, for the self-driving cars used in the UP-Drive project111The UP-Drive
project is a research endeavor funded by the European Commission, aiming at
advancing research and development towards fully autonomous cars in urban
environment. See www.up-drive.eu.. In a thorough evaluation of our proposed
localization system using our long-term outdoor dataset collection, we
investigate key performance metrics such as localization accuracy and recall
and demonstrate in a case study possible failure scenarios.

We see the following aspects as the main contributions of this paper:

  * •

A semantic extension of our key-point-based localization pipeline based upon
the extraction of curbstone information is presented, that allows to bridge
sparse key-point based feature scenarios in visual localization.

  * •

In a thorough evaluation on the long-term dataset collection UP-Drive, we
demonstrate a reliable localization performance across different appearance
conditions in urban outdoor environments. We compare our results to our
vision-based localization pipeline and demonstrate significant performance
increases.

  * •

A computational performance analysis showing that our proposed algorithm
exhibits real-time capabilities and better scalability.

##  II related work

Since our localization system is a multi-modal semantic extension of our
previous work we will concentrate the related work on frameworks that exploit
semantic features using either one modality or fusing multiple modalities in
different ways. Therefore these works can be subdivided into each of their
specific sensor setup. For general related work on our prior visual key-point
based system we refer to our previous work [1].

#### Vision-only

A recent example of using semantic features for the purpose of localization
and mapping is Lu et al. [2] using a monocular camera for road-mark detection
whereas other studies use traffic signs [3], line segments from multi-view
cameras [4] or poles [5] [6] for feature matching. On the detection of
curbstones, traditional image based curbstone detection mostly uses the
vanishing point and color distribution to detect the corresponding pixels [7],
[8]. Recent work such from Enzweiler et al. [9] and Panev et al. [10] also
demonstrate a learning based approach to detect curbs in images. In contrast
to the vision based approaches, we concentrate on the multi-modal aspect as
provided by Goga et al. [11].

#### LiDAR-only

LiDAR based methods use assumptions about the shape of the semantic features
like curbs, poles and planes by evaluating the difference in elevation [12,
13], slope [12] or curvature [14, 15]. Authors such as Schaefer et al. [16]
detect and extract 3D poles from the scenery which are then being used for map
tracking. In regards to the usage of curbstones, most applications use
geographical map data [17, 18] or road networks [19] as a reference to
localize with detected curbstones. Unlike these works, our approach does not
rely on external pre-generated data for curbstone map construction.

#### Vision and LiDAR

Recent work such from Kampker et al. [20] use a camera to extract pole like
landmarks and a LIDAR for cylinder shapes for the task of self-localization.
Kummerle et al. [21] demonstrate that basic geometric primitives can be
extracted using vision and LiDAR to obtain road markings, poles and facades
which can then be used for localization and mapping for the purpose of self-
localization on various weather conditions. While these approaches use both
modalities for mapping and localization separately, there has been recent
research into cross-modality. Xiao et al. [22] uses a LiDAR to build an HD map
and extract 3D semantic features from the map. Then a monocular camera is used
with a deep learning based approach to match these semantic features with the
ones from the camera. In contrast to the graph-based SLAM formulation used in
our approach, the mentioned approaches are filter-based, with Extended Kalman
Filters [23] or Monte Carlo Localization [18, 20], and they are evaluated at
low speed and/or on short maps of a few hundred meters [22]. In addition they
do not use raw curbstone measurements as a feature for localization and
mapping [21, 22, 16, 17, 18]. Our work is evaluated on a long-term map with a
length of over 5$km$ using urban driving speed of around 50$km/h$.

##  III Methodology

Figure 2:  The key-point based map-tracking module extracts 2D features from
current camera images, and matches them with 3D map landmarks locally in image
space using a pose prior $\hat{T}^{t}_{MB}$ while our semantic map-tracking
module matches point-cloud based curbstone measurements between our map and
immediate input. The state estimation module fuses the visual 2D-3D and
geometrical 3D-3D matches with the current wheel-odometry measurement to
obtain a current vehicle pose estimate $T^{t}_{MB}$.

A schematic overview of MOZARD can be found in Figure 2. Since our work
extends the VIZARD framework, we refer to the general methodology from Buerki
et al. [1]. We assume that our visual localization pipeline already created a
map by tracking and triangulating local 2D features extracted along a
trajectory.

###  III-A Curbstone Detection

For our curbstone detection we employ the work from Goga et al. [11]. Goga et
al., fuse a vision-based segmentation CNN with LiDAR data. In a post-
processing step they extract, refine and filter semantic curb ROIs to obtain
new curb measurements. In the following we use their curbstone detection as
input into our pipeline.

###  III-B Map Extension

The curbstones are added to a map that was built using the VIZARD pipeline
[1]. This map is called the base map in the following. Curbstone points
detected in a specific LiDAR pointcloud frame will be called curbstone
observation. The detection pipeline finds curbstone pointclouds in the vehicle
frame $\mathcal{F}_{B}$. We find the closest vertex in time within the base
map and allocate the curbstone pointcloud. This is performed for all curbstone
detections along the trajectory. From the base map, the respective
transformations from the map coordinate frame $\mathcal{F}_{M}$ to the body
frame at time $t$ can be looked up. Using $T_{MB}^{t}$ at each vertex in the
base map that contains a curbstone observation, a curbstone map in
$\mathcal{F}_{M}$ can then be created.

###  III-C Curbstone Map-Tracking

Figure 3:  For our curbstone parameterization pipeline we first obtain raw
curbstone measurements. After a voxelization processing step, we cluster the
curbstones into segments. Finally, a cubic b-spline is fitted to each segment.
In case the fitting algorithm fails, we store the raw points.

The curbstone tracking module is the core component of the curbstone
localization pipeline. It performs an alignment between the map curbstones and
the input curbstones to estimate the vehicle pose. A sanity check is performed
to detect wrong alignments. If it is fulfilled, a pose constraint is added to
the graph. The integration into the VIZARD system is shown in Figure 2. The
single steps are explained in detail in the following section.

####  III-C1 Reference Curbstone Retrieval

To retrieve the map curbstones, a prior estimate $\hat{T}^{t}_{MB}$ is used.
In a fixed radius $r_{lookup}$ around the estimated position $\hat{P}^{t}$, we
then search for the closest vertex in Euclidean distance in the base map that
contains curbstones. Furthermore, a criterion on the maximum yaw angle between
the prior pose estimate and the base map vertex pose is used to prevent wrong
associations.

####  III-C2 Pointcloud Registration

Given the map and input curbstones a pointcloud registration is performed. As
the registration algorithm NDT (Normal Distribution Transform) [24] is used
from the implementation of the Point Cloud Library [25]. Additionally, outlier
points are removed using a fixed ratio since some artifacts might only be
included in one of both pointclouds, due to occlusion or unsimilar detection.
The pointcloud registration estimates a transformation $T_{align}$ that aligns
the input cloud to the map cloud.

####  III-C3 Sanity Check

In some regions, the input or map pointcloud can consist of very few points.
Matching in those scenarios can be ambiguous and lead to wrong associations.
Thus, matching is only performed if both pointclouds exceed a minimum amount
of points. Since urban street scenarios change frequently, e.g due to
constructions or parked cars, the input and map pointcloud can diverge
heavily. In those cases, pointcloud registration might fail, ending up in
wrong alignments and thereby wrong pose estimates. Therefore, a sanity check
has to be performed, to detect wrong pose estimates. To do so, a matching
score can be calculated, that can be used as an indicator if the alignment was
successful. Magnusson et al. [24] proposed a matching score for NDT. It
corresponds to the likelihood that the aligned input points lie on the
reference scan. A more detailed explanation can be found in his work [24]. The
alignment is considered valid, if the mean likelihood over all input points is
higher than a threshold $P_{min}$.

####  III-C4 Pose Constraint

The new pose estimate is calculated as:

$T^{t}_{MB_{estimate}}=\hat{T}^{t}_{MB}*T_{align}$

If the sanity check is successful, the pose constraint is added to the pose
graph using a fixed covariance. For our experiments, the covariance was
determined empirically.

###  III-D Curbstone Parameterization

Since curbstone maps can scale quickly given the multitude of possibly
redundant observations, a memory overhead is induced. To reduce this memory
footprint, we perform a curbstone parameterization. Since the map contains
several artifacts like intersections or roundabouts, a curve parameterization
was preferred over a polyline. Curbstones are not continuous throughout the
whole map, as they often end at intersections. Thus, it naturally makes sense
to split the map into single connected regions. In a first step, the raw
curbstone pointcloud is subsampled. A clustering is then performed on the
subsampled points, to find connected segments of a maximum length. The length-
to-width ratio of each segment is then calculated. If a certain threshold is
fulfilled, a Cubic B-Spline is fitted to the segment. By doing so, only the
control points of the spline have to be saved, instead of all raw curbstone
points. If the threshold is not fulfilled, the raw points are saved. The steps
are explained in detail in the following and shown in Figure 3.

####  III-D1 Subsampling

The high point density of the raw pointcloud can result in high runtimes of
the clustering as well as in overfitting of the spline to noise in the points.
Thus, a spatial subsampling using a voxel grid with a leaf size of $30cm$ is
performed. A pointcloud of the means of the points inside each voxel is then
used for clustering.

####  III-D2 Clustering

The clustering is performed in a two-step fashion. First, a Euclidean
clustering using a tolerance of more than $2m$ is performed to find large
segments. Since the curvature can vary along long segments, fitting a single
spline to it can be problematic, as different levels of detail are needed
along the segment. An example is a curb going around a corner: While low
curvature is desired in the straight sections, high curvature is needed in the
area of the corner to properly describe the curb. Thus, the coarse cluster is
split into smaller sub-clusters with a maximum expansion of 20$m$ before
validating each sub-cluster by using an SVD Decomposition.

####  III-D3 Cubic B-Spline Fitting

Spline fitting usually refers to fitting a spline that goes through each
single input point. However, due to the noisy nature of the curbstone segment,
a best fit given a fixed amount of control points is preferred in this case
instead of fitting every single point. To achieve this, the approach proposed
by Wang et al. [26] to fit an open cubic B-Spline is used. The number of
control points is calculated proportionally to the approximate length of the
segment, using $0.25\ points/m$, but a minimum of $4$. For segments with a
large width (indicating an intersection, road curve or round-about) a fixed
amount of $20$ points is used to allow for a proper representation. To
validate our fitted spline, we define our goodness score $GS$ as follows:

$GS=\frac{\\#Spline\ Inliers}{\\#Spline\ Points}*\frac{\\#Point\
Inliers}{\\#Points}$

whereas $SplineInliers$ is the number of sampled spline point close to a raw
point and $PointInliers$ the number of raw points close to points sampled from
a spline. Naively using all sub-segment points for the spline fitting can lead
to an overfitting of the curve. Thus, the best set of points is found in a
RANSAC-like manner. In each iteration, one third of the sub-segment points is
sampled randomly. The spline is then fitted to the sampled points. Eventually,
the spline with the highest score is chosen.

####  III-D4 Spline Sampling

To be able to perform matching with the input cloud, points are spatially
uniformly sampled from the splines during runtime. Those sampled points are
then used as the map pointcloud.

##  IV Evaluation

In the following section, the performance of the proposed pipeline is
evaluated and compared against the VIZARD pipeline as a benchmark. Long-term
experiments in an urban scenario are performed on varying weather and
appearance conditions. A special focus is set on how curbstone map tracking
influences localization accuracy and recall. Example cases are presented,
where localization gaps in the VIZARD pipeline could be bridged using
curbstone localization. The sensor set-up of the UP-Drive vehicle and the
datasets used in the experiments are described in the next section.

###  IV-A The UP-Drive Platform

For the collection of the datasets, the UP-Drive vehicle was used. Its sensor
setup consists of four fish-eye cameras, resulting in a surround view of the
car. Gray-scale images with a resolution of $640x400px$ are recorded at
$30Hz$. Five Velodyne LiDARs are mounted on top of the car. Curbstones are
obtained from the approach as described by Goga et al. [11]. Additionally, a
low-cost IMU and wheel tick encoders are used to provide odometry
measurements. A consumer-grade GPS sensor is used to gain an initial position
estimate and near-by map poses are used to generate an initial orientation
estimate.

###  IV-B UP-Drive Dataset Collection

The UP-Drive dataset collection was recorded between December 2017 and
November 2019 in Wolfsburg, Germany, at the Volkswagen factory and its
surrounding area and aggregate a total driving distance of multiple $100$
kilometers. The environment is urban, with common artifacts such as busy
streets, buses, zebra crossings and pedestrians. Since the data was collected
over several months, seasonal appearance changes as well as multiple weather
and day-time conditions are present. For this work, our dataset selection is
dependent on the availability of curbstone measurements, which result from the
curbstone detection pipeline from Goga et al. [11]. Since the curbstone
detection module was only enabled in some of our datasets, our evaluation
dataset collection consists of $5$ sessions which totals to $10$ drives from
August 2019 to November 2019. Each session contains two partially overlapping
routes in opposite directions and consists of the same amount of sunny and
cloudy/rainy conditions captured throughout a day. Recordings in rainy
conditions are categorized as Cloudy, since there is little difference in
performance on rainy datasets as opposed to in dry conditions.

###  IV-C Metrics

####  IV-C1 Localization Recall

The fraction of the total travelled distance in which a successful
localization was achieved is calculated as the localization recall $r$[%].
While using only the visual pipeline, a localization attempt at time $t$ is
accepted as successful if a minimum of $10$ inlier landmark observations is
present after pose optimization. When using the combined pipeline, a
localization is counted as successful, if the condition above is fulfilled or
if a viable curbstone alignment (see section III-C) could be performed.

####  IV-C2 Localization Accuracy

As no ground-truth for the described dataset exists, the poses estimated by an
RTK GPS sensor are used instead as a reference. RTK GPS altitude estimates are
not reliable, thus the error in $z$ can not be calculated reliably. Therefore,
we focus on the planar $\mathbf{p^{e}_{xy}}$ and lateral translation error
$\mathbf{p^{e}_{y}}$ as well as on the orientation error
$\mathbf{\theta^{e}_{xyz}}$.

|  $\mathbf{r}_{mt}$[%] |  | $\mathbf{\bar{p}^{e}_{xy}}$, $\mathbf{\bar{p}^{e}_{y}}$ |  | $\mathbf{\bar{\theta}^{e}_{xyz}}$
---|---|---|---|---|---
|  $10$-$08$ |  $10$-$25$ |  $11$-$08$ |  $11$-$20$ |  |  $10$-$08$ |  $10$-$25$ |  $11$-$08$ |  $11$-$20$ |  |  $10$-$08$ |  $10$-$25$ |  $11$-$08$ |  $11$-$20$
$MOZARD$ \- $Map$ |  |  |  |  |  |  |  |  |  |  |  |  |  |
$($08-21$)$ | 100.0 | 99.94 | 99.06 | 99.82 |  | 0.08 [0.34],0.04 [0.21] | 0.07 [0.26], 0.03 [0.13] | 0.09 [0.37], 0.04 [0.2] | 0.13 [0.37], 0.05 [0.2] |  | 0.64 [0.75] | 0.74 [0.76] | 1.04 [1.33] | 1.09 [1.4]
$($08-21; 10-08$)$ | - | 100.0 | 100.0 | 100.0 |  | - | 0.06 [0.15], 0.03 [0.08] | 0.07 [0.24], 0.03 [0.13] | 0.1 [0.29], 0.04 [0.14] |  | - | 0.66 [0.65] | 1.15 [1.4] | 1.2 [1.4]
$($08-21; 10-08; 10-25$)$ | - | - | 100.0 | 100.0 |  | - | - | 0.07 [0.22], 0.03[0.11] | 0.09 [0.27], 0.03 [0.12] |  | - | - | 1.21 [1.43] | 1.23 [1.42]
$($08-21; 10-08; 10-25; 11-08$)$ | - | - | - | 100.0 |  | - | - | - | 0.07 [0.18], 0.02 [0.1] |  | - | - | - | 1.13 [1.38]
$VIZARD$ \- $Map$ |  |  |  |  |  |  |  |  |  |  |  |  |  |
$($08-21$)$ | 100.0 | 98.2 | 97.94 | 91.76 |  | 0.08 [0.28], 0.04 [0.16] | 0.07 [0.26], 0.03 [0.13] | 0.09 [0.29], 0.04 [0.17] | 0.13 [0.37], 0.05 [0.21] |  | 0.64 [0.76] | 0.74 [0.76] | 1.1 [0.16] | 1.07 [1.28]
$($08-21; 10-08$)$ | - | 100.0 | 99.9 | 97.89 |  | - | 0.06 [0.13], 0.02 [0.07] | 0.07 [0.24], 0.03 [0.13] | 0.1 [0.29], 0.04 [0.14] |  | - | 0.55 [0.67] | 1.15 [1.4] | 1.19 [1.37]
$($08-21; 10-08; 10-25$)$ | - | - | 100.0 | 99.18 |  | - | - | 0.07 [0.22], 0.03 [0.11] | 0.09 [0.25], 0.03 [0.13] |  | - | - | 1.21 [1.43] | 1.23 [1.41]
$($08-21; 10-08; 10-25; 11-08$)$ | - | - | - | 99.7 |  | - | - | - | 0.07 [0.18], 0.02 [0.1] |  | - | - | - | 1.13 [1.38]

TABLE I:  The localization performance on the UP-Drive dataset, showing
localization recall, and the median planar $\mathbf{\bar{p}^{e}_{xy}}$,
lateral $\mathbf{\bar{p}^{e}_{y}}$ and orientation
($\mathbf{\bar{\theta}^{e}_{xyz}}$) accuracy. The $90$ percentile is shown in
square brackets. Numbering in round brackets defines the timestamp of the
sessions used for mapping. E.g. (08-21) represents August, 21th.

###  IV-D Localization Accuracy and Recall

In order to fully rely on MOZARD to control the car in the UP-Drive project, a
high localization recall with an accuracy below 0.5$m$ is paramount, as only
short driving segments with no localization may be bridged with wheel-odometry
before the car may deviate from its designated lane. Curbstones are not
available for the whole trajectory, but for around 89% of the distance of the
map. We compare localization recall and accuracy of our localization system to
our prior work on visual localization - VIZARD [1]. Note, however, that our
prior work relied on the use of cameras for localization, as in contrast to
the former, the latter is now able to use LiDAR and vision. To demonstrate
that curbstones provide useful additional information, we construct and expand
a map iteratively using multiple datasets. Our first map is constructed from
two datasets (one session) from August 2019. We then evaluate this map against
multiple sessions from different months and add these sessions to our (multi-
session) map in a iterative fashion. We present the resulting key evaluation
metrics (localization recall $\mathbf{r}_{mt}$[%] and localization accuracy)
in Table I over all sessions. By including this comparison, we aim at
highlighting the gain in localization recall attainable by using MOZARD while
keeping a consistent median translation and orientation error. As shown in
Table I, MOZARD is able to attain close to a $100\%$ recall performance on all
$4$ sessions on the UP-Drive dataset, while VIZARD performance increase
correlates with the addition of sessions to its base map due to the change in
visual appearance. We further note that in both cases the planar median
localization accuracy are below 15$cm$, while the median lateral error is
below 10$cm$. The median orientation errors are on average less than 1
$degree$. For MOZARD the 90th percentile shows an increase which is likely to
be due to the higher uncertainty in precision of curbstone measurements.

###  IV-E Runtime

On our live car platform Goga et al. [11] demonstrated that their curbstone
detection pipeline deployed on 2 Nvidia GTX 1080 takes around 20$ms$ for the
CNN image segmentation to complete on all $4$ cameras. An additional 32$ms$
are needed for the fusion of 5 LiDARs to run on an Intel i7-3770K CPU. Our
curbstone alignment module takes an average of approximately 25$ms$, while the
map tracking module (with vision) can take from 27$ms$ with a single session
map up to 48$ms$ on our largest multi-session map (see Table I) and has been
evaluated on an Intel Xeon E3-1505M CPU. This would allow MOZARD to run with
around 10$Hz$ on a single machine on a single session map. Table II summarizes
our findings.

Module | Average Runtime [ms]
---|---
Curbstone Detection | 52
Curbstone Tracking | 25
Map Tracking (VIZARD) | 27-48
Total | 104-125
TABLE II:  Runtime of each component of MOZARD . Curbstone Detection and
Curbstone Tracking with average runtime over all evaluated datasets on a
single session map, while Map Tracking shows average runtime for running on a
single session map and on the largest multi-session map.

###  IV-F Case Study

We provide further insights into our pipeline by showing specific failure
examples for each component. Sample images of a section where the visual
localization fails on the evaluated datasets are depicted in Figure 4. Due to
occlusion and the absence of surrounding building structures, barely any
stable visual cues are found in this section, preventing the visual
localization system from matching a sufficient amount of landmarks from the
map. This example demonstrates the current limitations of VIZARD, while our
MOZARD pipeline is able to handle these sparse keypoint-based scenarios.
Unfortunately there are also scenarios where a lack of keypoints and
curbstones exists or our curbstone alignment fails - hence conditions where
both pipeline are likely to fail as depicted in the right image of Figure 4. A
further extension of our current framework to other geometric shapes such as
poles, road markings could provide additional useful information that would
allow us to further increase our localization performance. Note that we used a
single session map for the evaluation of this case study and VIZARD is able to
bridge some of these scenarios if enough datasets are provided during the
mapping process.

Figure 4:  On the left, a sample image of a trajectory segment that fails to
localize due to occlusion. A lack of keypoints renders it unfeasible to match
a sufficient number of map landmarks. On the middle, the projected curbstone
information is depicted in the camera frame in red - enabling a continued
localization although visual localization failed. On the right, a sample image
is depicted where our curbstone and vision pipeline fail. In this case
curbstones are actually detected but alignment fails due to our constraints.

##  V conclusions

We presented MOZARD, a geometric extension to our visual localization system
for urban outdoor environments. Through our evaluation on $8$ datasets,
including several kilometers of real-world driving conditions, we demonstrated
the benefits of using curbstone information for localization and mapping. Our
datasets used in the experiments contain challenging appearance conditions
such as seasonal changes, wet road surfaces and sun reflections. A comparison
with our prior work demonstrated that we can achieve a higher recall
performance while using less datasets during the mapping process, as the
pipeline would fail due to sparse keypoint scenarios. Our run-time analysis
shows that our approach demonstrates real time capabilities. Although the
curbstone detection stack of MOZARD takes in average more computing time than
VIZARD, it is to note that an object segmentation/detection algorithm on a
self-driving car has to be deployed for environmental perception independent
of whether a localization takes place or not. Even taking in account the total
computational time, our approach still runs at $10Hz$ while needing up to four
times less data while achieving the same localization performance. We also
showed specific cases where both of our pipelines would fail due to occlusions
and/or curbstone misalignment giving suggestions for future work such as the
extension of our approach to poles and road markings. Our findings showed that
by extending a keypoint based visual localization approach with geometric
features - curbstones in our case, an improvement in robustness with
consistent high accuracy in localization is obtained.

## ACKNOWLEDGMENT

This project has received funding from the EU H2020 research project under
grant agreement No 688652 and from the Swiss State Secretariat for Education,
Research and Innovation (SERI) under contract number 15.0284.

## References

  * [1] M. Bürki, L. Schaupp, M. Dymczyk, R. Dubé, C. Cadena, R. Siegwart, and J. Nieto, “Vizard: Reliable visual localization for autonomous vehicles in urban outdoor environments,” 2019.
  * [2] Y. Lu, J. Huang, Y.-T. Chen, and B. Heisele, “Monocular localization in urban environments using road markings,” 06 2017, pp. 468–474.
  * [3] L. DOrazio, N. Conci, and F. Stoffella, “Exploitation of road signalling for localization refinement of autonomous vehicles,” 07 2018, pp. 1–6.
  * [4] K. Hara and H. Saito, “Vehicle localization based on the detection of line segments from multi-camera images,” vol. 27, pp. 617–626, 01 2015.
  * [5] L. Weng, M. Yang, L. Guo, B. Wang, and C. Wang, “Pole-based real-time localization for autonomous driving in congested urban scenarios,” in _2018 IEEE International Conference on Real-time Computing and Robotics (RCAR)_ , Aug 2018, pp. 96–101.
  * [6] R. Spangenberg, D. Goehring, and R. Rojas, “Pole-based localization for autonomous vehicles in urban scenarios,” in _2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , Oct 2016, pp. 2161–2166.
  * [7] N. John, B. Anusha, and K. Kutty, “A Reliable Method for Detecting Road Regions from a Single Image Based on Color Distribution and Vanishing Point Location,” _Procedia Computer Science_ , vol. 58, pp. 2–9, jan 2015.
  * [8] S. Hosseinyalamdary and M. Peter, “Lane level localization : using images and hd maps to mitgate the lateral error,” in _Proceedings of ISPRS Hannover Workshop : HRIGI 17 – CMRT 17 – ISA 17 – EuroCOW 17, 6–9 June 2017, Hannover, Germany_ , ser. ISPRS Archives, C. Heipke, Ed., vol. XLII-1/W1. International Society for Photogrammetry and Remote Sensing (ISPRS), 2017, pp. 129–134.
  * [9] M. Enzweiler, P. Greiner, C. Knoppel, and U. Franke, “Towards multi-cue urban curb recognition,” in _2013 IEEE Intelligent Vehicles Symposium (IV)_. IEEE, jun 2013, pp. 902–907.
  * [10] S. Panev, F. Vicente, F. De la Torre, and V. Prinet, “Road curb detection and localization with monocular forward-view vehicle camera,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 20, no. 9, pp. 3568–3584, Sep. 2019.
  * [11] S. E. C. Goga and S. Nedevschi, “Fusing semantic labeled camera images and 3D LiDAR data for the detection of urban curbs,” in _Proceedings - 2018 IEEE 14th International Conference on Intelligent Computer Communication and Processing, ICCP 2018_ , 2018.
  * [12] Z. Liu, J. Wang, and D. Liu, “A new curb detection method for unmanned ground vehicles using 2d sequential laser data,” 2013.
  * [13] A. Miraliakbari, M. Hahn, and S. Sok, “Automatic extraction of road surface and curbstone edges from mobile laser scanning data,” 2015.
  * [14] C. F. Lopez, D. F. Llorca, C. Stiller, and M. Á. Sotelo, “Curvature-based curb detection method in urban environments using stereo and laser,” _2015 IEEE Intelligent Vehicles Symposium (IV)_ , pp. 579–584, 2015.
  * [15] C. F. Lopez, R. Izquierdo, D. F. Llorca, and M. Á. Sotelo, “Road curb and lanes detection for autonomous driving on urban scenarios,” _17th International IEEE Conference on Intelligent Transportation Systems (ITSC)_ , pp. 1964–1969, 2014.
  * [16] A. Schaefer, D. Buscher, J. Vertens, L. Luft, and W. Burgard, “Long-term urban vehicle localization using pole landmarks extracted from 3-d lidar scans,” 09 2019, pp. 1–7.
  * [17] P. Bonnifait, M. Jabbour, and V. Cherfaoui, “Autonomous navigation in urban areas using GIS-managed information,” _International Journal of Vehicle Autonomous Systems_ , vol. 6, no. 1/2, p. 83, 2008.
  * [18] B. Qin, Z. J. Chong, T. Bandyopadhyay, M. H. Ang, E. Frazzoli, and D. Rus, “Curb-Intersection Feature Based Monte Carlo Localization on Urban Roads,” Tech. Rep.
  * [19] J. Stueckler, H. Schulz, and S. Behnke, “In-lane localization in road networks using curbs detected in omnidirectional height images,” in _Proceedings of Robotik 2008_ , 2008.
  * [20] A. Kampker, J. Hatzenbuehler, L. Klein, M. Sefati, K. Kreisköther, and D. Gert, _Concept Study for Vehicle Self-Localization Using Neural Networks for Detection of Pole-Like Landmarks: Proceedings of the 15th International Conference IAS-15_ , 01 2019, pp. 689–705.
  * [21] J. Kummerle, M. Sons, F. Poggenhans, T. Kuhner, M. Lauer, and C. Stiller, “Accurate and efficient self-localization on roads using basic geometric primitives,” 05 2019, pp. 5965–5971.
  * [22] Z. Xiao, K. Jiang, S. Xie, T. Wen, C. Yu, and D. Yang, “Monocular vehicle self-localization method based on compact semantic map,” 05 2018.
  * [23] H. Lee, J. Park, and W. Chung, “Localization of Outdoor Mobile Robots Using Curb Features in Urban Road Environments,” _Mathematical Problems in Engineering_ , vol. 2014, pp. 1–12, apr 2014.
  * [24] M. Magnusson, “The Three-Dimensional Normal-Distributions Transform —an Efficient Representation for Registration, Surface Analysis, and Loop Detection,” 2009.
  * [25] R. B. Rusu and S. Cousins, “3D is here: Point Cloud Library (PCL),” in _IEEE International Conference on Robotics and Automation (ICRA)_ , Shanghai, China, May 9-13 2011.
  * [26] W. Wang, H. Pottmann, and Y. Liu, “Fitting b-spline curves to point clouds by curvature-based squared distance minimization,” _ACM Transactions on Graphics_ , vol. 25, pp. 214–238, 05 2006.


# Fairness Notions in DAG-based DLTs

Mayank Raikwar,1 Nikita Polyanskii,2 Sebastian Müller3  1University of Oslo,
Norway
Email<EMAIL_ADDRESS>2IOTA Foundation, Berlin, Germany
Email<EMAIL_ADDRESS>3Aix Marseille Université, CNRS, Centrale
Marseille, France
Email<EMAIL_ADDRESS>
###### Abstract

This paper investigates the issue of fairness in Distributed Ledger Technology
(DLT), specifically focusing on the shortcomings observed in current
blockchain systems due to Miner Extractable Value (MEV) phenomena and systemic
centralization. We explore the potential of Directed Acyclic Graphs (DAGs) as
a solution to address or mitigate these fairness concerns. Our objective is to
gain a comprehensive understanding of fairness in DAG-based DLTs by examining
its different aspects and measurement metrics. We aim to establish a shared
knowledge base that facilitates accurate fairness assessment and allows for an
evaluation of whether DAG-based DLTs offer a more equitable design. We
describe the various dimensions of fairness and conduct a comparative analysis
to examine how they relate to different components of DLTs. This analysis
serves as a catalyst for further research, encouraging the development of
cryptographic systems that promote fairness.

##  I Introduction

DLTs have become quite popular in the last decade due to their broad range of
applications. The most well-known DLT architecture is the Blockchain which was
introduced in Bitcoin cryptocurrency [1]. After the advent of Bitcoin, there
have been a plethora of cryptocurrencies [2] with similar underlying
blockchain structures but differing in consensus, security guarantees,
performance, and additional functionalities. Nevertheless, the main technical
hurdle to the adoption of blockchain in real-world applications is its
scalability. Therefore, many methods such as Layer-2 protocols [3], and
sharding techniques [4] have been proposed to solve the scalability issue of
the blockchain. Another alternative solution to the scalability problem is to
have a different structure of DLT than the linear chain structure of
blockchain. One such structure is Directed-Acyclic Graph (DAG)-based DLT [5,
6]. The assurance of DAG-based DLT is high scalability and fast confirmation
of transactions without significantly compromising security.

The idea of DAG-based DLT is to form a directed acyclic graph structure from
the blocks/transactions instead of forming a chain by referencing a single
block [7]. In this way, many transactions are verified in parallel and hence
provide a more scalable DLT architecture. The goal of these DAG-based DLTs is
to achieve higher throughput while keeping or reducing the communication
or/and computation complexity, latency, and storage overhead. Most of the
existing works in DAG-based DLTs focus on performance improvement, however,
fairness notions in DAG-based DLTs have not yet been explored.

Fairness plays a prominent role in DLTs encompassing technical, economic, and
social considerations. In a DLT, an unfair scenario can lead to discontent
among participants, thereby impeding the widespread adoption of the DLT.
Consequently, it is imperative for DAG-based systems to prioritize the
integration of fairness within their frameworks. The prevailing notion of
fairness, often acknowledged, entails the eventual acceptance of blocks
produced by slow yet honest nodes in the DAG-based DLT. A node can be termed
as slow if 1) the node has low computing power in Proof-of-Work (PoW)-based
DLT; 2) the node has a low stake in Proof-of-Stake (PoS)-based DLT; 3) the
node has large communication delay with the rest of the network, for example,
due to the network topology or being geographically distant. The above-defined
notion is a very general definition of fairness but in DAG-based DLTs,
fairness can be expressed in different notions.

While fairness has been examined and addressed in blockchain protocols, the
presence of a single miner or validator making decisions regarding the
ledger’s progress remains a prominent cause of fairness challenges. However,
in DAG-based protocols, the ledger’s state progression is controlled by
multiple nodes. In essence, this represents the potential for enhanced
fairness in DAG-based protocols. Furthermore, some DAG-based DLTs allow weak
references to rescue the old blocks and improve the fairness of the DLT [8,
9].

###  I-A Related Work

Since the inception of Bitcoin, there has been a substantial amount of work
and studies conducted toward improving the scalability and security of the
protocol [10]. Nevertheless, in recent years, a few works concentrate on
fairness in Bitcoin like linear blockchain models. These works examine
fairness in two main aspects: 1) Fairness in reward mechanisms of blockchain
systems [11, 12]; 2) Fairness in the ordering of transactions in blockchain
systems [13, 14].

Amoussou-Guenou et al. [11] propose the formal notions of fairness in
committee-based PoW blockchain protocols. The authors define two fairness
notions: 1) Selection fairness which says how fairly the subset of nodes are
selected to participate to append a block in a consensus round; 2) Reward
fairness which describes how the reward is distributed among the committee
nodes in a fair manner. Huang et al. [12] propose two types of fairness, i.e.,
exceptional fairness and robust fairness in PoS blockchain protocols. These
fairness notions characterize the relation between a miner’s stake and his/her
reward in a consensus round.

Fairness in transaction ordering refers to the ordering of transactions in a
block of a blockchain. A fair ordering expresses a fair block proposal where
the block proposer follows the random selection of transactions and does not
include/exclude/prioritize some transactions. Different fairness notions in
transaction ordering have been proposed in blockchain protocols [13, 14]. Even
so, manipulation in transaction ordering leads to MEV extraction and MEV
attacks [15]. There are different types of MEV attacks. Out of these attacks
Sandwich and Long-trail MEV attacks occur more often. In 2022, MEV searchers
generated $128 million revenue alone from Sandwich attacks [16].

Though a few efforts have been made to study and subsequently solve the
fairness issues in blockchain protocols, not many works endeavour to look into
fairness problems in DAG-based DLTs. The primary goal of these DLTs has been
to solve the inherent low throughput problem of blockchain.

The field of DAG-based protocols has experienced continuous growth in research
efforts [7]. While many of these works aim to enhance the performance of DAG-
based Distributed Ledger Technologies (DLTs), they also explore different
network models (synchronous, partially synchronous, asynchronous) and
adversarial models (static, adaptive). However, only a limited number of works
specifically address fairness in DAG-based DLTs. Birmpas et al. [17] present a
parametric model that evaluates the fairness and efficiency of DAG-based DLTs
by adjusting various ledger parameters. In their model, fairness is defined as
the proportional reward allocation to participating validator nodes based on
their hash power. Their findings demonstrate that fairness is significantly
influenced by the connectivity levels of validator nodes within the underlying
peer-to-peer network. It is important to note that their model focuses on
capturing fairness exclusively in DAG-based DLTs that employ Proof-of-Work
(PoW) puzzles as their consensus mechanism.

DAG-based DLTs such as DAG-Rider [18], Tusk [19], Bullshark [8] give attention
to fairness in their protocol. We will give more details about this in the
following sections.

In a PoW-based DLT protocol with high difficulty, slow nodes rarely get a
chance to append a block or issue the transactions. Vigneri et al. [20]
propose an adaptive rate control mechanism in a PoW-based DLT providing
dynamic difficulty for the fair treatment of nodes irrespective of their
computational power. Another work [21] in a similar direction shows fairness
between low and high power nodes through analytical and simulation results.
Müller et al. [22] construct a mathematical model for fairness in a weighted
voting consensus protocol in DAG-based DLT. Using their model, a node having
low weight also participates in consensus finding. These types of fairness
notions are out of the scope of this paper.

###  I-B Our Contribution

In this paper, we are primarily interested to explore the different notions of
fairness in the context of DAG-based DLTs. To the best of our knowledge, no
work has been done to systematize fairness notions in DAG-based DLTs. We
present informal definitions of these fairness notions and describe the
importance of these notions. We also discuss the relation of fairness with
other DLT components.

###  I-C Structure of the Paper

The rest of the paper is described as follows: Section II presents the
description of a DAG-based DLT. Section III demonstrates the different
fairness notions in DAG-based DLT protocols. Further, Section IV provides a
brief description of the relationship between defined notions and other
important components/functionalities in DAG-based DLTs. Finally, in Section V,
we conclude the paper with a few interesting research directions.

##  II DAG-based DLT

DAG-based DLT systems structure the transactions/blocks in the form of a DAG
topology. A directed graph $G$ is a tuple of vertex set $V$ and directed edge
set $E$, such that $G:=(V,E)$. In this graph, a vertex represents a unit
(transaction/block) and a directed edge represents a relationship between two
units. That means, an edge $e\in E$ in the graph $G$ represents a partial
order relationship between a pair of units $(u,v)$, where $u,v\in V$. An edge
$u\leftarrow v$ can have the meaning that $v$ verifies/confirms/witnesses $u$.
An edge can also represent a hash reference from one unit to another. A
directed graph $G$ is a directed acyclic graph if $G$ has no directed cycles,
whereas a directed cycle is a sequence of vertices where the first and last
vertices in the sequence are the same, and all edges are oriented in the same
direction.

The introduction of multiple references per block results in the formation of
a Directed Acyclic Graph (DAG). In a traditional linear blockchain, the
longest chain rule serves a dual purpose: agreeing on the included blocks and
establishing their order. However, when transitioning from linear chains to
DAGs, these two functions need to be replaced. To address this, two primary
classes of protocols have emerged: those that perform these tasks directly on
the DAG itself, and Byzantine Fault Tolerant (BFT) protocols that utilize
supplementary broadcast primitives.

The concept of using DAG in a ledger protocol was first introduced by
Sompolinsky et al. in GHOST protocol [5] which addresses the concurrency
problem of transactions in Bitcoin by building a tree instead of a linear
chain. Later, an improved version of the protocol [23] was utilized in
Ethereum [24]. In GHOST protocol, a newly created (mined) block does not refer
to the leaf block of the longest chain. Instead, starting from the genesis
block and at each fork, the branch with the heaviest sub-tree underneath is
chosen until a leaf block is found. Once the leaf block is found, the newly
mined block connects to it by including the hash pointer of the leaf block.
Therefore, in the GHOST protocol, blocks created by the forks also contribute
to the final consensus while maintaining robustness and high throughput.

Later, IOTA [6], Byteball [25], and many other DAG-based DLT protocols adopted
the paradigm of using individual transactions as vertices in a DAG. With this
modification, the transactions are disseminated and confirmed faster. In the
following years, many works and studies on DAG-based DLTs are conducted. These
works update and modify the DAG structure, and improve the performance by
requiring less computation, communication, and storage.

The structure of the DAG becomes very relevant while achieving the consensus
and proving the security guarantees. Many Proof-of-Work (PoW) employed
unstructured DAG-based protocols such as SPECTRE [26], PHANTOM [27], and DAG
KNIGHT [28] have been proposed. In protocols like SPECTRE, PHANTOM and DAG
KNIGHT, a newly created block has to cross-refer (point) to all the visible
tips (leaf) in the ledger. The ordering of all these blocks in the DAG becomes
the heart of the consensus protocol. Every node locally runs the ordering
procedure and returns a linear ordering over the blocks in its local DAG.

Structured DAG-based protocols such as Aleph [29], DAG-Rider [18], Tusk [19],
Bullshark [8], Cordial Miners [30] work in rounds in a permissioned setting,
i.e., there are fixed $n$ nodes that can add a block to the DAG, of which $f$
nodes are possibly faulty or Byzantine. Every round has at most $n$ blocks
(one for each node111Cordial Miners allows multiple blocks from one faulty
node per round. To mitigate equivocating blocks, this protocol suggests the
following: once an honest node detects an equivocator, the further
equivocator’s blocks are not directly referenced by the honest node.) where
every newly created block must refer to $n-f$ blocks from the previous round.
In these protocols, each node maintains its local version of the DAG and runs
the consensus protocol through logical interpretation of the DAG, i.e., blocks
represent transaction proposals and references serve as votes. Therefore,
consensus does not require any extra communication complexity. These protocols
are leader-based where a leader is elected after a constant number of rounds
(wave) using the encoded randomness in each wave in the asynchronous model or
the round-robin method in the partially synchronous model. Once the elected
leader block is committed and every node performs ordering on the leader
block’s casual history.

Out of the above protocols, only a few stress fairness while catering to high
throughput. Under the assumption of their network model, in these DAG-based
protocols, transactions and blocks propagated by the nodes/users in the P2P
network might take a long time before a validator node might receive them. Due
to that, validator nodes only see a portion of all the users’ transactions and
blocks ever produced in the network. Therefore, providing fairness to all the
issued transactions and blocks is a challenging but important task.

##  III Different notions of Fairness in DLTs

###  III-A Fairness to the Participants

  1. 1.

For Validators: Fairness for the validators refers to having an equal chance
for each validator node222Throughout the paper, we use validator node and node
interchangeably unless explicitly specified. to append its block to a
distributed ledger irrespective of communication latency and the validators’
computing power. A slow yet honest validator node cannot be distinguished from
an adversarial node, as it becomes challenging to identify the cause of delay
in the received block or transaction.

Fairness in this prospect has been taken into account in DLT protocols such as
Prime [31], HoneyBadger [32], and Fairledger [33]. These are BFT-based
blockchain protocols. To ensure fairness in these protocols, transactions from
multiple nodes are consolidated into batches, which are then committed
atomically within each epoch. Furthermore, these protocols incorporate
mechanisms to identify and penalize nodes that deviate from the prescribed
rules, thus bolstering fairness in favor of the honest nodes.

A recent line of work in DAG-based DLTs starting from Aleph [29], DAG-Rider
[18], Tusk [19], and Bullshark [8] emphasise on fairness to the validators.
During the construction of the DAG in certain DAG-based DLTs, a degree of
fairness is attained by mandating the inclusion of a minimum of $n-f$ blocks
from different validator nodes in the previous round. To provide fairness for
all the validators, some of these protocols [18, 8] use weak links to append
slow validators’ blocks. The idea of a weak link is to reference a tip (a
block that is not yet referenced) in the distant past together with other
“recent” tips while creating a new block in the DAG.

Fairness for validators ensures censorship resistance. It also shows a strong
notion of participation equity which refers to the Chain Quality property of
DLT, meaning that the ledger includes a certain portion of honest validators’
blocks. Therefore, to enforce fairness for the validator nodes, the new block
should include references to the slow validator’s block either by a weak link
in structured DAG-based DLTs or by referencing all the current tips.

  2. 2.

For Clients: Transactions in DLTs can be delayed inappropriately by a
malicious validator node. A validator node can prevent sending the
transactions received from a client to the rest of the DLT network. This
particular phenomenon can be termed as a compromise of fair access due to the
prevention of a client’s transaction from fairly accessing the network
relative to other clients’ transactions.

Fairness for a client can be defined as fair access to the client’s
transaction to the rest of the DLT network. It means when a validator node
receives a client transaction, the node should send the transaction to the
rest of the network without delay. To provide fairness to multiple clients
connected to a validator, the validator can either process the clients’
transactions in “First In First Out”(FIFO) order [34] or by monitoring the
latency of the transaction requests [35].

In protocols like Narwhal [19], a client transmits its transaction to all the
validator nodes to ensure fairness although it increases the bandwidth usage.
If the client’s transaction is not sequenced in the ledger in time, the client
re-submits its transaction. However, re-submitting the transaction to multiple
validator nodes not only wastes excessive resources such as bandwidth and CPU
but also comes under the radar of request duplication attacks. This attack
might harm honest clients if there is a penalty involved in every re-
transmission of honest clients’ transactions, for example, in Hedera Hashgraph
[36]. To prevent this duplication attack, a technique used in Mir-BFT [37]
based on hashing can be employed in DAG-based DLTs to provide fairness. On the
positive side, the dissemination of transactions is encoded in the very
structure of the Hashgraph. Each transaction carries with it the gossip
history which is used to achieve consensus on the validity and order of
transactions.

A malicious validator node could violate fair access. It can delete or ignore
client transactions. It can also delay a client’s transaction and favor other
clients’ transactions in order to punish the client or front-run the client’s
transaction. With the lack of delay in terms of fair access compromise, the
client’s transaction is transmitted and received later in the network and
hence the transaction is added later in the ledger than it should have been.

Clients can achieve fair access to their transactions in different ways as
follows:

     * •

Client can run a node that relieves the requirement of middleman proxy for the
client in the DLT network, e.g., Permissionless Hedera [36].

     * •

Client can submit a transaction to multiple or all validators in the DLT
network [19].

     * •

Client can submit a transaction to a node it trusts or the node having a
better rating if the nodes maintain a reputation system within the DLT network
[38].

     * •

Client can submit a transaction anonymously along with providing proof of
correctness to the transaction.

###  III-B Fairness in Consensus Ordering

Fairness in consensus ordering aka Order-Fairness ensures that the order of
transactions relative to each other is fair. There are different ways to
ensure fairness in transaction ordering. Order-Fairness is described in many
DLT protocols such as Helix [39], Hashgraph [36]. Kelkar et al. [14] presents
a good overview of order fairness in Byzantine consensus protocols. In a
similar direction, Kursawe [13] unveils a group of low overhead protocols,
Wendy, which can implement different notions of order-fairness in the
blockchain. Another interesting work [40] manifests a notion of content-
agnostic order-fairness.

Fairness in ordering can be abused by recording the transaction
inappropriately, meaning the transaction that arrived first is recorded as
received later. In other words, it is referred to as order manipulation.
Particularly in a leader-based consensus of a DLT, the consensus algorithm
elects a leader who is responsible for ordering and can delay the transaction
of a specific client while ordering. This phenomenon of manipulation of
transaction ordering is called the Miner Extractable Value (MEV) where a
validator (leader/miner) maximizes its profit by including, excluding, or
changing the order of client’s transactions within blocks. MEV was first
introduced as a measure in Flash Boys 2.0 [41], later it was named as Maximal
Extractable Value.

Fair ordering of transactions can solve the problem of front-running attacks
and censorship resistance in DLTs. The need for the fair ordering of
transactions becomes clear when we look at financial systems such as Ethereum
[24]. A recent report [42] delineates a comprehensive study of MEV extraction
on Ethereum and an overview of policymakers on MEV. Another latest paper [15]
presents a Systematization of Knowledge (SoK) on MEV countermeasures where a
brief description of common types of MEV and transaction ordering methods are
shown in a precise way.

In the pursuit of achieving order-fairness and mitigating Miner Extractable
Value (MEV) in DLT systems, two primary defensive measures are commonly
employed: 1) Time-based Order-Fairness and 2) Blind Order-Fairness.

####  III-B1 Time-based Order-Fairness

This protects from order manipulation by defining certain properties about
transaction ordering based on transaction arrival/sent time, and by satisfying
these properties. There are multiple definitions for Time-based Order-Fairness
in the literature [13, 14]. From these literature, following we exhibit a few
informal definitions of this order-fairness. Let $N$ represent the total
number of validator nodes, and $\alpha$ is a fraction parameter denoting
enough number of validator nodes.

  * •

Receive-Order-Fairness

###### Definition 1

(Receive-Order-Fairness) It states that if a sufficiently large number
${\alpha}N$ (with $\alpha>0.5$) of validator nodes receive a transaction
$tx_{1}$ before a transaction $tx_{2}$, then $tx_{1}$ should be ordered before
$tx_{2}$ in the final ordering of transactions agreed upon by the validator
nodes.

For the above definition to work, we need to make a few assumptions: 1) The
network must be synchronous; 2) The adversary must be non-colluding and non-
corrupting. Otherwise, it is almost impossible to achieve receive-order-
fairness. In some sense, this describes a distributed FIFO notion.

  * •

Send-Order-Fairness

###### Definition 2

(Send-Order-Fairness) It states that if a transaction $tx_{1}$ is sent before
a transaction $tx_{2}$, then $tx_{1}$ should be ordered before $tx_{2}$ in the
agreed-upon transaction log by the validator nodes.

For the above definition to work, we need a trusted way to timestamp the
transaction at the client’s end. One potential way to generate a trusted
timestamp is by using Trusted Execution Environment (TEE) such as Intel SGX
[43] or ARM Trustzone [44] at the client side. Nevertheless, even after having
a timestamp mechanism, network synchrony still plays a role to ensure that the
transaction is not arbitrarily delayed.

  * •

Approximate-Order-Fairness

###### Definition 3

(Approximate-Order-Fairness) For any two transactions $tx_{1}$ and $tx_{2}$,
let $n$ validator nodes receive both transactions in a given time-frame and
let $\epsilon$ be the number of rounds $tx_{1}$ and $tx_{2}$ are apart.
Approximate-Order-Fairness states that if ${\alpha}n$ nodes receive $tx_{1}$
more than $\epsilon$ rounds before $tx_{2}$, then for every honest node $j$,
$j$ does not deliver $tx_{2}$, unless it has previously delivered $tx_{1}$.

  * •

Block-Order-Fairness

###### Definition 4

(Block-Order-Fairness) For any two transactions $tx_{1}$ and $tx_{2}$, let $n$
validator nodes receive both transactions in a given time-frame and let
${\alpha}>\frac{1}{2}$. Block-Order-Fairness states that if at least
${\alpha}n$ nodes receive $tx_{1}$ before $tx_{2}$, then for every honest node
$j$, $j$ does not deliver $tx_{1}$ in a later block than it delivers $tx_{2}$.

The last two definitions are weaker notions of order-fairness. These two
definitions have inherent limitations related to the network model and
relative measures. To overcome these limitations, Cachin et al. [45] presented
a new notion of order-fairness, which they call Differential Order-Fairness.

Although most of the above definitions are used in the context of Byzantine
consensus, these definitions can also be used to provide order-fairness in
DAG-based DLT protocols.

####  III-B2 Blind Order-Fairness

This provides MEV protection by committing to a transaction ordering without
seeing the content of the transactions. That means this type of ordering is
determined independently of transaction content. It is also referred to as
content-agnostic ordering. The natural way of performing such ordering is by
realizing through commit-reveal protocols.

The idea of a commit-reveal protocol for ordering is to first commit the
transactions and reveal the committed transactions once the ordering has
already been determined. Nevertheless, there is an inherent leakage of
metadata in this ordering which makes the ordering weaker compared to time-
based ordering. Helix protocol [39] employs commit-reveal to provide fair
order. Although Helix provides censorship resistance it suffers from order
manipulation due to metadata leakage.

The commit-reveal is performed by clients using some cryptographic primitive.
Clients send their encrypted transactions as commitments along with metadata
to the validator nodes. Then the consensus protocol commits to an ordering of
transactions. Later, the commitments are opened and the transactions are
executed. The commit-reveal step can be instantiated using different
cryptographic primitives. Heimbach and Wattenhofer [46] present a
Systematization of Knowledge of commit-reveal approaches using different
cryptographic primitives in on-chain and off-chain. These approaches can also
be helpful in DLT to perform the commit-reveal step. We present a brief
overview of some of these primitives and their usage in DLTs to achieve blind
order-fairness as follows.

  * •

Threshold Encryption Threshold encryption allows a threshold number of honest
validator nodes to retrieve committed transactions. In a threshold encryption
scheme, during setup, the validator nodes generate a public key, and the
corresponding secret key is shared among validator nodes. Using this scheme, a
client encrypts a transaction using a public key in the commit phase, later in
the reveal phase the message is decrypted using the decryption shares from a
threshold number of validator nodes.

Malkhi and Szalachowski [40] construct a DAG-based protocol Fino which employs
a threshold encryption scheme to achieve blind order-fairness. They also
present other approaches, i.e., verifiable secret sharing scheme [47], AVID-M
[48] to achieve blind order-fairness in DAG-based DLTs.

  * •

Trusted Execution Environment (TEE) A TEE is a hardware-protected secure area
that provides an isolated execution environment for code and data. Hence, it
provides confidentiality and integrity of code and data. The state-of-the-art
popular implementation of TEE includes Intel SGX [43] and ARM Trustzone [44].

To provide blind order-fairness, for a round, a client first generates a key
pair inside TEE and encrypts its transaction using the public key. TEE can be
programmed in a way such that the decryption key for the round is released
only after the ordering for the round has already been done. TEE-employed
order-fairness can be used in the DAG-based DLT such as Teegraph [49] which is
already designed using TEE.

  * •

Time-lock Puzzle Time-lock puzzle [50] can be used to encrypt the transaction
as a commitment and the decryption only takes place after enough time has
elapsed. For the time-lock puzzle to work in the ordering protocol, the global
time-lock parameters must be set so that only after the transaction ordering,
the encrypted transactions can be decrypted. Moreover, an adversary should not
be able to solve a time-lock puzzle faster than an honest client.

Another cryptographic primitive related to the time-lock puzzle is delay
encryption [51] where all clients encrypt their transactions under the same
key for a given round. Delay encryption has been used to provide fairness in
FairPoS consensus protocol [52]. These primitives have the potential to be
used in any DLTs.

###  III-C Fairness in terms of DLT Components

  1. 1.

Block-level Fairness: Achieving block-level fairness can be approached through
various methods. One approach involves establishing weak links that connect
the blocks of slow yet honest validators during the creation of new blocks in
the DLT. Attaining block-level fairness is challenging. However, some degree
of fairness can be achieved through the tip selection mechanism. If the
mechanism selects a tip from a distant past, there is a higher likelihood of
including the block from a slow honest validator in the ledger. However,
achieving this level of fairness necessitates validator nodes to possess
substantial storage capacity to store the complete DLT history, which can be
practically challenging to implement without any relaxation. Additionally,
discarding old blocks poses difficulties, as it may inadvertently remove
blocks from slow validators that were never added to the ledger. DAG-Rider and
Bullshark are protocols that employ weak links to achieve block-level
fairness.

  2. 2.

Transaction-level Fairness: This principle asserts that transactions received
by an honest validator node will eventually be included in the ledger.
Transaction-level fairness is particularly relevant for ensuring censorship
resistance and is considered a more realistic measure than block-level
fairness. To achieve transaction-level fairness, it is crucial for honest
validator nodes to promptly relay client transactions to the DLT network upon
receiving them. However, due to network connectivity issues, such as those
encountered by slow validator nodes, transactions or blocks may not reach all
nodes in the network. In such cases, transaction-level fairness can be upheld
by re-injecting the transactions from a non-committed block belonging to a
slow honest validator into a newly created block. This process ensures that
the transactions ultimately find their way into the ledger.

##  IV Discussion

In the ensuing discussion, we delve into various aspects and implications of
the findings presented in the preceding sections, shedding light on the
broader implications of the research and exploring potential avenues for
further investigation. In a DLT, fairness notions are directly or indirectly
affected by different components or functionalities plugged into it. In this
section, we elaborate on the relation of some of these components with
fairness notions.

###  IV-A Writing Access

Writing access permits nodes to propose and write blocks, hence progressing
the state of the ledger. A DLT protocol can pertain to a high degree of
parallelism by having concurrent writing access by all the participants.

The fairness experienced by participants in a system is influenced by the
writing access policies in place. In transaction-based DAG ledgers, where
nodes add transactions to the ledger, providing writing access to all nodes
ensures fairness among them. On the other hand, block-based DAG ledgers
involve different node roles (validator, miner, ordinary, follower), and only
a subset of nodes (such as miners) possess the permission to append blocks.
This restricted access can introduce fairness limitations to the system. Thus,
a more open writing access approach leads to a fairer system overall.
Currently, the prevailing writing access solutions in the field encompass PoW
and PoS-based lotteries, alongside the permissioned setting.

Let us mention a few works that allow more general writing access. Zhao et al.
[53] compose an improved access control mechanism for DAG-based DLTs to
improve the security and robustness of the network. The work focuses on
fairness in the aspect of network parameters such as fairness in dissemination
rate and latency. Cullen et al. [54] achieve fairness in an adversarial
environment by proposing an access control mechanism for DAG-based DLTs. They
ensure fairness during congestion using a notion of weighted max-min fairness
that shows each node gets a fair share of throughput weighted by the
reputation score of each node.

###  IV-B Garbage Collection

In DAG-based DLT protocols, nodes require unbounded memory to guarantee
validity and fairness. This arises the practical challenges for these
protocols to be deployed. Due to the requirement of unbounded memory, nodes
are not allowed to garbage collect the old rounds. Otherwise, an honest slow
node block might be garbage collected before being added to the DAG. As per
this scenario, garbage collection directly conflicts with fairness, especially
in an asynchronous network model where a block or message can be delayed for
an indefinite time. Garbage collection is a trade-off between fairness and
performance.

Narwhal [19] employs a garbage collection mechanism to clean the DAG up to a
certain round in the past from the genesis. Nevertheless, fairness at the
block-level is sacrificed because slow nodes might be garbage collected before
they get a chance to be ordered. Bullshark [8] on the other hand, achieves
fairness for all the nodes in an asynchronous network while having a garbage
collection mechanism in place. Bullshark gives a practical implementation
where nodes have bounded memory and fairness is achieved after Global
Stabilization Time (GST) during the period of synchrony.

The garbage collection mechanism is rather new in the DAG-based DLT space.
Mechanisms similar to the one in Bullshark can be adopted in other DAG-based
DLTs. This kind of mechanism is also required for any high-throughput DLT
since eventually, the underlying data structure has to be pruned.

###  IV-C Reward Mechanism

In distributed ledgers, the reward (incentive) mechanism plays a crucial role
to ensure fairness among the participants. The reward mechanism should reward
the nodes according to their effort put forward to make the protocol progress.

In the majority of DLTs, expected rewards are typically proportional to the
delivered Proof-of-Work (PoW) or Proof-of-Stake (PoS), as well as the
performance of the nodes, resulting in a fair distribution. However, as a
second-order effect, nodes with higher PoW or PoS tend to exhibit less
variance in their profits and incur lower costs in running their nodes. This
phenomenon can lead to centralization, where a small number of nodes with
significant resources dominate the network.

To address this potential centralization, many PoS systems impose a cap on the
maximum amount of staked funds. This limitation aims to create a more
decentralized and fairer distribution of rewards.

Several DAG-based DLTs do not have a reward mechanism as being “feeless” is an
advantage for those DAG-based DLTs, e.g., [6]. Moreover, a few DAG-based DLTs
e.g., Inclusive [23], Sphinx [55] employ reward mechanisms to increase network
participation, and Graphchain [56] introduces its reward mechanism to maintain
the DAG.

Some DLT protocols do not uniformly distribute the rewards and hence lack
fairness. For example, scalable BFT protocols [57] employing threshold
signature distribute the rewards to every node no matter whether the node
participated or not. Nonetheless, Kokoris-Kogias [58] builds a fair reward
mechanism in the novel design of robust and scalable BFT protocol which can be
deployed in BFT-based DLT.

In SUI protocol [59], which is based on Bullshark [8], fairness is achieved by
rewarding validators based on their behavior and performance, as perceived by
other validators. This is done through subjective reporting which is then used
as input into the stake reward distribution rule.

###  IV-D Tip Selection

In the Nakamoto consensus mechanism [1], each block refers to a single
previous block, resulting in an ever-extending chain. Conversely, DAG-based
systems allow blocks to reference multiple preceding blocks, leading to a more
intricate structure as opposed to a straightforward, linear chain. As a result
of this partial order of vertices in a constructed DAG, the tip selection
algorithm becomes an integral part of the associated consensus mechanism.
Fairness in the context of tip selection algorithms generally refers to an
equal opportunity for all transactions to get selected and validated
regardless of their origin, ensuring that no transaction gets left out. We
list a few tip selection algorithms:

  * •

Uniform Random Tip Selection To issue a new block, a node chooses tips to
approve uniformly at random from all good tips in the DAG until a fixed number
$k$ of references is created, e.g., IOTA [9, 60]. This algorithm is
specifically designed for synchronous network models and permissionless DAG-
based DLTs since the size of the references should be negligible compared to
the block size. A good tip refers to a tip that is valid and consistent with
the finalized ledger and issued rather recently. Such tip selection gives a
fair chance to all good tips in the tip pool to be referenced and eventually
approved. Moreover, it leads to a Nash Equilibrium, i.e., knowing that other
nodes select tips with equal probabilities, a given node has nothing to gain
from deviating from this behavior, see [61].

  * •

Round-based Tip Selection To issue a new block at round $r$, a node chooses at
least $n-f$ tips in the DAG from round $r-1$, e.g., Aleph [29], Bullshark [8],
Cordial Miners [30], DAG-Rider [18], Tusk [19]. Such round-based tip selection
algorithms are used in permissioned DAG-based DLT protocols which work under
partially synchronous or asynchronous network models. The number $n-f$ is the
maximum guaranteed number of tips one can expect if $f$ nodes are faulty or
Byzantine. Moreover, certain protocols [8, 18], offer some sort of fairness to
slower nodes. This is achieved by allowing nodes to reference blocks from
previous rounds using weak links. These weak links facilitate the inclusion of
transactions from slower nodes into the ledger, while not being utilized for
voting purposes.

  * •

Heaviest Cluster Tip Selection To issue a new block, a node selects all tips
from the heaviest cluster, the largest subset of blocks in the DAG, in which
each block is not comparable by the partial order with at most a constant
number of other blocks, e.g., Phantom [27], DAG-KNIGHT [28]. This approach
achieves certain fairness as a new block references all existing tips in the
heaviest subDAG.

  * •

Sub-sampled Voting Tip Selection To issue a new block, a node first queries
small random samples of other nodes and based on their responses finds the
tips that are likely to be approved by the network, e.g., [62] and [9]. Due to
its nature, the algorithm works with permissionless DAG-based DLT protocols.
This tip selection algorithm is considered fair as with a high probability it
reflects the preference of the majority of the network.

###  IV-E Smart Contract Architecture

The increased level of parallelism in DAG-based DLTs shows promise in
addressing contention issues within UTXO, Cardano, and object-based smart
contracts like SUI [63]. These smart contracts offer distinct advantages
compared to account-based smart contracts, particularly in terms of
determinism. The deterministic nature of these smart contracts significantly
reduces the occurrence of Miner Extractable Value (MEV) possibilities.

The inherent deterministic execution model and parallelism in object-based
smart contract systems provide notable advantages in terms of fairness,
scalability, and security. The deterministic nature of object-based smart
contracts ensures predictable outcomes, facilitating auditing and verification
processes. Overall, these advantages position object-based smart contracts as
an attractive option for achieving fairness and performance in decentralized
applications within the context of DAG-based DLTs.

##  V Conclusion

In this study, we have conducted a thorough analysis of fairness in DAG-based
DLTs, defining different notions and examining their entanglement with DLT
components. Promising research directions include exploring alternative
methods for fairness without weak references and investigating cryptographic
schemes for blind order-fairness. By addressing these areas, we can enhance
the understanding and implementation of fairness in DAG-based DLTs, fostering
more equitable and robust systems.

## References

  * [1] S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” _Decentralized business review_ , p. 21260, 2008.
  * [2] F. Tschorsch and B. Scheuermann, “Bitcoin and beyond: A technical survey on decentralized digital currencies,” _IEEE Communications Surveys & Tutorials_, vol. 18, no. 3, pp. 2084–2123, 2016.
  * [3] L. Gudgeon, P. Moreno-Sanchez, S. Roos, P. McCorry, and A. Gervais, “Sok: Layer-two blockchain protocols,” in _Financial Cryptography and Data Security: 24th International Conference, FC 2020, Kota Kinabalu, Malaysia, February 10–14, 2020 Revised Selected Papers 24_. Springer, 2020, pp. 201–226.
  * [4] G. Wang, Z. J. Shi, M. Nixon, and S. Han, “Sok: Sharding on blockchain,” in _Proceedings of the 1st ACM Conference on Advances in Financial Technologies_ , 2019, pp. 41–61.
  * [5] Y. Sompolinsky and A. Zohar, “Accelerating bitcoin’s transaction processing. fast money grows on trees, not chains,” _Cryptology ePrint Archive_ , 2013\.
  * [6] S. Popov, “The tangle,” _White paper_ , vol. 1, no. 3, p. 30, 2018.
  * [7] Q. Wang, J. Yu, S. Chen, and Y. Xiang, “Sok: Dag-based blockchain systems,” _ACM Computing Surveys_ , vol. 55, no. 12, pp. 1–38, 2023.
  * [8] A. Spiegelman, N. Giridharan, A. Sonnino, and L. Kokoris-Kogias, “Bullshark: Dag bft protocols made practical,” in _Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security_ , 2022, pp. 2705–2718.
  * [9] S. Popov, H. Moog, D. Camargo, A. Capossele, V. Dimitrov, A. Gal, A. Greve, B. Kusmierz, S. Mueller, A. Penzkofer _et al._ , “The coordicide,” _Accessed Jan_ , pp. 1–30, 2020.
  * [10] M. Conti, E. S. Kumar, C. Lal, and S. Ruj, “A survey on security and privacy issues of bitcoin,” _IEEE Communications Surveys & Tutorials_, vol. 20, no. 4, pp. 3416–3452, 2018.
  * [11] Y. Amoussou-Guenou, A. Del Pozzo, M. Potop-Butucaru, and S. Tucci-Piergiovanni, “On fairness in committee-based blockchains,” _arXiv preprint arXiv:1910.09786_ , 2019.
  * [12] Y. Huang, J. Tang, Q. Cong, A. Lim, and J. Xu, “Do the rich get richer? fairness analysis for blockchain incentives,” in _Proceedings of the 2021 International Conference on Management of Data_ , 2021, pp. 790–803.
  * [13] K. Kursawe, “Wendy, the good little fairness widget: Achieving order fairness for blockchains,” in _Proceedings of the 2nd ACM Conference on Advances in Financial Technologies_ , 2020, pp. 25–36.
  * [14] M. Kelkar, F. Zhang, S. Goldfeder, and A. Juels, “Order-fairness for byzantine consensus,” in _Advances in Cryptology–CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part III 40_. Springer, 2020, pp. 451–480.
  * [15] S. Yang, F. Zhang, K. Huang, X. Chen, Y. Yang, and F. Zhu, “Sok: Mev countermeasures: Theory and practice,” _arXiv preprint arXiv:2212.05111_ , 2022.
  * [16] EIGENPHI, “MEV Outlook 2023: Walking Through the Dark Forest,” Feb 2023, accessed: 15-Jun-2023. [Online]. Available: https://eigenphi.substack.com/p/mev-outlook-2023
  * [17] G. Birmpas, E. Koutsoupias, P. Lazos, and F. J. Marmolejo-Cossío, “Fairness and efficiency in dag-based cryptocurrencies,” in _Financial Cryptography and Data Security: 24th International Conference, FC 2020, Kota Kinabalu, Malaysia, February 10–14, 2020 Revised Selected Papers_. Springer, 2020, pp. 79–96.
  * [18] I. Keidar, E. Kokoris-Kogias, O. Naor, and A. Spiegelman, “All you need is dag,” in _Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing_ , 2021, pp. 165–175.
  * [19] G. Danezis, L. Kokoris-Kogias, A. Sonnino, and A. Spiegelman, “Narwhal and tusk: a dag-based mempool and efficient bft consensus,” in _Proceedings of the Seventeenth European Conference on Computer Systems_ , 2022, pp. 34–50.
  * [20] L. Vigneri, W. Welz, A. Gal, and V. Dimitrov, “Achieving fairness in the tangle through an adaptive rate control algorithm,” in _2019 IEEE International Conference on Blockchain and Cryptocurrency (ICBC)_. IEEE, 2019, pp. 146–148.
  * [21] L. Vigneri and W. Welz, “On the fairness of distributed ledger technologies for the internet of things,” in _2020 IEEE International Conference on Blockchain and Cryptocurrency (ICBC)_. IEEE, 2020, pp. 1–3.
  * [22] S. Müller, A. Penzkofer, D. Camargo, and O. Saa, “On fairness in voting consensus protocols,” in _Intelligent Computing: Proceedings of the 2021 Computing Conference, Volume 2_. Springer, 2021, pp. 927–939.
  * [23] Y. Lewenberg, Y. Sompolinsky, and A. Zohar, “Inclusive block chain protocols,” in _Financial Cryptography and Data Security: 19th International Conference, FC 2015, San Juan, Puerto Rico, January 26-30, 2015, Revised Selected Papers 19_. Springer, 2015, pp. 528–547.
  * [24] G. Wood _et al._ , “Ethereum: A secure decentralised generalised transaction ledger,” _Ethereum project yellow paper_ , vol. 151, no. 2014, pp. 1–32, 2014.
  * [25] A. Churyumov, “Byteball: A decentralized system for storage and transfer of value,” _URL https://byteball. org/Byteball. pdf_ , p. 11, 2016.
  * [26] Y. Sompolinsky, Y. Lewenberg, and A. Zohar, “Spectre: A fast and scalable cryptocurrency protocol,” _Cryptology ePrint Archive_ , 2016.
  * [27] Y. Sompolinsky and A. Zohar, “Phantom,” _IACR Cryptology ePrint Archive, Report 2018/104_ , 2018.
  * [28] Y. Sompolinsky and M. Sutton, “The dag knight protocol: A parameterless generalization of nakamoto consensus,” _Cryptology ePrint Archive_ , 2022\.
  * [29] A. Gagol, D. Leśniak, D. Straszak, and M. Świetek, “Aleph: Efficient atomic broadcast in asynchronous networks with byzantine nodes,” in _Proceedings of the 1st ACM Conference on Advances in Financial Technologies_ , 2019, pp. 214–228.
  * [30] I. Keidar, O. Naor, and E. Shapiro, “Cordial miners: A family of simple, efficient and self-contained consensus protocols for every eventuality,” _arXiv preprint arXiv:2205.09174_ , 2022.
  * [31] Y. Amir, B. Coan, J. Kirsch, and J. Lane, “Prime: Byzantine replication under attack,” _IEEE transactions on dependable and secure computing_ , vol. 8, no. 4, pp. 564–577, 2010.
  * [32] A. Miller, Y. Xia, K. Croman, E. Shi, and D. Song, “The honey badger of bft protocols,” in _Proceedings of the 2016 ACM SIGSAC conference on computer and communications security_ , 2016, pp. 31–42.
  * [33] K. Lev-Ari, A. Spiegelman, I. Keidar, and D. Malkhi, “Fairledger: A fair blockchain protocol for financial institutions,” _arXiv preprint arXiv:1906.03819_ , 2019.
  * [34] S. Duan, K. Levitt, H. Meling, S. Peisert, and H. Zhang, “Byzid: Byzantine fault tolerance from intrusion detection,” in _2014 IEEE 33rd International Symposium on Reliable Distributed Systems_. IEEE, 2014, pp. 253–264.
  * [35] P.-L. Aublin, S. B. Mokhtar, and V. Quéma, “Rbft: Redundant byzantine fault tolerance,” in _2013 IEEE 33rd International Conference on Distributed Computing Systems_. IEEE, 2013, pp. 297–306.
  * [36] L. Baird, M. Harmon, and P. Madsen, “Hedera: A public hashgraph network & governing council,” _White Paper_ , vol. 1, pp. 9–10, 2019.
  * [37] C. Stathakopoulou, T. David, M. Pavlovic, and M. Vukolić, “Mir-bft: High-throughput robust bft for decentralized networks,” _arXiv preprint arXiv:1906.05552_ , 2019.
  * [38] C. Huang, Z. Wang, H. Chen, Q. Hu, Q. Zhang, W. Wang, and X. Guan, “Repchain: A reputation-based secure, fast, and high incentive blockchain system via sharding,” _IEEE Internet of Things Journal_ , vol. 8, no. 6, pp. 4291–4304, 2020.
  * [39] A. Asayag, G. Cohen, I. Grayevsky, M. Leshkowitz, O. Rottenstreich, R. Tamari, and D. Yakira, “A fair consensus protocol for transaction ordering,” in _2018 IEEE 26th International Conference on Network Protocols (ICNP)_. IEEE, 2018, pp. 55–65.
  * [40] D. Malkhi and P. Szalachowski, “Maximal extractable value (mev) protection on a dag,” _arXiv preprint arXiv:2208.00940_ , 2022.
  * [41] P. Daian, S. Goldfeder, T. Kell, Y. Li, X. Zhao, I. Bentov, L. Breidenbach, and A. Juels, “Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability,” in _2020 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2020, pp. 910–927.
  * [42] M. Barczentewicz, “Mev on ethereum: A policy analysis,” _ICLE White Paper_ , pp. 01–23, 2023.
  * [43] V. Costan and S. Devadas, “Intel sgx explained,” _Cryptology ePrint Archive_ , 2016.
  * [44] S. Pinto and N. Santos, “Demystifying arm trustzone: A comprehensive survey,” _ACM computing surveys (CSUR)_ , vol. 51, no. 6, pp. 1–36, 2019.
  * [45] C. Cachin, J. Mićić, N. Steinhauer, and L. Zanolini, “Quick order fairness,” in _Financial Cryptography and Data Security: 26th International Conference, FC 2022, Grenada, May 2–6, 2022, Revised Selected Papers_. Springer, 2022, pp. 316–333.
  * [46] L. Heimbach and R. Wattenhofer, “Sok: Preventing transaction reordering manipulations in decentralized finance,” _arXiv preprint arXiv:2203.11520_ , 2022.
  * [47] A. Shamir, “How to share a secret,” _Communications of the ACM_ , vol. 22, no. 11, pp. 612–613, 1979.
  * [48] Y. Zhang, S. Setty, Q. Chen, L. Zhou, and L. Alvisi, “Byzantine ordered consensus without byzantine oligarchy,” _Cryptology ePrint Archive_ , 2020\.
  * [49] X. Fu, H. Wang, P. Shi, and X. Zhang, “Teegraph: A blockchain consensus algorithm based on tee and dag for data sharing in iot,” _Journal of Systems Architecture_ , vol. 122, p. 102344, 2022.
  * [50] R. L. Rivest, A. Shamir, and D. A. Wagner, “Time-lock puzzles and timed-release crypto,” _Massachusetts Institute of Technology. Laboratory for Computer Science_ , 1996.
  * [51] J. Burdges and L. De Feo, “Delay encryption,” in _Advances in Cryptology–EUROCRYPT 2021: 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part I_. Springer, 2021, pp. 302–326.
  * [52] J. H.-y. Chiang, B. David, I. Eyal, and T. Gong, “Fairpos: Input fairness in proof-of-stake with adaptive security,” _Cryptology ePrint Archive_ , 2022\.
  * [53] L. Zhao, L. Vigneri, A. Cullen, W. Sanders, P. Ferraro, and R. Shorten, “Secure access control for dag-based distributed ledgers,” _IEEE Internet of Things Journal_ , vol. 9, no. 13, pp. 10 792–10 806, 2021.
  * [54] A. Cullen, P. Ferraro, W. Sanders, L. Vigneri, and R. Shorten, “Access control for distributed ledgers in the internet of things: A networking approach,” _IEEE Internet of Things Journal_ , vol. 9, no. 3, pp. 2277–2292, 2021.
  * [55] Q. Wang and R. Li, “A weak consensus algorithm and its application to high-performance blockchain,” in _IEEE INFOCOM 2021-IEEE Conference on Computer Communications_. IEEE, 2021, pp. 1–10.
  * [56] X. Boyen, C. Carr, and T. Haines, “Graphchain: A blockchain-free scalable decentralised ledger,” in _Proceedings of the 2nd ACM Workshop on Blockchains, Cryptocurrencies, and Contracts_ , 2018, pp. 21–33.
  * [57] G. Gueta, I. Abraham, S. Grossman, D. Malkhi, B. Pinkas, M. REITER, D. SEREDINSCHI, O. Tamir, and A. Tomescu, “Sbft: a scalable decentralized trust infrastructure for blockchains, 2018,” 1804.
  * [58] E. Kokoris-Kogias, “Robust and scalable consensus for sharded distributed ledgers,” _Cryptology ePrint Archive_ , 2019.
  * [59] The Mysten Labs Team, “The sui smart contracts platform: Economics and incentives,” 2022, accessed: 17.06.2023. [Online]. Available: https://github.com/MystenLabs/sui/blob/main/doc/paper/tokenomics.pdf
  * [60] S. Müller, A. Penzkofer, N. Polyanskii, J. Theis, W. Sanders, and H. Moog, “Tangle 2.0 leaderless nakamoto consensus on the heaviest dag,” _IEEE Access_ , vol. 10, pp. 105 807–105 842, 2022.
  * [61] S. Popov, O. Saa, and P. Finardi, “Equilibria in the tangle,” _Computers & Industrial Engineering_, vol. 136, pp. 160–172, 2019.
  * [62] T. Rocket, M. Yin, K. Sekniqi, R. van Renesse, and E. G. Sirer, “Scalable and probabilistic leaderless bft consensus through metastability,” _arXiv preprint arXiv:1906.08936_ , 2019.
  * [63] The Mysten Labs Team, “The sui smart contracts platform,” 2022, accessed: 17.06.2023. [Online]. Available: https://github.com/MystenLabs/sui/blob/main/doc/paper/sui.pdf