What is a directed acyclic graph (DAG)?

Directed-Acyclic-Graph-(DAG)
6 min read

As many of you know, the blockchain revolution consists of creating a distributed ledger, also called a distributed ledger. This ledger is where cryptocurrencies live and change ownership. Its maintenance does not depend on central points of failure, that is, it is decentralized.

 

This is why blockchains (if they are well built, with a native currency) offer us access to monetary and financial platforms freely and without trust. But since 2009, the year Bitcoin was launched, the research to create better technologies has not stopped, and one of those areas under development are cryptocurrencies based on Directed Acyclic Graph or simply DAG.

Blockchain data structure

As its name suggests, the information in a blockchain is organized in linked blocks. Each block points to a parent block (the previous block), specifically with the hash of the previous block header.

Actually the blockchain structure existed long before Bitcoin but the real innovation brought by blockchains (of cryptocurrencies) are the consensus protocols, such as the Proof of Work.

These protocols make modifications to the registry have a cumulative cost (depending on the block height), offering some guarantee that transactions will not be reversed and money stolen. They achieve all this by using the properties of the information structure we have described, the blockchain.

This is why the word blockchain is used to refer, rather than to the data structure itself, to distributed ledger technology (DLT).

 

In these distributed ledgers, blockchain blocks contain transactions, are generally limited in size so as not to cause centralization, and occur at an interval that can range from seconds to minutes.

DAG structure and difference with blockchain

Directed Acyclic Graph is a data structure different from the blockchain that comes from Graph Theory. Data are represented as vertices or “nodes” and are connected to each other by edges. The edges represent a vertex connecting to a previous vertex, in the same way that the blocks of the blockchain are linked to each other.

 

“Directed” comes from the fact that these edges have a direction. This also happens in the blockchain where block 70 points to 69, 69 to 68, and so on up to the genesis block.

 

The “Acyclic” part comes from the fact that you can’t give loops, it’s acyclic. Again, similar to blockchain. Block 69 cannot point to block 70. In fact, block 70 is built and added later, so block 69 cannot reference it beforehand.

This makes perfect sense because this registry only consists of adding new transactions grouped in blocks, which are transmitted over the P2P network on the fly. The blockchain therefore only grows in one direction.

 

But what differentiates DAG from a blockchain is that a vertex can reference different previous vertices, while in the blockchain there is only one parent block.

¿Qué es Directed Acyclic Graph (DAG)?

DAG-based distributed ledger

DAG-based cryptocurrencies work without using the famous transaction blocks. The transaction ledger becomes a continuum of linked transactions (instead of blocks). The transactions are the vertices of the DAG and the hashes are the edges.

 

When a user wants to make a transaction he has to solve a proof of work (much less expensive than Bitcoin). The proof consists of following an algorithm to see which transactions to build on (which transactions to target with hashes) and verify that these transactions are valid.

 

Once this test is done, the user transmits his transaction through the network and the network confirms the transactions he has referenced. In the same way the user’s transaction remains unconfirmed until it is referenced by other transactions. In general the algorithms are implemented in such a way that it will be more likely to build on transactions with more cumulative commits. For example, it will be more likely to build on a transaction that has committed 5, than on one that only references 1.

Just as in Bitcoin a transaction is more difficult to reverse the higher the number of confirmations, the same would happen here, although we do not know how many confirmations would be necessary to consider the transaction sufficiently secured. Under this design there is no miner and the accumulated work comes from the users.

 

The specific rules for reaching consensus depend on each implementation and could vary quite a bit, for example, using centralized servers.

¿Qué es Directed Acyclic Graph (DAG)?

Advantages and problems

Among the advantages of this type of system are shorter confirmation times, greater scalability as they are not subject to block size limitations and very low or non-existent commissions.

 

However, as we have already explained on different occasions, there is no free lunch in the blockchain world. If the number of transactions does not have a limit, the registry can grow too large and prevent users from verifying the information without trusting third parties, causing centralization.

 

The shorter confirmation times are really irrelevant, because what really matters are the finality guarantees. Waiting 10 minutes in Bitcoin could, for example, give you a thousand times more security than 10 minutes in a DAG system.

 

Another problem is that these systems are not fully decentralized and rely on points of failure such as coordination servers. The implementations are also centralized as is the case with Hedera Hashgraph and IOTA.

 

In conclusion this technology could be interesting if decentralization is not a priority. The problem is that these systems are not sufficiently tested and may be insecure. 

 

When looking for scalability, in my opinion, and surely in the opinion of many, it is much better to use second-layer technologies such as Lightning Network and ZK-Rollups that already run on secure, decentralized blockchains.