11institutetext: University of Washington at Seattle

#  Travelers: A scalable fair ordering BFT system

Bowen Xue  Sreeram Kannan

###### Abstract

Many blockchain platform are subject to maximal value extraction (MEV), and
users on the platform are losing money while sending transactions because the
transaction order can be manipulated to extract value from them. Consensus
protocols have been augmented with different notion of fair ordering in order
to counter the problem. Out of all practical protocols, the most efficient BFT
consensus requires $O(nTL+n^{2}T)$ communication complexity, where $n$ is
number node, $T$ is number of transactions and $L$ is average transaction
size. In this work, we propose a new system of BFT fair ordering protocols,
Travelers, that substantially reduce the communication complexity. The
proposed system of protocols satisfy a new notion of fair ordering, called
probabilistic fair ordering, which is an extension to some existing notions of
fairness. The new notion allows a small probability of error $\epsilon$, that
adversary can insert some transactions at any location in a block, but for the
remaining $1-\epsilon$ the a modified version of ordering linearizability
holds. Our mechanism neither require a dissemination network nor direct
submissions to all consensus nodes. The key innovation comes from a routing
protocol, that is both flexible and efficient. We construct a protocol with
$O(c\log({n})TL+n^{2})$ communication complexity with $\epsilon=1/n^{c}$ for
some system parameter $c\geq 1$.

###### Keywords:

Consensus Fair Ordering Scalability Network.

##  1 Introduction

Cryptocurrency transaction has been a major application to blockchain for more
than ten years since the start of Bitcoin. With the programmable features,
Ethereum has enabled an array of decentralized financial (Defi) applications
including exchanges, lending platform and stable coins. A great amount values
are transacted every day, the daily trading volume on Ethereum is more than
five Billions US dollar[7]. With so much values attracted into the blockchain,
people starts to exploit some unspecified area in the protocol to extract
Maximal Extractable Value (MEV) from users. The extraction is possible because
most consensus protocols used today does not concern about the ordering of
transactions.

For example, automated market maker (AMM) is an type of programmable exchange
on blockchain. If a user sends a transaction to purchases asset, adversary can
make profits out of user by placing two transactions before and after the
user’ transaction. Such attack is called sandwich attack, and has been
extensively documented and analyzed in the past, see [9, 13]. Besides the
sandwich attack, people have discovered various other attacks specific to the
Defi protocols, see [27] for a more comprehensive list.

To counter the problem, people have proposed at least three categories of
solutions. First, notions of fair ordering have been proposed by many
consensus protocols, including [5, 15, 29, 8, 28]. Most of them align on a
common FIFO principle: a transaction perceived by the protocol first, should
be executed before others, though the way they measure the ordering are
different. Second, many large projects including Ethereum and application-
chains from Cosmos adopt an approach called, MEV auction platform. With this
approach, MEV is not alleviated, but optimized to extract the greatest value
and then redistribute the revenue back to the block proposers who are parts of
ecosystem. The third approach can be categorized as content-agnostic
ordering[27, 24], essentially the transaction content is committed and
threshold encrypted to hide it from the adversary, so that by the time it is
revealed, the transaction is already confirmed on the blockchain. Compared to
fair ordering protocol, the content-agnostic approach offers a weaker
guarantee, because it provide no ordering properties about its transactions.
For example, a transaction submitted much later in a block can still front-run
others transaction.

In the current blockchain ecosystem, the MEV auction approach has demonstrated
to be the most popular. There is a flourishing ecosystem built on top of
foundation of economic incentives, that includes Flashbot[12], Bloxroute[4],
Blocknative[3], Eden[11], Skip Protocol[22]. The auction solution has a great
advantage of $O(1)$ communication complexities. This is achievable because
only a few centralized entities need to collect transactions in order to build
a best block to win the auction. The second popular approach is the content-
agnostic ordering. Although it offers less properties than fair ordering
protocols, many projects like Shutter network[19], Sikka[21] have implemented
and started to contribute the blockchain ecosystem, because of its simplicity
and wide spectrum of applications. With regard to the category of fair
ordering protocols, till now as far as author is aware, there is no well known
project that operates a fair ordering protocol (except Chainlink has promised
it since September 2020[6]).

We notice all existing fair ordering protocols have rather stiff ordering
policy enforcements regardless of the underlying fairness notions. Out of all
practical solution, Themis[15] is the most communication efficient protocol,
but still requires $O(nTL+n^{2}T)$ communication complexity, where $L$ is the
transaction size, $T$ is number of transactions, and $n$ is total number of
nodes111Themis SNARK[15] has $O(nTL+nT)$ communication complexity. But SNARK
requires cryptographic computation order of magnitude higher than commitments
or hashes. It serves only the theoretical purposes, as self-described by [15].
Importantly, Themis consensus protocol is entangled with complexity to deal
with Condorcet Cycle, which is a phenomenon that the ordering among
transactions are chained together to form nested loops, as the result those
transactions have to be batched together. Although the protocol is carefully
designed, the resulting protocol entails a great complexity.

This work explores a new notion of fair ordering, referred as probabilistic
fair ordering. The purpose is to relax the criteria of existing fair order, by
removing the requirement to have all nodes receiving identical transactions.
We then introduce a class of protocols, called Travelers, based on a new
notion called probabilistic ordering linearizability. Ordering linearizability
is proposed by Pompē[29], that requires a real clock on each node to lock a
transaction with a timestamp. Because timestamps are linear, all locked
transactions with timestamps can be totally ordered by a simle sorting. It is
a key insight mentioned in Pompē[29] that avoids the complex puzzle of
Condorcet cycle. But even with a clock, Pompē still requires a communication
complexity of $O(n^{2}TL+n)$. With the new relaxed notion of probabilistic
ordering linearizability, Travelers can achieve $O(c\log({n})TL+D)$
communication complexity with error probability $\epsilon=\frac{1}{n^{c}}$ for
some system parameter $c$, where $D$ is the total communication complexity for
some consensus protocol. In Travelers, the precision of fairness notion
depends on how large the mismatch $\delta$ among nodes’ clock and network
latency $\Delta$. We elaborate on the probabilistic notion in Section 3 and
provide a concrete fairness definition for one Travelers protocol in Section
5.2.

###  1.1 Travelers system

At the high level, we can use a framework to split the system into two
components: transaction submission and consensus. Transaction submission is
the part responsible for getting sufficient nodes to receive the transaction,
and it is where the transaction size $L$ shows up in the complexity analysis.
The consensus part is responsible for making agreement on some data critical
to the consensus protocol. We will further elaborate this framework in the
next Section. Unlike other fair ordering protocol, the submission component in
Travelers neither requires a P2P dissemination network, nor it is required to
send transactions to all correct nodes. Reducing the dissemination phase is
important to improve the first term of the communication complexity from
$O(nL)$ to sublinear in $L$, see Table 1.

