rate of attackers’ computing power, whilst the main graph grows at the rate of
the rest power of the network. The parasite chain, thus, gets heavily
penalized in the modified mechanism as the power of attackers is less than
that of honest participants. Additionally, a model-based detection mechanism
against this attack in IOTA is introduced by (psdetection, ).

Spectre (Sompolinsky2017SPECTRES, ) describes a type of attack which refers to
the malicious behaviors of the miners. We classify this attack as the parasite
chain attack in our model due to their similar approaches, although Spectre
named it the censorship attack. In the normal case, miners have to honestly
verify recent blocks and immediately publish their blocks. But in this attack,
dishonest miners deliberately ignore certain blocks and transactions,
preventing the blocks from being accepted due to the lack of enough votes. The
merchants may consider the transactions contained in such blocks unsafe. This
potentially delays the acceptance rate of transactions or even invalidates the
main subgraphs. However, a successful attack requires an instant Poisson
bursts in block creation to make the blocks generated by attackers outpace
others. The honest node can extend the waiting period of accepting
transactions to minimize the probability of such bursts. The correct votes
will eventually exceed the malicious votes since honest nodes occupy the
majority. Each round of iteration strengthens the decision of correct votes
that are consistent with the majority of past blocks. Spectre provides the
experimental results, showing that the acceptance rate may decrease to some
degree when compared to situations without attack, but still at a high-speed
level.

Balance attack. The attack (natoli2016balance, ), also know as liveness
attack, aims to profitably keep several chains/subgraphs growing in the same
pace. The attack partitions the network into multiple subgraphs with balanced
computational power. An adversary leverages a dynamic strategy to wander
across those balanced subgraphs and selects one favorable fork to maximize
his/her profit. To launch the attack, an adversary imposes a (time) delay to
the subgraphs with equivalent mining power and selects one subgraph to add his
issued transactions. The miner in this subgraph performs as normal to collect
transactions for block production and offer irrevocable benefits (like
services, merchants, goods, etc.) to the adversary. In the meanwhile, the
adversary accepts the benefits while issuing conflicting transactions in other
subgraphs with additional computing power, to guarantee that he can
arbitrarily let the second subgraph outweigh the original one. The miner
dynamically maintains the balance between two (or more) subgraphs until the
miner learns the fork. Even though, the adversary is still able to invalidate
the miner’s subgraph and conduct the double-spending.

This attack heavily relies on the assumption of a powerful adversary who: a)
can split/partition the network and add the time delay; b) can temporarily and
arbitrarily wander across different subgraphs without being known by honest
miners; c) has enough mining power to extend one subgraph outweighing others.
Thus, the balance attack targets PoW-based protocols with high block
generation rates. These protocols rely on miners for block/transaction
production, which is vulnerable to powerful and strategic attackers. DAG-based
systems confront similar threats as it does in Bitcoin, especially for
protocols that stem from the Bitcoin protocol like GHOST, Conflux, OHIE,
Prism, etc. We look through how these protocols mitigate attacks.

Instances. Balance attack strategically delays the confirmation process of new
blocks, instead of reverse past blocks as it is in parasite attack. We denote
the block generation rate as $\lambda$ and the delay from an adversary is time
$d$. As claimed in (yu2020ohie, ), an adversary with little computation power
stalls the normal procedure of consensus when $\lambda d>1$.444The equation is
obtained by the following assumption: the propagation delay $\lambda$ is
larger than the block generation interval $\frac{1}{\lambda}$, where
$d>\frac{1}{\lambda}$.  To solve the issue, reducing the rate of block
generation is a reasonable way, because a higher block generation interval
makes fewer blocks attached to the system. GHOST can tolerate the attack to
some degree since the interval between two consequent blocks requires a long
time (10 minutes in Bitcoin). The waiting period limits the behavior of
adversaries who rely on delay time $d$ to launch the attack. Thus, low mining
rates of GHOST (kiffer2018better, )(kiayias2017trees, ) mitigate the
effectiveness of the balance attack.

In contrast, this attack is effective in the early version of Conflux
(li2018scaling, ). The reason (yu2020ohie, ) is due to its high throughput
where massive blocks are generated in each round. If the production of one
block requires 1 second while the propagation needs around 10 seconds, around
10 blocks are attached to the system at the approximate same time. Such heavy
pressure is imposed on subgraphs where an attacker may take advantage of the
chaos. In its updated version (li2020decentralized, ), Conflux proposes its
improved consensus GHAST (li2020ghast, ) by providing two strategies to resist
the balance attack: an optimistic strategy as GHOST and a conservative
strategy. The switch of these strategies is inherently based on an adaptive
weight mechanism. When detecting a divergence of computing power, GHAST slows
down the block generation rate by adaptively switching to the conservative
strategy. The gap between these two strategies is that only a small fraction
of blocks in the conservative strategy, instead of all, are granted weights
for further branch selection. Other blocks are deemed valid but set to zero
weight. If we only consider the weighted blocks, the block generation rate is
sufficiently low to defend the balance attack. Another critical point is how
to detect the balance attack in the network. GHAST relies on its recursive
algorithm to see whether its best child has a dominant advantage compared to t
the sibling blocks. If no advantages, the child may have conflicting views and
GHAST thinks the attack exists.

The attack is ineffective in OHIE (yu2020ohie, ) and Prism (bagaria2019prism,
) due to their distinguished designs. OHIE achieves a high throughput based on
collaborative chains. However, for individual chains, the improvement is not
significant since the confirmation of each chain still follows the Nakamoto
consensus. A miner has to solve a mathematical puzzle to generate new blocks.
Thus, individual chains have low block generation rates, which can resist the
balance attack as discussed in GHOST. Prism runs parallel chains with a
distinguishable architecture. Generally, the balance attack impedes the
confirmation of a block. But in Prism, this block is disassembled into three
types of blocks according to its functionalities. These three types of blocks
are independent of each other: the proposer blocks, which can pack the
transaction blocks, and not necessarily wait for voters blocks to become
irreversible. On the one side, a delayed transaction block will not retard the
confirmation of leader blocks. An adversary cannot succeed in adding a delay
to impede the procedure of other types of blocks. Neither, on the other side,
the adversary can hardly partition the network that contains unevenly
distributed blocks of all types. Further results on the simulation of balance
attacks are provided in (bagaria2019prism, ).

Table 4. Attacks Analysis

| Behavior | Assumption | Scope | Instance
---|---|---|---|---
Parasite Chain Attack |  Adversaries secretly generate a subgraph to replace the honest subgraph with his prepared ones for more profits. |  - Enough power to generate a parasite chain outpacing than peers - No instant finality |  Probabilistic consensus |  IOTA Spectre
Balance attack |  Adversaries partition the network into balanced subgraphs and start mining on one subgraph to invalidate another that has a deal with merchants. |  - Split/partition the network - Secretly wander across subgraphs - Enough power to extend subgraphs |  PoW-based protocols |  GHOST, Conflux, OHIE, Prism
Splitting attack |  Adversaries insert a conflicting transaction into two balanced branches to double spend the coins. |  - Enough power for balanced subgraphs - No instant finality |  Probabilistic consensus |  IOTA
Large Weight Attack |  Adversaries creates a conflicting transaction with high confidence to invalidate a recently confirmed transaction. |  - Units heavier than others - No instant finality |  Probabilistic consensus |  IOTA Conflux
Censorship Attack |  Adversaries collude enough committee members who execute the consensus to take over the system and earn profits by preventing certain transactions from being packed into blocks. |  - A closed committee - Collude the majorities - Static committee selection mechanisms |  Permissioned systems |  Prism
Replay attack |  Adversaries reuse the same address of the victims to steal users’ coins by replaying transactions multiple times. |  - Balance has to be transited - Reuse addresses |  UTXO-based systems |  IOTA
Sybil Attack |  Adversaries create massive pseudonymous identities to participate in the membership selection (to become fake miners) to conduct malicious behaviors. |  - Generate identities without any cost - Enough power to create identities |  The committee selection and block production are separate |  Blockclique, Nano

Splitting attack. In splitting attack (popov2016tangle, ), an adversary can
launch double spending between two branches with a high probability. The
adversary traverses the network to find two branches/subgraphs whose total
cumulative weights are approximative. At this time, s/he attaches a pair of
conflicting transactions in different branches to double spend the coins. The
conflicting status will maintain for the long term if the adversary
continuously sends meaningless units to keep these branches growing evenly.
The adversary, thus, can conduct malicious behaviors or gain more profits
during this interval. The attack follows a similar principle to the balance
attack but still has differences. We observe that this attack is proved to be
effective even without any explicit roles of miners. This greatly simplifies
the procedures when launching attacks. An adversary only needs to send massive
transactions to targeted branches, without any further actions to avoid
detection from miners.

This attack relies on a simple assumption: an adversary has enough computing
power to extend the targeted branches which significantly outpace peers. Thus,
the splitting attack targets the naturally expanding systems without any
explicitly powerful roles in deciding the consensus. Matched systems are
mainly Type I systems. We take the matured project, IOTA, as an example.

Instances. Tip selection rules determine the properties of Tangle in IOTA
(popov2016tangle, ). As aforementioned, when the parameter of $\alpha$
approaches $0$, the selection rule is uniformly random, while approaches $1$,
the rule adopts the weighted random walk. A uniformly random selection rule is
insecure since the adversary can easily control the branches. Therefore, to
avoid the attack, a weighted random walk with the high $\alpha$ value is
necessary. Some of the transactions are marked with weights, and attackers can
hardly keep the balance between the two branches due to the unpredictable
distribution of weights. However, a higher $\alpha$ value causes more left-
behind tips, losing the confirmation rate of transactions. This design limits
IOTA in resisting the splitting attack.

A temporary solution has been proposed by their foundation, introducing a
central coordinator (coordnator, ). The coordinator acts as an authority to
periodically (every two minutes) issue milestones for finality. The milestone
is a special transaction that confirms the ancestor transactions with a
100$\%$ confirmation confidence. Therefore, launching the attack is
impractical for adversaries. However, this approach deviates from the design
principle of IOTA, making it centralized. G-IOTA (bu2019g, ) moves the focus
back to the tip selection rules. Increased left-behind tips slow down the
confirmation rate since tips stay in low confidences where they are rarely
approved by others. G-IOTA accordingly adds one more verification edge for
each tip, pointing to the left-behind tips. This design helps to increase the
confidence of honest transactions fast, while efficiently detecting fake
transactions with low confidence for a long time. It remains a higher $\alpha$
value while simultaneously keeping the confirmation rate. Further, E-IOTA
(bu2019metamorphic, ) proposes a parameterized algorithm to adjust the
distribution among different types of mechanisms (0 $\alpha$, low $\alpha$ or
high $\alpha$). This helps to achieve the balance between security and
performance. Thus, the splitting attack against IOTA is mitigated by making it
possible to choose a moderated $\alpha$.

Large weight attack. The attack (bu2019metamorphic, ) occurs when a heavy
conflicting transaction invalidates a recently confirmed transaction. The term
heavy represents the values of measurements (score/confidence/weights etc.)
The recently means a transaction is approved by several subsequent
transactions, but actually not buried in deep. This is equal to say, the
(cumulative) weights of a recent transaction are not too much heavier than the
weights of a newly attached transaction. In a large-weight attack, an
adversary targets a recent transaction and immediately generates a conflicting
transaction. The adversary improves the weights of the conflicting
transactions by methods such as making it approved by lots of meaningless
transactions, and appending it to the main graph until it becomes heavier than
the targeted one. These two transactions belong to different paths. When an
honest transaction arrives, it cannot effectively distinguish which path is
correct. The transaction can only select the path with more weights. Since the
coins in the original path have been irreversibly spent, double spending in
the new path happens when the adversary reuses the same coins.

This attack relies on assumptions in which: a) an adversary has enough
computing power to make the conflict transactions heavier than honest ones; b)
the consensus is probabilistic without instant finality. Thus, the large-
weight attack targets the systems with probabilistic-based consensus
mechanisms. We provide examples of IOTA and Conflux.

Instances. This attack is effective in the original design of IOTA
(popov2016tangle, ). Since the tips generated by honest nodes are uniformly
distributed in the network, an attacker may need a computing power rate far
less than $50\%$ (qin2020security, ). The temporary solutions based on
coordinator (coordnator, ) shift the IOTA into a completely centralized
network, but it is indeed able to resist the attack. The improved approach
(cullen2019distributed, ) can also prevent large weight attacks to some degree
since the effectiveness of MCMC sharply deteriorate at the margin of the
tangle. This increases the randomness of the selection procedure and reduces
the probability of unluckily selecting a heavier transaction. Meanwhile, the
effectiveness of the tip selection algorithm is adjustable in E-IOTA
(bu2019metamorphic, ), which provides a similar resistance against this type
of attack.

The attack is ineffective to Conflux (li2020ghast, )(li2020decentralized, ).
The clever point is that Conflux even gets inspired by the concept of weight,
proposing its adaptive weight algorithm to make two consensus strategies
switch between each other. If an attacker generates and broadcasts meaningless
blocks at a high speed to increase one’s weight, the system switch to a
conservative strategy. This strategy only grants a small portion of blocks
with valid weights, whereas others are marked with 0 weights. The attacker
cannot control the probability of being selected. Much more power is required
if the attacker attempts to have a stable advantage. Conflux also utilizes the
adaptive weight mechanism to prevent the balance attack as discussed above.

Censorship attack. The attack (vitalik2015censorship, ) happens when the
adversaries collude enough committee members who execute the consensus. These
members may cooperatively frame certain transactions, preventing them from
being packed into blocks. Malicious collusion breaks the basic security of a
system since colluded members have taken over the system and earned profits
according to their willingness. The attack relies on the incentive mechanism.
If the members can obtain extra profits through censoring specific blocks or
transactions, more members would join the game; if they obtain the profits via
honestly mining, these members would keep honest. A positive incentive
mechanism, like relating the reward proportional to the honest members
(vitalik2015censorship, ), will help to maintain a healthy network.
Specifically, one can earn a 100$\%$ reward if 100$\%$ of members are honest;
whereas he can only obtain an 80$\%$ reward if 20$\%$ of members have
colluded. Another factor is the attack must collude all targeted members
within the time window. If the members leave the committee under the rotation
rules, the collusion is useless and costly. These examples prove that the
censorship attack is closely related to the behaviors of committee members.

The assumptions of this attack are a) the consensus is completed by a closed
committee; b) an adversary has sufficient power/stake to collude a certain
proportion of committee members, who may further attract other incomers; c)
the committee relies on a relatively static mechanism without dramatically
dynamic membership rotation. Thus, the censorship attack mainly targets the
permissioned systems whose committees are fixed. Prism is an example.

