What's Going on with DAG?

DAG (Directed Acyclic Graph) is a kind of distributed ledger technology different from the mainstream blockchain. Since it can upgrade synchronous accounting to asynchronous accounting, it’s widely believed to solve the high concurrency problem of traditional blockchain as an innovation from capacity to speed. However, is DAG technology really so powerful?

This article aims to introduce the architecture, development trends and typical applications of DAG technology to the readers to provide a new idea on the development of blockchain.

What’s DAG?

DAG stands for Directed Acyclic Graph.

DAG used to be a common data structure of computers science and it’s often used to deal with various algorithms, such as dynamic planning, shortest path in navigation and data compression, due to its excellent features resulting from the unique topology.

Whats Going on with DAG IMG 10

Let’s have a look at the difference between traditional blockchain and DAG. Briefly speaking:

Unit: The blockchain component is Block while the DAG component is TX (transaction);
Topology: The blockchain is a single chain consisting of Block blocks, which can only be written in orders based on the blocking time in the same way of single-core single-thread CPU. The DAG is a network composed of TX units, which can be written asynchronously and concurrently in the same way of multi-core multi-thread CPU;
Granularity: Each unit of blockchain records multiple transactions for multiple users and each unit of the DAG records the transaction of a single user.

Several problems in traditional blockchain technology:

Efficiency: The traditional blockchain technology is based on the Block and the efficiency of bitcoin has been relatively low. Due to the chained storage structure of blockchain, the entire network can only have one single chain at the same time. The block generation on the basis of POW consensus mechanism cannot be executed concurrently; taking bitcoin for example, one block is generated every ten minutes and each block needs to have 6 confirmations, so the whole process will take about one hour. In the Ethereum, the blocking speed has been greatly improved to less than dozen seconds.
Certainty: Bitcoin and Ethereum are not immune to the 51% hash attack. The biggest hidden risk based on the POW consensus is the lack of definitive unchangeable final state; if certain group controls 51% of the hash to launch attacks, the bitcoin system is bound to collapse; considering the mining worker group in the real world as well as the amazing hashrate of quantum computers, such a kind of risk really exists.
Centralization: In the block-based POW consensus, the workers can form a centralized mining group on one hand, while on the other hand, those with packaging rights can own great authority to decide which transactions to enter the blocks and which not to be processed. They can even package the transactions which are in their own interest. So, such risks have really existed.
Energy consumption: Since the traditional blockchain is based on the POW consensus mechanism, the energy consumption of bitcoin has been equal to the electricity consumption in Argentina. The IMF and many governments are critical on the energy consumption of cryptocurrency mining.

The global mining generates a total of approximately 290 million tons of carbon emissions per year. Image credit: cryptoinvestigator.com

Due to the aforesaid problems, some people may ask: Why are the blocks necessary? The DAG technology is tried to solve the aforesaid problems in the blockchain.

Origin of DAG

It’s in the year 2013 that the DAG concept was introduced in the blockchain as a consensus algorithm for the first time. At the bitcointalik.org forum, the scholar of The Hebrew University of Jerusalem, whose ID is avivz78, proposed to use the GHOST protocol as a transaction processing capacity expansion solution for Bitcoin; the POS consensus protocol described in the Ethereum Purple Paper by Vitalik Casper is also a POS variant based on the GHOST POW protocol.

Later, those in the NXT community proposed to use DAG topology to store blocks and solve the problem of blockchain efficiency. With only one single chain, the packaging and trading of blockchain cannot be conducted concurrently. If the chained storage structure is changed into the mesh topology, the concurrent write-in can be realized. In the case of unchanged packaging time, N blocks can be packaged concurrently in the network so that the transactions can be expanded N times.

Then, the concept of combining DAG and blockchain still stayed in the idea of side chain solution while the transaction package can be conducted concurrently in different branch chains to improve efficiency and performance. The DAG still carried the concept of blocks then.

Whats Going on with DAG IMG 02

In September 2015, Sergio Demian Lerner published the paper DagCoin: a cryptocurrency without blocks, in which he proposed the concept of DAG-Chain. For the first time, the DAG network was improved from the coarse-grained block level to the transaction-based level. However, DagCoin itself was only a thesis without code support for implementation.