Figure 1: Travelers architecture. Suppose every hub consists of a single node.
Each of three copies of transaction has distinct path. Nodes $a,b,c$ are the
nodes from the final hubs. The path containing node $c$ consists of regular
hub only. We use $o_{ord}$ to denote the locked timestamp.

In our submission component, we design a routing protocol that moves a
transaction through a series of hubs on a path. The transaction receives
timestamp at each hub, and all timestamps are used together by the routing
protocol to produces the locked timestamp, which is used for ordering. Figure
1 displays several paths each contains three hubs. A hub is a collections of
nodes, whose membership and size are determined by some assignment function
decided by the protocol. We will discuss more about the assignment function
from Appendix 8.3. However, in Figure 1 each hub is assigned with only one
unique node.

When a transaction arrives, a hub timestamps its arrival time and approves it
with a cryptographic signature on both metadata and the transaction payload. A
corrupted hub indicates the set has significant amount of malicious nodes,
such that they alone can approve the transaction with arbitrary timestamp. On
the other hand, if honest nodes alone can approve the transaction, it is
called the regular hub. If all of hubs in a path approved the transactions,
the nodes from the last hub deliver all timestamps to the consensus along with
signatures and transaction payloads. We define maximal timestamps in the path
as the locked timestamp for the transaction on that path.

In Figure 1, we show a red path consisted entirely of malicious hubs. It is
referred as the corrupted path, and similarly a path of all regular hub as the
regular path. We want to decrease its probability of corrupted path such that
it is less than $\epsilon$. Because if no regular hub can bound the timestamp,
an adversary can lock arbitrary timestamp for any transactions that travel the
path. Not only we need to lower $\epsilon$, the routing protocol also needs to
cap the total possible number of paths by using a deterministic random
function. Because there are combinatorial number ways to arrange hubs into
distinct paths, no matter how small $\epsilon$ be, an adversary can find a
corrupted path if given sufficient chances.

When a client sends multiple copies of the same transaction to traverse
distinct paths, each would generate a different locked timestamp. It is the
ordering rule’s responsibility to determine the canonical timestamp for the
transaction. Once one canonical timestamp is selected by the ordering rule,
because timestamps are linear by nature, the total order of transactions can
be derived by a simple sorting algorithm. The right side of Figure 1 provides
global view about the ledger after the sanitization.

The notion of ordering linearizability decouples the ordering and consensus,
as pointed by many works[29, 13, 28]. Because timestamps lock transactions,
the only part we need from the standard consensus is just an agreement on a
stream of bit, which is data availability, so that anyone can be retrieved
them later. Standard asynchronous and partial asynchronous BFT protocol
inherently satisfy data availability, but make it a requirement for every node
to download the entire data during the agreement protocol. For fair ordering
protocol, censorship resistance is an important consensus property but missed
by many standard leader based protocol . It guarantees some transaction is
included in the next block even if the current and future leaders have the
intent of censoring. Travelers requires the underlying consensus to have this
property in order to commit the locked timestmap. Most standard leaderless BFT
protocol has censorship resistance in nature. For example, DispersedLedger[26]
is an asynchronous protocol that uses Erasure code to improve throughput.
VABA[1], Dumbo-MVBA[17] are leaderless protocols that have communication
complexity of $O(n^{2})$. Because timestamps lock transaction before
consensus, the confirmation latency required by the consensus protocol does
not affect final ordering. BigDipper[25], contains more rigorous formulation
and presentation, and shows that the complexity can be further reduced to
$O(\log(n)\lambda)$, resulting to a protocol with only
$O(c\log(n)TL+\log(n)n\lambda)$ overall communication complexity.

Similar to many protocols based on the notion of ordering linearizability,
Travelers can further protect transaction with encryption. The idea is to let
the client encrypt the transaction, so that the ciphertext can only be
decrypted toward the end of the path, such that no adversary has sufficient
time to frontrun the transaction. We discuss it in Section 4.5.

###  1.2 Comparison with other approaches

There are two general approaches inside the fair-ordering category. Almost all
of them can be split into the two components we used in the last section. The
first approach uses the notion of ordering linearizability, represented by
protocols including Pompē[29], Decentralized Clock Network(DCN)[13] and
Lyra[28]. At the high level, every transaction first goes through a
transaction submission component in order to lock a timestamp. For every
transaction, Pompē devises its broadcast protocol to ensure everyone agrees on
the median timestamp with $O(n^{2})$ complexity. DCN created a timestamp
agreement protocol that has $O(n^{3})$ complexity. Lyra designs a Validated
Value broadcast protocol based on Binary Agreement protocol[18] which take
$O(n^{2})$ complexity. All of them requires all nodes to receive the
transaction. For the consensus component, they use some modified version of
standard consensus protocol for replicating transaction along with the
timestamp. Both Lyra[28] and DCN[13] claim they do not assume a synchronous
clock. Those protocol can easily incorporate threshold encryption like
content-agnostic approach to provide further front-running protection.

The second common notion for fair ordering is batch order and differential
order fairness [5, 14, 15]. They rely on relative transaction ordering to
derive the final canonical ordering. In the transaction submission component,
all transaction is assumed to be propagated in a dissemination network which
ensures all honest nodes to observe everything eventually. This is the
necessary requirement for those protocols, so that every honest node can
create its local logical ordering to decide what can be ordered safely. In the
consensus component, because there are possible Condorcet cycle among the
transaction, the consensus protocol needs to handle more works to ensure only
subset of observed transactions can be confirmed.

Table 1 summarizes a comparison among each algorithm, and its analysis is
presented in Appendix 7. Like Quick Fair Ordering[5], we include the
transaction size $L$ in the table, since transactions might take significant
size as they become more complex. The number of transactions $T$ is a part of
analysis, because clients’ traffic is out of protocol control, this is
beneficial to take it into consideration to understand how system behave in
response to workload. $\lambda$ denote the size of signature and hash value,
and is typically $32$ bytes. Compared to others, Travelers reduces
communication complexity in both submission and consensus component. Travelers
is the first fair ordering protocol that achieves sublinear communication
complexity in the transaction submission phase, it is because we use
probabilistic fair ordering that allows some $\epsilon$ error. Since Travelers
is family of protocols, in Table 1 we include two versions of it. Travelers-
Speed is optimized for faster latency to traverse a path. Travelers-Light is
optimized for the lowest communication complexity. Not only Travelers is
efficient, it is also flexible because both the routing protocol and the BFT
consensus can be replaced easily by protocols with similar properties. For
example, all DAG based protocols can use Travelers to get fair ordering, like
BullShark[23], Tusk[10]. In the routing protocol, both hub size and path
length can be tuned; the assignment functions can also be designed to work
with a topology consisntent to distributed validators technology like Obol[20]
to achieve decentralization and threshold encryption.

