# Protocol for Asynchronous, Reliable, Secure and Efficient Consensus (PARSEC)
Version 2.0

Pierre Chevalier  Bartłomiej Kamiński  Fraser Hutchison  Qi Ma  Spandan Sharma
Andreas Fackler  William J Buchanan  MaidSafe Ltd.  POA Networks Ltd.
Edinburgh Napier University

###### Abstract

In this paper we present an open source, fully asynchronous, leaderless
algorithm for reaching consensus in the presence of Byzantine faults in an
asynchronous network. We prove the algorithm’s correctness provided that less
than a third of participating nodes are faulty. We also present a way of
applying the algorithm to a network with dynamic membership, i.e. a network in
which nodes can join and leave at will. The core contribution of this paper is
an optimal model in the definition of an asynchronous BFT protocol, and which
is resilient to 1/3 byzantine nodes. This model matches an agreement with
probability one (unlike some probabilistic methods), and where a common coin
is used as a source of randomization so that it respects the FLP impossibility
result.

###### keywords:

asynchronous, byzantine, consensus, distributed

††journal: Journal of Parallel and Distributed Computing

[figure]style=boxed

##  1 Introduction

This paper presents a new Byzantine fault tolerant (BFT) consensus algorithm
that can work under asynchronous conditions. Like Hashgraph [5] and Aleph
[12], it has no leaders, no round robin, no proof-of-work and reaches eventual
consensus with probability one. It is also fully open, and a work-in-progress
implementation written in Rust is available [13]. Like HoneyBadger BFT [14],
this algorithm is built by composing a number of good ideas present in the
literature. A gossip protocol is used to allow efficient communication between
nodes [11], as in Hashgraph [5], Aleph [12] and Avalanche [17].

The general problem of reaching Byzantine agreement on any value is reduced to
the simpler problem of reaching binary Byzantine agreement on the nodes
participating in each decision. This allows us to reuse the elegant binary
Byzantine agreement protocol described in [15] after adapting it to the gossip
protocol.

Finally, even though a trusted dealer (or another trusted external source of
private key shares) is still required to initialise the instances of the
algorithm (like in [14]), changes to the set of processes executing the
instances (which we call _dynamic membership_) can be made without the need
for such external sources. The resulting algorithm is a Protocol for
Asynchronous, Reliable, Secure and Efficient Consensus. PARSEC is a key
building block of the SAFE Network, an ethical decentralized network of data
and applications providing Secure Access For Everyone [16].

The key contribution of this paper is the creation of an asynchronous BFT
protocol, and which is resilient to 1/3 byzantine nodes. This is an optimal
model. It also satisfies an agreement with probability one (unlike some
probabilistic methods), and with a common coin for source of randomization
that it respects the FLP impossibility result [8][10]. The algorithm uses
gossip for efficient and resilient communication. It is leaderless (with a
caveat at network start-up) and the paper outlines how it can be adapted it to
a dynamic membership context, while remaining leaderless after start-up. In
comparable work, HBBFT (Honey Badger of BFT) has a less efficient
communication mechanism with a secure broadcast [14], and HashGraph is not
rigorous in a liveness proof [3] and where the published work only discusses
the possibility of using a common coin in passing [5]. AlephZero [12] is more
recent than our initial work [13] and is an improvement on HashGraph, and
which also includes the use of a common coin. Avalanche [17] differs from our
work in that is uses a synchronous context. None of these methods, though,
includes dynamic membership, and this is a key differentiator in this paper.

##  2 Related work

A gossip protocol has been likened to office workers spreading a rumour, and
where Alice starts a new rumour, and then passes it to Bob, who then passes it
to Dave. Alice then tells it to Frank, and who might have already heard it
from Dave. In this way the rumour propagates quickly through a network,
depending on the frequency that those spreading the rumours will pass them on.
The advantages of gossip protocols was outlined by [6] and who defined that
they could be used with autonomic self-management, repair of inconsistencies,
reliable multicast and distributed search. In actual operation, a gossip
protocol involves a group of agents who hold private information, and who can
communicate with each other. The core objective is for all of the agents to
learn the private information [4], and where distributed epistemic methods
lead to simplified system models. A core weakness of the gossip protocols is
that the dissemination of the rumour might not be radiated across a whole
network of connections. Recent applications of gossip protocols has included
the verifying the consistency of certificate logs [9].

Honey Badger is Byzantine Fault Tolerant [14] which is asynchronous in its
scope. It does not involve a leader node beyond the trusted setup phase and
can cope with corrupted nodes. It does not actually make any commitments
around the timing of the delivery of a message, and where even if Eve control
the scheduling of messages, there will be no impact of the overall consensus.
It can reach a consensus within an infrastructure of $f$ failed nodes, and
where the total number of node ($N$) is greater than $3\times f$.

Hashgraph builds on the Directed Acyclic Graphs (DAG) approach [5] with gossip
communications; _gossip-about-gossip_ methods; and Byzantine voting
algorithms. The gossip-about-gossip method allows for the history of all the
communications within an infrastructure to be reconstructed. Avalanche [17]
focuses on a scaleable electronic payment system. It uses synchronous
communications with a leaderless BFT. In the face of adversaries, it uses a
probabilistic safety guarantee.

##  3 The algorithm description

###  3.1 The network model

We assume the network to be a set $\mathcal{N}$ of $N$ instances of the
algorithm communicating via asynchronous connections, which means that
messages sent over these connections are all delivered eventually, but we make
no assumptions regarding the delays between sending the message and its
reception. In such a setup, it is impossible to distinguish between an
instance failing by completely stopping and a large delay in message delivery.

We allow a possibility of up to $f$ Byzantine (arbitrary) failures, where
$3f<N$. We will call the instances that have not failed _correct_ or _honest_
, and the failing instances _faulty_ or _malicious_ \- as the Byzantine
failure model allows for malicious behaviour and collaboration. We will refer
to any set of instances containing more than $\frac{2}{3}N$ of them as a
_supermajority_.

###  3.2 Data structures

A node executing the algorithm keeps two data structures: a _gossip graph_ and
an ordered set of _blocks_. The vertices of the gossip graph, called _gossip
events_ , contain the following fields:

  * 1.

Payload - data the node wants to pass to other nodes

  * 2.

Self-parent (optional) - a cryptographic hash of another gossip event created
by the same node

  * 3.

Other-parent (optional) - a hash of another gossip event created by some other
node

  * 4.

Cause - cause of creation for this event; can be _sync_ , _observation_ or
_coin share_

  * 5.

Creator ID - the public key of the event’s creator

  * 6.

Signature - a cryptographic signature of the above fields

The self-parent and other-parent are always present, except for the first
events created by respective nodes, as there are no parent events to be
referred to in such cases. Other-parent is also absent in events created
because of an observation or a coin share - because there is no gossip partner
in such a case.

The blocks in the ordered set are network events signed by a subset of the
nodes in the network. This set is the output of the algorithm, and represents
an order of network events that all nodes agree upon. We call the blocks that
are elements of the ordered set _stable blocks_. Let us also define a few
useful terms regarding the gossip graph for future use.

######  Definition 3.1.

We say that event $A$ is an _ancestor_ of event $B$ iff: $A=B$, or $A$ is an
ancestor of $B$’s self-parent, or $A$ is an ancestor of $B$’s other-parent.

######  Definition 3.2.

We say that event $A$ is a _self-ancestor_ of event $B$ iff: $A=B$, or $A$ is
a self-ancestor of $B$’s self-parent.

######  Definition 3.3.

We say that event $A$ is a _descendant_ of event $B$ iff $B$ is an ancestor of
$A$.

######  Definition 3.4.

We say that event $A$ is a _self-descendant_ of event $B$ iff $B$ is a self-
ancestor of $A$.

Following Hashgraph[5], we also define two additional useful notions:

######  Definition 3.5.

An event $A$ is said to _see_ an event $B$ iff $B$ is an ancestor of $A$, and
there doesn’t exist any pair of events by $B$’s creator $B_{1}$, $B_{2}$, such
that $B_{1}$ and $B_{2}$ are ancestors of $A$, but $B_{1}$ is neither an
ancestor nor a descendant of $B_{2}$ (see fig. 2). We call a situation in
which such a pair exists a _fork_.

