# Lachesis: Scalable Asynchronous BFT on DAG Streams

Quan Nguyen  FANTOM  Andre Cronje  FANTOM  Michael Kong  FANTOM  Egor Lysenko
FANTOM  Alex Guzev  FANTOM

###### Abstract

This paper consolidates the core technologies and key concepts of our novel
Lachesis consensus protocol and Fantom Opera platform, which is
permissionless, leaderless and EVM compatible.

We introduce our new protocol, so-called Lachesis, for distributed networks
achieving Byzantine fault tolerance (BFT) [10]. Each node in Lachesis protocol
operates on a local block DAG, namely _OPERA DAG_. Aiming for a low time to
finality (TTF) for transactions, our general model considers DAG streams of
high speed but asynchronous events. We integrate Proof-of-Stake (PoS) into a
DAG model in Lachesis protocol to improve performance and security. Our
general model of trustless system leverages participants’ stake as their
validating power [33]. Lachesis’s consensus algorithm uses Lamport timestamps,
graph layering and concurrent common knowledge to guarantee a consistent total
ordering of event blocks and transactions. In addition, Lachesis protocol
allows dynamic participation of new nodes into Opera network. Lachesis
optimizes DAG storage and processing time by splitting local history into
checkpoints (so-called epochs). We also propose a model to improve stake
decentralization, and network safety and liveness [32].

Built on our novel Lachesis protocol, Fantom’s Opera platform is a public,
leaderless, asynchronous BFT, layer-1 blockchain, with guaranteed
deterministic finality. Hence, Lachesis protocol is suitable for distributed
ledgers by leveraging asynchronous partially ordered sets with logical time
ordering instead of blockchains. We also present our proofs into a model that
can be applied to abstract asynchronous distributed system.

_K_ eywords Lachesis protocol $\cdot$ Consensus algorithm $\cdot$ DAG $\cdot$
Proof of Stake $\cdot$ Permissionless $\cdot$ Leaderless $\cdot$ aBFT $\cdot$
Lamport timestamp $\cdot$ Root $\cdot$ Clotho $\cdot$ Atropos $\cdot$ Main
chain $\cdot$ Happened-before $\cdot$ Layering $\cdot$ CCK $\cdot$ Trustless
System $\cdot$ Validating power $\cdot$ Staking model

###### Contents

  1. 1 Introduction
    1. 1.1 Motivation
    2. 1.2 Lachesis protocol: Proof-Of-Stake DAG aBFT
    3. 1.3 Contributions
    4. 1.4 Paper structure
  2. 2 Related work
    1. 2.1 An overview of Blockchains
      1. 2.1.1 Consensus algorithms
      2. 2.1.2 Proof of Work
      3. 2.1.3 Proof of Stake
      4. 2.1.4 DAG-based approaches
    2. 2.2 Lamport timestamps
    3. 2.3 Concurrent common knowledge
  3. 3 Lachesis: Proof-Of-Stake DAG-based Protocol
    1. 3.1 OPERA DAG
    2. 3.2 PoS Definitions
      1. 3.2.1 Stake
      2. 3.2.2 Validating Power and Block Validation
      3. 3.2.3 Stake-based Validation
      4. 3.2.4 Validation Score
    3. 3.3 S-OPERA DAG: A weighted DAG model
    4. 3.4 Overall Framework
    5. 3.5 Quorum
    6. 3.6 Event Block Creation
    7. 3.7 Event Block Structure
    8. 3.8 Root Selection
    9. 3.9 Clotho Selection
    10. 3.10 Atropos Selection
    11. 3.11 Atropos timestamp
    12. 3.12 Main chain
    13. 3.13 Topological ordering of events
    14. 3.14 Blocks
    15. 3.15 Block timestamp
    16. 3.16 Peer selection
    17. 3.17 Dynamic participants
    18. 3.18 Peer synchronization
    19. 3.19 Detecting Forks
    20. 3.20 Transaction confirmations
    21. 3.21 Checkpoint
  4. 4 Staking model
    1. 4.0.1 Definitions and Variables
    2. 4.0.2 Validating power
    3. 4.0.3 Block consensus and Rewards
    4. 4.0.4 Token Staking and Delegation
  5. 5 Opera Network
    1. 5.1 Network Architecture
    2. 5.2 Nodes and Roles
    3. 5.3 Boot Node Service
    4. 5.4 API Service
    5. 5.5 Mainnet
    6. 5.6 Testnet
    7. 5.7 Implementation
    8. 5.8 Performance and Statistics
      1. 5.8.1 Normal emission rate and gas allocation
      2. 5.8.2 High latency nodes
      3. 5.8.3 Emission rates
  6. 6 Discussions
    1. 6.1 Comparison with Existing Approaches
    2. 6.2 Protocol Fairness and Security
      1. 6.2.1 Protocol Fairness
      2. 6.2.2 Security
    3. 6.3 Response to Attacks
    4. 6.4 Choices of Stake Decentralization
      1. 6.4.1 Low staked validators
      2. 6.4.2 Choices of $L$ and $U$
      3. 6.4.3 Alternative models for gossip and staking
      4. 6.4.4 Network load
  7. 7 Conclusion
    1. 7.1 Future work
  8. 8 Appendix
    1. 8.1 Basic Definitions
      1. 8.1.1 Events
      2. 8.1.2 OPERA DAG
      3. 8.1.3 Happened-Before relation
      4. 8.1.4 Lamport timestamp
      5. 8.1.5 Domination relation
    2. 8.2 Proof of aBFT
      1. 8.2.1 S-OPERA DAG - A Weighted DAG
      2. 8.2.2 Consistency of DAGs
      3. 8.2.3 Root
      4. 8.2.4 Clotho
      5. 8.2.5 Atropos
      6. 8.2.6 Block
      7. 8.2.7 Main chain
      8. 8.2.8 Fork free
    3. 8.3 Semantics of Lachesis
      1. 8.3.1 Node State
      2. 8.3.2 Consistent Cut
      3. 8.3.3 State in aBFT Lachesis
  9. 9 Alternatives for scalability
    1. 9.1 Layering-based Model
      1. 9.1.1 Layering Definitions
      2. 9.1.2 H-OPERA DAG
      3. 9.1.3 Root Graph
      4. 9.1.4 Frame Assignment
      5. 9.1.5 Consensus
      6. 9.1.6 Main procedure
    2. 9.2 STAIR Model
  10. 10 Reference

##  1 Introduction

Interests in blockchains and distributed ledger technologies have surged
significantly since Bitcoin [30] was introduced in late 2008. Bitcoin and
blockchain technologies have enabled numerous opportunities for business and
innovation. Beyond the success over cryptocurrency, the decentralization
principle of blockchains has attracted numerous applications across different
domains from financial, healthcare to logistics. Blockchains provide
immutability and transparency of blocks that facilitate highly trustworthy,
append-only, transparent public distributed ledgers and area promising
solution for building trustless systems. Public blockchain systems support
third-party auditing and some of them offer a high level of anonymity.

Blockchain is generally a distributed database system, which stores a database
of all transactions within the network and replicate it to all participating
nodes. A distributed consensus protocol running on each node to guarantee
consistency of these replicas so as to maintain a common transaction ledger.
In a distributed database system, _Byzantine_ fault tolerance (BFT) [23] is
paramount to reliability of the system to make sure it is tolerant up to one-
third of the participants in failure.

Consensus algorithms ensure the integrity of transactions over the distributed
network, and they are equivalent to the proof of BFT [1, 22]. In practical BFT
(pBFT) can reach a consensus for a block once the block is shared with other
participants and the share information is further shared with others [19, 29].

Despite of the great success, blockchain systems are still facing some
limitations. Recent advances in consensus algorithms [44, 24, 26, 17, 41, 42]
have improved the consensus confirmation time and power consumption over
blockchain-powered distributed ledgers.

_Proof of Work_ (PoW): is introduced in the Bitcoin’s Nakamoto consensus
protocol [30]. Under PoW, validators are randomly selected based on their
computation power. PoW protocol requires exhaustive computational work and
high demand of electricity from participants for block generation. It also
requires longer time for transaction confirmation.

_Proof Of Stake_ (PoS): leverages participants’ stakes for selecting the
creator of the next block [44, 24]. Validators have voting power proportional
to their stake. PoS requires less power consumption and is more secure than
PoW, because the stake of a participant is voided and burnt if found
dishonest.

_DAG_ (Directed Acyclic Graph): DAG based currency was first introduced in
DagCoin paper [26]. DAG technology allows cryptocurrencies to function
similarly to those that utilize blockchain technology without the need for
blocks and miners. DAG-based approaches utilize directed acyclic graphs (DAG)
[26, 41, 42, 37, 27] to facilitate consensus. Examples of DAG-based consensus
algorithms include Tangle [38], Byteball [11], and Hashgraph [2]. Tangle
selects the blocks to connect in the network utilizing accumulated weight of
nonce and Monte Carlo Markov Chain (MCMC). Byteball generates a main chain
from the DAG and reaches consensus through index information of the chain.
Hashgraph connects each block from a node to another random node. Hashgraph
searches whether 2/3 members can reach each block and provides a proof of
Byzantine fault tolerance via graph search.

###  1.1 Motivation

Practical Byzantine Fault Tolerance (pBFT) allows all nodes to successfully
reach an agreement for a block (information) when a Byzantine node exists [7].
In pBFT, consensus is reached once a created block is shared with other
participants and the share information is shared with others again [19, 29].
After consensus is achieved, the block is added to the participants’ chains
[7, 14]. It takes $O(n^{4})$ for pBFT, where $n$ is the number of
participants.

DAG-based approaches [26, 41, 42, 37, 27] and Hashgraph [2] leverage block DAG
of event blocks to reach consensus. The propose to use virtual voting on the
local block DAG to determine consensus, yet their approach has some
limitations. First, the algorithm operates on a known network comprised of
known authoritative participants aka permissioned network. Second, gossip
propagation is slow with a latency of $O(n)$ for $n$ participants. Third, it
remains unclear whether their consensus and final event ordering algorithms
are truly asynchronous BFT.

In addition, there is only a few research work studying Proof-of-Stake in DAG-
based consensus protocols. One example is [2], but it is briefly mentioned in
that paper.

Hence, in this paper, we are interested in a new approach to address the
aforementioned issues in existing pBFT and DAG-based approaches, and the new
approach leverages participant’s stake to improve DAG-based consensus
decisions. Specifically, we propose a new consensus algorithm that addresses
the following questions:

  * •

Can we achieve a public Proof-Of-Stake + DAG-based consensus protocol?

  * •

Can pBFT be achieved when time-to-finality (TTF) for transactions is kept
closed to 1 second?

  * •

Can we reach local consensus in a $k$-cluster faster for some $k$?

  * •

Can we achieve faster event propagation such as using a subset broadcast?

  * •

Can continuous common knowledge be used for consensus decisions with high
probability?

###  1.2 Lachesis protocol: Proof-Of-Stake DAG aBFT

In this paper, we introduce our Lachesis protocol, denoted by $\mathcal{L}$ to
reach faster consensus using topological ordering of events for an
asynchronous non-deterministic distributed system that guarantees pBFT with
deterministic finality.

The core idea of Lachesis is the OPERA DAG, which is a block DAG. Nodes
generate and propagate event blocks asynchronously and the Lachesis algorithm
achieves consensus by confirming how many nodes know the event blocks using
the OPERA DAG. In Lachesis protocol, a node can create a new event block,
which has a set of 2 to $k$ parents. OPERA DAG is used to compute special
event blocks, such as Root, Clotho, and Atropos. The Main chain consists of
ordered Atropos event blocks. It can maintain reliable information between
event blocks. The OPERA DAG and Main chain are updated frequently with newly
generated event blocks and can respond strongly to attack situations such as
forking and parasite attack.

PoS + DAG: We introduce StakeDag protocol [33] and StairDag protocol [32]
presents a general model that integrates Proof of Stake model into DAG-based
consensus protocol Lachesis. Both generate blocks asynchronously to build a
_weighted DAG_ from Validator blocks. Consensus on a block is computed from
the gained validating power of validators on the block. We use Lamport
timestamp, Happened-before relation between event blocks, graph layering and
hierarchical graphs on the weighted DAG, to achieve deterministic topological
ordering of finalized event blocks in an asynchronous leaderless DAG-based
system.

Figure 1: Consensus Method through Path Search in a DAG (combines chain with
consensus process of pBFT)

Figure 1 illustrates how consensus is reached through the path search in the
OPERA DAG. Leaf set, denoted by $R_{s0}$, consists of the first event blocks
created by individual participant nodes. Let $R_{si}$ be the $i$-th root set.
A root $r_{1}$ in $R_{s1}$ can reach more than a quorum in the leaf set. A
quorum is 2/3W, where W is the total validating power in a weighted DAG, or
2/3n where n is the number nodes in an unweighted DAG. A root $r_{3}$ in a
later root set may confirm some root $r^{\prime}$ in $R_{s1}$ and the subgraph
of $r^{\prime}$. Lachesis protocol reaches consensus in this manner and is
similar to the proof of pBFT approach.

Dynamic participation: Lachesis protocol supports _dynamic participation_ so
that all participants can join the network [9].

Layering: Lachesis protocol leverages the concepts of graph layering and
hierarchical graphs on the DAG, as introduced in our ONLAY framework [31].
Assigned layers are used to achieve deterministic topological ordering of
finalized event blocks in an asynchronous leaderless DAG-based system.

The main concepts of Lachesis protocol are given as follows:

  * •

Event block: Nodes can create event blocks. Event block includes the
signature, generation time, transaction history, and reference to parent event
blocks.

  * •

Happened-before: is the relationship between nodes which have event blocks. If
there is a path from an event block $x$ to $y$, then $x$ Happened-before $y$.
“$x$ Happened-before $y$” means that the node creating $y$ knows event block
$x$.

  * •

Lamport timestamp: For topological ordering, Lamport timestamp algorithm uses
the happened-before relation to determine a partial order of the whole event
block based on logical clocks.

  * •

Stake: This corresponds to the amount of tokens each node possesses in their
deposit. This value decides the validating power a node can have.

  * •

User node: A user node has a small amount stake (e.g., containing 1 token).

  * •

Validator node: A validator node has large amount of stake ($\geq$ 2 tokens).

  * •

Validation score: Each event block has a validation score, which is the sum of
the weights of the roots that are reachable from the block.

  * •

OPERA DAG: is the local view of the DAG held by each node, this local view is
used to identify topological ordering, select Clotho, and create time
consensus through Atropos selection.

  * •

S-OPERA DAG: is the local view of the weighted Directed Acyclic Graph (DAG)
held by each node. This local view is used to determine consensus.

  * •

Root: An event block is called a _root_ if either (1) it is the first event
block of a node, or (2) it can reach more than $2/3$ of the network’s
validating power from other roots. A _root set_ $R_{s}$ contains all the roots
of a frame. A _frame_ $f$ is a natural number assigned to Root sets and its
dependent event blocks.

  * •

Clotho: A Clotho is a root at layer $i$ that is known by a root of a higher
frame ($i$ \+ 1), and which in turns is known by another root in a higher
frame ($i$ +2).

  * •

Atropos: is a Clotho assigned with a consensus time.

  * •

Main chain: StakeDag’s Main chain is a list of Atropos blocks and the
subgraphs reachable from those Atropos blocks.