Table 1: Difference of ordering notion and complexity

Fairness | Algorithm | Security | Tx Submission | Total
---|---|---|---|---
Notion | Complexity | Assumption | Per payload |  $T$ Payload
|  |  | Complexity | Complexity
Batch-Order-Fairness[15] | Themis | $1/4$ | $O(nL)$ | $O(nTL+n^{2}T\lambda)$
Differential-Order-Fairness[5] | Quick o.-f. | $1/3$ | $O(n^{2}L+n^{3}\lambda)$ | $O(n^{2}TL+n^{3}T\lambda)$
Ordering Linearizability[29] | Pompē | $1/3$ | $O(nL+n^{2}\lambda)$ | $O(nTL+n^{2}T\lambda+n\lambda)$
Prob. Ordering Linearizability | Travelers-Speed | $1/3$ | $O(c\log^{2}(n)L)$ |  $O(c\log^{2}(n)TL+n^{2}\lambda$)
Prob. Ordering Linearizability | Travelers-Light | $1/3$ | $O(c\log(n)\lambda+L)$ |  $O((c\log(n)\lambda+L)T+\log(n)n\lambda)$)222By using iterative routing from Appendix 8.2, and BigDipper for consensus

In Section 4.4, we delineates the adversary action spaces, and in Section 5.1
we reason about how Travelers defends against MEV attacks.

##  2 Background

###  2.1 BFT problems

A Byzantine Fault Tolerant(BFT) protocol is a system of $n$ nodes that reaches
consensus on a common state. Clients submit transactions to some honest nodes
in order to modify the state. To reach agreement, nodes communicate among in a
network which can be modeled as asynchronous, partial asynchronous and
synchronous. Most real system choose to use either asynchronous or partial
asynchronous network model. In a partial asynchronous network, there is a
notion of Glocal Stabilization Time, after which all transaction arrive at
known bounded duration. Whereas in the asynchronous network model, messages
among nodes are eventually delivered, but its time is unknown. A BFT protocol
has to satisfy the safety and liveness properties:

  * •

Safety: At any time, the ledger of every pair of honest nodes is a prefix of
another

  * •

Liveness: Transactions submitted by honest clients are eventually added into
the ledger of honest nodes.

There is a lower bound for the number of malicious nodes. For most standard
BFT protocol, it is $n\geq 3f+1$. For Themis, it is effectively $n\geq 4f+1$.

###  2.2 Condorcet Cycle and Relaxation

Drawn from Social choice theory, a Condorcet cycle is a phenomenon that groups
of transitive relation results into a final non-transitive relation. For
example, suppose three voters $a,b,c$ rank three commands,
$c_{1},c_{2},c_{3}$. A Condorcet cycle arise if the following ranks are given:
$c_{1}^{a}\prec c_{2}^{a}\prec c_{3}^{a},c_{2}^{b}\prec c_{3}^{b}\prec
c_{1}^{b},c_{3}^{c}\prec c_{1}^{c}\prec c_{2}^{c}$, where the superscript
denotes the voter and $\prec$ is some transitive relation. At the end, there
is no conclusion which command is ranked the highest. Due to this fact,
previous work[16] shows that it is impossible to define fairness based on
reception order and instead define batch-order-fairness, such that all
transactions in the cycle are delivered altogehter. However, sometimes when
there is Condorcet cycle spanning across multiple blocks intervals, a
transaction might have been already recognized by the consensus, but needs to
wait for multiple blocks before confirming the transaction. It is due this
fact, the consensus protocol based on batch order fairness needs not only just
the data availability, it needs to decide what transactions are allowed to
confirm. Ordering linearizability avoids this problem and has been pointed by
Pompē, Lyra, DCN[13, 28, 29]. In Themis, nodes and the leader exchange not
only the transactions list, but also the leader is responsible for aggregating
the updates messages from the nodes. In order to prevent a violation to a weak
notion of liveness, special techniques like unspooling or deferred ordering
are introduced to Themis.

##  3 Probabilistic Order Fairness

We introduce a high level notion called Probabilistic Order Fairness. We start
by introducing Ordering Linearizability, and based on that we state where the
probabilistic component arise in the new notion. In simple term, Ordering
Linearizability requires that

  * •

if the highest timestamp of a transaction $tx_{a}$ provided by any honest
nodes is lower than the lowest timestamp of a transaction $tx_{b}$ provided by
any honest nodes, and if both transactions are committed, then $tx_{a}$ will
occur before $tx_{b}$ in the final totally ordered ledger.

In Pompē, it is implemented by locking timestamps for all commands, so that
the ordering linearizability can be enforced. To lock a transaction, all nodes
need to first receive the transaction, then broadcasts and agree on the median
timestamp, which is both upper and lower bounded by timestamp generated by
honest nodes.

However, when Pompē defines the fairness, it is implicit that every node has a
vote on the final results, which is achieved by having everyone receiving the
transaction. In our case, only nodes along the path will receive the
transaction, and there is a case that some transaction whose delivery is
entirely determined by the malicious hubs. So in the probabilistic version, we
made the following modification based on the previous definition:

  * •

For every new block in the BFT protocol, there is $\epsilon$ probability that
some transaction $tx_{c}$ provided by a corrupted path can be added into the
block at any locations, for the remaining $1-\epsilon$ probability, if
timestamp of a transaction $tx_{a}$ provided by a regular path is $x$ duration
before the timestamp of a transaction $tx_{b}$ provided a regular hub, and
both transactions are committed, then $tx_{a}$ will occur before $tx_{b}$ in
the final totally ordered ledger.

where $x$ is the duration parameter affected by the length of the path, clock
mismatch among all nodes and exact routing algorithm. We elaborate in Section
4.

Travelers is a set of possible realization for such probabilistic notions, and
it is likely other systems might achieve the similar properties. Compared to
Pompē, Travelers relaxes the assumption that everything is received by
everyone, hence it has to add new definition to cover the case.

###  3.1 Error Interpretation and Probability in Consensus

The probabilistic notion relax the condition which a protocol has to satisfy,
and therefore allows us to simplify protocol. The error probability $\epsilon$
can be set in two ways depending on the interpretation. Algorithmically, we
can set the target $\epsilon$ to be negligible by letting
$\epsilon=O(1/n^{c})$ where $n$ is the number of nodes. We can also interpret
$\epsilon$ economically. Suppose the cost of attack per block is $C$, and the
revenue from block reordering is $D$, then as long as $\frac{C}{\epsilon}>>D$,
there is no benefits for adversary to initiate an attack.