Instances. Prism (bagaria2019prism, ) provides simulation results against the
censorship attack with a tolerable threshold of $\beta=0.25$, where $\beta$
indicates the fraction of hash power used for the attack. Prism simplifies the
behaviors of attackers to slow down the confirmation by producing empty blocks
(proposer block and voter block). Empty proposer blocks may slow down the
ordering procedure of transactions since the generation of proposer blocks is
delayed. Empty voter blocks may retard the voting procedure which indirectly
affects the creation of proposer blocks. Based on simulation results, Prism
performs better than the longest-chain protocols w.r.t the censorship attack.
The confirmation delay of Prism is greatly smaller than delays in longest-
chain protocols since the actual delays are merely caused by the insertion of
empty blocks. This is the key point to resist the attack, where each decoupled
block would not hinder other types of blocks. In contrast, delays in the
longest-chain protocols would impede all the procedures.

Replay attack. The attack (Josephd018replay, ) refers to stealing users’ coins
by replaying transactions multiple times. The key to performing the attack
requires an adversary to reuse the address of the victims. Reusing the same
address makes certain transactions repeatedly confirmed and all the addresses
following this vulnerable address become vulnerable. Adversaries may drain the
funds from all transactions associated with this vulnerable address. In case
of the funds in this address is insufficient, the adversary first tops up the
address, and then replays the transaction to steal more funds until using them
up. The replay attack is mainly used for the systems based on the UTXO model,
because the remaining values have to be instantly transferred from the current
address to another new address, rather than directly being removed as it is in
the account model. Besides, two types of variants are identified. The first
one is brute force, where an adversary tries to guess the seed. But it cost
massive computing power which may not be worth it. Another type is to analyze
the past transaction to find a potential input address with remaining values.
All these variants still rely on reusing addresses.

The assumptions of this attack are: a) the remaining values of one address has
to be transited to another address; b) the address can be reused multiple time
through some technique. Based on this, the replay attack targets the systems
which adopt the UTXO model as their data structure. We take the IOTA as an
example.

Instances. IOTA (popov2016tangle, ) relies on bundle (bundle, ) to finish the
token transferring. The bundle is a virtually top-level construction used to
simulate accounts for users. Each bundle links related transactions to
complete the operations through a set of addresses generated by the same seed
from the user. Specifically, the remaining values of transactions in the
bundle need to be transferred from the current address to a new address. These
two addresses are linked by the seed. The user who holds the seed can control
transactions that relate to him. The replaying attack is feasible in IOTA
since the transaction bundle is inherently based on the UTXO model. Joseph
(Josephd018replay, ) shows the possibility of the attack, while Roode et al.
(de2018break, ) provides a practical method to conduct the attack. The method
modifies the functions (mainly addRemainder) of IOTA’s API, enabling input
address reused. The modification removes the procedure of generating remaining
funds such that the funds can stay on the input address. Fortunately, this
attack can be mitigated. As suggested by (Josephd018replay, ), each signed
transaction bundle should be tracked via its unique hash, and each subtangle
only permits one bundle. As a counterpart, this method increases the overhead.

Sybil attack. The attack (douceur2002sybil, ) is a common attack in the P2P
network which is also adaptable to the blockchain network. An adversary may
generate multiple pseudonymous identities to conduct malicious behaviors, such
as disconnecting the channel between nodes or even taking control of the whole
network. Specifically, an adversary may add a large number of pseudonymous
identities in the blockchain network to participate in the membership
selection. If one of them is luckily selected to be the committee member, s/he
can arbitrarily generate blocks that benefit himself. The fake members can
efficiently forward the block generated by adversaries whilst abandoning the
genuine blocks from users. As a result, the adversary who controls the network
finally reduces the overall throughput and obtains extra rewards. The more
fake identities are created, the larger chance they are selected. The key to
successfully launching this attack is to generate a large number of identities
with low/zero costs. Then, a malicious node will use these identities to gain
disproportionately significant influence.

The attack relies on the assumptions: a) generate identities without any cost;
b) the nodes have enough power to efficiently create identities. Sybil attack
affects the network by its generated massive identities. Current blockchains
that adopt PoS/PoW consensus effectively avoid this vulnerability since
becoming a block packager (membership selection) must simultaneously solve a
lot of puzzles (block production). Therefore, this attack mainly targets the
systems whose committee selection and block production are separate. We take
the Blockclique as an example to show how to avoid this attack in DAG-based
blockchain systems.

Instances. Blockclique (forestier2018blockclique, ) indicates that its
protocol relies on a Sybil-resistant selection mechanism. Achieving this
mechanism needs to meet two requirements: a) a valid membership of nodes must
be obtained with a sufficient cost, and b) the membership in the next round
cannot be guessed in advance. The key of the first requirement is to
explicitly select a node based on the proof of ownership of a resource: nodes
have to spend some resources and add certain delays each time participate in
the node selection. The more costs or mortgages are spent, the more reputation
a node will obtain. This increases the confidence of a node, decreasing
friction when communicating with others. The core of the second requirement is
to guarantee randomness without leakage. Blockclique utilizes an oracle to
describe the random selection of nodes. All nodes need to consult this oracle
to confirm their membership in a certain slot. To meets these requirements,
Blockclique gives two adaptable mechanisms: the PoW-based membership selection
as in OHIE (yu2020ohie, ) or ELASTICO (luu2016secure, ), and the PoS-based
selection as in Tezos (tezos, ). OHIE utilizes the residue of hash to decide
which thread it switches to. ELASTICO employs PoW to generate identities and
then select the membership randomly from those identities. Nodes in Tezos are
randomly selected with a probability proportional to their stakes. All these
selections prevent the adversaries from maliciously spawning massive nodes.

###  6.2. System Challenges

This part focuses on design considerations from the view of system level and
development feasibility.

Absent Details of Committee Configuration. Maintaining liveness and security
in committee configuration is an open and neglected issue. We observe that
current committees are formed either statically or dynamically. Specifically,
static committee configuration lacks liveness, making systems vulnerable to
attacks like the DDoS attack, Sybil attack, and censorship attack. Dynamic
committee configuration improves security by raising the bar for attacks but
brings new challenges on how to maintain liveness. It includes the frequency
and fraction of committee membership (epoch, dynamism). The property directly
relates to the committee’s security. However, the systems which seriously
discuss or comprehensively analyze the issues only make up a minority.

Absence of System Setup. Setup configuration refers to the information that
can be available at the onset of the protocol to each participant. Three types
of setup configurations are introduced in (garay2020sok, ), namely no setup,
public-state setup and private-state setup. Most NC protocols (Bitcoin, etc.)
rely on a global-viewed genesis block as the initial state, while a number of
systems (like (garay2018bootstrapping, )) need pre-existing configurations
(such as a common reference string [CRS], or a public-key infrastructure
[PKI]). In current DAG-based blockchains, some of the systems rely on the
genesis block, mainly TypeI/II/V/VI, whereas other systems simultaneously
initialize several chains in parallel, mainly Type III/IV. It is unclear how
these (parallel chain) blockchains bootstrap the systems.

Absence of Incentive Mechanism. Three major goals of incentive mechanisms are
a) letting more nodes get involved in a committee to participate in consensus;
b) encouraging honest behaviors of committee members; and c) directly
affecting consensus mechanisms, such as Graphchain (boyen2018graphchain, ).
There has been little investigation into how to build incentives for increased
participation. The absence of incentives makes it hard for committee members
to maintain the system stable since no laws guarantee they never get
compromised. Although several DAG systems claim that feeless is one of the
most outstanding advantages of DAG, they still utilize additional techniques
as complementary mechanisms. For example, IOTA (popov2016tangle, ) introduces
an authority to maintain stability.

Unknown Compatibility. Although this paper provides insights into physical
components (structure, consensus) and featured techniques (see Section 4),
there are still a large number of related components and techniques that have
a significant influence on their designs/operations. Current studies lack the
corresponding description, and we provide some instances as follows.

  * -

Smart contract is an essential component to achieve state transition in
classic blockchain systems. However, none of the state-of-the-art DAG systems
have implemented the mature smart contract. This is mainly because a complete
state transition highly relies on the total linear order of units, ensuring
the correctness and integrity of states. The systems without linear order can
only encompass auxiliary components. For example, IOTA provides a decoupled
upper layer solution (qubic20, ) as the external component.

  * -

Sharding (bano2019sok, ) splits transactions into separated zones. Several DAG
systems (Blockchique (forestier2018blockclique, ), Eunomia (niu2019eunomia, ),
Dexon (chen2018dexon, )) get inspired from the sharding technique to allocate
the transactions into different chains in advance, preventing potential
conflicts during the consensus. However, DAG systems only capture the simplest
and most straightforwards concept from sharding. The issues such as how to
fairly and randomly allocate the transaction, and how to maintain the separate
chains relatively balances, are still left as gaps.

  * -

Layer2 technique (gudgeon2020sok, ) is an upper layer solution for linear-
based blockchains. As discussed in Section 8.3, the layer2 technique
attempting to solve performance issue share lots of similarities with the DAG
approach in the perspective of system design. It is interesting to explore
whether the layer2 technique can support more applications for DAG systems,
especially the scenarios having to manage both off-chain and on-chain
transactions.

  * -

Cross-chain (zamyatin2019sok, ) enables the chains that are heterogeneously
structured able to communicate with each other. The usage of this technique
requires powerful tools such as the global clock. Traditional blockchain
systems achieve the goal of either relying on a third party as an external
clock or depending on chain-dependent time definition, such as the block
generation rate. The tools are relatively easy to implement on their (unique)
main chains. In contrast, DAG systems can hardly achieve the regiments for
cross-chain due to their inherent complex situations: they create many forks
(Type V/VI), coexist multiple chains (Type III/IV) or even without the main
chain (Type I/II). The difficulty to synchronize the information, both
internally and externally, hinders the application across chains in DAG
systems.

Deployment Difficulty. Deploying proposed DAG-based systems is hard for
developers. Most implemented systems, like (zhou2019dlattice,
)(forestier2018blockclique, ), only present the designed protocols with
incomplete evaluations, rather than releasing their source codes. A developer
can hardly learn the full logic by conditional access to the repositories.
Many systems (li2020decentralized, )(liu2018vite, ), with accessible
repositories, do not provide proper documents on guidelines or deployment.
Several systems (e.g., (baird2016swirlds, )) developed by official teams are
protected by patents. We denote them as n/a: the system can be deployed but
lacks evidence to show difficulties. The current status indicates that the
widespread usage of applications built on DAG-based blockchain systems is
still far away from reality.

Trade-off. Blockchain systems cannot improve the performance, scalability,
security, decentralization, and strict consistency at the same time. For
example, we observe that some systems, like IOTA (popov2016tangle, ),
Graphchain (boyen2018graphchain, ), improves the performance and scalability
at the expense of security and consistency. While some systems, such as Prism
(bagaria2019prism, ), OHIE (yu2020ohie, ) ensures strict consistency, but the
scalability and performance are sacrificed as a balance. In traditional
distributed systems, FLP Impossibility theorem (FischerLP85, ) and CAP
(GilbertL02, ) theorem help us understand the limitation of some factors.
However, in DAG-based systems, or even blockchain systems, there is no theorem
or experience to clarify the boundaries of each factor, the way of reaching a
balance between multiple factors, or even the range of factors that are
involved.

###  6.3. Theoretical Analysis

Formal treatment is important for system security. However, only a minority of
systems present analysis under specific models.

Informal Model. Many systems are informally presented and lack formal models
either on security or properties. This leads to confused proofs or discussions
when they claimed to be secure. Several systems are presented in a formal
manner, formalizing models consistent with their properties. Although their
models vary from system to system, we still list them as typical samples (cf.
Table.5). Besides, several studies provide analysis with formal analyses,
including topics on properties (birmpas2019fairness, ) or performance (of
parallel-chain systems) (fitzi2018parallel, ). We encourage future work to
conform to this format, enabling them to be thoroughly discussed and
critically proved.

Table 5. DAG Systems with Formal Models

| Adopted Model
---|---
IOTA (ferraro2018iota, )(popov2019equilibria, )(kusmierz2018extracting, ) | Markov Process
Avalanche (rocket2019scalable, ) | Continuous-Time Markov Process
GHOST/Inclusive (sompolinsky2015secure, )(lewenberg2015inclusive, ) | Nakamoto’s
Spectre/Phantom (sompolinsky2020phantom, ) | Self-defined
Prism (bagaria2019prism, ) | Nakamoto’s (Backbone (garay2015bitcoin, ))
OHIE (yu2020ohie, ) | Nakamoto’s (Backbone (garay2015bitcoin, ))
Conflux (li2020ghast, ) | Nakamoto’s
Haootia (tang2020haootia, ) | Crypto-style proof
Informal |  (boyen2018graphchain, )(sompolinsky2016spectre, )(lemahieu2018nano, )(bentov2017tortoise, )(he2019consensus, )(baird2016swirlds, )(xiang2019jointgraph, )(will2019chainweb, )(gkagol2019aleph, )
(choi2018fantom, )(liu2018vite, )(zhou2019dlattice, )(amiri2019caper,
)(danezis2018blockmania, )(gupta2019cdag, )(yin2019streamnet, )

Informal models lead to non-unified properties in different systems. We
mention several types of properties that defined in concurrent literature,
such as effectiveness, atomicity and timeliness in (zamyatin2019sok, );
efficiency in (birmpas2019fairness, ); liveness and correntness in
(bonneau2015sok, ); persistence and liveness in (garay2015bitcoin, ); etc.

Whitepaper Information. Whitepapers were the earliest documents to express
ideas and proposals from developers and technicians. These documents encompass
brief models, related components, and, more importantly, the developing plan,
which targets future investors. In this paper, not all the discussed DAG
systems are written in the form of academic papers. For those non-academic
documents, we only select and discuss systems with formal documents, which
present design details and technical models consistent with the literature.
Besides selected systems, a series of ever-existing projects confront the
situation of non-updating. Most of them follow similar models and we omit them
here.

###  6.4. Privacy-Preserving Properties

Privacy in classical blockchain systems (conti2018survey, ) is a complicated
issue. Generally, the privacy of blockchain systems includes two categories:
anonymity of identities and privacy of metadata. Firstly, Bitcoin allows users
to generate multiple addresses. Adversaries can obtain the link between these
addresses and user entities by collecting massive historical transactions and
analyzing the relations to pursue profits (miller2017empirical, ). Most DAG
systems following this concept will confront the same threats. Secondly, the
metadata on the ledger is shown in plaintext as default. Adversaries can trace
any interested transactions (e.g., with large balance) and conduct harmful
activities by locating their associated accounts (wang2020preserving, ).
Unfortunately, we find that none of the existing DAG-based blockchain systems
(at least till the completion of this paper) empower their system with
privacy-related properties. No (effective) privacy-preserving solutions have
been applied to DAG systems so far. Therefore, ways to properly enhance
privacy are a promising area.

Table 6. Attack Defense, System Challenge, Model Availability and Privacy1

