# SoK: Diving into DAG-based Blockchain Systems

Qin Wang§, Jiangshan Yu‡, Shiping Chen§, Yang Xiang† ${\dagger}$ Swinburne
University of Technology, Australia.
${\ddagger}$ Monash University, Australia
$\S$ CSIRO Data61, Australia

###### Abstract.

Blockchain plays an important role in cryptocurrency markets and technology
services. However, limitations on high latency and low scalability of
classical blockchain systems retard their adoptions and applications.
Reconstructed blockchain systems have been proposed to avoid the consumption
of competitive transactions caused by linear sequenced blocks. These systems,
instead, structure transactions/blocks in the form of Directed Acyclic Graph
(DAG) and consequently rebuild upper layer components. The promise of DAG-
based blockchain systems is to enable fast confirmation (complete transactions
within million seconds) and high scalability (attach transactions in parallel)
without significantly compromising security. However, this field still lacks
systematic work that summarises DAG techniques. To bridge the gap, this
Systematization of Knowledge (SoK) provides a comprehensive analysis of ever-
existing and ongoing DAG-based blockchain systems. Based on substantial
investigation, we abstract a general model to capture the main features and
identify six types of design patterns. Then, we evaluate these systems from
the perspectives of structure, consensus, property, security, and performance.
We further discuss the trade-off between different factors, open challenges
and potentiality of DAG-based solutions, indicating their promising directions
for future research.

DAG-based Blockchain, SoK, Scalability, Performance

$\diamond$ This work has been accepted by ACM Computing Surveys (CSUR) [Nov
2022].
$\diamond$ Affiliations are ordered by the text length.

##  1\. Introduction

Limitations. Blockchain becomes an emerging technology to realize the
distributed ledgers111In this paper, we regard “blockchain” as a general term
covering types and models which are based on the same technology. For
simplicity, we ignore the difference between “blockchain” and “distributed
ledger”. Also, we occasionally use “DAGs” to represent “DAG-based Blockchains”
for short. . The rising interest in blockchain has attracted extensive
attention. Thanking to its great potential to tackle critical security and
trust challenges in various distributed environments, blockchain technology
enjoys rapid development (nakamoto2008peer, )(wood2014ethereum, ) with derived
topics evolving into a well-studied field (bonneau2015sok,
)(belotti2019vademecum, ) in both industry (ali2018applications,
)(xie2019survey, ) and academia (salman2018security, )(conti2018survey, ).
However, the great impact of blockchain promotes an influx of participants
joining the game. Continuously increased traffic results in unavoidably
catastrophic congestion due to the performance bottlenecks (croman2016scaling,
) including slow confirmation, low throughput and poor scalability. Compared
to most centralized systems, these factors cannot be easily improved in
blockchain systems which require decentralization as the priority. Several
studies raise the view of blockchain trilemma (trilemma2019, ) and the trade-
off (kiayias2015speed, ), claiming that decentralization, security, and
scalability, cannot perfectly co-exist in a blockchain system. For example,
one major hindrance to Nakamoto Consensus (NC) (nakamoto2008peer, ) is the
reduced security with an increased block generation rate. The security of NC’s
longest chain wins rule requires that honest nodes should be aware of other’s
blocks soon after the block’s production. If the block creation rate exceeds
the propagation time, concurrent blocks increase the possibility of forks
happening. To mitigate the bottleneck of performance, multiple approaches have
been proposed from different angles.

Potential Solutions. These approaches include the methods on sharding
technique (wang2019sok, )(avarikioti2019divide, ), layer2 protocols
(gudgeon2020sok, ), sidechain technique (back2014enabling, ), heterogeneous
structure (garay2020sok, ), hybrid consensus solutions (bano2019sok, ) and
assisted techniques (hafid2020scaling, ) such as modifying hard-coded
parameters (bch17, ) and cross-chain technique (zamyatin2019sok, ). Sharding
splits pending transactions into smaller shards and makes them processed in
parallel, but it is hard to achieve the consensus across shards due to
asynchronization. Cross-chain protocols help to partially solve the problem by
establishing the channels between multiple shards (horizontal sharding
(zamyatin2019sok, )). As a sacrifice, these on-top protocols inevitably result
in heavy and redundant systems, weakening efficiency and stability. Layer2
protocols enable participants to perform off-(main)chain transactions through
private communication rather than broadcasting to the whole network. Together
with such features, the challenge is how to properly and effectively guarantee
the validity and consistency between off-chain and on-chain transactions. The
technique of sidechain pegs the auxiliary chains to involve more transactions.
A heterogeneous structure adds new types of blocks to assign them to different
tasks. Hybrid consensus solution combines multiple fundamental consensus
mechanisms together (PoX+BFT (bano2019sok, )(garay2020sok, )) to integrate
their benefits. Modifying hard-coded parameters e.g., directly increases the
volume of block from 1M to 8M in BCH (bch17, ). However, these techniques are
still based on the linear-based backbone protocol, limiting the scope of
exploitation. Therefore, radical modification – reconstructing chains from the
underlying structure and topology, becomes an emerging solution.

DAG-based Approach. Linearly structured blockchain systems maintain all the
transactions/blocks in one single chain. Concurrent transactions/blocks
compete for one valid position each round. This design inevitably leads to
slow confirmation due to competitive miners, conflicted transactions, and
wasted computations. The performance of the system can only be artificially
suppressed (e.g., adjust the confirm time) so that each block is fully
attached before the next one’s arrival. Very few orphan blocks can be involved
in the system. To this end, aiming to enable more transactions simultaneously
processed/confirmed motivates the emerge of DAG-based blockchain systems
(sompolinsky2013accelerating, )(popov2016tangle, )(churyumov2016byteball,
)(sompolinsky2016spectre, ). They structure the transactions/blocks in the
form of graph topology to underlyingly alter the actual operations. DAG-based
systems can improve performance by requiring less communication, computation
and storage overhead. However, the sources of existing open-sourced projects
and solutions are disparate and disorganized. Various basic concepts in DAGs
(e.g., vertex meaning, consensus approach, order sequence) are still confused,
and potential challenges have neither been clearly identified. An organized
and structured systematic overview is absent for newcomers. Several studies
draw their attention to this field, but the works are either rough in
summaries (pervez2018comparative, )(birmpas2019fairness, )(bai2018state,
)(gorczyca2019distributed, )(he2019consensus, )(zhou2020solutions,
)(silvano2020iota, )(xiao2020survey, ), superficial in analysis
(hafid2020scaling, )(zander2019dagsim, )(lathif2018cidds, )(dong2019dagbench,
)(raderblockchain, )(benvcic2018distributed, )(saad2019decentralized,
)(schueffel2017alternative, )(webblock18, ), or incomplete in evaluations
(canon2009evaluation, )(li2019direct, )(fan2019performance, ).

Contributions. In this SoK, we attempt to consolidate the core knowledge of
the structural shift in blockchain systems and review the state-of-the-art
DAG-based blockchain systems with comprehensive mechanisms and properties. To
drive future research, we also provide multifaceted discussions and
comparisons with concurrent scaling techniques of blockchain. Furthermore, we
summarise unsolved problems existed in current DAG systems, hoping to
highlight the research challenges in this field. We start with a series of
simple questions, aiming to provide brief guidance for readers.

Q1. What is the DAG-based blockchain? Q2. How do they structure the ledgers?
Q3. How to run the consensus? Q4. What are the desired properties? Q5. How
secure are they? Q6. What is performance improvement? Q7. How is this
different from other techniques? Q8. What are the research challenges?

Framework.To understand the DAG-based blockchains, establishing a DAG system
step by step is necessary. We provide our analysis framework as follows. This
framework helps to clear the mist surrounding the DAG technique applied in
blockchain systems and provides a comprehensive systematic overview of such
systems.

  * $\diamond$

Overview of DAG. Firstly, we review sufficient existing works surrounding DAG-
based blockchain systems in Section 2, covering the topics of protocol design,
analysis and discussion, evaluation and simulation, improvement, application,
and indirectly relevant studies.

  * $\diamond$

Identified types. Secondly, we give an informal mathematical model to
generically describe the DAG-based systems in Section 3, which contains two
elements in different dimensions. Then, we obtain six types of structures by
combining each element. According, we collect and categorize in-the-wild
projects and studies under our identified types.

  * $\diamond$

Consensus. Thirdly, we focus on the consensus mechanism of each aforementioned
system in Section 4. Specifically, we deconstruct the consensus mechanism into
several components, assisting in understanding how these systems operate. We
further discuss the technique features to show their design principles and
potential applications to the systems.

  * $\diamond$

Analysis. Then, we analyse the properties in Section 5, securities in Section
6 and performance in Section 7. These sections enable a deep understanding of
the design principles, system features, and unique properties.

  * $\diamond$

Discussion. Additionally, we review concurrent techniques surrounding the DAG
and clarify a series of open questions in Section 8, 9. Detailed discussions
help us learn more about current challenges and the potential future of this
field.

  * $\diamond$

Summary. As a summary, our analysis framework has answered the listed
questions in detail. Discussions on elements of the DAG model provide us with
a simple but complete classification of current DAG-based systems, answering
Q1 and Q2. Deconstructions of consensus mechanisms show us how current DAG-
based systems operate with their unique designs, answering Q3. Analysis of the
properties, securities, and performance enables us to understand Q4, Q5, and
Q6. Discussions, comparisons, and challenges answer Q7 and Q8. Surrounding
details about the origination, progress, and application are provided in
Section 8, 9.

From a bird’s view, this work provides a roadmap for studying applied-DAG
blockchain systems. Based on our scrutinized analysis, we provide several
remarks in this part: a) DAG-based blockchains are still far away from
commercial applications due to their incompatible designs, absence of
standards, unreliable security, varied performance, and unfinished
implementations. b) DAG structure has the potential to improve scalability and
performance but inevitably sacrifices certain properties like consistency or
finality. c) DAG-based systems vary from one to another. A uniformly
formalized model can hardly cover all key points. Instead, a loose and
informal model benefits a lot for better understanding. d) Although applying
the DAG structure to classic distributed systems and blockchain systems is
quite challenging, many studies with their proposed systems have greatly
progressed and improved. We believe more exciting new protocols/solutions will
emerge shortly.

##  2\. Overview of DAG-Based Blockchains

This section provides a quick overview of existing studies on DAG blockchain
systems. Three aspects are summarized as follows.

Origination and Evolution. Directed Acyclic Graph (DAG) represents a finite
directed graph with no directed cycles in the mathematic and computer field.
Due to the unique topology, it is frequently employed as a basic data
structure and applied to various algorithm scenarios such as seeking the
shortest path in navigation and data compression in storage. The concept was
first introduced to mainstream blockchains by Sompolinsky et al. in the work
of GHOST (sompolinsky2013accelerating, )(sompolinsky2015secure, ), aiming to
address the concurrency problem by allowing transactions structured in trees.
The improved version (lewenberg2015inclusive, ) was applied to Ethereum
(wood2014ethereum, ) as its core consensus mechanism. GHOST protocol and its
variants enable all blocks to quote more than one parent block, and all types
of references can be converted into rewards as incentives. Thus, the
irreversibility of chains can also be strengthened by blocks that are off the
chain. After that, a shift of granularity from block-level to transaction-
level was noted by Lerner et al. in DAGCoin (lerner2015dagcoin, ).
Transactions take over the tasks of blocks, directly confirming the pending
transactions and maintaining the order of sequence. Consequently, efficiency
was leap due to the abandonment of packaging and competing steps. IOTA
(popov2016tangle, ) and ByteBall (churyumov2016byteball, ), inheriting the
concept of blockless, were proposed with full open-sourced implementation and
leads the markets till now. In the following times, several modifications and
updates were added to DAGs. Spectre (sompolinsky2016spectre, ) aims to
establish a system that enables concurrent block creation. Hashgraph
(baird2016swirlds, ) proposed a permissoned graph-based blockchain with the
consensus inspired by BFT-style protocols (malkhi2018blockchain, ). Nano
(lemahieu2018nano, ) proposed a so-called block-lattice structure to realize
immediate and asynchronous processing by allowing users to maintain their
lightweight accounts. Conflux (li2018scaling, ) brought blocks back to the
system for the purpose of a total linear sequence. More cases will be
discussed in later sections.

Analysis and Evaluations. Open-sourced and published works provide their basic
design patterns. Related studies based on them are rooted in different views.
Several works provide analysis by components, including topics on backbone
properties (bramas2018stability, )(kusmierz2017first, )(attias2018tangle, ),
consensus design (he2019consensus, )(tian2020design, ), random walk tip
selection (kusmierz2019properties, ), witness selection
(gorczyca2019distributed, ), cryptographic hash algorithm
(heilman2019cryptanalysis, ), timestamps (popov2017timestamps, ), signature
scheme (buchmann2011security, ), memory model (melnykappend, ), committee
selection (kusmierz2021committee, ), pending probability
(kusmierz2018probability, ), component design (iotacoordicide, ), fees
(popov2019iota, ) etc. While some studies are based on properties, covering
fairness (birmpas2019fairness, ), consistency (kiffer2018better, ), anonymity
(tennant2017improving, )(ince2018adding, )(sarfraz2019privacy, ), performance
(fan2019performance, )(fan2019performance, ), practicability
(dong2019dagbench, ), robustness (canon2009evaluation, ), stability
(bramas2018stability, ), lightweight client (shafeeq2019curbing, ), security
(li2019direct, )(cullen2020resilience, )(cai2019parasite, )(staupe2017quasi,
)(de2018break, )(penzkofer2020parasite, )(monica2018chainweb,
)(tanana2019avalanche, ), incentive and rewards (szalachowski2019strongchain,
), etc. Discussions (pervez2018comparative, )(bai2018state,
)(yuva2018directed, )(raderblockchain, )(saad2019decentralized, ) and
comparisons (schueffel2017alternative, )(benvcic2018distributed, ) on selected
systems (e.g., IOTA, Byteball, Hashgraph, Nano) have identified several
features and challenges, but they were technically or theoretically
insufficient. In-depth analysis employs different techniques and tools, such
as establishing an analysis framework (birmpas2019fairness, ) and converting
complicated environment into simulations (lathif2018cidds, )(wang2020security,
)(zander2019dagsim, )(kusmierz2017first, )(tarun2018chainweb,
)(wang2020chainsim, ). Meanwhile, several types of formal analyses have also
been proposed, including brief models with qualitative arguments
(boyen2018graphchain, )(sompolinsky2015secure, )(sompolinsky2015secure, ),
formal model analysis (sompolinsky2020phantom, )(bentov2017tortoise,
)(tang2020haootia, ) and formal model with mathematics induction
(fitzi2018parallel, ). Beyond that, a few of modified protocols
(kan2018improve, )(manoppodesigning, ) and improved schemes (bu2019g,
)(bu2019metamorphic, )(ferraro2018iota, ) are proposed for further
exploitation.