We note that there has a history to introduce probability into the consensus
properties. In the classic partial synchronous BFT protocols, like Hotstuff,
PBFT, the liveness property guarantees an eventual inclusion of a transaction
depending on if the next leader is honest, which is a probabilistic statement.
For asynchronous BFT protocols, both safety and liveness are probabilistic
requiring a random coin for ensuring the correctness. In the next section, we
elaborate on ordering linearizability, which is used for developing a specific
version of fairness.

##  4 Routing Protocols

At the high level, the goal of a routing protocol is to deterministically
assign nodes to hubs, and to create a fixed number of random paths for
transactions to traverse. After a client submits copies of a transaction to
expected number of paths, it is the goal of the routing protocol that there is
a constant probability that at least one of the paths is made of entirely
regular hubs. Similarly for adversary, the protocol ensures there is
negligible probability that there is a path made of entirely corrupted hubs,
even if the adversary sends the transaction to all possible paths. Those paths
are randomly generated for preventing adversary from manipulating the creation
process. In every block, there are only a fixed number of path available
regardless of transactions, so that no adversary can grind its transactions to
discover the corrupted path. To achieve the above property, the protocol
design makes use a key assumption from the standard BFT protocol that there
are at most $1/3$ malicious nodes. In the following, we show how to use a
common technique in computer science called boosting to design the routing
protocols. Due to the size limitation, we state the properties of the routing
protocol in Appendix 8.1. The path traversal mechanism is stated in Appendix
8.2. The Assignment functions in Appendix 8.3.

###  4.1 Technique of Boosting

Suppose there are two types of hubs: a regular hub which occurs at probability
of $p_{h}$, and a corrupted hub with the probability $p_{d}$, such that
$p_{h}>p_{d}$. Since $p_{h}>p_{d}$, we can represent $p_{d}^{\rho}=p_{h}$, for
some $\rho<1$. By arranging the term, we got
$\rho=\frac{\log{1/p_{h}}}{\log{1/p_{d}}}$. Suppose all path has a length of
$k$, the probability of a path of entire honest nodes is therefore
$g_{h}=p_{h}^{k}$, and for a path of corrupted hubs is $g_{d}=p_{d}^{k}$. As
length of path $k$ increases, the probability of occurrence for both type
becomes negligible. Although both are very small, there is a large gap between
the two small number. With some calculation, we can show $g_{d}^{\rho}=g_{h}$
or equivalently $\frac{\log{1/g_{h}}}{\log{1/g_{d}}}=\rho$. Suppose all paths
are created independently, as the client can try distinct paths linear number
of time, the probability for both type increases linearly. Up to some point
after trying $L$ different paths, there is a constant probability the client
would hit a honest path. But since there is a large gap between the two
probabilities $g_{h}$ and $g_{d}$. It is possible to find a $L$, such that the
product $g_{h}L=O(1)$, but $g_{d}L$ is still negligible. By keeping the total
number of possible path low enough, such that there is no much room beyond $L$
tries, we can keep the chance for any adversary to find any corrupted paths
negligible. In the following, we demonstrate two different designs of the
routing protocol using this common technique. However, as the hub size and
path length can be adjusted, there are much more possible design there.

###  4.2 Path of Singleton

Suppose every node becomes its own hub, then by BFT adversary assumption,
$p_{d}=1/3$ and $p_{h}=2/3$. As the result, $\rho=0.369$. Because we want
$g_{d}={p_{d}^{k}}=\frac{1}{n^{\tau}}$ be negligible, where ($\tau\geq 1$). We
can rearrange the term to get the path length
$k=\frac{\tau\log{n}}{\log{1/p_{d}}}$, then probability of both paths can be
computed as

$\displaystyle g_{h}$
$\displaystyle={p_{h}}^{\frac{\tau\log{n}}{\log{(1/p_{d})}}}=n^{-\frac{\log{(1/p_{h})}}{\log{(1/p_{d})}}\tau}=n^{-\rho\tau}=n^{-0.369\tau}$
(1) $\displaystyle g_{d}$ $\displaystyle=n^{-\tau}$ (2)

The second equality in Eq(1) comes from the logrithmic rule
$a^{\log{b}}=b^{\log{a}}$. By limiting the total number possible paths to
$o(n^{\tau})$, the probability is always negligible for adversary to get a
path made of entirely malicious nodes. If a client retry $L$ different paths,
the lower bound for the honest client that at least one path is regular is
$1-(1-g_{h})^{L}$. By adjusting $L$, we can ensure there is a constant
probability which one of the transaction will go through a regular path made
of entirely honest nodes.

With those numbers, we can easily build a simple protocol with communication
complexity of $O(n^{0.369(1+c)})$ with $\epsilon=1/n^{c}$. However, in order
to ensure the communication complexity be sublinear, we require $c<1.71$. The
system allows $n$ total possible path, such that every node is a starting
point of some path. By letting $\tau=c+1$, although adversary can try $n$
different times, by taking the union bound the upper bound probability for
adversary is $n^{-c}$. On the other hand, if a client sends transaction to
$n^{0.369(c+1)}$ nodes. The probability with at least one regular path is
$1-(1-g_{h})^{L}$. Suppose we have $n=200,c=1.2$, then the probability with at
least one regular path is $0.576$, with $L=n^{0.8118}$. To further reduce the
complexity, we need to increase the hub size.

###  4.3 Non-Singleton hubs

In the last section, $p_{h}$ and $p_{d}$ only differs by a constant factor, so
the approach we use to differentiate them is by increasing the path length in
order to increase the gap between the two probability. However, if $p_{h}$ and
$p_{d}$ already differs by more than constant factor, we can reduce the length
of path and therefore decrease the number of tries for transactions to find a
regular path.

Suppose now each hub is made of $q$ distinct nodes and every node is draw
independently with replacement. We know that it is binomial distribution with
mean equal to $2/3$, and the binomial distribution is a good approximation to
a distribution when nodes are draw without replacement if $n$ is much larger
than $q$. Similarly for the distribution for malicious nodes, it can also be
modeled as a binomial distribution with mean equal to $1/3$. The left diagram
of Figure 2 displays both distributions, when $q=6$. Since the hub is not
singleton, we need to define a threshold, $t$, which is the minimal number of
signatures to get approved by the hub. A small $t$ makes it easy to pass a
hub, but it also increases the chance that a hub gets corrupted. We start with
$t=\frac{2n}{3}$. In the left Figure 2, we denotes the mass of probability for
passing event in the shaded area. However, as we increase the size of hub, as
shown in Figure 2(b), while keeping $t=\frac{2n}{3}$, the difference between
$p_{h}$ and $p_{d}$ becomes much more significant. Since $t$ is equal to the
mean of binomial distribution for honest nodes, $p_{h}=1/2$. For computing
$p_{d}$, we can derive it from Chernoff bound ([2] Theorem 1), where $D$ is
the Kullback-Liebler distance, and $p=1/3$

