Ultimate Guide to Directed Acyclic Graph DAG in Cryptocurrency

When you think of cryptocurrency, the terms “blockchain” or “distributed ledger technology” likely spring to mind. Since the launch of Bitcoin, hundreds of other cryptocurrencies have been created. Most of them rely on similar network architecture. Their data structures allow users to transfer value or to interact with decentralized applications.

In a blockchain, a new block is periodically added to a growing chain of blocks. Each block is connected to the previous one with a sort of cryptographic link (specifically, a hash). In each of these blocks are recent transactions that have been broadcast by users.

But there’s often a waiting period between a transaction being broadcast and its inclusion in a block. Think of it like waiting for a train at a station. Depending on the size of the carriages (block size), and the number of other people waiting (pending transactions), you might not even be able to get the next train. Or even the one after that. You can be waiting anywhere from seconds to hours for the transaction to be confirmed.

To many, this is a decent trade-off. After all, it provides a very high degree of security without relying on a centralized coordinator. To others, blockchain technology has an expiration date. Detractors believe that, in the long run, the scalability problems faced by blockchain technology will prevent mass adoption.

Some believe that the future of cryptocurrency payments networks lies in an altogether different architecture – directed acyclic graphs (or DAGs).

What is a DAG?

A DAG is a different kind of data structure – think of it like a database that connects different pieces of information together. “Directed acyclic graph” is a loaded term, so let’s start by breaking it down.

A Directed Acyclic Graph.

Conceptually, DAGs look something like the above. They’re made up of vertices (the spheres) and the edges (the lines connecting them). They’re directed because they head in one direction (you can see this illustrated with the arrows). They’re acyclic (i.e., not cyclic) because the vertices don’t loop back on themselves – if you start at one point and follow the graph, you can’t return to that same point. This will become clearer shortly.

Such data structures are generally used to model data. You might rely on a DAG in scientific or medical fields to observe the relationship between variables and to determine how they impact each other. For instance, you could take things like nutrition, sleep cycles, and physical symptoms, so that you can draw links between them to establish how they affect a patient.

For our purposes, we’re more interested in how they can help 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’s no notion of blocks here, nor is mining required to extend the database. So instead of gathering transactions into blocks, each transaction is built on top of another. Still, there’s a small Proof-of-Work operation that’s done when a node submits a transaction. This ensures that the network isn’t being spammed and also validates previous transactions.

For a new transaction to be added, it must build on top of older ones. Suppose that Alice creates a new transaction. For it to be acknowledged, this transaction must reference previous ones. A bit like how a block in Bitcoin references the one that came before it, but there are multiple transactions referenced.

In some systems, an algorithm will select which transactions (or “tips”) a new transaction must build on. Tips more likely to be selected are those that have more accumulated weight – a measure of how many confirmations the path to the tip has.

The transactions that Alice will build on top of are unconfirmed. But once Alice references them, they become confirmed. Alice’s transaction is now unconfirmed, so someone else must build on top of it before it’s accepted.

Users are more likely to confirm transactions with a “heavier” weight so that the system keeps growing. Otherwise, there would be nothing stopping users from continuously building on older transactions.

With blockchains, double-spend protection is easy enough. The same funds can’t be spent twice in a block – nodes can easily detect any attempt and will reject any block containing conflicting transactions. Since it’s so expensive for miners to produce blocks in the first place, they’re incentivized to play fair.

DAGs also have a mechanism to prevent double-spending. It’s sort of similar, but without miners. When a node confirms older transactions, they assess a whole path back to the DAG’s very first transaction to be sure that the sender has a sufficient balance. There could be multiple paths, but only one needs to be verified.

If users build on an invalid path, they run the risk of their own transaction being ignored. Theirs could be legitimate, but because the previous one wasn’t, no one will want to extend that particular path.

It seems unintuitive at first – couldn’t you end up in a situation where multiple branches that aren’t aware of each other exist? Then, couldn’t people spend the same funds on these different branches?

That’s indeed a possibility, but it’s resolved with a selection algorithm that favors tips with a heavier accumulated weight. That means that, over time, you’ll end up with a branch that is much stronger than the rest. Weaker ones will be abandoned, and the network will continue building on the heaviest one.

As with blockchains, there isn’t absolute finality – you can never be 100% sure that a transaction won’t be reversed. It’s incredibly unlikely, but you could theoretically “undo” a Bitcoin or Ethereum block, reversing all of the transactions inside. The more blocks added after the one your transaction is in, the more confidence you can have in it. This is why it’s recommended that you wait for six confirmations before spending funds.

In a DAG such as IOTA’s Tangle, there is an idea of confirmation confidence. The selection algorithm is run 100 times, and you count how many times your transaction has been directly or indirectly approved in the selected tips. The higher the percentage, the more confidence you can have that your transaction will remain “settled.”

This might seem like it leads to bad user experience. But that isn’t the case. If Alice sends Bob 10 MagicDAGTokens, she doesn’t need to worry about selecting the right tips of the graph. Under the hood, her wallet might do the following:

• Select heavy tips (remember, these are the ones with the most accumulated confirmations).
• Follow the path back through previous transactions to make sure the tips have a sufficient balance to spend.
• Once satisfied, they add their transaction to the DAG, confirming the transactions they’re built on.

To Alice, this will just look like the regular cryptocurrency workflow. She enters Bob’s address and the amount she wants to spend, then presses send. The list above is the Proof of Work that every participant runs when creating a transaction.

Pros and cons of directed acyclic graphs

Pros of DAGs

Speed

Unrestricted by block times, anyone can broadcast and have their transactions processed at any time. There’s no limit on the number of transactions that users submit, provided they confirm older ones as they do.

No mining

DAGs don’t use PoW consensus algorithms in the way we’re accustomed to. Their carbon footprint is thus a fraction of that of cryptocurrencies that rely on mining to secure their blockchain network.

No transaction fees

Because there aren’t any miners, users do not need to pay fees to broadcast their transactions. That said, some require that a small fee is paid to special kinds of nodes. Low fees (or better, zero fees) are enticing for micropayments, as their purpose is defeated with significant network fees.

No scalability issues

Unconstrained by block times, DAGs can process many more transactions per second than traditional blockchain networks. Many proponents believe this will make them valuable in Internet of Things (IoT) use cases, where all kinds of machines will interact with each other.

Cons of DAGs

Not entirely decentralized

Protocols that rely on DAGs have various elements of centralization. For some, it’s supposedly a short-term solution to bootstrap the network, but it remains to be seen whether DAGs can thrive without the intervention of third-parties. If not, they open themselves up to attack vectors that could eventually cripple their networks.

Not tested at scale

Though DAG-based cryptocurrencies have been around for a few years, they have a long way to go before seeing widespread use. As such, it’s difficult to predict what incentives users might have to exploit the system in the future.

Closing thoughts

Directed Acyclic Graphs are certainly an interesting technology for building cryptocurrency networks. So far, there are relatively few projects that use the data structure, and they have yet to evolve fully.

That said, if they can deliver on their potential, they could power massively scalable ecosystems. DAG technology has a myriad of use cases in areas that require high throughput and no fees, such as in the Internet of Things (IoT) and micropayments.