Applications. Systems based on DAG mainly benefit distributed applications
(DApp) with high performance and low cost. Existing solutions could be roughly
categorized by their combination layers. Directly integrating building blocks
with the underlying network (tesei2018iota, )(lamtzidis2019novel,
)(fantowards, ) helps to enjoy almost equal properties and advantages of DAG,
but it requires expertise development skills and costly hardware devices.
Establishing applications through official components (e.g., Qubic (qubic20,
), MAM (mam, ) in IOTA) is an alternative selection for developers
(lamtzidis2019novel, )(zheng2019accelerating, )(brogan2018authenticating, ).
It simplifies the processes of deployment and maintenance but scarifies
flexibility and customization to a certain degree. Beyond that, various
specific scenarios are considered, which includes the fields on Internet of
Things (alsboui2019enabling, )(cui2019efficient, ), data management
(ruiz2018distributed, ), vehicular applications(bartolomeu2018iota,
)(strugar2018m2m, )(yang2020ldv, ), charging scheduling (guo2020double, ), M2M
Communications (zivic2019distributed, )(assante2019m2m, ), manufacturing
(raschendorfer2019iota, ), smart home infrastructure (fantowards, ), precision
agriculture (lamtzidis2019novel, ), P2P energy trading (murkinblock, ),
intelligent transport systems (tesei2018iota, ), air-quality data-monitoring
System (sun2019indoor, ), smart transportation services (lamtzidis2019novel,
)(zichichi2019distributed, ), sensor node system (lamtzidis2018iota, ), data
quality management (wu2018data, ), E-health (zheng2019accelerating,
)(brogan2018authenticating, )(zheng2019activity, )(shafeeq2019privacy, ),
smart grid (park2019dag, ), feedback control system (cullen2019distributed, ),
database platform (ding2020dagbase, ), voting system (srivastava2018crypto,
)(srivastava2018phantom, )(bahri2019electronic, ), named data network
(zhang2019dledger, ), smart city (ferraro2018distributed, ) etc. It should be
noted that proposed schemes cannot simply achieve multifaceted requirements.
They need to employ additional techniques such as IPFS file system
(benet2014ipfs, ) for storage, zero-knowledge proof (ZKP) for privacy, access
control for authentication (ruiz2018distributed, ), etc. Finally, an important
fact based on the aforementioned solutions is that all combinations aiming to
implement DApps are still staying at the stage of Proof of Concept (PoC), far
away from practical realizations and commercial applications.

Guidelines. For an overview, we summarise related works to provide a full
picture of DAG. Among citations in this paper, the topics that are frequently
studied include three aspects: the protocol designs (including both projects
in industry and schemes in academic); the analysis, comparison, and
evaluations; and potential applications to real scenarios. A handful of
studies provide improved suggestions or schemes, and several works focus on
the techniques or analyses that are (indirectly) related to DAGs (cf.
Table.1).

Table 1. Guideline of Literature

Protocol Design |  (sompolinsky2013accelerating, ) (lewenberg2015inclusive, ) (sompolinsky2015secure, ) (amores2021generalizing, ) (popov2016tangle, ) (iotacoordicide, ) (churyumov2016byteball, ) (li2018scaling, ) (baird2016swirlds, ) (Choi2018OPERARA, ) (choi2018fantom, ) (Nguyen2019ONLAYOL, ) (Nguyen2019StakeDagSC, ) (he2019consensus, ) (melnykappend, ) (wang2021weak, ) (wang2019improving, ) (wang20213ddag, ) (Nguyen2019StairDagCV, )(sompolinsky2018phantom, ) (sompolinsky2016spectre, ) (Sompolinsky2017SPECTRES, ) (lemahieu2018nano, ) (gkagol2018aleph, ) (rocket2019scalable, ) (bagaria2019prism, ) (danezis2018blockmania, ) (yang2019prism, ) (lerner2015dagcoin, ) (chen2018dexon, ) (boyen2016blockchain, ) (yin2019streamnet, ) (boyen2018graphchain, ) (Soteria, ) (zdag, ) (liu2018vite, ) (li2020ghast, ) (li2020decentralized, ) (itc, ) (webblock18, ) (manoppodesigning, ) (istvan2018streamchain, ) (popov2018local, ) (yu2020ohie, ) (niu2019eunomia, ) (will2019chainweb, ) (gupta2019cdag, ) (chevalier2019protocol, ) (cao2019high, ) (zhou2020hotdag, ) (zhang2020c, ) (abram2020democratising, ) (swaroopa2020scalable, ) (tian2020design, ) (Idit2019dagrider, ) (nguyen2021lachesis, ) (giridharan2022bullshark, ) (muller2022tangle, ) (wang2021securing, );
---|---
Analysis/Discussion |  (kiayias2017trees, ) (kovalchuk2018number, ) (popov2019equilibria, ) (kusmierz2018extracting, ) (bramas2018stability, ) (heilman2019cryptanalysis, ) (silvano2020iota, ) (melnykappend, ) (attias2018tangle, ) (buchmann2011security, ) (popov2017timestamps, ) (popov2019iota, ) (kusmierz2018probability, ) (kusmierz2019properties, ) (kiffer2018better, ) (tennant2017improving, ) (staupe2017quasi, ) (li2019analysis, ) (li2019direct, ) (kan2018improve, ) (fan2019performance, ) (pervez2018comparative, ) (bai2018state, ) (kannengiesser2019mind, ) (raderblockchain, ) (benvcic2018distributed, ) (saad2019decentralized, ) (qin2020security, ) (fitzi2018parallel, ) (monica2018chainweb, ) (tanana2019avalanche, ) (divya2018iota, );
Evaluation/Simulation |  (popov2019equilibria, ) (kusmierz2017first, ) (kusmierz2018probability, ) (birmpas2019fairness, ) (park2019performance, ) (gorczyca2019distributed, ) (wang2020security, ) (dong2019dagbench, ) (lathif2018cidds, ) (zander2019dagsim, ) (tarun2018chainweb, ) (wang2020chainsim, ) (wang2020prism, ) (demotest, );
Attack/Defense |  (cullen2020resilience, ) (cai2019parasite, ) (penzkofer2020parasite, ) (staupe2017quasi, ) (tarun2018chainweb, ) (de2018break, ) (psdetection, ) (qin2020security, );
Improvement |  (shafeeq2019curbing, ) (kusmierz2021committee, ) (ferraro2018iota, ) (vigneriachieving, ) (sarfraz2019privacy, ) (tennant2017improving, ) (ince2018adding, ) (bu2019g, ) (bu2019metamorphic, ) (gkagol2019aleph, ) (cullen2020congestion, );
Application/Cases |  (yuva2018directed, ) (bartolomeu2018iota, ) (yang2020ldv, ) (raschendorfer2019iota, ) (ruiz2018distributed, ) (wu2018data, ) (lamtzidis2018iota, ) (brogan2018authenticating, ) (zheng2019accelerating, ) (lamtzidis2019novel, ) (zichichi2019distributed, ) (sun2019indoor, ) (murkinblock, ) (xiao2019large, ) (cui2019efficient, ) (zhou2019dlattice, ) (xiang2019jointgraph, ) (park2019dag, ) (tesei2018iota, ) (fantowards, ) (alsboui2019enabling, ) (strugar2018m2m, ) (cullen2019distributed, ) (srivastava2018crypto, ) (srivastava2018phantom, ) (zivic2019distributed, ) (assante2019m2m, ) (bahri2019electronic, ) (zheng2019activity, ) (ferraro2018distributed, ) (shafeeq2019privacy, ) (zhang2019dledger, ) (guo2020double, );
Related Discussion |  (wang2019sok, ) (bano2019sok, ) (zamyatin2019sok, ) (bonneau2015sok, ) (gudgeon2020sok, ) (gramoli2017blockchain, ) (szalachowski2019strongchain, ) (makhdoom2019blockchain, ) (wang2019survey, ) (xiao2020survey, ) (vukolic2017rethinking, ) (kaur2020scalability, ) (malkhi2022maximal, ).

##  3\. Modeling

This section defines an informal DAG model and network model. Then, we
classify current systems into six types accordingly.

###  3.1. From Classic Blockchain To DAG

Blockchain records activities in the form of transactions. Transactions are
organized into a hierarchical structure as a block, and blocks are arranged in
an irreversibly ordered sequence. New blocks can only be attached to the main
chain which are strictly sequenced by predecessors and successors. Although
consensus mechanisms vary from system to system, classic blockchains base on
the same linear-based chain structure. Transactions cannot be tampered or
compromised due to the global view shared by all participants, integrity and
traceability are consequently provided. Other types of blockchain modeling
could be referred to (sompolinsky2015secure, )(lewenberg2015inclusive,
)(atzei2018formal, )(garay2015bitcoin, ).

The performance bottleneck of the linear structure is mainly caused by
consensus mechanisms. Specifically, a group of nodes compete for the right of
block packaging though many methods such as rotating leaders (BFT-style),
solving puzzles (PoW), holding stakes (PoX), etc. Only winners are able to
determine the validity and confirmation of transactions, while left
transactions are pended in the pool or discarded off the chain. Adding blocks
at the same time causes more conflicts. In contrast, DAG-based structure aims
to enable multiple transactions confirmed in one round. Each unit
(transactions/blocks/events) of the ledger could refer to more than one parent
units, and also could be referenced by numerous subsequent units. This
structural design supports concurrent operations. Multiple nodes can
simultaneously add units to the ledger, thereby significantly improving the
throughput.

###  3.2. DAG-based Model

A directed acyclic graph $\mathcal{G}$ consists of a point set $\mathcal{V}$
and an edge set $\mathcal{E}$. Firstly, each element in the point set
corresponds to a unit. A unit can be instantiated as a transaction
$\mathsf{Tx}\in\mathcal{T}$, a block $\mathsf{B}\in\mathcal{B}$, or an event
$\mathsf{E}\in\mathcal{E}$ in protocols, where
$\mathcal{T},\mathcal{B},\mathcal{E}$ represents the sets of elements.
Secondly, the element in the edge set is a pair $(u,v)$, which represents the
partial order relationship between two points $u$ and $v$. The relationship,
in most cases, indicates that one of the unit references another unit. For
instance, $u\leftarrow v$ means $v$ confirms/verifies/witnesses/sees $u$,
where $\\{u,v\\}\subseteq\mathcal{V}$. We define the DAG-based model with two
properties as follows:

###### Definition 3.1 (DAG-based blockchain model).

The model $\mathcal{G}$ is defined as,

$\begin{array}[]{ll}\begin{aligned}
\mathcal{G}&=(\mathcal{E},\mathcal{V})^{{\dagger}}{{}^{{\ddagger}}},\,\,\textit{where}\\\
\mathcal{V}&=\\{u\,|u\in\\{\mathcal{T}\cup\mathcal{B}\cup\mathcal{E}\\}\\},\,\,\mathcal{E}=\\{(u,v)\,|\,u\leftarrow
v\land\\{u,v\\}\subseteq\mathcal{V}\\}.\\\ &{\dagger}:\,\,\forall u\leftarrow
v\nRightarrow v\leftarrow u;\\\ &{\ddagger}:\,\textit{{Assume
that}}\,\,u_{i}\in\\{u_{1},u_{2},...,u_{l}\\}\subseteq\mathcal{V}:\,\,\,\forall
i,j,k\in[1,l],\,\\\ &\quad
where\,\,k>j>i,\,\,\\{j\\}\subset\\{\varnothing,...,\\{i+1,...,k-1\\}\\}\,\,\\\
&\quad\textbf{if}\,\,u_{i}\leftarrow u_{j},u_{j}\leftarrow
u_{k},\,\,\textbf{then,}\,\,u_{k}\leftarrow u_{i}\,\,\textit{does not
exist}.\\\ \end{aligned}\end{array}$

Here, the operation “$a|b$” means $a$ satisfies the condition of $b$.
“$\leftarrow$” represents an action that happens in the network. The property
means (i) unidirectional†: the references point in the same direction; (ii)
acyclic‡: no loop exists in graph. It enables the units in the network
appended-only and orderable. (more details refer to Appendix A)

###  3.3. Identified Types

The abstracted model describes the protocol in a theoretical and mathematical
form. We first specify the exact representations of units $\mathcal{V}$ and
edges $\mathcal{E}$ in the model. These elements define the structure and
topology of a DAG-based system. We start our analysis framework from here.

  * -

Unit Representation.  This shows the underlying element of a system, either
transactions, events, or blocks. We have two types of options:  $1^{od}$ and
$2^{od}$. The former represents the request that is immediately handled
whenever it is received, without having to wait for more requests from peers.
The forms of this type include transactions and triggering-events. The latter
represents the request that needs further handling. In most cases, such
requests are pre-computed or packaged by powerful parties (e.g., miner,
validator) and then be disseminated. The forms of this type contain blocks.

  * -

Graph Topology.  A single edge may be insufficient to represent all
relationships within a DAG-based system. The system is usually meshed by a set
of edges. We identify three types of typologies based on their formed graphs,
namely Divergence, Parallel and Convergence (abbreviated as
$\widehat{D},\widehat{P},\widehat{C}$, respectively). Specifically, divergence
means the units sparsely spread in unpredictable directions without
predetermined orders. Parallel means the units are maintained in the form of
multiple (parallel) chains. Convergence means the units are organized in a
determined sequence or tend to converge in a determined sequence.

The unit representation indicates the element of the system. It also reflects
the ledger execution model, indicating how a transaction is completed in DAG-
based systems. Generally, two types of models are included: UTXO-based model
and account-based (acct) model. The former one means all operations are
completed through atomic transactions. Users can calculate the balance by
tracing the history of previous transactions. For the latter one, each user
holds an account and the transaction is merely configured as one of the fields
in its structure (e.g., the changes of balance). Users calculate the balance
directly in their accounts.

The topology mainly focuses on an eventual trend of these units in the
network. The units that initially spread to multiple directions but finally
converge to the main chain, can still be classified into convergence. For
example, the blocks in GHOST (sompolinsky2015secure, ) attach to their parents
in a random way, but they are eventually structured into the main chain. This
metric indirectly shows the finality and consistency of a blockchain system.

Figure 1. Topology Patterns

Then, we identify six types based on the combinations of the options in each
metric. We collect 30+ DAG-based blockchains systems (from 2011 to date) and
classify these systems into the aforementioned types. Detailed classifications
are shown in Table.2.

  * $\diamond$

