Directed Acyclic Graph (DAG) based Distributed Ledgers
The word ‘graph’ is vernacular precluding any special mention. In Computer Science dialect, the graph points towards the data structure consisting a set of “vertices” connected by “edges”.
Amused what are vertices?? Check out the below illustration.
Here, the square denotes a vertex and the lines between vertices denote edges. If the edges are directed (arrows), it is called a directed graph.
Consider the path A -> B -> G -> F -> D -> A.
This is known as a cycle, as it begins and ends at the same vertex. A directed graph which does not have any cycles is known as DAG — directed acyclic graph. Below are two examples of DAG.
Does the second figure reminds you of something ?Yes… , blockchain follows a DAG structure. Each block is connected only to its previous block and the first block (genesis block) is not connected to any other block. So we get a straight line of blocks.
Blockchain is used to implement a distributed ledger. If you ask for any other DAG structure for the same purpose, the answer is yes . All the distributed ledger technologies are not blockchains. There are alternatives available. Let us see how a DAG can implement a distributed ledger. We will discuss this topic based on tangle, a DAG associated with IOTA. IOTA is a distributed ledger used to manage transactions between devices connected in an IoT ecosystem.
Tangle: A DAG for storing transactions
Let us see the concepts in the tangle.
Each block represents a storage structure used for a single transaction. It consists of details of that particular transaction, hash value, and digital signature. So a block in the DAG can also be called as a transaction. Tips represent transactions which are not yet approved. Each edge represents an approval. Direct edge between two blocks indicate direct approval. A path between two blocks, which has one or more blocks in between, denotes indirect approval.
The weight of a transaction is proportional to the computational work required to build the block. Cumulative weight of a transaction is the sum of its weight and weights of all transactions which directly or indirectly approves it. For example consider the transaction A . It is directly approved by transactions C and B. Direct approvals of B and C act as indirect approvals of A. So it includes F and (D, E, G). The direct approvals of F, D, E, G are H and I. So cumulative weight of A is calculated as :
A + (B+C+D+E+F+G+H+I) = 9.
If the cumulative weight of a transaction becomes equal to or larger than a particular value (threshold), it is considered as confirmed. Approved transactions which have cumulative weight less than the upper limit are called unconfirmed transactions.
Transaction Processing in DAG
When a node creates a transaction, it selects two tips (unapproved transactions) based on a tip-selection algorithm. Each new transaction should approve two previous transactions, which are represented by directed edges. The transactions should be verified before the approval and the node should make sure that it does not approve any conflicting transactions. The node should solve a cryptographic puzzle, similar to Proof of Work, but of lower difficulty level. The signed transaction will be broadcasted to the network. Other nodes in the network will verify the transaction and add it as a new tip in the DAG.
If a node wants to issue a transaction, it should work to approve previous transactions. So users who issue a transaction contributes to the security of the system by verifying previous transactions. If a node issues a transaction that approves conflicting transactions, then it may not get approval of the network since other nodes in the network can detect this and reject the transaction. DAG does not require any separate miners since the nodes themselves do the transaction approval and mining.
Stages of a transaction
Initially when a transaction is added as a tip in the DAG, it is unapproved. When any further transactions selects that tip, it becomes approved. The cumulative weight associated with a transaction will be updated whenever a transaction approves it directly/indirectly. The cumulative weight of a transaction is a measure of the computational effort behind it. So once it reaches a threshold value, the transaction is marked as confirmed as the probability of malicious modification is low.
Blockchain Vs DAG
In a blockchain, a block consists of a list of transactions, whereas in DAG, a block represents a single transaction. Any node in the network can issue and approve the transactions. This allows processing several transactions in parallel since no professional miners are necessary as any node can act as a miner. So little or no transaction fee is required. It also helps improve the system scalability.
DAG has several properties which conflict with the concepts of blockchain. Blockchain tries to prevent forking, by delaying block creation time using an appropriate consensus algorithm whereas DAG allows any node to insert transactions into the ledger at the same time, causing many forks simultaneously. So how does it deal with the conflicting transactions in multiple branches ?. Even though DAG has a forked topology, the degree of forking is limited to prevent issues like double spending. We have already seen how bitcoin handles double spending in a previous article. Similar to the “longest chain rule” in Bitcoin, DAG follows a “heaviest DAG rule”. The algorithm used for selection of tip, will select the tip based on highest cumulative weight. To know about tip-selection in details check this link. Similar to Bitcoin, a transaction with larger weight is considered more important than a transaction with smaller weight.
The time taken for transaction confirmation in blockchain networks will be proportional to block creation time, whereas in DAG, it is proportional to the transaction arrival rate. If the transaction arrival rate is high, then the confirmation time will be low. But in certain systems, the transaction arrival rate may be low, which increases the confirmation delay.
Other than IOTA, some distributed ledgers based on DAG are Obyte (formerly ByteBall ), Dagcoin, Swirlds etc.
References
- Popov, Serguei Yu.. “The Tangle.” (2015).
- Yixin Li, Bin Cao, Mugen Peng, Long Zhang, Lei Zhang, Daquan Feng, and Jihong Yu. 2020. “Direct Acyclic Graph-Based Ledger for Internet of Things: Performance and Security Analysis “. IEEE/ACM Trans. Netw. 28, 4 (Aug. 2020), 1643–1656. DOI:https://doi.org/10.1109/TNET.2020.2991994