$\displaystyle p_{d}$ $\displaystyle\leq\exp\\{-qD(2/3||1/3)\\}$ (3)
$\displaystyle=\exp\\{-q(\frac{2}{3}\log{\frac{2}{3p}}+\frac{1}{3}\log{\frac{1}{3(1-p)}})\\}=\exp\\{-\frac{q}{3}\\}$
(4)

By letting $q=3\log{n}$, we have $p_{d}=n^{-1}$. To arrive at
$\epsilon=1/n^{c}$, there are two approaches. We can let the path length
$k=c$. Or alternatively, we could let $q=3(c+1)\log{n}$, let $k$ be a small
constant. If we choose choose $k=2$ and let $t=2q/3$, then $p_{h}=1/2$. The
client only needs to submit its transaction to eight different path to ensure
one regular path with $90\%$ probability.

In summary, by letting $t=2q/3$ and $k$ be a small constant, we can achieve
$O(c\log{n})$ communication complexity to ensure an error probability of
$\epsilon=1/n^{c}$. However, the protocol does not have to set $t=2q/3$, the
threshold can be adjusted by the system to balance between $p_{d}$ and
$p_{h}$.

Figure 2: Hub Distributions

###  4.4 Timestamp rendered by types of paths

The compositions of a path affect the properties of final timestamps. In this
section, we delineate all types of hubs, and analyzes how they affect the
properties of a path and the resulting timestamps. Understanding them is
important to reason about how Travelers defend against the MEV attacks in the
Section 5.1.

We start by examining the definition of hubs. Suppose the size of a hub be $q$
and the passing threshold be $t$. Depending on how many nodes of each type are
present in the hub compared to $t$. Let’s define an binary event PASS by
comparing if certain types of node alone can approve the transaction, i.e. if
the number of certain type nodes is at least $t$. We can define four types of
hubs, as shown in in Figure 3.

Figure 3: Four types of Hubs
Figure 4: Timestamp Types to paths

A hub of Type 3 occurs when both honest and malicious nodes alone can approve
the transaction. But since we want to decrease the chance of a corrupted hub,
we can simply rmove this case by setting $t>q/2$. A hub of Type 1 is
equivalent to our previous definition of regular hub, and a hub of Type 4 is
equivalent to our definition of corrupted hub. The last type of hub we have
not explored is Type 2, when a hub is in the situation of impasse if neither
honest and malicious nodes alone can approve the transactions, and we want to
avoid it for liveness reason.

After defining all types of hub, we can start analyzing types of path made of
those hubs. In a path made of corrupted hubs, a transaction does not need to
be sent on the network to get approval, because the adversary who holds the
private keys can approve everything in a central location, any possible
timestamp can be manipulated as long as the timestamp does not violate
consensus. But this is rare by lowering $\epsilon$. Similarly, a regular path
is made of regular hubs. It produces a true timestamp reflective of current
network and clock condition. But the most common case are paths made of a
mixture of corrupted and regular hubs.

When adversary wants to delay an transaction, as long as there exist one hub
along the path that honest nodes cannot approve the transaction alone, the
adversary can control to delay the transactions. A delayed timestamp must have
a timestamp later than the earliest true timestamp, otherwise it is advancing
timestamps of the transaction.

Sometimes an adversary wants to speedup the delivery and therefore advance the
timestamp. Suppose the last $x$ hubs on some path are corrupted type 4 hubs,
adversary can use a simple method to make it deliver faster, by reusing the
last timestamp from honest hubs. There is another way to advance the timestamp
if there is a consecutive corrupted hubs on the path (not necessarily from the
end). Since all malicious nodes can be controlled by a single adversary, the
first corrupted hub can create the approval for all the following corrupted
hubs, and therefore help the transaction moves faster than it should have.
Figure 4 summarizes four types of outcomes depending on how a path is
constituent of.

Depending on the purpose of adversary, it can selectively choose either tools
to advance or delay some transactions. For sandwich attack, adversary can
setup a sandwich trap, and then either advance or delay some victim
transaction, in order for the victim fall into the trap. However, by devising
the ordering rule properly, we can prevent the adversary from using delaying
timestamp entirely. The idea is to always use the earliest timestamp as the
canonical timestamp, we will elaborate more in Section 5.3 and 5.1. Then the
only tactics which adversary can use is to advance the timestamp of the
victim’s transaction. But it makes the sandwich attack much harder because
adversary has to setup the trap earlier than victim’s transaction. By the
property of automated market maker, the adversary incurs a loss if attack is
not successful.

###  4.5 Encrypting the transaction

However, if we assume adversary has an advanced infrastructure that is
magnitude faster than regular Internet backbone, there is a chance that
adversary can peek the content of the victim transaction and still have time
to setup a sandwich trap. In this section, we look at how to incorporate
encryption to delay the time when adversary can know about a transaction,
therefore making it impossible to setup a trap early enough.

There are multiple ways to implement such encryption scheme. At the high
level, there must be at least one hub that can decrypt the entire transaction.
If the hub contains only one node, the decryption is simple. However, if the
hub size has $q$ nodes, there are exponential signature combinations. Unless
$q$ is small enough, otherwise we need a threshold encryption scheme to make
it efficient. Let’s define a decryption set $S$ that contains hubs capable of
performing decryption. The hubs can either be group of nodes capable of
threshold decryption, or hub whose size is small enough. For example $6$
choosing $5$ contains only 6 possibilities. For any path that has the ability
to perform decryption, it must contain at least one hub from the decryption
set $S$. Ideally the decryption hub is at the end of the path, so that the
routing protocol can hide the transaction as long as possible. If we use
iterative path traversal method discussed in Appendix 8.2, the initiator needs
to provide all approval signatures from the beginning of the path to convince
the decryption hub that enough time is spent on traversal. A transaction can
be encrypted layer by layer if multiple hubs in the decryption set is
available. It offers a better protection in case one decryption hub is
corrupted. Our scheme is slightly different from the threshold encryption used
by Shutter or anything that uses commit-and-reveal scheme. In our scheme, the
plaintext will be available after the last hub, so data can be read
immediately without further processing.

##  5 Travelers

Travelers is a consensus protocol that provides probabilistic fair ordering
notion we introduced in Section 3. In this section, we first provide an
overview on the strategy which Travelers use to prevent ordering attacks. We
then show how to design the ordering rule to support such strategy by removing
delayed timestamps. Because ordering linearizability decouples the ordering
from the underlying consensus protocol, the BFT protocol is very modular.
However, it is important to ensure the BFT protocol has censorship resistance.
We provide an overview on the category of BFT protocols that satisfy the
requirements.

###  5.1 Strategy to prevent reordering attacks