###  1.3 Contributions

In summary, this paper makes the following contributions:

  * •

We propose a novel consensus protocol, namely Lachesis, which is Proof-Of-
Stake DAG-based, aiming for practical aBFT distributed ledger.

  * •

Our Lachesis protocol uses Lamport timestamp and happened-before relation on
the DAG, for faster consensus. Our consensus algorithms for selection of
roots, Clothos and Atropos are deterministic and scalable.

  * •

Lachesis protocol allows _dynamic participation_ for all participants to join
the network.

  * •

Our protocol leverages _epochs_ or _checkpoints_ to significantly improve
storage usage and achieve faster consensus computation.

  * •

We define a formal model using continuous consistent cuts of a local view to
achieve consensus via layer assignment. Our work is the first that give a
detailed model, formal semantics and proofs for an aBFT PoS DAG-based
consensus protocol.

###  1.4 Paper structure

The rest of this paper is organized as follows. Section 2 gives the related
work. Section 3 presents our model of Lachesis protocol that is Proof of Stake
DAG-based. Section 4 introduces a staking model that is used for our STAIR
consensus protocol. Section 5 describes the Opera network’s overall
architecture, node roles and running services to support Fantom’s ecosystem.
We also give a brief performance analysis and some statistics of the Opera
network. Section 6 gives some discussions about our Proof of Stake STAIR
protocol, such as fairness and security. Section 7 concludes.

##  2 Related work

###  2.1 An overview of Blockchains

A blockchain is a type of distributed ledger technology (DLT) to build record-
keeping system in which its users possess a copy of the ledger. The system
stores transactions into blocks that are linked together. The blocks and the
resulting chain are immutable and therefore serving as a proof of existence of
a transaction. In recent years, the blockchain technologies have seen a
widespread interest, with applications across many sectors such as finance,
energy, public services and sharing platforms.

For a public or permissionless blockchain, it has no central authority.
Instead, consensus among users is paramount to guarantee the security and the
sustainability of the system. For private, permissioned or consortium
blockchains, one entity or a group of entities can control who sees, writes
and modifies the data on it. We are interested in the decentralization of BCT
and hence only public blockchains are considered in this section.

In order to reach a global consensus on the blockchain, users must follow the
rules set by the consensus protocol of the system.

####  2.1.1 Consensus algorithms

In a consensus algorithm, all participant nodes of a distributed network share
transactions and agree integrity of the shared transactions [23]. It is
equivalent to the proof of Byzantine fault tolerance in distributed database
systems [1, 22]. The Practical Byzantine Fault Tolerance (pBFT) allows all
nodes to successfully reach an agreement for a block when a Byzantine node
exists [7].

There have been extensive research in consensus algorithms. Proof of Work
(PoW) [30], used in the original Nakamoto consensus protocol in Bitcoin,
requires exhaustive computational work from participants for block generation.
Proof Of Stake (PoS) [44, 24] uses participants’ stakes for generating blocks.
Some consensus algorithms [8, 17, 41, 42] have addressed to improve the
consensus confirmation time and power consumption over blockchain-powered
distributed ledges. These approaches utilize directed acyclic graphs (DAG)
[26, 41, 42, 37, 27] to facilitate consensus. Examples of DAG-based consensus
algorithms include Tangle [38], Byteball [11], and Hashgraph [2]. Lachesis
protocol [10] presents a general model of DAG-based consensus protocols.

####  2.1.2 Proof of Work

Bitcoin was the first and most used BCT application. Proof of Work (PoW) is
the consensus protocol introduced by the Bitcoin in 2008 [30]. In PoW
protocol, it relies on user’s computational power to solve a cryptographic
puzzle that creates consensus and ensures the integrity of data stored in the
chain. Nodes validate transactions in blocks (i.e. verify if sender has
sufficient funds and is not double-spending) and competes with each other to
solve the puzzle set by the protocol. The incentive for miners to join this
mining process is two-fold: the first miner, who finds a solution, is rewarded
(block reward) and gains all the transaction fees associated to the
transactions. Nodes validate transactions in blocks with an incentive to gain
block reward and transaction fees associated to the transactions.

The key component in Bitcoin protocol and its successors is the PoW puzzle
solving. The miner that finds it first can issue the next block and her work
is rewarded in cryptocurrency. PoW comes together with an enormous energy
demand.

From an abstract view, there are two properties of PoW blockchain:

  * •

Randomized leader election: The puzzle contest winner is elected to be the
leader and hence has the right to issue the next block. The more computational
power a miner has, the more likely it can be elected.

  * •

Incentive structure: that keeps miners behaving honestly and extending the
blockchain. In Bitcoin this is achieved by miners getting a block discovery
reward and transaction fees from users. In contrast, subverting the protocol
would reduce the trust of the currency and would lead to price loss. Hence, a
miner would end up undermining the currency that she itself collects.

Based on those two characteristics, several alternatives to Proof-of-Work have
been proposed.

####  2.1.3 Proof of Stake

_Proof of Stake_(PoS) is an alternative to PoW for blockchains. PoS relies on
a lottery like system to select the next leader or block submitter. Instead of
using puzzle solving, PoS is more of a lottery system. Each node has a certain
amount of stake in a blockchain. Stake can be the amount of currency, or the
age of the coin that a miner holds. In PoS, the leader or block submitter is
randomly elected with a probability proportional to the amount of stake it
owns in the system. The elected participant can issue the next block and then
is rewarded with transaction fees from participants whose data are included.
The more stake a party has, the more likely it can be elected as a leader.
Similarly to PoW, block issuing is rewarded with transaction fees from
participants whose data are included. The underlying assumption is that:
stakeholders are incentivized to act in its interests, so as to preserve the
system.

There are two major types of PoS. The first type is chain-based PoS [36],
which uses chain of blocks like in PoW, but stakeholders are randomly selected
based on their stake to create new blocks. This includes Peercoin [18],
Blackcoin [45], and Iddo Bentov’s work [4], just to name a few. The second
type is BFT-based PoS that is based on BFT consensus algorithms such as pBFT
[7]. Proof of stake using BFT was first introduced by Tendermint [20], and has
attracted more research [8]. Ethereum’s Parity project have investigated to
migrate into a PoS blockchain [46].

PoS is more advantageous than PoW because it only requires cheap hardware and
every validator can submit blocks. PoS approach reduces the energy demand and
is more secure than PoW.

Every validator can submit blocks and the likelihood of acceptance is
proportional to the % of network weight (i.e., total amount of tokens being
staked) they possess. Thus, to secure the blockchain, nodes need the actual
native token of that blockchain. To acquire the native tokens, one has to
purchase or earn them with staking rewards. Generally, gaining 51% of a
network’s stake is much harder than renting computation.

Security Although PoS approach reduces the energy demand, new issues arise
that were not present in PoW-based blockchains. These issues are shown as
follows:

  * •

Grinding attack: Malicious nodes can play their bias in the election process
to gain more rewards or to double spend their money.

  * •

Nothing at stake attack: In PoS, constructing alternative chains becomes
easier. A node in PoS seemingly does not lose anything by also mining on an
alternative chain, whereas it would lose CPU time if working on an alternative
chain in PoW.

Delegated Proof of Stake To tackle the above issues in PoS, _Delegated Proof
of Stake_ (DPoS) consensus protocols are introduced, such as Lisk, EOS [15],
Steem [43], BitShares [5] and Ark [13]. DPoS uses voting to reach consensus
among nodes more efficiently by speeding up transactions and block creation.
Users have different roles and have a incentive to behave honestly in their
role.

In DPoS systems, users can _vote_ to select _witnesses_ , to whom they trust,
to create blocks and validate transactions. For top tier witnesses that have
earned most of the votes, they earn the right to validate transactions.
Further, users can also _delegate_ their voting power to other users, whom
they trust, to vote for witnesses on their behalf. In DPoS, votes are weighted
based on the stake of each voter. A user with small stake amount can become a
top tier witness, if it receives votes from users with large stakes.

Top witnesses are responsible for validating transactions and creating blocks,
and then get fee rewards. Witnesses in the top tier can exclude certain
transactions into the next block. But they cannot change the details of any
transaction. There are a limited number of witnesses in the system. A user can
replace a top tier witness if s/he gets more votes or is more trusted. Users
can also vote to remove a top tier witness who has lost their trust. Thus, the
potential loss of income and reputation is the main incentive against
malicious behavior in DPoS.

Users in DPoS systems also vote for a group of _delegates_ , who are trusted
parties responsible for maintaining the network. Delegates are in charge of
the governance and performance of the entire blockchain protocol. But the
delegates cannot do transaction validation and block generation. For example,
they can propose to change block size, or the reward a witness can earn from
validating a block. The proposed changes will be voted by the system’s users.

DPoS brings various benefits: (1) faster than traditional PoW and PoS Stake
systems; (2) enhance security and integrity of the blockchains as each user
has an incentive to perform their role honestly; (3) normal hardware is
sufficient to join the network and become a user, witness, or delegate; (4)
more energy efficient than PoW.

Leasing Proof Of Stake Another type of widely known PoS is Leasing Proof Of
Stake (LPoS). Like DPoS, LPoS allows users to vote for a delegate that will
maintain the integrity of the system. Further, users in a LPoS system can
lease out their coins and share the rewards gained by validating a block.

Proof of Authority Another successor of PoS is _Proof of Authority_ (PoA). In
PoA, the reputation of a validator acts as the stake [16]. PoA runs by a set
of validators in a permissioned system. It gains higher throughput by reducing
the number of messages sent between the validators. Reputation is difficult to
regain once lost and thus is a better choice for “stake”.

There are a number of surveys that give comprehensive details of PoW and PoS,
such as [40, 35].

Based on STAIR [32] and StakeDag [33], our Lachesis consensus protocos can be
used for public permissionless asynchronous Proof of Stake systems.
Participants are allowed to delegate their stake to a node to increase
validating power of a node and share the validation rewards. Unlike existing
DAG-based previous work, our Lachesis protocols are PoS+DAG approach.

####  2.1.4 DAG-based approaches

DAG-based approaches have currently emerged as a promising alternative to the
PoW and PoS blockchains. The notion of a _DAG_ (directed acyclic graph) was
first coined in 2015 by DagCoin [26]. Since then, DAG technology has been
adopted in numerous systems, for example, [26, 41, 42, 37, 27]. Unlike a
blockchain, DAG-based system facilitate consensus while achieving horizontal
scalability.

DAG technology has been adopted in numerous systems. This section will present
the popular DAG-based approaches. Examples of DAG-based approaches include
Tangle [38], Byteball [11], Hashgraph [2], RaiBlocks [25], Phantom [42],
Spectre [41], Conflux [27], Parsec [37] and Blockmania [14] .

Tangle is a DAG-based approach proposed by IOTA [38]. Tangle uses PoW to
defend against sybil and spam attacks. Good actors need to spend a
considerable amount of computational power, but a bad actor has to spend
increasing amounts of power for diminishing returns. Tips based on transaction
weights are used to address the double spending and parasite attack.

Byteball [11] introduces an internal pay system called Bytes used in
distributed database. Each storage unit is linked to previous earlier storage
units. The consensus ordering is computed from a single main chain consisting
of roots. Double spends are detected by a majority of roots in the chain.

Hashgraph [2] introduces an asynchronous DAG-based approach in which each
block is connected with its own ancestor. Nodes randomly communicate with each
other about their known events. Famous blocks are computed by using see and
strong see relationship at each round. Block consensus is achieved with the
quorum of more than 2/3 of the nodes.

RaiBlocks [25] was proposed to improve high fees and slow transaction
processing. Consensus is obtained through the balance weighted vote on
conflicting transactions. Each participating node manages its local data
history. Block generation is carried similarly as the anti-spam tool of PoW.
The protocol requires verification of the entire history of transactions when
a new block is added.

Phantom [42] is a PoW based permissionless protocol that generalizes
Nakamoto’s blockchain to a DAG. A parameter $k$ is used to adjust the
tolerance level of the protocol to blocks that were created concurrently. The
adjustment can accommodate higher throughput; thus avoids the security-
scalability trade-off as in Satoshi’s protocol. A greedy algorithm is used on
the DAG to distinguish between blocks by honest nodes and the others. It
allows a robust total order of the blocks that is eventually agreed upon by
all honest nodes.

Like PHANTOM, the GHOSTDAG protocol selects a $k$-cluster, which induces a
colouring of the blocks as Blues (blocks in the selected cluster) and Reds
(blocks outside the cluster). GHOSTDAG finds a cluster using a greedy
algorithm, rather than looking for the largest $k$-cluster.

Spectre [41] uses DAG in a PoW-based protocol to tolerate from attacks with up
to 50% of the computational power. The protocol gives a high throughput and
fast confirmation time. Sprectre protocol satisfies weaker properties in which
the order between any two transactions can be decided from the transactions by
honest users; whilst conventionally the order must be decided by all non-
corrupt nodes.

Conflux [27] is a DAG-based Nakamoto consensus protocol. It optimistically
processes concurrent blocks without discarding any forks. The protocol
achieves consensus on a total order of the blocks, which is decided by all
participants. Conflux can tolerate up to half of the network as malicious
while the BFT-based approaches can only tolerate up to one third of malicious
nodes.

Parsec [37] proposes a consensus algorithm in a randomly synchronous BFT
network. It has no leaders, no round robin, no PoW and reaches eventual
consensus with probability one. Parsec can reach consensus quicker than
Hashgraph [2]. The algorithm reaches 1/3-BFT consensus with very weak
synchrony assumptions. Messages are delivered with random delays, with a
finite delay in average.

Blockmania [14] achieves consensus with several advantages over the
traditional pBFT protocol. In Blockmania, nodes in a quorum only emit blocks
linking to other blocks, irrespective of the consensus state machine. The
resulting DAG of blocks is used to ensure consensus safety, finality and
liveliness. It reduces the communication complexity to $O(N^{2})$ even in the
worse case, as compared to pBFT’s complexity of $O(N^{4})$.

In this paper, our StakeDag protocol is different from the previous work. We
propose a general model of DAG-based consensus protocols, which uses Proof of
Stake for asynchronous permissionless BFT systems. StakeDag protocol is based
on our previous DAG-based protocols[10, 9] to achieve asynchronous non-
deterministic pBFT. The new $S_{\phi}$ protocol, which is based on our ONLAY
framework [31], uses graph layering to achieve scalable, reliable consensus in
a leaderless aBFT DAG.

###  2.2 Lamport timestamps

Lamport [21] defines the ”happened before” relation between any pair of events
in a distributed system of machines. The happened before relation, denoted by
$\rightarrow$, is defined without using physical clocks to give a partial
ordering of events in the system. The relation ”$\rightarrow$” satisfies the
following three conditions: (1) If $b$ and $b^{\prime}$ are events in the same
process, and $b$ comes before $b^{\prime}$, then $b\rightarrow b^{\prime}$.
(2) If $b$ is the sending of a message by one process and $b^{\prime}$ is the
receipt of the same message by another process, then $b\rightarrow
b^{\prime}$. (3) If $b\rightarrow b^{\prime}$ and $b^{\prime}\rightarrow
b^{\prime\prime}$ then $b\rightarrow b^{\prime\prime}$. Two distinct events
$b$ and $b^{\prime}$ are said to be concurrent if $b\nrightarrow b^{\prime}$
and $b^{\prime}\nrightarrow b$.

