An introduction to directed acyclic graphs
Blockchain technologies have evolved quite a bit since late 2008, when someone using the pseudonym Satoshi Nakamoto published a cryptography paper titled ‘Bitcoin: A Peer-to-Peer Electronic Cash System’. In the past two years alone, interest and investment in blockchain, cryptocurrencies and initial coin offerings have accelerated wildly, sometimes to the point of becoming a punchline.
When people achieve such notoriety, you know it’s only a matter of time before they’re declared overexposed and passé, and someone new steps in to take their place. Could the same thing be happening soon with blockchain?
Yes. Meet the directed acyclic graph, or DAG, sometimes described as ‘blockchain 3.0’.
Writer Shrey Fadia noted recently in IoT Evolution World: “Just when we thought we had only entered the beginning of the ‘hype cycle’ for blockchain being used to secure networks, devices and applications, DAG fans are saying blockchain could be easily disrupted by this alternative approach.”
And what exactly is a directed acyclic graph?
“DAG is a directed graph data structure that uses a topological ordering,” Zeroth.AI partner and RavenProtocol.com founder Sherman Lee wrote earlier this year in Forbes. “The sequence can only go from earlier to later. DAG is often applied to problems related to data processing, scheduling, finding the best route in navigation, and data compression.”
Put more simply, the structure of a DAG resembles a tree with branches. And in this branching structure of connected nodes (the ‘graph’ part), the order and flow of connections matters (this is the ‘directed’ part) — i.e., going from A to B is different from going from B to A. Finally, the flow of connections means each node is passed through only once — there’s no going around or back and passing through the same node twice (this is the ‘acyclic’ part).
One user on the Stack Overflow developer forum compared DAG to the order in which a student needs to take classes to fulfil prerequisites for a specific advanced course: “Now [it’s] clear that you cannot take a class on artificial intelligence [B] without a prerequisite course on algorithms [A]. Hence B depends on A or in better terms A has an edge directed to B. So in order to reach node B you have to visit node A. It will soon be clear that after adding all the subjects with its pre-requisites into a graph, it will turn out to be a directed acyclic graph.”
With DAG, there are no blocks and no mining, so transactions can be managed and recorded more quickly than with blockchain. The improved speed makes it possible to handle even small payments cost-efficiently, without the steep fees charged on, say, the bitcoin network. And, because each transaction needs to verify only the validity of the immediately previous transaction or transactions, rather than every past transaction — which is how verification works on the bitcoin blockchain — the energy required is much lower than with blockchain.
“That is actually the beauty of the system…, that not everyone is saving everyone’s data, which will save the computing power, which will save the storage power, which will also save the bandwidth,” said Oskar Syahbana, a researcher at the Cambridge Centre for Alternative Finance. “It’s quite different than the verification in the blockchain, in which you have to do the verification to the genesis block.”
Despite those advantages, DAG technology still suffers from the same problem as blockchain.
“They do have some value… particularly in reducing latency,” said Ethereum creator Vitalik Buterin. However, he added, “What they do not solve, first of all, they do not solve the scalability problem.”
As with blockchain itself, it’s far too soon to predict how adoption of DAG technology will evolve over time, much less predict whether DAG will eventually supplant blockchain. Despite the advantages in speed and cost that DAG offers, the distributed ledger scalability problem is one that has yet to be solved.
