# Vision-Aided Beam Tracking: Explore the Proper Use of Camera Images with
Deep Learning

Yu Tian, Chenwei Wang Email: {yu.tian<EMAIL_ADDRESS>DOCOMO
Innovations Inc., Palo Alto, CA 94304

###### Abstract

We investigate the problem of wireless beam tracking on mmWave bands with the
assistance of camera images. In particular, based on the user’s beam indices
used and camera images taken in the trajectory, we predict the optimal beam
indices in the next few time spots. To resolve this problem, we first
reformulate the “ViWi” dataset in [1] to get rid of the image repetition
problem. Then we develop a deep learning approach and investigate various
model components to achieve the best performance. Finally, we explore whether,
when, and how to use the image for better beam prediction. To answer this
question, we split the dataset into three clusters – (LOS, light NLOS, serious
NLOS)-like – based on the standard deviation of the beam sequence. With
experiments we demonstrate that using the image indeed helps beam tracking
especially when the user is in serious NLOS, and the solution relies on
carefully-designed dataset for training a model. Generally speaking, including
NLOS-like data for training a model does not benefit beam tracking of the user
in LOS, but including light NLOS-like data for training a model benefits beam
tracking of the user in serious NLOS.

##  I Introduction

Geared towards supporting substantial latency reduction and massive
connectivity, the mmWave deployment is expected to be a key in 5G/B5G.
Compared to their sub-6GHz counterparts, the channel on mmWave bands change
much faster due to higher Doppler, thereby making accurate and timely channel
acquisition challenging in applications, such as channel inference, user
localization, and beam tracking. Contrary to the conventional beam tracking
that relies on the pilot-based channel estimation within a coherent block,
machine learning has been attractive to perform proactive beam prediction.
While this approach can deal with the users in the line-of-sight (LOS)
scenarios, it will likely struggle in real wireless environments with multiple
users, multiple blockages, and rich dynamics [1]. In response to that,
Alrabeiah _et al._ recently developed a dataset named for “ViWi” [3, 1]. The
scenario is characterized by two base stations (BSs), static objects, and
dynamic objects, including persons, cars, trucks and buses with different
speeds. While the BSs are positioned on the opposite sides of the street to
cover the entire street, the transmitted signal could be LOS, NLOS, and
blocked. Moreover, three RGB cameras are installed in each BS and takes photos
of certain part of the street. For each user, each BS aims to proactively
predict the optimal beam in the next few time spots.

The turn to visual data as a supplementary information for beam tracking is
motivated by two key factors: (i) the fact that images are rife with
information about the environments they are depicting, and (ii) the major
strides computer vision has taken in image comprehension with the help of deep
learning. _Compared to using the beam only, whether, when, and how to use the
image for better beam prediction_ are of interest.

The research interests in vision-aided wireless applications are skyrocketing
in academia in recent two years. Starting from [4], Alrabeiah _et al._
investigated mmWave link blockage prediction and beam prediction. Assuming
each image contains only one object, they directly applied classical image
classification models for prediction. Later, when they investigated vision-
aided mmWave beam tracking in [3] by using the beam sequence only, they also
offered a dataset where each image could contain multiple moving objects, but
which user is the target is unknown111In practice, this assumption might be
little ill-posed, as without knowing which object in the image is the target,
one cannot claim that user is in the covered area of that camera. Admittedly,
this assumption reduces the difficulty from the actual situation, and could be
a start vision-aided beam tracking.. Similar to the baseline in [3] but
replacing the uni-GRU with bi-LSTM and bi-GRU, [5] performed $3\%$ (slightly)
better. Then in [2], Alrabeiah _et al._ investigated signal blockage
prediction. In particular, object detection was applied to extract the image
features, followed by further feature embedding. Finally, the sequential image
feature embedding and beam embedding were alternatively fed to a uni-GRU for
supervised learning. Still in 2020, as the data competition task at IEEE ICC,
vision-aided beam tracking attracted nine teams [1]. Although the approaches
of the participants have not been available in public, the most interesting
observation is that even compared to the baseline in [3], the scores of all
the submissions were much worse in the test dataset (for participants only)
[1]. This is usually caused by either over-fitting or more likely, in the
competition, the different data distribution of unseen test dataset from the
training and validation datasets. The most recent work on resolving this
competition task was shown by Tian _et al._ in [6] where a new deep learning
model based on ResNet and ResNeXt was proposed to embed the image. Leveraging
the power of deeper models, they achieved significantly better scores than
those in literature. However, it is still not clear whether the performance is
significantly improved by the use of powerful deeper and complicated model for
better processing the beam sequence only or the image sequence as well.

In this paper, we investigate the problem of vision-aided beam tracking
defined in [1] but with a reformulated new dataset from the “ViWi” dataset in
[1]. More importantly, we shed light on the question compared to using the
beam only, whether, when, and how to use the image for better beam prediction.
Our contribution can be summarized as follows.

Firstly, in the original “ViWi” dataset, the training and validation datasets
share _nearly all_ the images in common. In practice, after a model is
trained, the images in the validation dataset should not be seen before even
they are taken from the same environment. Thus, for all the prior results in
[3, 5, 6], whatever the performance scores have been achieved, it is not clear
if the model performs well in validation because it is able to better learn
image features or it just memorizes the same image in training. To get rid of
the image repetition in both training and validation, we reformulate a new
dataset where the images in training and validation are mutually exclusive.

Second, we develop a deep learning approach based on the extension of the
model used for link blockage prediction in [2] with several variations.
Specifically, in the image feature extraction component we consider CNN, AE,
PCA, and in the sequential model component we consider uni-GRU and bi-GRU.
Finally, it turns out that the combination of AE and bi-GRU produces the best
performance metric value $0.687$.

Finally, during the process of model component selection and parameter tuning,
we are aware that compared to using the beam only, the benefit brought by
using the image for beam prediction readily becomes marginal when the model
becomes deeper and more complicated. Thus, we explore whether, when, and how
to use the image for better beam prediction. To answer this question, we split
the dataset into three clusters – (LOS, light NLOS, and serious NLOS)-like –
based on the standard deviation of the beam sequence. Our experiments
demonstrate that using the image indeed helps beam tracking especially when
the user is in serious NLOS, and the solution relies on carefully-designed
dataset for training a model.

##  II Problem Definition

The problem of vision-aided beam tracking and its evaluation metric were
introduced in [1]. For completeness, we briefly re-introduce them in this
section and then introduce the newly reformulated dataset from the ViWi
dataset in [1].

We assume that each BS is equipped with $N$ antennas operating in 28G Hz band.
For each user $u$ at time $t$, a beam ${\bf f}_{u}(t)$ is selected by the BS
from a predefined codebook $\mathcal{F}$ to serve it in the downlink. For
proactive beam prediction in each of the next $m$ time spots, the BS can
observe the used beams and the corresponding camera images in up to $\tau$
prior time spots. Given a fixed codebook $\mathcal{F}$, since the beam ${\bf
f}$ and its index $f$ form a one-to-one mapping, we define an observational
sequence for each user instance $u$ as

$\displaystyle{\bf S}_{u}(t)\\!=\\![(f_{u}(t\\!\\!-\\!\tau\\!+\\!1),{\bf
X}_{u}(t\\!\\!-\\!\tau\\!+\\!1)),\cdots,(f_{u}(t),{\bf X}_{u}(t))]\\!\\!\\!$
(1)

where ${\bf X}$ is a 3-D tensor representing the camera RGB image. Given an
observational sequence ${\bf S}(t)$, we aim to predict the best beams in the
next $m$ time instances, denoted by
$\hat{f}(t^{\prime}),~{}t^{\prime}=t+1\cdots,t+m$. The ground truth indices
for the next $m$ time spots are already given in the dataset, under the sense
of maximizing the received SNR at the user.

To compare how close the prediction $\hat{f}(t^{\prime})$ is to
$f^{*}(t^{\prime})$, we follow the metric proposed in [1]. Specifically,
define the score of next $m$ predictions over user instances of interest as

$\displaystyle\textrm{score}_{m}=\mathbb{E}_{u}\mbox{$\left[\exp\left(-\frac{1}{m\sigma}\sum_{t^{\prime}=t+1}^{t+m}\big{|}\hat{f}_{u}(t^{\prime})-f_{u}^{*}(t^{\prime})\big{|}\right)\right]$}$
(2)

where $\sigma$ is a predefined penalization factor. In Section IV, we will
leverage this definition and its variations for evaluation. To be consistent
with [1] and for comparison with the literature, we explore the metric of
TotalScore defined by:

$\displaystyle\textrm{TotalScore}=(\textrm{score}_{1}+3\cdot\textrm{score}_{3}+5\cdot\textrm{score}_{5})/9.$
(3)

###  II-A Dataset Description

In this section, we introduce the new training and validation datasets by
varying the Viwi dataset [1]. In the Viwi dataset, We denote by
$\mathcal{D^{\prime}}_{t}$ the training dataset that contains $281100$ user
instances (rows) and $\mathcal{D^{\prime}}_{v}$ the validation dataset with
$120468$ user instances (rows). Each instance has an observational sequence
${\bf S}(t)$ with length $\tau=8$ and the beam indices in the next $5$ time
spots. Meanwhile, each camera image in ${\bf S}(t)$ could contain multiple
objects and thus appear in multiple instances. Hence, the number of the camera
images in ${\bf S}(t)$ is only $23916$, much fewer than the instance number.

A closer observation of the Viwi dataset reveals that almost all the images in
$\mathcal{D^{\prime}}_{v}$ also exist in $\mathcal{D^{\prime}}_{t}$.
Specifically, out of the $23916$ images, only $13$ and $2$ images uniquely
appear in $\mathcal{D^{\prime}}_{t}$ and $\mathcal{D^{\prime}}_{v}$,
respectively, and all the other $23901$ images appear in both. As introduced
earlier, to avoid the possibility that a model performs well in
$\mathcal{D^{\prime}}_{v}$ just because it memorizes the images in
$\mathcal{D^{\prime}}_{t}$, we reformulate the datasets as follows:

$\displaystyle\mathcal{D}_{t}$
$\displaystyle\\!\\!\\!\\!\triangleq\\!\\!\\!\\!$
$\displaystyle\mathcal{D^{\prime}}_{t}[70251:210787]\cup\mathcal{D^{\prime}}_{v}[30141:90389],$
(4) $\displaystyle\mathcal{D}_{v1}$
$\displaystyle\\!\\!\\!\\!\triangleq\\!\\!\\!\\!$
$\displaystyle\mathcal{D^{\prime}}_{t}[:70251]\cup\mathcal{D^{\prime}}_{v}[:30141],$
(5) $\displaystyle\mathcal{D}_{v2}$
$\displaystyle\\!\\!\\!\\!\triangleq\\!\\!\\!\\!$
$\displaystyle\mathcal{D^{\prime}}_{t}[210787:]\cup\mathcal{D^{\prime}}_{v}[90389:],$
(6)

where $\mathcal{D}[a:b]$ represents the dataset $\mathcal{D}$ in the matrix
form from the $a^{th}$ to the $(b-1)^{th}$ rows, and the index count starts
from 0 (consistent with Python grammar). It can be verified that no data is
wasted and the images included in the three sets are mutually exclusive.
Moreover, $\mathcal{D}_{t}$ has $200,784$ instances with $11958$ images,
$1,993$ from each of the 6 cameras, respectively; $\mathcal{D}_{v1}$
($\mathcal{D}_{v2}$) has $100,392$ instances with $5979$ images, $1,993$ from
camera 1, 2, 3 (camera 4, 5, 6), respectively.

To this end, we guarantee that the images in each dataset are exclusive from
the others. Thus, one can (1) train a model on $\mathcal{D}_{t}$ and test it
on $\mathcal{D}_{v1}\cup\mathcal{D}_{v2}$; or (2) train a model on
$\mathcal{D}_{t}\cup\mathcal{D}_{v2}$ and test it on $\mathcal{D}_{v1}$, so
that the dataset size is close to that in the Viwi dataset [1]; or (3) train a
model on $\mathcal{D}_{t}$ and test it on $\mathcal{D}_{v1}$ and
$\mathcal{D}_{v2}$ separately, so as to investigate the prediction difference
between cameras 1, 2, 3 and cameras 4, 5, 6. Due to the page limit, we choose
the option (1) in this paper.

##  III The Proposed Scheme

In this section, we propose a deep learning model, extended from the model in
[2] for link blockage prediction. The proposed model consists of four
components – beam embedding, objective recognition for feature extraction,
feature embedding for further dimension reduction, and sequential model for
prediction. Although these components also exist in [2], the formulation is
not the same. In particular, we utilize a wider range of models to explore the
proper use of the images in this project. We introduce these four components
individually.

###  III-A Beam Embedding

To represent each beam index $f$ at time $t$ with a vector that can be fed
into the machine learning models, we can directly utilize its beamforming
vector ${\bf f}$ from the codebook $\mathcal{F}$. Similar to [3, 2], we
consider each vector ${\bf f}_{q}$ in $\mathcal{F}$ is independently draw from
a Gaussian distribution with zero mean and the identify matrix as
covariance222We also consider $\mathcal{F}$ as an orthogonal codebook owing to
its attributes of suppressing multi-user interference and less power
variations in wireless systems. However, based on our experiments, there is no
significant difference in the final performance evaluation and comparison.,
where the length of the ${\bf f}_{q}$ vector is assumed to be $2N$ as an
example. Note that this beam embedding process is straightforward as it does
not need any more than code generation and assignment.

###  III-B Objective Recognition for Feature Extraction

Considering the image dimension is much larger than the beam vector dimension,
we are inclined to extract image features. Recall that each image contains a
moving user of interest, but which user is of interest is unknown. Thus, we
can extract some information related to the user trajectories and thus reduce
the noise. With this goal, we apply objective detection. In this paper, we
utilize the well known pre-trained model – You Only Look Once (YOLO) [7, 8] –
to extract features for predetermined classes including persons, cars, trucks,
etc. To fit it in our problem, we retain the features at the last intermediate
layer before the prediction is made. Then, we have three options of the output
dimension: $[13,13,255]$, $[26,26,255]$, $[52,52,255]$. For speeding up the
computation process, we choose the option with $[13,13,255]$ as the output
size333For the other options with larger dimensions, although the recognition
resolution improves, more redundant information could also be involved as
noise. Thus, we start with the option with the smallest dimension size..

###  III-C Feature Embedding for Further Dimension Reduction

Since the output from objective detection is with the dimension of $13\times
13\times 255$ much larger than the beam embedding size $2N=256$, we tend to
further reduce the dimension via feature representation. Several approaches,
either supervised or unsupervised learning, can be used for dimension
reduction. In this paper, we consider three methods below:

  1. 1.

We use supervised learning by assigning one or multiple beam indices (w.r.t.
the users) to each image. Then we build a CNN-based model for multi-label
multi-class classification, and obtain the feature embedding from an
intermediate layer. Here, “multi-label” captures the multiple users appearing
in the same image, and “multi-class” is because of $N$ beams available to the
users.

  2. 2.

Since the dataset distribution is highly skewed in labels and classes, we
consider unsupervised learning – AutoEncoder (AE) – to represent each image at
the bottleneck. To deal with the heavier computation load of AE, in practice
the model can be trained offline, as long as the environment does not
significantly change.

  3. 3.

We consider PCA, a linear and fast-computational method for exploration and
comparison. Since feature embedding is only an intermediate component of the
entire model and it is unclear what kind of image processing is more favorable
for the end-to-end performance, we usually prefer a simpler scheme.

For the three methods introduced above, we set the embedding dimension as
$|{\bf f}_{q}|$ for uni-GRU and $|{\bf f}_{q}/4|$ for bi-GRU, the models that
we use in the next component. Generally, one can adjust the value so that
better algorithms might be discovered.

###  III-D Sequential Models for Prediction

Note that the processing components introduced above apply for each image and
beam only. Consider the observational sequence defined in Sec. II contains
$\tau$ time spots, we apply uni-GRU and bi-GRU models for beam prediction.

Another interesting question is how to incorporate the beam and image
embedding together efficiently. In this paper, we consider both alternatively
staggering them and concatenating them, which result in $2\tau\times|{\bf
f}_{q}|=16\times 256$-dimensional input to the uni-GRU and $\tau\times(|{\bf
f}_{q}|+|{\bf f}_{q}/4|)=8\times 320$-dimensional input to the bi-GRU,
respectively. We use $|{\bf f}_{q}/4|$ rather than $|{\bf f}_{q}|$ as the size
of the AE’s bottleneck for achieving better performance, and it can be better
tuned as well.

##  IV Experimental Results

In this section, we experiment on the proposed scheme introduced in Sec. III.
Besides the model parameters for each component, the general parameters for
training models include: optimizer: Adam, learning rate: 0.001, batch size:
1000, GRU layers: 4, GRU hidden layer dimension: 256, epoch number: 12 (for
bi-GRU) and 50 (for bi-GRU), dropout: 0.2, and the loss function: cross
entropy loss.

We start with the baselines by using beams only and then focus on improving
the performance with using the images.

###  IV-A Results of the Baseline Solutions

Four baselines by using beam sequence only are considered: (1) _The modified
baseline in[3]_: we consider the baseline introduced in [3] by changing the
uni-GRU layers from 1 to 4 and increasing the hidden layer dimension from 20
to 256 for achieving better performance. (2) _The last-step repetition
baseline_ : for each user instance, we repeat the last-step index in the
observational sequence as the next $m$ predictions. This is very simple, with
short memory, and can be directly performed on the validation dataset. (3)
_The linear regression baseline_ : we use linear regression to fit the beam
indices in the observational sequence and then apply it for prediction. (4)
_The statistical baseline_ : based on all data in the first $\tau=8$ columns
of the training dataset, we calculate the beam index distribution, from which
we randomly draw a beam index for each user instance in the validation as the
next $m$ predictions.

The results of the baselines above are shown in the first four rows of Table
I. It can be seen that the modified baseline in [3] generally performs the
best due to the use of deep learning, and both it and the last-step repetition
baseline perform much better than the other two. A little surprisingly, the
simple last-step repetition performs even $0.004$ better than the modified
baseline in [3] and with much cheaper computation, and the advantage is even
more significant, as large as $0.024$, in Score5. This is probably because the
user moves with a relatively low speed and/or in the LOS environment, and the
beam index also changes slowly. If the user moves in a relatively high speed
or in NLOS, then as Score5 suggests, deep learning might not be a good choice
for the beam only.

Models | Score1 | Score3 | Score5 | TotalScore
---|---|---|---|---
modified baseline in [3] | 0.862 | 0.642 | 0.517 | 0.597
Last-step repetition | 0.797 | 0.635 | 0.541 | 0.601
Linear regression | 0.358 | 0.324 | 0.298 | 0.313
Statistical baseline | 0.039 | 0.035 | 0.033 | 0.034
YOLO + PCA (256) | 0.857 | 0.638 | 0.517 | 0.595
YOLO + CNN (256) | 0.862 | 0.660 | 0.552 | 0.622
YOLO + AE (256) | 0.862 | 0.660 | 0.558 | 0.626
YOLO + AE (128) | 0.861 | 0.662 | 0.552 | 0.623
YOLO + AE (64) | 0.860 | 0.660 | 0.548 | 0.620
TABLE I: Performance of a variety of image feature extraction and embedding
methods with “uni-GRU beams + images” based on the modified dataset

###  IV-B Results of the Proposed Scheme by using uni-GRU

We apply the uni-GRU as the sequential model. For brevity, we use “model for
feature extraction + model for feature embedding (the output dimension)” to
represent the corresponding method. For example, “YOLO + PCA (256)” means we
apply YOLO to extract images features and PCA to further reduce the feature
dimension, and the output dimension is 256. The results are shown in the last
five rows of Table I.

Firstly, we compare the performance between PCA, AE, and CNN for feature
embedding (see the $5^{th}-7^{th}$ rows of Table I). First, AE outperforms the
PCA, e.g., the overall score of “YOLO + PCA (256)” is 0.595, which is 0.027
lower than “YOLO + AE (256)”. This is because AE can well learn non-linear
features and thus retains more information than PCA. Second, AE outperforms
the CNN, e.g., the overall score of “YOLO + CNN (256)” is 0.622, which is
0.004 lower than that of “YOLO + AE (256)”. Thus, the combination of YOLO and
AE turns out to be the best option in our experiment.

Next, we investigate the performances with varying the embedding dimension.
Consider the “YOLO + AE” as an example (see the $7^{th}-9^{th}$ rows of Table
I). When we change the output dimension from 256 to 128 and 64, the overall
score decreases from 0.626 to 0.623 and 0.620, which are dominated by Score5.
This is again consistent with our expectation, because the features with
larger dimensions can retain more information and benefit the larger multi-
step ahead prediction.

Finally, we apply the same model on the original ViWi dataset [1] and obtained
the four scores $0.867$, $0.6894$, $0.588$, $0.653$ like in Table I,
respectively. The comparison reveals that the experimental performance on our
reformulated dataset in Sec. II-A significantly drops. For example, for the
“YOLO + AE (256)”, the overall score for the modified dataset drops from 0.653
to 0.626, which is consistent with our expectation.

###  IV-C Results of the Proposed Scheme by using bi-GRU

We also play the bi-GRU model for the beam prediction. The results are shown
in the first two rows of Table II. The overall score is $0.687$, which is
$0.061$ higher than the best using uni-GRU in Table I. However, we also note
that the score $0.687$ is achieved regardless of the use of the image. Thus,
we can conclude the performance improvement does _not_ come from using the
image. In fact, for the use of the image sequence, while it helps the beam
prediction by providing more useful underlying features behind the
environment, it may also neutralize the additional benefits brought by the use
of the image. Thus, with the use of bi-GRU, it is of interest whether the
image is useful for beam prediction. We will address this interesting and non-
straightforward question in Sec. V.

Observation sequence | Score1 | Score3 | Score5 | TotalScore
---|---|---|---|---
beam only with $\tau=8$ | 0.856 | 0.717 | 0.635 | 0.687
beam + image with $\tau=8$ | 0.857 | 0.717 | 0.635 | 0.687
beam + image with $\tau=6$ | 0.854 | 0.714 | 0.625 | 0.680
beam + image with $\tau=4$ | 0.846 | 0.700 | 0.605 | 0.663
TABLE II: Performance w.r.t. the observation sequence length using the model
of “bi-GRU beams + images”

###  IV-D Trade-off between Memory Size $\tau$ and Performance

Usually, the larger $\tau$, the better (or no worse) prediction. However, a
larger $\tau$ also implies the need for higher computation and larger memory.
Thus, one may ask what a reasonable value of $\tau$ achieves a certain
performance. By varying the value of $\tau$ (and changing the input size of
the model), we obtain the prediction results in the last three rows of Table
II, indicating the longer observational sequence indeed benefits the
prediction. For example, with $\tau=4$ the model achieves $0.605$ for $m=5$,
and can be readily improved to $0.625$ and $0.635$ for the settings with
$\tau=6,~{}8$, respectively, which also implies marginal diminishing return.
To achieve the target performance, we expect $\tau$ as smaller as possible,
e.g., $\tau=6$ suffices to achieve 0.85 as the target score for $m=1$. Using
$\tau=8$ can only bring marginal improvement, and requires much heavier
computational load and $33\%$ more storage.

##  V Does the Image Really Assist Beam Prediction?

In this section, we follow the question in Sec. IV-C and try to shed light on
how to properly use the image in addition to the beam for beam prediction with
bi-GRU. In addition, on the ICC competition website, it is interesting that
the highest score of the participants is only 0.38433, even much lower than
the modified baseline and the last-step prediction by using beam only shown in
Table I. We suspect that the unseen test dataset might contain many more
moving users in NLOS areas, because the user in NLOS would see more unstable
beam over time than in LOS. Since the ViWi dataset does not tell whether each
user instance is in LOS or NLOS area, we propose to use the standard deviation
(std) of the beam index sequence to indicate the sequence stability, i.e., the
larger std, the more unstable, and thus more likely to be in NLOS.

With two predetermined std thresholds to form three cluster intervals,
representing LOS-like, light NLOS-like, and serious NLOS-like, we assign each
user instance to one cluster. As an example, we use $\mathcal{D}_{t}$ for
training and $\mathcal{D}_{v1}[:5000]$ for validation444This assumption is
made to investigate if the training and validation datasets contain quite
different ratio between the numebrs of LOS/NLOS-like data instances. In
particular, the std of the beam sequences in $\mathcal{D}_{t}$ is with mean
4.922 and median 0.484, but with 7.842 and median 1.378 for
$\mathcal{D}_{v1}[:5000]$. Moreover, the percentage of the user instances with
constant beam indices, i.e,, std$=0$, reduces from $38.74\%$ for
$\mathcal{D}_{t}$ to only $20.6\%$ for $\mathcal{D}_{v1}[:5000]$, nearly
$50\%$ off. Hence, we conclude the significant decrease in score is due to the
fact that more links are NLOS in testing than in training.. By choosing “0”
and “2” as the std thresholds, each dataset can be split into three subsets.
For brevity, we name each subset with a corresponding letter as shown in Table
III. The results are shown in Table IV for Score5 only.

std range | std = 0 | 0 $<$ std $\leq$ 2 | std $>$ 2
---|---|---|---
Training $\mathcal{D}_{t}$ | $\mathcal{A}_{t}$ | $\mathcal{B}_{t}$ | $\mathcal{C}_{t}$
Validation $\mathcal{D}_{v1}[:5000]$ | $\mathcal{A}_{v}$ | $\mathcal{B}_{v}$ | $\mathcal{C}_{v}$
TABLE III: The names of subsets w.r.t. the std ranges Training | Validation | beams only | beams + images
---|---|---|---
$\mathcal{A}_{t}$ | $\mathcal{A}_{v}$ | 0.593 | 0.595
$\mathcal{A}_{t}\cup\mathcal{B}_{t}\cup\mathcal{C}_{t}=\mathcal{D}_{t}$ | $\mathcal{A}_{v}$ | 0.583 | 0.585
$\mathcal{B}_{t}$ | $\mathcal{B}_{v}$ | 0.471 | 0.474
$\mathcal{A}_{t}\cup\mathcal{B}_{t}$ | $\mathcal{B}_{v}$ | 0.480 | 0.481
$\mathcal{A}_{t}\cup\mathcal{B}_{t}\cup\mathcal{C}_{t}=\mathcal{D}_{t}$ | $\mathcal{B}_{v}$ | 0.467 | 0.470
$\mathcal{C}_{t}$ | $\mathcal{C}_{v}$ | 0.275 | 0.279
$\mathcal{B}_{t}\cup\mathcal{C}_{t}$ | $\mathcal{C}_{v}$ | 0.279 | 0.290
$\mathcal{A}_{t}\cup\mathcal{B}_{t}\cup\mathcal{C}_{t}=\mathcal{D}_{t}$ | $\mathcal{C}_{v}$ | 0.279 | 0.280
TABLE IV: Score5 performances of the model using “bi-GRU beams + images” under
different link situation

Firstly, let us look at each individual validation subset: (1) for the LOS-
like case, we train two models on $\mathcal{A}_{t}$ and $\mathcal{D}_{t}$ and
validate them on $\mathcal{A}_{v}$, respectively (see the first two rows of
Table IV). It can be seen that including NLOS-like data to train the model
actually hurts the model performance in validation. In addition, no matter for
which model, using the image brings extra $0.002$ improvement in the score.
(2) for the light NLOS-like case, we train three models on three datasets and
validate them on $\mathcal{B}_{v}$, respectively (see the middle three rows of
Table IV). Compared to training on $\mathcal{B}_{t}$ only, interestingly, it
implies including LOS-like data $\mathcal{A}_{t}$ significantly help the model
in validation, but including serious NLOS-like data $\mathcal{C}_{t}$
significantly hurts the model in validation. (3) for the serious NLOS-like
case, we train three models on three datasets and validate them on
$\mathcal{C}_{v}$, respectively (see the last three rows of Table IV).
Compared to training on $\mathcal{C}_{t}$ only, interestingly, it shows
including light NLOS-like data $\mathcal{B}_{t}$ significantly help the model
in validation, but further including LOS-like data $\mathcal{A}_{t}$
surprisingly neutralizes the benefits. While for beam only, the improvement
can achieve $0.004$, but when the image come to play, there is no significant
improvement anymore.

Second, from the LOS-like to the light NLOS-like and then to the serious NLOS-
like, the scores of “beam only” and “beam $+$ image” both significantly drop,
suggesting that NLOS is the main obstacle. Moreover, the score improvement
owing to the use of the image turn out to be $0.002$, $0.001$, $0.011$,
respectively. While the first two numbers imply the improvement is very
marginal, the last number indicates the image use can significantly improve
the beam prediction for the user in serious NLOS environment, and the non-
straightforward solution is to include the light NLOS-like data but not the
LOS-like as extra data augmentation to train the model.

Finally, adding up the scores of the three clusters weighted by the
cardinality of each cluster results in TotalScore $=0.426$, significantly
higher than $0.414$ obatined by training on $\mathcal{D}_{t}$ and validation
on $\mathcal{D}_{v}$. This suggests incorporating data clustering helps beam
prediction of the user in serious NLOS-like cases.

To conclude, splitting the user instances according their link LOS/NLOS status
can improve the prediction performance especially in the NLOS, and the key is
to find an appropriate subset of the training dataset for training a model.
Note that here we consider only three clusters, and many insights are already
non-trivial. If we consider more clusters, it is much harder to design a
systematic approach to find the optimal combination of the corresponding
subsets for training a model.

##  VI Conclusion

For vision-aided beam tracking, we developed a deep learning approach via beam
embedding, image recognition, image feature embedding, and sequential models,
and the experimental results suggest the overall score $0.687$ can be achieved
in a variation of ViWi dataset in [1]. We also explore the proper use of the
image for better beam prediction than using the beam only. Our experiments
demonstrate that using the image indeed improves the beam prediction
particularly when the user is in NLOS-like environment, and the key is to
carefully design the dataset with clustering for training a model. Future work
could include improving the beam prediction for the user in NLOS via
developing better models and obtaining higher-quality data that can better
reflect the use cases, and interpreting the performance score with real system
metrics.

## References

  * [1] The official website of the vision-aided beam tracking data competition at IEEE ICC 2020: “ https://viwi-dataset.net/viwi-bt.html.”
  * [2] M. Alrabeiah and A. Alkhateeb, “Deep learning for mmwave beam and blockage prediction using sub-6 ghz channels,” IEEE Transactions on Communications, vol. 68, no. 9, pp. 5504–5518, 2020.
  * [3] M. Alrabeiah, J. Booth, A. Hredzak, and A. Alkhateeb, “Viwi visionaided mmWave beam tracking: Dataset, task, and baseline solutions,” arXiv preprint arXiv:2002.02445, 2020.
  * [4] M. Alrabeiah, A. Hredzak, and A. Alkhateeb, “Millimeter Wave Base Stations with Cameras: Vision Aided Beam and Blockage Prediction,” arXiv:1911.06255v2 [cs.IT], Nov 2019.
  * [5] Shrreenithi Srinivasan, “Beam Prediction Using Deep Learning Methods for mmWave Communications,” https://csus-dspace.calstate.edu/bitstream/handle/10211.3/217943/Shrreenith_Srinivasan_Report.pdf, 2020.
  * [6] Y. Tian, G. Pan, and M. Alouini, “Applying Deep-Learning-Based Computer Vision to Wireless Communications: Methodologies, Opportunities, and Challenges,” arXiv:2006.05782v4, Dec 2020.
  * [7] J. Redmon, S. Divvala, R. Girshick, and A. Farhadi, “You only look once: Unified, real-time object detection,” in Proc. of the IEEE conference on computer vision and pattern recognition, 2016, pp. 779–788.
  * [8] J. Redmon and A. Farhadi, “YOLO9000: better, faster, stronger,” in Proc. of the IEEE CVPR 2017, 2017, pp. 7263–7271.


# Maximal Extractable Value (MEV) Protection on a DAG

Dahlia Malkhi and Pawel Szalachowski
Chainlink Labs

###### Abstract.

Many cryptocurrency platforms are vulnerable to Maximal Extractable Value
(MEV) attacks (Daian et al., 2020), where a malicious consensus leader can
inject transactions or change the order of user transactions to maximize its
profit.

A promising line of research in MEV mitigation is to enhance the Byzantine
fault tolerance (BFT) consensus core of blockchains by new functionalities,
like hiding transaction contents, such that malicious parties cannot analyze
and exploit them until they are ordered. An orthogonal line of research
demonstrates excellent performance for BFT protocols designed around Directed
Acyclic Graphs (DAG). They provide high throughput by keeping high network
utilization, decoupling transactions’ dissemination from their metadata
ordering, and encoding consensus logic efficiently over a DAG representing a
causal ordering of disseminated messages.

This paper explains how to combine these two advances. It introduces a DAG-
based protocol called Fino, that integrates MEV-resistance features into DAG-
based BFT without delaying the steady spreading of transactions by the DAG
transport and with zero message overhead. The scheme operates without complex
secret share verifiability or recoverability, and avoids costly threshold
encryption.

††copyright: none††conference: Crypto Economics Security Conference; Oct 31 -
Nov 1, 2022; Berkeley, CA, USA††isbn:

##  1\. Introduction

###  1.1. MEV

Over the last few years, we have seen exploding interest in cryptocurrency
platforms and applications built upon them, like decentralized finance
protocols offering censorship-resistant and open access to financial
instruments; or non-fungible tokens. Many of these systems are vulnerable to
MEV attacks, where a malicious consensus leader can inject transactions or
change the order of user transactions to maximize its profit. Thus it is not
surprising that at the same time we have witnessed rising phenomena of MEV
professionalization, where an entire ecosystem of MEV exploitation, comprising
of MEV opportunity ”searchers” and collaborating miners, has arisen.

Daian et al. (Daian et al., 2020) introduced a measure of the “profit that can
be made through including, excluding, or re-ordering transactions within
blocks”. The original work called the measure miner extractable value, which
was later extended by maximal extractable value (MEV) (Obadia et al., 2021)
and blockchain extractable value (BEV) (Qin et al., 2021), to include other
forms of attacks, not necessarily performed by miners. At the time of this
writing, an “MEV-explore” tool (mev, 2022) estimates the amount of MEV
extracted on Ethereum since the 1st of Jan 2020 to be close to $700M. However,
it is safe to assume that the total MEV extracted is much higher, since MEV-
explore limits its estimates to only one blockchain, a few protocols, and a
limited number of detectable MEV techniques. Although it is difficult to argue
that all MEV is ”bad” (e.g., market arbitrage can remove market
inefficiencies), it usually introduces some negative externalities like:
network congestion: especially on low-cost chains, MEV actors often try to
increase their chances of exploiting an MEV opportunity by sending a lot of
redundant transactions, spamming the underlying peer-to-peer network; chain
congestion: many such transactions finally make it to the chain, making the
chain more congested; higher blockchain costs: while competing for profitable
MEV opportunities, MEV actors bid higher gas prices to prioritize their
transactions, which results in overall higher blockchain costs for regular
users; consensus stability: some on-chain transactions can create such a
lucrative MEV opportunity that it may be tempting for miner(s) to create an
alternative chain fork with such a transaction extracted by them, which
introduces consensus instability risks.

###  1.2. Blind Order-Fairness on a DAG

A promising way of thwarting some forms of MEV on blockchains is to extend
their BFT (Byzantine fault tolerance) consensus core by new properties like
Blind Order-Fairness, where no consensus ”validator” can learn the content of
transactions until they are committed to a total ordering. This notion of
_“commit-reveal”_ is the key mechanism we focus on in this paper.

An orthogonal line of research concentrates on scaling the BFT consensus of
blockchains via a DAG communication substrate. A DAG transport can spread yet-
unconfirmed transactions in parallel, every message having utility and
carrying transactions that eventually become committed to a total ordering.
The DAG provides Reliability, Non-equivocation, and Causal-ordering delivery
guarantees, enabling a simple and ”zero-overhead” consensus ordering on top of
it. That is, validators can interpret their DAG locally without exchanging
more messages and determine a total ordering of accumulated transactions.
Several recent DAG-based BFT systems, including Blockmania (Danezis and
Hrycyszyn, 2018), Aleph (Gagol and Świetek, 2018), Narwhal (Danezis et al.,
2022), DAG-Rider (Keidar et al., 2021), and Bullshark (Giridharan et al.,
2022), demonstrate excellent performance.

This paper combines these two advances in a solution called Fino, that
integrates smoothly two ingredients: A framework for commit-reveal consensus
protocols, and a simple DAG-based BFT consensus that leverages the
Reliability, Non-Equivocation, and Causality properties of the DAG transport
to integrate the commit-reveal framework smoothly and efficiently into
consensus.

A commit-reveal framework. The core of the commit-reveal framework of Fino is
a standard k-of-n secret sharing approach consisting of two functionalities,
Disperse() and Retrieve(). Users first send transactions to validators
encrypted, so that the consensus protocol commits to an ordering of
transactions blindly. Disperse() entrusts shares of the secret decryption key
for each transaction to validators. After an ordering is committed, Retrieve()
opens encrypted transactions by collecting shares from $F+1$ validators.

Implementing Disperse()/Retrieve() efficiently enough to meet DAG-based
consensus throughput is the core challenge Fino addresses. Two straw man
approaches are (i) threshold cryptography, but it would incur an order of
milliseconds per transaction, (ii) using polynomial secret-sharing and
verifying shares during dispersal, also requiring costly cryptography as well
as implementing a share-recovery protocol.

The third approach, and the one we recommend using, shares transaction
encryption keys using Shamir’s secret-sharing scheme (Shamir, 1979), but
without secret share verifiability or recoverability (slow and complex), and
without threshold encryption (slow). Instead, to guarantee a unique,
deterministic outcome of encrypted transactions, Fino borrows a key insight
from DispersedLedger (Yang et al., 2022) called AVID-M, protecting against
share manipulation attacks by verifying that the sharing was correct post
reconstruction. If the dispersal was incorrect and fails post-reconstruction
verification, the transaction is rejected.

Notably, this approach works in microseconds latency and is orders of
magnitude faster than threshold encryption.

Section 3 describes a fourth approach, a hybrid combining AVID-M with
threshold cryptography. Hybrid tackles adversarial conditions where Disperse()
partially fails, at the cost of a slower post-reconstruction verification.

We repeat that all four approaches above are compatible with the Fino
framework, though the fastest and simplest one is AVID-M.

DAG-based integration. Fino integrates Disperse()/Retrieve() into a DAG-based
consensus without delaying the steady spreading of transactions by the DAG
transport and with zero message overhead. Validators interpret their local
DAGs to arrive at commit decisions on blind ordering. After an ordering has
committed for a batch of transactions, validators invoke Retrieve() and
present decryption shares piggybacked on DAG broadcasts. Finally, validators
interpret their local DAGs to arrive at unanimous, deterministic outcome of
transaction opening.

During periods of synchrony, Fino has a happy path for transaction commit of
two DAG latencies, plus a single DAG latency for determining an opening
outcome.

##  2\. Background and Preliminaries

###  2.1. System Model

The Byzantine fault tolerance (BFT) Consensus core of blockchains implements
state machine replication (SMR), where non-faulty parties–also known as
validators–agree on an order of transactions and execute them consistently.
The goal of our work is to extend BFT consensus and build into it protection
against MEV attacks which rely on transaction content analysis.

We assume that the system should be resilient to Byzantine faults, i.e.,
faulty validators can implement any adversarial behavior (like crashing,
equivocating, or colluding). We assume a partially synchronous network (Dwork
et al., 1988), where asynchronous periods last up to unknown global
stabilization time (GST), while in synchronous periods there is a known bound
$\Delta$ on delays for message delivery. This model requires a BFT threshold
$N\geq 3F+1$, where $N$ and $F$ is the number of all and Byzantine faulty
validators, respectively.

###  2.2. MEV and Blind Order-Fairness

In this paper, we focus on consensus-level MEV mitigation techniques. There
are fundamentally two types of MEV-resistant Order-Fairness properties:

Blind Order-Fairness. A principal line of defense against MEV stems from
committing to transaction ordering without seeing transaction contents. This
notion of MEV resistance, referred to here as Blind Order-Fairness, is used in
a recent SoK on Preventing Transaction Reordering by Heimbach and Wattenhofer
(Heimbach and Wattenhofer, 2022), and is defined as: ”when it is not possible
for any party to include or exclude transactions after seeing their contents.
Further, it should not be possible for any party to insert their own
transaction before any transaction whose contents it already been observed.”

Time-Based Order-Fairness. Another measure for MEV protection is brought by
sending transactions to all BFT parties simultaneously and using the relative
arrival order at a majority of the parties to determine the final ordering. In
particular, this notion of order fairness ensures that ”if sufficiently many
parties receive a transaction tx before another tx’, then in the final commit
order tx’ is not sequenced before tx.”

This defines the transactions order and prevents adversaries that can analyze
network traffic and transaction contents from reordering, censoring, and
front-/back-running transactions received by Consensus parties. Moreover,
Time-Based Order-Fairness protects against a potential collusion between users
and BFT leaders/parties because parties explicitly input relative ordering
into the protocol. Time-Based Order-Fairness is used in various flavors in
several recent works, including Pompe (Zhang et al., 2020), Aequitas (Kelkar
et al., 2020), Themis (Kelkar et al., 2021), ”Wendy Grows Up” (Kursawe, 2021),
and ”Quick Order Fairness” (Cachin et al., 2021). We briefly discuss some of
those protocols in Section 8.

Another notion of fairness found in the literature, that does not provide
Order-Fairness, revolves around participation fairness:

Participation Fairness. A different notion of fairness aims to ensure
censorship-resistance or stronger notions of participation equity.
Participation Fairness guarantees that the committed sequence of transactions
includes a certain portion of honest contribution (aka ”Chain Quality”).
Several BFT protocols address Participation Fairness, including Prime (Amir et
al., 2010), Fairledger (Lev-Ari et al., 2019), HoneyBadger (Miller et al.,
2016). As mentioned in Section 4, some DAG-based BFT protocols like Aleph
(Gagol and Świetek, 2018), DAG-Rider (Keidar et al., 2021), Tusk (Danezis et
al., 2022), and Bullshark (Giridharan et al., 2022) use a layered DAG
paradigm. In this approach, Participation Fairness comes essentially for free
because every DAG layer must include messages from 2F+1 participants. It is
worth noting that Participation Fairness does not prevent a corrupt party from
injecting transactions after it has already observed other transactions, nor a
corrupt leader from reordering transactions after reading them, violating both
Blind and Time-Based Order-Fairness.

###  2.3. Threshold Methods

Beside standard cryptographic primitives, like a symmetric encryption scheme
or a cryptographic hash function $H()$, we employ primitives specifically
designed for hiding and opening transactions.

Secret Sharing For positive integers $k,n$, where $k\leq n$, a (k,n)-threshold
scheme is a technique where a secret is distributed among $n$ parties , such
that it can be reconstructed by any $k$ parties, while any group of $k-1$
parties cannot learn the secret. The secret $S$ is selected by a trusted third
party, called dealer, who splits it into $n$ individual shares by calling:
$s_{1},...,s_{n}\leftarrow{\tt SS.Split(S)}$. After at least $k$ parties
exchange shares, they can combine them and recover the secret by calling
$S\leftarrow$ SS.Combine($s^{\prime}_{1},...,s^{\prime}_{k}$).

Shamir’s Secret Sharing (SSS) (Shamir, 1979) is one of the first and most
widely used (k,n)-threshold schemes. In SSS, Split($S$) chooses a polynomial
$f$ of degree $k-1$ that hides $S$ at the origin point, and generates $n$
points on the polynomial. Then, any $k$ points allow to interpolate the
polynomial and compute its value at $f(0)$.

Threshold Encryption. A (k,n)-threshold encryption is a scheme where messages
encrypted under a single public encryption key $pk$ can be decrypted by a
private decryption key, shared among $n$ parties – each with its secret key
$sk_{i}$, where any group of $k$ parties can decrypt a message. The message
$m$ is encrypted with an encryption algorithm: $c\leftarrow$ TE.Enc($pk,m$).
We consider schemes where each party, upon receiving a ciphertext $c$,
computes its own decryption share by invoking: $ds_{i}\leftarrow$
TE.ShareGen($sk_{i},c$); and any set of $k$ unique decryption shares is enough
to recover the plaintext, which we denote
$m\leftarrow$TE.Dec($c,ds^{\prime}_{1},...,ds^{\prime}_{k}$).

Moreover, some threshold encryption schemes, like shown by Shoup and Gennaro
(Shoup and Gennaro, 1998), allow parties to verify that a given decryption
share corresponds to the ciphertext, which we denote by the
TE.Verify($c,ds_{i}$) function. Note that, without such a verification, it is
trivial for a malicious party, providing an incorrect share, to cause
decryption failures.

##  3\. The commit-reveal Framework

The core of blind fairness-ordering is a standard k-of-n secret sharing
approach. For each transaction tx, a user (“Alice”) picks a secret symmetric
key tx-key, and sends tx encrypted with it to validators. Secret sharing
allows Alice to share tx-key with validators such that $F+1$ shares are
required to reconstruct tx-key, and no set of $F$ bad validators can open it
before it is committed (blindly) to the total order. Honest validators wait to
commit to a blind order of transactions first, and only later open them. At
the same time, before committing a transaction to the total ordering,
validators ensure that they can open it.

More formally, a sharing protocol has two abstract functionalities,
Disperse(tx) and Retrieve(tx). Disperse() allows a dealer to disseminate
shares of the secret tx-key to validators, with the following guarantees:

Hiding::

A set of F bad validators cannot reconstruct tx-key.

Binding::

After Disperse(tx-key) completes successfully at an honest validator, any set
of honest $F+1$ validators doing Retrieve(tx-key) can reconstruct tx-key
generating a unique outcome.

Validity::

If the dealer is honest, then the outcome from Retrieve(tx-key) by any $F+1$
honest validators is tx-key.

It is worth noting that Disperse()/Retrieve() does not require certain
properties which some use-cases in the literature may need, but not the
framework here:

  * •

When Disperse() completes, it does not guarantee that Retrieve() can
reconstruct an output value that a dealer commits to.

  * •

It doesn’t require that individual shares can be recovered.

  * •

It doesn’t require being able to use tx-key to derive other values while
keeping tx-key itself secret.

We proceed to present four approaches for implementing Disperse()/Retrieve().
All of them are compatible with the DAG-based consensus protocol in the next
section, though the fastest and simplest one, which we recommend using, is
AVID-M.

### Approach-1: Threshold Cryptography

It is straight-forward to implement Disperse/Retrieve using threshold
encryption, such that the public encryption TE.Enc() is known to users and the
private decryption TE.Dec() is shared (at setup time) among validators. To
Disperse(tx-key), the user attaches TE.Enc(tx-key), the transaction key
encrypted with the global threshold key. Once a tx is committed to the total-
ordering, Retrieve(tx-key) is implemented by each validator generating its
decryption share via TE.ShareGen(). Validators can try applying TE.Dec() over
$F+1$ valid decryption shares to decrypt tx.

Binding stems from two properties. First, a threshold of honest validators can
always succeed in generating $F+1$ valid decryption shares. Second, as
indicated in Section 2, some threshold cryptography schemes allow verifying
that a validator is contributing a correct decryption share, hence by
retrieving $F+1$ valid threshold shares, a unique outcome is guaranteed.

Unfortunately, this method is computationally somewhat heavy: Disperse() takes
about $300\mu s$ to encrypt using TDH2 on standard hardware, and Retrieve()
takes about $3500\mu s$ for in a 6-out-of-16 scheme (see Section 7).

### Approach-2: VSS

Another way for users to Disperse(tx-key) is Shamir’s secret sharing (SSS)
scheme. To Disperse(tx-key), a user employs SS.Split(tx-key) to send
individual shares of tx-key to each validator. A set of $F+1$ share holders
reveal their shares during Retrieve() and combine shares via SS.Combine() to
reconstruct tx-key.

Combining shares is three orders of magnitude faster than threshold crypto and
takes a few microseconds in today’s computing environment (see Section 7).
However, after Disperse() completes with $N-F$ validators, “vanilla”
SS.Split()/SS.Combine() does not guarantee Binding: first, not every set of
$F+1$ honest validators may hold shares from the Disperse() phase. Second,
retrieving shares from different sets of $F+1$ validators may result in
different outcome from SS.Combine().

VSS schemes support Binding through a share-verification functionality
VSS.Verification(share, commit value). Verification allows validators to check
that shares are consistent with some committed value $S’$, such that any set
of $F+1$ shares applied to SS.Combine() results in output $S’$. When a
validator receives a share, it should verify the share before acknowledging
it. Disperse() completes when there are $N-F$ acknowledgements of verifiable
shares, certifying that valid shares are held by $F+1$ honest validators and
guaranteeing a unique reconstruction by any subset of $F+1$. It is possible to
add a share-recovery functionality to allow a validator to obtain its
individual share prior to Retrieve().

However, despite the vast progress in VSS schemes (see Section 8.1), share
recovery requires linear communication. Additionally, implementing VSS
requires non-trivial cryptography.

### AVID-M

VSS provides stronger guarantees than necessary to satisfy the Binding
requirement of commit-reveal. Specifically, Disperse() only needs to guarantee
a unique outcome from Retrieve(), not success. Borrowing a technique called
AVID-M, which was introduced in DispersedLedger (Yang et al., 2022) for
reliable information dispersal, validators can completely avoid verifying
shares during Disperse(). Instead, they verify during Retrieve() that the
(entire) sharing would have a unique outcome, which is very cheap to do. This
works as follows.

To Disperse(tx), a user employs SS.Split(tx-key) to send individual shares to
validators. This operation requires a deterministic way of splitting secret
shares which, in particular, can be based on validator identifiers (e.g.,
$s_{i}=P(id_{i})$, where $P$ is the polynomial hiding tx-key). Additionally,
the user combines all shares in a Merkle-tree, certifies the root, and sends
with each share a proof of membership, i.e., a Merkle tree path to the root.

When a validator receives a share, it should verify the Merkle tree proof
against the certified root before acknowledging the share. Disperse()
completes when there are $N-F$ acknowledgements, guaranteeing that untampered
shares are held by $F+1$ honest validators.

During Retrieve(), $F+1$ validators reveal individual shares, attaching the
Merkle tree path to prove shares have not been tampered with. Note that $F+1$
shares can be validated by checking only one signature on the root. Validators
use SS.Combine() to try to reconstruct tx-key.

Then they _post-verify_ that every subset of $F+1$ (untampered) shares sent to
validators would have the same outcome. To do this, a validator does not need
to wait for missing shares nor try combinations of $F+1$ shares. Moreover, it
does not need to communicate with others. A validator simply generates missing
shares and re-encodes the Merkle tree. Then, it compares the re-generated
Merkle tree with the root certified by the sender. If the comparison fails,
the dealer was faulty and the validator rejects tx. The unique reconstruction
is guaranteed because the post-verification outcome – succeed or fail –
becomes fixed upon Disperse completion. Each validator arrives at the same
outcome no matter which subset of $F+1$ (untampered) shares are input.

AVID-M takes roughly $50\mu s$ to SS.split() and generate Merkle tree
commitments, and roughly $50\mu s$ for Retrieve(), including post-
verification, in a 6-out-of-16 scheme.

### Hybrid

Even after Disperse() has completed, both VSS and AVID-M may need to interact
with a specific set of $F+1$ honest validators during Retrieve(). This implies
that the latency of Retrieve() is impacted by this specific set of $F+1$ share
holders, and not the speed of the fastest $F+1$ honest validators. Employing
threshold cryptography removes this dependency but incurs a costly
computation.

A Hybrid approach combines the benefits of threshold cryptography with AVID-M.
In Hybrid, Retrieve() works with (fast) secret-sharing during steady-state,
and falls back to threshold cryptography, avoiding waiting for specific $F+1$
validators, during a period of network instability.

Disperse(tx-key) is implemented in two parts. First, a user applies AVID-M to
send validators individual shares and proofs. Second, as a fallback, it sends
validators TE.Enc(tx-key). Once tx is committed to the total ordering,
Retrieve(tx-key) has a fast track and a slow track. In the fast track, every
validator that holds an AVID-M share reveals it. A validator that doesn’t hold
an AVID-M share for tx-key reveals a threshold key decryption share. In the
slow track, validators may give up on waiting for AVID-M shares and reveal
threshold key decryption shares, even if they already revealed AVID-M shares.

Post-verification after $F+1$ valid shares of either kind are revealed checks
that both the AVID-M and threshold encryption were shared correctly and would
have the same outcome. More specifically, a validator both re-encrypts tx-key
and re-encodes the AVID-M Merkle tree after reconstruction. It compares both
outcomes with the sender’s. If the comparison fails, the dealer was faulty and
the validator rejects tx. Binding holds because the post-verification outcome
– succeed or fail – becomes fixed upon Disperse() completion. Each validator
arrives at the same outcome no matter which scheme and what subset of $F+1$
(untampered) shares are retrieved, thus ensuring Binding.

##  4\. DAG transport

In a DAG-based BFT protocol, validators store messages delivered via reliable
and causally ordered broadcast in a local graph. A message inserted into the
local DAG has the following guarantees: Reliability: there are copies of the
message stored on sufficiently many participants, such that eventually, all
honest validators can download it. Non-equivocation: messages by each
validator are numbered. If a validator delivers some message as the k’th from
a particular sender, then the message is authenticated by its sender and other
validators deliver the same message as the sender k’th message. Causal
Ordering: the message carries explicit references to messages which the sender
has previously delivered (including its own). Predecessors are delivered
locally before the message.

Note that the DAGs at different validators may be slightly different at any
moment in time. This is inevitable in a distributed system due to message
scheduling. However, a DAG-based Consensus protocol allows each participant to
interpret its local DAG, reaching an autonomous conclusion that forms total
ordering. Reliability, Non-equivocation and Causal Ordering make the design of
such protocols extremely simple as we shall see below.

DAG API. A DAG transport exposes two basic API’s, broadcast() and deliver().

Broadcast.:

broadcast() is an asynchronous API for a validator to present payload for the
DAG transport to be transmitted to all other validators. The main use of DAG
messages in a DAG-based Consensus protocol is to pack meta-information on
transactions into a block and present the block for broadcast. The DAG
transport adds references to previously delivered messages, and broadcasts a
message carrying the block and the causal references to all validators.

Deliver.:

When another validator receives the message carrying the block, it checks
whether it needs to retrieve a copy of any of the transactions in the block
and in causally preceding messages. Once it obtains a proof-of-availability of
all transactions in the block and its causal past, it can acknowledge it. A
validator’s upcall deliver(m) is triggered when sufficiently many
acknowledgments for it are gathered, guaranteeing that the message itself, the
transactions it refers to, and its entire causal past maintain Reliability,
Non-equivocation and Causal Ordering.

It is worth noting that in the protocol discussed in this paper, the Consensus
protocol injects meta-information (e.g., complaints), DAG broadcast never
stalls or waits for input from it.

Implementing a DAG. There are various ways to implement reliable, non-
equivocating and causally-ordered broadcast among $N=3F+1validators$, at most
$F$ of which are presumed Byzantine faulty and the rest are honest.

Lifetime of a message.:

A validator packs transaction information and meta-information into a message,
adds references to previously delivered messages (including the sender’s own
preceding messages), and broadcasts the message to all validators.

Echoing.:

The key mechanism for reliability and non-equivocation is for validators to
echo a digest of the first message they receive from a sender with a
particular index. When $2F+1$ echoes are collected, the message can be
delivered. There are two ways to echo, one is all-to-all broadcast over
authenticated point-to-point channels a la Bracha Broadcast (Bracha, 1987);
the other is converge-cast with cryptographic signatures a la Rampart (Reiter
and Birman, 1994) and Cachin et al. (Cachin et al., 2001). In either case,
echoing can be streamlined so the amortized per-message communication is
linear, which is anyway the minimum necessary to spread the message.

Layering.:

Transports are often constructed in a layer-by-layer regime. In this regime,
each sender is allowed one message per layer, and a message may refer only to
messages in the layer preceding it. Layering is done so as to regulate
transmissions and saturate network capacity, and has been demonstrated to be
highly effective by various projects (Danezis and Hrycyszyn, 2018; Gagol and
Świetek, 2018; Danezis et al., 2022). We reiterate that Fino does not require
a layered structure.

##  5\. Fino

Fino incorporates MEV protection into a BFT protocol for the partial synchrony
model, riding on a DAG transport. BFT validators periodically pack pending
encrypted transactions into a batch and use the DAG transport to broadcast
them. The key insight for operating commit-reveal on a DAG is that each view
must wait until Retrieve() completes on transactions tx of the previous view.

###  5.1. The Protocol

Views. The protocol operates in a view-by-view manner. Each view is numbered,
as in view(r), and has a designated leader known to everyone.

View change. A validator enters view(r+1) when two conditions are met, viewA
and viewB: viewA is satisfied when the local DAG of a validator contains $F+1$
valid votes on proposal(r) or $2F+1$ valid complaint(r) on view(r). viewB is
satisfied when every committed transaction tx in the local DAG has $F+1$ valid
shares revealed, hence Retrieve(tx) can be completed. Note that viewB prevents
BFT validators that do not reveal (correct) shares from enabling the protocol
to make progress without opening committed transactions.

Proposing. When a leader enters a new view(r), it broadcasts proposal(r).111
Recall, broadcast() merely presents payload to be transmitted as scheduled by
the DAG transport, e.g., piggybacked on messages carrying other transaction
info. Implicitly, proposal(r) suggests to commit to the global ordering of
transactions all the messages in the causal history of the proposal. A
leader’s proposal(r) is valid if it is well-formatted and is justified in
entering view(r).

Voting. When a validator sees a valid leader proposal, it broadcasts vote(r).
A validator’s vote(r) is valid if it follows a valid proposal(r).

Committing. Whenever a leader’s proposal(r) has $F+1$ valid votes in the local
DAG, the proposal and its causal history become committed. The commit order
induced by a commit decision is described below.

Share revealing. When a validator observes that a transaction tx becomes
committed, it starts Retrieve(tx) and calls broadcast() to present its share
of the decryption key tx-key.

Complaining. If a validator gives up waiting for a commit to happen in
view(r), it broadcasts complaint(r). Note, a vote(r) by a validator that
causally follows a complaint(r) by the validator, if exists, is not
interpreted as a valid vote.

Ordering Commits. When a validator observes that a leader’s proposal(r)
becomes committed, it orders newly committed transactions as follows:

  1. (1)

Let r’ be the highest view r’ < r for which proposal(r’) is in the causal
history of proposal(r). proposal(r’) is recursively ordered.

  2. (2)

The remaining causal predecessors of proposal(r) which have not yet been
ordered are appended to the committed sequence (within this batch, ordering
can be done using any deterministic rule to linearize the partial ordering
into a total ordering.)

Opening Transactions. When a validator observes that a leader’s proposal(r)
becomes committed, it decrypts every committed transaction tx in its causal
past that hasn’t been decrypted already. That is, let c be the highest view c
< r for which proposal(r) causally follows $F+1$ valid votes. Transactions in
the causal past of proposal(c) are opened as follows:

  1. (1)

Let r’ be the highest view r’ < c for which proposal(r’) is in the causal
history of proposal(c). proposal(r’) is recursively opened.

  2. (2)

The remaining (committed) transactions tx in proposal(c)’s causal past are
opened using Retrieve(tx) to either produce a key tx-key that decrypts tx or
to reject tx.

Figure 1. A commit of proposal(r) is followed by share retrieval. A commit of
proposal(r+2) causes an indirect commit of proposal(r+1), followed by share
revealing of both.

Fig. 1 illustrates a couple of Fino scenarios.

Happy-path scenario. In the first view (view(r)), proposal(r) becomes
committed. The commit sets an ordering for transactions in the causal past of
proposal(r), enabling retrieval of shares for transactions from proposal(r).

Scenario with a slow leader. A slightly more complex scenario occurs when a
view expires because validators do not observe a leader’s proposal becoming
committed and they broadcast complaints. Fig. 1 depicts this happening in
view(r+1). Entering view(r+2) is enabled by $2F+1$ complaints about view(r+1).
When proposal(r+1) itself becomes committed, it indirectly commits
proposal(r+1) as well. Thereafter, validators reveal shares for all pending
committed transactions, namely, those in both proposal(r+1) and proposal(r+2).

##  6\. Analysis

Fino is minimally integrated with a DAG transport. BFT commit-reveal logic is
embedded into the DAG structure simply by broadcasting (more precisely,
injecting payloads into broadcasts) in the form of protocol
proposals/votes/complaints and revealing shares. Importantly, at no time is
DAG broadcast slowed down by the Fino protocol. The reliability and causality
properties of the DAG transport make arguing about safety and liveness
relatively easy.

###  6.1. Safety

###### Lemma 6.1.

Assume a proposal(r) ever becomes committed. Denote by $r^{\prime}$ the
minimal view, where $r^{\prime}>r$, such that proposal(r’) ever becomes
committed. Then for every $r\leq q<r^{\prime}$, proposal(q+1) causally follows
proposal(r).

###### Proof.

(Sketch) Since proposal(r) becomes committed, by definition $F+1$ parties sent
votes for it. There are two possibilities for a leader’s proposal(q+1) to be
valid. The first is proposal(q+1) may reference $F+1$ valid vote(q) messages.
This case occurs only for $q==r$ by the lemma assumption that $r^{\prime}\geq
q+1$ is the minimal view that ever becomes committed. The second possibility
can occur for all $r\leq q<r^{\prime}$, namely, proposal(q+1) references
$2F+1$ valid complaint(q) messages.

In the first case, valid vote(r) causally follows proposal(r), and a fortiori
proposal(r+1) causally follows proposal(r).

In the second case, one of $2F+1$ complaint(q) messages is sent by a party who
sent a valid vote(r). By definition, vote(r) must precede complaint(q),
otherwise it is not considered a (valid) vote. Hence, proposal(q+1) causally
follows complaint(q) which follows proposal(r). ∎

###### Lemma 6.2.

If ever a proposal(r) becomes committed, then every valid proposal(q), where q
> r, causally follows proposal(r).

###### Proof.

(Sketch) The proof follows by a simple induction on Lemma 6.1. ∎

###### Lemma 6.3.

If an honest party commits proposal(r), and another honest party commits
proposal(r’), where $r^{\prime}>r$, then the sequence of transactions
committed by proposal(r) is a prefix of the sequence committed by
proposal(r’).

###### Proof.

(Sketch) When proposal(r’) becomes committed, the commit ordering rule is
recursively applied to valid proposals in its causal past. By Lemma 6.2, the
(committed) proposal(r) is a causal predecessor of every valid proposal(s),
for $r<s\leq r^{\prime}$, and eventually the recursion gets to it. ∎

###### Lemma 6.4.

If ever a proposal(r) becomes committed, then every committed transaction
proposed by a valid proposal(r’), where r’ < r, can be uniquely decrypted.

###### Proof.

(Sketch) When proposal(r) becomes committed, then by Lemma 6.3, all the
transactions from previously committed proposals are part of the committed
transaction history. Moreover, committing proposal(r) implies the view change
(from r-1) which occurs only if the condition viewB (see Section 5) is met,
i.e., every committed transaction tx in the local DAG can complete
Retrieve(tx), hence can be uniquely decrypted (or rejected).

∎

###  6.2. Liveness

Liveness is guaranteed after GST, i.e., after communication has become
synchronous with a known $\Delta$ upper bound on transmission delays.

After GST, views are semi-synchronized through the DAG. In particular, suppose
that after GST, every broadcast by an honest party arrives at all honest
parties within $DD$. Once a view(r) with an honest leader is entered by the
first honest party, within $DD$ all the messages seen by one party are
delivered by both the leader and all other honest parties. Hence, within $DD$,
all honest parties enter view(r) as well. Within two additional DAG latencies,
$2\cdot DD$, the view(r) proposal and votes from all honest parties are spread
to everyone.

Assuming view timers are set to be at least $3\cdot DD$, once view(r) is
entered, a future view will not interrupt a commit. In order to start a future
view, its leader must collect either $F+1$ vote(r) messages, hence commit
proposal(r); or $2F+1$ complaint(r) expiration messages, which is impossible
as argued above.

###  6.3. Communication complexity

Protocols for the partial synchrony model have unbounded worst case by nature,
hence, we concentrate on the costs incurred during steady state when a leader
is honest and communication with it is synchronous:

DAG message cost. In order for DAG messages to be delivered reliably, it must
implement reliable broadcast. This incurs either a quadratic number of
messages carried over authenticated channels, or a quadratic number of
signature verifications, per broadcast. In either case, the quadratic cost may
be amortized by pipelining, driving it in practice to (almost) linear per
message.

Commit message cost. Fino sends $F+1$ broadcast messages, a proposal and
votes, per decision. A decision commits the causal history of the proposal,
consisting of (at least) a linear number of messages. Moreover, each message
may carry multiple transactions in its payload. As a result, in practice the
commit cost is amortized over many transactions.

###  6.4. Latency

Commit latency. The commit latency in terms of DAG messages is 2, one proposal
followed by votes.

Opening latency. During periods of stability, there are no complaints about
honest leaders by any honest party. If tx is proposed by an honest leader in
view(r), it will receive $F+1$ votes and become committed within two DAG
latencies. Within one more DAG latency, every honest party will post a message
containing a share for tx. Thereafter, whenever $F+1$ are available, everyone
will be able to complete Retrieve(tx) with a unique outcome.

###  6.5. Faulty User

One drawback of the proposed protocol is that it assumes a well-connected and
honest user (dealer), able to entrust $F+1$ honest validators with their
shares. If the dealer is malicious or unable to broadcast shares it can lead
to the situation where the transport layer buffers a transaction indefinitely
without being able to deliver() it. The Hybrid approach we presented in
Section 3 solves this issue by using threshold encryption as a fallback
mechanisms (i.e., whenever enough shares cannot be received, parties would
proceed with threshold decryption). However, the hybrid construction suffers
the slowness of threshold encryption to verify a unique outcome even in
faultless executions.

##  7\. Evaluation (prelim)

We implemented the proposed variants of the Fino Disperse and Retrieve
functionalities and investigated the computational overhead that these schemes
introduce. For secret sharing we implemented SSS (Shamir, 1979), while for
threshold encryption we implemented the TDH2 scheme (Shoup and Gennaro, 1998).
We selected the schemes with the most efficient cryptographic primitives we
had access to, i.e., the secret sharing scheme uses the Ed25519 curve
(Bernstein et al., 2012), while TDH2 uses ristretto255 (de Valence et al.,
2020) as the underlying prime-order group. Performance for both schemes is
presented in a setting where 6 shares out of 16 are required to recover the
plaintext.

Table 1. Comparison of the implementations’ performance. Scheme | Disperse | ShareGen | ShareVerify | Reconstruct
---|---|---|---|---
TDH2-based |  311.6$\mu s$ |  434.8$\mu s$ |  492.5$\mu s$ |  763.9$\mu s$
SSS-AVID-M |  52.7$\mu s$ | N/A |  2.7$\mu s$ |  52.5$\mu s$
Hybrid opt. |  360.3$\mu s$ | N/A |  2.7$\mu s$ |  361.5$\mu s$
Hybrid pess. |  360.3$\mu s$ |  434.8$\mu s$ |  492.5$\mu s$ |  828.9$\mu s$

The results presented in Table 1 are obtained on an Apple M1 Pro. Disperse
refers to the overhead on the client-side while ShareGen is the operation of
deriving a decryption share from the TDH2 ciphertext (it is absent in SSS and
the optimistic path of the hybrid scheme). In TDH2, ShareVerify verifies if a
decryption share matches the ciphertext, while in SSS-based Fino it only
checks whether a share belongs to the tree aggregated by the signed Merkle
root attached by the client. Reconstruct recovers the plaintext from the
ciphertext and the number of shares and verifies the outcome integrity (i.e.,
AVID-M and threshold re-encryption verification, where applicable).

As demonstrated by these micro-measurements, the SSS-AVID-M scheme is the most
efficient: in our blind ordering scenario using threshold encryption, each
party processing a TDH2 ciphertext would call ShareGen once to derive its
decryption share, ShareVerify k-1 times to verify the threshold number of
received shares, and Reconstruct once to obtain the plaintext. Assuming k=6,
the total computational overhead for a single transaction to be recovered
would take around 3.7ms CPU time. With secret-sharing based Fino, the party
would also call ShareVerify k-1 times and Reconstruct once, which requires
only 66$\mu s$ CPU time. The hybrid approach introduces an interesting trade-
off between its properties and performance. In the optimistic path, it
requires around 378$\mu s$ CPU time per transaction, while its fallback
introduces negligible overhead to the plain threshold-encryption scheme.

We emphasize that these are micro-benchmarks of the blinding/unblinding of
transactions; in the future, we plan to complete a performance evaluation of
the entire DAG-based blind-ordering protocol.

##  8\. Related Work and Discussion

Despite the MEV problem being relatively new, there already exist consensus-
related systems aiming at solving it. For instance, Flash Freezing Flash Boys
(F3B) (Zhang et al., 2022) is a commit-and-reveal architecture, where clients
send TDH2-encrypted ciphertexts to be ordered by Consensus, and afterward to
be decrypted via shares released by a dedicated secret-management committee.
Other closely related techniques and schemes helpful in mitigating MEV are
discussed below.

###  8.1. Verifiable Secret Sharing (VSS)

Although we ultimately end up forgoing verifiability/recoverability of shares,
VSS is used in many settings like ours. The overall communication complexity
incurred in VSS on the dealer sharing a secret and on a party recovering a
share has dramatically improved in recent years. VSS can be implemented inside
the asynchronous echo broadcast protocol in $O(n^{3})$ communication
complexity using Pederson’s original two-dimensional polynomial scheme Non-
Interactive Polynomial Commitments (Pedersen, 1991). Kate et al. (Kate et al.,
2010) introduce a VSS scheme with $O(n^{2})$ communication complexity,
utilized for asynchronous VSS by Backes et al. (Backes et al., 2013). Basu et
al. (Basu et al., 2019) propose a scheme with linear $O(n)$ communication
complexity.

A related notion is robust secret sharing (RSS) introduced by Krawczyk
(Krawczyk, 1993) and later revised by Bellare and Rogaway (Bellare and
Rogaway, 2007). RSS allows recoverability in case of incorrect (not just
missing) shares, however, these schemes assume an honest dealer. Duan et al.
(Duan et al., 2017) propose ARSS extending RSS to the asynchronous setting.

###  8.2. Time-Based Order-Fairness

Blind Order-Fairness is achieved by deterministically ordering encrypted
transactions and then, after the order is final, decrypting them. The
deterministic order can be enhanced by sophisticated ordering logic present in
other protocols. In particular, Fino can be extended to provide Time-Based
Fairness additionally ensuring that the received transactions are not only
unreadable by parties, but also their relative order cannot be influenced by
malicious parties (the transaction order would be defined by the time of its
ciphertext arrival).

For instance, Pompē (Zhang et al., 2020) proposes a property called Ordering
Linearizability: “if all correct parties timestamp transactions tx, tx’ such
that tx’ has a lower timestamp than tx by everyone, then tx’ is ordered before
tx.” It implements the property based on an observation that if parties
exchange transactions associated with their receiving timestamps, then for
each transaction its median timestamp, computed out of 2F+1 timestamps
collected, is between the minimum and maximum timestamps of honest parties.
Fino can be easily extended by the Linearizability property offered by Pompē
and the final protocol is similar to the Fino with Blind Order-Fairness (see
above) with only one modification. Namely, every time a new batch of
transactions becomes committed, parties independently sort transactions by
their aggregate (median) timestamps.

More generally, Fino can easily incorporate other Time-based Fairness ordering
logic. Note that in Fino, the ordering of transactions is determined on
encrypted transactions, but time ordering information should be open. The
share revealing, share collection, and unique decryption following a committed
ordering are the same as presented previously. The final protocol offers much
stronger properties since it not only hides payloads of unordered transactions
from parties, but also prevents parties from reordering received transactions.

One form of Time-based Order-Fairness introduced in Aequitas (Kelkar et al.,
2020) is Batch-Order Fairness: “if sufficiently many (at least ½ of the)
parties receive a transaction tx before another transaction tx’, then no
honest party can deliver tx in a block after tx’, ” and a protocol achieving
it. Other forms of Time-Based Order-Fairness which may be used in Fino include
“Wendy Grows Up” (Kursawe, 2021), which introduced Timed Relative Fairness,
“if there is a time t such that all honest parties saw (according to their
local clock) tx before t and tx’ after t , then tx must be scheduled before
tx’, ” and “Quick Order Fairness” (Cachin et al., 2021), which defined
Differential-Order Fairness, “when the number of correct parties that
broadcast tx before tx’ exceeds the number that broadcast tx’ before tx by
more than $2F+\kappa$, for some $\kappa\geq 0$, then the protocol must not
deliver tx’ before tx (but they may be delivered together).”

Themis (Kelkar et al., 2021) is a protocol realizing Batch-Order Fairness,
where parties do not rely on timestamps (as in Pompē) but only on their
relative transaction orders reported. Themis can also be integrated with Fino,
however, to make it compatible this design requires some modifications to
Fin’s underlying DAG protocol. More concretely, Themis assumes that the
fraction of bad parties cannot be one quarter, i.e., F out of 4F+1. A leader
makes a proposal based on 3F+1 out of 4F+1 transaction orderings (each
reported by a distinct party). Therefore, we would need to modify the DAG
transport so that parties reference 3F+1 preceding messages (rather than
2F+1).

###  8.3. DAG-based BFT

There are many known BFT solutions for partial synchrony, and more
specifically, several recent solutions that ride on a DAG (Danezis et al.,
2022; Giridharan et al., 2022; Keidar et al., 2022). When constructing Fino,
we wanted to build MEV protection into a simple DAG-based BFT solution,
described below. Notwithstanding, we remark that Fino’s MEV protection can
possibly be incorporated into other DAG-riding BFT solutions.

We borrowed a subprotocol from Bullshark (Giridharan et al., 2022) that deals
with partial synchrony, modifying it so that DAG transmissions would never
stall waiting for BFT protocol steps or timers. Fino is different from the
borrowed Bullshark component in that BFT protocol steps (e.g., view changes,
proposals, votes, and complaints) are injected into the DAG at any time,
independent of DAG layers. It uses broadcast() (defined in Section 2) to
present these steps as payloads to the DAG transport, completely
asynchronously, while normal DAG transmissions continue. A hallmark of the
DAG-riding approach, which Fino preserves while adding Blind Order-Fairness,
is zero message overhead.

Narwhal (Danezis et al., 2022) is a recent DAG transport that has a layer-by-
layer structure, each layer having at most one message per sender and
referring to 2F+1 messages in the preceding layer. A similarly layered DAG
construction appears earlier in Aleph (Gagol and Świetek, 2018), but it does
not underscore the separation of transaction dissemination from DAG messages.
Narwhal-HS is a BFT Consensus protocol within (Danezis et al., 2022) based on
HotStuff (Yin et al., 2019) for the partial synchrony model, in which Narwhal
is used as a ”mempool”. In order to drive Consensus decisions, Narwhal-HS adds
messages outside Narwhal, using the DAG only for spreading transactions.

DAG-Rider (Keidar et al., 2021) and Tusk (Danezis et al., 2022) build
randomized BFT Consensus for the asynchronous model riding on Narwhal, These
protocols are zero message overhead over the DAG, not exchanging any messages
outside the Narwhal protocol. Both are structured with purpose-built DAG
layers grouped into ”waves” of 4 (2) layers each. Narwal waits for the
Consensus protocol to inject input value every wave, though in practice, this
does not delay the DAG materially.

Bullshark (Giridharan et al., 2022) builds BFT Consensus riding on Narwhal for
the partial synchrony model. It is designed with 8-layer waves driving commit,
each layer purpose-built to serve a different step in the protocol. Bullshark
is a ”zero message overhead” protocol over the DAG, however, due to a rigid
wave-by-wave structure, the DAG is modified to wait for Bullshark timers/steps
to insert transactions into the DAG. In particular, if leader(s) of a wave are
faulty or slow, some DAG layers wait to fill until consensus timers expire.

More generally, since the eighties, causally ordered reliable broadcast has
been utilized in forming distributed Consensus protocols, e.g., (Birman and
Joseph, 1987; Peterson et al., 1989; Melliar-Smith et al., 1990; Moser and
Melliar-Smith, 1999; Amir et al., 1991; Dolev et al., 1993).

The notion of the secure, causal, reliable broadcast was introduced by Reiter
and Birman (Reiter and Birman, 1994), and later refined by Cachin (Cachin et
al., 2001) and Duan et al. (Duan et al., 2017). This primitive was utilized in
a variety of BFT replicated systems, but not necessarily in the form of zero
message overhead protocols riding on a DAG. Several of these pre blockchain-
era BFT protocols are DAG based, notably Total (Moser and Melliar-Smith, 1999)
and ToTo (Dolev et al., 1993), both of which are BFT solutions for the
asynchronous model.

##  9\. Conclusions

In this paper, we show how DAG-based BFT protocols can be enhanced to mitigate
MEV – arguably one of the main threats to the success of cryptocurrencies. We
investigate the design space of achieving Blind Order-Fairness, and we propose
an approach that focuses on practicality. We present preliminary correctness
and performance results which indicate that our scheme is secure and
efficient. In the future, we plan to extend our analysis and experiments, and
investigate other cryptographic tools which can improve our scheme.

## Acknowledgment

We are grateful to Soumya Basu, Christian Cachin, Ari Juels, Mahimna Kelkar,
Lefteris Kokoris-Kogias, Oded Naor, Mike Reiter and Nibesh Shrestha for many
comments that helped improve this writeup.

## References

  * (1)
  * mev (2022) 2022\.  MeV-Explore v1.  https://explore.flashbots.net/. (2022).  Accessed: 2022-07-18.
  * Amir et al. (2010) Yair Amir, Brian Coan, Jonathan Kirsch, and John Lane. 2010\.  Prime: Byzantine replication under attack.  IEEE TDSC (2010).
  * Amir et al. (1991) Yair Amir, Danny Dolev, Shlomo Kramer, and Dalia Malki. 1991\.  Transis: A communication sub-system for high availability.  Hebrew University of Jerusalem. Leibniz Center for Research in Computer ….
  * Backes et al. (2013) Michael Backes, Amit Datta, and Aniket Kate. 2013\.  Asynchronous computational VSS with reduced communication complexity. In CT-RSA. Springer.
  * Basu et al. (2019) Soumya Basu, Alin Tomescu, Ittai Abraham, Dahlia Malkhi, Michael K Reiter, and Emin Gün Sirer. 2019.  Efficient verifiable secret sharing with share recovery in BFT protocols. In ACM CCS.
  * Bellare and Rogaway (2007) Mihir Bellare and Phillip Rogaway. 2007.  Robust computational secret sharing and a unified account of classical secret-sharing goals. In ACM CCS.
  * Bernstein et al. (2012) Daniel J Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang. 2012.  High-speed high-security signatures.  Journal of cryptographic engineering (2012).
  * Birman and Joseph (1987) Ken Birman and Thomas Joseph. 1987.  Exploiting virtual synchrony in distributed systems. In ACM SOSP.
  * Bracha (1987) Gabriel Bracha. 1987\.  Asynchronous Byzantine agreement protocols.  Information and Computation (1987).
  * Cachin et al. (2001) Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. 2001.  Secure and efficient asynchronous broadcast protocols. In CRYPTO. Springer.
  * Cachin et al. (2021) Christian Cachin, Jovana Mićić, and Nathalie Steinhauer. 2021\.  Quick Order Fairness.  arXiv preprint arXiv:2112.06615 (2021).
  * Daian et al. (2020) Philip Daian, Steven Goldfeder, Tyler Kell, Yunqi Li, Xueyuan Zhao, Iddo Bentov, Lorenz Breidenbach, and Ari Juels. 2020\.  Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability. In IEEE SP. IEEE.
  * Danezis and Hrycyszyn (2018) George Danezis and David Hrycyszyn. 2018.  Blockmania: from block dags to consensus.  arXiv preprint arXiv:1809.01620 (2018).
  * Danezis et al. (2022) George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. 2022.  Narwhal and Tusk: a DAG-based mempool and efficient BFT consensus. In EuroSys.
  * de Valence et al. (2020) Henry de Valence, Jack Grigg, George Tankersley, Filippo Valsorda, and Isis Lovecruft. 2020\.  The ristretto255 Group.  IETF CFRG Internet Draft. (2020).
  * Dolev et al. (1993) Danny Dolev, Shlomo Kramer, and Dalia Malki. 1993\.  Early delivery totally ordered multicast in asynchronous environments. In FTCS. IEEE.
  * Duan et al. (2017) Sisi Duan, Michael K Reiter, and Haibin Zhang. 2017\.  Secure causal atomic broadcast, revisited. In IEEE/IFIP DSN. IEEE.
  * Dwork et al. (1988) Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. 1988\.  Consensus in the presence of partial synchrony.  J. ACM (1988).
  * Gagol and Świetek (2018) Adam Gagol and Michał Świetek. 2018\.  Aleph: A leaderless, asynchronous, byzantine fault tolerant consensus protocol.  arXiv preprint arXiv:1810.05256 (2018).
  * Giridharan et al. (2022) Neil Giridharan, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. 2022.  Bullshark: Dag bft protocols made practical.  arXiv preprint arXiv:2201.05677 (2022).
  * Heimbach and Wattenhofer (2022) Lioba Heimbach and Roger Wattenhofer. 2022.  SoK: Preventing Transaction Reordering Manipulations in Decentralized Finance.  arXiv preprint arXiv:2203.11520 (2022).
  * Kate et al. (2010) Aniket Kate, Gregory M Zaverucha, and Ian Goldberg. 2010\.  Constant-size commitments to polynomials and their applications. In ASIACRYPT. Springer.
  * Keidar et al. (2021) Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. 2021.  All you need is dag. In ACM PODC.
  * Keidar et al. (2022) Idit Keidar, Oded Naor, and Ehud Shapiro. 2022.  Cordial Miners: A Family of Simple, Efficient and Self-Contained Consensus Protocols for Every Eventuality.  arXiv preprint arXiv:2205.09174 (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. Springer.
  * Krawczyk (1993) Hugo Krawczyk. 1993\.  Secret sharing made short. In CRYPTO. Springer.
  * Kursawe (2021) Klaus Kursawe. 2021\.  Wendy grows up: More order fairness. In Financial Crypto. Springer.
  * Lev-Ari et al. (2019) Kfir Lev-Ari, Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi. 2019.  Fairledger: A fair blockchain protocol for financial institutions.  arXiv preprint arXiv:1906.03819 (2019).
  * Melliar-Smith et al. (1990) Peter M Melliar-Smith, Louise E. Moser, and Vivek Agrawala. 1990\.  Broadcast protocols for distributed systems.  IEEE TPDS (1990).
  * Miller et al. (2016) Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. 2016.  The honey badger of BFT protocols. In ACM CCS.
  * Moser and Melliar-Smith (1999) Louise E Moser and Peter M Melliar-Smith. 1999.  Byzantine-resistant total ordering algorithms.  Information and Computation (1999).
  * Obadia et al. (2021) Alexandre Obadia, Alejo Salles, Lakshman Sankar, Tarun Chitra, Vaibhav Chellani, and Philip Daian. 2021\.  Unity is Strength: A Formalization of Cross-Domain Maximal Extractable Value.  arXiv preprint arXiv:2112.01472 (2021).
  * Pedersen (1991) Torben Pryds Pedersen. 1991\.  Non-interactive and information-theoretic secure verifiable secret sharing. In CRYPTO. Springer.
  * Peterson et al. (1989) Larry L Peterson, Nick C Buchholz, and Richard D Schlichting. 1989\.  Preserving and using context information in interprocess communication.  ACM TOCS (1989).
  * Qin et al. (2021) Kaihua Qin, Liyi Zhou, and Arthur Gervais. 2021.  Quantifying blockchain extractable value: How dark is the forest?  arXiv preprint arXiv:2101.05511 (2021).
  * Reiter and Birman (1994) Michael K Reiter and Kenneth P Birman. 1994.  How to securely replicate services.  ACM TOPLAS (1994).
  * Shamir (1979) Adi Shamir. 1979\.  How to share a secret.  Commun. ACM (1979).
  * Shoup and Gennaro (1998) Victor Shoup and Rosario Gennaro. 1998.  Securing threshold cryptosystems against chosen ciphertext attack. In EUROCRYPT. Springer.
  * Yang et al. (2022) Lei Yang, Seo Jin Park, Mohammad Alizadeh, Sreeram Kannan, and David Tse. 2022.  DispersedLedger: High-Throughput Byzantine Consensus on Variable Bandwidth Networks. In USENIX NSDI.
  * Yin et al. (2019) Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abraham. 2019\.  Hotstuff: Bft consensus with linearity and responsiveness. In ACM PODC.
  * Zhang et al. (2022) Haoqian Zhang, Louis-Henri Merino, Vero Estrada-Galinanes, and Bryan Ford. 2022.  Flash Freezing Flash Boys: Countering Blockchain Front-Running. In DINPS.
  * Zhang et al. (2020) Yunhao Zhang, Srinath Setty, Qi Chen, Lidong Zhou, and Lorenzo Alvisi. 2020.  Byzantine ordered consensus without Byzantine oligarchy. In USENIX OSDI.