| Type I | Type II | Type III | Type IV | Type V | Type VI
---|---|---|---|---|---|---
|  IOTA |  IOTA+ (cullen2019distributed, ) |  Graphchain |  Avalanche |  Spectre |  Phantom |  Meshcash |  Nano |  Hashgraph |  DLattice |  Jointgraph |  Chainweb |  Aleph |  Vite |  Caper |  $\mathcal{L}$-series |  Prism |  OHIE |  Sphinx |  Blockmania |  Blockclique |  Eunomia |  Dexon |  PARSEC |  Byteball |  Haootia |  JHdag |  GHOST |  Inclusive |  CDAG |  Conflux |  StreamNet
Parasite chain at. |  | ✓ |  |  | ✓ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
Balance at. |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | ✓ | ✓ |  |  |  |  |  |  |  |  |  | ✓ |  |  | ✓ |
Large Weight at. | ✓ | ✓ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | ✓ |
Censorship at. |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | ✓ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
Sybil at. |  |  |  |  |  |  |  | ✓ |  |  |  |  |  |  |  |  |  |  |  |  | ✓ |  |  |  |  |  |  |  |  |  |  |
Committee Conf. | - | - | - | - | - | - | - | dy | dy | dy | st | dy | st | st | st | dy | dy | st | st | dy | dy | dy | st | st | dy | - | - | - | - | - | - | -
System Init. | genesis unit | CRS / PKI / genesis unit | genesis unit
Incentive |  |  | ✓ |  | ✗ |  |  |  |
Compatibility (SC) |  |  |  |  |  | ✓ |  |  |  |  |  |  | ✓ | ✓ | ✓ | ✓ |  | ✓ |  |  |  | ✓ | ✓ | ✓ |  | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
Deployment | ✓ | - | n/a | - | - | ✓ | n/a | - | - | - | n/a | - | n/a | - | - | - | n/a | - | ✓ | ✓ | n/a | -
Formal Model | ✓ |  |  | ✓ | ✓ | ✓ |  |  |  |  |  |  |  |  |  |  | ✓ | ✓ |  |  |  |  |  |  |  | ✓ |  | ✓ | ✓ |  | ✓ |
Document | ${\dagger}{\ddagger}$ | ${\dagger}$ | ${\dagger}{\ddagger}$ | ${\dagger}{\ddagger}$ | ${\dagger}{\ddagger}$ | ${\dagger}$ | ${\dagger}$ | ${\dagger}{\ddagger}$ | ${\ddagger}\flat$ | ${\dagger}{\ddagger}$ | ${\dagger}{\ddagger}$ | ${\dagger}$ | ${\dagger}$ | ${\ddagger}$ | ${\dagger}{\ddagger}$ | ${\dagger}$ | ${\dagger}{\ddagger}$ | ${\dagger}{\ddagger}$ | ${\dagger}{\ddagger}$ | ${\dagger}{\ddagger}$ | ${\dagger}{\ddagger}$ | ${\dagger}$ | ${\dagger}$ | ${\dagger}$ | ${\dagger}{\ddagger}$ | ${\dagger}{\ddagger}$ | ${\dagger}$ | ${\dagger}{\ddagger}$ | ${\dagger}{\ddagger}$ | ${\dagger}{\ddagger}$ | ${\dagger}{\ddagger}$ | ${\dagger}$
Privacy | ✗

  * ✓= prevent attacks / with the property / easy to use; default (blank) = not mentioned or N/A; - = do not apply;
✗= without consideration. CRS = common reference string; SC= smart contract;
at. = attack; conf.= configuration; init. = initiation;
dy = dynamic setup; st = static setup; ${\dagger}$ = Academic documents
available; ${\ddagger}$ = Implementation available;
$\flat$ = Patent protection; default = Whitepaper/Concept; n/a = can be
deployed but lack of evidence to show difficulties.

###  6.5. Summary

Firstly, removing the leader/miner makes DAG systems vulnerable towards
attacks with intensive-computing power. The systems with natural topology
(Type I/II/V/VI) require auxiliary techniques to maintain stability and
security, e.g., the coordinator in IOTA (coordnator, ) and the mainchain in
Type V/VI systems. Secondly, building smart contracts or state transition
applications rely on linear order. The transition of states differs from the
operation of a token transfer. State transition requires multiple steps where
each state can be traced back to the initial state. In contrast, a token
transfer finishes once both the sender and receiver agree to it. Thirdly, very
few systems consider the incentive mechanisms. The systems that follows the
Nakamoto’s model (like GHOST (sompolinsky2015secure, ), Inclusive
(lewenberg2015inclusive, ), Conflux (li2020decentralized, )) inherit the
reward system of Bitcoin. This is feasible because the system still relies on
a mainchain. Other types of systems do not provide solutions on how to inspire
more participants. Next, none of DAG blockchains equips privacy-related
techniques or crypto primitives. We think the reason comes from their goals.
Improving the performance and scalability is the key target of DAG systems.
Additional privacy protocols will greatly increase the complexity and slow
down the confirmation time. Last, a universal theoretical analysis model will
not appear (at least in a short time) in DAG systems. We have identified six
types of models, but none of them can share the same model. A suitable
analysis closely depends on its design model.

##  7\. Performance

In terms of performance, we consider throughput (i.e., the maximum rate at
which values can be agreed upon by the consensus protocol), scalability (i.e.,
the system’s ability to achieve greater throughput when consensus involves a
larger number of nodes) and latency (i.e., the time it takes from when a value
is proposed, until when consensus has been reached on it). Here are the
details.

  * -

Throughput ($\lambda$) is the maximum rate of confirmed units over the
network. It is affected by various factors, including the limitations of
bandwidth, the design of consensus protocols, and the fraction $\beta$ of
(hashing power of) the adversaries. The throughput in DAG systems calculates
the confirmed total units during a specific time frame, no matter they are
collected from one single chain or multiple chains. We follow the classic
measures called TPS (Transaction Per Seconds).

  * -

Latency ($\tau$) mainly consists of two parts, the unit propagation time and
confirmation time. The propagation time is the length of time that a unit
reaches its destination. It is closely related to the parameter coverage, used
to describe how many nodes received these broadcasted units. The confirmation
time represents the length of time that a unit is deemed as confirmed. For
instant confirmation protocols (e.g., BFT-style), the consumed time is static
on average. For delayed confirmation protocols (e.g., NC-based), the time is
unpredictable. The probability $\varepsilon$ of a unit is removed by its child
will drop as the chain/graph grow. When the unit is buried deep enough, an
approximate time is obtained.

  * -

Scalability ($\phi$) shows the ability of a system to handle a growing amount
of units when adding a large number of nodes. The assumption of consistency is
the leading factor that influences the property. The strict consistency (which
requires total linear order of the units) will significantly retard the
performance since the complexity of consensus increase with the enlarged
committee. In contrast, a weak consistency can greatly scale the blockchain
due to its tolerance of forks. Other factors including the design of consensus
protocols, the fraction of malicious nodes, etc.

###  7.1. General Analysis

Performance is the bottleneck of Bitcoin due to its security limitation.
Simply increasing the mining rate can improve the performance but with the
expense of decreased security. Suppose the block creation rate of an attacker
is greater than the growth rate of the main chain, the malicious chain will
eventually outpace the honest chain. Thus, increasing the mining rate while
maintaining security is critical for improving the throughput and latency of
protocols. Current (leading) systems avoid the aforementioned limitations in
three independent ways as follows.

The first line of work (GHOST, Conflux) provides the solutions by maximizing
the mining rate until reaching the security-limitation. These solutions follow
the main architecture of Bitcoin, but with the modifications of adopting more
sophisticated extension rules to solve forks. The systems mainly belong to
Type V/VI. These systems have to extend graphs and sort units in the main
chain. Such designs confront a similar bottleneck with classic blockchain
systems. Improving performance relies on decreasing the confirmation time of
the main chain. The time cost from conflict solving and unit sorting limits
the upper bound of throughput.

The second line of work (Prism, OHIE) aims to horizontally scale the
blockchain by enabling multiple chains processed in parallel. The system
adopting this type of method generally has a fixed security threshold. Within
this threshold, the throughput can maximally approach the communication
limitation. Conversely, once exceeding the threshold, the system is limited by
its security bound. Improving scalability without undermining safety is the
key point in this line of studies. This design pattern mainly appears in Type
III and Type IV. The systems are based on structured DAGs and each individual
chain speeds up simultaneously.

Another line of work (IOTA, Avalanche, Spectre, Phantom) reconstructs systems
to reach the (physical) communication-limitation. The approach greatly
modifies the original designs, decreasing the confirmation time as well as
improving scalability. However, as a sacrifice, systems inevitably either
weaken the security promise or increase the system’s complexity. Such
limitations arise from excessive random forks due to unstructured networks
when the mining rate is increased. These systems usually appear in Type I/II.

Observations. We further capture several experimental testing results from the
corresponding literature and list them in Fig.33. The performance of a DAG-
based blockchain system can be measured in its total TPS, equivalently, the
multiplication of individual chain throughput (in y axis), and participated
nodes (scalability in x axis). The entire figure can be made up by two ways:
Area1, Area2 and Area3 separated by blue lines, or Area4 and Area5 by red
lines. Based on results, we observe several facts:

  * $\diamond$

Most DAG blockchains locate in Area2 and Area3. This indicates the performance
improvements of DAG solutions mainly come from the contribution of
scalability. Systems rely on parallel chains and side chains to carry more
transactions in each short period.

  * $\diamond$

Type I/II and Types V/VI systems locate in Area3 with a high probability while
Type III/IV in Area3. This reflects DAG blockchains with natural-graph
topology (mainchain-based designs included) perform better at scalability, but
are poor in individual throughput. The is because frequent forks in the
network retard the confirmation time of transactions. In contrast, parallel-
chain based protocols sitting in the middle of the figure balance these two
factors. The more nodes joining the networks, the more witnesses are required
in each round of voting, requiring much time for negotiation.

  * $\diamond$

Several systems locate in Area4 while others in Area5 without seemly
associations. We review their decoupled components and find some commons.
Area4 systems mainly adopt BFT-style consensus mechanisms or rely on TR-based
protocols with instant decisions. This would facilitate confirmation
procedures but cannot scale chains very well. On the contrary, Area5 systems
leverage NC/NC-variants protocols with permissionless settings. Such designs
provide satisfactory scalability but are poor in throughput.

  * $\diamond$

As discussed, we identify two main factors that have significant impacts on
the system performance, namely structure topology and consensus mechanism. A
graph-based topology can greatly improve scalability while BFT-style consensus
brings benefits in chain throughput (fast confirmation). Besides, other
techniques also play critical roles. We discuss them separately in instance
analyses.

  * $\diamond$

We observe that existing DAG blockchain systems cannot achieve both individual
throughput and scalability at the same time. Frankly speaking, it is not clear
what the optimal solution is for the sweet spot when considering a trade-off
between scalability and throughput. The bottleneck might be limited by
security considerations or physical boundaries.

Figure 33. Throughput and Scalability

###  7.2. Instance Analysis

We provide detailed analyses of mentioned instances. Due to the differences
between experimental settings and hardware devices, we focus on qualitative
reasons that help to gain high performance or cause potential sacrifices,
instead of quantitative outcomes.

GHOST (sompolinsky2015secure, ) follows the model of Bitcoin, but with
modifications on chain selection rules. The protocol extends the chain by
selecting the weightest subtree, instead of the longest subchain. It greatly
changes the way to organize blocks. Unlike Bitcoin’s linear structure, GHOST
organizes blocks in a tree structure which improves the utilization of mining
power under high contention. This design enables GHOST to significantly
improve the block generation rate, and decrease the confirmation time of
blocks. A high generation rate leads to unsolvable forks in Bitcoin, whereas a
large proportion of the forks are tolerable in GHOST. As proved in
(sompolinsky2015secure, ), when the rate moronically increases, the security
threshold of Bitcoin sharply decreases, whilst the GHOST protocol maintains
stability. Forks frequently appear in a high block generation rate, but GHOST
is more resilient and scalable than Bitcoin.

Conflux (li2020decentralized, ) inherits the design of GHOST to achieve high
performance without undermining security. Standard NC-based protocols reach a
total linear order of transactions while confirming blocks. The key insight of
Conflux is to decouple the confirmation of blocks against transactions.
Differing from Bitcoin and GHOST, Conflux defers the steps of the transaction
sorting, making it processed after the block confirmation, rather than at the
same time. The order of transactions can be deterministically derived from the
agreed order of blocks. The dependency between these two components is thus
changed. Each time a block only needs to concentrate on a gross-grain sorting
of blocks, without having to simultaneously consider the fine-grain sorting of
transactions. Besides, Conflux enables each block to reference multiple edges
at each time, which allows concurrent transactions and blocks. Conflux also
stresses its adaptive weight mechanisms to switch the strategies between a
fast model and a slow model. This design smoothly balances security as well as
performance.

Spectre (sompolinsky2016spectre, ) and Phantom (sompolinsky2020phantom, )
embrace the DAG structure to support faster block generation and larger block
volume. The improved performance of Spectre comes from two aspects: a) The
system structures blocks to form a topological network. Transactions can
concurrently attend to the network, making the system scalable. b) Increasing
the block generation rate contributes to performance. This is due to the fact
that Spectre only requires a pairwise ordering between two blocks, avoiding
the barrier of conflicting states among many blocks. Similarly to Spectre,
blocks are created and attached concurrently in Phantom. The main difference
is that Phantom requires a total linear order of blocks and transactions. This
makes Phantom have to maintain a trade-off between security and performance.
Simply increasing the block generation rate will unpredictably affect several
associated factors. Thus, the confirmation time of transactions is much slower
than that in Spectre but still faster than any NC-based blockchain system
under the single linear chain structure.

IOTA (popov2016tangle, ), adopting the third method, both decrease the
confirmation time and improve the system scalability. It relies on a simple
and intuitive tip selection rule to extend the graph without any further
limitations. The fast block creation rate directly improves the confirmation
rate for pending transactions. A peak rate ($>400$ TPS) has been observed with
a confirmation coverage of over 99%. It is sufficient for most application
cases. Further, we capture two features with respect to the performance of
IOTA. a) Theoretically, the performance is merely limited by the physical
hardware, including bandwidth and propagation delay. The Tangle can grow
without hindrance and forks are tolerable. b) The confirmation time of
transactions significantly varies according to their confidence. The higher
confidence a transaction initially obtains, the faster it can be confirmed.
Uneven distribution of confirmation time is formed since most of the
transactions follow biased incentives. As a sacrifice, the design of IOTA
inherently weakens the strong guarantee of consistency and security. IOTA has
to (temporarily) rely on a centralized Coordinator to periodically take
snapshots of the history to balance stability and performance.

