What is a DAG (Directed Acyclic Graph)?

0
111
What is a DAG (Directed Acyclic Graph)?
What is a DAG (Directed Acyclic Graph)?

The Directed Acyclic Graph (DAG) is a type of graph applied in the context of distributed register technology. Often put in opposition to the blockchain, some projects in the cryptocurrency industry use it to develop the infrastructure of their platform—a detailed presentation of the DAG, its applications and its differences from the blockchain.

What is a DAG?

The DAG, acronym for “Directed Acyclic Graph”, meaning is a type of graph that has its origins in history even before graph theory was defined. Indeed, a DAG is a set of nodes representing something which are connected to each other directly in such a way that there are no loops.

In 1736, Leonhard Euler, a Swiss mathematician, managed to solve Koenigsberg’s seven bridges problem using what is considered the first theorem of graph theory.

This problem was to determine if there was a path in the streets of the city by which it was possible to pass to borrow only once each of the seven bridges and return to the starting point.

sfiLdjwTmtRJzQ0opXCzMxsuLvJzquRGOnp9IplOgM8 d cUe33eRdGd JjnB0FoEzcOEuQrGTrhweWrYF59vFjPO7QfvuMQzs

Figure 1: Illustration of Koenigsberg’s seven bridges problem

From there, graph theory became a field of study concerned with the relationships between objects represented by mathematical structures (graphs).

There are many types of graphs, and the Directed Acyclic Graph  (DAG) is one of them.

One of the oldest DAG models is simply the family tree. This model has been used since ancient Rome to illustrate family ties between individuals.

The family tree is a graph that is oriented since it goes in a single direction (from ancestors to descendants) via direct links and acyclic since no one can be their own parent: no turning back is possible.

Another very old DAG model is simply task scheduling. The complexity of the graph varies depending on the magnitude of what one is trying to accomplish, whether it is cooking a recipe or planning a war.

The DAG is therefore not an invention of recent years, it is an old method for solving various problems, and it is notably used a lot in computer science to model data. Of particular interest to us here is the application of DAG in the context of distributed ledger technology.

rUFgjojLXoJukayHryiYq4fxoqRfvISb6AzeX2Q sL0ZzHTRAjyWBWCo

Figure 2: Diagram of a DAG

A DAG, therefore, has a tree structure, which has only direct links between its nodes and no cycles; that is to say that you cannot fall back on the same node during navigation in the graph. This allows direct navigation from node to node through the links of the latter.

Figure 3: Simplified diagram of a DAG with its direct links and acyclic nature

We see that in Figure 3, representing a simplification of the DAG, the direction is clear: from the node at the bottom right to the node at the top left, connected by direct links. It is therefore oriented towards a single direction and acyclic since it does not go back.

This allows the DAG to process transactions simultaneously, giving this technology a high level of scalability. This is one of the main reasons for using a DAG in the cryptocurrency industry.

Some applications of the DAG in the cryptocurrency industry

Phantom (FTM)

Fantom is a smart contracts platform using a DAG to solve the scalability problem of blockchains.

IOTA (MIOTA)

This cryptocurrency is based on a DAG called Tangle and uses a Proof of Work (PoW) consensus. This DAG is designed to record and execute transactions between machines and devices of the Internet of Things (IoT), but also to provide a way to monetize the data. The Internet of Things requires very high scalability, which explains the choice of the DAG for this project.

WziYMFM79lrEg4C9z3OU5LJMXZcyI1s5jFeugPY4OtXmMVNzfAi Y9LRvbgTZC4V2kfbWuEk4hOmq9 silHMOln5fRYF3iyU0F8KXF7vUca0JX2L0o8D6 oGXhlZz1zXmbiXlpj2VL7haAGKjQ

Figure 4: Representation of the IOTA DAG

Nano (NANO)

The Nano is a cryptocurrency with the ambition to be an alternative to fiat currencies thanks to its instantaneous and free transactions, as well as low energy consumption. It relies on a DAG to try to achieve these objectives.

Avalanche (AVAX)

Avalanche is a platform dedicated to the deployment of smart contracts. Its eponymous consensus uses a DAG to process multiple transactions in parallel and thus improve the scalability of the network.

Hedera Hashgraph (HBAR)

This network relies on its information transmission system, the Gossip protocol, which is concretely a DAG, in an attempt to solve the blockchain trilemma (security, scalability and decentralization) that blockchains face.