$(\widehat{D},1^{od})$. For better understanding, we describe the situations
with terms frequently used in blockchain. This type means the data structure
is blockless and the topology is a natural graph. Transactions are in equal
and fair entities. Exemplified systems include IOTA (popov2016tangle, ),
Graphchain (boyen2018graphchain, ) and Avalanche (rocket2019scalable, ). We
denote this type as Type I.

  * $\diamond$

$(\widehat{D},2^{od})$. Transactions needed to be organized in blocks for
packaging, and the topology is a natural graph. Exemplified systems contains
Spectre (sompolinsky2016spectre, ), Phantom (sompolinsky2020phantom, ) and
Meshcash (bentov2017tortoise, ). This type is denoted as Type II.

  * $\diamond$

$(\widehat{P},1^{od})$. The data structure is blockless, and transactions are
maintained by individual nodes which form multiple parallel chains.
Exemplified systems cover Nano (lemahieu2018nano, ), Hashgraph
(baird2016swirlds, ), DLattice (zhou2019dlattice, ), Jointgraph
(xiang2019jointgraph, ), Chainweb (will2019chainweb, ), Aleph
(gkagol2019aleph, ), Vite (liu2018vite, ), Caper (amiri2019caper, ) and
Lachesis-class protocols (Choi2018OPERARA, )(choi2018fantom, )
(Nguyen2019ONLAYOL, )(Nguyen2019StakeDagSC, )(Nguyen2019StairDagCV, ). This
type is denoted as Type III.

  * $\diamond$

$(\widehat{P},2^{od})$. Transactions are structured in blocks to form parallel
chains. The systems include Prism (bagaria2019prism, ), OHIE (yu2020ohie, ),
Shpnix (wang2021weak, ), Blockmania (danezis2018blockmania, ), Blockclique
(forestier2018blockclique, ), Eunomia (niu2019eunomia, ), Dexon
(chen2018dexon, ) and PARSEC (chevalier2019protocol, ). We denote this type as
Type IV.

  * $\diamond$

$(\widehat{C},1^{od})$. The data structure is blockless, and transactions
converge into the main chain. Examples are Byteball (churyumov2016byteball, ),
Haootia (tang2020haootia, ) and JHdag (he2019consensus, ). The type is denoted
as Type V.

  * $\diamond$

$(\widehat{C},2^{od})$. Transactions are structured in blocks with the main
chain. The systems include GHOST (sompolinsky2015secure, ), Inclusive
(lewenberg2015inclusive, ), 3D-DAG (wang20213ddag, ), Conflux (li2018scaling,
)(li2020ghast, )(li2020decentralized, ), CDAG (gupta2019cdag, ) and StreamNet
(yin2019streamnet, ). We denote this type as Type VI.

Compared with Previous Classification. Previous classifications are coarse-
grained that make newcomers confused, such as the blocklattice mentioned in
(chen2018dexon, ), blockDAG in (forestier2018blockclique, ), GHOSTDAG in
(sompolinsky2020phantom, ), Lattice-based DAG in (natoli2019deconstructing, ),
etc. We observe that the gap is caused by the lack of classification metrics
or dimensions. We, instead, classify existing systems in fine-grained forms by
two dimensions (the topology made by edges, the units that indicate
structures). With this in hand, we find that so-called TxDAG/blockDAG are
named by their unit representations, while the terms GHOSTDAG/TreeDAG are
based on their topology. Our classification method, naturally, leads to the
fact that each term in previous classifications maps more than one type in
ours. For example, Lattice-based structure (equiv. parallel-chains) covers
Type III/IV defined in our method.

###  3.4. Key Parameters of the Structure

We capture several qualitative metrics as the basic terminologies to describe
the systems. In contrast, we omit the quantitative parameters (such as
confirmation time, transaction fees, propagation time). These parameters can
hardly be estimated due to the absence of implementations.

  * -

In/Out degree, denoted as $(|In|,|Out|)$, describes the number of connections
of each unit. Equivalently, the in-degree $|In|$ represents the number of a
certain unit’s successors. The out-degree $|Out|$ shows the number of a unit’s
ancestors.

  * -

Transaction model describes how to complete a transaction. Two main model
types have been identified. UTXO (nakamoto2008peer, ) stands for the unspent
outputs. The transaction in UTXO model is atomic and unsplittable. Every
operation has to be completed through these transactions. Account model
(wood2014ethereum, ) maintains the balance field in its data structure.
Transactions are completed via the changes in the user’s balance. The user
modifies its data in the local view and then synchronizes it to the network.
Additionally, in several cases (e.g., (lemahieu2018nano, )), a complete token
transfer, relying on the so-called pair model, consists of two closely coupled
transactions: a “send” transaction signed by the sender and a “receive”
transaction by the receiver. These two transactions are required to occur
within a negligible time interval.

  * -

Confidence is a cumulative number that is used to show the confidence of a
unit being verified by subsequent units both directly and indirectly. It also
reflects the probability of a unit that will be selected in the next round.
The parameter can be instantiated as different forms in the systems, such as
the cumulative weight in IOTA (popov2016tangle, ) and the witness in Hashgraph
(baird2016swirlds, ), the score in Phantom (sompolinsky2018phantom, ).

  * -

Identifiers are used to identify the unit in the network. Each system has its
customized parameters. These parameters include: height ($h$) represents the
length of a path, where the path starts from genesis transaction to a
specified transaction; depth ($d$) means the longest reverse-oriented path,
starting from the tip222A tip transaction indicates the latest transaction
that is involved in branches. transaction to a certain transaction; chain
index ($i$) identifies the chain with an index number when multiple chains
coexist in the network; logic clock ($t$) plays the role of capturing
chronological and causal relationships.

Here, we provide details of types, In/Out degree and transaction model in
Table.3 to describe the system structure. Confidence and identifiers will be
mentioned when discussing mechanisms and properties in latter sections.

Table 2. Identified Types with Corresponding Systems

|  $\widehat{D}$ivergence |  $\widehat{P}$arallel |  $\widehat{C}$onvergence
---|---|---|---
$1^{od}$ | IOTA(popov2016tangle, ), | Nano(lemahieu2018nano, ), Hashgraph(baird2016swirlds, ), DLattice(zhou2019dlattice, ), Jointgraph(xiang2019jointgraph, ), | Byteball(churyumov2016byteball, ),
Graphchain(boyen2018graphchain, ), | Chainweb(will2019chainweb, ), Aleph(gkagol2019aleph, ), Vite(liu2018vite, ), Caper(amiri2019caper, ), | Haootia(tang2020haootia, ),
Avalanche(rocket2019scalable, ) | Lachesis(Choi2018OPERARA, )(choi2018fantom, )(Nguyen2019ONLAYOL, )(Nguyen2019StakeDagSC, )(Nguyen2019StairDagCV, ) | JHdag(he2019consensus, )
(Type I) | (Type III) | (Type V)
$2^{od}$ | Spectre(sompolinsky2016spectre, ), | Prism(bagaria2019prism, ), OHIE(yu2020ohie, ), Shpnix(wang2021weak, ), Blockmania(danezis2018blockmania, ), | GHOST(sompolinsky2015secure, ), Inclusive(lewenberg2015inclusive, ), 3D-DAG(wang20213ddag, )
Phantom(sompolinsky2020phantom, ), | Blockclique(forestier2018blockclique, ), Eunomia(niu2019eunomia, ), | Conflux(li2018scaling, ), CDAG(gupta2019cdag, ),
Meshcash(bentov2017tortoise, ) | DEXON(chen2018dexon, ), PARSEC(chevalier2019protocol, ) | StreamNet(yin2019streamnet, )
(Type II) | (Type IV) | (Type VI)

##  4\. Consensus of DAG Systems

This section aims to explain consensus in a simple way through the
deconstruction. We present several key aspects of discussion in consensus
mechanisms and provide the details of each system. Then, we further conclude
technical features and give our discussions.

###  4.1. Deconstructed Components.

Achieving the consensus considers three aspects: a) who conducts the
consensus? b) how do they operate? and c) what is the technique? We answer
questions by presenting consensus mechanisms of each system (summaries in
Table.3). Specifically, we deconstruct the consensus into several decoupled
components for a better understanding of different systems and capture their
commons. The nodes that can conduct the consensus procedures make up a
consensus group, called the committee. Openness indicates whether this
committee is open to every node. Membership selection defines the rules of
becoming a committee member. Unit allocation, unit positioning, extension rule
and conflict solving determine the methods to reach the agreement. Technical
feature highlights the distinguished techniques in each system. Further, we
provide discussions from perspectives of key techniques and consensus
algorithms that are frequently utilized in systems.

  * -

Openness indicates whether an arbitrary node can run the consensus algorithm
without permission. Two types of selections are included, namely
permissionless and permissioned. A permissionless DAG system means every node
can join/leave the committee without restrictions. The size of the committee
is dynamic. A permissioned DAG system means the new-coming nodes are required
to obtain permission when joining the committee. The permitted conditions are
unusually predefined by founder teams or core members. The size of the
committee is fixed.

  * -

Membership selection defines the rules that are used to select the nodes into
the committee. For a permissionless system, every node can participate in the
competition for producing units. Nodes are ranked for priority according to
their owned resources. The resources includes computing work (Proof of Work,
PoW), stake (Delegated Proof of Stake, PoS/DPoS), vote (voting for favorable
nodes, Elect). The node that holds/obtains the most resources has the highest
probability to win the competition. For a permissioned system, nodes have to
prove the fact that they can meet the predefined rules. The committee
membership is designated by their developing teams (Assign).

  * -

Unit allocation is a prelude for consensus. Units in this step are required to
be allocated with an identifier (Role) or a destination (App, Chain). The
identifier refers to the unit that need to play a specific role with
responsibilities for tasks. The destination indicates that a newly appended
unit is uniquely allocated to a specific place, instead of broadcasting to the
network. This design arranges the units into isolated zones in advance to
reduce potential conflicts. The option App refers to a unit that is allocated
to a specific application, whilst Chain represents a unit that is allocated
(randomly or by certain rules) to a certain chain among all chains.

  * -

Unit Positioning is a way to locate the unit in the network. This step is
essential to sort the units into a total linear order. In classic blockchain
systems, locating a block can reference the parameter of height ($h$).
However, locating the unit in DAG systems is hard. For the systems based on
Topology $\widehat{D}$, unstructured units make it almost impossible to
precisely locate the unit in the expanding network. Only when the units are
sorted into a linear sequence and buried deep enough, a unique location in the
form of height ($h$) is obtained. In contrast, for the systems based on
Topology $\widehat{P}$, chains with unique indexes ($i$) are structured in
parallel. A unit can be positioned via the orthogonal parameters $(i,h)$.
Similarly, for the systems based on Topology $\widehat{C}$, any unit can be
roughly located by key blocks for the first step on the main chain, and then
be precisely searched inside these blocks by sub-parameters like hash,
timestamp.

  * -

Extension rule empathizes how to extend the chains/graphs and break ties. Tie-
breaking occurs when equivalent forks (subgraphs) compete for one winner,
which is essential to maintain consistency by deleting the overlapped branches
and reducing the data overburden. Extension rules conclude the main consensus
mechanisms. Feasible methods includes Nakamoto consensus ($NC$) by the longest
chain, variant Nakamoto consensus (variant-NC) by the heaviest weighted sub-
tree, asynchronous Byzantine agreement (async-BA), classic PBFT protocols
(PBFT) and its variation (smpl-PBFT), tip selection algorithm (TSA), some
special algorithms like greedy algorithm (GA), recursive traverse algorithm
(RTA) and sampling algorithm. For the systems without explicit rules, we use
natural to denote the case.

  * -

Conflict solving presents a set of parameters that determine the priority of
conflicting units. The parameters include three types: a) the confidence of
each unit, instantiated by the forms of weight, confidence, fee, score,
fitness; b) the random beacon like Hash; and c) a natural sequence, containing
logic clock, appearance and rank. Sometimes, the decision is made by powerful
authorities such as the leader and coordinator. We denoted them as the trusted
roles (TRs). Additionally, conflict solving differs from tie-breaking in their
scope of adoption. Tie-breaking happens at the level of (main) chains, whereas
conflict solving impacts on every single unit and mostly happens in the
sorting algorithm with the aim to order units in linearization. In several
systems, both tie-breaking and conflict solving are integrated into the
extension rule. The consensus mechanism, by this way, reaches the agreement in
one-step.

  * -

Technical feature provides the techniques that are different with other
systems. We highlight one main feature of each system to distinguish them from
peers.

###  4.2. Consensus Algorithms in Each Type.

This subsection provides our reviews of the consensus mechanisms of current
DAGs. We mainly analyze them in the view of our identified types, which helps
to find some insights.

Consensus on Type I. Type I systems are blockless. The topology of
transactions is a natural expanding graph. This type of systems include IOTA
(tang2020haootia, ), Graphchain (boyen2018graphchain, ) and Avalanche
(rocket2019scalable, ).

IOTA (popov2016tangle, ) is a permissionless network where each node can
freely participate and leave it. IOTA adopts the UTXO model as the data
structure. This design makes IOTA establish the system through transactions.
The transactions issued by nodes constitute the site set of the tangle, which
is the ledger for an up-to-date history of transactions. All nodes in an IOTA
network store a copy of the tangle and reach a consensus on its contents.
Specifically, the extension of the tangle follows the rule333It should be
noted that, at the current stage, IOTA relies on a central coordinator
(coordnator, ) issuing milestones to periodically confirm the transactions for
stability. They claim the coordinator will be removed in a short future time.
where one tip (pending/unapproved transaction) is required to approve two
ancestor transactions. Thus, users who issue a transaction will contribute to
the security of the system. However, as tips are continuously generated and
attached to the tangle, formed sub-graphs inevitably spread in different
directions. To prevent the network from splitting into isolated cliques, tip
selection algorithms are essential for stability. The algorithms help to
maintain a uni-direction graph by controlling the way to select tips. Three
types of mechanisms are provided in (popov2016tangle, ): uniform random,
unweighted random walk and weighted random walk. All these mechanisms are
based on statistical probability to simulate real scenarios. The most advanced
mechanism is a weighted random walk algorithm, which is an application of
Markov Chain Monte Carlo (MCMC) algorithms. MCMC could be transformed into
other strategies through $\alpha$, a configurable parameter used to control
the effectiveness. When $\alpha$ converges towards $0$, tip selection becomes
uniformly random; while towards $1$, tip selection becomes deterministic.
Additionally, we introduce two types of modified tip selections as
improvements:

  * •