Avalance (rocket2019scalable, ) redesigns the consensus protocols by
leveraging network sampling. Similar to IOTA, Avalanche achieves high
throughput and scalability with the expense of undermining strict consistency.
The high performance derives from three aspects: a) Leaderless BFT protocols
in Avalanche avoid the congestion and vulnerability of the centralized
authority; b) The system only maintains correct pairwise orders rather than a
total linear sequence of transactions. c) The complexity of handling a message
is fixed ($O(k)$), free from the expansion of the network. Besides these three
intuitive reasons, an additional factor is the fraction of Byzantine nodes in
the network. The probabilistic guarantee of its safety will significantly
degrade when Byzantine participants exceed $f$ due to the exponential effect
of the repeated sampling. Keeping the fraction at a low level enables the
subsampled voting mechanism to reach the consensus more safely and
efficiently.

Prism (bagaria2019prism, ) deconstructs the Nakamoto consensus into basic
functionalities and reconstructs its new system by scaling up these
functionalities. The bottleneck is limited by physical conditions, rather than
security requirements. The key point is that all functionalities are decoupled
and independent. This design greatly improves the performance in the following
aspects: a) The transaction blocks are instantly confirmed by the powerful
leader blocks without delay. The confirmation does not rely on any intensive
resources like computing power or stakes, which enables fast execution. b) Th
leader block confirms a list of possible ledgers instead of a unique ledger,
making non-conflicted transactions simultaneously processed. c) The
confirmation of a leader block will not be hindered by the states of voter
blocks. Once the leader block receives a majority of votes from voter blocks,
it becomes permanent without having to worry about situations of voter blocks.
Prism can be deemed as the first NC-based protocol (w.r.t the leader chain)
that breaks the confirmation barrier of transactions.

OHIE (yu2020ohie, ) scales NC-based protocols by processing chains in
parallel. The system achieves high performance as well as maintains a linear
order of transactions thanks to the design that speeds up almost every
procedure. Specifically, OHIE makes improvements in the following aspects: a)
A pre-allocation of transactions into individual chains avoids duplicated
confirmation and potential conflicts. Assume a total of $k$ transactions and
$n$ nodes, each chain just needs to take $1/n$ workload to process $k/n$
transactions. b) The system applies NC-based extension rules to every single
chain, rather than the whole system. This is essential to overcome the
bottleneck because much of the time is wasted under the high contention of
forks. Instead, OHIE sorts the blocks by comparing their intrinsic parameters
(positions) at a high speed. 3) OHIE decouples the functions of confirmation
and sorting where sorting blocks happen before the confirmation of blocks. The
sorting relies on the location of a block, while the confirmation is based on
its proposed confirm bar. This design provides an additional benefit of
scalability. Unlike BFT-style protocols, newly joint nodes (with legal
permission) will not increase the burden of existing ones and the system can
still reach peak performance. The limitation of OHIE comes from its sorting
algorithm.

###  7.3. Summary

Based on previous discussions, we conclude with some insights. Since the
design of each DAG system varies from one to another, we capture several
common features as follows.

  * $\diamond$

We can hardly improve the scalability and throughput at the same time under
the assumption of strict consistency. The more nodes are involved, the more
time will be spent on decisions. Even though each type of system is radically
different, they still have to reach the trade-off between security and
performance to a certain degree.

  * $\diamond$

To achieve strict consistency, the sorting algorithm might become the
bottleneck in DAG-based systems. The computing complexity in sorting
algorithms exponentially increase with the participating members. One
particular case is that the committee member only has one member (might
dynamically change) – a leader who can decide the sequence, such as Vite
(liu2018vite, ), Jointgraph (xiang2019jointgraph, ). This design maximally
decreases the confirmation time but results in centralization.

  * $\diamond$

Weakening the strict requirements of consistency enables high scalability and
fast confirmation. Systems like IOTA (popov2016tangle, ), Nano
(lemahieu2018nano, ), Spectre (Sompolinsky2017SPECTRES, ), only guarantee the
partial/pairwise order of the transactions. This is enough for asset
transferring between two/multiple parties, but cannot support strict state
transitions like smart contract components.

  * $\diamond$

For the NC/NC-variant based DAG systems, we observe that the depth $d$ only
has impacts on the confirmation latency, rather than the throughput and the
propagation latency. Depth is used to measure how deep a block is buried in
the chain.

  * $\diamond$

Theoretical analysis of performance usually adopts Nakamoto’s model
(garay2015bitcoin, ), such as the analysis in GHOST (sompolinsky2015secure, ),
Prism (bagaria2019prism, ), OHIE (yu2020ohie, ) Conflux (li2020ghast, ).
Unfortunately, only a handful of them provides experimental evaluations.

##  8\. Further Discussion

In this section, we discuss a) ways to integrate each component (structure,
consensus, properties) and their impact on each other; b) differences between
the DAG technique and existing scaling approaches; c) related components with
their impact on DAG systems; d) challenges surrounding DAG-based blockchains.

###  8.1. Intra-Component

This subsection explores the mechanisms, features, and differences of each
sub-component inside each component. We discuss two physical components
structure and consensus mechanism and one virtual component property.

Structure defines the way units are recorded in DAG systems. It consists of
two aspects, namely data structure and graph topology. Traditional blockchain
systems neglect the second factor since they rely on the linear-chain topology
as default. In contrast, graph-based topology in DAG systems is the most
distinguishable feature. Here, we provide more discussion.

Data structure. The metadata stored on the ledgers can be structured in either
transactions or blocks. A major difference between these “containers” is their
permission to operate the ledgers. This includes the rights of read and write.
Read means a node can access the states in the ledger and obtain the messages
to generate his new transaction without changing any previous states. Write
means the node can change the states of the ledger by adding new content. In
the transaction-container systems, all participants can both read and write
the data into ledgers. The nodes who receive legal transactions will directly
append them into their ledgers. However, in block-container systems, the
committee members (miner/validator/etc.) have the rights of read and write,
whereas the ordinary participant can only read. Transactions sent by the
ordinary nodes require to be packaged by the committee nodes and then written
to the ledger after the consensus. Ordinary participants cannot directly
affect the status of the account. Additionally, the difference also lies in
its role of filter. The committee nodes can filter malicious transactions to
some extent. A double-spending transaction will be abandoned directly, rather
than being appended to the ledger. This effectively resists the flooding
attack and replay attack.

Topology. Topology refers to the graph formed by the units and their
relationships. It also describes the way to organize each unit in the network.
Three design patterns are identified in Section 3, namely divergence
($\widehat{D}$), parallel ($\widehat{P}$), and convergence ($\widehat{C}$).
The topology cannot determine the final properties. It only shows the
visualized graph made by edges and vertexes. Additionally, the topology can
indirectly reflect the complexity of the protocols. $\widehat{D}$ type
contains the most flexible systems without strict/uniform consensus
mechanisms. Transactions and blocks can arbitrarily be dispersed in the
network. Only a simple rule (TSA/RTA/GA/Sampling) is applied to each system.
$\widehat{P}$ type includes the systems with a group of nodes who separately
maintain their chains/accounts. The complexity depends on their aimed
properties, such as the linear order. An additional sorting algorithm is
introduced to the system for the final sequence. $\widehat{C}$ type generally
consists of two main steps, from the main chain and determine the sequence.
The main chain both records the history as a trusted snapshot chain and solves
the conflicts among blocks and transactions.

Consensus mechanism defines the way to reach the agreement. Traditional
linear-based blockchain systems decouple the consensus into two main
questions: who conducts the consensus and how to operate the consensus. We
follow this category (see Section 4) with additional details as follows.

Openness and membership selection answer the question of who. In blockchain
systems, a group of nodes that participate in the consensus procedure is
called the committee. These sub-components define the rules on how to select a
set of trustworthy nodes to form the committee. The committee is essential for
successfully running consensus algorithms since it improves the security
threshold of the systems. Specifically, for an open environment
(permissionless), nodes compete for winners according to their resources, like
computing power, stake, and reputation. For a closed environment
(permissioned), the member is generally assigned by the developer team.
Adversaries cannot become legal members if they have not invested in large
amounts. Even though an attacker temporarily holds sufficient resources, the
advantages cannot last for the long term. For example, IOTA (popov2016tangle,
) only utilizes the PoW as the anti-spam tool, rather than the rules of
membership selection. An attacker may easily launch the parasite attack and
splitting attack (see Section 6). Thus, applying the coordinator to the IOTA
network is evidence of improving the security threshold. Similarly, assigning
several authority nodes as legal members also exclude unfamiliar nodes outside
the committee. Besides, the small size committee enables the systems to run
optimally with lightweight payloads. This is especially critical for parallel-
chain based systems (Type III, Type IV). The more nodes are involved, the more
messages are broadcast.

Unit allocation, unit positioning, extension rule, conflict solving and
featured technique answer the question of how. Classic blockchain systems
focus on the procedure of extension rule where the chain only needs to
consider how to select its child. The rule is straightforwards since the
metric of child selection is based on one dimensional parameters, such as
length (Bitcoin (nakamoto2008peer, )), weight (sompolinsky2015secure, ), age
(king2012ppcoin, ). In contrast, DAG-based systems are complex. Firstly, the
role of the units is uncertain. A unit might be a transaction, an event, or a
block and the role of a block can even be decoupled into different
functionalities (see Prism (bagaria2019prism, )). Secondly, locating a unit,
as the pre-step for the sorting algorithm, is hard in the graph-based network.
A well-structured DAG (such as Type III, Type IV) can position a specific unit
by at least two parameters, $(i,h)$ in Table.3. The sub-component Unit
position helps to mitigate this issue. However, an unstructured DAG (Type I,
Type II) cannot precisely locate their units. Thirdly, each DAG system has its
designs with customized aims and properties. Not all of the systems require
strict consistency or total ordered sequence. This leads to different
extension rules in multidimensional metrics. We separately use extension rule
and conflict solving to describe their consensus approaches. The extension
rule mainly refers to the principles of tie-breaking, while conflict-solving
represents the way to sort the selected units into the final sequence.
Technical feature emphasizes key techniques adopted by each system. A complete
consensus mechanism in DAG systems might include all sub-components or several
of them.

Properties are not physical components (like structure and consensus).
Instead, properties describe the final goals of each system. It is not
standalone since the aimed properties determine how to design the algorithms
and integrate them. Three properties are identified in Section 3, namely
consistency, order, and finality. Consistency describes whether a state is
globally viewed among different ledgers; order shows how each unit is ordered,
and finality represents the possibility that a ledger can be reversed. These
three factors are orthogonal in most cases but might have overlaps in a few
cases. For example, Vite (liu2018vite, ) consists of multiple parallel chains
and one snapshot chain. If we watch from the whole system, consistency is not
achieved since the ledgers in each node have totally different views. In
contrast, if we watch from the snapshot chain, consistency is achieved. Such
conflicts are caused by the role of its main (snapshot) chain. In most cases,
the main chain records the full history and simultaneously conducts the
consensus. The decisions will be synchronized to each distributed node, and
they can reach the same view of states. However, if the main chain only
records the history without further consensus steps, common nodes cannot
obtain any synchronized states. In this situation, we measure the consistency
in the view of its main chain.

###  8.2. Inter-Component

This subsection explores the connections between individual components and
their impacts on each other. Two physical components structure and consensus
mechanism and one virtual component property are included. Here, we provide
more details.

Structure and Consensus. The structure defines the way transactions are
recorded in the systems. It greatly impacts the consensus of the unit types
they agreed upon. In our classification, two major types of units are
identified: transaction and block. If the system is directly based on
transactions, the consensus tends to be simpler than that based on blocks. The
former only requires the rules of conflict solving and unit sorting, whereas
the latter needs additional procedures such as membership selection, the
configuration of committees, etc. Conversely, the consensus also diversifies
the types of structural design. For example, an additional snapshot block in
Vite (liu2018vite, ) is introduced into the system due to the design of
consensus. We ignore the classification of block types at more specific
levels, such as vote/propose/transaction blocks in Prism (bagaria2019prism, ).
We consider they are encompassed in the consensus procedures.

Consensus and Property. The Properties indicate the goal of consensus, and
conversely, consensus algorithms are the way to achieve properties.
Traditional blockchain systems do not often mention this virtual component
since they attempt to achieve strict consistency, or the total linear order,
as their default requirements. In contrast, DAG-based systems relax such
requirements, letting systems achieve partial consistency or stay in
topological order. Thus, the consensus algorithms under different properties
vary from system to system. The consensus procedures and complexity to achieve
the total linear order are much more complicated than staying in the
topological order. But the latter sacrifices security and compatibility to
some degree.

Structure and Property. Properties indirectly impose requirements on the
structure design. For example, a unit to be deemed as valid or confirmed
requires high confidence to prove it is attached by sufficient child units.
This makes the unit equipped with a counter to measure confidence. For systems
based on transactions, the counter can only be initiated as an additional
field: weight, vote, etc. In contrast, for the systems based on blocks, the
counter may consider more options like the block volume or the block size,
which are used to show the collected/verified transactions in every single
block. Also, some powerful blocks may instantly have decisions on contained
transactions, like the proposed block in Prism (bagaria2019prism, ).

###  8.3. Differences with Parallel Approaches

The performance and scalability can be optimized by many techniques. We
conclude with the most prevailing approaches and highlight their differences
compared with DAG.

Sharding technique (wang2019sok, ) splits the transactions into disjoint
shards to enable them processed in parallel. DAG approach differs from the
sharding technique in the following aspects: a) The systems adopting the
sharding approach rely on strict consistency. In contrast, strict consistency
is not necessarily for DAG systems. b) Sharding-based systems still utilize
the linear-chain structure to maintain their ledgers for final states. The
separated zones have to reach an agreement in each epoch across multiple
shards, which makes c) the multiple-committee consensus becomes essential in
the sharding technique. The key idea of such consensus protocols is to assign
the nodes to committees in a non-deterministic way, preventing the adversary
from threatening specific members. Conversely, the DAG systems are generally
based on single-committee consensus. Some studies (bano2019sok, ) claim that
single-committee consensus is not scalable where newly participated nodes
decrease the throughput. This is only one side of the coin since the
assumption of consistency is neglected. If the system only requires partial
consistency, like Nano (lemahieu2018nano, ), a single committee will not
become the limitation for scalability.

Layer2 technique (gudgeon2020sok, )(jourenko2019sok, ), refers to the
solutions that process certain transactions outside of the main chain, but the
consensus of these transactions still relies on a parent chain. The parent
chain is a traditional linear-based blockchain, selectively recording the
important transactions (e.g. balance, final state). Compared with DAG, this
technique is inherently an upper-layer protocol without changing the structure
or undermining the properties of its parent chain. Layer2 technique cannot
maximally improve the performance since the consensus is still limited by its
linear-based parent chain. The bottleneck is significantly affected by its
main chain. Another critical problem is to reliably guarantee the consistency
between off-chain states and on-chain states. Relying on authority nodes for
endorsement or charging the deposit in advance might increase extra costs
either computationally or economically.

