A Directed Acyclic Graph (DAG) is a type of graph data structure that consists of nodes connected by directed edges, where the edges have a specific direction and do not form any cycles. It is a directed graph that does not have any directed cycles.

Each node in a DAG can have one or more incoming edges and one or more outgoing edges. The edges in a DAG represent dependencies between the nodes, where the direction of the edge indicates the direction of the dependency. For example, if node A has an outgoing edge to node B, it means that node A depends on node B.

Overview

Directed Acyclic Graphs (DAGs) differ from blockchains in that they do not use a block-based structure. Instead, transactions are represented as vertices in the graph and are linked to previous transactions. Nodes validate and add transactions to the DAG, and submitting a transaction requires completing a proof-of-work task. ^[1]

In a DAG-based network, a new transaction must reference previous transactions to be accepted, similar to how blocks in a blockchain refer to previous blocks. Referencing a transaction confirms it, and for a transaction to be fully confirmed, it needs to be referenced by subsequent transactions. ^[1]

DAGs have high transaction speeds due to the absence of block creation and no transaction fees because there are no miners, which can have environmental benefits. ^[2]

DAGs are superior to blockchains in a sense that they allow higher throughput, by combining the concepts of blockchains, proof of work and proof of stake, and the longest chain rule with directed acyclic graphs.

History

The first use of a DAG is undated, but the concept is so useful, it extends back to the dawn of human existence.

The publication ‘Seven Bridges of Königsberg’ by Leonhard Euler in 1736 is regarded as the first paper to cover Graph Theory. The seven bridges of Königsberg is a notable problem in the history of mathematics. The challenge is to find a route to cross each of the seven bridges in Königsberg (now Kaliningrad, Russia) once and only once. After simplifying the map of the city to a graph, Euler introduced his formula relating to the number of edges, vertices and faces.

From here, Graph Theory has developed into a study of relationships between objects, depicted by mathematical structures. There are many different types of graphs, all with specific definitions, and a DAG is one of them. ^[3]

Use Cases

Family Tree

An original use case of DAGs is creating a family tree. Interestingly, the definition of a tree in Graph Theory did not include most family trees. This is because in most family trees stretching back far enough, distant relatives have mated at some point, allowing a common ancestor on both the paternal and maternal sides of the family. This means, a family tree can be considered a DAG–where each node is a person, and each parent-offspring relationship is drawn as an arrow pointing towards the offspring. This forms a graph shown below, which is directed (the arrows) and acyclic (no person can be a parent of themselves).

Depictions of family trees as DAGs have been recorded in Ancient Rome, by Pliny the Elder who described the graphs decorating the walls of Roman patrician houses. Prior to this, DAGs may not have been recorded, but often described when explaining family histories.^[3]

Task Scheduling

Another historic use case for DAGs is task scheduling where animals and humans innately use DAGs to work out the order of tasks to complete. Some tasks cannot begin until others are complete and other tasks can begin at any time — this in itself is a DAG.

In the above DAG, T1 may be to decide which animal to hunt for dinner, task 2 is to hunt the animal, and task 3 which can be done concurrently is to collect firewood. Task 4 is to start the fire. Task 5, to cook the animal, requires both the fire to be burning and the animal to be hunted, and task 6 is to eat the dinner, which needs the animal to be cooked first. Similar (but more complex) DAGs would have been used for any large task, such as building the pyramids, designing Rome, planning an attack during a war, etc.^[3]

Computer Science

Other use cases for DAGs are more modern, with multiple uses related to computer science. Data processing networks, version history, and some data compression algorithms all utilize DAGs. But the important thing to note is DAGs aren’t a new revelation, but an age-old problem-solving mechanism. The merge of DAGs and blockchains is a huge leap forward for distributed ledger scalability.^[3]