G-IOTA (bu2019g, ) modifies the rule (the weighted random walk tip selection
rule) that a tip can approve three ancestor transactions at one time, instead
of two. The extra one selects a left-behind tip in the tangle, used to
increase the fairness in terms of transaction confidence for all honest
transactions. The algorithm allows left-behind tips to regain the opportunity
to be approved by incoming tips. G-IOTA further discusses the incentive
mechanism to punish conflicting transactions and introduces a mutual
supervision mechanism to reduce the benefits of speculative and lazy
behaviors.

  * •

E-IOTA (bu2019metamorphic, ) propose a parameterized algorithm to provide the
randomness for tip selection. The algorithm sets two specific parameters
$p_{1},p_{2}$ where $0<p_{1}<p_{2}<1$. When appended to the network, a tip
generates a random number $r$ where $r\in(0,1]$ to decide which types of
mechanisms to conduct: $r\in(0,p_{1})$ – uniformly random selection;
$r\in[p_{1},p_{2})$ – low $\alpha$ weighted selection; or $r\in[p_{2},1)$ –
high $\alpha$ weighted selection. Thus, E-IOTA controls the distribution of
different types of mechanisms by changing the parameters $p_{1},p_{2}$. This
assists to establish a self-adjusted tangle. The algorithm suits both IOTA and
G-IOTA.

Figure 2. IOTA with its Improvements

Graphchain (boyen2018graphchain, ) is a permissionless network that has a
similar design to IOTA. Graphchain is formed by tasking each transaction to
confirm its ancestors. Specifically, a transaction must verify several (at
least two) ancestor transactions and each transaction carries a PoW of
elective difficulty. PoW cumulatively and transitively affirms the prior valid
history. In contrast, Graphchain differs from IOTA in its incentive mechanism.
IOTA removes incentives from participated nodes where all transactions are
feeless. The system progresses under the tip selection rules and is free from
the influence of incentives. Graphchain, instead, introduces an incentive
mechanism to maintain the graph. Transactions are required to post transaction
fees as the offering for collection. That means each transaction must refer to
a group of ancestor transactions to deplete their deposit (fees) when
verifying the validity. Meanwhile, ancestor transactions must have enough fees
for collection. Fees are depleted by incoming transactions from the oldest
ancestors in paths to reach a prescribed total amount. High-fee transactions
attract powerful miners working in parallel for rapid confirmation, while low-
fee transactions will finally be picked up by a small miner. Based on this
design, Graphchain makes the current transactions quickly become enshrined in
the ancestry of all future transactions.

Figure 3. Graphchain

Avalanche (rocket2019scalable, )(rocket2018snowflake, ) is a permissionless
system based on a new type of approach to reach the consensus. Deviating from
BFT-style and Nakamoto mechanisms, Avalanche constructs its underlying
protocol called Slush, a CFT-tolerant mechanism, by capturing the concepts
from the gossip algorithm and epidemic networks. More specifically, Avalanche
randomly samples a small group of nodes to obtain their bias in a bivalent
state. Regardless of the size of the network, the size of the sampled group
ranges in a small intervals (such as from 10 to 20) to facilitate the
execution time at each round. Then, the system arguments Slush to the extended
algorithms with a series of parameters (like the single counter in Snowflake
and the confidence in Snowball) for finality and security. These parameters
assist to yield a threshold result for their historical colors via countering
the number of queries (as votes in BFT protocols). Last, the augmented
algorithm is applied to the whole network which is naturally formed in
topological DAG. Thus, the final state, represented by a color in blue (b) or
red (r), is achieved by repeated sampling of the network and customized
guidelines of bias. Avalanche also provides a demo to show the process in
visualization (demotest, ).

Figure 4. Avalanche

Consensus on Type II. Type II systems are based on blocks. Blocks are
structured as a natural expanding graph. This part includes systems of Spectre
(sompolinsky2016spectre, ), Phantom (sompolinsky2020phantom, ), and Meshcash
(bentov2017tortoise, ).

Spectre (sompolinsky2016spectre, )(Sompolinsky2017SPECTRES, ) is a
permissionless network. The key technique behind Spectre is a recursive
weighted-voting algorithm based on the precedence of blocks in the underlying
topology. The voting procedure is completed by blocks, instead of miners.
Newly attached blocks are required to submit votes for every pair of blocks,
denoted as $(x,y)$, according to their locations. The vote, $(-1,0,1)$, over
such a pair of blocks, is inherently a preference ordering of the selected
blocks, such as $x$ arrives before $y$ (denoted as $x<y$) and vice versa
($y<x$). Consequently, the final decision of the pairwise ordering is measured
in the absolute values of aggregate votes (a.k.a, weights). A consistent set
of transactions is extracted according to the majority of collected votes. The
ordering is not necessarily linearizable. This design relaxes the assumption
of the ordering where any two transactions must be agreed upon by all non-
corrupt nodes. Instead, Spectre decides its ordering only by honest nodes.
Furthermore, the block renewal rate in Spectre has to slow down, to ensure the
voting procedure has been completed by honest nodes.

Figure 5. Spectre

Phantom (sompolinsky2020phantom, ) is a PoW-based protocol for the
permissionless network. Each block in Phantom contains multiple hash
references to predecessors and referenced by multiple successors. The
protocol, firstly, identifies a set of well-connected blocks to exclude blocks
(with high probability) created by dishonest nodes. Then, Phantom utilizes a
recursive $k$-cluster algorithm (equally, a greedy approximation algorithm) to
achieve the partial ordering of the identified set of blocks (cluster) to a
full topological order. The greedy algorithm incentives selected blocks inside
the cluster while penalizing outside blocks via iterative rounds. The
parameter $k$ is used to adjust the level of tolerance of concurrent blocks.
After the sorting of blocks, transactions in blocks are ordered according to
the order of their appearance. Consistent transactions will be accepted and
confirmed as the final state. The iteration over transactions enables a total
order of the network. Similar to Spectre, Phantom also relies on honest nodes
to agree upon this robust ordering of blocks and transactions. But Phantom
differs from Spectre in that it enforces a strict linear ordering over blocks
and transactions in the network.

Figure 6. Phantom

Meshcash (bentov2017tortoise, ) is a layered DAG system that allows the blocks
to coexist at the same time. Firstly, to generate a block, the mining strategy
follows classic Nakamoto PoW computations but with the modifications where
each block: a) points to every block in the previous layer (a specified field
as round in other systems); b) points to every block with 0 in-degree; and c)
increases the counter of layer $i$ when seeing more than threshold blocks in
the previous layer. To achieve the consensus, two types of protocols are
integrated: a slow PoW-based protocol tortoise to guarantee long-term
consensus and irreversibility of blocks, and an interchangeable fast consensus
protocol hare to get quick consensus. A block belonging to which type of the
protocol depends on its appearance in the network, measured by its layer. For
blocks in old layers (earlier than $i-s$), the system follows the rules in
tortoise protocol. The protocol is inherently a leaderless BFT consensus,
which decides the consistency (be part of the canonical history) of a block
according to the weighted votes of its subsequent blocks. This protocol
guarantees a total ordering of blocks. If the same transaction is contained in
multiple blocks, the transaction appearing in an earlier block is preferred.
For blocks in recent layers (from $i-s$ to latest updates), Meshcash shifts to
the hare protocol. The protocol is an interchangeable protocol with the aim of
quickly settling down the blocks. Meshcash provides both a simple but limited-
security method and a complex but attack-resistance one by utilizing the off-
chain asynchronous byzantine agreement protocol (ABA). It enlarges the gap
between honest and bad blocks and ensures that the honest parties tend to vote
in the same direction once completing the protocol.

Figure 7. Meshcash

Consensus on Type III. Type III systems are blockless data structures.
Transactions are maintained by individual nodes and finally form multiple
parallel chains. This part includes systems of Nano (lemahieu2018nano, ),
Hashgraph (baird2016swirlds, )(baird2018hedera, ), DLattice (zhou2019dlattice,
), Jointgraph (xiang2019jointgraph, ), Chainweb (will2019chainweb, ), Aleph
(gkagol2019aleph, ), Vite (liu2018vite, ), Caper (amiri2019caper, ) and
Lachesis-class protocols (Choi2018OPERARA, )(choi2018fantom,
)(Nguyen2019ONLAYOL, )(Nguyen2019StakeDagSC, )(Nguyen2019StairDagCV, ).

Nano (RaiBlocks) (lemahieu2018nano, ) is a permissionless network with two
types of entities involved, namely account holder and representative (short
for Rpst). Account holders can select a representative to vote on their behalf
in case of offline leaves. Elected representatives serve for solving
conflicted transactions. Transactions in Nano are atomic, and an account
record all the transaction history related to himself. A complete transfer in
Nano consists of two parts – a send transaction and a receive transaction.
First, the sender creates a send transaction by referring to the latest block
in his account. At this time, corresponding amounts have been deducted from
his account. Then, the receiver creates a receive transaction by also
referring to the send transaction and the latest block in her account. When
forks occur, a representative creates a vote referencing the conflicted
transaction. Then, it starts to observe incoming votes from other
representatives. This process lasts for four voting periods and spends one
minute in total. Finally, it confirms the winning transaction with the highest
cumulative votes (weights, $w$).

Figure 8. Nano

Hashgraph (baird2016swirlds, )(baird2018hedera, ) is a permissioned network.
Each participated node maintains a separate chain, and nodes mutually interact
via the gossip protocol. The node locally creates an event to record the
history of received information. An event mainly contains three fields,
including timestamp for synchronization, transaction for trading and hash for
cross-references. Paralleled chains interact with each other based on the
design of cross-references. These references point to the latest event on his
chain, and also to the events from synchronized neighbor chains. Events
carrying the complete history of ledgers’ views are transmitted through the
gossip protocol and nodes will eventually obtain a full history. The hashgraph
achieves the consensus by a virtual Byzantine agreement consensus. One event
to be finally deemed as valid has to go through a three-stage procedure,
namely see, strongly see, and decide. Each procedure needs to collect the
votes more than a threshold — 2/3 famous witnesses, who are the proposers
elected by committee members in each round. This design simulates a
conventional BFT consensus and integrates the concepts into parallel chains.
Events, in this way, can be structured in a global total order. Meanwhile,
they are able to reach finality when consensus is completed in current rounds.

Figure 9. Hashgraph

DLattice (zhou2019dlattice, ) follows the structure of Nano and Hashgraph
where parallel chains maintained by individual nodes make up a DAG system. The
system consists of a Genesis Header and multiple nodes. Genesis Header
organizes the involved nodes in the form of Merkle Patricia Tree (MPT), whilst
the nodes mainly complete the tasks such as token transferring. Similarly to
Nano, the action of a token transferring is split into the send transaction
and the receive transaction between the sender and the receiver. If a node
observes any forks of transactions, a consensus program is launched to solve
the conflicts. DLattice uses a so-called DPoS-BA-DAG (PANDA) protocol to reach
consensus among users. DPOS provides the way of committee formation and BA
shows how to achieve consensus in their DAG. Specifically, the nodes who
satisfy the customized PoS condition are able to locally and secretly generate
their identities based on the voting power by the Verifiable Random Function
(VRF) technique (gilad2017algorand, ). After broadcasting the messages, other
nodes can verify whether an identity is selected as the consensus identity.
The consensus is divided into two phases Vote and Commit. Committee members
select a transaction to vote at the Vote phase and start the commit according
to collected votes at the Commit phase. If the count of committed votes
exceeds the threshold, the consensus reaches the current agreement.

Figure 10. DLedger

Jointgraph (xiang2019jointgraph, ) is a simplified protocol based on
Hashgraph. The consensus in Hashgraph needs at least two voting rounds for
events, while Jointgraph, instead, simplifies the voting process into one
round by introducing a powerful supervisor node. This node mainly monitors the
misbehaving nodes by replacing them with honest ones, and periodically takes
snapshots of system states to release the memory. Specifically, each event
(carrying transactions) in Jointgraph is broadcast to peer nodes through the
gossip protocol. Upon receiving the event from another member, the node will
verify its validity (signatures and hash). If all passed, the node votes the
event. The finality of this event can be confirmed if it receives more than
2/3 of all the nodes, one of them must be voted by the supervisory node. If
any conflicts happen, the supervisory node plays the role of a judge to make
the final decision. After a certain time of running, two special types of
events are issued by the supervisor node, namely the snapshot event and the
storage event. These two events are used to take snapshots and store them.
Once finishing the permanent storage, the previous memories could be released.

Figure 11. Jointgraph

Chainweb (will2019chainweb, ) is a permissionless system attempting to scale
Nakamoto consensus by maintaining multiple parallel chains. The system has two
features. On the one hand, Chainweb uses the cross-reference of hashes to
connect parallel chains. Individual chains in the system are based on a PoW
consensus that incorporates each Merkle root from others to increase the hash
rate. A block needs to reference the header of its ancestor block, and
additionally, reference the headers of peers at the same block height. Thus,
each block references all peer chains to form a weaved web according to the
base graph (Petersen graph, the graph topology of Chainweb). On the other
hand, Chainweb employs simple payment verification (SPV) proof to complete
token transfers. The procedure follows a similar approach to Nano
(lemahieu2018nano, ). Each token to be transferred cross-chain has to move
under the SPV proofs. The method forces to destroy tokens from one chain and
create equal amounts on another chain. This requires a strict assumption that
all chains can grow at a synchronous pace, and fast-growing chains need to be
periodically stalled and cleared. As a result, SPV proofs of token transfer
can only be validated until the blocks are recorded in other chains.

Figure 12. Chainweb

Aleph (gkagol2019aleph, ) is a permissioned BFT-style distributed system. The
essential idea of Aleph is learned from blockchain systems that adopt the
pattern of Type III. Specifically, Aleph modifies the classic BFT consensus by
removing the role of the leader. Instead, it enables each node to equally and
concurrently issue messages, also denoted as units. This design makes the
units able to be asynchronously and efficiently transmitted in the network.
Similar to the aforementioned systems, The units issued by the same node
naturally form a chain. The units issued by the different nodes are organized
in parallel chains and each of them is independent where they can freely
create, disseminate, and vote. The key is to build a collectively total
ordering among these units. Aleph utilizes leaderless BFT consensus to achieve
the consensus. Firstly, each unit is configured with a round number, and the
units with the round number ranging from $0,1,...,r-1$ to $r$ are collected in
a batch. The system sorts the batches in linearization according to their
round numbers. Then, the units within batches break ties by their hashes.
Next, with a uniform set of units, the system conducts the voting processes
for each unit in the set, to verify whether all nodes can see this unit. If
collecting more than $2f$ votes, the unit is deemed as confirmed and finishes
the consensus procedure.