Sidechain technique (back2014enabling, ) deviates from the layer2 technique in
whether they have own consensus algorithms. The sidechain is a separate
blockchain that processes transactions individually. It interacts with the
main chain and tokens can be transferred between them. Several DAG systems
(such as Vite/Parsec) get inspired by this design to some degree, which
introduces a hybrid architecture with one main chain to sort the units and
multiple ordinary (side) chains to process transactions in parallel. However,
a major difference is the coupling between the main chain and side chains. In
DAG-based systems, the main chain and side chains are closely integrated. The
states (metadata) are recorded on all involved side chains and the consensus
across these chains (ledgers) is then finished with the help of the main
chain. In contrast, the main chain and side chain are completely decoupled in
this technique. The side chain is merely an auxiliary chain, providing a very
small proportion of information to the complete system.

Heterogeneous structure represents a vertically structural shift. The approach
changes originally homogeneous blocks into heterogeneous blocks by adding new
block types. It assigns the blocks with different functionalities, generally,
including two types: the keyblocks used to conduct consensus and the
microblocks to vote for leaders and carry transactions. This line of studies
include Bitcoin-NG (eyal2016bitcoin, ), Fruitchain (pass2017fruitchains, ),
ByzCoin (kogias2016enhancing, ), and ComChain (vizier2018comchain, ). All
these systems improve the throughput of performance without terribly
undermining the security promise. The most significant difference is that: the
DAG approach inherently is the horizontally scaling solution that aims to
enable transactions processed in parallel. Several DAG-based systems directly
adopt the concepts of this technique, such as Prism (bagaria2019prism, ), to
decouple the functionality of blocks; while some systems indirectly utilized
the concept, such as Conflux (li2020decentralized, )/Vite(liu2018vite, ), to
organize the key blocks in a separate (main) chain for consensus.

Hybrid consensus solution refers to the systems which combine two or more
consensus protocols. These systems attempt to abstract the advantages of each
system and integrate them into one protocol. Thunderella (pass2018thunderella,
) replaces the complex process of view-change in PBFT with the Nakamoto
consensus. This makes the system smoothly switch between the optimistic
conditions and the worst-case conditions. In optimistic conditions,
Thunderella provides a high throughput since the adversary is weak, whereas,
in the worst-case conditions, it falls back to the NC protocol for the
conservative guarantee of security. Other systems includes Tangaroa (Raft+BFT)
(copeland2016tangaroa, ), Tendermint (PoS+PBFT) (buchman2016tendermint, ),
etc. However, these systems only optimize the performance at the consensus
level, which cannot overcome the bottleneck from the linear-based structure or
topology. DAG-based systems also adopt the concept of this approach to
construct their integrated components, especially how to combine the procedure
of committee formation and agreement decision.

Other techniques (hafid2020scaling, ) include on-chain solutions that propose
the modifications towards blockchain protocols. Increasing the size or
improving the volume of blocks is the key feature. BCH (bch17, ) modifies the
hardcoded parameter, adjusting the block size from 1M to 8M. Larger blocks
increase the total throughput and reduce transaction fees. SigWit (sigwit, )
splits a classic block (1M) into the associated blocks: a base transaction
block with a size of 1 MB and an extended block with 3 MB. These blocks
individually take different functionalities. However, these systems typically
require a hard/soft fork from the original blockchain, which costs much time
for the negotiation with their communities. Compared to DAG systems, this
approach merely changes the components of blockchains, rather than any
structure or topology. The performance bottleneck still depends on its base
blockchain.

##  9\. Concluding Remarks

We provide a handful of open problems come from developers and communities and
finally conclude this paper.

Questions from Communities. We also collect several highly mentioned problems
from communities. At the end of the paper, we provide our answers as follows.

Do we need blocks? We do not always need blocks. The systems in Type I/III/V
show us a series of examples.

What’s the main difference between DAG-based and classic blockchains?  The
main difference is the organization of units that transits from the linear-
based model to the graph-based model. Another point that is often neglected is
their properties. Classic blockchain systems set strict consistency as their
default requirements, whereas DAG systems may greatly weaken such
requirements.

Does DAG indeed help to improve the performance? DAG solutions do improve the
performance of blockchain, in three aspects: scalability, throughput, and
confirmation time. A system may improve one or two of them, which depends on
its design of the protocol and requirements of the properties.

Can smart contract be supported? Ensuring correct state transitions is the
most fundamental task of smart contracts. This requires units sorted in a
linear sequence for a consistent view across different ledgers. Thus, only the
system designed with a linear sorting algorithm has the chance to establish
upper-layer components such as the smart contract.

What types of applications can be applied?  Existing systems can only support
basic functionalities like asset transferring. Upper layer components like the
smart contract have not been implemented so far (except for external
components such as (iotacoordicide, )). The applications, heavily relying on
state transitions, cannot be directly applied to current DAG systems.

Is there a blockchain design that simultaneously scales throughput, storage
efficiency, and security (wang2019sok, )?  Currently, no protocols in the
context of DAG blockchains exist and meet all these requirements at the same
time. Moreover, the metrics mentioned in the question are even controversial
among peer researchers.

What types of paradigm can we learn?  We have identified six types of DAG-
based blockchain systems under two-dimensional metrics. No concurrent work can
outpace ours with respect to the refinement of classification. Fitzi et al.
introduces the parallel chain model, which in fact contains Type III/IV. Other
studies (sompolinsky2020phantom, ), mentioning the blockDAG or TxDAG, cannot
clearly and comprehensively present the features and differences among current
DAG systems, either.

Conclusion. Constrained by limitations on performance and scalability, the
revolution of classic blockchains is required. DAG-based systems provide
innovative models whose underlying structures enable high throughput and large
scalability. However, the ﬁeld has grown increasingly complex with different
designs and patterns, making newcomers confused. In this work, we provide the
first structured analysis of DAG-based blockchains. We provide the overview by
reviewing and analyzing ever-existing and ongoing studies. Then, we abstract a
general model to capture the features of DAG and identify six types of design
patterns. We analyze the collected systems by respectively evaluating their
structure, consensus mechanism, property, security, and performance, followed
by discussions on their impacts, comparisons, and challenges. To the best of
our knowledge, this paper provides the first comprehensive and insightful
analysis and summary of DAG-based blockchain systems, making a timely
contribution to the prolific and vibrant area of this field. Optimistically,
we believe new mechanisms will be progressively proposed to improve the
current systems. Future developments, especially structure shifts, will impact
performance, scalability, or security in a variety of ways.