######  Definition 3.6.

An event $A$ is said to _strongly see_ an event $B$ iff $A$ sees a set of
events created by a supermajority of nodes in the system that all see $B$ (see
fig. 2).

[] []

Figure 1: d_4 sees b_0: b_0 is its ancestor and there are no forks Figure 2:
a_1 strongly sees b_0: it sees itself, b_1 and d_1, which have been created by
a supermajority of nodes and all see b_0

###  3.3 General overview of the algorithm

The nodes execute two main steps in an infinite loop:

  * 1.

Synchronise the gossip graph with another random node

  * 2.

Determine whether any new blocks should be appended to the ordered set

####  3.3.1 Synchronisation

This step is responsible for building the gossip graph and spreading
information around the network. Nodes continually make random calls, called
_sync calls_ , to other nodes and exchange information about the graph, so
that all correct nodes end up with the same data in their graphs. The hashes
and signatures in gossip events make sure that malicious nodes won’t be able
to tamper with any part of the graph.

Whenever a node receives a sync call, it creates a new gossip event. The self-
parent of this event is the hash of the last gossip event created by the
recipient, and the other-parent is the hash of the last event created by the
sender (which the recipient learns about from the call). The new event also
stores the reason for which it was created (cause: _sync_).

If the recipient of a sync call believes it knows a network event that should
be appended as the next one in the chain, it records its vote as the payload
of the newly created event. The other nodes will learn of this vote during
subsequent sync calls made by its creator.

######  Lemma 3.1.

If A and B are correct nodes, then every event created by A will eventually
have a descendant created by B.

###### Proof.

This trivially follows from the network assumption that every message is
eventually delivered, and from the fact that nodes continue to make sync
calls, which result in the callee creating a descendant of the caller’s last
event. ∎

####  3.3.2 Determining order

During this step, a node analyses the graph, counts the votes and decides
which block should become the next one. This step is a complex one and so it
is described in detail in a separate subsection below.

###  3.4 Calculating the order

To be able to order blocks, we need first to have some blocks that can be
ordered.

Every event has a set of _interesting payloads_ associated with it, which are
some of the network events its ancestors contain votes for. The exact way the
set of interesting payloads is calculated is left to the user; however, it has
to satisfy some constraints:

  * 1.

If event $e$ has an interesting payload $p$, there exists an ancestor of $e$
containing a vote for $p$.

  * 2.

If $e$ has an interesting payload $p$, no self-descendants of $e$ have an
interesting payload $p$.

  * 3.

If event $a$ has an interesting payload $p$, $a$ is an ancestor of event $e$
and $e$ has no self-ancestor having an interesting payload $p$, then $e$ has
an interesting payload $p$.

  * 4.

If $e$ has an interesting payload $p$, then no stable block contains $p$.

For example, $p$ might become an interesting payload of $e$ if $e$ has a
single ancestor that contains a vote for $p$. Another option is that $p$ only
becomes an interesting payload if there is a supermajority of ancestors of $e$
containing votes for $p$. An event that has a non-empty set of interesting
payloads is called an _interesting event_.

From the first constraint on interesting payloads it follows that an
interesting event always has a self-parent. Only the initial events have no
self-parents, but they are their only ancestors, and they never contain votes,
so they can’t be interesting.

The first gossip event created by any given node which strongly sees
interesting events created by a supermajority of nodes is said to be an
_observer_. The interesting events don’t need to have the same interesting
payloads - in fact, it is the case when they have different payloads that is
the most interesting.

Since observers are descendants of interesting events, and interesting events
always have self-parents, it follows that observers always have self-parents
as well. An observer implicitly carries a list of $N$ _meta-votes_. Every
meta-vote is just a binary value denoting whether a corresponding node’s
interesting event is to be taken into account when determining the order. An
observer casts a meta-vote of $true$ on a node if it can strongly see an
interesting event by that node. Each node casts a meta-vote on every node,
hence each node casts $N$ meta-votes, and since an observer strongly sees a
supermajority of interesting events, by definition, more than $\frac{2}{3}N$
of them are $true$.

Meta-votes reduce the problem of Byzantine agreement about the order to that
of binary Byzantine agreement, which has been solved previously[15]. The
algorithm described in [15], like many ABFT algorithms, requires a device
called a common coin. PARSEC is no different in this regard. In PARSEC, we
utilise a common coin based on a threshold cryptography scheme using Boneh-
Lynn-Shacham signatures [7].

####  3.4.1 Binary agreement

For the sake of simplicity, we will define the algorithm in terms of deciding
a single _meta-election_ \- that is, deciding whether or not to take a single
node’s opinion into account when trying to choose a single new block. We can
view a meta-election for node $X$ with latest agreed block $B$ as a function
on a subset $H_{X,B}$ of the gossip graph $G$, which is the set of all events
that are descendants of any observer of this meta-election:

$\mathsf{meta\\_election}_{X,B}:H_{X,B}\to\\{0,1,\bot\\}$

The $\bot$ value means that the result has not been decided yet at this point
in the graph.

Any gossip event which is an element of $H_{X,B}$ and is not an observer
trivially has a self-parent in $H_{X,B}$.

From this point on, until section 3.4.3, whenever we mention a meta-election,
we mean a single meta-election regarding a single node, with a specific block
$B$ being the last stable one.

In order to calculate the meta-election value for events in $H_{X,B}$, we will
need to calculate a few helper values as well:

  * 1.

$\mathsf{stage}$ \- a counter denoting the calculation stage

  * 2.

$\mathsf{estimates}$ \- a set of one or two values estimating the final result

  * 3.

$\mathsf{bin\\_values}$ \- a helper set of binary values

  * 4.

$\mathsf{aux}$ \- a helper binary value

$\mathsf{stage}$ is an integer value which represents the stage of the
protocol we are considering when looking at a specific gossip event. A number
is associated with each gossip event, such that the $\mathsf{stage}$ of the
observers is always 0. The $\mathsf{stage}$ of any other gossip event is
either the $\mathsf{stage}$ of its self-parent, or the stage of its self-
parent plus one under specific conditions. The exact conditions under which
the stage is incremented will be described later in more details. Other
variables such as $\mathsf{estimates}$, $\mathsf{bin\\_values}$ and
$\mathsf{aux}$ all depend on the stage.

$\mathsf{estimates}$ (abbreviated $\mathsf{est}$) is a set of binary values
that represent the perceived opinion(s) of the creator of any gossip event on
the outcome of a meta-election. The initial $\mathsf{estimates}$ of an
observer is the set containing just its own meta-vote, and it is the set of
the self-parent’s $\mathsf{estimates}$ for other events, except the events
which increase the stage - it is then calculated from the results of the
previous stage.

If the initial estimates for an event contain a single value $v$, and that
event sees more than $\frac{N}{3}$ events with $\neg v$ in their
$\mathsf{estimates}$ (which means that at least one honest node estimated
$\neg v$), this opposite value gets added to its $\mathsf{estimates}$ (so it
will contain both true and false).

Note: the convention in function definitions below is that the value of the
function is the first value for which the corresponding condition is
satisfied. We also use the common convention of $0$ denoting _false_ , and $1$
denoting _true_.