Figure 13. Aleph

Vite (liu2018vite, ) follows the basic (lattice) structure of Nano, but
introduces a global snapshot chain to the achieve the total order sequence.
Each account in Vite individually creates transactions in parallel. A complete
transaction is split into a trading pair based on an asynchronous request-
response model, similar to the send-receive model in Nano. Transactions can be
instantly written into the ledgers without being blocked by the procedure of
confirmation. The confirmation is completed by a snapshot chain, a storage
structure to maintain consistency. Snapshot blocks play the role to store the
states (balance, Merkle root, the hash of the last block) of Vite ledgers. The
snapshot chain adopts the Nakamoto consensus to structure the blocks linearly.
The confidence of confirmation is measured by an accumulated value. The value
will increase as the chain grows. If forks happen, the snapshot chain breaks
the tie by selecting the longest-chain. Thus, the transaction is deemed valid
in a probabilistic way.

Figure 14. Vite

Caper (amiri2019caper, ) is a permissoned system with aims to support
distributed applications. The system considers both the confidentiality of
internal states generated in each application and the interoperability of
external states that come from the cross-application transactions. Ledgers in
Caper are formed as parallel chains. Deviating from the aforementioned
systems, the units are created by different types of applications, rather than
nodes. Each application maintains its view of the ledger, including both the
internal state and all external states. To achieve the consensus, Caper
introduces three consensus protocols by a separate set of orderers,
hierarchical consensus, and one-level consensus. These protocols are commonly
based on BFT-style consensus mechanisms (CFT, BFT). The mechanism is pluggable
and each application can adopt any fitted one according to the specific
scenarios. Here, we take the most complex one, hierarchical consensus, as an
example. The hierarchical consensus contains two main procedures: a) achieving
the local view consensus in each application, and b) reaching a global view
consensus across multiple applications. Every application operates its local
consensus to internally decide on a state. These states from multiple
applications are regarded as the input of the global consensus protocol. The
global consensus, then, employs an asynchronous Byzantine fault-tolerant
protocol to reach the agreement, where all states are structured in a total
linear ordered sequence.

Figure 15. Caper

Lachesis-class (Choi2018OPERARA, ), denoted by $\mathcal{L}$, is a new family
of consensus protocols, designed for distributed networks with features of
being asynchronous, leaderless, and resistant against Byzantine fault. This
family of protocols integrates a series of algorithms such as peer selection,
synchronization, block creation, and consensus. We focus on how to achieve
consensus in Lachesis. Generally, the Lachesis has two main steps that
corresponded to its hybrid structure. This structure includes two layers. The
first layer maintains the DAG structure (called the Opera chain) to enable the
parallel processing, while the second layer keeps the Mainchain to achieve a
total order of events. The bridge between these two layers is to select a set
of key events, called Atropos. A general algorithm of the Opera chain takes
multiple events (in the DAG network) as inputs and outputs a selected set of
Atropos events. Then, the algorithm of the Mainchain inputs these events and
outputs a topological ordering of events. Each node in the network will share
this sequence. Thus, all nodes have the same view of the network and the
protocol completes the consensus. Lachesis instantiates a family of protocols,
including Fantom (choi2018fantom, ), Onlay (Nguyen2019ONLAYOL, ), StakeDAG
(Nguyen2019StakeDagSC, ), and StairDAG (Nguyen2019StairDagCV, ). The
difference between these frameworks is their customized ways to implement the
sub-algorithms. More details are shown as follows.

  * •

Fantom (choi2018fantom, ) adopts the leaderless BFT mechanisms to select the
key set. In the Opera chain, firstly, several events become the root events
once collecting more than the threshold (2/3) references of previous roots.
Next, a root event becomes the Atropos event if more than the threshold (2/3)
participated nodes agree on this root event. Last, these Atropos events form
the Mainchain, a core subgraph of the Opera chain with aims to order the
events in the graph. Each Atropos events are created by adding several
parameters as their identities including frame, consensus time and Lamport
timestamp. In the Mainchain, the sorting algorithm is determined based on the
allocated identities of each Atropos event, and it follows the priorities of
a) the frame value of each Atropos; b) the consensus time when multiple
Atropos events coexist at the same frame; c) the Lamport timestamp when more
than one Atropos having any of the same consensus time on the same frame; d)
the hash value when above conditions stay same.

  * •

Onlay (Nguyen2019ONLAYOL, ) employs an online layering algorithm to achieve
leaderless BFT mechanisms. This layering provides a better structure of DAG to
select the key set. In Onlay, the protocol introduces the H-OPERA chain, built
on top of the OPERA chain. To compute the H-OPERA chain, the protocol applies
a layering algorithm, such as LongestPathLayer (LPL), to the OPERA chain. The
algorithm is inherently a list-scheduling algorithm that produces a
hierarchical graph with the smallest possible height. A group of Atropos
events is, as a consequence, selected to be the key set. As for the Mainchain,
the protocol orders the Atropos vertices based on priorities of a) their
layer, b) Lamport timestamp, and c) hash information of the event blocks.

  * •

StakeDAG (Nguyen2019StakeDagSC, ) adopts the PoS mechanism to select the key
set, instead of BFT-style protocols. Three steps are included in the Opera
chain: a) initialize accounts with stakes, b) compute the validation score of
an event, and c) assign weights to new roots. Correspondingly, confirming
whether some block is a root in StakeDag is different from that in Fantom:
StakeDag requires more than 2/3 of the validating power (total stakes) while
Fantom requires more than 2/3 of the total number of nodes. The key set is
obtained by such a procedure. The following sorting algorithm in the Mainchain
is similar to which in Onlay.

  * •

StairDAG (Nguyen2019StairDagCV, ) builds on top of StakeDAG with the
difference to distinguish participants into validators (high stake) and users
(low stake) by their stake. Validators can expose more validating power to
complete the onchain validation for faster consensus, while users can
participant in the system as observers or monitors to retrieve DAG for post-
validation. Both of them create and validate event blocks and maintain a DAG
network. Similar to calculating the stakes in StakeDAG, each event in StairDAG
is associated with a validation score, which is measured by the total weights
of the roots reachable from it. The key set is obtained when events have been
validated by more than two-thirds of the total validating power in the OPERA
chain. After that, the sorting algorithm is launched in the same way as
StakeDAG.

Figure 16. Lachesis-class Protocols

Consensus on Type IV. Type IV systems are block-based structures. Blocks are
maintained by individual nodes. This part includes Prism (bagaria2019prism, ),
OHIE (yu2020ohie, ), Sphinx (wang2021weak, ), Blockmania
(danezis2018blockmania, ), Blockclique (forestier2018blockclique, ), Eunomia
(niu2019eunomia, ), Dexon (chen2018dexon, ), and PARSEC
(chevalier2019protocol, ).

Prism (bagaria2019prism, ) is designed in a similar parallel chain approach.
Prism decouples the functionalities of Nakamoto consensus into transaction
proposing, validation and confirmation, and utilizes three types of blocks to
take these functionalities. Blocks are hence divided into transaction block,
voter block, and proposer block. Transaction blocks only generate and carry
transactions, acting as the fruit in FruitChain (pass2017fruitchains, ). Voter
blocks are used to vote for the proposer blocks and specify a leader block
according to their heights. Proposer blocks will pack these transaction blocks
and extends the chain under the longest-chain rule. The leader (winning miner)
confirms the integrity and validity of transactions to form the final ledger.
These three types are relatively independent but as well as interacted with
each other. Miners will simultaneously work on one transaction block, one
proposer block, and multiple voter blocks. A block to be allocated with which
type of functionalities depends on a random hash value when the block is
successfully mined. In Prism, transactions are confirmed before being ordered,
and unrelated ones are simultaneously processed. Meanwhile, a leader block
will not be stopped by waiting for its voters becoming irreversible since
reverting a majority of voter chains in a short time interval spends much more
computing power than reverting one voter chain as in the Nakamoto consensus.
Thus, Prism, armed with its deconstruction approach, separately scales each
functionality to its physical limits for maximum optimization.

Figure 17. Prism

OHIE (yu2020ohie, ) shares similarities in composing multiple parallel chains.
OHIE is a permissionless blockchain system where chains are equivalent and
symmetric. The system operates the standard Nakamoto consensus on each
individual chain and allocates each block into these chains according to their
hash values. Then, OHIE deterministically sorts the blocks to obtain a global
order across parallel chains. To achieve that, the system defines a special
tuple embedded in each block, denoted as (Rank,NextRank). The field of Rank
represents the current index of a block located on each individual chain,
while the field of NextRank specifies a reference to the next block. Here,
NextRank is used to balance the length of parallel chains in case of a huge
gap between them. It is usually pointed to the block with a high Rank. Blocks
with ranks higher than the bar are deemed as totally confirmed, otherwise are
partially confirmed. In fact, the tuple together with the chain index
inherently locates a block in the network, and their positions assist to sort
blocks in linearization. Generated blocks across parallel chains are sorted by
Ranks with a tie-breaking of chain index. Specifically, the block with a
smaller Rank number will be arranged in front of a block with a higher Rank.
This is the first priority. Then, if several blocks with the same Rank number,
the block holding a smaller chain index will take the advance. Thus, a total
linear ordering achieves by adjusting the special Rank fields.

Figure 18. OHIE

Sphinx (wang2021weak, ) introduces a weak consensus mechanism to relax the
requirement of strict consistency in most distributed systems. Strict
consistency indicates that only one block can be confirmed as valid in each
round, where most competitive blocks are afterward abandoned. In contrast,
weak consensus aims to weaken such requirements by allowing a loose
consistency: only the relative positions between two blocks are guaranteed, no
matter how many blocks are inserted between them. For instance, in the
following figure, the proposed mechanism only ensures the sequence of (B1-¿ B2
-¿B3) in peer nodes. It is also correct when inserting other blocks between
these blocks like (B2 -¿ A3 -¿B3) in A or (B2 -¿ D1 -¿B3) in D. Weak consensus
is a variant of PBFT protocol, changing the leader-based protocol to a
leaderless protocol. All the committee nodes maintain their chains and
independently process received transactions. From a system perspective, the
transactions are executed in parallel and the performance and scalability are
thus improved. Based on this concept, the authors apply the weak consensus to
a blockchain system called Sphinx. The implementation contains other
underlying components covering the P2P network, account, incentive model, etc.

Figure 19. Sphinx

Blockmania (danezis2018blockmania, ) is a BFT-style protocol which mainly
bases on PBFT (CastroL99, ). Blockmania simplifies the PBFT protocol by a)
deciding on a position rather than a sequence number. The position of a block
is denoted as $B_{n,k}$, where $n$ is the index of nodes and $k$ is the height
of blocks emitted by the node; b) becoming leaderless which is egalitarian for
involved nodes; and c) removing several complex procedures like
“checkpointing”. Nodes in Blockmania separately create blocks by themselves
and jointly form the DAG network. Here, each node can only propose one block
for the given position without any equivocation. Then, the modified PBFT
consensus is executed by these nodes in parallel and a decision is required to
execute a classic three-stage (pre-prepare, prepare, commit). Besides, an
incentive mechanism, as another essential factor, is introduced to sort
transactions in the total order. To solve potential conflicts, each
transaction included in a block will be associated with both the height of the
block $k$ and deposited fee $\phi$. Clients who expect a priority of
confirmation can send transactions in earlier rounds or spend higher fees.
Upon reaching a decision from sufficient blocks (2/3 threshold), transactions
are sorted across parallel nodes according to the tuples $(k,-\phi)$.
Alternatively, fees-based tiebreakers may also be replaced by a traditional
way — by the value of their hashes, as used in Hashcash (back2002hashcash, ).
Note that, the formed DAG system is interpreted as a state machine that
contains the blocks. Each state machine carrying the interpreted information
(view number, a count for prepare and commit messages, stored in square blocks
in Fig.20) will be sent and received through blocks. In real network
communication, only the blocks are broadcast to peers.

Figure 20. Blockmania

Blockclique (forestier2018blockclique, ) shares a similar design of the
parallel-chain model, though it names with multi-thread. The system is a
permissoned protocol that adopts the proof of ownership of a resource (PoR,
including PoS, PoW, etc.) to select its committee members. The selected
members take responsibility for creating blocks. Then, Blockclique allocates
the received transactions separately into different chains according to their
hashes. The transaction sharding avoids incompatibility when blocks are
produced in parallel. A block in Blockclique can only pack the transactions
with input addresses assigned to this thread, whereas the outputs can point to
any thread. Thus, the links between blocks make different threads connected.
Meanwhile, Blockclique embeds a scalar fitness value for each block to measure
the required resources. The fitness is calculated by the total number of
involved addresses during the block creation. To achieve the consensus,
Blockclique identify two types of incompatibility cases, namely transaction
incompatibility and grandparent incompatibility. Transaction incompatibility
represents the conflict transactions that reference the same parent in one
thread, while grandparent incompatibility means the grandparent references of
two blocks are reversed across different threads. Then, avoiding incompatible
cases, the system recursively searches for the maximal clique of compatible
blocks according to total fitness values contained in blocks. If two cliques
hold the same fitness values, the clique with the smallest sum of block hashes
is preferred.

Figure 21. Blockclique

Eunomia (niu2019eunomia, ) is a permissionless system with multiple parallel
chains. The system achieves the consensus by the following steps. Firstly, to
avoid the conflicts of transactions, Eunomia utilizes a fine-grained UTXO
sharding to avoid double-spending. A transaction can only take the UTXOs with
the same sharding index as input and generate the output UTXOs with random
indexes ranging from $0$ to $m-1$. Then, to package these cross-reference
transactions, miners adopt the m-for-1 PoW mechanism (garay2015bitcoin,
)(fitzi2018parallel, ) where they can simultaneously create blocks on $m$
chains, but a block only extends one chain for each time. Generated blocks
across $m$ chains are sorted by their logical clocks with a tie-breaking of
chain index. Specifically, each chain in Eunomia is identified by the chain
index $i$, and the blocks in individual chains are measured in a virtual
logical clock $v$, as a counter for increments. Since each chain maintains a
local state of the clock, nodes need to involve a hash reference of the
updated blocks to synchronize clocks across different chains. The block with
the largest $v$ can be recognized in priority. Here, $v$ indicates the epochs
to provide separated time slots as mentioned in other protocols
(li2020decentralized, )(gupta2019cdag, ). Thus, the ordering algorithm based
on such positions $(i,v)$ sorts the blocks in the priorities of a) the virtual
logical clock $v$ and b) the chain index $i$.

Figure 22. Eunomia