How do DAGs work?

DAGs are structures composed of two different types of elements, the nodes and the links between them. This can be used in the context of keeping a history of data such as versions of software or interactions between users.

In particular, this avoids the conflicts associated with using a linear history in which the addition of a new element must be directly linked to the most recent element and only the latter.

Within the framework of versions of a software, version 5 can only be linked to version 4 in a linear framework. Using a DAG, this version can be linked to version 3, while version 6 will link versions 4 and 5.

Simply specify the parent node(s) to add new data to a DAG and define the bindings between them. Regarding the course of a DAG, there are different algorithms that each have their own specificities. A DAG facilitates the use of certain algorithms compared to other more general graphs; this is the case in particular of the search for the shortest or longest paths between two specific nodes.

What are the Differences between a DAG and a Blockchain?

Some consider DAG to be a rival technology to the blockchain since it is another type of distributed ledger. What are the differences between these two systems?

HrLYOsSbewjJpG h2VwsPxo2bfm0fNTKKgQW LYS3hPZOvyRqekzpkbIjgXghNMZonmc8121iDIzQi6v5C0HXIuU9qj85jP31Q4r7GItK 7TvVMdNyac01h7YWMuYByzG0s DXI9ZVgw1oYk A

Figure 4: Representation of a blockchain and a DAG

As we see in Figure 3, a blockchain is a distributed ledger that forms a chain of blocks in chronological order. Transactions are grouped into a block which is validated and added after previously validated blocks.

Although two blocks (or more) can theoretically be validated at the same time by miners, only one of the two will be attached to the main chain, the other being what is called a stale block (purple blocks on the plan).

Because of this, if there are more transactions performed than the limit of transactions a block can incorporate due to the storage space limit, it is necessary to wait for the next block, which causes a delay in transaction confirmation; this potentially leads to network congestion if too many transactions are pending.

A DAG does not face these problems since there are no blocks to speak of. A DAG is a network of individual transactions linked to multiple other transactions. Transactions are, therefore, directly added to the ledger, and there is almost no delay, so the execution of transactions is very fast.

Individual transactions validate each other through a process that confirms previous transactions with new transactions.

With a DAG, for a new transaction A to be added to the ledger, it must reference several prior transactions. Then, it will be necessary to wait for a new transaction B which notably references transaction A for it to be confirmed. This also explains the very low transaction fees in a DAG, but also that a DAG needs an adequate level of adoption to function properly.

To avoid the problem of double spending on a DAG, when a previous transaction is confirmed, the node verifies the entire path from that transaction to the first transaction in the DAG. Thus, if a path does not go back there, no node will want to validate it.

Each transaction has a different cumulative weight, i.e. a different number of cumulative confirmed transactions. Thus, those with a higher weight will be favored by an algorithm for the DAG to grow around and improve network security.

Finally, most DAG-based cryptocurrencies operate on a variation of Proof of Stake (PoS) since no miners are required, with the exception of Iota and its Proof of Work (PoW) partial to improve network security.

Blockchain could be simply summarized as a list of blocks, while a DAG could be likened to a tree of transactions.

Advantages and disadvantages of using a DAG

Advantages

A DAG does not need to depend on classic Proof of Work to validate transactions, which means that it does not need blocks and, therefore, no chain, which is a definite gain in terms of energy consumption.

A DAG makes it possible to offer a high level of scalability to the network due to its architecture since it is not limited by the blocks. This, coupled with extremely low, if any, transaction fees and fast transactions, make it the main selling point for applying a DAG in a distributed ledger.

Disadvantages

Lack of decentralization is the main flaw mentioned when talking about a DAG. Most protocols operating on a DAG need to maintain certain elements that make it a relatively centralized technology. DAGs have yet to prove whether they can scale independently, as this poses a network security risk that is potentially more vulnerable to attack.

Finally, a DAG has never before been subjected to a very high level of transaction volume. There are, of course, several cryptocurrencies that have been operating on a DAG for several years, but these still have a long way to go before they reach high enough adoption to test the technology on a large scale.

Conclusion on DAGs

Cryptocurrencies operating on a DAG are still few in number. Still, this technology can be particularly useful in areas that require a high level of scalabilities, such as micro-payments or the Internet of Things.

It will also be important to observe in the future whether the DAG has the capacity to offer a high level of decentralization as it evolves. That said, it remains an attractive blockchain alternative for distributed ledgers.