The happened-before relation can be viewed as a causality effect: that
$b\rightarrow b^{\prime}$ implies event $b$ may causally affect event
$b^{\prime}$. Two events are concurrent if neither can causally affect the
other.

Lamport introduces logical clocks which is a way of assigning a number to an
event. A clock $C_{i}$ for each process $P_{i}$ is a function which assigns a
number $C_{i}(b)$ to any event $b\in P_{i}$. The entire system of blocks is
represented by the function $C$ which assigns to any event $b$ the number
$C(b)$, where $C(b)=C_{j}(b)$ if $b$ is an event in process $P_{j}$. The Clock
Condition states that for any events $b$, $b^{\prime}$: if $b\rightarrow
b^{\prime}$ then $C(b)$ $<$ $C(b^{\prime})$.

The clocks must satisfy two conditions. First, each process $P_{i}$ increments
$C_{i}$ between any two successive events. Second, we require that each
message $m$ contains a timestamp $T_{m}$, which equals the time at which the
message was sent. Upon receiving a message timestamped $T_{m}$, a process must
advance its clock to be later than $T_{m}$.

Given any arbitrary total ordering $\prec$ of the processes, the total
ordering $\Rightarrow$ is defined as follows: if $a$ is an event in process
$P_{i}$ and $b$ is an event in process $P_{j}$, then $b\Rightarrow b^{\prime}$
if and only if either (i) $C_{i}(b)<C_{j}(b^{\prime})$ or (ii)
$C(b)=Cj(b^{\prime})$ and $P_{i}\prec P_{j}$. The Clock Condition implies that
if $b\rightarrow b^{\prime}$ then $b\Rightarrow b^{\prime}$.

###  2.3 Concurrent common knowledge

In the Concurrent common knowledge (CCK) paper [34], they define a model to
reason about the concurrent common knowledge in asynchronous, distributed
systems. A system is composed of a set of processes that can communicate only
by sending messages along a fixed set of channels. The network is not
necessarily completely connected. The system is asynchronous in the sense that
there is no global clock in the system, the relative speeds of processes are
independent, and the delivery time of messages is finite but unbounded.

A local state of a process is denoted by $s^{j}_{i}$. Actions are state
transformers; an action is a function from local states to local states. An
action can be either: a send(m) action where m is a message, a receive(m)
action, and an internal action. A local history, $h_{i}$, of process $i$, is a
(possibly infinite) sequence of alternating local states—beginning with a
distinguished initial state—and actions. We write such a sequence as follows:
$h_{i}=s_{i}^{0}\xrightarrow{\alpha_{i}^{1}}s_{i}^{1}\xrightarrow{\alpha_{i}^{2}}s_{i}^{2}\xrightarrow{\alpha_{i}^{3}}...$
The notation of $s^{j}_{i}$ ($\alpha^{j}_{i}$) refers to the $j$-th state
(action) in process $i$’s local history An event is a tuple $\langle
s,\alpha,s^{\prime}\rangle$ consisting of a state, an action, and a state. The
$j$th event in process $i$’s history is $e^{j}_{i}$ denoting $\langle
s^{j-1}_{i},\alpha^{j}_{i},s^{j}_{i}\rangle$.

An asynchronous system consists of the following sets.

  1. 1.

A set $P$ = {1,…,$N$} of process identifiers, where $N$ is the total number of
processes in the system.

  2. 2.

$A$ set $C$ $\subseteq$ {($i$,$j$) s.t. $i,j\in P$} of channels. The
occurrence of $(i,j)$ in $C$ indicates that process $i$ can send messages to
process $j$.

  3. 3.

A set $H_{i}$ of possible local histories for each process $i$ in $P$.

  4. 4.

A set $A$ of asynchronous runs. Each asynchronous run is a vector of local
histories, one per process, indexed by process identifiers. Thus, we use the
notation $a=\langle h_{1},h_{2},h_{3},...h_{N}\rangle$. Constraints on the set
$A$ are described throughout this section.

  5. 5.

A set $M$ of messages. A message is a triple $\langle i,j,B\rangle$ where
$i\in P$ is the sender of the message, $j\in P$ is the message recipient, and
$B$ is the body of the message. $B$ can be either a special value (e.g. a tag
to denote a special-purpose message), or some proposition about the run (e.g.
“$i$ has reset variable $X$ to zero”), or both. We assume, for ease of
exposition only, that messages are unique.

The set of channels $C$ and our assumptions about their behavior induce two
constraints on the runs in $A$. First, $i$ cannot send a message to $j$ unless
$(i,j)$ is a channel. Second, if the reception of a message $m$ is in the run,
then the sending of $m$ must also be in that run; this implies that the
network cannot introduce spurious messages or alter messages.

The CCK model of an asynchronous system does not mention time. Events are
ordered based on Lamport’s happened-before relation. They use Lamport’s theory
to describe global states of an asynchronous system. A global state of run $a$
is an $n$-vector of prefixes of local histories of $a$, one prefix per
process. Happened-before relation can be used to define a consistent global
state, often termed a consistent cut, as follows.

######  Definition 2.1 (Consistent cut).

A consistent cut of a run is any global state such that if
$e^{x}_{i}\rightarrow e^{y}_{j}$ and $e^{y}_{j}$ is in the global state, then
$e^{x}_{i}$ is also in the global state.

A message chain of an asynchronous run is a sequence of messages $m_{1}$,
$m_{2}$, $m_{3}$, $\dots$, such that, for all $i$, $receive(m_{i})$
$\rightarrow$ $send(m_{i+1})$. Consequently, $send(m_{1})$ $\rightarrow$
$receive(m_{1})$ $\rightarrow$ $send(m_{2})$ $\rightarrow$ $receive(m_{2})$
$\rightarrow$ $send(m_{3})$ $\dots$.

##  3 Lachesis: Proof-Of-Stake DAG-based Protocol

This section presents the key concepts of our new PoS+DAG consensus protocol,
namely Lachesis.

In BFT systems, a synchronous approach utilizes a broadcast voting and asks
each node to vote on the validity of each block. Instead, we aim for an
asynchronous system where we leverage the concepts of distributed common
knowledge and network broadcast to achieve a local view with high probability
of being a consistent global view.

Each node in Lachesis protocol receives transactions from clients and then
batches them into an event block. The new event block is then communicated
with other nodes through asynchronous event transmission. During
communication, nodes share their own blocks as well as the ones they received
from other nodes. Consequently, this spreads all information through the
network. The process is asynchronous and thus it can increase throughput near
linearly as nodes enter the network.

###  3.1 OPERA DAG

In Lachesis protocol, each (participant) node, which is a server (machine) of
the distributed system, can create messages, send messages to and receive
messages from other nodes. The communication between nodes is asynchronous.
Each node stores a local block DAG, so-called OPERA DAG, which is Directed
Acyclic Graph (DAG) of event blocks. A block has some edges to its parent
event blocks. A node can create an event block after the node communicates the
current status of its OPERA DAG with its peers.

_[OPERA DAG]_ The OPERA DAG is a graph structure stored on each node. The
OPERA DAG consists of event blocks and references between them as edges.

OPERA DAG is a DAG graph $G$=($V$,$E$) consisting of $V$ vertices and $E$
edges. Each vertex $v_{i}\in V$ is an event block. An edge ($v_{i}$,$v_{j}$)
$\in E$ refers to a hashing reference from $v_{i}$ to $v_{j}$; that is,
$v_{i}\hookrightarrow v_{j}$. We extend with $G$=($V$,$E$,$\top$,$\bot$),
where $\top$ is a pseudo vertex, called _top_ , which is the parent of all top
event blocks, and $\bot$ is a pseudo vertex, called bottom, which is the child
of all leaf event blocks. With the pseudo vertices, we have $\bot$ happened-
before all event blocks. Also all event blocks happened-before $\top$. That
is, for all event $v_{i}$, $\bot\rightarrow v_{i}$ and $v_{i}\rightarrow\top$.

Figure 2 shows an example of an OPERA DAG (DAG) constructed through the
Lachesis protocol. Event blocks are represented by circles.

Figure 2: An Example of OPERA DAG

The local DAG is updated quickly as each node creates and synchronizes events
with each other. For high speed transaction processing, we consider a model of
DAG as _DAG streams_. Event blocks are assumed to arrive at very high speed,
and they are asynchronous. Let $G$=($V$,$E$) be the current OPERA DAG and
$G^{\prime}$=($V^{\prime}$,$E^{\prime}$) denote the _diff graph_ , which
consists of the changes to $G$ at a time, either at event block creation or
arrival. The vertex sets $V$ and $V^{\prime}$ are disjoint; similar to the
edge sets $E$ and $E^{\prime}$. At each graph update, the updated OPERA DAG
becomes $G_{new}$=($V\cup V^{\prime}$, $E\cup E^{\prime}$).

Each node uses a local view of OPERA DAG to identify Root, Clotho and Atropos
vertices, and to determine topological ordering of the event blocks.

###  3.2 PoS Definitions

Inspired from the success of PoS [36, 18, 45, 4, 20, 8], we introduce a
general model of StakeDag protocols that are Proof of Stake DAG-based for
trustless systems [33]. In this general model, the stakes of the participants
are paramount to a trust indicator.

A stake-based consensus protocol consists of nodes that vary in their amount
of stake. Based on our generic Lachesis protocol, any participant can join the
network. Participants can increase their impact as well as their contributions
over the Fantom network by increasing the stake amount (FTM tokens) they
possess. Validating power is based on the amount of FTM tokens a node
possesses. The validating power is used for online validation of new event
blocks to maintain the validity of blocks and the underlying DAG.

####  3.2.1 Stake

Each participant node of the system has an account. The _stake_ of a
participant is defined based on their account balance. Account balance is the
number of tokens that was purchased, accumulated and/or delegated from other
account. Each participant has an amount of stake $w_{i}$, which is a non-
negative integer.

Each participant with a positive balance can join as part of the system. A
user has a stake of 1, whereas a validator has a stake of $w_{i}>1$. The
number of stakes is the number of tokens that they can prove that they
possess. In our model, a participant, whose has a zero balance, cannot
participate in the network, either for block creation nor block validation.

####  3.2.2 Validating Power and Block Validation

In the base Lachesis protocol, every node can submit new transactions, which
are batched in a new event block, and it can communicate its new (own) event
blocks with peers. Blocks are then validated by all nodes, which have the same
validating power.

Here, we present a general model that distinguishes Lachesis participants by
their validating power. In this model, every node $n_{i}$ in Lachesis has a
stake value of $w_{i}$. This value is then used to determine their validating
power to validate event blocks.

The base Lachesis protocol contains only nodes of the same weights; hence, it
is equivalent to say that all nodes have a unit weight ($w_{i}$=1). In
contrast, the full version of Lachesis protocol is more general in which nodes
can have different validating power $w_{i}$.

In order to reach asynchronous DAG-based consensus, validators in Lachesis
protocol are required to create event block (with or without transactions) to
indicate that which block (and all of its ancestors) they have validated.

####  3.2.3 Stake-based Validation

In Lachesis, a node must validate its current block and the received ones
before it attempts to create (or add) a new event block into its local DAG. A
node must validate its (own) new event block before it communicates the new
block to other nodes.

A root is an important block that is used to compute the final consensus of
the event blocks of the DAG. Lachesis protocol take the stakes of participants
into account to compute the consensus of blocks. The weight of a block is the
sum of the validating power of the nodes whose roots can be reached from the
block.

####  3.2.4 Validation Score

The _validation score_ of a block is the total of all validating powers that
the block has gained. The validation score of a block $v_{i}$ $\in$ $G$ is
denoted by $s(v_{i})$. If the validation score of a block is greater than 2/3
of the total validating power, the block becomes a root. The weight of a root
$r_{i}$ is denoted by $w(r_{i})$, which is the weight $w_{j}$ of the creator
node $j$ of the $r_{i}$. When an event block becomes a root, its score is the
validating power of the root’s creator.

###  3.3 S-OPERA DAG: A weighted DAG model

Like StakeDag protocol, Lachesis protocol uses a DAG-based structure, namely
_S-OPERA DAG_ , which is a weighted DAG $G$=($V$,$E$, $w$), where $V$ is the
set of event blocks, $E$ is the set of edges between the event blocks, and $w$
is a weight mapping to associates a vertex $v_{i}$ with its weight $w(v_{i})$.
Each vertex (or event block) is associated with a weight (validation score).
Event block has a validating score, which is the total weights of the roots
reachable from it. A root vertex has a _weight_ equal to the validating power
of the root’s creator node.

Figure 3: An example of an S-OPERA DAG in Lachesis. The validation scores of
some selected blocks are shown.

Figure 3 depicts an S-OPERA DAG obtained from the DAG. In this example,
validators have validating power of 2, while users have validating power of 1.
Blocks created by validators are highlighted in red color. First few event
blocks are marked with their validating power. Leaf event blocks are special
as each of them has a validation score equal to their creator’s validating
power.

_[S-OPERA DAG]_ In Lachesis, a S-OPERA DAG is weighted DAG stored on each
node.

Let $\mathcal{W}$ be the total validating power of all nodes. For consensus,
the algorithm examines whether an event block has a validation score of at
least a quorum of $2\mathcal{W}/3$, which means the event block has been
validated by more than two-thirds of total validating power in the S-OPERA
DAG.

###  3.4 Overall Framework

Figure 4: A General Framework of StakeDag Protocol

Figure 4 shows a general framework of Lachesis protocol. Each node contains a
DAG consisting of event blocks. In each node, the information of accounts and
their stakes are stored. The main steps in a PoS DAG-based consensus protocol
include (a) block creation, (b) computing validation score, (c) selecting
roots and updating the root sets, (d) assigning weights to new roots, (e)
decide frames, (f) decide Clothos/Atropos, and (f) order the final blocks.

###  3.5 Quorum

To become a root, an event block requires more than 2/3 of validating power
(i.e., 2W/3) rather than 2n/3 in unweighted version of Lachesis. For
simplicity, we denote quorum $Q$ to be $2W/3+1$ for weighted DAG. In the
original unweighted version, quorum $Q$ is $2n/3+1$ for unweighted DAG.

###  3.6 Event Block Creation

Each event block has at most $k$ references to other event blocks using their
hash values. One of the references must be a self-ref (or self-parent) that
references to an event block of the same node. The other references, which are
also known as other-parent or other-ref references, are the top event blocks
of other nodes.

Prior to creating a new event block, the node will first validate its current
block and the selected top event block(s) from other node(s). With
cryptographic hashing, an event block can only be created or added if the
self-ref and other-ref event blocks exist.

Nodes with a higher stake value $w_{i}$ have a higher chance to create a new
event block than other nodes with a lower stake.

###  3.7 Event Block Structure

An event (or an event block) is a vertex in the DAG, which stores the
structure of consensus messages. Each event has a number of links to past
events (parents). The links are the graph edges. Sometimes, ”event” and ”event
block” can be used interchangeably, but they are different from ”block”, which
means a finalized block in the blockchain.

Each event is a signed consensus message by a validator sent to the network,
which guarantees the following that: ”The creator of this event has observed
and validated the past events (and their parents), including the parents of
this event. The event’s creator has already validated the transactions list
contained in this event.”

The structure of an event block in Lachesis is as follows:

  * •

event.Epoch: epoch number (see epoch). Not less than 1.

  * •