Dexon (chen2018dexon, ) is a permissioned system. The system is maintained by
two special sets of nodes: the CRS set to generate public randomness and the
notary set used to propose blocks. Dexon confirms each parallel chain through
the reference field called ack, and determines the global order through these
references. Specifically, the consensus of Dexon consists of four steps: a) To
avoid the waste of space utility of blocks, Dexon makes each transaction only
be packed into one single chain according to the residue of its hash value.
This design acts as a load balance to schedule the incoming transactions to
the individual chains. b) Upon receiving transactions, every single chain
individually generates blocks and achieves consensus by employing the
technique of a modified Algorand (gilad2017algorand, ) (mainly VRF) scheme.
Nodes in CRS set periodically generate updated common random numbers to
maintain the variations in each epoch. c) The involved chains form the
blocklattice, and each node executes the total ordering algorithm with this
blocklattice as input. The output is a globally-ordered compaction chain with
all blocks sorted in linearization. d) The compaction chain applies the
timestamping algorithm to compute the consensus time for each block. Then, the
consensus timestamp, the height of blocks, and the threshold signature
together determine a unique block in the compaction chain. Thus, the validity
of the block can be further verified by the following blocks.

Figure 23. Dexon

PARSEC (chevalier2019protocol, ) is a permissioned protocol with the creation
of an asynchronous BFT mechanism that is resilient to 1/3 byzantine nodes. The
protocol follows the main concepts from Hashgraph (baird2016swirlds, ), where
involved nodes spread their events via the gossip algorithm and the consensus
of these events is completed by virtual voting. PARSEC deviates from Hashgraph
in that PARSEC additionally defines a new type of data structure called stable
block. The block inputs a selected set of events after the virtual voting in
the graph and sorts them in linearization. Then, it finds the next valid block
according to the votes from events. The stable blocks record an order of
events that all nodes agree upon, which can also be regarded as periodical
checkpoints to confirm the states of the network. The consensus of PARSEC
requires two steps: obtain a set of valid events from its graph network and
sort the selected events and find the next block. For the first step, we
narrow the focus down to its graph network. In PARSEC, the nodes execute the
virtual voting algorithm to decide the qualification of events. The algorithm
has two similar procedures as Hashgraph, namely see and strongly see, to
collect the votes (in the form of binary values). The event that receives more
than the supermajority (2/3 of total nodes) is considered to be qualified in
the next step. Here, the virtual voting elects a set of events agreed upon by
all the nodes as a temporary agreement. Next, for the second step, we focus on
the operation surrounding blocks. The key point is to achieve a consensus on
both selected events and the next block without any conflicts. The algorithm
considers the following three aspects: a) multiple events in the same
individual chain are sorted according to their appearance, measured by the
embedded counter; b) conflicting blocks seen by multiple events are elected by
their collected votes; and c) the tiebreaker is based on the lexicographical
sequence.

Figure 24. PARSEC

Consensus on Type V. Type V systems are blockless. Appended transactions
gradually converge into the main chain. This part includes the systems of
Byteball (churyumov2016byteball, ), Haootia (tang2020haootia, ) and JHdag
(he2019consensus, ).

Byteball (churyumov2016byteball, ) is a permissionless network. Byteball
organizes units (transactions) in the graph topology but later forms a main-
chain with the help of trustful and reputable witness nodes. These nodes
distinguish common nodes by periodically generating witness units. Each unit
is marked with an index called Main Chain Index (MCI) that links to a
witnessed unit. Conflicting states are resolved by MCI, where the unit with
the lower MCI is deemed valid and the higher one fails. If both nonserials
hold the same MCI, a tiebreaker rule is applied that the unit with the lower
hash value (as represented in base64 encoding) is deemed valid. In Byteball, a
total of 12 witnesses are selected to protect against the occasional failures.
Witnesses can be replaced by common nodes, who change with better candidates
in his list. But the changes happen only gradually since the majority of users
are required to achieve an agreement on a new candidate.

Figure 25. Byteball

Haootia (tang2020haootia, ) is a permissioned network that consists of three
types of roles, transaction proposers, miners, and committee members.
Transaction proposers can only send/synchronize transactions; miners can
dynamically become the committee members by solving the hash puzzles;
committee members are able to participate in its (intra-committee) PBFT
consensus process to decide the blocks. In Haootia, a two-layer consensus
framework is induced. The first layer embraces generated transactions and
organizes them in a naive graph topology. The second layer is a PoW-based
backbone chain with key blocks to decide the total order of transactions. PBFT
consensus runs on the backbone chains to achieve linearization by directly
sorting key blocks, where key blocks confirm the trees of attached
transactions (denoted as increment tree). Each transaction in the tree may
reference multiple ancestors. Only one reference with the smallest
lexicographic order could be saved and other parental references are erased.
Then, through concatenating the reversed breath-first traverse (RBF-traverse)
sequence of the increment trees of key nodes, Haootia achieves an append-only
total ordering.

Figure 26. Haootia

JHdag (he2019consensus, ) is a permissionless system that applies Nakamoto
consensus to the DAG-based protocol. Instead of packing a batch of
transactions, each block only contains one transaction to limit the block size
and simplify the cryptographic puzzles of PoW. Fast confirmation of blocks is
achieved without having to wait for peers (so that we categorize this system
in $1^{od}$). In JHdag, two types of blocks exist: common block for carrying
transactions and milestone block for making decisions. Becoming which types of
blocks depends on their hashes of PoW, where a common block needs 10
consecutive bits of 0 and a milestone block requires 15 consecutive bits.
Then, to create a block, each miner specifies three pointers: a) points to the
miner’s previous block to form a peer chain representing the state of that
miner; b) points to the previous milestone to form the main chain under the
longest chain rule, and c) points to another miner’s common block to enhance
the connectivity for peer chains. Each milestone block can verify multiple
common blocks surrounding themselves, and such a clique is denoted as a level
set. The level set essentially acts as the role of a (Nakamoto) block in
Bitcoin, since all blocks in the system are directly or indirectly confirmed
by the longest milestone chain. Therefore, the consensus of JHdag inherits
similar principles and properties as Bitcoin.

Figure 27. JHdag

Consensus on Type VI. Type VI systems are based on blocks. These blocks
gradually converge into the main chain. This part includes protocols and
systems of GHOST (sompolinsky2015secure, ), Inclusive (lewenberg2015inclusive,
), 3D-DAG(wang20213ddag, ), Conflux (li2020decentralized, ), CDAG
(gupta2019cdag, ) and StreamNet (yin2019streamnet, ).

GHOST, Greedy Heaviest Observed Sub-Tree (sompolinsky2013accelerating,
)(sompolinsky2015secure, ), is a permissionless network with two types of
entities, common node and miner. Each common node in the network can compete
for the rights of packaging blocks, and the winner becomes a miner by
successfully resolving a hash puzzle as Bitcoin does. GHOST introduces the
weight to measure the number of blocks in the subtree attached to each block.
The difference focuses on the extension rule: the chain grows by recursively
selecting the heaviest (weight) sub-tree, instead of the longest chain. Here,
a sub-tree is formed by blocks rooted in the same ancestors. In this scenario,
DAG topology is converged to one main chain among several growing sub-trees.

Inclusive protocol (lewenberg2015inclusive, ) is an variant of GHOST, which
allows one block to reference multiple ancestors. Only one of the referenced
blocks with the same height can be elected as the father, earning most of the
rewards, while others are denoted as uncle, sharing the rest of the rewards.
The ancestors are considered within the order of seven generations of the
chain. This design makes off-chain transactions involved in the protocol and
incentive miners continuously contribute to the network. Ethereum (Casper)
adopts this protocol in its implementation.

Figure 28. GHOST and Inclusive Protocols

3D-DAG (wang20213ddag, )(wang2019improving, ) establishes a hybrid
architecture that combines multiple sidechains for parallel processing and a
mainchain for linearization ordering. The sidechains are based on the natural
DAG topology where each transaction can reference more than one previous
transaction. In this stage, the transactions are validated by not sorted. The
“validated” means the token has been permanently spent, but unrelated
transactions cannot be compared. The “sorted” means all transactions are
linear sequences. On-top applications like the smart contract can thus be
supported. The design of the sidechain partially follows the model of IOTA
(popov2016tangle, ) but modifies with additional functions. One of the
significant differences is that every transaction has to vote for a valid
member in the main-chain. The voting procedure utilizes the VRF technique to
hide the identity of the elected leader. After that, the leader in the
mainchain launches the procedure of sorting transactions and packing blocks.
Once the block is broadcast and agreed upon by enough committee members, the
ledger achieves finality.

Figure 29. 3D-DAG

Conflux (li2018scaling, )(li2020decentralized, ) is a permissionless system
attempting to scale NC-based blockchain for fast confirmation and high
throughput. The system achieves the goal by proposing its improved protocol of
GHOST, named GHAST (Greedy Heaviest Adaptive Sub-Tree, (li2020decentralized,
)). The design introduces an adaptive weight mechanism, which enables Conflux
to switch between two strategies: an optimistic strategy (similar to GHOST)
for fast confirmation and a conservative strategy to resist the liveness
attack. Specifically, each block in Conflux has one parent edge to form a
pivot chain and multiple reference edges to operate concurrent blocks. A newly
generated block will be adaptively assigned with weights according to its past
sub-graph (a.k.a, Tree-Graph). If all ancestors in the pivot chain are secured
(with a low probability of being reversed), the system assigns 1 to the new
block; otherwise, the system assigns a block with weight $h$ within $1/h$
chance ($h$ is a protocol parameter configured as 600 (li2020decentralized,
)). Blocks with their weights are organized in several sub-trees, and the
pivot chain grows by selecting the heaviest sub-tree among them. Every block
on the pivot chain is marked with one epoch. Then, Conflux derives a total
order of blocks. The priority of sorting blocks follows the metrics: a) their
epochs, b) topological order, and c) PoW quality or block hash. Last, the
priority of sorting transactions follows a) the orders of enclosed blocks, and
b) the time of the appearance in the same block.

Figure 30. Conflux with its consensus GHAST

CDAG (Converging Directed Acyclic Graph) (gupta2019cdag, ) is a permissioned
network consisting of two types of entities, namely Colosseum and block
proposer. Colosseum is designed for permissioned blockchains where the
identities of participants are known. Members of Colosseum compete to become
the block proposer in a fair and randomized two-player game for each time slot
(contain $log_{2}N$ where $N$ is the number of participants asynchronous
rounds). These proposers partition the transactions into non-intersecting
buckets and then select a random bucket to generate blocks and disseminate
them into the network. The generated blocks are required to be consistent with
a Converging Block (C-Block), which is a collection of blocks proposed in a
time slot and works as a single point of reference for the next set of blocks.
C-Block in each slot enables the system to progress as a chain and maintains a
total ordering among blocks. Temporary forks that may frequently occur in the
formed chain are solved by using a variant of the heaviest chain selection
approach (sompolinsky2015secure, ).

Figure 31. CDAG

StreamNet (yin2019streamnet, ) adopts the concept from Conflux (li2018scaling,
) and IOTA (popov2016tangle, ) to form a permissionless network with a main
chain. The system combines the rule of tip selection from IOTA (two ancestors
are approved by one transaction) and the structure from Conflux (a pivot chain
is required to sort blocks). Specifically, StreamNet consists of multiple
machines where each machine locally creates the block and instantly broadcasts
the blocks through a gossip protocol. To achieve the consensus, a new attached
block will approve two ancestor blocks: one is deterministic, and the other is
random. The first selected ancestor is deemed as the parent block to construct
a pivot chain for the purpose of total ordering. The algorithm recursively
advances to the previous child block with the highest score child of the sub-
tree. In case of the same score between two child blocks, the one who has the
largest hash value wins. The second ancestor is randomly selected through the
technique of Markov Chain Monte Carlo (MCMC) to scale out. The random walk
starts from the genesis to the latest attached blocks. Next, a total ordering
algorithm is conducted recursively to order the blocks in previous epochs. The
algorithm breaks ties by comparing the hash of each block. Upon every machine
reaching a unified view of DAG, the globally total ordering is completed.

Figure 32. StreamNet

###  4.3. Analysis

Table.3 provides the summary of aforementioned systems. This part provides
discussions focusing on techniques and algorithms.

Techniques. We abstract technical features in each system, and some of them
are frequently adopted. Details are shown as follows.

  * $\diamond$

Cross-referencing enables chains “twisted” together for improved throughput,
high scalability, or low confirmation times. This technique enables the
systems to involve orphaned units and increase the in-degree and out-degree of
a single unit. As shown in the Table.3, we use $(x,y)$ to show that each unit
can reference multiple ancestors, as well as be referenced by multiple
successors, where $x$ and $y$ are flexible positive integers larger than $1$.
Several systems explicitly define the rules of in/out-degree, such as $(x,2)$
in IOTA, Hahsgraph (baird2016swirlds, ) and StreamNet (yin2019streamnet, ).
Furthermore, the references might be allocated with different roles, which
generally includes the parent edge and reference edges. This design is adopted
by Conflux (li2020decentralized, ) and StreamNet (yin2019streamnet, ) to form
the main chain, or by Chainweb (will2019chainweb, ) and OHIE (yu2020ohie, ) to
form parallel chains.

  * $\diamond$

Trusted authority represents the powerful authority who makes the final
decision. The authority can be instantiated as the leader in PBFT (CastroL99,
), the coordinator in IOTA (popov2016tangle, ), the snapshot chain in Vite
(liu2018vite, ), the supervisory nodes in Jointgraph (xiang2019jointgraph, ),
the representatives in Nano (lemahieu2018nano, ), the proposer block in Prism
(bagaria2019prism, ), and the witness nodes in Byteball
(churyumov2016byteball, ). Trusted authorities can either directly affect the
consensus or indirectly solve the conflicts. This technique speeds up the
confirmation of units but sacrifices the decentralization, bringing additional
risks. The adversary may launch several types of attacks against these
centralized parties.

  * $\diamond$

Pairwise vote is a $2$-for-$1$ voting selection, rather than $n$-for-$1$ in
normal voting algorithms. Each unit according to its knowledge decides one
element has a high priority than another. The procedure only guarantees
partial consistency. This technique is adopted by Spectre
(sompolinsky2016spectre, ) as the consensus, as well as by several systems to
solve the conflicts when sorting the units. Additionally, the pairwise vote
differs from the coin-flip (tanana2019avalanche, ) in their randomness.
Pairwise vote relies on the willingness and knowledge of the node, whereas
coin-flip is based on a mathematically random selection with even distribution
between two values.

  * $\diamond$