## References

  * [1] Satoshi Nakamoto et al.  A peer-to-peer electronic cash system.  Bitcoin.–URL: https://bitcoin. org/bitcoin. pdf, 2008.
  * [2] Gavin Wood et al.  Ethereum: A secure decentralised generalised transaction ledger. ethereum project yellow paper.(2014), 2014.
  * [3] Joseph Bonneau, Andrew Miller, Jeremy Clark, Arvind Narayanan, Joshua A Kroll, and Edward W Felten.  SoK: Research perspectives and challenges for bitcoin and cryptocurrencies.  In IEEE Symposium on Security and Privacy (S&P), pages 104–121. IEEE, 2015.
  * [4] Marianna Belotti, Nikola Božić, Guy Pujolle, and Stefano Secci.  A vademecum on blockchain technologies: When, which, and how.  IEEE Communications Surveys & Tutorials, 21(4):3796–3838, 2019\.
  * [5] Muhammad Salek Ali, Massimo Vecchio, Miguel Pincheira, Koustabh Dolui, Fabio Antonelli, and Mubashir Husain Rehmani.  Applications of blockchains in the internet of things: A comprehensive survey.  IEEE Communications Surveys & Tutorials, 21(2):1676–1717, 2018\.
  * [6] Junfeng Xie, Helen Tang, Tao Huang, F Richard Yu, Renchao Xie, Jiang Liu, and Yunjie Liu.  A survey of blockchain technology applied to smart cities: Research issues and challenges.  IEEE Communications Surveys & Tutorials, 21(3):2794–2830, 2019\.
  * [7] Tara Salman, Maede Zolanvari, Aiman Erbad, Raj Jain, and Mohammed Samaka.  Security services using blockchains: A state of the art survey.  IEEE Communications Surveys & Tutorials, 21(1):858–880, 2018.
  * [8] Mauro Conti, E Sandeep Kumar, Chhagan Lal, and Sushmita Ruj.  A survey on security and privacy issues of bitcoin.  IEEE Communications Surveys & Tutorials, 20(4):3416–3452, 2018\.
  * [9] Kyle Croman, Christian Decker, Ittay Eyal, Adem Efe Gencer, Ari Juels, Ahmed Kosba, Andrew Miller, Prateek Saxena, Elaine Shi, Emin Gün Sirer, et al.  On scaling decentralized blockchains.  In International Conference on Financial Cryptography and Data Security (FC), pages 106–125. Springer, 2016.
  * [10] NeonVest.  The scalability trilemma in blockchain.  https://medium.com/@aakash_13214/the-scalability-trilemma-in-blockchain-75fb57f646df, 2019\.
  * [11] Aggelos Kiayias and Giorgos Panagiotakos.  Speed-security tradeoffs in blockchain protocols.  IACR Cryptology ePrint Archive, 2015:1019, 2015.
  * [12] Gang Wang, Zhijie Jerry Shi, Mark Nixon, and Song Han.  SoK: Sharding on blockchain.  In Proceedings of the 1st ACM Conference on Advances in Financial Technologies (AFT), pages 41–61, 2019.
  * [13] Georgia Avarikioti, Eleftherios Kokoris-Kogias, and Roger Wattenhofer.  Divide and scale: Formalization of distributed ledger sharding protocols.  arXiv preprint arXiv:1910.10434, 2019.
  * [14] Lewis Gudgeon, Pedro Moreno-Sanchez, Stefanie Roos, Patrick McCorry, and Arthur Gervais.  SoK: Layer-two blockchain protocols.  In International Conference on Financial Cryptography and Data Security (FC), pages 201–226. Springer, 2020.
  * [15] Adam Back, Matt Corallo, Luke Dashjr, Mark Friedenbach, Gregory Maxwell, Andrew Miller, Andrew Poelstra, Jorge Timón, and Pieter Wuille.  Enabling blockchain innovations with pegged sidechains.  URL: http://www. opensciencereview. com/papers/123/enablingblockchain-innovations-with-pegged-sidechains, 72, 2014\.
  * [16] Juan Garay and Aggelos Kiayias.  SoK: A consensus taxonomy in the blockchain era.  In Cryptographers’ Track at the RSA Conference (CT-RSA), pages 284–318. Springer, 2020.
  * [17] Shehar Bano, Alberto Sonnino, Mustafa Al-Bassam, Sarah Azouvi, Patrick McCorry, Sarah Meiklejohn, and George Danezis.  SoK: Consensus in the age of blockchains.  In Proceedings of the 1st ACM Conference on Advances in Financial Technologies (AFT), pages 183–198, 2019.
  * [18] Abdelatif Hafid, Abdelhakim Senhaji Hafid, and Mustapha Samih.  Scaling blockchains: A comprehensive survey.  IEEE Access, 8:125244–125262, 2020.
  * [19] Community.  Bitcoin cash.  https://www.bitcoincash.org, 2017.
  * [20] Alexei Zamyatin, Mustafa Al-Bassam, Dionysis Zindros, Eleftherios Kokoris-Kogias, Pedro Moreno-Sanchez, Aggelos Kiayias, and William J Knottenbelt.  SoK: Communication across distributed ledgers.  Technical report, IACR Cryptology ePrint Archive, 2019: 1128, 2019.
  * [21] Yonatan Sompolinsky and Aviv Zohar.  Accelerating bitcoin’s transaction processing. fast money grows on trees, not chains.  IACR Cryptology ePrint Archive, 2013(881), 2013.
  * [22] Serguei Popov.  The tangle.  cit. on, page 131, 2016.
  * [23] Anton Churyumov.  Byteball: A decentralized system for storage and transfer of value.  URL https://obyte.org/Byteball.pdf, 2016.
  * [24] Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar.  Spectre: A fast and scalable cryptocurrency protocol.  IACR Cryptology ePrint Archive, 2016:1159, 2016.
  * [25] Huma Pervez, Muhammad Muneeb, Muhammad Usama Irfan, and Irfan Ul Haq.  A comparative analysis of dag-based blockchain architectures.  In 12th International Conference on Open Source Systems and Technologies (ICOSST), pages 27–34. IEEE, 2018.
  * [26] Georgios Birmpas, Elias Koutsoupias, Philip Lazos, and Francisco J Marmolejo-Cossío.  Fairness and efficiency in dag-based cryptocurrencies.  International Conference on Financial Cryptography and Data Security (FC), 2020.
  * [27] Chong Bai.  State-of-the-art and future trends of blockchain based on dag structure.  In International Workshop on Structured Object-Oriented Formal Language and Method (SOFL+MSV), pages 183–196. Springer, 2018.
  * [28] Andrew Gorczyca and Audrey Decker.  Distributed ledger witness selection in bounded width directed acyclic graphs.  In IEEE International Conference on Blockchain and Cryptocurrency (ICBC), pages 124–127. IEEE, 2019.
  * [29] Jiahao He, Guangju Wang, Guangyuan Zhang, and Jiheng Zhang.  Consensus mechanism design based on structured directed acyclic graphs.  arXiv preprint arXiv:1901.02755, 2019.
  * [30] Qiheng Zhou, Huawei Huang, Zibin Zheng, and Jing Bian.  Solutions to scalability of blockchain: A survey.  IEEE Access, 8:16440–16455, 2020.
  * [31] Wellington Fernandes Silvano and Roderval Marcelino.  Iota tangle: A cryptocurrency to communicate internet of things data.  Future Generation Computer Systems (FGCS), 2020.
  * [32] Yang Xiao, Ning Zhang, Wenjing Lou, and Y Thomas Hou.  A survey of distributed consensus protocols for blockchain networks.  IEEE Communications Surveys & Tutorials, 22(2):1432–1465, 2020\.
  * [33] Manuel Zander, Tom Waite, and Dominik Harz.  Dagsim: Simulation of dag-based distributed ledger protocols.  ACM SIGMETRICS Performance Evaluation Review (PER), 46(3):118–121, 2019.
  * [34] Mohamed Riswan Abdul Lathif, Pezhman Nasirifard, and Hans-Arno Jacobsen.  Cidds: A configurable and distributed dag-based distributed ledger simulation framework.  In Proceedings of the 19th International Middleware Conference, Poster Session (Middleware), pages 7–8. ACM, 2018.
  * [35] Zhongli Dong, Emma Zheng, Young Choon, and Albert Y Zomaya.  Dagbench: A performance evaluation framework for dag distributed ledgers.  In IEEE 12th International Conference on Cloud Computing (CLOUD), pages 264–271. IEEE, 2019.
  * [36] Vincenzo Gabrielle Rader.  Blockchain and dag, the technology which enables distributed market places.
  * [37] Federico Matteo Benčić and Ivana Podnar Žarko.  Distributed ledger technology: Blockchain compared to directed acyclic graph.  In 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS), pages 1569–1570. IEEE, 2018.
  * [38] A Saad and Soo Young Park.  Decentralized directed acyclic graph based dlt network.  In Proceedings of the International Conference on Omni-Layer Intelligent Systems (COINS), pages 158–163. ACM, 2019.
  * [39] Patrick Schueffel.  Alternative distributed ledger technologies blockchain vs. tangle vs. hashgraph-a high-level overview and comparison.  Tangle vs. Hashgraph-A High-Level Overview and Comparison (December 15, 2017), 2017.
  * [40] Isaac Sheff, Andrew Wang, Xinwenand Myers, and Robbert Renesse.  A web of blocks.  https://arxiv.org/abs/1806.06978, 2018.
  * [41] Louis-Claude Canon and Emmanuel Jeannot.  Evaluation and optimization of the robustness of dag schedules in heterogeneous environments.  IEEE Transactions on Parallel and Distributed Systems (TPDS), 21(4):532–546, 2009.
  * [42] Yixin Li, Bin Cao, Mugen Peng, Long Zhang, Lei Zhang, Daquan Feng, and Jihong Yu.  Direct acyclic graph based blockchain for internet of things: Performance and security analysis.  arXiv preprint arXiv:1905.10925, 2019.
  * [43] Caixiang Fan.  Performance Analysis and Design of an IoT-Friendly DAG-based Distributed Ledger System.  PhD thesis, University of Alberta, 2019.
  * [44] Yonatan Sompolinsky and Aviv Zohar.  Secure high-rate transaction processing in bitcoin.  In International Conference on Financial Cryptography and Data Security (FC), pages 507–527. Springer, 2015.
  * [45] Yoad Lewenberg, Yonatan Sompolinsky, and Aviv Zohar.  Inclusive block chain protocols.  In International Conference on Financial Cryptography and Data Security (FC), pages 528–547. Springer, 2015.
  * [46] Sergio Demian Lerner.  Dagcoin: a cryptocurrency without blocks.  https://bitslog.files.wordpress.com/2015/09/dagcoin-v41.pdf, 2015.
  * [47] Leemon Baird.  The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance.  Swirlds, Inc. Technical Report SWIRLDS-TR-2016, 1, 2016.
  * [48] Dahlia Malkhi.  Blockchain in the lens of $\\{$BFT$\\}$.  2018\.
  * [49] Colin LeMahieu.  Nano: A feeless distributed cryptocurrency network.  https://nano.org/en/whitepaper, 2018.
  * [50] Chenxing Li, Peilun Li, Dong Zhou, Wei Xu, Fan Long, and Andrew Yao.  Scaling nakamoto consensus to thousands of transactions per second.  https://arxiv.org/pdf/1805.03870.pdf, 2018.
  * [51] Quentin Bramas.  The stability and the security of the tangle.  2018\.
  * [52] B Kusmierz.  The first glance at the simulation of the tangle: discrete model.  IOTA Found. WhitePaper, pages 1–10, 2017.
  * [53] Vidal Attias and Quentin Bramas.  Tangle analysis for iota cryptocurrency.  2018\.
  * [54] Haibo Tian, Huizhi Lin, and Fangguo Zhang.  Design a proof of stake based directed acyclic graph chain.  In International Conference on Frontiers in Cyber Security (FCS), pages 150–165. Springer, 2020.
  * [55] Bartosz Kusmierz, William Sanders, Andreas Penzkofer, Angelo Capossele, and Alon Gal.  Properties of the tangle for uniform random and random walk tip selection.  In IEEE International Conference on Blockchain (Blockchain), pages 228–236. IEEE, 2019.
  * [56] Ethan Heilman, Neha Narula, Garrett Tanzer, James Lovejoy, Michael Colavita, Madars Virza, and Tadge Dryja.  Cryptanalysis of curl-p and other attacks on the iota cryptocurrency.  IACR Cryptology ePrint Archive, 2019:344, 2019.
  * [57] Serguei Popov.  On the timestamps in the tangle.  2017\.
  * [58] Johannes Buchmann, Erik Dahmen, Sarah Ereth, Andreas Hülsing, and Markus Rückert.  On the security of the winternitz one-time signature scheme.  In International Conference on Cryptology in Africa (AFRICACRYPT), pages 363–378. Springer, 2011.
  * [59] Darya Melnyk and Roger Wattenhofer.  The append memory model: Why blockdags excel blockchains.  2020\.
  * [60] Bartosz Kuśmierz, Sebastian Müller, and Angelo Capossele.  Committee selection in dag distributed ledgers and applications.  arXiv preprint arXiv:2102.03139, 2021.
  * [61] Bartosz Kusmierz and Alon Gal.  Probability of being left behind and probability of becoming permanent tip in the tangle v0. 2, 2018.
  * [62] IOTA Foundation Coordicide Team.  The coordicide.  https://files.iota.org/papers/20200120$\\_$Coordicide$\\_$WP.pdf, 2019\.
  * [63] Serguei Popov.  Iota: Feeless and free.  IEEE Blockchain Technical Briefs (BTB), 2019.
  * [64] Lucianna Kiffer, Rajmohan Rajaraman, and Abhi Shelat.  A better method to analyze blockchain consistency.  In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 729–744, 2018.
  * [65] Laurence Tennant.  Improving the anonymity of the iota cryptocurrency, 2017.
  * [66] Peter Ince, Joseph K Liu, and Peng Zhang.  Adding confidential transactions to cryptocurrency iota with bulletproofs.  In International Conference on Network and System Security (NSS), pages 32–45. Springer, 2018.
  * [67] Umair Sarfraz, Masoom Alam, Sherali Zeadally, and Abid Khan.  Privacy aware iota ledger: Decentralized mixing and unlinkable iota transactions.  Computer Networks, 148:361–372, 2019.
  * [68] Sehrish Shafeeq, Sherali Zeadally, Masoom Alam, and Abid Khan.  Curbing address reuse in the iota distributed ledger: A cuckoo-filter-based approach.  IEEE Transactions on Engineering Management (TEM), 2019.
  * [69] A Cullen, P Ferraro, C King, and R Shorten.  On the resilience of dag-based distributed ledgers in iot applications.  IEEE Internet of Things Journal (IoT), 2020.
  * [70] D Cai.  A parasite chain attack in iota.  B.S. thesis, University of Twente, 2019.
  * [71] Philip Staupe.  Quasi-analytic parasite chain absorption probabilities in the tangle, 2017\.
  * [72] Gerard De Roode, Ikram Ullah, and Paul JM Havinga.  How to break iota heart by replaying?  In IEEE Globecom Workshops (GC Wkshps), pages 1–7. IEEE, 2018.
  * [73] Andreas Penzkofer, Bartosz Kusmierz, Angelo Capossele, William Sanders, and Olivia Saa.  Parasite chain detection in the iota protocol.  arXiv preprint arXiv:2004.13409, 2020.
  * [74] Quaintance Monica and Martino and Will.  Chainweb protocol security calculations.  https://d31d887a-c1e0-47c2-aa51-c69f9f998b07.filesusr.com/ugd/86a16f_26d87f20cf8548d2927e28152babf533.pdf, 2018\.
  * [75] Dmitry Tanana.  Avalanche blockchain protocol for distributed computing security.  In IEEE International Black Sea Conference on Communications and Networking (BlackSeaCom), pages 1–3. IEEE, 2019.
  * [76] Pawel Szalachowski, Daniël Reijsbergen, Ivan Homoliak, and Siwei Sun.  Strongchain: Transparent and collaborative proof-of-work consensus.  In 28th USENIX Security Symposium (USENIX Security), pages 819–836, 2019.
  * [77] Nihat Yuva and İsmail Kırbaş.  Directed acyclic graph based on crypto currency application example: Iota.  In Proceedings of the International Conference on Data Science and Applications (DATA), pages 26–28, 2018.
  * [78] Bozhi Wang, Qin Wang, Shiping Chen, and Yang Xiang.  Security analysis on tangle-based blockchain through simulation.  In Australasian Conference on Information Security and Privacy (ACISP), pages 653–663. Springer, 2020.
  * [79] Chitra1 Tarun, Quaintance Monica, Haber Stuart, and Martino Will.  Agent-based simulations of blockchain protocols illustrated via kadena’s chainweb.  https://d31d887a-c1e0-47c2-aa51-c69f9f998b07.filesusr.com/ugd/86a16f_3b2d0c58179d4edd9df6df4d55d61dda.pdf, 2018\.
  * [80] Bozhi Wang, Shiping Chen, Lina Yao, and Qin Wang.  Chainsim: A p2p blockchain simulation framework.  In CCF China Blockchain Conference (CBC), pages 1–16. Springer, 2020.
  * [81] Xavier Boyen, Christopher Carr, and Thomas Haines.  Graphchain: A blockchain-free scalable decentralised ledger.  In Proceedings of the 2nd ACM Workshop on Blockchains, Cryptocurrencies, and Contracts (BCC), pages 21–33, 2018.
  * [82] Yonatan Sompolinsky and Aviv Zohar.  Phantom, ghostdag, 2020.
  * [83] Iddo Bentov, Pavel Hubácek, Tal Moran, and Asaf Nadler.  Tortoise and hares consensus: the meshcash framework for incentive-compatible, scalable cryptocurrencies.  IACR Cryptology ePrint Archive, 2017:300, 2017.
  * [84] Shuyang Tang, Qingzhao Zhang, Zhengfeng Gao, Jilai Zheng, , and Dawu Gu.  Bracing a transaction dag with a backbone chain.  https://eprint.iacr.org/2020/472.pdf, 2020.
  * [85] Matthias Fitzi, Peter Gazi, Aggelos Kiayias, and Alexander Russell.  Parallel chains: Improving throughput and latency of blockchain protocols via parallel composition.  IACR Cryptology ePrint Archive, 2018:1119, 2018.
  * [86] Jia Kan, Shangzhe Chen, and Xin Huang.  Improve blockchain performance using graph data structure and parallel mining.  In 1st IEEE International Conference on Hot Information-Centric Networking (HotICN), pages 173–178. IEEE, 2018.
  * [87] Marco Manoppo.  Designing a better blockchain consensus.
  * [88] Gewu Bu, Önder Gürcan, and Maria Potop-Butucaru.  G-iota: Fair and confidence aware tangle.  In IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pages 644–649. IEEE, 2019.
  * [89] Gewu Bu, Wassim Hana, and Maria Potop-Butucaru.  Metamorphic iota.  https://arxiv.org/abs/1907.03628, 2019.
  * [90] Pietro Ferraro, Christopher King, and Robert Shorten.  Iota-based directed acyclic graphs without orphans.  arXiv preprint arXiv:1901.07302, 2018.
  * [91] Andrea Tesei, Luca Di Mauro, Mariano Falcitelli, Sandro Noto, and Paolo Pagano.  Iota-vpki: A dlt-based and resource efficient vehicular public key infrastructure.  In 2018 IEEE 88th Vehicular Technology Conference (VTC-Fall), pages 1–6. IEEE, 2018.
  * [92] Odysseas Lamtzidis, Dennis Pettas, and John Gialelis.  A novel combination of distributed ledger technologies on internet of things: Use case on precision agriculture.  Applied System Innovation (ASI), 2(3):30, 2019.
  * [93] Caixiang Fan, Hamzeh Khazaei, Yuxiang Chen, and Petr Musilek.  Towards a scalable dag-based distributed ledger for smart communities.  In 2019 IEEE 5th World Forum on Internet of Things (WF-IoT), pages 177–182. IEEE, 2019.
  * [94] IOTA Foundation.  Qubic: Accessed on june 01, 2020.  https://qubic.iota.org/, 2020.
  * [95] IOTA Foundation.  Masked authenticated messaging module.  https://github.com/iotaledger/MAM.
  * [96] Xiaochen Zheng, Shengjing Sun, Raghava Rao Mukkamala, Ravi Vatrapu, and Joaquín Ordieres-Meré.  Accelerating health data sharing: A solution based on the internet of things and distributed ledger technologies.  Journal of Medical Internet Research (JMIR), 21(6):e13583, 2019\.
  * [97] James Brogan, Immanuel Baskaran, and Navin Ramachandran.  Authenticating health activity data using distributed ledger technologies.  Computational and Structural Biotechnology Journal (CSBJ), 16:257–266, 2018.
  * [98] Tariq Alsboui, Yongrui Qin, and Richard Hill.  Enabling distributed intelligence in the internet of things using the iota tangle architecture.  2019\.
  * [99] Laizhong Cui, Shu Yang, Ziteng Chen, Yi Pan, Mingwei Xu, and Ke Xu.  An efficient and compacted dag-based blockchain protocol for industrial internet of things.  IEEE Transactions on Industrial Informatics (TII), 2019.
  * [100] Gerard Ruiz.  Distributed data management in internet of things networking environments: Iota tangle and bitcoin blockchain distributed ledger technologies, 2018.
  * [101] Paulo C Bartolomeu, Emanuel Vieira, and Joaquim Ferreira.  Iota feasibility and perspectives for enabling vehicular applications.  In IEEE Globecom Workshops (GC Wkshps), pages 1–7. IEEE, 2018.
  * [102] Dragos Strugar, Rasheed Hussain, Manuel Mazzara, Victor Rivera, Joo Young Lee, and Ruslan Mustafin.  On m2m micropayments: a case study of electric autonomous vehicles.  In IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData), pages 1697–1700. IEEE, 2018.
  * [103] Wenhui Yang, Xiaohai Dai, Jiang Xiao, and Hai Jin.  Ldv: A lightweight dag-based blockchain for vehicular social networks.  IEEE Transactions on Vehicular Technology (TVT), 69(6):5749–5759, 2020.
  * [104] Jianxiong Guo, Xingjian Ding, and Weili Wu.  A double auction for charging scheduling among vehicles using dag-blockchains.  arXiv preprint arXiv:2010.01436, 2020.
  * [105] Natasa Zivic, Christoph Ruland, and Jochen Sassmannshausen.  Distributed ledger technologies for m2m communications.  In 2019 International Conference on Information Networking (ICOIN), pages 301–306. IEEE, 2019.
  * [106] Dario Assante and Roberto Crucco.  M2m learning environment for electric applications.  In 2019 IEEE Global Engineering Education Conference (EDUCON), pages 1518–1522. IEEE, 2019.
  * [107] Alexander Raschendorfer, Benjamin Mörzinger, Eric Steinberger, Patrick Pelzmann, Ralf Oswald, Manuel Stadler, and Friedrich Bleicher.  On iota as a potential enabler for an m2m economy in manufacturing.  Procedia CIRP, 79:379–384, 2019.
  * [108] Jordan Murkin.  A block-free distributed ledger for p2p energy trading: Case with iota?  In Advanced Information Systems Engineering (CAiSE), page 111. Springer.
  * [109] Shengjing Sun, Xiaochen Zheng, Javier Villalba-Díez, and Joaquín Ordieres-Meré.  Indoor air-quality data-monitoring system: Long-term monitoring benefits.  Sensors, 19(19):4157, 2019.
  * [110] Mirko Zichichi, Stefano Ferretti, and Gabriele D’Angelo.  A distributed ledger based infrastructure for smart transportation system and social good.  arXiv preprint arXiv:1910.03280, 2019.
  * [111] Odysseas Lamtzidis and John Gialelis.  An iota based distributed sensor node system.  In IEEE Globecom Workshops (GC Wkshps), pages 1–6. IEEE, 2018.
  * [112] Chao Wu, Liyi Zhou, Chulin Xie, Yuhang Zheng, and Jiawei Yu.  Data quality transaction on different distributed ledger technologies.  In International Conference on Big Scientific Data Management (BigSDM), pages 301–318. Springer, 2018.
  * [113] Xiaochen Zheng, Alba Vieira, Sergio Labrador Marcos, Yolanda Aladro, and Joaquín Ordieres-Meré.  Activity-aware essential tremor evaluation using deep learning method based on acceleration data.  Parkinsonism & related disorders, 58:17–22, 2019.
  * [114] Sehrish Shafeeq, Masoom Alam, and Abid Khan.  Privacy aware decentralized access control system.  Future Generation Computer Systems (FGCS), 101:420–433, 2019.
  * [115] Seongjoon Park and Hwangnam Kim.  Dag-based distributed ledger for low-latency smart grid network.  Energies, 12(18):3570, 2019.
  * [116] Andrew Cullen, Pietro Ferraro, Christopher King, and Robert Shorten.  Distributed ledger technology for smart mobility: Variable delay models.  arXiv preprint arXiv:1903.12466, 2019.
  * [117] Yepeng Ding and Hiroyuki Sato.  Dagbase: A decentralized database platform using dag-based consensus.  In IEEE 44rd Annual Computer Software and Applications Conference (COMPSAC). IEEE, 2020.
  * [118] Gautam Srivastava, Ashutosh Dhar Dwivedi, and Rajani Singh.  Crypto-democracy: A decentralized voting scheme using blockchain technology.  In ICETE (2), pages 674–679, 2018.
  * [119] Gautam Srivastava, Ashutosh Dhar Dwivedi, and Rajani Singh.  Phantom protocol as the new crypto-democracy.  In IFIP International Conference on Computer Information Systems and Industrial Management (CISIM), pages 499–509. Springer, 2018.
  * [120] Jamileh Bahri and Hamid Reza Shayegh Borojeni.  Electronic voting through de-pbft consensus and dag data structure.  In 9th International Conference on Computer and Knowledge Engineering (ICCKE), pages 391–396. IEEE, 2019.
  * [121] Zhiyi Zhang, Vishrant Vasavada, Xinyu Ma, and Lixia Zhang.  Dledger: An iot-friendly private distributed ledger system based on dag.  arXiv preprint arXiv:1902.09031, 2019.
  * [122] Pietro Ferraro, C King, and Robert Shorten.  Distributed ledger technology for smart cities, the sharing economy, and social compliance.  IEEE Access, 6:62728–62746, 2018.
  * [123] Juan Benet.  Ipfs-content addressed, versioned, p2p file system.  arXiv preprint arXiv:1407.3561, 2014.
  * [124] Ignacio Amores-Sesar, Christian Cachin, and Anna Parker.  Generalizing weighted trees: A bridge from bitcoin to ghost.  arXiv preprint arXiv:2108.13502, 2021.
  * [125] Sang-Min Choi, Jiho Park, Quan Hoang Nguyen, Andre Cronje, Ki-Young Jang, Hyunjoon Cheon, Yo-Sub Han, and Byung-Ik Ahn.  Opera: Reasoning about continuous common knowledge in asynchronous distributed systems.  arXiv, abs/1810.02186, 2018.
  * [126] Sang-Min Choi, Jiho Park, Quan Nguyen, and Andre Cronje.  Fantom: A scalable framework for asynchronous distributed systems.  arXiv, abs/1810.10360, 2018.
  * [127] Quan Nguyen and Andre Cronje.  Onlay: Online layering for scalable asynchronous bft system.  arXiv, abs/1905.04867, 2019.
  * [128] Quan Nguyen, Andre Cronje, Michael Gangyu Kong, Antonia Kampa, and George Samman.  Stakedag: Stake-based consensus for scalable trustless systems.  arXiv, abs/1907.03655, 2019.
  * [129] Qin Wang and Rujia Li.  A weak consensus algorithm and its application to high-performance blockchain.  In IEEE Conference on Computer Communications (INFOCOM). IEEE, 2021\.
  * [130] Qin Wang.  Improving the scalability of blockchain through dag.  In Proceedings of the 20th International Middleware Conference Doctoral Symposium, Poster Session (Middleware), pages 34–35, 2019.
  * [131] Qin Wang, Jun Zou, Yi Tang, and shiping Chen.  3d-dag: Improving the scalability and performance of blockchain through dag.  arXiv preprint arXiv:xxx, 2021.
  * [132] Quan Thanh Nguyen, Andre Cronje, Michael Gangyu Kong, Alex Kampa, and George Samman.  Stairdag: Cross-dag validation for scalable bft consensus.  arXiv, abs/1908.11810, 2019.
  * [133] Yonatan Sompolinsky and Aviv Zohar.  Phantom: A scalable blockdag protocol.  IACR Cryptology ePrint Archive, 2018:104, 2018.
  * [134] Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar.  Spectre : Serialization of proof-of-work events: Confirming transactions via recursive elections.  2017\.
  * [135] Adam Gagol and Michal Swietek.  Aleph: A leaderless, asynchronous, byzantine fault tolerant consensus protocol.  arXiv preprint arXiv:1810.05256, 2018.
  * [136] Team Rocket, Maofan Yin, Kevin Sekniqi, Robbert van Renesse, and Emin Gün Sirer.  Scalable and probabilistic leaderless bft consensus through metastability.  arXiv preprint arXiv:1906.08936, 2019.
  * [137] Vivek Bagaria, Sreeram Kannan, David Tse, Giulia Fanti, and Pramod Viswanath.  Prism: Deconstructing the blockchain to approach physical limits.  In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 585–602, 2019.
  * [138] George Danezis and David Hrycyszyn.  Blockmania: from block dags to consensus.  https://arxiv.org/pdf/1809.01620.pdf, 2018.
  * [139] Lei Yang, Vivek Bagaria, Gerui Wang, Mohammad Alizadeh, David Tse, Giulia Fanti, and Pramod Viswanath.  Prism: Scaling bitcoin by 10,000 x.  arXiv preprint arXiv:1909.11261, 2019.
  * [140] Tai-Yuan Chen, Wei-Ning Huang, Po-Chun Kuo, Hao Chung, and Tzu-Wei Chao.  Dexon: A highly scalable, decentralized dag-based consensus algorithm.  arXiv preprint arXiv:1811.07525, 2018.
  * [141] Xavier Boyen, Christopher Carr, and Thomas Haines.  Blockchain-free cryptocurrencies: A framework for truly decentralised fast transactions.  IACR Cryptology ePrint Archive, 2016.
  * [142] Zhaoming Yin, Anbang Ruan, Ming Wei, Huafeng Li, Kai Yuan, Junqing Wang, Yahui Wang, Ming Ni, and Andrew Martin.  Streamnet: A dag system with streaming graph computing.  arXiv preprint arXiv:1908.06405, 2019.
  * [143] Foundation.  Soteria-dag.  https://github.com/soteria-dag/soterd/blob/master/docs/README.md.
  * [144] Foundation.  Z-dag withepaper.  https://syscoin.org/zdag_syscoin_whitepaper.pdf.
  * [145] Chunming Liu, Daniel Wang, and Ming Wu.  Vite: A high performance asynchronous decentralized application platform.  https://github.com/vitelabs/whitepaper/blob/master/vite_en.pdf, 2018.
  * [146] Chenxing Li, Fan Long, and Yang Guang.  Ghast: Breaking confirmation delay barrier in nakamoto consensus via adaptive weighted blocks.  arXiv:2006.01072, 2020.
  * [147] A decentralized blockchain with high throughput and fast confirmation.  In USENIX Annual Technical Conference (USENIX ATC). USENIX Association, July 2020.
  * [148] Foundation.  Iot chain withepaper.  https://iotchain.io/pdf/ITCWHITEPAPER.pdf.
  * [149] Zsolt István, Alessandro Sorniotti, and Marko Vukolić.  Streamchain: Do blockchains need blocks?  In Proceedings of the 2nd Workshop on Scalable and Resilient Infrastructures for Distributed Ledgers (SERIAL), pages 1–6. ACM, 2018.
  * [150] Serguei Popov.  Local modifiers in the tangle.  Work in Progress, 2018.
  * [151] Haifeng Yu, Ivica Nikolic, Ruomu Hou, and Prateek Saxena.  Ohie: blockchain scaling made simple.  41st IEEE Symposium on Security and Privacy (S&P), 2020.
  * [152] Jianyu Niu.  Eunomia: A permissionless parallel chain protocol based on logical clock.  arXiv preprint arXiv:1908.07567, 2019.
  * [153] Martino Will, Quaintance Monica, and Popejoy Stuart.  Chainweb: A proof-of-work parallel-chain architecture for massive throughput.  https://d31d887a-c1e0-47c2-aa51-c69f9f998b07.filesusr.com/ugd/86a16f_029c9991469e4565a7c334dd716345f4.pdf, 2018\.
  * [154] Himanshu Gupta and Dharanipragada Janakiram.  Cdag: A serialized blockdag for permissioned blockchain.  arXiv preprint arXiv:1910.08547, 2019.
  * [155] Pierre Chevalier, Bartlomiej Kaminski, Fraser Hutchison, Qi Ma, Spandan Sharma, Andreas Fackler, and William J Buchanan.  Protocol for asynchronous, reliable, secure and efficient consensus (parsec) version 2.0.  arXiv preprint arXiv:1907.11445, 2019.
  * [156] Kaituo Cao, Fei Lin, Chaohui Qian, and Keyu Li.  A high efficiency network using dag and consensus in blockchain.  In IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom), pages 279–285. IEEE, 2019.
  * [157] Chun-Xuan Zhou, Qiang-Sheng Hua, and Hai Jin.  Hotdag: Hybrid consensus via sharding in the permissionless model.  In International Conference on Wireless Algorithms, Systems, and Applications (WASA), pages 807–821. Springer, 2020.
  * [158] Zhujun Zhang, Dali Zhu, and Baoxin Mi.  C-dag: Community-assisted dag mechanism with high throughput and eventual consistency.  In International Conference on Wireless Algorithms, Systems, and Applications (WASA), pages 113–121. Springer, 2020.
  * [159] Marcin Abram, David Galindo, Daniel Honerkamp, Jonathan Ward, and Jin-Mann Wong.  Democratising blockchain: A minimal agency consensus model.  arXiv preprint arXiv:2006.05390, 2020.
  * [160] B Swaroopa Reddy and GVV Sharma.  Scalable consensus protocols for pow based blockchain and blockdag.  arXiv e-prints, pages arXiv–2010, 2020.
  * [161] Keidar Idit, Kokoris-Kogias Eleftherios, Naor Oded, and Spiegelman Alexander.  All you need is dag.  arXiv preprint arXiv:2102.08325, 2021.
  * [162] Quan Nguyen, Andre Cronje, Michael Kong, Egor Lysenko, and Alex Guzev.  Lachesis: Scalable asynchronous bft on dag streams.  arXiv preprint arXiv:2108.01900, 2021.
  * [163] Neil Giridharan, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman.  Bullshark: Dag bft protocols made practical.  arXiv preprint arXiv:2201.05677, 2022.
  * [164] Sebastian Müller, Andreas Penzkofer, Nikita Polyanskii, Jonas Theis, William Sanders, and Hans Moog.  Tangle 2.0 leaderless nakamoto consensus on the heaviest dag.  arXiv preprint arXiv:2205.02177, 2022.
  * [165] Xuechao Wang, Viswa Virinchi Muppirala, Lei Yang, Sreeram Kannan, and Pramod Viswanath.  Securing parallel-chain protocols under variable mining power.  arXiv preprint arXiv:2105.02927, 2021.
  * [166] Aggelos Kiayias and Giorgos Panagiotakos.  On trees, chains and fast transactions in the blockchain.  In International Conference on Cryptology and Information Security in Latin America (LATINCRYPT), pages 327–351. Springer, 2017.
  * [167] Lyudmila Kovalchuk, Dmytro Kaidalov, Andrii Nastenko, Oleksiy Shevtsov, Mariia Rodinko, and Roman Oliynykov.  Number of confirmation blocks for bitcoin and ghost consensus protocols on networks with delayed message delivery.  In Proceedings of the 1st Workshop on Cryptocurrencies and Blockchains for Distributed Systems (CryBlock), pages 42–47. ACM, 2018.
  * [168] Serguei Popov, Olivia Saa, and Paulo Finardi.  Equilibria in the tangle.  Computers $\&$ Industrial Engineering (CAIE), 136:160–172, 2019\.
  * [169] Bartosz Kusmierz, Philip Staupe, and Alon Gal.  Extracting tangle properties in continuous time via large-scale simulations.  Technical report, Working Paper, 2018.
  * [170] Jing Li and Dongning Guo.  On analysis of the bitcoin and prism backbone protocols.  arXiv preprint arXiv:1907.05016, 2019.
  * [171] Niclas Kannengießer, Sebastian Lins, Tobias Dehling, and Ali Sunyaev.  Mind the gap: trade-offs between distributed ledger technology characteristics.  arXiv preprint arXiv:1906.00861, 2019.
  * [172] Bozhi Wang, Qin Wang, Shiping Chen, and Yang Xiang.  Security analysis on tangle-based blockchain through simulation.  In Australasian Conference on Information Security and Privacy (ACISP), pages 653–663. Springer, 2020.
  * [173] M Divya and Nagaveni B Biradar.  Iota-next generation block chain.  International Journal of Engineering and Computer Science (IJECS), 7(04):23823–23826, 2018.
  * [174] Seongjoon Park, Seounghwan Oh, and Hwangnam Kim.  Performance analysis of dag-based cryptocurrency.  In 2019 IEEE International Conference on Communications workshops (ICC WKSHP), pages 1–6. IEEE, 2019.
  * [175] Gerui Wang, Shuo Wang, Vivek Bagaria, David Tse, and Pramod Viswanath.  Prism removes consensus bottleneck for smart contracts.  Crypto Valley Conference on Blockchain Technology (CVCBT), 2020\.
  * [176] Team Rocket.  Demo visualization: Snowball protocol.  https://tedyin.com/archive/snow-bft-demo/#/snow, 2019.
  * [177] Penzkofer IAndreas, Kusmierz1 Bartosz, Capossele Angelo, Sanders William, and Saa Olivia.  Parasite chain detection in the iota protocol.  https://arxiv.org/pdf/2004.13409.pdf.
  * [178] Luigi Vigneri, Wolfgang Welz, Alon Gal, and Vassil Dimitrov.  Achieving fairness in the tangle through an adaptive rate control algorithm.  In IEEE International Conference on Blockchain and Cryptocurrency (ICBC), pages 146–148. IEEE, 2019.
  * [179] Adam Gagol, Damian Lesniak, Damian Straszak, and Michal Swietek.  Aleph: Efficient atomic broadcast in asynchronous networks with byzantine nodes.  In Proceedings of the 1st ACM Conference on Advances in Financial Technologies (AFT), pages 214–228, 2019.
  * [180] Andrew Cullen, Pietro Ferraro, William Sanders, Luigi Vigneri, and Robert Shorten.  On congestion control for distributed ledgers in adversarial iot networks.  arXiv preprint arXiv:2005.07778, 2020.
  * [181] Shuai Xiao, Xu An Wang, and Han Wang.  Large-scale electronic voting based on conflux consensus mechanism.  In International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS), pages 291–299. Springer, 2019.
  * [182] Tong Zhou, Xiaofeng Li, and He Zhao.  Dlattice: A permission-less blockchain based on dpos-ba-dag consensus for data tokenization.  IEEE Access, 7:39273–39287, 2019.
  * [183] Fu Xiang, Wang Huaimin, Shi Peichang, Ouyang Xue, and Zhang Xunhui.  Jointgraph: A dag-based efficient consensus algorithm for consortium blockchains.  Software: Practice and Experience, 2019.
  * [184] Vincent Gramoli.  From blockchain consensus back to byzantine consensus.  Future Generation Computer Systems (FGCS), 2017.
  * [185] Imran Makhdoom, Mehran Abolhasan, Haider Abbas, and Wei Ni.  Blockchain’s adoption in iot: The challenges, and a way forward.  Journal of Network and Computer Applications (JNCA), 125:251–279, 2019.
  * [186] Xu Wang, Xuan Zha, Wei Ni, Ren Ping Liu, Y Jay Guo, Xinxin Niu, and Kangfeng Zheng.  Survey on blockchain for internet of things.  Computer Communications, 136:10–29, 2019.
  * [187] Marko Vukolić.  Rethinking permissioned blockchains.  In Proceedings of the ACM Workshop on Blockchain, Cryptocurrencies and Contracts (BCC), pages 3–7. ACM, 2017.
  * [188] Gagandeep Kaur and Charu Gandhi.  Scalability in blockchain: Challenges and solutions.  In Handbook of Research on Blockchain Technology, pages 373–406. Elsevier, 2020.
  * [189] Dahlia Malkhi and Pawel Szalachowski.  Maximal extractable value (mev) protection on a dag.  arXiv preprint arXiv:2208.00940, 2022.
  * [190] Nicola Atzei, Massimo Bartoletti, Stefano Lande, and Roberto Zunino.  A formal model of bitcoin transactions.  In International Conference on Financial Cryptography and Data Security (FC), pages 541–560. Springer, 2018.
  * [191] Juan Garay, Aggelos Kiayias, and Nikos Leonardos.  The bitcoin backbone protocol: Analysis and applications.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), pages 281–310. Springer, 2015.
  * [192] Mohammad Javad Amiri, Divyakant Agrawal, and Amr El Abbadi.  Caper: a cross-application permissioned blockchain.  Proceedings of the VLDB Endowment, 12(11):1385–1398, 2019.
  * [193] Sébastien Forestier, Damir Vodenicarevic, and Adrien Laversanne-Finot.  Blockclique: scaling blockchains through transaction sharding in a multithreaded block graph.  arXiv preprint arXiv:1803.09029, 2018.
  * [194] Christopher Natoli, Jiangshan Yu, Vincent Gramoli, and Paulo Esteves-Verissimo.  Deconstructing blockchains: A comprehensive survey on consensus, membership and structure.  arXiv preprint arXiv:1908.08316, 2019.
  * [195] IOTA Foundation.  Coordinator-part-1: The-path-to-coordicide.  https://blog.iota.org/coordinator-part-1-the-pathto-coordicide-ee4148a8db08.
  * [196] Team Rocket.  Snowflake to avalanche: A novel metastable consensus protocol family for cryptocurrencies, 2018.
  * [197] Leemon Baird, Mance Harmon, and Paul Madsen.  Hedera: A governing council & public hashgraph network.  The Trust Layer of the Internet, Whitepaper, 1, 2018.
  * [198] Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich.  Algorand: Scaling byzantine agreements for cryptocurrencies.  In Proceedings of the 26th Symposium on Operating Systems Principles (SOSP), pages 51–68. ACM, 2017.
  * [199] Rafael Pass and Elaine Shi.  Fruitchains: A fair blockchain.  In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 315–324, 2017.
  * [200] Miguel Castro and Barbara Liskov.  Practical byzantine fault tolerance.  In Proceedings of the 3rd USENIX Symposium on Operating Systems Design and Implementation (OSDI), pages 173–186, 1999.
  * [201] Adam Back et al.  Hashcash-a denial of service counter-measure.  2002\.
  * [202] Christian Cachin and Marko Vukolić.  Blockchain consensus protocols in the wild.  arXiv preprint arXiv:1707.01873, 2017.
  * [203] Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov.  Ouroboros: A provably secure proof-of-stake blockchain protocol.  In Annual International Cryptology Conference (CRYPTO), pages 357–388. Springer, 2017.
  * [204] Rafael Pass, Lior Seeman, and Abhi Shelat.  Analysis of the blockchain protocol in asynchronous networks.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), pages 643–673. Springer, 2017.
  * [205] Ling Ren.  Analysis of nakamoto consensus.  Technical report, Cryptology ePrint Archive, Report 2019/943.(2019). https://eprint. iacr. org …, 2019.
  * [206] Christian Decker, Jochen Seidel, and Roger Wattenhofer.  Bitcoin meets strong consistency.  In Proceedings of the 17th International Conference on Distributed Computing and Networking (ICDCN), pages 1–10, 2016.
  * [207] Marko Vukolić.  The quest for scalable blockchain fabric: Proof-of-work vs. bft replication.  In International Workshop on Open Problems in Network Security (iNetSec), pages 112–125. Springer, 2015.
  * [208] Ittay Eyal and Emin Gün Sirer.  Majority is not enough: Bitcoin mining is vulnerable.  In International Conference on Financial Cryptography and Data Security (FC), pages 436–454. Springer, 2014.
  * [209] Christopher Natoli and Vincent Gramoli.  The balance attack against proof-of-work blockchains: The r3 testbed as an example.  arXiv preprint arXiv:1612.09426, 2016.
  * [210] Buterin Vitalik.  The problem of censorship.  https://blog.ethereum.org/2015/06/06/the-problem-of-censorship/, 2015.
  * [211] Rebstock Joseph.  Replay attacks in iota.  2018\.
  * [212] IOTA Foundation.  Structure of a bundle.  https://docs.iota.org/docs/iota-basics/0.1/references/structure-of-a-bundle.
  * [213] John R Douceur.  The sybil attack.  In International Workshop on Peer-to-Peer Systems (IPTPS), pages 251–260. Springer, 2002.
  * [214] Loi Luu, Viswesh Narayanan, Chaodong Zheng, Kunal Baweja, Seth Gilbert, and Prateek Saxena.  A secure sharding protocol for open blockchains.  In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 17–30, 2016.
  * [215] Tezos.  Tezos github.  https://gitlab.com/tezos/tezos, 2017.
  * [216] Juan A Garay, Aggelos Kiayias, Nikos Leonardos, and Giorgos Panagiotakos.  Bootstrapping the blockchain, with applications to consensus and fast pki setup.  In IACR International Workshop on Public Key Cryptography (PKC Wkshps), pages 465–495. Springer, 2018.
  * [217] Michael J. Fischer, Nancy A. Lynch, and Mike Paterson.  Impossibility of distributed consensus with one faulty process.  Journal of ACM (JACM), 32(2):374–382, 1985.
  * [218] Seth Gilbert and Nancy A. Lynch.  Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services.  SIGACT News, 33(2):51–59, 2002.
  * [219] Andrew Miller, Malte Möser, Kevin Lee, and Arvind Narayanan.  An empirical analysis of linkability in the monero blockchain.  arXiv preprint arXiv:1704.04299, 2017.
  * [220] Qin Wang, Bo Qin, Jiankun Hu, and Fu Xiao.  Preserving transaction privacy in bitcoin.  Future Generation Computer Systems, 107:793–804, 2020.
  * [221] Sunny King and Scott Nadal.  Ppcoin: Peer-to-peer crypto-currency with proof-of-stake.  Self-published paper, August, 19:1, 2012.
  * [222] Maxim Jourenko, Kanta Kurazumi, Mario Larangeira, and Keisuke Tanaka.  SoK: A taxonomy for layer-2 scalability related protocols for cryptocurrencies.  IACR Cryptol. ePrint Arch., 2019:352, 2019.
  * [223] Ittay Eyal, Adem Efe Gencer, Emin Gün Sirer, and Robbert Van Renesse.  Bitcoin-ng: A scalable blockchain protocol.  In 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI), pages 45–59, 2016.
  * [224] Eleftherios Kokoris Kogias, Philipp Jovanovic, Nicolas Gailly, Ismail Khoffi, Linus Gasser, and Bryan Ford.  Enhancing bitcoin security and performance with strong consistency via collective signing.  In 25th USENIX security symposium (USENIX Security), pages 279–296, 2016.
  * [225] Guillaume Vizier and Vincent Gramoli.  Comchain: Bridging the gap between public and consortium blockchains.  In 2018 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData), pages 1469–1474. IEEE, 2018.
  * [226] Rafael Pass and Elaine Shi.  Thunderella: Blockchains with optimistic instant confirmation.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), pages 3–33. Springer, 2018\.
  * [227] Christopher Copeland and Hongxia Zhong.  Tangaroa: a byzantine fault tolerant raft, 2016.
  * [228] Ethan Buchman.  Tendermint: Byzantine fault tolerance in the age of blockchains.  PhD thesis, 2016.
  * [229] Sigwit.  https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki.