$\mathsf{init\\_est}:H_{X,B}\to 2^{\\{0,1\\}}$
$\mathsf{init\\_est}(e)=\left\\{\begin{array}[]{ll}\\{v\\}&\textrm{if $e$ is
an observer}\\\ &\textrm{with meta-vote $v$}\\\
\mathsf{next\\_est}(\mathsf{self\\_par}(e))&\textrm{if
$\mathsf{stage}(e)>\mathsf{stage}(\mathsf{self\\_par}(e))$}\\\
\mathsf{est}(\mathsf{self\\_par}(e))&\textrm{otherwise}\end{array}\right.$

$\mathsf{est}:H_{X,B}\to 2^{\\{0,1\\}}$
$\mathsf{est}(e)=\left\\{\begin{array}[]{ll}\\{v\\}&\textrm{if there exists an
ancestor $d$ of $e$}\\\ &\textrm{such that
$v=\mathsf{meta\\_election}(d)\neq\bot$}\\\ \\{0,1\\}&\textrm{if
$\mathsf{init\\_est}(e)=\\{v\\}$}\\\ &\textrm{and $e$ sees $\geq\frac{N}{3}$
events $x$}\\\ &\textrm{by different nodes such that}\\\
&\textrm{$\mathsf{stage}(x)=\mathsf{stage}(e)$ and $\neg
v\in\mathsf{est}(x)$}\\\
\mathsf{init\\_est}(e)&\textrm{otherwise}\end{array}\right.$

$\mathsf{self\\_par}(e)$ denotes $e$’s self-parent, and $\mathsf{next\\_est}$
and $\mathsf{stage}$ will be defined later, once we have defined more values
related to the events.

Once an event can see a supermajority of events by different nodes which agree
in their estimates, this agreed estimate becomes an element of this event’s
$\mathsf{bin\\_values}$ (abbreviated $\mathsf{bv}$). This set serves to
validate values proposed by other nodes - if they propose something we don’t
have in $\mathsf{bin\\_values}$, we will reject it, as we have no way to
ensure its validity.

$\mathsf{bv}:H_{X,B}\to 2^{\\{0,1\\}}$
$\mathsf{bv}(e)=\\{v:\begin{array}[t]{l}\textrm{there exist $>\frac{2}{3}N$
events $x$}\\\ \textrm{by different nodes such that}\\\ \textrm{$e$ sees $x$
and $\mathsf{stage}(e)=\mathsf{stage}(x)$ and $v\in\mathsf{est}(x)$}\\\
\textrm{or there exists an ancestor $d$ of $e$}\\\ \textrm{such that
$\mathsf{meta\\_election}(d)=v\neq\bot$}\\}\end{array}$

Figure 3: An example gossip graph, along with estimates and bin_values
associated with each gossip event. It illustrates how different nodes process
the information they receive in order to populate their bin_values.

If an event’s parent has an empty $\mathsf{aux}$ value, and the event itself
has non-empty $\mathsf{bin\\_values}$, it can propose a value to be agreed.
This proposing is realised by having a non-empty $\mathsf{aux}$ value. If
$\mathsf{bin\\_values}$ contains just one value, this value becomes the
$\mathsf{aux}$ value; otherwise, we can pick an arbitrary value, so we will
pick true. If the parent’s value isn’t empty, it becomes our value as well.

$\mathsf{aux}:H_{X,B}\to\\{0,1,\bot\\}$
$\mathsf{aux}(e)=\left\\{\begin{array}[]{ll}v&\textrm{if there exists an
ancestor $d$ of $e$}\\\ &\textrm{such that
$v=\mathsf{meta\\_election}(d)\neq\bot$}\\\ \bot&\textrm{if
$\mathsf{bv}(e)=\varnothing$}\\\ w&\textrm{if $\mathsf{bv}(e)=\\{w\\}$}\\\
&\textrm{and $\mathsf{aux}(\mathsf{self\\_par}(e))=\bot$ }\\\ 1&\textrm{if
$\mathsf{bv}(e)=\\{0,1\\}$}\\\ &\textrm{and
$\mathsf{aux}(\mathsf{self\\_par}(e))=\bot$ }\\\
\mathsf{aux}(\mathsf{self\\_par}(e))&\textrm{if
$\mathsf{aux}(\mathsf{self\\_par}(e))\neq\bot$}\end{array}\right.$

Whenever an event sees a supermajority of events with valid $\mathsf{aux}$
values, we perform the common coin protocol (described in section 3.4.2),
which will lead either to deciding the final agreed value, or updating the
estimates and moving to the next stage.

First, let us define some helper functions:

$\mathsf{supermajority\\_valid\\_aux}:H_{X,B}\to\\{0,1\\}$
$\mathsf{supermajority\\_valid\\_aux}(e)=\begin{array}[t]{l}\textrm{$e$ sees a
supermajority}\\\ \textrm{of events $x$ by different nodes}\\\ \textrm{such
that $\mathsf{stage}(x)=\mathsf{stage}(e)$}\\\ \textrm{and
$\mathsf{aux}(x)\in\mathsf{bv}(e)$}\end{array}$

$\mathsf{count\\_aux}:H_{X,B}\times\\{0,1\\}\to\mathbb{N}$
$\mathsf{count\\_aux}(e,v)=\begin{array}[t]{l}\textrm{number of events $x$ by
different nodes such that}\\\ \textrm{$e$ sees $x$ and
$\mathsf{stage}(x)=\mathsf{stage}(e)$}\\\ \textrm{and
$\mathsf{aux}(x)\in\mathsf{bv}(e)$ and $\mathsf{aux}(x)=v$}\end{array}$

Now we can define how to determine a decided value:

$\mathsf{meta\\_election}:H_{X,B}\to\\{0,1,\bot\\}$
$\mathsf{meta\\_election}(e)=\left\\{\begin{array}[]{ll}v&\textrm{if there
exists an ancestor $d$ of $e$}\\\ &\textrm{such that
$v=\mathsf{meta\\_election}(d)\neq\bot$}\\\ 1&\textrm{if
$\mathsf{coin\\_flip}(e)=1$}\\\ &\textrm{and
$\mathsf{count\\_aux}(e,1)>\frac{2}{3}N$}\\\ 0&\textrm{if
$\mathsf{coin\\_flip}(e)=0$}\\\ &\textrm{and
$\mathsf{count\\_aux}(e,0)>\frac{2}{3}N$}\\\
\bot&\textrm{otherwise}\end{array}\right.$

$\mathsf{coin\\_flip}$ is the value of the common coin flip and will be
defined later, in section 3.4.2.

If an event sees a supermajority of valid $\mathsf{aux}$ values, but isn’t
able to decide, the next event will mark the beginning of the next stage of
the algorithm. This lets us finally define $\mathsf{stage}$:

$\mathsf{stage}:H_{X,B}\to\mathbb{N}$
$\mathsf{stage}(e)=\left\\{\begin{array}[]{ll}0&\textrm{if $e$ is an
observer}\\\
\mathsf{next\\_stage}(\mathsf{self\\_par}(e))&\textrm{otherwise}\end{array}\right.$
$\mathsf{next\\_stage}:H_{X,B}\to\mathbb{N}$
$\mathsf{next\\_stage}(e)=\mathsf{stage}(e)+\left\\{\begin{array}[]{ll}1&\textrm{if
$\mathsf{supermajority\\_valid\\_aux}(e)$}\\\ &\textrm{and
$\mathsf{next\\_est}(e)\neq\bot$}\\\ 0&\textrm{otherwise}\end{array}\right.$

If we don’t decide in a stage, we need new estimates for the next one. This is
being taken care of by the common coin protocol briefly mentioned before, and
described in more detail in section 3.4.2.

In every stage, when the coin value is known, we can either decide or
calculate the initial estimate for the next stage. The general rule is this:
we decide $v$ if we see a supermajority of $\mathsf{aux}$ values of $v$ and
the coin value is $v$. If we see a supermajority of $\mathsf{aux}$ values of
$\neg v$ and the coin value is $v$, we estimate $\neg v$ in the next stage. If
we don’t see any supermajority, we estimate the coin value in the next stage.

To calculate new estimates, we will define a $\mathsf{next\\_est}$ function
(which appeared already in the definition of $\mathsf{est}$):

$\mathsf{next\\_est}:H_{X,B}\to 2^{\\{0,1\\}}\cup\\{\bot\\}$
$\mathsf{next\\_est}(e)=\left\\{\begin{array}[]{ll}\\{v\\}&\textrm{if
$\mathsf{count\\_aux}(e,v)>\frac{2}{3}N$}\\\ &\textrm{and
$\mathsf{coin\\_flip}(e)\neq\bot$}\\\ \\{\mathsf{coin\\_flip}(e)\\}&\textrm{if
$\mathsf{count\\_aux}(e,0)\leq\frac{2}{3}N$}\\\ &\textrm{and
$\mathsf{count\\_aux}(e,1)\leq\frac{2}{3}N$}\\\ &\textrm{and
$\mathsf{coin\\_flip}(e)\neq\bot$}\\\
\bot&\textrm{otherwise}\end{array}\right.$

We can now start defining the $\mathsf{coin\\_flip}$ function.

####  3.4.2 Common coin

The common coin protocol is used to calculate the value of the coin flip in a
stage. Every stage can either have a predefined coin value, or demand a
genuine flip. The exact pattern of which stage has which option associated
with it can be defined by the user, as long as there will be infinitely many
genuine flips with the stage number tending towards infinity (otherwise the
termination property of the algorithm - explained later in the paper - will
not hold).

The simplest pattern would be to require a genuine flip at every stage. But
other patterns [2], e.g. 1, 0, flip, 1, 0, flip[18], etc. can be used to avoid
some of the expensive flips, and optimise more for the optimistic case. Using
fixed values at some stages may speed up reaching consensus in some cases, as
it doesn’t require the exchange of coin shares and returns the coin value
right away.

For the genuine flip, the nodes do need to exchange coin shares. In order to
define what they are, let us first define the _round hash_ as follows. This
hash will help us uniquely identify one particular stage of a specific meta-
election for a given node’s meta vote:

$\mathsf{round\\_hash}:H_{X,B}\to[0,2^{256})$
$\mathsf{round\\_hash}(e)=\mathsf{hash}(\mathsf{hash}(X),\mathsf{hash}(payload(B)),\mathsf{hash}(\mathsf{stage}(e)))$

All nodes are assumed to possess private key shares - parts of a Boneh-Lynn-
Shacham private key in a threshold scheme, in which at least $\frac{N}{3}$
signature shares (signatures generated with private key shares) are needed to
reconstruct a full signature, and any $\frac{N}{3}$ signature shares will
result in the same, bit-by-bit identical signature. All nodes are also in
possession of public keys corresponding to all other nodes, so that they can
verify each signature share independently, as well as the full signature.

When a node creates an event $e$ with $\mathsf{stage}(e)$ corresponding to a
genuine flip, that sees a supermajority of aux values in its stage, it signs
$\mathsf{round\\_hash}(e)$ with its private key share and publishes the
resulting signature share in a gossip event with cause _coin share_. Once an
event sees enough events with valid coin shares, it can collect them and
calculate the full signature, of which the lowest order bit will be taken as
the coin flip value.

Let us define $\mathsf{count\\_shares}$ analogously to $\mathsf{count\\_aux}$:

$\mathsf{count\\_shares}:H_{X,B}\times\\{0,1\\}\to\mathbb{N}$
$\mathsf{count\\_shares}(e)=\begin{array}[t]{l}\textrm{number of events $x$ by
different nodes such that}\\\ \textrm{$e$ sees $x$ and
$\mathsf{stage}(x)=\mathsf{stage}(e)$}\\\ \textrm{and $x$ contains a valid
coin share for $\mathsf{stage}(e)$}\\\ \end{array}$

The genuine flip can then be defined as:

$\mathsf{genuine\\_flip}:H_{X,B}\to\\{0,1,\bot\\}$
$\mathsf{genuine\\_flip}(e)=\left\\{\begin{array}[]{ll}\textrm{lowest order
bit}&\\\ \textrm{of the full signature}&\textrm{if
$\mathsf{count\\_shares}(e)\geq\frac{N}{3}$}\\\
\bot&\textrm{otherwise}\end{array}\right.$

Let us denote the set of stages with coin value fixed to 1 as $C_{1}$, the set
of stages with coin value fixed to 0 as $C_{0}$, and the set of genuine flip
stages as $C_{f}$. The sets satisfy $C_{1}\cup C_{0}\cup C_{f}=\mathbb{N}$,
$C_{1}\cap C_{0}=C_{1}\cap C_{f}=C_{0}\cap C_{f}=\varnothing$, and
$|C_{f}|=|\mathbb{N}|$. Then, the full coin flip will be defined as follows:

$\mathsf{coin\\_flip}:H_{X,B}\to\\{0,1,\bot\\}$
$\mathsf{coin\\_flip}(e)=\left\\{\begin{array}[]{ll}1&\textrm{if
$\mathsf{stage}(e)\in C_{1}$}\\\ 0&\textrm{if $\mathsf{stage}(e)\in C_{0}$}\\\
\mathsf{genuine\\_flip}(e)&\textrm{if $\mathsf{stage}(e)\in
C_{f}$}\end{array}\right.$

This is all we need to reach consensus on the meta-votes.

####  3.4.3 Agreement about the next block

Using the above, every node can calculate the results of all meta-elections.
Once the results are known, they can be used to determine the next block in
the ordered set.

Let us remember that the meta-elections started with a set of observers - a
set of events that all strongly see a supermajority of interesting events. The
results of the meta-elections tell us which interesting events are to be taken
into account.

The properties of meta-elections ensure that all nodes will agree on the
considered set of nodes. What we need to do is change that into an agreement
on what the next block should be. This is pretty trivial, although we must
consider two issues: every node could create multiple interesting events, and
every interesting event could contain multiple interesting payloads.

To counter the first issue, we can just take the earliest interesting event
created by a given node. The events created by a single node form a linear
sequence, so the earliest one is well-defined. This narrows the considered set
down to a single interesting event per node.

The next step is to choose a valid block among potentially multiple ones seen
by the chosen interesting event. To do that, we can take the lexicographically
first one, or use really any method that will always choose the same element
of a set.

Once we have one vote on a block per node, we just count them and the next
agreed block will be the one with the most votes. Any ties can be broken again
by lexicographic ordering, or some other method.

It is also possible to repeat the steps above for other interesting payloads
of the interesting events that have been selected by the meta-election as an
optimisation, so that a single meta-election results in appending multiple
stable blocks.

This completes the description of the algorithm. The next section will prove
that it is correct, that is, that it provides robust consensus in an
asynchronous setting, and in the presence of Byzantine faults.

##  4 Proof of correctness

Let us begin by stating two important properties of the gossip graph.

######  Definition 4.1.

We call two gossip graphs _consistent_ iff for every gossip event $x$ that is
present in both graphs, both contain the same set of ancestors of $x$ with the
same sets of edges between them.

######  Lemma 4.2.

All nodes in the network have consistent gossip graphs.

######  Lemma 4.3.

If a pair of gossip events $(x,y)$ is a fork, and another gossip event $z$
strongly sees $x$, then no other gossip event in a consistent graph can
strongly see $y$.

We won’t prove the above lemmas - they have been proved in [5] (as Lemma 5.11
and 5.12, respectively). Note that lemma 4.3 only holds if $N>3f$, but we
assume that anyway.

Let us now prove some properties of our approach stemming from it being an
adaptation of [15].

######  Lemma 4.4 (Interesting events).

If a correct node creates an interesting event with payload $p$, then all
correct nodes will eventually create an interesting event with payload $p$.

###### Proof.

Let $e$ be the event created by a correct node that has interesting payload
$p$. By lemma 3.1, eventually every correct node will create a descendant of
$e$. By the properties of interesting payloads, either this descendant or one
of its self-ancestors will then have interesting payload $p$. Thus, for every
correct node, there will be an event that is an interesting event with payload
$p$, which completes the proof. ∎

######  Lemma 4.5 (Aux values).

If all correct nodes created an event in stage $s$, then all correct nodes
will eventually create an event with an $aux$ value in stage $s$.

###### Proof.

Every event in stage $s$ has at least one estimate. There is a supermajority
of correct nodes, so there will exist a value $v$ such that at least $N/3$
correct nodes have $v$ in estimates. Thus, there will exist a value $v$ that
will eventually be estimated by all honest nodes, which means it will get
promoted to bin-values by all honest nodes. Once $\mathsf{bin\\_values}$ is
not empty for an event, this event also has an aux value. Since all honest
nodes will eventually create events with non-empty bin-values, these events
will have aux values, which completes the proof. ∎

######  Lemma 4.6 (Progress).

If a correct node created a gossip event in stage $s$, every other correct
node will eventually create an event in stage $s$ as well.

###### Proof.

Assume $s=0$. The first gossip event in stage 0 is an observer. If a correct
node created an observer, it must have strongly seen a supermajority of
interesting events. A supermajority always contains a correct node, so at
least one correct node created an interesting event. By lemma 4.4, all correct
nodes will eventually have created interesting events.

If all correct nodes created interesting events, it means that eventually all
correct nodes will create an event strongly seeing a supermajority of
interesting events - as there is a supermajority of correct nodes, they
continue gossipping and they never fork. Thus, all correct nodes will
eventually create observers, which completes the proof for $s=0$.

Assume the lemma holds for stage $s$. We will now prove that this implies it
holds for stage $s+1$.

Assume a correct node created an event in stage $s+1$. This means that this
event sees a supermajority of events in stage $s$ with some _aux_ values. This
means that at least one honest node created an event in stage $s$, so by our
assumption, all honest nodes will have eventually created an event in stage
$s$. By lemma 4.5, this means that all honest nodes will eventually have
created an event in stage $s$ with an aux value. All honest nodes will
eventually create events that see all these events with aux values, which
constitutes a supermajority, which is enough to progress to the next stage -
so all honest nodes will create an event in stage $s+1$. By induction, the
proof is complete. ∎

######  Lemma 4.7.

If all correct nodes created events in stage $s$ and stage $s$ is a genuine
flip stage, then the estimates of the nodes’ events in the next stage will be
in agreement with probability $\geq\frac{1}{2}$.

###### Proof.

Let us consider the worst case scenario, in which there are $f$ malicious
nodes among the $N=3f+1$ nodes. Let us also assume that the adversary controls
the timing of the messages, so by controlling which messages are delivered
when, they can control the gossip pattern and effectively, to some extent, the
values associated with the gossip events.

Assume the adversary tries to force a disagreement among the honest nodes. The
only way to do so is to make some honest nodes see no agreeing supermajority
among the aux values, which will make them take the coin value as the next
estimate, and other honest nodes to see a supermajority of aux values opposite
to the coin value. In other cases the honest nodes will automatically have
agreeing estimates in stage $s+1$.

The adversary cannot control the coin value, so they need to learn its value
first. It is only possible if at least one honest node published its coin
share, which means it has already seen a supermajority of aux values. Then,
for the first $2f+1$ aux values seen by the correct node, exactly one of the
following is true:

  * 1.

There are at least $f+1$ _true_ aux values.

  * 2.

There are at least $f+1$ _false_ aux values.

Whichever one is true, no matter what control the adversary has over the
remaining aux values, it cannot make other honest nodes see a supermajority
for the opposite value. Thus, it is out of the adversary’s control to make the
nodes disagree, as they couldn’t have known beforehand which value they need
to have a supermajority of.

If there is no supermajority of agreeing aux values, the honest nodes will
automatically be in agreement. If there is one and all of them see it, they
will also be in agreement. If not all of them see it, there is a $\frac{1}{2}$
probability that the coin value will agree, thus also making all honest nodes
agree.

Thus, the probability of the honest nodes agreeing in stage $s+1$ is at least
$\frac{1}{2}$. ∎

######  Lemma 4.8.

If all correct nodes’ first events in stage $s$ had
$\mathsf{estimates}=\\{v\\}$, either they will decide $v$ in stage $s$, or
their first events in stage $s+1$ will also have $\mathsf{estimates}=\\{v\\}$.

###### Proof.

If all correct nodes only estimate $v$, there is no way for any event to see
even $\frac{N}{3}$ of estimates for $\neg v$ \- so no event by a correct node
will have it in its estimates in stage $s$.

For a value to be an element of $\mathsf{bin\\_values}$, there must be a
supermajority of events estimating that value. Because of the above, the only
value that can have a supermajority is $v$. Thus, every event with nonempty
$\mathsf{bin\\_values}$ will have it equal to $\\{v\\}$. Hence, every event
with an $\mathsf{aux}$ value will have it equal to $v$.

In order to proceed to the next stage, an event has to see a supermajority of
valid $\mathsf{aux}$ values. No event can have a value other than $v$ as
$\mathsf{aux}$ in stage $s$, so there will always be a supermajority for $v$.
Depending on the coin flip value, this can either lead to deciding $v$, or
estimating $v$ in stage $s+1$. Either way, the agreement will still hold. ∎

######  Lemma 4.9.

If all correct nodes’ first events in stage $s$ had
$\mathsf{estimates}=\\{v\\}$, they will all decide $v$ eventually.

###### Proof.

No matter what malicious nodes do, there is less than a third of them, so no
event by a correct node will have $\neg v$ in estimates (by definition of the
$\mathsf{est}$ function). This means that for $\mathsf{bin\\_values}$ of an
event to be non-empty, it must see a supermajority of estimates for $v$, as
there will never be a supermajority for $\neg v$.

The above means that no correct node will add $\neg v$ to
$\mathsf{bin\\_values}$, so all of them will eventually create an event with
$\mathsf{aux}=v$. This means there will be a supermajority of events by
different creators with $\mathsf{aux}=v$, which will make the correct nodes
either decide in stage $s$ (if $\mathsf{coin\\_flip}=v$), or estimate $v$ for
the next stage. This will repeat until $\mathsf{coin\\_flip}=v$ and the nodes
decide $v$. Since there will be infinitely many genuine flips with the number
of stages tending to infinity, and each genuine flip will result in $v$ with
probability $\frac{1}{2}$, this will eventually happen with probability 1. ∎

######  Theorem 4.10 (Binary Byzantine Consensus).

The algorithm for calculating meta-election results presented in this paper
satisfies the general properties of a Byzantine fault tolerant consensus
algorithm:

  * 1.

_Validity_ \- if a correct node decides on a value, it has been proposed by a
correct node.

  * 2.

_Agreement_ \- if a correct node decides on a value, all correct nodes decide
on that value.

  * 3.

_Integrity_ \- once a correct node decides on a value, it never decides on
another value.

  * 4.

_Termination_ \- all correct nodes eventually decide with probability 1.

###### Validity.

We will prove an equivalent statement: that if initially all correct nodes
propose $v$, then all correct nodes will decide $v$. Since $v$ is a binary
value, a node can only decide a value not proposed by a correct node if all
correct nodes propose $v$, and the node decides $\neg v$. Thus, deciding $v$
when all correct nodes propose $v$ is equivalent to always deciding on a value
proposed by a correct node.

If all correct nodes propose $v$, they will all put $v$ in their estimates. By
Lemma 4.9, they will all decide $v$ eventually. ∎

###### Agreement.

Assume there is an event $e$ created by a correct node which was able to
decide a value $v$. It means that $\mathsf{coin\\_flip}(e)=v$ and this event
must have seen a supermajority of events with $\mathsf{aux}=v$. This means
there was no supermajority for $\neg v$. Thus, if a correct node has seen a
supermajority in this stage, it must have been for $v$, so it would decide
$v$. If it hasn’t, it would estimate $v$ for the next stage, which means there
will be agreement at the start of the next stage. Following Lemma 4.8, this
agreement will propagate to the end of the stage and the next stages, until
everyone decides $v$. ∎

###### Integrity.

Once an event $e$ created by a correct node decides on a value $v$, all later
events created by that node will have event $e$ as an ancestor. Following the
definition of $\mathsf{meta\\_election}$, all later events will also decide
$v$. ∎

###### Termination.

By Lemma 4.6, if a correct node creates an event in stage $s$, then every
correct node eventually creates an event in stage $s$. This means there will
be events by $>\frac{2}{3}N$ correct nodes, which will eventually be seen by
every correct node. Every such event will have non-empty estimates. It is not
possible for both 0 and 1 to be estimated by $<\frac{N}{3}$ events by
different correct nodes, so at least one of those values will eventually be an
element of estimates of every correct node’s event.

Eventually, the events with agreeing estimates will all be seen by an event
created by every correct node. Hence, every correct node will eventually
create an event with non-empty $\mathsf{bin\\_values}$, and so an
$\mathsf{aux}$ value.

The events with $\mathsf{aux}$ values will eventually be seen by every correct
node’s event, which means every correct node will eventually either decide or
progress to the next stage.

By Lemma 4.7, after every stage with a genuine coin flip, all nodes’ estimates
agree with probability $>\frac{1}{2}$. This means that the probability of
estimates still not agreeing at stage $s$ is less than:

$(1-\frac{1}{2})^{\mathsf{gf}(s)}=\frac{1}{2^{\mathsf{gf}(s)}}$

where $\mathsf{gf}(s)$ is the number of genuine flips up to stage $s$. Since
we assume an infinite number of genuine flip stages as $s$ tends to infinity,
$\mathsf{gf}(s)$ grows to infinity as $s$ grows, which implies that the
probability of estimates not agreeing tends to 0. This means that the
estimates will eventually agree with probability 1. By Lemma 4.9, the nodes
will decide eventually after that happens. ∎

The above theorem proves that our algorithm will reach agreement about every
single meta-election in a Byzantine fault tolerant way. This is not the end,
though - we also need to prove that meta-elections lead to agreement about the
next block in the ordered set. The proof of that is presented below.

######  Lemma 4.11.

If the result of a meta-election is $v$, there have been at least
$\frac{N}{3}$ meta-votes for $v$.

###### Proof.

Assume there have been less than $\frac{N}{3}$ meta-votes for $v$ and $v$ has
been decided. When nodes that initially meta-voted $v$ create an event that
sees a supermajority of meta-votes, this supermajority must contain at least
$\frac{N}{3}$ votes for $\neg v$ \- so their estimates will contain $\neg v$.
On the other hand, no node that meta-voted $\neg v$ can ever create an event
that will see at least $\frac{N}{3}$ estimates for $v$, so they won’t add $v$
to estimates.

Due to the above, any supermajority among the estimates must be for $\neg v$.
Any event with non-empty $\mathsf{bin\\_values}$ can thus only have $\neg v$
in this set, which means that all valid $\mathsf{aux}$ values will also be
$\neg v$, which will lead to a decision on $\neg v$ eventually.

This is a contradiction. Such a situation is impossible, which proves the
lemma. ∎

######  Lemma 4.12.

The set of nodes for which the result of meta-election is $true$ is always
non-empty.

###### Proof.

Assume all meta-elections resulted in $false$. By Lemma 4.11, at least
$\frac{N}{3}$ nodes meta-voted $false$ for every node, so there have been at
least $\frac{N^{2}}{3}$ meta-votes for $false$.

On the other hand, by definition of an observer, every node voted $true$ for
more than $\frac{2}{3}N$ nodes - so there have been more than
$\frac{2}{3}N^{2}$ meta-votes for $true$, which leaves less than
$\frac{N^{2}}{3}$ meta-votes for $false$ (there are $N^{2}$ meta-votes in
total: $N$ nodes meta-vote in $N$ meta-elections).

This is a contradiction, which proves the lemma. ∎

######  Theorem 4.13 (Byzantine Consensus).

The algorithm for calculating the next block presented in this paper satisfies
the general properties of a Byzantine fault tolerant consensus algorithm:

  * 1.

_Validity_ \- if a correct node decides on a next block, its payload was in at
least one interesting event created by a correct node.

  * 2.

_Agreement_ \- if a correct node decides on a next block, all correct nodes
decide on that block.

  * 3.

_Integrity_ \- once a correct node decides on a next block, it never decides
on another block.

  * 4.

_Termination_ \- all correct nodes eventually decide with probability 1.

###### Validity.

Assume that no correct node created an interesting event with payload $p$, but
$p$ was still decided as the payload of the next block.

This means that only faulty nodes could create interesting events with payload
$p$, so there is less than $N/3$ such interesting events. Furthermore, if a
correct node created a descendant of such an interesting event, then either it
or one of its self-ancestors would have to be an interesting event with
payload $p$ as well. This would contradict our assumption, so no correct node
could have created a descendant of an interesting event with payload $p$.

It follows from this that when correct nodes create observers, no such
observer can meta-vote _true_ for a creator of an interesting event with
payload $p$ (as it would require the observer to be a descendant of such an
event). This means that after the meta-election is complete, no interesting
event with payload $p$ will be taken into consideration, so $p$ will not be
decided as the payload of the next stable block.

QED by contradiction. ∎

###### Agreement.

Assume that a correct node decided the next block $B$. Since a decision has
been reached, this means that there is consensus about the meta-votes, so
every correct node will have chosen the same nodes’ interesting events.

For any observer to meta-vote $true$ on a node, it must have strongly seen an
interesting event by that node. By Lemma 4.3, even if that node created a
fork, if any other observers also voted $true$ on that node, they must have
strongly seen interesting events on the same fork. Thus, we can consider
interesting events by all elected nodes to form linear histories - which will
be seen the same way by all nodes by Lemma 4.2.

In a linear history, the earliest interesting event is well-defined. Also,
because all correct nodes see the same history, they will all choose the same
interesting event as the earliest. If the interesting events has multiple
payloads, all correct nodes will use the same tie-breaker algorithm and choose
the same single one. Thus, all correct nodes will gather the same set of
votes, and because they use the same voting rules, decide the same block as
the next one. ∎

###### Integrity.

By construction of the algorithm, once the next block has been decided, it is
appended to the ordered set and no other block can be decided in its place. ∎

###### Termination.

The consensus algorithm starts when a correct node creates an interesting
event. Once that happens, by lemma 4.4, all correct nodes will eventually
create interesting events, and this in turn implies that all of them will
create observers. Once there is a supermajority of observers, we start the
binary agreement algorithm, which will terminate by Theorem 4.10. After binary
agreement terminates, because the set of voters for the next block is non-
empty (by Lemma 4.12), the next block is already determined - so the agreement
about the next block also terminates. ∎

##  5 Conclusions

A new consensus algorithm has been presented, building upon some previous
achievements in this field ([5], [15]), but combining their features in a
novel way. It works under asynchronous conditions, uses a gossip graph (like
[12], [5] and [17]), and a common coin. It is also leaderless (barring the
very initialisation of the network, when a trusted dealer may be required) and
an open source implementation is provided. We believe this approach will be
useful in numerous applications, one of which is the SAFE Network.

##  Appendix A : Extending the algorithm to a network with dynamic membership

The main algorithm is formulated in terms of a network in which all the
members are known a priori (a static network). This is enough in some
settings, but sometimes it is necessary to allow the set of members to be
modified, so that members of the network can join and leave at will.

In order to accommodate dynamic membership in the network, every node has to
keep a record of who the current members are. We will call this record the
_network members list_. This list is initialised with the so called _genesis
group_ and can only be modified as a result of a block becoming stable.

Changing the membership list requires re-generating the common coin secret key
shares, too. We need to generate them in a way that doesn’t allow any single
node to get to know more than just their share. Fortunately, there are
distributed key generation (DKG) algorithms in existence that solve this
problem. One of the simplest ones is [1], but it requires synchronous
communications.

Fortunately, we can simulate synchronous communications using the instances of
PARSEC held by the old set of members. DKG messages can be input as votes into
the graph, and the consensus algorithm will ensure that all nodes will process
them in the same order. The messages in the order that was agreed upon can
also be passed to the nodes that are joining, thus allowing them to generate
their key shares.

In summary, a membership change would be processed as follows:

  1. 1.

The old set of members votes for a membership change (adding or removing a
node).

  2. 2.

A block with node addition/removal becomes stable.

  3. 3.

Nodes from the old members set start the DKG algorithm and begin voting for
DKG messages.

  4. 4.

Blocks with DKG messages become stable. At some point, enough of them are
stable to complete the DKG algorithm.

  5. 5.

Nodes from the old set calculate their new key shares and update their members
lists.

  6. 6.

If a new node was joining, it will start receiving gossip containing the
gossip events since genesis up to this point. By processing the graph, it can
learn of all the blocks that became stable, including the DKG messages, from
which it will be able to derive its own key share. It will also arrive at the
current members list.

  7. 7.

The membership change is complete.

This method ensures that every meta-election uses a constant list of members
from start to finish - the members list only gets modified once a meta-
election finishes (the one regarding the block that completed the DKG), and
another one is not yet started. Thanks to this approach, the proofs of
correctness apply without modifications.

## References

  * [1] Fackler A.  Distributed Key Generation.  https://github.com/poanetwork/hbbft/issues/47#issuecomment-394422248.
  * [2] Miller A.  Optimistic Randomness for ABA.  https://github.com/amiller/HoneyBadgerBFT/issues/63.
  * [3] Bowen Alpern and Fred B Schneider.  Defining liveness.  21(4):181–185.
  * [4] Krzysztof R Apt, Eryk Kopczynski, and Dominik Wojtczak.  On the computational complexity of gossip protocols.  In IJCAI, pages 765–771.
  * [5] Leemon Baird.  The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance.
  * [6] Ken Birman.  The promise, and limitations, of gossip protocols.  41(5):8–13.
  * [7] Dan Boneh, Ben Lynn, and Hovav Shacham.  Short signatures from the weil pairing.  17(4):297–319.
  * [8] Elizabeth Borowsky and Eli Gafni.  Generalized flp impossibility result for t-resilient asynchronous computations.  In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 91–100. ACM.
  * [9] Laurent Chuat, Pawel Szalachowski, Adrian Perrig, Ben Laurie, and Eran Messeri.  Efficient gossip protocols for verifying the consistency of certificate logs.  In 2015 IEEE Conference on Communications and Network Security (CNS), pages 415–423. IEEE.
  * [10] Michael J Fischer, Nancy A Lynch, and Michael S Paterson.  Impossibility of distributed consensus with one faulty process.
  * [11] Rachid Guerraoui, Kévin Huguenin, Anne-Marie Kermarrec, Maxime Monod, and Swagatika Prusty.  Lifting: lightweight freerider-tracking in gossip.  In Proceedings of the ACM/IFIP/USENIX 11th International Conference on Middleware, pages 313–333. Springer-Verlag.
  * [12] Adam Gągol and Michał Świętek.  Aleph: A leaderless, asynchronous, byzantine fault tolerant consensus protocol.
  * [13] MaidSafe.  PARSEC reference implementation (WIP).  https://github.com/maidsafe/parsec.
  * [14] Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song.  The honey badger of bft protocols.  In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 31–42. ACM.
  * [15] Achour Mostefaoui, Hamouma Moumen, and Michel Raynal.  Signature-free asynchronous byzantine consensus with t< n/3 and o (n 2) messages.  In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pages 2–9. ACM.
  * [16] A Penland, David Shrier, T Hardjono, and I Wladawsky-Berger.  Towards an internet of trusted data: A new framework for identity and data sharing.
  * [17] Team Rocket.  Snowflake to avalanche: A novel metastable consensus protocol family for cryptocurrencies.
  * [18] Micali S.  Byzantine Agreement, Made Trivial.


# Ultrawideband USRP-Based Channel Sounding Utilizing the RFNoC Framework

Michiel Sandra, Christian Nelson, Anders J Johansson  Electrical and
Information Technology
Lund University
Lund, Sweden
<EMAIL_ADDRESS>
###### Abstract

This paper shows how an ultrawideband channel sounder can be built with the
latest National Instruments (NI) Universal Software Radio Peripheral (USRP)
equipment, featuring onboard FPGA processing and utilizing open-source tools.
Compared to other USRP-based channel sounders, our design is versatile, eases
the requirements on the data link between the USRPs and the host, limits the
measurement data size, and increases the signal-to-interference-plus-noise
ratio due to averaging. Furthermore, this paper serves as a proof-of-concept
for other researchers seeking to build a channel sounder based on the USRP
equipment.

###### Index Terms:

channel sounding, ultra wideband, SDR, USRP

##  I Introduction

New parts of the spectrum are available with the new fifth and sixth
generation wireless standards. The systems go higher in frequency and are also
becoming more wide-band, requiring us to deepen our knowledge about wireless
channels. Measurement of wireless channels, also known as channel sounding,
has played a vital role in developing realistic channel models. In the last
decade, channel sounding based on software-defined radios (SDR), such as the
Universal Software Radio Peripheral (USRP) platform from National Instruments
(NI), has gained much popularity due to flexibility, portability, and cost-
efficiency [1, 2, 3, 4, 5, 6, 7]. With the third generation NI USRPs, the
bandwidth has been limited to 160 MHz. The release of the new X410 USRP has
now opened up for bandwidths up to 400 MHz, which can provide a more detailed
insight into the wireless propagation channels. However, such a large
bandwidth imposes challenges in handling the massive stream of I/Q samples.
Whereas most USRP-based channel sounder designs stream all sample data to the
host computer at the receiver side, we have developed a custom signal
processing block on the FPGA onboard the X410 to limit the data stream. The
authors of [8] also developed a USRP-based channel sounder containing custom
signal processing blocks; however, our design is more compact and and can
handle a higher bandwidth. Our custom signal processing block was developed
within the open-source framework RF Network on Chip (RFNoC) by Ettus Research
[9]. This framework is responsible for the streaming and processing of RF data
on the FPGA, and offers the possibility to create custom applications based on
so-called RFNoC blocks. There are already various types of blocks available;
nevertheless, one can create one’s own block tailored to a specific purpose.

Figure 1: RFNoC processing block functionality for one channel snapshot

##  II Implementation

The transmitter and the receiver of the channel sounder each consist of a host
computer and a NI USRP X410, which is a four-channel full-duplex SDR based on
the Xilinx UltraScale+ RFSoC. The center frequency can be tuned from 1 MHz up
to 7.2 GHz, and bandwidths up to 400 MHz are supported. Custom development has
been done for the host computer and for the FPGA on the X410. In the following
paragraphs, we first give a functional description of the channel sounder,
followed by the details of the development on FPGA and the host computer. In
the last subsection, we also discuss how the transmitter and the receiver are
synchronized.

###  II-A Functional Description

During one channel snapshot, the transmitter sends multiple repetitions of the
same sounding signal (SS) with a length of $L$ samples, as illustrated in Fig.
1. Note that to avoid aliasing $L$ should be longer than

$L>\frac{\Delta\tau_{\mathrm{max}}}{T_{s}}$ (1)

where $\Delta\tau_{\mathrm{max}}$ is the maximum delay difference between the
first and last received multi-path component, and $T_{s}$ is the sample
period. These signals then propagate through the wireless channel and arrive
at the receiver with an unknown propagation delay. Hence, samples have to be
discarded according to this propagation delay. Otherwise, a couple of samples
will be averaged with noise, which reduces the signal-to-noise ratio. In
addition, another $L$ samples have to be discarded so the received sounding
signals are the result of a circular convolution between the channel impulse
response and the original sounding signal. We define $P$ as the total number
of samples that are discarded and it should be higher than

$P\geq\frac{\tau_{\mathrm{0,max}}}{T_{s}}+L$ (2)

where $\tau_{\mathrm{0,max}}$ the maximum delay of the first multi-path
component. In practice, $P$ can be set higher than required to account for
eventual timing synchronization errors between receiver and transmitter. After
disregarding $P$ samples, $M$ signals are captured and averaged. The averaging
is done by averaging each $i^{\mathrm{th}}$ sample of each received sounding
signal where $i\in[0,L-1]$, resulting in averaged received sounding signal of
length $L$, as depicted in Fig. 1. Then, the averaged signal is sent to the
host for channel estimation and storage. The rest of the received samples are
skipped until the following channel snapshot.

Figure 2: RFNoC architecture at the receiver

###  II-B Logic circuit on FPGA

At the transmitter, we utilized the X4_400 FPGA image flavor, part of the UHD
Release v4.2.0.0 [10], which includes a four-channel replay block. With the
replay block, we can download our sounding signal into the DRAM of the X410
and then transmit it at the appropriate time. The sounding signal loaded into
the DRAM of the transmitter has the length of the channel measurement interval
$T_{\mathrm{rep}}$, where the first part contains the
$\lceil\frac{ML+P}{L}\rceil$ sounding signals, and the second part is filled
with zeros. By using the onboard DRAM to transmit the sounding signal, there
is no transfer of sample data between the host computer and the USRP while the
USRP is transmitting. Hence, a standard Ethernet cable can be used to connect
the USRP and the host computer.

At the receiver, we took the same flavor as a basis but installed our custom
RFNoC block, written in Verilog, replacing the replay RFNoC block. The high-
level architecture of the receiver FPGA is depicted in Fig. 2. The custom
block selects samples based on a sample counter and averages the received
sounding signals described in the previous subsection. Since the data type is
complex short, the averaging could be efficiently done by bit-wise right
shifting each sample $K$ times and then adding up the $i^{\mathrm{th}}$ sample
of each sounding signal. The top-level circuit diagram of the averager is
depicted in Fig. 3. The averager consists of a shifter, block RAM (BRAM), and
an adder. The multiplexers are controlled by a state machine which consist of
three states: 1) IN: The samples are saved in the BRAM. 2) ADD_IN: The
$i^{\mathrm{th}}$ sample comes in and the $i^{\mathrm{th}}$ sample is fetched
out of the memory, and their sum is stored in the memory. 3) ADD_OUT: The
$i^{\mathrm{th}}$ sample comes in and the $i^{\mathrm{th}}$ sample is fetched
out of the memory. The sum of those samples is presented at the output of the
averager. Because of the high sample rate, two samples are being processed per
clock cycle, which results in a memory width of 64 bits. The clock driving
this RFNoC block is clk_radio2x, which is equal to of 250 MHz.

TABLE I: Overview of the parameters of the channel sounder  Parameter | Value | Description
---|---|---
$L$ | 1024 samples | Sound signal length
$P$ | 2048 samples | Skipped samples due to propagation
$M$ | 64 signals | Average quantity
$K$ | 6 bits | Bit shift in averager
$R$ | 2432416 samples | Skipped samples until next snapshot
$f$ | 5.725 GHz | Center frequency
$P_{\mathrm{Tx}}$ | 14 dBm | Output power
$T_{\mathrm{rep}}$ | 5 ms | Channel measurement repetition
$T_{s}$ | 2 ns | Sample period
Figure 3: Simplified top-level circuit diagram of the averager in the select
and average RFNoC block.

###  II-C Software on host computer

A custom C++ application has been written which utilizes the UHD library
(Release v4.2.0.0)[10], containing all the essential software to control the
USRPs. An additional library was also developed to set the parameters ($L$,
$P$, $K$, and $M$) belonging to the RFNoC block.

###  II-D Synchronization of transmitter and receiver

The transmitter and the receiver USRPs are synchronized via a PPS signal for
time synchronization, and a 10 MHz reference signal for frequency
synchronization. Through the main application on the host computer, the
synchronization source can be set to either a global positioning system (GPS)
disciplined oscillator or an external clock (e.g. Rubidium clock). The channel
sounder is designed to start at the positive flank of a PPS. In order to
remove the requirement for the transmitter and the receiver to start at the
same PPS flank, the repetition time $T_{\mathrm{rep}}$ needs to be chosen in
such a way that at each PPS flank a sounding signal starts transmitting, e.g.
$T_{\mathrm{rep}}$ = 5 ms. In this way, the transmitter and receiver can start
at different PPS flanks; hence, no communication is needed between the
transmitter and the receiver. Nevertheless, the transmitter and receiver can
also start on the same PPS flank via the GPS time when the system is
synchronized with GPS.

Figure 4: Measurement setup on the receiver side. Equipment on the desk from
left to rigth: Rubidium clock, NI USRP X410, PC (Advantech MIC-770 V2), a
power supply for the PC. Figure 5: Measured channel impulse responses in a lab
environment at 5.725 GHz with 400 MHz bandwidth, with and without averaging.

##  III Evaluation

Our design has been validated by employing a test-bench that verified sample
selection and averaging. In addition, we performed single-input, single-output
channel measurements of an indoor lab environment with two omnidirectional
antennas at 5.725 GHz separated by 5 meters. A picture of our setup can be
found in Fig. 4. The sounding signal, a Zadoff-Chu (ZC) signal, was sent in an
OFDM scheme, covering 813 out of 1024 sub-carriers, so that it covers a
bandwidth of about 400 MHz at a sample rate of 500 Msps. The parameter
configuration of the channel can be found in Table I. In Fig. 5, the measured
channel impulse response is depicted for two measurements, one with averaging
and one without averaging. Several multi-path components can be distinguished
in the figure due to the ultra-wide bandwidth. For $M=1$, one can observe a
higher noise level and several lobes beyond
$0.2\text{\,}\mathrm{\SIUnitSymbolMicro s}$. These lobes are caused by in-band
interference coming from an unknown device. However, by averaging the received
signals, this interference can be suppressed. Also, the effects of the RF
chains are taken into account by means of a back-to-back calibration. Because
of the onboard processing, the average data rate to the host computer during
the measurement was reduced to about 1 MB/s.

##  IV Conclusion

In this paper, we have presented the design of our UWB channel sounder built
with the USRP X410 and open-source tools that can be employed in various
channel measurement scenarios. Owing to a custom RFNoC block on the FPGA that
performs sample selection and averaging, the data rate to the host computer
could be reduced significantly. In the future, the design will be extended so
it is capable of measuring multiple-input multiple-output channels.

## References

  * [1] A. Merwaday, N. Rupasinghe, . Güvenç, W. Saad, and M. Yuksel, “USRP-based indoor channel sounding for D2D and multi-hop communications,” in _WAMICON_ , 2014, pp. 1–6.
  * [2] S. Zelenbaba, D. Löschenbrand, M. Hofer, A. Dakić, B. Rainer, G. Humer, and T. Zemen, “A Scalable Mobile Multi-Node Channel Sounder,” in _IEEE Wireless Communications and Networking Conference (WCNC)_ , May 2020, pp. 1–6.
  * [3] D. Stanko, G. Sommerkorn, A. Ihlow, and G. Del Galdo, “Enable software-defined radios for real-time MIMO channel sounding,” in _IEEE International Instrumentation and Measurement Technology Conference (I2MTC)_ , 2021, pp. 1–5.
  * [4] G. Zhang, X. Cai, W. Fan, and G. F. Pedersen, “A USRP-Based Channel Sounder for UAV Communications,” in _14th European Conference on Antennas and Propagation (EuCAP)_ , Mar. 2020, pp. 1–4.
  * [5] X. Cai, J. Rodríguez-Piñeiro, X. Yin, N. Wang, B. Ai, G. F. Pedersen, and A. P. Yuste, “An empirical air-to-ground channel model based on passive measurements in LTE,” _IEEE Transactions on Vehicular Technology_ , vol. 68, no. 2, pp. 1140–1154, 2019.
  * [6] X. Cai, T. Izydorczyk, J. Rodríguez-Piñeiro, I. Z. Kovács, J. Wigard, F. M. L. Tavares, and P. E. Mogensen, “Empirical low-altitude air-to-ground spatial channel characterization for cellular networks connectivity,” _IEEE Journal on Selected Areas in Communications_ , vol. 39, no. 10, pp. 2975–2991, 2021.
  * [7] X. Cai, A. Gonzalez-Plaza, D. Alonso, L. Zhang, C. B. Rodríguez, A. P. Yuste, and X. Yin, “Low altitude UAV propagation channel modelling,” in _2017 11th European Conference on Antennas and Propagation (EUCAP)_ , 2017, pp. 1443–1447.
  * [8] B. Gokalgandhi, P. Maddala, and I. Seskar, “Implementation of fgpa based channel sounder for large scale antenna systems using rfnoc on usrp platform,” 09 2017.
  * [9] Ettus Research, “RFNoC.” [Online]. Available: https://www.ettus.com/sdr-software/rfnoc/
  * [10] ——, “USRP Hardware Driver (UHD™) Software.” [Online]. Available: https://github.com/EttusResearch/uhd