In Section 4.4, we show that four types of locked timestamps are generated
depending on the paths they are from, as shown in Figure 4. For an adversary,
since the true timestamp is undesirable, and manipulated timestamp is bounded
with $O(n^{-c})$ probability, the adversary only has two tools for arranging
its attack: by advancing timestamps and by delaying timestamps. In the Section
5.3, we show by designing proper ordering rules, we can remove the delayed
timestamps from the attack vectors, as long as there is at least one true
timestamps being committed by the consensus protocol. So the only tool which
an adversary can affect the ordering is using advanced timestamps by speeding
up its or victim’s transactions. However, by using encryption in Section 4.5,
we can ensure that the clients’ transactions have completed most of its
traversal on the path. At last, we note it is up to clients to decide how much
front-running protection being offered, a worried client would sends
transaction to many paths to ensure the true timestamps from the regular hub
is not censored, and the client would use the most secure encryption discussed
in Section 4.5 to make sure the transaction is not front-runnable.

###  5.2 $1-\kappa$ Probabilistic ordering linearizability Property

We now formally define the probabilistic properties which overall Travelers
has, based on the probabilistic fair ordering notion. The proof is provided in
Appendix 9.1.

  * •

For every new block in the BFT protocol, there is $1/n^{c}$ probability that
some transaction $tx_{d}$ provided by a corrupted path can be added into the
block at any locations. For the remaining $1-1/n^{c}$ probability, if there is
$1-\kappa$ probability that the timestamps of both transaction $tx_{a},tx_{b}$
provided by some regular paths are committed, then with $1-\kappa$ probability
the following fairness notion holds: if the timestamp of $tx_{a}$ is
$4k\Delta+2\delta$ duration before the timestamp of $tx_{b}$, then $tx_{a}$
will occur before $tx_{b}$ in the final totally ordered ledger, where $k$ is
the number of hubs in a path.

We added a new probability $1-\kappa$ to ensure that the protocol covers the
case that both transactions are committed. Im compute the resolution
$4k\Delta+2\delta$, the protocol uses the iterative routing, which doubles the
latency to traverse a path. If we choose to use a leaderless asynchronous BFT
protocol which is inherently censorship resistance, then $\kappa$ can be
decreased to negligible. DispeseredLedger[26] invents a technique called
inter-node linking that guarantees every collected transaction is delivered.
Similarly, all DAG-based protocols can fetch transactions that were submitted
but not confirmed in the past, and confirm them in the new blocks. However,it
requires longer confirmation latency, which we discuss in Section 5.3.

###  5.3 Ordering Rule

When a client sends a transaction on multiple paths, the same transaction
would have been locked many timestamps. The ordering rule decides which one
becomes the canonical timestamp used by the totally ordered ledger.

The core observation is that we always have a set of true timestamps committed
in the final ledger. By letting the earliest time among them as the canonical
timestamps, we filter out all any delayed timestamps. By definition any
timestamps that is earlier than the earliest true timestamp belongs to the
category of advancing timestamps.

Note that the protocol does not need to process anything to specify which
timestamp is canonical for each transaction. It is because if a party
retrieves all confirmed transactions from the BFT protocol, the party can
collects all the timestamps corresponding to a transaction and determine the
canonical timestamp by a sorting algorithm. For this reason, consensus is
simply a matter of arriving agreement on a stream of bit, which is much
simpler than deducing Condorcet cycle and mitigating the nested loops.

Sometimes there might be a new transaction that locks to a timestamp earlier
than what is already confirmed in the past. There are two methods to deal with
it. The simplest approach is to add the transaction to the latest unconfirmed
block with a new timestamp as early as possible without violating the block
boundary. Another way would be altering confirmation rule at the application
layer, such that the most recent $x$ block are subject to changes, depending
the timestamps of transactions in the new block. However, we have to modify
the property a bit to cover the effect when there is a corrupted path.

###  5.4 Consensus and Censorship Resistance

Travelers is intended to be modular systems. However, there is another desired
property called censorship resistance, which is not covered by most BFT
protocol. It is important for Travelers, because if the leader is malicious,
it can selectively remove the earlier timestamps, so that only the delay
timestamped manipulated by the adversary is regarded the canonical timestamp
for the transactions. Then the adversary can setup a sandwich and delay the
victim transactions to fall into the trap.

It can be fixed by requiring the underlying consensus protocol be censorship
resistance. For example, most leaderless protocols are censorship resistant.
But they all have at least communication complexity of $O(n^{2})$ because of
all-to-all communication pattern. Both DispersedLedger and Dumbo-MVBA[17] use
erasure code to make agreement on a stream of bits without downloading the
whole data. Dumbo-MVBA has a communication complexity of $O(n^{2})$. BigDipper
provides a more systematic presentation, and offers $O(n^{2})$ or
$O(n\log{n})$ communication complexity.

##  6 Conclusion

We present Travelers composed of a flexible routing protocol and a censorship
resistant BFT protocol. It achieves a notion called probabilistic ordering
linearizability with $O(c\log(n)L+n^{2})$ communication communication
complexity. However, the probabilistic notion can also be applied to batch-
order-fairness. It will be interesting to discover new protocols based on
relative transaction order.