event.Seq: sequence number. Equal to self-parent’s seq + 1, if no self-parent,
then 1.

  * •

event.Frame: frame number (see consensus). Not less than 1.

  * •

event.Creator: ID of validator which created event.

  * •

event.PrevEpochHash: hash of finalized state of previous epoch.

  * •

event.Parents: list of parents (graph edges). May be empty. If Seq ¿ 1, then
first element is self-parent.

  * •

event.GasPowerLeft: amount of not spent validator’s gas power for each gas
power window, after connection of this event.

  * •

event.GasPowerUsed: amount of spent validator’s gas power in this event.

  * •

event.Lamport: Lamport timestamp. If parents list is not empty, then Lamport
timestamp of an event v, denoted by LS(v) is maxLS(u) — u is a parent of v +
1. Otherwise, LS(v) is 1

  * •

event.CreationTime: a UnixNano timestamp that is specified by the creator of
event. Cannot be lower than creation time of self-parent (if self-parent
exists). Can be too-far-in-future, or too-far-in-past.

  * •

event.MedianTime: a UnixNano timestamp, which is a weighted median of highest
observed events (their CreationTime) from each validator. Events from the
cheater validators are not counted. This timestamp is used to protect against
”too-far-in-future” and ”too-far-in-past”.

  * •

event.TxHash: Merkle tree root of event transactions.

  * •

event.Transactions: list of originated transactions.

  * •

event.Sig: ECDSA256 secp256k1 validator’s signature in the R/S format (64
bytes).

Each event has two timestamps. Event’s creationTime is the created timestamp
an assigned by the creator of event block. Event’s MedianTime is a weighted
median of highest observed events (their CreationTime) from each validator.
Events from the cheater validators aren’t counted.

###  3.8 Root Selection

Root events get consensus when 2/3 validating power is reached. When a new
root is found, ’Assign weight’ step will assign a weight to the root. The
root’s weight is set to be equal to the validating power $w_{i}$ of its
creator. The validation score of a root is unchanged. Figure 4 depicts the
process of selecting a new root in Lachesis. A node can create a new event
block or receive a new block from other nodes.

To guarantee that root can be selected correctly even in case a fork exists in
the DAG, we introduce $forklessCause$ concept. The relation
$forklessCause(A,B)$ denote that event $x$ is forkless caused by event $y$. It
means, in the subgraph of event $x$, $x$ does not observe any forks from $y$’s
creator and at least QUORUM non-cheater validators have observed event $y$.

An event is called a root, if it is _forkless causes_ by QUORUM roots of
previous frame. The root starts a new frame. For every event, its frame number
is no smaller than self-parent’s frame number. The lowest possible frame
number is 1. Relation $forklessCause$ is a stricter version of happened-before
relation, i.e. if $y$ forkless causes $x$, then $y$ is happened before A. Yet,
unlike happened-before relation, forklessCause is not transitive because it
returns false if fork is observed. So if $x$ forkless causes $y$, and $y$
forkless causes $z$, it does not mean that $x$ forkless causes $z$. If there’s
no forks in the graph, then the forklessCause is always transitive.

###  3.9 Clotho Selection

Next, we present our algorithm to select Clotho from roots. A Clotho is a root
that is known by more than a quorum $Q$ of nodes, and there is another root
that knows this information. In order for a root $r_{i}$ in frame $f_{i}$ to
become a Clotho, $r_{i}$ must be reach by some root $r_{i+3}$ in frame
$f_{i+3}$. This condition ensures an equivalence to a proof of practical BFT.

Algorithm 1 Clotho Selection

1:procedure DecideClotho

2: for $x$ range roots: lastDecidedFrame + 1 to $up$ do

3: for $y$ range roots: $x.frame$ \+ 1 to $up$ do

4: // y is a root which votes, x is a voting subject root

5: round $\leftarrow$ y.frame - x.frame

6: if round == 1 then

7: // y votes positively if x forkless causes y

8: y.vote[x] $\leftarrow$ forklessCause(x, y)

9: else

10: prevVoters $\leftarrow$ getRoots(y.frame-1) // contains at least QUORUM
events, from definition of root

11: yesVotes $\leftarrow$ 0

12: noVotes $\leftarrow$ 0

13: for prevRoot range prevRoots do

14: if forklessCause(prevRoot, y) == TRUE then

15: // count number of positive and negative votes for x from roots which
forkless cause y

16: if prevRoot.vote[x] == TRUE then

17: yesVotes $\leftarrow$ yesVotes + prevVoter’s STAKE

18: else

19: noVotes $\leftarrow$ noVotes + prevVoter’s STAKE // y votes likes a
majority of roots from previous frame which forkless cause y

20: y.vote[x] $\leftarrow$ (yesVotes - noVotes) $>=$ 0

21: if yesVotes $>=$ QUORUM then

22: x.candidate $\leftarrow$ TRUE // decided as a candidate for Atropos

23: decidedRoots[x.validator] $\leftarrow$ x

24: break

25: if noVotes $>=$ QUORUM then

26: x.candidate $\leftarrow$ FALSE // decided as a non-candidate for Atropos

27: decidedRoots[x.validator] $\leftarrow$ x

28: break

Algorithm 1 shows a pseudo code to select Clothos from the current set of
roots. For every root $x$ from last decided frame + 1, it then loops for every
root $y$ from $x$.frame + 1, and executes the inner loop body. Coloring of the
graph is performed such that each root is assigned with one of the colors: IS-
CLOTHO (decided as candidate for Clotho), IS-NOT-CLOTHO (decided as not a
candidate for Clotho), or a temporary state UNDECIDED (not decided). Once a
root is assigned a color by a node, the same color is assigned to the root by
all other honest nodes, unless more than 1/3W are Byzantine. This is the core
property of Lachesis consensus algorithm.

  * •

If a root has received $w$ $\geq$ QUORUM votes for a color, then for any other
root on next frame, its prevRoots (contains at least QUORUM events, from
definition of root) will overlap with V, and resulting overlapping will
contain more than 1/2 of the prevVoters. It iscrucial that QUORUM is $2/3W+1$,
not just 2/3W. The condition implies that ALL the roots on next frame will
vote for the same color unanimously.

  * •

A malicious validator may have multiple roots on the same frame, as they may
make some forks. The forklessCause relation and the condition that no more
than $1/3W$ are Byzantine will guarantee that no more than one of these roots
may be voted YES. The algorithm assigns a color only in round $>=$ 2, so
prevRoots will be ”filtered” by forklessCause relation, to prevent deciding
differently due to forks.

  * •

If a root has received at least one YES vote, then the root is guaranteed to
be included in the graph.

  * •

A root event $x$ from an offline validator will be decided NO by all. Thus,
$x$ is considered as non-existent event and cannot be assigned IS-CLOTHO
color, and hence it cannot become Atropos.

  * •

Technically, the election may take many rounds. Practically, however, the
election ends mostly in 2nd or 3rd round.

Unlike HashGraph’s decideFame function in page 13 [2], our Lachesis algorithm
has no coin round and is completely deterministic.

A Clotho is an Atropos candidate that has not been assigned a timestamp.

###  3.10 Atropos Selection

From the array of roots that are decided as candidate, there are several ways
to sort these Atropos candidates. Atropos candidates can be sorted based on
the Lamport timestamp, layering information, validator’s stake, validator’s
id, and the Atropos’s id (see our ONLAY paper [31]).

Here, we present an algorithm that sorts these Atropos candidates using
validator’s stake and validator’s id. Algorithm 2 shows the pseudo code for
Atropos selection. The algorithm sorts the decided roots based on their
validator’s information. Validators are sorted based on their stake amount
first, and then by their Id. The algorithms requires a sorted list of
validators. The sorting is $O(n.log(n))$, where $n$ is the number of roots to
process.

Algorithm 2 Atropos Selection

1:function DecideAtropos

2: for validator: range sorted validators do

3: root = decidedRoots[validator]

4: if root == NULL then // not decided

5: return nil // frame isn’t decided yet

6: if root.candidate == TRUE then

7: return root // found Atropos

8: if root.candidate == FALSE then

9: continue

Nodes in Lachesis reach consensus about Atropos selection and Atropos
timestamp without additional communication (i.e., exchanging candidate time)
with each other. Through the Lachesis protocol, the OPERA DAGs of all nodes
are “consistent“. This allows each node to know the candidate time of other
nodes based on its OPERA DAG and reach a consensus agreement. Our proof is
shown in Section 8.2.

Atropos event block, once decided, is final and non-modifiable. All event
blocks can be in the subgraph of an Atropos guarantee finality.

###  3.11 Atropos timestamp

Validators are sorted by their stake amount and then by their ID. For roots
from different validators, they are sorted based on the ordering of their
validators. Atropos is chosen as a first candidate root in the sorted order.
Notice that, an Atropos may be decided even though not all the roots on a
frame are decided. Our Lachesis algorithm allows to decide frames much earlier
when there’s a lot of validators, and hence reduce TTF (time to finality).

###  3.12 Main chain

The _Main-chain_ is an append-only list of blocks that caches the final
consensus ordering of the finalized Atropos blocks. The local hashing chain is
useful to improve path search to quickly determine the closest root to an
event block. Each participant has an own copy of the Main chain and can search
consensus position of its own event blocks from the nearest Atropos. The chain
provides quick access to the previous transaction history to efficiently
process new coming event blocks. After a new Atropos is determined, a
topological ordering is computed over all event blocks which are yet ordered.
After the topological ordering is computed over all event block, Atropos
blocks are determined and form the Main chain.

###  3.13 Topological ordering of events

Every node has a physical clock, and each event block is assigned with a
physical time (creation time) from the event’s creator. Each event block is
also assigned a Lamport timestamp. For consensus, Lachesis protocol relies on
a logical clock (Lamport timestamp) for each node.

We use Lamport timestamp [21] to determine the time ordering between event
blocks in a asynchronous distributed system. The Lamport timestamps algorithm
is as follows: (1) Each node increments its count value before creating an
event block; (2) When sending a message, sender includes its count value.
Receiver should consider the count sent in sender’s message is received and
increments its count value, (3) If current counter is less than or equal to
the received count value from another node, then the count value of the
recipient is updated; (4) If current counter is greater than the received
count value from another node, then the current count value is updated.

###  3.14 Blocks

Next, we present our approach to ordering event blocks under Atropos event
block that reaches finality.

Once a new Atropos is decided, a new block will be created. The new block
contains all the events in the Atropos’s subgraph; it only includes events,
which were yet included in the subgraphs of any previous Atroposes. The events
in the new block are ordered by Lamport time, then by event’s hash. Ordering
by Lamport time ensures that parents are ordered before their children. Our
approach gives a deterministic final ordering of the events in the block.

Figure 5 illustrates the steps to make blocks from decided Atroposes. In the
example, Clotho/Atropos vertices are colored red. For each Atropos vertex, we
compute the subgraph under it. Atropos vertices can be selected by using of
several criteria (see ONLAY paper [31]). Subgraphs under Atropos vertices are
shown in different colors. Atropos event blocks are processed in the order
from lower layer to high layer.

Figure 5: Peeling the subgraphs in topological sorting order

We present an algorithm for topological ordering of Atropos event blocks
(introduced in our ONLAY paper [31]). Algorithm 3 first orders the Atropos
candidates using SortByLayer function, which sorts vertices based on their
layer, Lamport timestamp and then hash information of the event blocks.
Second, we process every Atropos in the sorted order, and then compute the
subgraph $G[a]=(V_{a},E_{a})$ under each Atropos. The set of vertices $V_{u}$
contains vertices from $V_{a}$ that are not yet processed in $U$. We then
apply $SorByLayer$ to order vertices in $V_{u}$ and then append the ordered
result into the final ordered list $S$.

Algorithm 3 TopoSort

1:Require: OPERA DAG $H$, $\phi$, $\phi_{F}$.

2:function TopoSort($A$)

3: $S\leftarrow$ empty list

4: $U\leftarrow\emptyset$

5: $Q\leftarrow$ SortByLayer($A$)

6: for Atropos $a\in Q$ do

7: Compute subgraph $G[a]=(V_{a},E_{a})$

8: $V_{u}\leftarrow V_{a}\setminus U$

9: $T$ $\leftarrow$ SortByLayer($V_{u}$)

10: Append $T$ into the end of ordered list $S$.

11:function SortByLayer(V)

12: Sort the vertices in $V_{u}$ by layer, Lamport timestamp and hash in that
order.

With the final ordering computed by using above algorithms, we can assign the
consensus time to the finally ordered event blocks.

Then the Atropos is assigned a timestamp from the event.MedianTimestamp, which
is computed as a median of the event’s timestamps sent by all the nodes. The
median time is used to guarantee aBFT for the consensus time for the Atropos
to avoid incorrect time from malicious nodes. Once Atropos consensus time is
assigned, the Clotho becomes an Atropos and each node stores the hash value of
Atropos and Atropos consensus time in Main-Chain. The Main-chain is used for
time order between event blocks.

###  3.15 Block timestamp

In Lachesis, block timestamp is assigned using Atropos’s median time.

###  3.16 Peer selection

In Lachesis protocol, we use a model in which each node only stores a subset
of $n$ peers. To create a new event block, a node first synchronizes the
latest blocks from other peers and then it selects the top blocks of at most
$k$ peers. Lachesis protocol does not depend on how peer nodes are selected.

There are multiple ways to select $k$ peers from the set of $n$ nodes. An
simple approach can use random selection from the pool of $n$ nodes. In ONLAY
[31], we have tried a few peer selection algorithms as follows:

  * •

Random: randomly select a peer from $n$ peers;

  * •

Least Used: select the least use peer(s).

  * •

Most Used (MFU): select the most use peer(s).

  * •

Fair: select a peer that aims for a balanced distribution.

  * •

Smart: select a peer based on some other criteria, such as successful
throughput rates, number of own events.

Stake-based Peer Selection: We also propose new peer selection algorithms,
which utilize stakes to select the next peer. Each node has a mapping of the
peer $i$ and the frequency $f_{i}$ showing how many times that peer was
selected. New selection algorithms define some function $\alpha_{i}$ that take
user stake $w_{i}$ and frequency $f_{i}$ into account. We give a few examples
of the new algorithms, described as follows:

  * •

Stake-based: select a random peer from $n$ peers with a probability
proportional to their stakes $w_{i}$.

  * •

Lowest: select the peer with the lowest value of $\alpha_{i}$.

  * •

Highest: select the peer with the highest value of $\alpha_{i}$.

  * •

Balanced: aim for a balanced distribution of selected peers of a node, based
on the values $\alpha_{i}$.

There are other possible criteria can be used a peer selection algorithm, such
as successful validation rates, total rewards, etc. A more complex approach is
to define a cost model for the node selection, such as low communication cost,
low network latency, high bandwidth and high successful transaction
throughput. In Lachesis, available gas and origination power are used.

###  3.17 Dynamic participants

Unlike some existing DAG-based approaches [2], our Lachesis protocol allows an
arbitrary number of participants to dynamically join the system.

OPERA DAG can still operate with new participants. Algorithms for selection of
Roots, Clothos and Atroposes are flexible enough and not dependent on a fixed
number of participants.

###  3.18 Peer synchronization

Algorithm 4 shows a pseudo code to synchronize events between the nodes.

Algorithm 4 EventSync