Transaction sharding is to allocate the transactions into different chains, in
advance, to prevent potential duplication and conflict in sorting procedures.
The technique is adopted by the models of parallel chains, including
Blockclique (forestier2018blockclique, ), Eunomia (niu2019eunomia, ), and
Dexon (chen2018dexon, ). In general cases, the allocation follows the rules
according to the residue of the transaction hash. Transaction sharding relies
on an implicit assumption that each transaction will be only processed by one
miner/validator in the network.

  * $\diamond$

The PoW mechanism in several DAG systems, e.g., IOTA (popov2016tangle, ), Nano
(lemahieu2018nano, ), is simply used as an anti-spam tool that can be computed
within seconds. PoW for subsequent blocks is pre-computed once the transaction
is sent. The design enables transactions instantaneous to an end-user.

Algorithms. We further discuss the consensus with the following types. This
provides a general perspective when designing and analyzing DAG-based
blockchain systems.

  * $\diamond$

Tip selection algorithm is a set of rules specifying how an ancestor
transaction selects its subsequent transactions, or how a new transaction
attaches to the ancestors. The algorithm is widely adopted by the systems in
topology $\widehat{D}$, such as IOTA (popov2016tangle, ), Graphchain
(boyen2018graphchain, ), and StreamNet (yin2019streamnet, ). The advantage of
applying TSA in DAG systems is to replace complex consensus mechanisms with
the simplest rules. This design enables higher throughput and better
scalability, and tolerable resistance against forks. But as sacrifices, they
reduce security and strict consistency to some degree.

  * $\diamond$

Recursive algorithm represents a family of algorithms that makes each round’s
outputs progressively approach stable values. Recursion obtains the result by
using functions that call themselves several times. This design is widely
adopted by consensus mechanisms to enable the disordered units convergence
into a total sequenced chain. The systems can extend the graph in a determined
way. This family of algorithms include the recursive transverse algorithm in
Spectre (sompolinsky2016spectre, )/Blockclique (forestier2018blockclique, ),
greedy algorithm in Phantom (sompolinsky2020phantom, ), and sampling algorithm
in Avalanche (rocket2019scalable, ).

  * $\diamond$

BFT-style consensus in DAG systems can be classified into three types. The
first is to directly apply the classic BFT consensus protocols (PBFT, BFT,
CFT) into the system. It requires selecting a committee in advance to operate
the consensus. The committee members are selected according to their owned
resources (PoW, PoS). The approach is adopted by the systems of Blockmania
(danezis2018blockmania, ), Dexon (chen2018dexon, ), and Haootia
(tang2020haootia, ). The second type is modifying the protocols to fit
parallel chains. It is acknowledged as async-BA, and sometimes known as
leaderless BFT protocols. The key design of this type is to remove the single-
leader related phrases from the protocols. Each chain can freely produce and
broadcast blocks and vote for anyone it favors. Any block that collects enough
(2/3 of the total) votes is deemed as confirmed. Since blocks in each chain
get confirmed and confirm peers in asynchronization, it is difficult to
achieve a global linear order. Additional techniques are required, such as
gossip by gossip in Hashgraph (baird2016swirlds, ), or the sorting algorithm
in PARSEC (chevalier2019protocol, ), Fantom (choi2018fantom, ). The third type
is integrating the former two types to form a hierarchical protocol such as
Caper (amiri2019caper, ). Classic BFT protocols are first applied to each
separated zone, and async-BA is adopted by an upper-layer protocol to achieve
the final consensus across zones.

  * $\diamond$

Nakamoto consensus and its variants are the most prevailing consensus
approaches in current blockchain systems. Classic NC selects the longest sub-
chain whilst the variant NC selects the highest weighted sub-chain. NC and
variant-NC are adopted by the systems that can form a pivot (main) chain, such
as GHOST (sompolinsky2015secure, ), Inclusive (lewenberg2015inclusive, ),
Conflux (li2020decentralized, ), Vite (liu2018vite, ), CDAG (gupta2019cdag, ),
and Prism (bagaria2019prism, ). This design relies on complex rules to extend
the chains and then sort the rest of the units in each round. NC/variant-NC
can also be applied to multiple chains that simultaneously grow, such as
Eunomia (niu2019eunomia, ), JHdag (he2019consensus, ), and OHIE (yu2020ohie,
). But singly NC/variant-NC, in this case, cannot guarantee the linear order
of units so additional techniques are necessary.

  * $\diamond$

Sorting algorithm aims to sort the units in total linear order. This is
essential to guarantee global consistency. Sorting algorithm relies on several
types parameters, including cumulative confidence like weight, score, fee,
random beacon like hash, or natural sequence like lexicographic order and
appearance. Then, the algorithm sorts the units by setting a priority among
these parameters. For example, Conflux (li2020decentralized, ) organizes the
blocks under the priorities of a) their epochs, b) topological order, and c)
PoW quality or block hash. This procedure is used as a complementary mechanism
to sort filtered units after NC or BFT protocols. Half of DAG systems apply
the sorting algorithm to their protocols for strict consistency and better
security. A linear order of units would support upper-layer constructions such
as the state-transited smart contract.

Table 3. The Structures, Consensus, Properties of DAG-based Blockchain
Systems1

|  | Structure | Consensus | Property
---|---|---|---|---
|  Types |  Unit Representation |  Topology |  In/Out Degree |  Transaction Model |  Openness |  Membership Selection |  Unit Allocation |  Unit Positioning |  Extension Rule |  Conflict Solving |  Technical Feature |  Consistency |  Ordering |  Finality
IOTA (popov2016tangle, )†‡ |  I |  Bundle |  $\widehat{D}$ |  (x,2) |  UTXO |  .less |  - |  - |  - |  TSA(MCMC) |  Weight |  Blockless |  |  |
IOTA (coordnator, )⋆ |  I |  Bundle |  $\widehat{D}$ |  (x,2) |  UTXO |  .ed |  Assign |  - |  - |  TSA(MCMC) |  TR |  Coordinator |  |  |
Graphchain (boyen2018graphchain, )†‡ |  I |  Tx |  $\widehat{D}$ |  (x,y) |  UTXO |  .less |  - |  - |  - |  TSA |  Fee |  Incentive |  |  |
Avalanche (rocket2019scalable, )†‡ |  I |  Tx |  $\widehat{D}$ |  (x,y) |  Acct |  .less |  - |  - |  - |  Sampling |  Query |  Coin-flip |  |  |
Spectre (sompolinsky2016spectre, )†‡ |  II |  Block |  $\widehat{D}$ |  (x,y) |  Acct |  .less |  - |  - |  - |  RTA |  Vote |  Pairwise vote |  |  |
Phantom (sompolinsky2020phantom, )†‡ |  II |  Block |  $\widehat{D}$ |  (x,y) |  Acct |  .less |  - |  - |  |  GA |  Score |  $k$-cluster |  |  |
Meshcash (bentov2017tortoise, )† |  II |  Block |  $\widehat{D}$ |  (x,y) |  Acct |  .less |  - |  - |  - |  async-BA |  - |  Layered ptcl |  |  |
Nano (lemahieu2018nano, )†‡ |  III |  Tx |  $\widehat{P}$ |  (1,1) |  Pair |  .less |  Elect |  - |  $(i,h)$ |  Natural♮ |  TRs |  Trading pair |  |  |
Hashgraph (baird2016swirlds, )‡♭ |  III |  Event |  $\widehat{P}$ |  (x,2) |  Acct |  .ed |  Elect |  - |  $(i,h)$ |  async-BA |  Witness |  Gsp by Gsp |  |  |
DLattice (zhou2019dlattice, )†‡ |  III |  Tx |  $\widehat{P}$ |  (1,1) |  Pair |  .less |  DPoS |  - |  $(i,h)$ |  async-BA |  - |  Trading pair |  |  |
Jointgraph (xiang2019jointgraph, )†‡ |  III |  Event |  $\widehat{P}$ |  (x,2) |  Acct |  .ed |  Assign |  - |  $(i,h)$ |  async-BA |  TR |  Supervisory |  |  |
Chainweb (will2019chainweb, )† |  III |  Tx |  $\widehat{P}$ |  (x,y) |  Acct |  .less |  PoW |  - |  $(i,h)$ |  Natural |  Length |  Cross-Ref |  |  |
Aleph (gkagol2019aleph, )† |  III |  Unit |  $\widehat{P}$ |  (x,y) |  Acct |  .ed |  Elect |  - |  $(i,h)$ |  async-BA |  Hash |  Sorting ptcl |  |  |
Vite (liu2018vite, )‡ |  III |  Tx |  $\widehat{P}$ |  (1,1) |  Pair |  .less |  Assign |  - |  $(i,h)$ |  NC |  TR |  Snpst chain |  |  |
Caper (amiri2019caper, )†‡ |  III |  Tx |  $\widehat{P}$ |  (x,y) |  Acct |  .ed |  Assign |  App |  $(i,h)$ |  async-BA |  - |  Hierarchical |  |  |
$\mathcal{L}$-Fantom (choi2018fantom, )† |  III |  Event |  $\widehat{P}$ |  (x,y) |  Acct |  .less |  Elect |  - |  $(i,h)$ |  async-BA |  Apprnce |  Sorting ptcl |  |  |
$\mathcal{L}$-Onlay (Nguyen2019ONLAYOL, )† |  III |  Event |  $\widehat{P}$ |  (x,y) |  Acct |  .less |  Elect |  - |  $(i,h)$ |  async-BA |  Apprnce |  Layered DAG |  |  |
$\mathcal{L}$-StakeDag (Nguyen2019StakeDagSC, )† |  III |  Event |  $\widehat{P}$ |  (x,y) |  Acct |  .less |  PoS |  - |  $(i,h)$ |  Natural |  Weight |  Validator |  |  |
$\mathcal{L}$-StairDag (Nguyen2019StairDagCV, )† |  III |  Event |  $\widehat{P}$ |  (x,y) |  Acct |  .less |  DPoS |  - |  $(i,h)$ |  Natural |  Weight |  $w$-Validator |  |  |
Prism (bagaria2019prism, )†‡ |  IV |  Block |  $\widehat{P}$ |  (x,y) |  Acct |  .less |  Elect |  Role |  $(i,h)$ |  NC |  TR |  Decoupling |  |  |
OHIE (yu2020ohie, )†‡ |  IV |  Block |  $\widehat{P}$ |  (x,y) |  Acct |  .less |  PoW |  - |  $(i,h)$ |  NC |  Rank |  Sorting ptcl |  |  |
Sphinx (wang2021weak, )†‡ |  IV |  Block |  $\widehat{P}$ |  (x,y) |  Acct |  .ed |  Elect |  - |  $(i,h)$ |  async-BA |  - |  position |  |  |
Blockmania (danezis2018blockmania, )†‡ |  IV |  Block |  $\widehat{P}$ |  (x,y) |  Acct |  .less |  PoS |  - |  $(i,h)$ |  smpl-PBFT |  Fee |  weak rules |  |  |
Blockclique (forestier2018blockclique, )†‡ |  IV |  Block |  $\widehat{P}$ |  (x,y) |  Acct |  .less |  PoR |  Chain |  $(i,h)$ |  RTA |  Fitness |  Tx sharding |  |  |
Eunomia (niu2019eunomia, )† |  IV |  Block |  $\widehat{P}$ |  (x,y) |  UTXO |  .less |  PoW |  Chain |  $(i,h)$ |  NC |  Clock |  $m$-for-1 PoW |  |  |
Dexon (chen2018dexon, )† |  IV |  Block |  $\widehat{P}$ |  (x,y) |  Acct |  .ed |  Assign |  Chain |  $(i,h)$ |  BA |  Apprnce |  VRF |  |  |
PARSEC (chevalier2019protocol, )† |  IV |  Event |  $\widehat{P}$ |  (x,y) |  Acct |  .ed |  Assign |  - |  $(i,h)$ |  async-BA |  LO |  Stable block |  |  |
Byteball (churyumov2016byteball, )†‡ |  V |  Unit |  $\widehat{C}$ |  (x,y) |  UTXO |  .less |  Elect |  - |  - |  Natural |  TRs |  Witness node |  |  |
Haootia (tang2020haootia, )†‡ |  V |  Unit |  $\widehat{C}$ |  (x,y) |  Acct |  .less |  PoW |  - |  $(h,i)$ |  PBFT |  LO |  Hybrid ptcl |  |  |
JHdag (he2019consensus, )† |  V |  Tx |  $\widehat{C}$ |  (x,y) |  Acct |  .less |  PoW |  - |  $(h,i)$ |  NC |  Hash |  Flexible PoW |  |  |
GHOST (sompolinsky2015secure, )†‡ |  VI |  Block |  $\widehat{C}$ |  (x,1) |  UTXO |  .less |  PoW |  - |  $(h,i)$ |  variant-NC |  Apprnce |  Earliest DAG |  |  |
Inclusive (lewenberg2015inclusive, )†‡ |  VI |  Block |  $\widehat{C}$ |  (x,1) |  UTXO |  .less |  PoW |  - |  $(h,i)$ |  variant-NC |  Apprnce |  Involve Uncles |  |  |
3D-DAG (wang20213ddag, )†‡ |  VI |  Block |  $\widehat{C}$ |  (x,1) |  UTXO |  .ed |  Elect |  - |  $(h,i)$ |  BA |  Apprnce |  hybrid ptcl |  |  |
Conflux (li2020ghast, )†‡ |  VI |  Block |  $\widehat{C}$ |  (x,y) |  UTXO |  .less |  PoW |  - |  $(h,i)$ |  variant-NC |  Apprnce |  Adaptive ptcl |  |  |
CDAG (gupta2019cdag, )†‡ |  VI |  Block |  $\widehat{C}$ |  (x,y) |  Acct |  .less |  PoW |  - |  $(h,i)$ |  variant-NC |  Hash |  C-Block CDAG |  |  |
StreamNet (yin2019streamnet, )† |  VI |  Block |  $\widehat{C}$ |  (x,2) |  Acct |  .less |  - |  - |  $(h,i)$ |  TSA(MCMC) |  Weight |  Pivot chain |  |  |

  * = totally provided (global consistency; linear sorting; deterministic finality).  = partially provided (partial consistency; topological sorting; probabilistic finality).

  * $-$ = does not provide property; $\star$ = Temporary Settings. $\natural$: This represents the tip attachment procedure without any predefined rules.

  * ${\dagger}$ = Academic documents (Preprint included) available; ${\ddagger}$ = Implementation available; $\flat$ = Patent Protection; default = Whitepaper/Concept.

  * (x,y) represents the number of in-degree and out-degree edges, satisfying $1<x\leq m,1<y\leq m$ where $m$ is the maximum number of generated units at one round.

  * $h$ = unit index/height/clock in the (sorted) chain; $(i,h)$ = the unit with index/height/clock $h$ in the $i$-th chain; $(h,i)$ = the unit $i$ inside the $h$-th block/set.

  * Abbreviation: Tx = transaction; Acct = account; ptcl= protocol; strc = structure; smpl = simple; Gsp = Gossip; Apprnce = Appearance; $w$-Validator = Weighted validator.

  * TR = Trusted Role; TRs = a small group of TR; LO = lexicographic order; MCMC = Markvo Chain Monte-Carlo (popov2019equilibria, ); Adaptive ptcl = Adaptive weighted protocols.

  * TSA/RTA/GA = Tip Selection / Recursive Traverse / Greedy Algorithm; async-BA = asynchronous Byzantine Agreement; variant-NC = NC with the weightest subgraph;