The concept of DagCoin enabled each transaction to be directly involved in the transaction order of the whole network. Once the transaction is initiated, it will be directly broadcast in the entire network by skipping the stage of packaging to realize the so-called Blockless. Then, the packaging time can be saved. As being mentioned above, the DAG and blockchain were combined to improve the efficiency. Now, since there’s no need to confirm the packaging and the transaction will be directly confirmed after being initiated in the entire network, the efficiency will be improved theoretically. DAG has evolved into a solution which completely abandons the blockchains.

In July 2016, the IOTA was born based on the genesis post at Bitcointalk. Then, ByteBall also debuted. IOTA and Byteball realized the DAG technology for the first time and became the most dazzling leader in this field. At that time, the DAG chain family known as the unique block-free chain almost came into being.

In one word, DAG is a new generation of blockchain for the future. From the perspective of graph topology model, it’s an innovation of capability and speed in the blockchain from single-chain to tree and mesh chains, from block granularity to transaction granularity and from single point to concurrent write-in.

Current Development of DAG

The most well-known representative projects of DAG is undoubtedly the troika of DAG — IOTA, Byteball and Nano (original Raiblocks). When IOTA jumped to the fourth in the currency rankings in the second half of 2017, DAG started to attract attentions as the latest main competitive technology of distributed ledger. Later, the new projects based on DAG technology debuted one after another.

IOTA

Whats Going on with DAG IMG 07

The most important innovation behind IOTA, Tangle, is a newly-designed distributed ledger structure based on DAG technology. It’s a blockchain with neither blocks nor chains. In Tangle, each node represents one transaction. In IOTA there are neither blocks nor the concept of mining and workers, which means no transaction fees and high throughput of the entire network. So, that’s the most attractive highlight of IOTA.

The core principles of Tangle are still one distributed database, P2P network and transaction validation based on consensus algorithms, which is consistent with that of blockchains. The main difference between them is the data structure and consensus mechanism of Tangle.

In IOTA there’s only transaction network instead of the concept of blocks. Every transaction will quote two TX records in the past, so that the previous TX will prove the legitimacy of the two completed transactions as well as all the transaction in the past indirectly.

In this way, the entire network will participate in the verification of transaction legitimacy, instead of only a small number of nodes in the entire network (or the owner of the PoS) to verify the legality of the transaction in the traditional blockchain. Therefore, the IOTA consensus is the internalization of its own, which makes it possible to form scales without transaction costs. IOTA has no concept of blocks and the transaction is just the smallest unit of consensus.

Another advantage of the Tangle is the its capability of stripping transactions from the network or merge them back. Such a capability of offline asynchronous processing is especially important in the application of the IOT.

Current problems for IOTA:

Firstly, the MIT report points out that IOTA uses its own hash algorithm curl, but it’s easy for the hash value of curl algorithm to suffer from collision, so the counterfeit digital signatures can be realized.
Secondly, since the consensus is determined by the whole network transaction, then in theory, if someone can generate 1/3 of the transaction volume, he can turn the invalid transactions into valid ones. On the other hand, since IOTA demands no transaction fees, there is no incentive for mining workers, either, so IOTA will face the possibility of denial service attacks and spam attacks. It’s just like a community without charging service fees, it is difficult for the property owners to clear the illegal elements alone.
Thirdly, IOTA introduces a closed-source centralized component Coordinator to check the entire network transactions (for example, double-spending). As for how to effectively remove the Coordinator and establish a decentralized “Coordinator group” with benign incentive mechanism, the IOTA has not provided the solution yet.

Byteball

Whats Going on with DAG IMG 04

Byteball is called the representative of blockchain 3.0. With the most complete application ecosystem in the DAG family, Byteball wallet has rich built-in features, including BotStore similar to the Appstore in which free developers can freely develop applications, so the developers are very active.

Based on DAGCoin, Byteball introduces the concept of main chain and witnesses in a creative way and encourages the verification of multiple parent TX units to form a digital-signature hash network with increasing transactions, mutual verificatios and enhanced security. Byteball creatively introduces the “main chain” concept, that is, the Parents preferred algorithm of the shortest path MC identified by the witness. The main chain creates a TX time sequence based on the whole network consensus to elegantly avoid the problem of double spending.