## Appendix A: Mathematical Model Explanation

We give more detailed explanation of the property acyclic in our DAG-based
model. The definition in Section 3 is stated as:

$\begin{array}[]{ll}\begin{aligned} &{\ddagger}:\,\textit{{Assume
that}}\,\,u_{i}\in\\{u_{1},u_{2},...,u_{l}\\}\subseteq\mathcal{V}:\,\,\,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\forall\\{i,j,k\\}\in[1,l]},\,\\\
&\quad
where\,\,k>j>i,\,\,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}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}$

We emphasize two critical points in our mathematical model (highlighted in
blue). The first first key point of avoiding the loop graph is the settings of
dynamical boundary of the range $[i,k]$. The parameter $i$ and $k$ are set to
be variable, acting as a sliding window. The second key point lies in the
settings of parameter set $j$. Here, $j$ can be either a single element or a
subset that contains multiple elements in the range of $(i,k)$.

Elements |  Vertex Sets |  Boundary Settings
---|---|---
$\textrm{size}(j)=0$ |  $\\{i,i+1\\},...,\\{j,j+1\\},...,\\{k-1,k\\}$ |  $i\in[1,l-1],k\in[2,l]$
$\textrm{size}(j)=1$ |  $\\{i,i+1,i+2\\},...,\\{j-1,j,j+1\\},...,\\{k-2,k-1,k\\}$ |  $i\in[1,l-2],k\in[3,l]$
$\textrm{size}(j)=2$ |  $\\{i,i+1,i+2,i+3\\},...,\\{k-3,k-2,k-1,k\\}$ |  $i\in[1,l-3],k\in[4,l]$
$\textrm{size}(j)=n$ |  … |  $i\in[1,l-n-1],k\in[1+n,l]$
$\textrm{size}(j)=l-2$ |  $\\{i,i+1,,...,k-1,k\\}$ |  $i=1,k=l$