##  5\. Property Analysis

Properties reflect the inherent protocol designs. We capture three properties
related to the consensus procedure, namely consistency, ordering and finality.
Other properties (that are potentially related, but not frequently mentioned)
are omitted in this paper. In the following subsections, we respectively
provide the reasons, definitions, and analyses of these properties.

###  5.1. Properties Between BA and NC.

Byzantine Agreement (BA-style) (CastroL99, )(cachin2017blockchain, ) and
Nakamoto consensus (NC) (nakamoto2008peer, ) are the most prevailing protocols
adopted by current blockchain systems (bano2019sok, )(vukolic2017rethinking,
). BA-style protocols have been proposed to achieve consensus in the presence
of malicious nodes, where the tolerance is maximal $2/3$ of the total nodes
(CastroL99, ). NC protocols, in recent decades, stand out in one critical
aspect thanks to its remarkable simplicity. NC introduces a new method to
extend the chain – the longest subchain wins. This design breaks the
assumption in BA-style protocols that only the closed committee can conduct
the consensus. Instead, it enables all participants to get involved in the
consensus process by the ways like PoW (nakamoto2008peer, ), PoS
(kiayias2017ouroboros, ), etc (PoX). These two types of protocols are
radically different in the mechanism designs, but they follow similar rules in
properties. Here, we start our observation.

Classic BA-style protocols follow three well-known properties: ($a1$)
agreement: for a given consensus instance, if a correct node decides the block
$B$, then all correct nodes decide $B$; ($a2$) validity: if all correct nodes
propose a valid transaction before starting a consensus instance, then the
block decided in this instance is not empty; and ($a3$) termination: all
correct nodes eventually have the decisions. Nakamoto consensus slightly
modifies the definitions. Two key properties of NC protocols
(garay2015bitcoin, )(kiayias2015speed, ) are: ($b1$) persistence: if a
transaction is seen in a block deep enough in the chain, it will stay in the
position; and ($b2$) liveness: if a transaction is given as input to all
honest nodes, it will be eventually inserted in a block that is deep enough in
the chain.

Properties between $(a1,a2,a3)$ and $(b1,b2)$ are different. The difference
roots in their system formulations. The BA-style protocols rely on the
interactive model of communication, where transmitted messages need to be
responded from peers. The decision, which cannot change anymore, is completed
once enough participants agree on it. In contrast, Nakamoto consensus is based
on the non-interactive model and the states get updated in every phase. The
probability of being reversed depends on its depth. The formulation of NC
protocols shifts from the send-receive replication to state machine
replication (garay2015bitcoin, )(pass2017analysis, ). These modifications make
the above-mentioned properties presented in different forms.

However, in fact, the properties from BA and NC essentially pursue the same
goals. Firstly, the liveness property of NC $(b2)$ is phrased as chain growth
and chain quality, and a block is inserted in the chain with a negligible
probability of being reversed. As one block is sufficiently buried in the
chain, the property $a3$ and $b2$ could be regarded as approximately
identical. Several studies even provide the boundary of reversibility
(pass2017analysis, )(ren2019analysis, ). Secondly, the consistency property
($a1$ and $b1$) ensures that a system can obtain the global view of states.
All blocks see the same blocks at a specific height. Decisions in BA-style
consensus are deterministic since peers are allowed to negotiate at each
round. Decisions in NC protocols are probabilistic. The confidence increases
as the chain develop under the longest chain wins rule. Thirdly, the validity
property ($a2$) is guaranteed by the verification of hashes in each block
header, as a default setting in systems.

Their similarities enable us to inherit the common principles of both BA-style
and NC properties and also left gaps to add specialized properties concerning
DAG. Specifically, we provide three properties, namely consistency, ordering
and finality. The consistency is similar to the properties of $a1$ and $b1$,
while the finality matches $a3$ and $b2$. The property ordering is added as
the distinguished property when adapting to DAG-based blockchain systems. This
property is neglected in BA-style consensus and NC protocols due to their
implicit structure: all units in their systems must be sorted in
linearization. Details are shown in the next subsection.

###  5.2. Properties

Consistency. Scalability and performance in blockchain systems are closely
related to the requirements of consistency. Smart contract-supported platforms
rely on strict consistency. The state transition must be aligned in a linear
sequence since the state-disorder may fail operations. In comparison, some
scenarios may only require a weak assumption – partial consistency, where the
sortation happens in associated transactions, rather than all transactions. It
fits the scenarios that do not provide strict integrity, such as the proof of
existence in certificate systems, the token transferring inside organizations.
Here, we define two types of consistency as follows.

  * -

Strict consistency. Each honest node has the same decisions for a given
position on the ledger so that the units can be precisely positioned in the
system. For example, BA-style consensus and Nakamoto consensus rely on strict
consistency by default.

  * -

Partial consistency. Only associated nodes have the same view of decisions,
whereas the decisions of disjoint nodes (no intersect backward or forward) are
unknown to each other. The number of associated transactions ranges from two
(equiv. pairwise order) to multiple.

Comparison with the global view. The view of a ledger/node represents its
corresponding local state. The strict consistency does not necessarily require
an arbitrary node has a global view since the assumption of global is much
stronger than that of strict consistency. Assuming that all nodes maintain the
same ledger (like Bitcoin(nakamoto2008peer, )/GHOST(sompolinsky2015secure,
)/etc.), the property of strict consistency can be approximately regarded as a
global view because all nodes synchronize the same (latest) states that have
been agreed and synchronized to their local chains. In contrast, if every node
only maintains its own ledger (like Nano(lemahieu2018nano, )/OHIE(yu2020ohie,
)/Prism(bagaria2019prism, )/etc. in Type III/IV), the property of global views
can hardly be achieved due to the isolation of their units. But achieving
strict consistency is feasible with the help of special operations such as the
sorting algorithm.

Ordering. Ordering indicates how the units in the systems are organized.
Classic blockchain systems arrange the units in linearization as default. In
contrast, DAG-based systems break this implicit assumption by introducing the
concept of graph-based structure. Units attached to the network may form any
shapes of topologies, either the divergent graph or parallel-line graph. The
difference between DAG systems is whether they sort the disordered units into
a linear sequence with an additional step. We use the term topological sorting
to describe the systems that stay the status of disordered units. We define
two types of ordering to distinguish the desired property as follows.

  * -

Topological ordering. The topological ordering in a DAG system is an ordering
of the vertices satisfying the properties of unidirectional and cyclic as
defined in Equation 3.1.

  * -

Linear ordering. Besides satisfying the properties of unidirectional and
cyclic in topological ordering, linear ordering additionally requires the
vertices (units) in the network being ordered in a total linear sequence. BA-
style consensus and NC protocols rely on the linear sorting by default.

Approaches to achieving the linear ordering. The systems, where multiple nodes
maintain the same ledger, sort units recursively. This means the sorting
algorithm runs instantly once a unit is attached to the main chain
(Phantom(sompolinsky2020phantom, )/Aleph(gkagol2019aleph,
)/GHOST(sompolinsky2015secure, )). Every unit will be recognized with a height
or an index after the serialization. In contrast, the systems, where each node
only maintains its ledger, rely on a periodical way to sort the units. The
systems collect the qualified units (e.g. with sufficient votes) during each
time interval. Then, these units are sorted according to their confidence
(appearance time, weight, hash, lexicographical order, etc.) into a linear
sequence. The sorting algorithms also might be operated by trusted authorities
(Vite(liu2018vite, )/Jointgraph(xiang2019jointgraph, )). But in most cases,
they are embedded in the default systems.

Features of the topological ordering. Topological ordering includes all the
typologies except for linearly structured ones. The systems in Type V/VI are
inherently designed with the main chain for unit linearization. In contrast,
topological ordering appears in systems belonging to Type I-IV. We have
identified two types of topological ordering from the perspective of whether
an arbitrary unit can be traced back to the genesis unit or not. Transitive
systems includes IOTA (popov2016tangle, ), Graphchain (boyen2018graphchain, ),
etc. Otherwise, a user can only trace to a certain transaction in the graph.
This frequently appears in the pairwise-ordering systems, such as Nano
(lemahieu2018nano, ), Spectre (sompolinsky2016spectre, ) and DLattice
(zhou2019dlattice, ). The topological ordering limits the systems only suited
to support cryptocurrency networks where the global state transition is not a
necessity.

Relation with consistency. If the units in a system are organized in a linear
order, this system can achieve strict consistency. The reason is
straightforward: every unit in the formed chain can be uniquely identified and
recognized. The decision (including the history of previous states) of a
specific position is shared by all the nodes without conflicts. However, in
topological sorting, we cannot derive similar results because the properties
in each type of typology are significantly varied. We only discuss the systems
in the convergence topology. Convergence states the idea where the generated
units are expected to be close to a certain distribution. Units, being
organized in linear sequence or tending to be organized in a linear sequence,
could be denoted as convergence systems. Thus, in our classification, the
systems in Type V/VI can reach strict consistency since all units will be
eventually organized in a linear sequence.

Finality. Consensus finality (a.k.a. “forward security” (decker2016bitcoin, ))
represents the property where a confirmed unit cannot be removed from the
blockchain once successfully appended to his parent unit at some point in
time. Formally, as defined in (vukolic2015quest, ), if a correct node $i$
appends a unit $b$ to its copy of the blockchain before appending the unit
$b^{\prime}$, then no correct node $j$ can append the block $b^{\prime}$
before $b$ to its copy of the blockchain.  A block will be eventually either
fully abandoned or fully adopted. For traditional BA-style consensus, such
decisions are instantly made through two/three rounds of negotiation between
the leader and replicas. In contrast, a block in NC protocols is appended in
the chain with the risk of being reversed. The possibility is decreased along
with the increased depth that this block is being buried. We abstract two
types of finality when adapting to the DAG-based systems.

  * -

Probabilistic. The units appended to the system are always accompanied by the
risk of being reversed. The probability is inversely proportional to its
cumulative confidence (including the forms of depth/score/weight etc). The
confidence is obtained from the contributions of subsequent units.

  * -

Deterministic. The units, once attached to the system at some point in time,
will instantly and permanently get confirmed so that they can never be removed
from the system.

Comparison with liveness. Liveness, as we discussed in the previous content,
ensures that if a unit is given as input to all honest players, it will
eventually be inserted into the chain. The property of liveness focuses on the
problem: whether the systems can continuously run without crash or faults.
Network failure and malicious attacks are the two major threats against
liveness. In contrast, finality guarantees that the unit inserted in the chain
will be reversed with a negligible probability. This is equal to saying the
units are buried deep enough. The property of finality emphasizes the problem:
whether attached units are permanently valid in systems.

Approaches to achieving deterministic finality. Achieving instant and
deterministic finality relies on trusted roles (TRs) in current DAG-based
systems. TRs can be instantiated as the forms of leader, validator,
coordinator, etc. The way to elect TRs and the principles to be followed
distinguish different systems. We give several examples. Byteball
(churyumov2016byteball, ) relies on a set of reputable and honest witnesses to
determine the main chain with finality. Nano (lemahieu2018nano, ) provides
quicker and deterministic transactions by a group of voted representatives via
a balance-weighted vote on conflicting transactions. Vite (liu2018vite, )
makes assigned TR create a snapshot chain to record the transactions from
common nodes. The finality in Prism (bagaria2019prism, ) is determined by its
leading proposal blocks.

##  6\. Security Analysis

This section provides security analyses (cf. Table.6) consisting of the scopes
of attack-defending, system challenge, theoretical analysis and privacy-
preserving.

###  6.1. Attack Defending

We first conclude several mainstream attacks with their assumptions and
scopes. Accordingly, we list a few of the leading systems mentioned in the
literature as instances to show how to mitigate these attacks. A summary is
presented in Table.4.

Parasite chain attack. The attack (popov2016tangle, ) shares a similar
mechanism as selfish mining in Bitcoin (eyal2014majority, ). The attack
attempts to replace an honest subgraph with a prepared subgraph (a.k.a.,
parasite chain) for more profits. To launch the attack, an adversary secretly
generates a subgraph offline but occasionally references the main graph to
obtain a high score (equally weights/confidence/votes etc.). Then, the
adversary sends a pair of conflicting transactions separately to the main
graph and his private subgraph. He continues to work for a while ensuring that
his subgraph collects competitive scores for games. At this time, the
conflicting transaction in the main graph may get confirmed (money spent) by
several approvals from honest tips. The adversary at the same time publishes
his prepared subgraph to invalidate the main graph and wins the competition
with a high probability. Thus, a coin has been spent twice.

This attack relies on the assumption that an adversary has the sufficient
computing power to efficiently generate the units. Based on that, the attack
targets the protocols without instant finality by powerful leaders. We show
how IOTA overcomes this attack.

Instances. The tip selection mechanism plays a critical role in the security
of IOTA (popov2016tangle, ). IOTA proposes a weighted random walk (MCMC) to
adjust the transition probability by a parameter $\alpha$. Theoretically, if
$\alpha$ is high enough, the system is secure under the assumption (malicious
power $<51\%$). However, an excessively high $\alpha$ makes the main graph
become a chain, with lots of transactions being orphaned. The study of
(cullen2019distributed, ) proposes a modified tip selection mechanism to
resist the parasite chain attack. The modification focuses on the explicit
formulation of the MCMC algorithm, where they employ the derivative of
original MCMC equations, called First Order MCMC. They conduct a set of
experiments to simulate the effect on the likelihood of an MCMC walk
terminating on tips. The derivative of MCMC formulations makes the cumulative
weight on the main graph grow at a different rate. When the particle
($x$-axis) is far away from the tips, the algorithm has significant effects,
whereas the particle approaches the tips, the algorithm performance starts to
deteriorate. With the algorithm, the parasite chain grows linearly with the