The true meaning of “witnesses” in Byteball is the establishment of consensus mechanism; the TX units issued by 12 “witnesses” draw a deterministic transaction time sequence in the DAG concurrent trading network which theoretically infinite wide. It’s the transaction sequence with infinite extension based on the deterministic time that creates the main chain in the Byteball to establish a strong and orderly unique backbone in the broad, disordered, directed and acyclic hash world. Based on the consensus mechanism of witness + main chain, the problems such as double spending have been easily solved.

Abandoning the concept of blockchain and POW mining, Byteball chooses the DAG data storage technology. Compared with the traditional blockchain cryptocurrency, it has a strong advantage. All transactions in Byteball are related to encryption and the newly generated transactions will be added to the tips trading unit, so that all the nodes (users) on the network can participate in the verified transactions to realize complete decentralization.

It can not only realize faster verification of payments, but it also keep the network being dispersed enough and avoid some problems in bitcoin: for example, the large centralized pools which may threaten the network; meanwhile, Byteball can reduce SPAM on the network by charging data storage fee based on every byte stored on the DAG network.

Some people claim that the Byteball Witness depends on the centralization. We’d like to make it clear here that in design of Byteball Witness node, the witness node is very safe because it can only issue witness units instead of accessing to transactions, so the Witness is not the mining worker and it just plays the role of WatchMan to help the system to anchor the TX time sequence without any space for evil actions; in addition, the number of Witness can also be set and selected according to requirements, not limited to 12 witnesses currently.

Since every transaction carries the private key signature of the initiator and every transaction will be verified and quoted from previous transactions, a huge network will be woven in which any tampering will trigger wide effect on the entire network. Meanwhile, it’s impossible for anybody to own the private keys of all the users on the network, so Byteball owns the bank-grade security.

The problems for Byteball include: since the main chain algorithm is related to the witness release frequency, the time of transaction confirmation is uncertain; because Byteball stores data based on relational database and SQL language is too coupled with algorithm logic, the expansion capabilities and speed of Byteball has been restricted to some extent currently.

NANO(XRB)

Whats Going on with DAG IMG 09

Nano (originally known as RaiBlocks XRB) is a new type of cryptocurrency based on the Block Lattice structure.

Nano creatively adopts the way of one user for one chain to record its own transactions only, so that only itself can modify the records. It does not share data with other accounts so that all transactions can be done concurrently. With second-level transaction speed and unlimited scalability, it allows them to update to the rest of the network asynchronously to realize fast confirmation at the minimal cost of resources.

One Nano node can store the history records of all accounts or only the last modification record of each account. When one transaction occurs, the party that issues the amount will generate a block of send Tx in which contains the deduction amount; and the receiver account will generate the receive Tx block based on corresponding amount. The transaction data can be sent and received asynchronously, so there will be no problem even if multiple amounts are remitted into one account concurrently, because the final amount is the addition of all the received amounts. If the receiving part is not online, it does not matter. The amount unreceived will be marked separately. Once the receiving part is online, the amount will enter the receiving block from the unsettled area to complete the transaction.

NANO adopts the DPOS consensus mechanism. The account can designate representative to vote for it and the representative with the most votes will handle the fork, broadcast it to the network and observe the voting results from the high-authority account nodes in a fixed time to determine which block to be kept. DPOS can ensure the block operation with reasonable low energy consumption. NANO also adopts the POW mechanism to confirm the transactions of very little proof of work (PoW).

The problems for NANO: not fully tested, lacking peer reviews, consensus algorithm may have the risk of serious defects. For example, what happens if there’s no enough quorum to resolve the network conflict? Another big problem: If some parts of the NANO network are separated for a long time, what happens when the separated network comes back to join again? Will the rejoined network fail in the inevitable voting process?

Whats Going on with DAG IMG 03

DAG Innovation and Trend

DAG technology is undergoing rapid development and innovation. In addition to the troika, the emerging DAG projects have made new progress in consensus algorithms, decentralization mechanism, speed and concurrency. The recent projects which have attracted wide attentions include:

HashGraph

Whats Going on with DAG IMG 05