## References

  * [1] Abraham, I., Malkhi, D., Spiegelman, A.: Validated asynchronous byzantine agreement with optimal resilience and asymptotically optimal time and word communication. arXiv preprint arXiv:1811.01332 (2018)
  * [2] Arratia, R., Gordon, L.: Tutorial on large deviations for the binomial distribution. Bulletin of mathematical biology 51(1), 125–131 (1989)
  * [3] blocknative: blocknative, https://docs.blocknative.com/blocknative-relay
  * [4] bloxroute: bloxroute, https://bloxroute.com/
  * [5] Cachin, C., Mićić, J., Steinhauer, N., Zanolini, L.: Quick order fairness. In: International Conference on Financial Cryptography and Data Security. pp. 316–333. Springer (2022)
  * [6] chainlink: chainlink, https://blog.chain.link/chainlink-fair-sequencing-services-enabling-a-provably-fair-defi-ecosystem/
  * [7] coinmarketcap: coinmarketcap, https://coinmarketcap.com/currencies/ethereum/
  * [8] Constantinescu, A., Ghinea, D., Heimbach, L., Wang, Z., Wattenhofer, R.: A fair and resilient decentralized clock network for transaction ordering (2023)
  * [9] Daian, P., Goldfeder, S., Kell, T., Li, Y., Zhao, X., Bentov, I., Breidenbach, L., Juels, A.: Flash boys 2.0: Frontrunning, transaction reordering, and consensus instability in decentralized exchanges (2019)
  * [10] Danezis, G., Kokoris-Kogias, L., Sonnino, A., Spiegelman, A.: Narwhal and tusk: a dag-based mempool and efficient bft consensus. In: Proceedings of the Seventeenth European Conference on Computer Systems. pp. 34–50 (2022)
  * [11] Eden: Eden, https://docs.edennetwork.io/
  * [12] Flashbot: Flashbot, https://www.flashbots.net/
  * [13] Heimbach, L., Wattenhofer, R.: SoK: Preventing transaction reordering manipulations in decentralized finance. In: Proceedings of the 4th ACM Conference on Advances in Financial Technologies. ACM (sep 2022). https://doi.org/10.1145/3558535.3559784, "https://doi.org/10.1145%2F3558535.3559784"
  * [14] Kelkar, M., Deb, S., Kannan, S.: Order-fair consensus in the permissionless setting. In: Proceedings of the 9th ACM on ASIA Public-Key Cryptography Workshop. pp. 3–14 (2022)
  * [15] Kelkar, M., Deb, S., Long, S., Juels, A., Kannan, S.: Themis: Fast, strong order-fairness in byzantine consensus. Cryptology ePrint Archive (2021)
  * [16] Kelkar, M., Zhang, F., Goldfeder, S., Juels, A.: Order-fairness for byzantine consensus. Cryptology ePrint Archive, Paper 2020/269 (2020), https://eprint.iacr.org/2020/269, https://eprint.iacr.org/2020/269
  * [17] Lu, Y., Lu, Z., Tang, Q., Wang, G.: Dumbo-mvba: Optimal multi-valued validated asynchronous byzantine agreement, revisited. Cryptology ePrint Archive, Paper 2020/842 (2020). https://doi.org/10.1145/3382734.3405707, https://eprint.iacr.org/2020/842, https://eprint.iacr.org/2020/842
  * [18] Mostéfaoui, A., Moumen, H., Raynal, M.: Signature-free asynchronous byzantine consensus with t¡ n/3 and o (n2) messages. In: Proceedings of the 2014 ACM symposium on Principles of distributed computing. pp. 2–9 (2014)
  * [19] network, S.: Shutter network, https://shutter.network/
  * [20] Obol: Obol, https://docs.obol.tech/docs/int/key-concepts#distributed-validator-threshold
  * [21] Sikka: Sikka, https://sikka.tech/projects/
  * [22] skip: skip, https://skip.money/docs
  * [23] Spiegelman, A., Giridharan, N., Sonnino, A., Kokoris-Kogias, L.: Bullshark: Dag bft protocols made practical. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. pp. 2705–2718 (2022)
  * [24] Wadhwa, S., Zanolini, L., D’Amato, F., Asgaonkar, A., Zhang, F., Nayak, K.: Breaking the chains of rationality: Understanding the limitations to and obtaining order policy enforcement. Cryptology ePrint Archive, Paper 2023/868 (2023), https://eprint.iacr.org/2023/868, https://eprint.iacr.org/2023/868
  * [25] Xue, B., Deb, S., Kannan, S.: Bigdipper: A hyperscale bft system with short term censorship resistance (2023)
  * [26] Yang, L., Park, S.J., Alizadeh, M., Kannan, S., Tse, D.: $\\{$DispersedLedger$\\}$:$\\{$High-Throughput$\\}$ byzantine consensus on variable bandwidth networks. In: 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22). pp. 493–512 (2022)
  * [27] Yang, S., Zhang, F., Huang, K., Chen, X., Yang, Y., Zhu, F.: Sok: Mev countermeasures: Theory and practice (2022)
  * [28] Zarbafian, P., Gramoli, V.: Lyra: Fast and scalable resilience to reordering attacks in blockchains. In: 2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS). pp. 929–939 (2023). https://doi.org/10.1109/IPDPS54959.2023.00097
  * [29] Zhang, Y., Setty, S., Chen, Q., Zhou, L., Alvisi, L.: Byzantine ordered consensus without byzantine oligarchy. In: 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). pp. 633–649 (2020)

##  7 Complexity Analysis

###  7.1 Themis

Themis requires a desemination network, such that everyone can receive the
transaction of size $L$, therefore the total communication complexity is
$O(nL)$. In the consensus part, suppose there are $T$ total transaction, each
node has to provide the relative ordering among the $T$ transactions to the
leader. So the leader has a complexity of $O(nT\lambda)$, where $\lambda$ is
the hash digest to used to denote a transaction among the relative ordering.
Because the leader in the practical non-SNARK version needs to send the
relative ordering of all nodes to every node, the total complexity is
$O(n^{2}T)$ for consensus, and $O(nTL)$ for transaction submission.

###  7.2 Quick Ordering Fairness

Quick Ordering Fairness protocol consists of a BCCH (Byzantine FIFO consistent
broadcast channel) and a VBC (validated byzantine consensus). To send one
transaction, BCCH requires $nL+n^{2}\lambda$ communication complexity, as
provided by the Quick Ordering Fairness paper[5] itself. The VBC part is
modular, the most efficient asynchronous consensus requires $O(n^{2})$.
Although it can also be used with partial synchronous protocol, its complexity
is dominated by the BCCH.

###  7.3 Pompē

The Pompē protocol also requires all nodes to receive a transaction. There is
$O(n^{2})$ term, because there is a Sequence message to all nodes, and the
message contains collected timestamps from $O(n)$ nodes. It is required to let
every node to make agreement on the median timestamp. For Pompē, it uses a
standard leader based Hotstuff protocol, which does not offer censorship
resistance, and its the complexity is simply $O(n\lambda)$. Overall the
complexity for $T$ transactions is $(n^{2}TL+n\lambda)$.

###  7.4 Travelers