1:procedure sync-events()

2: Node $n_{1}$ selects random peer to synchronize with

3: $n_{1}$ gets local known events

4: $n_{1}$ sends RPC sync request to peer

5: $n_{2}$ receives RPC sync request

6: $n_{2}$ does an graph-diff check on the known map

7: $n_{2}$ returns unknown events, and mapping of known events to $n_{1}$

The algorithm assumes that a node always needs the events in topological
ordering (specifically in reference to the Lamport timestamps), an alternative
would be to use an inverse bloom lookup table (IBLT) for completely potential
randomized events. Alternatively, one can simply use a fixed incrementing
index to keep track of the top event for each node.

In Lachesis, when a node receives a coming (new) event block from a peer, it
will perform several checks to make sure the event block has been signed by an
authorized peer, conforms to data integrity, and has all parent blocks already
added in the node’s local DAG.

###  3.19 Detecting Forks

_[Fork]_ A pair of events ($v_{x}$, $v_{y}$) is a fork if $v_{x}$ and $v_{y}$
have the same creator, but neither is a self-ancestor of the other. Denoted by
$v_{x}\pitchfork v_{y}$.

For example, let $v_{z}$ be an event in node $n_{1}$ and two child events
$v_{x}$ and $v_{y}$ of $v_{z}$. if $v_{x}\hookrightarrow^{s}v_{z}$,
$v_{y}\hookrightarrow^{s}v_{z}$, $v_{x}\not\hookrightarrow^{s}v_{y}$,
$v_{y}\not\hookrightarrow^{s}v_{z}$, then ($v_{x}$, $v_{y}$) is a fork. The
fork relation is symmetric; that is $v_{x}\pitchfork v_{y}$ iff
$v_{y}\pitchfork v_{x}$.

By definition, ($v_{x}$, $v_{y}$) is a fork if $cr(v_{x})=cr(v_{y})$,
$v_{x}\not\hookrightarrow^{a}v_{y}$ and $v_{y}\not\hookrightarrow^{a}v_{x}$.
Using Happened-Before, the second part means $v_{x}\not\rightarrow v_{y}$ and
$v_{y}\not\rightarrow v_{x}$. By definition of concurrent, we get
$v_{x}\parallel v_{y}$.

######  Lemma 3.1.

If there is a fork $v_{x}\pitchfork v_{y}$, then $v_{x}$ and $v_{y}$ cannot
both be roots on honest nodes.

Here, we show a proof by contradiction. Any honest node cannot accept a fork
so $v_{x}$ and $v_{y}$ cannot be roots on the same honest node. Now we prove a
more general case. Suppose that both $v_{x}$ is a root of $n_{x}$ and $v_{y}$
is root of $n_{y}$, where $n_{x}$ and $n_{y}$ are honest nodes. Since $v_{x}$
is a root, it reached events created by nodes having more than $2W/3$.
Similarly, $v_{y}$ is a root, it reached events created by nodes of more than
$2W/3$. Thus, there must be an overlap of more than $W$/3. Since we assume
less than $W$/3 are from malicious nodes, so there must be at least one honest
member in the overlap set. Let $n_{m}$ be such an honest member. Because
$n_{m}$ is honest, $n_{m}$ does not allow the fork.

###  3.20 Transaction confirmations

Here are some steps for a transaction to reach finality in our system.

  * •

First, when user submits a transaction into a node, a successful submission
receipt will be issued to the client as a confirmation of the submitted
transaction.

  * •

Second, the node will batch the submitted transaction(s) into a new event
block, and add it into its OPERA DAG. Then will broadcast the event block to
all other nodes of the system. Peer nodes will update its own record
confirming that the containing event block identifier is being processed.

  * •

Third, when the event block is known by majority of the nodes (e.g., it
becomes a Root event block), or being known by such a Root block, new status
of the event block is updated.

  * •

Fourth, our system will determine the condition at which a Root event block
becomes a Clotho for being further acknowledged by a majority of the nodes. A
confirmation is then sent to the client to indicate that the event block has
come to the semi-final stage as a Clotho or being confirmed by a Clotho. After
the Clotho stage, we will determine the consensus timestamp for the Clotho and
its dependent event blocks.

  * •

Once an event block gets the final consensus timestamp, it is finalized and a
final confirmation will be issued to the client that the transaction has been
successfully finalized.

The above five steps are done automatically by ONLAY. Steps (2), (3) and (4)
are internal steps. Steps (1) and (5) are visible to the end users. Currently,
the whole process will take 1-2 seconds from transaction submission to
transaction confirmation (through the five steps). Once a block is confirmed,
it will be assigned with a block id in the blockchain and that confirmation is
final.

There are some cases that a submitted transaction can fail to reach finality.
Examples include a transaction does not pass the validation, e.g.,
insufficient account balance, or violation of account rules. The other kind of
failure is when the integrity of DAG structure and event blocks is not
complied due to the existence of compromised or faulty nodes. In such
unsuccessful cases, the event block’s status is updated accordingly. Clients
can always query the latest transaction status regardless of its success or
failure.

###  3.21 Checkpoint

STAIR uses the following procedure, which is similar to the Casper model [46].
Our approach can be summarized as follows:

  1. 1.

We can divide into checkpoints, each will take every 100th (some configurable
number) frame.

  2. 2.

Stakeholders can choose to make more deposits at each check point, if they
want to become validators and earn more rewards. Validators can choose to
exit, but cannot withdraw their deposits until three months later.

  3. 3.

A checkpoint is selected based on a consistent global history that is
finalized with more than 2/3 of the validating power for the checkpoint. When
a checkpoint is finalized, the transactions will not be reverted.

  4. 4.

With asynchronous system model, validators are incentivized to coordinate with
each other on which checkpoints the history should be updated. Nodes gossip
their latest local views to synchronize frames and accounts. Attackers may
attempt double voting to target double spending attacks. Honest validators are
incentivized to report such behaviors and burn the deposits of the attackers.

Each frame in Lachesis is about 0.3-0.6s, and blocks are confirmed in 0.7-1.5s
depending on the number of transactions put into the system. To have more
deterministic checkpoints, we divide into epochs, each of which lasts around 4
hours.

##  4 Staking model

This section presents our staking model for Opera network. We first give
general definitions and variables of our staking model, and then present the
model in details.

####  4.0.1 Definitions and Variables

Below are the general definitions and variables that are used in Opera
network.

General definitions

$\mathcal{F}$ |  denotes the network itself
---|---
$SFC$ |  ”Special Fee Contract” – managing the collection of transaction fees and the payment of all rewards
$FTM$ |  main network token

Accounts

$\mathbb{U}$ |  |  set of all participant accounts in the network
---|---|---
$\mathbb{A}$ |  $\subset\mathbb{U}$ |  accounts with a positive FTM token balance
$\mathbb{S}$ |  $\subseteq\mathbb{A}$ |  accounts that have staked for validation (some of which may not actually be validating nodes)
$\mathbb{V}$ |  $\subseteq\mathbb{S}$ |  validating accounts, corresponding to the set of the network’s validating nodes

A participant with an account having a positive FTM token balance, say
$i\in\mathbb{A}$, can join the network (as a delegator or a validator). But an
account $i$ in $\mathbb{S}$ may not participate in the protocol yet. Those who
join the network belong to the set $\mathbb{V}$.

_[Validating account]_ A validating account has more than $U$ tokens.

Network parameters subject to on-chain governance decisions

$F$ |  $3.175e9$ |  total supply of FTM tokens
---|---|---
$\lambda$ |  $7$ |  period in days after which validator staking must be renewed, to ensure activity
$\varepsilon$ |  1 |  minimum number of tokens that can be staked by an account for any purpose
$\phi$ |  30% |  SPV commission on transaction fees
$\mu$ |  15% |  validator commission on delegated tokens

Tokens held and staked

Unless otherwise specified, any mention of tokens refers to FTM tokens.

_[Token helding]_ The token helding $t_{i}$ of an account is number of FTM
tokens held by account $i\in\mathbb{A}$.

$t_{i}$ |  |  number of FTM tokens held by account $i\in\mathbb{A}$
---|---|---
$t_{i}^{[x]}$ |  $>\varepsilon$ |  transaction-staked tokens by account $i$
$t_{i}^{[d]}(s)$ |  $>\varepsilon$ |  tokens delegated by account $i$ to account $s\in\mathbb{S}$
$t^{[d]}(s)$ |  |  total of tokens delegated to account $s\in\mathbb{S}$
$t_{i}^{[d]}$ |  |  total of tokens delegated by account $i$ to accounts in $\mathbb{S}$
$t_{i}^{[s]}$ |  |  validation-staked tokens by account $i$

The sum of tokens staked or delegated by an account $i\in\mathbb{A}$ cannot
exceed the amount of tokens held:
$t_{i}^{[x]}+t_{i}^{[s]}+\sum_{s\in\mathbb{S}}t_{i}^{[d]}(s)\leq t_{i}$. The
total amount of tokens delegated to an account $s\in\mathbb{S}$ is:
$t^{[d]}(s)=\sum_{i\in\mathbb{A}}t_{i}^{[d]}(s)$. The total amount of tokens
delegated by an account $i\in\mathbb{A}$ is:
$t_{i}^{[d]}=\sum_{s\in\mathbb{S}}t_{i}^{[d]}(s)$.

####  4.0.2 Validating power

We use a simple model of validating power, which is defined as the number of
tokens held by an account. The weight of an account $i\in\mathbb{A}$ is equal
to its token holding $t_{i}$.

####  4.0.3 Block consensus and Rewards

_[Validation score]_ Validation score of a block is the total validating power
that a given block can achieve from the validators $v\in\mathbb{V}$.

_[Quorum]_ Validating threshold is defined by $2/3$ of the validating power
that is needed to confirm an event block to reach consensus.

Below are the variables that define the block rewards and their contributions
for participants in Fantom network.

$Z$ |  996,341,176 |  total available block rewards of $FTM$, for distribution by the $SPV$ during the first 1460 days after mainnet launch
---|---|---
$F_{s}$ |  |  $FTM$ tokens held by the $SPV$
$F_{c}$ |  $F-F_{s}$ |  total circulating supply

Block rewards will be distributed over each epoch.

####  4.0.4 Token Staking and Delegation

Participants can chose to stake or delegate their FTM tokens. When staking or
delegating, the validating power of a node is based on the number of FTM
tokens held. Three possible ways to stake are given as follows.

_[Transaction staking]_ Participants can gain more stakes or tokens via the
transaction staking. Transaction submitter can gain reward from the
transaction fees of submitted transactions. This style of staking helps
increases transaction volume on the network. The more liquidity, the more
transaction staking they can gain.

_[Validation staking]_ By validating blocks, a participant can gain validation
rewards. Honest participants can gain block rewards for successfully validated
blocks.

Participants can achieve block rewards for blocks that they co-validated and
gain transaction fees from transaction submitter for the successfully
finalized transactions. The more stake they gain, the more validating power
they will have and thus the more rewards they can receive as it is
proportional to their validating power.

_[Validation delegation]_ Validation delegation allows a participant to
delegate all or part of their tokens to another participant(s). Delegating
participants can gain a share of block rewards and transaction fees, based on
the amount of delegated stake.

Delegators can delegate their stake into a validator or into multiple
validators. Participants with large amount of stake can delegate their stakes
into multiple validators. Delegators earn rewards from their delegations.
Validators will not be able to spend delegated tokens, which will remain
secured in the stakeholder’s own address. Validators will receive a fixed
proportion of the validator fees attributable to delegators.

_[Validation performance]_ Participants are rewarded for their staked or
delegated amount. Delegators will be incentivized to choose validator nodes
that have a high self-stake, i.e. are honest and high performing. Delegators
can delegate their tokens for a maximum period of days, after which they need
to re-delegate. The requirements to delegate are minimal:

  * •

Minimum number of tokens per delegation: 1

  * •

Minimum lock period: 1 day

  * •

Maximum lock period: 1 year

  * •

Maximum number of delegations made by a user: None

  * •

Maximum number of delegated tokens per validator: 15 times of the validator’s
tokens.

##  5 Opera Network

###  5.1 Network Architecture

Figure 6 depicts an overview of Opera network, as introduced in our STAIR
framework [32].

A Validator node consists of three components: state machine, consensus and
networking. A application can communicate to a node via CLI. Opera network
supports auditing by permitting participants to join in post-validation mode.
An observer (or Monitor) node consists of state machine, post validation
component and networking component.

Figure 6: An overview of Opera network

###  5.2 Nodes and Roles

For an asynchronous DAG-based system, Lachesis supports three types of
participants: users, validators and monitors.

Each validating node can create new event blocks. Generation of a new even
block indicates that the new block and all of its ancestors have been
validated by the creator node of that new event block.

Users have less than $U$ FTM tokens, where $U$ is a predefined threshold
value. The current threshold value, which is voted by the community is $U$ =
1,000,0000 FTMs. Each validator must have more than $U$ tokens. In Lachesis,
users can only delegate their stake to validator nodes. User nodes cannot run
as a validating node, which can create and validate event blocks.

Besides validating nodes, Opera network allows another type of participants —
observers, who can join the network, but do not act as validating nodes.
Observers are not required to have any stake to join the network and thus they
cannot generate nor perform online voting (online validation). But observers
can do post-validation. This is to encourage the community to join the checks-
and-balances of our public network.

###  5.3 Boot Node Service

A new node that joins Opera network for the first time will connect to one of
our boot nodes, which provides a discovery service to connect with other peers
in the network. Currently, there are five boot nodes in Opera network and the
boot nodes are distributed in different zones. Boot nodes serve RPC requests
from peers and help new nodes to discover peers in the network.

###  5.4 API Service

Since the first launch of Opera mainnet, the network has served lots of dApp
projects and users. We have scaled our infrastructure on EC2 AWS accordingly
to cope with a huge amount of requests.

There are currently about 30 servers used for RPC API. The RPC API load is
about 250,000 requests per second at peaks. Each server can serve about 9000
requests per second. They are run in 3 hives that are independently serviced
by their own balancing gateways and the gateways are switched by round robin
DNS setup in 60s roundtrip time. Also, we have additional 3 public RPC
endpoints for API calls that are use for backup service.

Our infrastructure include other servers to serve explorer and wallet service.
We also maintain a different set of servers for cross-chain integration.

Apart from the servers run by the Foundation, there are many more API servers
operated by our community members, who are active contributors to the Opera
network.

###  5.5 Mainnet

There are currently 46 validator nodes, 5 boot nodes and more than 50 servers
running API service. Our Mainnet has served more than 35 million transactions,
and have produced more than 12.8 million blocks. There are more than 300k
accounts.

###  5.6 Testnet

There are currently 7 validator nodes and 2 API nodes. The testnet has been
used by developers to test and deploy new smart contracts and to prepare for
new integration prior into launch it on our mainnet.

###  5.7 Implementation

We have implemented our Lachesis protocol in GoLang 1.15+. Our implementation
is available at https://github.com/Fantom-foundation/go-opera. Our previous
repository is available at https://github.com/Fantom-foundation/go-lachesis.

Opera network is fully EVM compatible and smart contracts can be deployed and
run on our Opera network. We implemented Lachesis on top of Geth
111https://github.com/ethereum/go-ethereum. We provide Web3 API calls support
through our API Service layer. Decentralized applications (dApps) can query
and send transactions into the network for execution. Documentation and guides
are available at https://docs.fantom.foundation/.

Figure 7 shows the overall architecture of a Lachesis node.

Figure 7: Architecture of a Lachesis node

Transaction Fee: Like many existing platforms, Opera network leverages
transaction fee, which is paramount to prevent transaction flooding. It will
cost attackers when they attempt to send a lot of spamming transactions to the
network.

Clients can send transactions to Opera network. Each transaction requires a
small amount of fee to compensate for the cost to execute the transaction on
Validator nodes. Transaction can range from simple account transfer, new smart
contract deployment or a complex smart contract call. Transaction fee is
proportional to the mount of op codes included in the transaction.

In Ethereum and few others, transaction fees are calculated in a separate gas
token rather than the native token of the network. Instead, Fantom’s Opera
network calculates transaction fees in native FTM. This design removes the
burden of acquiring two types of token for users and developers to be able to
use and run dApps on our Opera mainnet.

Transaction Pool: Transactions once submitted will be appended into a
transaction pool of a node. The transaction pool is a buffer to receive
incoming transactions sent from peers. Similar to Ethereum’s txpool
implementation, transactions are placed in a priority queue in which
transactions with higher gas will have more priority.

Each node then pulls transactions from the pool and batches them into new
event block. The number of new event blocks a node can create is proportional
to the validating power it has.

###  5.8 Performance and Statistics

For experiments and benchmarking, we set up a private testnet with 7 nodes on
EC2 AWS. Each node is running m2.medium instance, which is 2vCPU with 3.3 GHz
each, 4GB RAM and 200GB SSD storage. We also experimented using a local
machine with the following specs (CPU: AMD Ryzen 7 2700, Memory: 2x DDR4/16G
2.6 Ghz, SSD storage).

####  5.8.1 Normal emission rate and gas allocation

We ran experiments with the private testnet with 7 nodes. The experiment was
run using normal emission rate (200ms) and normal gas allocation rules. We ran
the local machine to sync with the testnet.

On the local machine, the maximum raw TPS is 11000, and maximum syncing TPS is
4000-10000 TPS. The total number of transactions executed is 14230, the total
of events emitted is 109, and there are 108 finalized blocks. The peak TPS for
P2P syncing on a local non-validator node (16 CPUs, SSD) is 3705.

Our results on a validator node show that the peak TPS for P2P syncing is
2760. Maximum syncing TPS is 3000-7000 on testnet server, whereas maximum
network TPS is 500 due to txpool bottleneck on testnet servers.

####  5.8.2 High latency nodes

We also ran an experiment where 1/3 of the nodes in the network were lagged.
Additional latency of 300-700ms was added into 3 validators, whereas normal
latency was used for others.

Test duration (seconds) | 485 | 793
---|---|---
Blocks finalized | 1239 | 605
Transactions executed | 24283 | 39606
Events emitted | 10930 | 5959
Average TTF (seconds) | 0.92 | 4.64
Average TPS | 50.06 | 49.94
Table 6: Statistics of with 3 nodes of high latency

Table 6 shows that the added latency into 3 nodes can increase TTF by 4-fold,
but TPS is slightly reduced.

####  5.8.3 Emission rates

We ran experiments in that each node will generate 1428 transactions per
second and thus the whole network of 7 test servers generated 10000
transactions per second. Each generated transaction has around 100 bytes, like
a simple FTM transfer. To benchmark the consensus, this experiment disabled
transaction execution, so it only counted the transaction creation, consensus
messages, and finalized transactions and blocks.

(a) tps

(b) ttf

Figure 8: TPS and TTF measures on a testnet with 7 nodes

Figure 8 shows the statistics of block TPS and block TTF when 10000
transactions are submitted into the network per second. We experimented with
different emission rates (100ms, 150ms and 200ms), which is the amount of time
each new event created per node. As depicted in the figure, when increase
emission rate from 100ms to 200ms, the tps increased and the average TTF also
increased.

##  6 Discussions

###  6.1 Comparison with Existing Approaches

Compared with existing PoS protocols [36, 18, 45, 4, 20, 8], our Lachesis
protocol is built on top of DAG and it is more deterministic and more secure.

Compared with existing DAG-based approaches [26, 41, 11, 2, 38, 42, 37, 27],
Lachesis algorithms are quite different. Among them, Hashgraph [2] is the
closest to ours. However, our Lachesis algorithm is quite different from
Hashgraph’s algorithm in many ways:

  * •

Lachesis algorithm for finding roots and Atropos is deterministic, whereas
Hashgraph uses coin round to decide ’famous’ event blocks.

  * •

Our Lachesis leverages the notion of Happened-before relation, Lamport
timestamp, and graph layering to reach consensus on the final ordering for
Atropos blocks.

  * •

Our algorithm to create blocks (i.e., finalized blocks of the blockchains) is
unique. New block is created for every newly decided Atropos, whereas
Hashgraph tends to process with multiple Famous event blocks at once.

  * •

The event blocks under Atropos are sorted based on Lamport timestamp and graph
layering information. On the contrary, Hashgraph uses a heuristics, so-called
_findOrder_ function described in their paper, to compute the ordering of
events as well as their timestamps.

  * •

Lachesis protocol is permissionless aBFT, whereas it is unclear if their
algorithm is truly BFT.

  * •

Fantom’s Opera network is a permissionless (public) network and our Lachesis
protocol has run successfully. In contrast, Hashgraph aims for a permissioned
network.

  * •

We give a detailed model of our Proof-of-Stake model in StakeDag and StairDag
framework [33, 32], whereas PoS is briefly mentioned in their Hashgraph paper
[2].

  * •

We also provide a formal semantics and proof for our Lachesis protocol using
common concurrent knowledge [34].

###  6.2 Protocol Fairness and Security

There has been extensive research in the protocol fairness and security
aspects of existing PoW and PoS blockchains (see surveys [40, 35]). Here, we
highlight the benefits of our proposed PoS+DAG approach.

####  6.2.1 Protocol Fairness

Regarding the fairness, PoW protocol is fair because a miner with $p_{i}$
fraction of the total computational power can win the reward and create a
block with the probability $p_{i}$. PoS protocol is fair given that an
individual node, who has $w_{i}$ fraction of the total stake or coins, can a
new block with $w_{i}$ probability. However, in PoS systems, initial holders
of coins tend to keep their coins in their balance in order to gain more
rewards.

Our Lachesis protocol is fair since every node has an equal chance to create
an event block. Nodes in Lachesis protocol can enter the network without an
expensive hardware like what is required in PoW. Further, any node in Lachesis
protocol can create a new event block with a stake-based probability, like the
block creation in other PoS blockchains.

Like a PoS blockchain system, it is a possible concern that the initial
holders of coins will not have an incentive to release their coins to third
parties, as the coin balance directly contributes to their wealth. Unlike
existing PoS protocols, each node in Lachesis protocol are required to
validate parent event blocks before ot can create a new block. Thus, the
economic rewards a node earns through event creation is, in fact, to
compensate for their contribution to the onchain validation of past event
blocks and it’s new event block.

Criterion | PoW | PoS | Lachesis
---|---|---|---
Block creation probability | $p_{i}/P$ | $w_{i}/W$ | $w_{i}/W$
Validation probability | $1/n$ | $w_{i}/W$ | $1/n$
Validation reward | $p_{i}/P$ | $w_{i}/W$ | $w_{i}/W$
Txn Reward | $p_{i}/P$ | $w_{i}/W$ | $w_{i}/W$
Performance reward | - | - | (+$1$ Saga point)
Table 7: Comparison of PoW, PoS and Lachesis protocol

Table 7 gives a comparison of PoW, PoS and Lachesis protocols. Let $p_{i}$
denote the computation power of a node and $P$ denote the total computation
power of the network. Let $w_{i}$ be the stake of a node and $W$ denote the
total stake of the whole network. Let $\alpha_{i}$ denote the number of Saga
points a node has been rewarded from successful validations of finalized
blocks.

Remarkably, our Lachesis protocol is more intuitive because our reward model
used in stake-based validation can lead to a more reliable and sustainable
network.

####  6.2.2 Security

Regarding security, Lachesis has less vulnerabilities than PoW, PoS and DPoS.
As for a guideline, Table 8 shows a comparison between existing PoW, PoS, DPoS
and our Lachesis protocol, with respect to the effects of the common types of
attack on previous protocols. Note that, existing PoS and DPos approaches have
addressed one or some of the known vulnerabilities in one way or the other. It
is beyond the scope of this paper to give details of such approaches.

Attack type | PoW | PoS | DPoS | Lachesis (PoS+DAG)
---|---|---|---|---
Selfish mining | ++ | - | - | -
Denial of service | ++ | + | + | +
Sybil attack | ++ | + | + | -
Precomputing attack | - | + | - | -
Short range attack (e.g., bribe) | - | + | - | -
Long range attack | - | + | + | -
Coin age accumulation attack | - | maybe | - | -
Bribe attack | + | ++ | + | -
Grinding attack | - | + | + | -
Nothing at stake attack | - | + | + | -
Sabotage | - | + | + | +
Double-Spending | - | + | + | -
Table 8: Comparison of Vulnerability Between PoW, PoS, DPoS and Lachesis
Protols

PoW-based systems are facing _selfish mining attack_ , in which an attacker
selectively reveals mined blocks in an attempt to waste computational
resources of honest miners.

Both PoW and PoS share some common vulnerabilities. _DoS attack_ and _Sybil
attack_ are shared vulnerabilities, but PoW are found more vulnerable. A DoS
attack disrupts the network by flooding the nodes. In a Sybil attack, the
attacker creates multiple fake nodes to disrupt the network. Another shared
vulnerable is _Bribe attack_. In bribing, the attacker performs a spending
transaction, and at the same time builds an alternative chain secretly, based
on the block prior to the one containing the transaction. After the
transaction gains the necessary number of confirmations, the attacker
publishes his/her chain as the new valid blockchain, and the transaction is
reversed. PoS is more vulnerable because a PoS Bribe attack costs 50x lower
than PoW Bribe attack.

PoS has encountered issues that were not present in PoW-based blockchains.
These issues are: (1) _Grinding attack:_ malicious nodes can play their bias
in the election process to gain more rewards or to double spend their money:
(2) _Nothing at stake attack:_ A malicious node can mine on an alternative
chain in PoS at no cost, whereas it would lose CPU time if working on an
alternative chain in PoW.

There are possible attacks that are only encountered in PoS. Both types of
attack can induce conflicting finalized checkpoints that will require offline
coordination by honest users.

_Double-Spending_ An attacker (a) acquires $2W/3$ of stakes; (b) submits a
transaction to spend some amount and then votes to finalize that includes the
transactions; (c) sends another transaction to double-spends; (d) gets caught
and his stakes are burned as honest validators have incentives to report such
a misbehavior. In another scenario, an attacker acquires (a) $W/3+\epsilon$ to
attempt for an attack and suppose Blue validators own $W/3-\epsilon/2$, and
Red validators own the rest $W/3-\epsilon/2$. The attacker can (b) vote for
the transaction with Blue validators, and then(c) vote for the conflicting
transaction with the Red validations. Then both transactions will be finalized
because they have $2W/3+\epsilon/2$ votes. Blue and Red validators may later
see the finalized checkpoint, approve the transaction, but only one of them
will get paid eventually.

_Sabotage (going offline)_ An attacker owning $W/3+\epsilon$ of the stakes can
appear offline by not voting and hence checkpoints and transactions cannot be
finalized. Users are expected to coordinate outside of the network to censor
the malicious validators.

Attack cost in PoS versus PoW It will cost more for an attack in PoS
blockchain due to the scarcity of the native token than in a PoW blockchain.
In order to gain more stake for an attack in PoS, it will cost a lot for an
outside attacker. S/he will need $2W/3$ (or $W/3$ for certain attacks) tokens,
where $W$ is the total number of tokens, regardless of the token price.
Acquiring more tokens will definitely increase its price, leading to a massive
cost. Another challenge is that all the tokens of a detected attempt will be
burned. In contrast, PoW has no mechanism nor enforcement to prevent an
attacker from reattempting another attack. An attacker may purchase or rent
the hash power again for his next attempts.

Like PoS, our Lachesis protocol can effectively prevent potential attacks as
attackers will need to acquire $2W/3$ tokens (or at least $W/3$ for certain
attacks) to influence the validation process. Any attempt that is detected by
peers will void the attacker’s deposit.

###  6.3 Response to Attacks

Like other decentralized blockchain technologies, Fantom platform may also
face potential attacks by attackers. Here, we present several possible attack
scenarios that are commonly studied in previous work, and we show how Lachesis
protocol can be used to prevent such attacks.

Transaction flooding: A malicious participant may run a large number of valid
transactions from their accounts with the purpose of overloading the network.
In order to prevent such attempts, our Fantom platform has applied a minimal
transaction fee, which is still reasonable for normal users, but will cost the
attackers a significant amount if they send a large number of transactions.

Parasite chain attack: In some blockchains, malicious node can make a parasite
chain with an attempt to make a malicious event block. In Lachesis protocol,
when a consensus is reached, finalized event block is verified before it is
added into the Main chain.

Our Lachesis protocol is 1/3-BFT, which requires less than one-third of nodes
are malicious. The malicious nodes may create a parasite chain. As root event
blocks are known by nodes with more than 2W/3 validating power, a parasite
chain can only be shared between malicious nodes, which are accounted for less
than one-third of participating nodes. Nodes with a parasite chain are unable
to generate roots and they will be detected by the Atropos blocks.

Double spending: A double spending attack is when a malicious actor attempts
to spend their funds twice.

Let us consider an example of double spending. Entity $A$ has 10 tokens, but
it sends 10 tokens to $B$ via node $n_{A}$ and at the same time it also sends
10 tokens to $C$ via node $n_{C}$. Both node $n_{A}$ and node $n_{C}$ agree
that the transaction is valid, since $A$ has the funds to send to $B$
(according to $n_{A}$) and $C$ (according to $n_{C}$). In case one or both of
$n_{A}$ and $n_{C}$ are malicious, they can create a fork $x$ and $y$.

Lachesis protocol can structurally detect the fork by all honest nodes at some
Atropos block. Specially, let us consider the case an attacker in Lachesis
protocol with $W/3+\epsilon$. Assume the attacker can manage to achieve a root
block $r_{b}$ with Blue validators and a conflict root block $r_{r}$ with Red
validators. However, in order for either of the two event blocks to be
finalized (becoming Clotho and then Atropos), each of root blocks need to be
confirmed by roots of next levels. Since peers always propagate new event
blocks, an attacker cannot stop the Blue and Red validators (honest) to sent
and receive event blocks to each other. Therefore, there will exist an honest
validator from Blue or Red groups, who detects conflicting event blocks in the
next level roots aka Atroposes. Because honest validators are incentivized to
detect and prevent these misbehavior, the attacker will get caught and his
stakes are burned.

Sabotage attack: Similarly, for Sabotage attack, the attacker may refuse to
vote for a while. In Lachesis, honest validators will find out the absence of
those high stake validators after some time period. Validators what are
offline for a while will be pruned from the network. After that, those pruned
validators will not be counted and the network will function like normal with
the rest of nodes.

Long-range attack: In some blockchains such as Bitcoin [30], an adversary can
create another chain. If this chain is longer than the original, the network
will accept the longer chain because the longer chain has had more work (or
stake) involved in its creation.

In Lachesis, this long-range attach is not possible. Adding a new block into
the block chain requires an agreement of $2n/3$ of nodes (or $2W/3$ in our PoS
model). To accomplish a long-range attack, attackers would first need to
create more than $2n/3$ malicious nodes (or gain validating power of $2W/3$ in
our PoS model) to create the new chain.

Bribery attack: An adversary could bribe nodes to validate conflicting
transactions. Since $2n/3$ participating nodes (or nodes with a total more
than $2W/3$) are required, this would require the adversary to bribe more than
$n/3$ of all nodes (or $W/3$) to begin a bribery attack.

Denial of Service: Lachesis protocol is leaderless requiring $2n/3$
participation. An adversary would have to attack more than $n/3$ (or $W/3$)
validators to be able to successfully mount a DDoS attack.

Sybil: Each participating node must stake a minimum amount of FTM tokens to
participate in the network. But staking $2/3$ of the total stake would be
prohibitively expensive.

###  6.4 Choices of Stake Decentralization

This section presents discussions and benefits of our proposed DAG-based PoS
approach.

####  6.4.1 Low staked validators

To have more validating nodes, STAIR framework introduces a model which allows
Users with small of tokens can still run a validating node. Details are given
in the paper [32]. Here, we give a summary.

There are three general types of nodes that we are considered in our new
protocol. They are described as follows.

  * •

Validators Validator node can create and validate event blocks. They can
submit new transactions via their new event blocks. To be a validator, a node
needs to have more than $U$ = 1,000,000 FTM tokens. The validating power of a
Validator node is computed by $w_{i}=U\times\lfloor\frac{t_{i}}{U}\rfloor$.

  * •

Users User node can create and validate event blocks. They can submit new
transactions via their new event blocks. To be a user, a node needs to have
more than 1 FTM token. The number of tokens of a User is from 1 to $U$-1 =
999,999 FTM tokens. All users have the same validating power of $w_{i}$ = 1.

  * •

Observers:  Observer node can retrieve even blocks and do post-validation.
Observers cannot perform onchain voting (validation). Observers have zero FTM
tokens and thus zero validating power (e.g., $w_{i}$ = 0).

The value of $U$ is system configurable, which is determined and updated by
the community. Initially, $U$ can be set to a high value, but can be reduced
later on as the token value will increase. Note that, there is a simple model
in which validators have the validating power $w_{i}$ = $U$, instead of
$U\times\lfloor\frac{t_{i}}{U}\rfloor$.

####  6.4.2 Choices of $L$ and $U$

The value of lower bound $L$=$1$ is used to separate between Observers and
Users. The upper bound $U$=$1,000,000$ separates between Users and Validators.
Both $L$ and $U$ are configurable and will vary based on the community’s
decision.

Figure 9 shows the differences between three different account types. The
level of trust is proportional to the number of tokens. Observers have a trust
level of zero and they have incentives to do post-validation for Saga points.
Users have low trust as their token holding varies from 1 to $U$, whereas
Validators have high trust level with more than $U$ tokens in their account.
Both Users and Validators have incentives to join the network to earn
transaction fees and validation rewards.

Figure 9: Token holding, trust levels and incentives of the three account
types

There are a limited number of Observers and a small pool of Validators in the
entire network. The number of Users may take a great part of the network.

####  6.4.3 Alternative models for gossip and staking

We also propose an alternative model to ensure a more balanced chance for both
Users and Validators. This is to improve liveness and safety of the network.
Specifically, each User node randomly selects a Validator node in
$\mathcal{V}$ and each Validator node randomly chooses a User node in
$\mathcal{U}$. The probability of being selected is proportional to the value
$w_{i}$ in the set, in both cases. Alternatively, each Validator node can
randomly select a node from all nodes with a probability reversely
proportional to the stake $w_{i}$.

####  6.4.4 Network load

More observers may consume more network capacity from the validating nodes. To
support more nodes, observers may not be allowed to synchronize and retrieve
events directly from Validators. Instead, we suggest to use a small pool of
Moderator nodes that will retrieve updated events from Validators. Observers
will then synchronize with the Moderator nodes to download new updates and to
perform post-validation. Similarly, low staked validators can synchronize with
such Moderator nodes as well.

##  7 Conclusion

In this paper, we consolidate the key technologies and algorithms of our
Lachesis consensus protocol used in Fantom’s Opera network. Lachesis protocol
integrates Proof of Stake into a DAG-based model to achieve more scalable and
fast consensus. It guarantees asynchronous practical BFT. Further, we present
a staking model.

By using Lamport timestamps, Happened-before relation, and layer information,
our algorithm for topological ordering of event blocks is deterministic and
guarantees a consistency and finality of events in all honest nodes.

We present a formal proofs and semantics of our PoS+DAG Lachesis protocol in
the Appendix. Our work extends the formal foundation established in our
previous papers [9, 31, 33], which is the first that studies concurrent common
knowledge sematics [34] in DAG-based protocols. Formal proofs for our
layering-based protocol is also presented.

###  7.1 Future work

We are considering several models to improve the scalability and
sustainability of Opera network. In particular, we investigate several
approaches to allow more validating nodes to join the network, whilst we aim
to improve decentralization, increase TPS and keep TTF low. A brief
introduction of these approaches is given in the Appendix.

##  8 Appendix

###  8.1 Basic Definitions

Lachesis protocol is run via nodes representing users’ machines which together
create the Opera network. The basic units of the protocol are called event
blocks - a data structure created by a single node, which contains
transactions. These event blocks reference previous event blocks that are
known to the node. This flow or stream of information creates a sequence of
history.

_[Lachesis]_ Lachesis protocol is a consensus protocol

_[Node]_ Each machine that participates in the Lachesis protocol is called a
_node_. Let $n$ denote the total number of nodes.

_[ $k$]_ A _constant_ defined in the system.

_[Peer node]_ A node $n_{i}$ has $k$ _peer nodes_.

_[Process]_ A process $p_{i}$ represents a machine or a _node_. The process
identifier of $p_{i}$ is $i$. A set $P$ = {1,…,$n$} denotes the set of process
identifiers.

_[Channel]_ A process $i$ can send messages to process $j$ if there is a
channel ($i$,$j$). Let $C$ $\subseteq$ {($i$,$j$) s.t. $i,j\in P$} denote the
set of channels.

####  8.1.1 Events

_[Event block]_ Each node can create event blocks, send (receive) messages to
(from) other nodes.

The structure of an event block includes the signature, generation time,
transaction history, and hash information to references. All nodes can create
event blocks. The first event block of each node is called a _leaf event_.

Suppose a node $n_{i}$ creates an event $v_{c}$ after an event $v_{s}$ in
$n_{i}$. Each event block has exactly $k$ references. One of the references is
self-reference, and the other $k$-1 references point to the top events of
$n_{i}$’s $k$-1 peer nodes.

_[Top Event]_ An event $v$ is a top event of a node $n_{i}$ if there is no
other event in $n_{i}$ referencing $v$.

_[Height Vector]_ The height vector is the number of event blocks _created_ by
the $i$-th node.

_[Ref]_ An event $v_{r}$ is called “ref” of event $v_{c}$ if the reference
hash of $v_{c}$ points to the event $v_{r}$. Denoted by
$v_{c}\hookrightarrow^{r}v_{r}$. For simplicity, we can use $\hookrightarrow$
to denote a reference relationship (either $\hookrightarrow^{r}$ or
$\hookrightarrow^{s}$).

_[Self-ref]_ An event $v_{s}$ is called “self-ref” of event $v_{c}$, if the
self-ref hash of $v_{c}$ points to the event $v_{s}$. Denoted by
$v_{c}\hookrightarrow^{s}v_{s}$.

_[Event references]_ Each event block has at least $k$ references. One of the
references is self-reference, and the others point to the top events of other
peer nodes.

_[Self-ancestor]_ An event block $v_{a}$ is self-ancestor of an event block
$v_{c}$ if there is a sequence of events such that
$v_{c}\hookrightarrow^{s}v_{1}\hookrightarrow^{s}\dots\hookrightarrow^{s}v_{m}\hookrightarrow^{s}v_{a}$.
Denoted by $v_{c}\hookrightarrow^{sa}v_{a}$.

_[Ancestor]_ An event block $v_{a}$ is an ancestor of an event block $v_{c}$
if there is a sequence of events such that $v_{c}\hookrightarrow
v_{1}\hookrightarrow\dots\hookrightarrow v_{m}\hookrightarrow v_{a}$. Denoted
by $v_{c}\hookrightarrow^{a}v_{a}$.

For simplicity, we simply use $v_{c}\hookrightarrow^{a}v_{s}$ to refer both
ancestor and self-ancestor relationship, unless we need to distinguish the two
cases.

####  8.1.2 OPERA DAG

In Lachesis protocol, the history of event blocks form a directed acyclic
graph, called OPERA DAG. OPERA DAG $G=(V,E)$ consists of a set of vertices $V$
and a set of edges $E$ . A path in $G$ is a sequence of vertices ($v_{1}$,
$v_{2}$, $\dots$, $v_{k}$) by following the edges in $E$ such that it uses no
edge more than once. Let $v_{c}$ be a vertex in $G$. A vertex $v_{p}$ is the
_parent_ of $v_{c}$ if there is an edge from $v_{p}$ to $v_{c}$. A vertex
$v_{a}$ is an _ancestor_ of $v_{c}$ if there is a path from $v_{a}$ to
$v_{c}$.

######  Definition 8.1 (OPERA DAG).

OPERA DAG is a DAG graph $G=(V,E)$ consisting of $V$ vertices and $E$ edges.
Each vertex $v_{i}\in V$ is an event block. An edge $(v_{i},v_{j})\in E$
refers to a hashing reference from $v_{i}$ to $v_{j}$; that is,
$v_{i}\hookrightarrow v_{j}$.

######  Definition 8.2 (vertex).

An event block is a vertex of the OPERA DAG.

Suppose a node $n_{i}$ creates an event $v_{c}$ after an event $v_{s}$ in
$n_{i}$. Each event block has at most $k$ references. Thus, each vertex has at
most $k$ out-edges. One of the references is self-reference, and the other
$k$-1 references point to the top events of $n_{i}$’s $k$-1 peer nodes.

####  8.1.3 Happened-Before relation

The “happened before” relation, denoted by $\rightarrow$, gives a partial
ordering of events from a distributed system of nodes. Each node $n_{i}$ (also
called a process) is identified by its process identifier $i$. For a pair of
event blocks $v$ and $v^{\prime}$, the relation ”$\rightarrow$” satisfies: (1)
If $v$ and $v^{\prime}$ are events of process $P_{i}$, and $v$ comes before
$v^{\prime}$, then $b\rightarrow v^{\prime}$. (2) If $v$ is the send($m$) by
one process and $v^{\prime}$ is the receive($m$) by another process, then
$v\rightarrow v^{\prime}$. (3) If $v\rightarrow v^{\prime}$ and
$v^{\prime}\rightarrow v^{\prime\prime}$ then $v\rightarrow v^{\prime\prime}$.
Two distinct events $v$ and $v^{\prime}$ are said to be concurrent if
$v\nrightarrow v^{\prime}$ and $v^{\prime}\nrightarrow v$.

_[Happened-Immediate-Before]_ An event block $v_{x}$ is said Happened-
Immediate-Before an event block $v_{y}$ if $v_{x}$ is a (self-) ref of
$v_{y}$. Denoted by $v_{x}\mapsto v_{y}$.

_[Happened-Before]_ An event block $v_{x}$ is said Happened-Before an event
block $v_{y}$ if $v_{x}$ is a (self-) ancestor of $v_{y}$. Denoted by
$v_{x}\rightarrow v_{y}$.

The happened-before relation is the transitive closure of happens-immediately-
before. An event $v_{x}$ happened before an event $v_{y}$ if one of the
followings happens: (a) $v_{y}\hookrightarrow^{s}v_{x}$, (b)
$v_{y}\hookrightarrow^{r}v_{x}$, or (c) $v_{y}\hookrightarrow^{a}v_{x}$.

In Lachesis, we come up with the following proposition:

######  Proposition 8.1 (Happened-Immediate-Before OPERA).

$v_{x}\mapsto v_{y}$ iff $v_{y}\hookrightarrow v_{x}$ iff edge $(v_{y},v_{x})$
$\in E$ in OPERA DAG.

######  Lemma 8.2 (Happened-Before Lemma).

$v_{x}\rightarrow v_{y}$ iff $v_{y}\hookrightarrow^{a}v_{x}$.

_[Concurrent]_ Two event blocks $v_{x}$ and $v_{y}$ are said concurrent if
neither of them happened before the other. Denoted by $v_{x}\parallel v_{y}$.

Let $G_{1}$ and $G_{2}$ be the two OPERA DAGS of any two honest nodes. For any
two vertices $v_{x}$ and $v_{y}$, if both of them are contained in two OPERA
DAGs $G_{1}$ and $G_{2}$, then they are satisfied the following:

  * •

$v_{x}\rightarrow v_{y}$ in $G_{1}$ if $v_{x}\rightarrow v_{y}$ in $G_{2}$.

  * •

$v_{x}\parallel v_{y}$ in $G_{1}$ if $v_{x}\parallel v_{y}$ in $G_{2}$.

Happened-before defines the relationship between event blocks created and
shared between nodes. If there is a path from an event block $v_{x}$ to
$v_{y}$, then $v_{x}$ Happened-before $v_{y}$. “$v_{x}$ Happened-before
$v_{y}$” means that the node creating $v_{y}$ knows event block $v_{x}$. This
relation is the transitive closure of happens-immediately-before. Thus, an
event $v_{x}$ happened before an event $v_{y}$ if one of the followings
happens: (a) $v_{y}\hookrightarrow^{s}v_{x}$, (b)
$v_{y}\hookrightarrow^{r}v_{x}$, or (c) $v_{y}\hookrightarrow^{a}v_{x}$. The
happened-before relation of events form an acyclic directed graph
$G^{\prime}=(V,E^{\prime})$ such that an edge $(v_{i},v_{j})\in E^{\prime}$
has a reverse direction of the same edge in $E$.

####  8.1.4 Lamport timestamp

Lachesis protocol relies on Lamport timestamps to define a topological
ordering of event blocks in OPERA DAG. By using Lamport timestamps, we do not
rely on physical clocks to determine a partial ordering of events.

We use this total ordering in our Lachesis protocol to determine consensus
time.

For an arbitrary total ordering ‘$\prec$‘ of the processes, a relation
‘$\Rightarrow$‘ is defined as follows: if $v$ is an event in process $P_{i}$
and $v^{\prime}$ is an event in process $P_{j}$, then $v\Rightarrow
v^{\prime}$ if and only if either (i) $C_{i}(v)<C_{j}(v^{\prime})$ or (ii)
$C(v)=C_{j}(v^{\prime})$ and $P_{i}\prec P_{j}$. This defines a total
ordering, and that the Clock Condition implies that if $v\rightarrow
v^{\prime}$ then $v\Rightarrow v^{\prime}$.

####  8.1.5 Domination relation

In a graph $G=(V,E,r)$, a dominator is the relation between two vertices. A
vertex $v$ is dominated by another vertex $w$, if every path in the graph from
the root $r$ to $v$ have to go through $w$. The immediate dominator for a
vertex $v$ is the last of $v$’s dominators, which every path in the graph have
to go through to reach $v$.