Hashgraph is a Gossip protocol consensus algorithm developed by Leemon Baird. All nodes randomly share the known transactions with other nodes, so that all transactions can be delivered to all nodes ultimately. Hashgraph is very fast (more than 250,000 transactions per second). Due to the closed-source and patent, Hashgraph is suitable for private chain or alliance chain instead of being applied to the public chain with scale verification within short period of time.

Hashgraph took the initiative to focus on the asynchronous BFT consensus in the public chain. One big problem for the traditional BFT is the high message complexity has largely consumed the network bandwidth so that dynamic network cannot be well handled. So, Hashgraph introduces the traditional Gossip Protocol with unique innovation as well as the virtual voting mechanism, so that the sudden large-scale messaging storm will not occur when a consensus is needed.

Hashgraph and Algorand improve the BFT application conditions from different aspects to make BFT consensus applied to the public chain. HG adopts the Gossip and conduct virtual voting to minimize the instantaneous communication required by traditional consensus while ensuring the consensus efficiency of local computer.

The latest Hashgraph business manual introduces the switching to POS and supports to DOPS, which allows holders who do not run the entire node to choose agents and share revenue.

Hashgraph has made great breakthroughs in scalability, security and consensus cost, but it has not run in a large-scale public chain due to high technical difficulty. If what has been described in the rigorous mathematics and application testing HG white paper can be realized, Hashgraph would certainly be regarded as an important milestone in the exploration of the trusted Internet.

SPECTRE/PHANTOM

SPECTRE Protocol adopts the Block+DAG technology supporting concurrent mining with greater throughput and instant payment; In February, 2018, SPECTRE releases the expansion protocol, Phantom, to greatly expand the network transaction capacity with compatibility with smart contracts. As “the blockchain generalization proposed by Nakamoto Satoshi”, the technology solves the compatibility between security and capacity expansion, so it’s more suitable for building faster or larger blocks. .

Unlike the off-chain solution such as lightning network, PHANTOM is an on-chain expansion solution. Meanwhile, the linear ordering will sacrifice the achievable transaction confirmation speed to a certain extent.

Hycon

Whats Going on with DAG IMG 06

As a DAG project in South Korea, Hycon focuses on the platform-type public chain and relevant ecology, including the exchange of decentralized value medium. It’s ready to raise nearly one billion US dollars of funds and the other 70% will depend on mining.

The entire ecosystem to be built includes three phases: value exchange media, blockchain platform and decentralized exchange, which aim to create a value ecosystem of value exchange, business applications and Token circulation. Wherein, the blockchain platform is the core of the entire ecosystem, which will solve the performance bottleneck such as low transaction confirmation speed and limited throughput, to achieve business-grade applications.

The main features of Hycon public-chain platform: instant payment, on-chain transaction scalability (up to 3000 TPS transaction throughput at 2MB/S), concurrent block production (can link blocks based on DAG structure location instead of time order) and smart contracts.

Algorand

Whats Going on with DAG IMG 01

Algorand, the popular star project in the world lately, aims to build a distributed ledger with low energy consumption, high speed and democratization, good scalability and almost no forks. Algorand does not introduce incentives or issue cryptocurrencies. Algorand was developed by MIT professor SivioMicali, the winner of Turing Award, by $4 million of fund-raising.

GHOST, SPECTRE, and Meshcash are partial proposals to improve bitcoin throughput lately. They adopt the tree or DAG to replace the ledger structure of bottom blockchains to solve the problem of fork conflicts. These protocols use POW consensus to greatly improve throughput through a well-designed selection rule for tree/graph branches.

Summary

Everything has its advantages and disadvantages. DAG is fast with high throughput. However, as a very young data structure, its security and consistency have yet to be verified and recognized, and its applications are not as extensive as some traditional blockchains; However, the DAG technology has displayed more and more advantages and higher innovation speed. More DAG-based innovation projects and DAPP are rapidly emerging correspondingly.

People like to compare DAG with traditional blockchains nowadays, but we believe that DAG is only a technical implementation of distributed ledger application. Some innovative blockchain projects have already been exploring the integration mode of Block+DAG.

In a broad sense, DAG is only a component technology of general blockchains. As the key components, blockchain and Token economic drive will greet the arrival of the 4th value internet tide together with AI, big data, AR/VR and 5G high-speed wireless network.

Appendix

Series articles on cryptocurrency introduction and analysis at EastShore: