What is a Directed Acyclic Graph?

A directed acyclic graph (DAG) is a distinctly different data structure that can be thought of as a database connecting various pieces of information. The term "directed acyclic graph" is quite information-dense, so let's break it down layer by layer.

Conceptually, a DAG resembles the diagram above, consisting of vertices (spheres) and edges (connecting lines). Both are directed, meaning they point in one direction (as indicated by arrows), and acyclic, meaning there are no cycles—vertices do not loop back to their starting point. In other words, if we start at one point and follow the graph, we cannot return to the same starting point. We'll delve deeper into this later.

This data structure is commonly used for data modeling. In scientific or medical fields, DAGs are used to observe relationships between variables and determine their mutual influences. For example, we can use this graph to establish connections between nutrition, sleep cycles, and physical symptoms to determine how these factors affect patients.

Our focus, however, is on how this graph can be used to achieve consensus in a distributed cryptocurrency network.

How Does a DAG Work?

In a DAG-based cryptocurrency, each vertex in the structure represents a transaction. There is no concept of blocks, nor is there mining required to expand the database. Instead of grouping transactions into blocks, transactions are built on top of other transactions. When a node submits a transaction, a small amount of proof-of-work is still performed to ensure the network isn't spammed while also verifying previous transactions.

To add a new transaction, it must be built on top of prior transactions. Suppose Alice creates a new transaction. For this transaction to be confirmed, it must reference previous transactions—similar to how a Bitcoin block references the one before it, except here, multiple transactions must be referenced.

In some systems, an algorithm selects which transactions (or "tips") new transactions must build upon. The higher the cumulative weight of a tip, the more likely it is to be selected. Cumulative weight measures the number of confirmations along the path to the tip.

The transactions Alice is about to build upon are unconfirmed. However, once Alice references them, they become confirmed. Alice's current transaction remains unconfirmed until others build transactions on top of it.

Users prefer to confirm transactions with "higher" weights to ensure the system continues to grow. Otherwise, users might indiscriminately keep building on old transactions.

Blockchains easily prevent double-spending. The same funds cannot be spent twice in a block, and nodes can easily detect such attempts, rejecting any blocks containing conflicting transactions. Mining blocks is costly, incentivizing miners to compete fairly.

DAGs also prevent double-spending through a similar mechanism but without miners. When confirming older transactions, nodes evaluate the entire path back to the first transaction in the DAG to ensure the sender has sufficient balance. There may be multiple paths, but only one needs to be validated.

If a user builds a transaction on an invalid path, their transaction will be ignored. Even if their transaction is valid, no one will extend the path because the previous transaction is invalid.

At first glance, this might seem counterintuitive—couldn't there be cases where different branches are unaware of each other? Could a user spend the same funds on different branches?

This is indeed possible. However, by weighting tips based on their cumulative weight through a selection algorithm, this issue is resolved. Over time, one branch will grow more robust than others. Weaker branches are abandoned, and the network continues to grow on the highest-weight branch.

Like blockchains, this network has no absolute confirmation—we can never be entirely certain a transaction won't be reversed. While highly unlikely, Bitcoin or Ethereum blocks can theoretically be "undone," reversing all their transactions. The more blocks added after a transaction, the more secure it becomes. This is why users are advised to wait for six confirmations before committing funds.

In DAGs like IOTA's Tangle, there's a concept called "confirmation confidence." The selection algorithm runs 100 times, calculating how often a transaction is directly or indirectly approved by the selected tips. The higher the percentage, the greater the confidence that the transaction remains "settled."

This might seem to degrade the user experience, but it doesn't. If Alice sends Bob 10 MagicDAGTokens, she doesn't need to worry about selecting the right tips in the graph because her wallet handles the following in the background:

1. Selecting high-weight tips (those with the most cumulative confirmations).

2. Tracing the path back to previous transactions to ensure the tip has sufficient balance for the payment.

3. Once these conditions are met, the transaction is added to the DAG and confirmed.
   To Alice, this is just the usual cryptocurrency process. She enters Bob's address and the amount to send, then hits "Send." The above steps are the proof-of-work every participant performs when creating a transaction.
   Pros and Cons of DAGs
   Pros of DAGs
   Speed
   There are no block time limits—anyone can publish and process transactions at any time. As long as earlier transactions are confirmed first, users face no restrictions on submission frequency.

No Mining Required

DAGs don't use traditional proof-of-work consensus algorithms. Compared to cryptocurrencies relying on mining to maintain blockchain networks, DAGs have a fraction of the carbon footprint.

No Transaction Fees

Since there are no miners, users don't pay fees to publish transactions, though some systems may charge small fees for specific node types. Low (or zero) fees are highly attractive for microtransactions, where high network fees would negate the value.

No Scalability Issues

Unlike traditional blockchains, DAGs aren't constrained by block times, allowing for significantly higher transactions per second. Many proponents believe this makes DAGs highly valuable for IoT use cases involving machine-to-machine interactions.

Cons of DAGs

Not Fully Decentralized

DAG-based protocols often have centralized features. Some argue this is a short-term solution for bootstrapping the network, but it remains to be seen whether DAGs can thrive without third-party intervention. If not, the network could be vulnerable to attacks, potentially suffering severe damage.

Not Massively Tested

Although DAG-based cryptocurrencies have been around for years, widespread adoption will take time. Thus, it's hard to predict what incentives users will have when using the system in the future.

Conclusion

There's no doubt that DAGs are an intriguing technology for building cryptocurrency networks. So far, few projects use this data structure, and it remains underdeveloped.

Still, if DAGs realize their potential, they could power numerous scalable ecosystems. With high throughput and zero fees, DAGs have countless use cases, such as IoT and microtransactions.