_[Pseudo top]_ A pseudo vertex, called top, is the parent of all top event
blocks. Denoted by $\top$.

_[Pseudo bottom]_ A pseudo vertex, called bottom, is the child of all leaf
event blocks. Denoted by $\bot$.

With the pseudo vertices, we have $\bot$ happened-before all event blocks.
Also all event blocks happened-before $\top$. That is, for all event $v_{i}$,
$\bot\rightarrow v_{i}$ and $v_{i}\rightarrow\top$.

Then we define the domination relation for event blocks. To begin with, we
first introduce pseudo vertices, _top_ and _bot_ , of the DAG OPERA DAG $G$.
_[pseudo top]_ A pseudo vertex, called top, is the parent of all top event
blocks. Denoted by $\top$.

_[dom]_ An event $v_{d}$ dominates an event $v_{x}$ if every path from $\top$
to $v_{x}$ must go through $v_{d}$. Denoted by $v_{d}\gg v_{x}$.

_[strict dom]_ An event $v_{d}$ strictly dominates an event $v_{x}$ if
$v_{d}\gg v_{x}$ and $v_{d}$ does not equal $v_{x}$. Denoted by
$v_{d}\gg^{s}v_{x}$.

_[domfront]_ A vertex $v_{d}$ is said “domfront” a vertex $v_{x}$ if $v_{d}$
dominates an immediate predecessor of $v_{x}$, but $v_{d}$ does not strictly
dominate $v_{x}$. Denoted by $v_{d}\gg^{f}v_{x}$.

_[dominance frontier]_ The dominance frontier of a vertex $v_{d}$ is the set
of all nodes $v_{x}$ such that $v_{d}\gg^{f}v_{x}$. Denoted by $DF(v_{d})$.

From the above definitions of domfront and dominance frontier, the following
holds. If $v_{d}\gg^{f}v_{x}$, then $v_{x}\in DF(v_{d})$.

For a set $S$ of vertices, an event $v_{d}$ $\frac{2}{3}$-dominates $S$ if
there are more than 2/3 of vertices $v_{x}$ in $S$ such that $v_{d}$ dominates
$v_{x}$. Recall that $R_{1}$ is the set of all leaf vertices in $G$. The
$\frac{2}{3}$-dom set $D_{0}$ is the same as the set $R_{1}$.The
$\frac{2}{3}$-dom set $D_{i}$ is defined as follows:

_[ $\frac{2}{3}$-dom set]]_ A vertex $v_{d}$ belongs to a $\frac{2}{3}$-dom
set within the graph $G[v_{d}]$, if $v_{d}$ $\frac{2}{3}$-dominates $R_{1}$.
The $\frac{2}{3}$-dom set $D_{k}$ consists of all roots $d_{i}$ such that
$d_{i}$ $\not\in$ $D_{i}$, $\forall$ $i$ = 1..($k$-1), and $d_{i}$
$\frac{2}{3}$-dominates $D_{i-1}$.

######  Lemma 8.3.

The $\frac{2}{3}$-dom set $D_{i}$ is the same with the root set $R_{i}$, for
all nodes.

###  8.2 Proof of aBFT

This section presents a proof to show that our Lachesis protocol is Byzantine
fault tolerant when at most one-third of participants are compromised. We
first provide some definitions, lemmas and theorems. We give formal semantics
of PoS+DAG Lachesis protocol using the semantics in concurrent common
knowledge.

####  8.2.1 S-OPERA DAG - A Weighted DAG

The OPERA DAG (DAG) is the local view of the DAG held by each node, this local
view is used to identify topological ordering between events, to decide Clotho
candidates and to compute consensus time of Atropos and events under it’s
subgraph.

######  Definition 8.3 (S-OPERA DAG).

An S-OPERA DAG is the local view of a weighted DAG $G$=($V$,$E$, $w$). Each
vertex $v_{i}\in V$ is an event block. Each block has a weight, which is the
_validation score_. An edge ($v_{i}$,$v_{j}$) $\in E$ refers to a hashing
reference from $v_{i}$ to $v_{j}$; that is, $v_{i}\hookrightarrow v_{j}$.

####  8.2.2 Consistency of DAGs

_[Leaf]_ The first created event block of a node is called a leaf event block.

_[Root]_ An event block $v$ is a root if either (1) it is the leaf event block
of a node, or (2) $v$ can reach more than $2W/3$ validating power from
previous roots.

_[Root set]_ The set of all first event blocks (leaf events) of all nodes form
the first root set $R_{1}$ ($|R_{1}|$ = $n$). The root set $R_{k}$ consists of
all roots $r_{i}$ such that $r_{i}$ $\not\in$ $R_{i}$, $\forall$ $i$ =
1..($k$-1) and $r_{i}$ can reach more than $2W/3$ validating power from other
roots in the current frame, $i$ = 1..($k$-1).

_[Frame]_ The history of events are divided into frames. Each frame contains a
disjoint set of roots and event blocks.

_[Subgraph]_ For a vertex $v$ in a DAG $G$, let $G[v]=(V_{v},E_{v})$ denote an
induced-subgraph of $G$ such that $V_{v}$ consists of all ancestors of $v$
including $v$, and $E_{v}$ is the induced edges of $V_{v}$ in $G$.

We define a definition of consistent DAGs, which is important to define the
semantics of Lachesis protocol.

######  Definition 8.4 (Consistent DAGs).

Two OPERA DAGs $G_{1}$ and $G_{2}$ are consistent if for any event $v$
contained in both chains, $G_{1}[v]=G_{2}[v]$. Denoted by $G_{1}\sim G_{2}$.

######  Theorem 8.4 (Honest nodes have consistent DAGs).

All honest nodes have consistent OPERA DAGs.

If two nodes have OPERA DAGs containing event $v$, $v$ is valid and both
contain all the parents referenced by $v$. In Lachesis, a node will not accept
an event during a sync unless that node already has all references for that
event, and thus both OPERA DAGs must contain $k$ references for $v$. The
cryptographic hashes are assumed to be secure, therefore the references must
be the same. By induction, all ancestors of $v$ must be the same. Therefore,
for any two honest nodes, their OPERA DAGs are consistent. Thus, all honest
nodes have consistent OPERA DAGs.

_[Creator]_ If a node $n_{x}$ creates an event block $v$, then the creator of
$v$, denoted by $cr(v)$, is $n_{x}$.

######  Definition 8.5 (Global DAG).

A DAG $G^{C}$ is a global DAG of all $G_{i}$, if $G^{C}\sim G_{i}$ for all
$G_{i}$.

Let denote $G\sqsubseteq G^{\prime}$ to stand for $G$ is a subgraph of
$G^{\prime}$. Some properties of the global DAG $G^{C}$ are given as follows:

  1. 1.

$\forall G_{i}$ ($G^{C}\sqsubseteq G_{i}$).

  2. 2.

$\forall v\in G^{C}$ $\forall G_{i}$ ($G^{C}[v]\sqsubseteq G_{i}[v]$).

  3. 3.

($\forall v_{c}\in G^{C}$) ($\forall v_{p}\in G_{i}$) (($v_{p}\rightarrow
v_{c})\Rightarrow v_{p}\in G^{C}$).

####  8.2.3 Root

We define the ’forkless cause’ relation, as follows:

######  Definition 8.6 (forkless cause).

The relation $forklessCause(A,B)$ denote that event $x$ is forkless caused by
event $y$.

It means, in the subgraph of event $x$, $x$ did not observe any forks from
$y$’s creator and at least QUORUM non-cheater validators have observed event
$y$.

######  Proposition 8.5.

If $G_{1}\sim G_{2}$, and $x$ and $y$ exist in both, then forklessCause($x$,
$y$) is true in $G_{1}$ iff forklessCause($x$, $y$) is true in $G_{2}$.

For any two consistent graphs $G_{1}$ and $G_{2}$, the subgraphs
$G_{1}[x]=G_{2}[x]$ and $G_{1}[y]=G_{2}[y]$. Also $y$’s creator and QUORUM is
the same on both DAGs.

_[Validation Score]_ For event block $v$ in both $G_{1}$ and $G_{2}$, and
$G_{1}\sim G_{2}$, the validation score of $v$ in $G_{1}$ is identical with
that of $v$ in $G_{2}$.

######  Definition 8.7 (root).

An event is called a root, if it is _forkless causes_ by QUORUM roots of
previous frame.

For every event, its frame number is no smaller than self-parent’s frame
number.

The lowest possible frame number is 1. Relation $forklessCause$ is a stricter
version of happened-before relation, i.e. if $y$ forkless causes $x$, then $y$
is happened before A. Yet, unlike happened-before relation, forklessCause is
not transitive because it returns false if fork is observed. So if $x$
forkless causes $y$, and $y$ forkless causes $z$, it does not mean that $x$
forkless causes $z$. If there’s no forks in the graph, then the forklessCause
is always transitive.

######  Proposition 8.6.

If $G_{1}\sim G_{2}$, and then $G_{1}$ and $G_{2}$ are root consistent.

Now we state the following important propositions.

######  Definition 8.8 (Root consistency).

Two DAGs $G_{1}$ and $G_{2}$ are root consistent: if for every $v$ contained
in both DAGs, and $v$ is a root of $j$-th frame in $G_{1}$, then $v$ is a root
of $j$-th frame in $G_{2}$.

######  Proposition 8.7.

If $G_{1}\sim G_{2}$, then $G_{1}$ and $G_{2}$ are root consistent.

###### Proof.

By consistent chains, if $G_{1}\sim G_{2}$ and $v$ belongs to both chains,
then $G_{1}[v]$ = $G_{2}[v]$. We can prove the proposition by induction. For
$j$ = 0, the first root set is the same in both $G_{1}$ and $G_{2}$. Hence, it
holds for $j$ = 0. Suppose that the proposition holds for every $j$ from 0 to
$k$. We prove that it also holds for $j$= $k$ \+ 1. Suppose that $v$ is a root
of frame $f_{k+1}$ in $G_{1}$. Then there exists a set $S$ reaching 2/3 of
members in $G_{1}$ of frame $f_{k}$ such that $\forall u\in S$ ($u\rightarrow
v$). As $G_{1}\sim G_{2}$, and $v$ in $G_{2}$, then $\forall u\in S$ ($u\in
G_{2}$). Since the proposition holds for $j$=$k$, As $u$ is a root of frame
$f_{k}$ in $G_{1}$, $u$ is a root of frame $f_{k}$ in $G_{2}$. Hence, the set
$S$ of 2/3 members $u$ happens before $v$ in $G_{2}$. So $v$ belongs to
$f_{k+1}$ in $G_{2}$. The proposition is proved. ∎

From the above proposition, one can deduce the following:

######  Lemma 8.8.

$G^{C}$ is root consistent with $G_{i}$ for all nodes.

By consistent DAGs, if $G_{1}\sim G_{2}$ and $v$ belongs to both chains, then
$G_{1}[v]$ = $G_{2}[v]$. We can prove the proposition by induction. For $j$ =
0, the first root set is the same in both $G_{1}$ and $G_{2}$. Hence, it holds
for $j$ = 0. Suppose that the proposition holds for every $j$ from 0 to $k$.
We prove that it also holds for $j$= $k$ \+ 1. Suppose that $v$ is a root of
frame $f_{k+1}$ in $G_{1}$. Then there exists a set $S$ reaching 2/3 of
members in $G_{1}$ of frame $f_{k}$ such that $\forall u\in S$ ($u\rightarrow
v$). As $G_{1}\sim G_{2}$, and $v$ in $G_{2}$, then $\forall u\in S$ ($u\in
G_{2}$). Since the proposition holds for $j$=$k$, As $u$ is a root of frame
$f_{k}$ in $G_{1}$, $u$ is a root of frame $f_{k}$ in $G_{2}$. Hence, the set
$S$ of 2/3 members $u$ happens before $v$ in $G_{2}$. So $v$ belongs to
$f_{k+1}$ in $G_{2}$.

Thus, all honest nodes have the same consistent root sets, which are the root
sets in $G^{C}$. Frame numbers are consistent for all nodes.

####  8.2.4 Clotho

Algorithm 1 shows our Lachesis’s algorithm to decide a Clotho candidate, as
given in Section 3.9.

######  Definition 8.9 (Clotho consistency).

Two DAGs $G_{1}$ and $G_{2}$ are Clotho consistent: if every $v$ contained in
both DAGs, and $v$ is a Clotho candidate in $j$-th frame in $G_{1}$, then $v$
is a Clotho candidate in $j$-th frame in $G_{2}$.

Thus, we have the following proposition.

######  Proposition 8.9.

If $G_{1}\sim G_{2}$, and then $G_{1}$ and $G_{2}$ are Clotho consistent.

The Algorithm 1 uses computed roots, and $forklessCause$ relation to determine
which roots are candidates for Clotho. As proved in previous proposition and
lemma, honest nodes have consistent DAGs, consistent roots, and so is the
$forklessCause$ relation. Therefore, the Clotho candidate selection is
consistent across honest nodes. All honest nodes will decide the same set of
Clotho events from the global DAG $G^{C}$.

####  8.2.5 Atropos

Algorithm for deciding Atropos is shown in Algorithm 2 in Section 3.10.

The set of roots and Clothos are consistent in all honest nodes, as proved in
previous sections. Validators and their stakes are unchanged within an epoch.
The selection of first Atropos from the sorted list of Clotho is
deterministic. So Atropos candidate is consistent.

######  Definition 8.10 (Atropos consistency).

Two DAGs $G_{1}$ and $G_{2}$ are Atropos consistent: if every $v$ contained in
both DAGs, and $v$ is an Atropos in $j$-th frame in $G_{1}$, then $v$ is an
Atropos in $j$-th frame in $G_{2}$.

Thus, we have the following proposition.

######  Proposition 8.10.

If $G_{1}\sim G_{2}$, then $G_{1}$ and $G_{2}$ are Atropos consistent.

All honest nodes will decide the same set of Atropos events from the global
DAG $G^{C}$.

####  8.2.6 Block

After a new Atropos is decided, the Atropos is assigned a consensus time using
the Atropos’s median timestamp. The median timestamp is the median of the
times sent by all nodes. The median time makes sure that the consensus time is
BFT, even in case there may exist Byzantine nodes accounting for up to 1/3 of
the validation power.

When an Atropos is decided and assigned a consensus time, a new block is
created. The events under the Atropos $a_{i}$ but not included yet on previous
blocks will be sorted using a topological sorting algorithms outlined in
Section 3.14 and 3.13. The subgraph $G[a_{i}]$ under the Atropos $a_{i}$ is
consistent (as proved previous lemma). The sorting algorithms are
deterministic, and thus the sorted list of events will be the same on all
honest nodes.

After sorting, all these events under the new Atropos will be added into the
new block, and they are all assigned the same consensus time, which is the
Atropos’s consensus time. Transactions of these events are added into the new
block in the sorted order.

######  Definition 8.11 (Block Consistency).

Two DAGs $G_{1}$ and $G_{2}$ are Block consistent: if a block $b_{i}$ at
position $i$ will consist of the same sequence of event blocks and
transactions, for every $i$.

From the above, event blocks in the subgraph rooted at the Atropos are also
final events. It leads to the following proposition:

######  Proposition 8.11.