Table of contents
Introduction
What is a Directed Acyclic Graph?
How do directed acyclic graphs work?
Advantages and disadvantages of directed acyclic graphs
Advantages of Directed Acyclic Graphs
Disadvantages of Directed Acyclic Graphs
Summarize
Introduction
When we think of cryptocurrency, we immediately think of concepts such as blockchain or "distributed ledger technology." Since the advent of Bitcoin, hundreds of cryptocurrencies have emerged on the market, and most of them have similar network architecture foundations. Users use these data structures to transfer value or interact with decentralized applications.
In a blockchain, new blocks are regularly added to the growing chain. Each block is connected to the previous block with some kind of cryptographic link (a hash, to be exact). Within each block are the latest transactions that users have posted.
However, there is usually a waiting period between publishing a transaction and including it in a block, just like waiting for a train at a station. Depending on the size of the carriage (block size) and the number of people waiting (pending transactions), passengers may not be able to catch the next train, or even the next one. The waiting time for transaction confirmation varies from a few seconds to several hours.
For many, this is a good deal. After all, it is highly secure and does not rely on a centralized coordination agency. Others believe that blockchain technology will eventually become obsolete. Opponents believe that in the long run, scalability issues will hinder the large-scale application of blockchain technology.
Supporters believe that future cryptocurrency payment networks will be built on a completely different architecture, namely a directed acyclic graph, or "DAG."
What is a Directed Acyclic Graph?
A directed acyclic graph is a very different data structure, and can be thought of as a database that connects different pieces of information together. “Directed acyclic graph” is a very informative concept, so let’s break it down layer by layer.
Directed acyclic graph.
Conceptually, a directed acyclic graph is similar to the one shown above, consisting of vertices (spheres) and edges (lines). Both are directed, pointing in one direction (as shown by the arrows), and are acyclic, meaning there are no cycles, and vertices will not return to the original starting point, meaning that if we start from a point and walk along the graph, we cannot return to the same starting point. We will explain this in more detail below.
This data structure is often used in data modeling. In science or medicine, directed acyclic graphs are used to observe the relationship between variables and determine the impact of each other. For example, we use this graph to establish the relationship between nutrition, sleep cycle, and physical symptoms to determine the impact of these indicators on patients.
We are more concerned with how to use this graph to reach consensus in a distributed cryptocurrency network.
How do directed acyclic graphs work?
A cryptocurrency based on a directed acyclic graph, where each vertex in the structure represents a transaction. There is no concept of blocks involved, and no mining required to expand the database. Therefore, transactions are not included in blocks in a centralized manner, but are built on top of one another. When a node submits a transaction, there is still a small amount of proof-of-work operation, which ensures that the network is not disturbed by spam, while also verifying previous transactions.
To add a new transaction, it must be built on top of the previous transaction. Suppose Alice creates a new transaction. In order for the transaction to be confirmed, it must reference the previous transaction, which is somewhat similar to a block’s reference to the previous block in Bitcoin, except that multiple transactions must be referenced here.
In some systems, an algorithm selects which transactions (or "ends") a new transaction must build on. The higher the cumulative weight of an end, the more likely it is to be chosen. The cumulative weight measures the number of confirmations in the path to the end.
The transactions that Alice is about to create on top of it are not confirmed. However, once these transactions are referenced by Alice, they will be confirmed. Alice's current transaction is not confirmed, so others must create transactions on top of it before it can be accepted.
Users are more willing to confirm transactions with “higher” weights so that the system can continue to evolve. Otherwise, users will continue to create transactions on top of old transactions without any scruples.
The blockchain easily prevents double spending. The same funds cannot be spent twice in a block, and nodes can easily detect such attempts and reject all blocks containing conflicting transactions. It is very expensive for miners to produce blocks, so the mechanism incentivizes them to compete fairly.
Directed acyclic graphs can also prevent double spending, with a similar mechanism, but without miners involved. When confirming an older transaction, a node will evaluate the entire path back to the first transaction in the directed acyclic graph to ensure that the sender has sufficient balance. There may be many paths, but only one needs to be verified.
If users place transactions on an invalid path, their transactions will be ignored. Perhaps these users’ transactions are valid, but because the previous transaction is invalid, no one is willing to expand this path.
At first glance, this may seem counterintuitive - how can there be a situation where different branches are unaware of each other's existence? So, can a user spend the same funds on different branches?
It is possible. But this problem can be solved by adding cumulative weight to the end through the selection algorithm. That is, over time, one branch will prosper more than the others. The weaker branches are abandoned, and the network continues to grow and develop on the branches with the highest weights.
As is the case with blockchain, there is no absolute confirmation on this network, and we can never be completely sure whether a transaction will be reversed. Although the possibility is extremely low, in theory, a Bitcoin or Ethereum block can be "undone", causing all transactions within it to be reversed. The more blocks added after a transaction, the more reassuring it is that the transaction is safe. This is why we recommend users wait for six confirmations before committing funds.
In a directed acyclic graph such as the IOTA Tangle, there is a concept called "confirmation confidence". The selection algorithm is run 100 times, counting the number of transactions that are directly or indirectly approved by the selected peers. The higher the percentage, the greater the confidence that the transaction remains "settled".
This may seem like a poor user experience, but it is not. If Alice sends 10 MagicDAGTokens to Bob, she does not have to worry about whether she has chosen the correct end of the graph, because her wallet will do the following in the background:
Select the endpoints with the highest weight (remember, these are the ones with the most cumulative confirmations).
Trace back to previous transactions along the path to ensure that there is enough balance at the end to make the payment.
Once the above requirements are met, the transaction will be added to the directed acyclic graph and the created transaction will be confirmed.
To Alice, this is normal cryptocurrency operation. She enters Bob's address and the amount she wants to pay, and presses send. The above list is the proof of work that each participant runs when creating a transaction.
➠ Want to start your cryptocurrency journey? Buy Bitcoin on Binance!
Advantages and disadvantages of directed acyclic graphs
Advantages of Directed Acyclic Graphs
speed
There is no block time limit, and anyone can publish and process transactions at any time. As long as the earlier transaction is confirmed first, the user is not limited in the number of transactions submitted.
No mining required
Directed acyclic graphs do not use the conventional proof-of-work consensus algorithm. Compared to cryptocurrencies that rely on mining to maintain the blockchain network, the carbon footprint of directed acyclic graphs is only a fraction of the original.
No transaction fees
Because there are no miners, users do not have to pay fees for posting transactions, but sometimes they have to pay a small fee to certain types of nodes. Low fees (free is better) are very attractive to users who make small payments, because high network fees would make them work in vain.
No scalability issues
Compared to traditional blockchain networks, DAGs are not constrained by block times and can process many more transactions per second, which many supporters believe makes DAGs more valuable in Internet of Things (IoT) use cases where machines interact with each other.
Disadvantages of Directed Acyclic Graphs
Not completely decentralized
Protocols based on directed acyclic graphs have various centralized properties. Some believe that this is a short-term solution to launch the network, but it remains to be seen whether directed acyclic graphs can thrive without third-party interference. If they do not succeed, the network will be opened to attack vectors and will eventually be severely damaged.
Not tested on a large scale
Although DAG-based cryptocurrencies have been around for a few years, they will take time to become widely adopted, so it is difficult to predict what incentives users will enjoy when using the system in the future.
Summarize
There is no doubt that directed acyclic graphs are an interesting technology for building cryptocurrency networks. So far, there are relatively few projects using this data structure and they are still underdeveloped.
Even so, if DAGs can realize their potential, they will certainly provide a driving force for many scalability ecosystems. There are countless use cases for DAG technology in areas that require high throughput and are free, such as the Internet of Things (IoT) and micropayments.