In travelers, a transaction passes the the submission protocol if it can
traverse a path. In Section 4.3, we show if the hub size is $O(\log{n})$, and
the length of path is constant. A client can send the transaction to constant
number of path. The overall complexity per transaction is
$O(\log{n}(\lambda)$.

In Table 1, we list two versions of Travelers. In Travelers-Speed, the
protocol uses recursive routing, so that the same transaction is sent every
node in the hub, therefore it is $O(\log(n)(\lambda+L))$. Recursive routing is
useful for reducing the time for the traversal time. See Appendix 8.2 for more
information. In evaluation the complexity for consensus, we can either use
VABA[1] or Dumbo-MVBA[17], they require $O(n^{2})$ communication for reaching
consensus on a stream of bit. In BigDipper, it contains a protocol with
consensus complexity of $O(n^{2})$.

In the other version, Travelers-Light optimizes for low communication
complexity. It uses iterative routing, so only the hash of transaction needs
to be sent to nodes, which is used for signing. The initiator in the recursive
routing can just collect the signatures, and deliver the transaction along
with the signatures to the consensus protocol. Therefore the communication
complexity per transaction is $O(c\log{n}\lambda+L)$. In BigDipper, we show it
is possible to design a censorship resistance protocol with total
communication complexity of $O(\log(n)n)$. Each node only needs to spend
$O(x/n+\log{n})$ complexity in consensus, where $x$ is total amount of data
required to be reached agreement on after traversing the routing protocol from
all nodes, which equals to $\log(n)TL$.

The overall complexity for $T$ transaction is therefore
$O((c\log{n}\lambda+L)T+\log(n)n)$.

##  8 Routing Protocol

###  8.1 Routing Protocol Properties

The routing protocol satisfy the following properties:

  * •

$O(1)$ Probabilistic Regular path: For any transaction, there is $O(1)$
probability that the protocol can generate a set of timestamps from a path
made of entire regular hubs.

  * •

$\epsilon$ Probabilistic Corrupted path: In each block, there is only
$\epsilon$ probability that an adversary can arbitrarily create certificate
with any metadata for all transactions in the block.

###  8.2 Path Traversal Mechanism

In this section, we delineate the procedure how a transaction starts to be
processed by the system and how a hub delivers its approval to the next hub.
When a client sends a few copies of its transaction to the routing protocol,
with high probability there is at least one honest node following the protocol
to forward the transaction to the next hubs. Let’s call the head of a path the
initiator. The initiator is always a single node. If the initiator is trusted
by the client, it can simplify protocols like encryption in Section 4.5.

Since a threshold of signatures are required for an approval from a hub, we
need an efficient way to aggregate those signatures, because all signatures
need to be carried to the end, which can be verified to show the transaction
has traversed the entire path. We choose to use BLS signature for its property
to combine signature. Once the first nodes in the first hub receives the
transaction, honest nodes in the hub need to combine the signature and deliver
them to nodes in the next hub.

####  8.2.1 Iterative vs. Recursive routing

Suppose hub $A$ is a regular hub that has sufficient honest nodes to approve
the transaction. There are multiple solutions to solve the problem. We can
categorize them as either iterative or recursive solution. When using
iterative queries, like DNS, the initiator sends hashes of transactions to
every nodes in the hub, and waits to collect any aggregate signature. The
initiator repeats for all hubs. This approach increases the latency to finish
a query and increases the workload for the initiator. But it has benefits of
being simple. Because the initiator is the single entity, we can easily add
more features like encryption we mentioned later. It also offers a benefits of
communication efficient, because to create a signature, the node does not need
the entire transaction, but just its hash digest.

On the other hand, in a recursive routing, the initiator only participates in
the beginning. Once sufficient honest nodes in the first hub receives the
transactions, the hub works with the next hub directly to deliver the
signature. The solution requires all honest nodes in the hub to broadcast its
signatures to all nodes in the next hubs, once sufficient honest nodes in the
next hub collect sufficient signatures, they combine the signature from
previous hub locally and repeat the same procedures until the end of a path.
This approach is faster in latency but requires $q^{2}$ communication
complexity per hub. All signatures along the hub needs to be carried to the
last hub, so that the consensus is able to verify that the transaction has
traversed sufficient hubs.

###  8.3 Assignment functions

So far, we simply assume there is a hub assignment function from nodes to hub,
and a path assignment function from hubs to path. In this section, we provide
a general description on those functions. Let $\mathcal{D}$ denotes the set of
all nodes, $\mathcal{H}$ denotes be the power set (set of all possible subset)
of $\mathcal{D}$. Let’s denote the hub assignment functions as
$f:\mathcal{D}\rightarrow{\mathcal{H}}$. Let $k$ be the path length for all
paths, then the path assignment function is
$g:\mathcal{H}\rightarrow\mathcal{H}^{k}$.

Multiple ways are possible to create those assignment function. One method
requires the use of a random source that produces a random number in every
block, let’s denote the randomness as $r$. For block number $b$, node $i$ can
computes $q$ different members in the $j$-th hub by taking
$Hash(i,j,k,b,r)\;mod\;n$, where $n$ is number of nodes, and $0<k<q$ (if one
node is selected twice, then replace $k$ with $2k,3k..$ until a distinct node
is found). Then repeat the procedure for $0<j<k$, to obtain all nodes on its
path. Because the randomness is globally visible by every nodes, all nodes
would be able to obtain all paths by computing locally. Since eac Randao in
Ethereum currently offer such randomness.

Another method does not require a global visible randomness, it can be
achieved with verifiable random function (VRF)). A VRF is cryptographic tool
that takes inputs of a seed and secret key of a key pair, and outputs a random
number and a proof that the number is generated correctly. Every node then
uses its private key as the source of randomness and generate all the nodes on
its path.

Because the node assignment function can be very generic, we can add some
structure to the function for enabling some features. For example, if we know
some group of nodes already have the threshold signature setup, and the group
of nodes has sufficiently high security assumption. We can group those nodes
as a super node, so that when creating a new hub, if the node assignment
function pick the super node, it would not select other nodes that is outside
the group to be part of the new hub. In Obol[20], it is possible to have a
threshold setup with 7 honest out of 10 nodes.

We can also change the path assignment functions to improve encryption scheme
from Section 4.5. For example, the assignment function always include a hub
from the decryption hub set in the end of every path. The assignment function
can also change the size of hubs on a path, as long as the final probabilities
for both corrupted path and regular path satisfy the protocol requirement.
Some smaller hubs are therefore eligible to be a part of decryption hub set.

##  9 Travelers Consensus

###  9.1 Property Proof

An adversary can arbitrarily add new transaction into any location in the
ledger if it can find a corrupted paths. Otherwise it will only be able to
advance or delay the timestamps. By the properties of the routing protocol,
there is the error probability of $\epsilon=1/n^{c}$ for some $c\geq 1$ for
that to happen. In the rest of case, no such event can happen.

Suppose there is $1-\kappa$ probability for a transaction $tx_{a}$ to get
included in the ledger, then by the routing protocol there is $O(1)$
probability that this transaction has a regular path. Similarly for the other
transaction $tx_{b}$. Suppose every path has a length of $k$ hubs and network
latency is bounded by $\Delta$. In reference to the true timestamp produced by
the regular path, due to the network uncertainty, those two transactions are
separable as long as the true timestamps between the two differ by $2k\Delta$.

Suppose we choose the iterative routing mechanism to move from hubs to hubs
which is the longer compared to the recursive routing, the total time spent on
the traversal is doubled as $4k\Delta$, because of the round trip.

Suppose the mismatch among nodes’ clock is bounded by $\delta$, then the
maximal mismatch between two true timestamps are $2\delta$. Hence if
transaction $tx_{a}$ is committed and separated by duration $4k\Delta+2\delta$
from the transaction $tx_{b}$, then $tx_{a}$ is ordered before $tx_{b}$.