We give concrete examples as follows.

  * -

Case I: Assume that $j=\varnothing$, the definition deteriorates into the
first property of unidirectional where $u_{i}\leftarrow u_{k}$ and
$u_{k}\leftarrow u_{i}$ cannot co-exist.

  * -

Case II: Assume that $j$ is a single element which belongs to $(i,k)$. It
ensures when $u_{i}\leftarrow u_{j}$ and $u_{j}\leftarrow u_{k}$, no edge of
$u_{k}\leftarrow u_{i}$ exists. This avoid all loops made up by three vertices
.

  * -

Case III: Assume that $j$ a subset that contains several elements. For
simplicity, we suppose totally $5$ vertices in the graph, where
$u_{i}\in\\{u_{1},u_{2},...,u_{5}\\}$ and $l=5$. In this case, as
$1\leq\textrm{size}(j)\leq 3$ (here, $3=l-2$), we list all potential vertex
sets covered by our model.

    * $\circ$

$\textrm{size}(j)=1$: {1,2,3}, {1,2,4}, {1,2,5}, {2,3,4}, {2,3,5}, {3,4,5}. In
this situation, our definition avoids loops that are consisted of $3$
vertices.

    * $\circ$

$\textrm{size}(j)=2$: {1,2,3,4}, {2,3,4,5}. In this case, our model avoids
loops made by $4$ vertices.

    * $\circ$

$\textrm{size}(j)=3$: {1,2,3,4,5}. In this case, our model avoids loops
containing $5$ vertices.

##  10\. Appendix B. General Description of Our Types

We analyze consensus mechanisms and corresponding features of existing DAG
systems. In this part, we merely provide a very rough description for quick
access. Detailed discussions for each DAG blockchain system are presented in
Section.4. The following contents are aligned with our summaries in Table.3.

Type I systems are blockless. The topology of transactions is a naturally
expanding graph. The systems in this type follow the simplest design when
compared to others – a transaction can directly verify the ancestors. The only
restriction comes from their rules of graph extension. IOTA [22] and Graphain
[81] adopt a similar tip selection rule (TSA), in which one newly attached
transaction can verify multiple ancestor transactions. Avalanche [75] utilizes
a sampling method to randomly select the child set of transactions in each
round. Type II systems deviate from Type I by introducing the block to package
transactions. These blocks are structured as a naturally expanding graph.
Spectre [134] employs the recursive traverse algorithm to collect transactions
and determines a pairwise order between two blocks by voting. Phantom [119]
extends the graph via a greedy algorithm to gradually include valid blocks.
Meshcash [83] combines slow PoW-based protocols with a fast consensus
protocol. Systems of these types obtain scalability (processing) and
flexibility (design).