DAG applied to the blockchain: explanation and use in IOTA
Blockchain

DAG applied to the blockchain: explanation and use in IOTA

By Emanuele Pagliari - 30 Jun 2019

Chevron down

The concept of DAG has often been applied to the blockchain and is already used by several cryptocurrencies including IOTA, ByteBall and even IoTChain.

Blockchain vs DAG

DAG, aka Direct Acyclic Graph, is a data structure that has no direct cycles, meaning that by choosing any vertex of the graph it is not possible to get back to it by going through the arcs of the graph. A sequence can only pass from the one before to the one after and not vice versa.

DAG is often applied to problems related to data processing, scheduling, searching for the best route for navigation and data compression.

In summary, therefore, it allows a different approach to creating a distributed ledger. In the blockchain, transactions are collected into blocks, which can only be created in sequence, thus forming a chain.

In DAGs, the concept of a block as a set of transactions isn’t used, due to the fact that all transactions are directly linked to each other. A block, therefore, will consist of a single transition within the DAG.  In this way, it is possible to execute transactions at the same time, in parallel and much faster, thus increasing the throughput of the network.

One of the main reasons why bitcoin is inefficient for high transactions is because of the use of a very resource-intensive Proof of Work, which is necessary for transaction verification and therefore block sealing.

Also, as mentioned above, blocks in the blockchain cannot be created at the same time but only in sequence. As a result, all transactions that occur more or less in the same period are kept in the same block, although sometimes there may be more transactions than those that can be inserted in the block, which is why it is necessary to wait for the next block, causing delays in the confirmation of transactions.

The system, therefore, becomes congested beyond a certain threshold of transactions. Obviously, it is possible to increase the size of the blocks, so more transactions can be included, but doing so there’s a risk of further increasing the size of the blockchain, which is already close to 225 GB.

Rather than a storage problem though (a 1TB HDD costs less than 50 euros), the real problem of blocks of several tens of MegaBytes is the propagation on the network, which can lead to real block reorgs, as already happened on Bitcoin SV.

The DAG, therefore, by exploiting a different concept of blocks and a different structure of the network, can significantly improve scalability, solving, at least theoretically, this classic problem now encountered by both Bitcoin and Ethereum.

Mining and DAG

However, there is another problem that affects Bitcoin, namely mining. In the blockchain, the mechanism for confirming transactions and thus creating and signing blocks, requires the intervention of miners to perform the required Proof of Work.

A miner that runs the PoW is rewarded with bitcoin, which varies according to the block number, and by the transaction fees that the sender pays when creating the transaction

Precisely for this reason, also thanks to the spread of bitcoin, a real mining race has arisen over the years.

The evolution went from CPUs and GPUs to FPGAs and specificic mining machines called ASICs for various mining algorithms. However, these specific machines cost far more than the classic GPUs and CPUs found in today’s PCs and smartphones, which is why bitcoin mining has shrunk to a limited number of people and companies.

A true business has emerged in this sector, which however threatens the decentralisation of the network, as the private individual and the small miner are no longer encouraged to run the PoW.

It emerges, therefore, that even mining can prove to be a partial threat to the decentralisation of the network. Cryptocurrencies like Monero, in fact, are constantly fighting against ASICs or systems that can put at risk the decentralization of the network. It must also be said that mining also involves an enormous use of energy. For this very reason, some coins are planning to switch to PoS, although there are numerous discussions on this matter.

In networks based on the DAG concept, at least in the applications seen so far, there is no need to have external miners to confirm transactions. However, depending on the implementation, it may be necessary to run a PoW to prevent network or SPAM attacks.

In the IOTA tangle, in fact, when a transaction is recorded in a node, the latter must first verify two other transactions, which are chosen using the Poisson Arrival Process concept.

The node must verify if the two transactions are not in conflict and execute a PoW, but since it is limited only to the two transactions accepted, no unnecessary checks are performed, thus maximising efficiency. Whereas in other DAG based coins, as with ByteBall, it is not necessary to run any additional PoW, thanks to the presence of a mainchain.

In essence, therefore, within a DAG the nodes become the miners of themselves, only that this process is much more efficient and less expensive in terms of used resources. Since external miners are no longer needed, transaction costs are reduced to virtually zero.

This allows to carry out micro-payments and, considering the confirmation mechanism, as the number of nodes participating in the network increases, the number of transactions that can be confirmed and therefore executed increases, in turn boosting the throughput of the entire network.

Double spending and fast transactions

A distributed ledger, however, must also ensure the trustless nature of the system to be functional: it is expected to prevent double spending attempts and to ensure that transactions are executed quickly.

The low transaction confirmation times are guaranteed by the blockless nature of DAGs, since, as mentioned at the beginning, there is no need to create a transaction block and propagate it on the network once verified. This process in fact, in addition to limiting the number of transactions, has time constraints, since, for example, the bitcoin blockchain creates a block every 10 minutes

As a result, a transaction is unlikely to be confirmed in less than 8-10 minutes, which is the average time per block.

In DAGs, on the other hand, since transactions are directly propagated over the network, confirmation takes place very quickly, just a few seconds. Obviously, this time depends on how populated the network is, hence at first a DAG network could be slower due to lack of nodes. A bit like what happened to IOTA in the first months of the network’s existence.

As far as double spending is concerned, i.e. the attempt to spend the same money several times, there are different approaches to prevent this from happening. The concept of DAG itself involves that transactions are distributed according to a certain topological order, given the nature of the structure.

Taking as an example the implementation adopted in IOTA, suppose, for example, that someone spends their funds twice. When a double spending attempt occurs, two branches are created, but only one of them will be verified correctly. To do this, IOTA uses the concept of weight during the transaction confirmation phase, which is why one branch will grow faster than the other. In doing so, the smaller branch, therefore with less weight, will remain isolated, negating the attempt at double spending.

ByteBall, on the other hand, relies on a mainchain for final synchronisation, which thus rejects double spending attempts.

It is precisely for this reason that it is not possible to reduce the confirmation time for transactions to zero, as the legitimacy of the transactions also needs to be verified.

The limitations of DAGs

Obviously, not even the DAGs are perfect, but several scientists and mathematicians are working hard in the development of such systems in the field of distributed ledgers, given the different merits compared to the classic blockchain.

One of the limits of DAGs is the need to have a good number of active nodes in order to function properly and quickly. So in networks with little activity or with a few nodes it may not work at its best and involve confirmation times of transactions greater than the classic blockchains.

For this reason, sudden changes in the number of nodes in the network may also affect the operation of the network. For example, a sudden drop in the number of active nodes would cause a drop in the ability to confirm transactions, drastically reducing throughput.

In addition, it is necessary to implement a proper consensus algorithm and node weighting, in order to avoid illegitimate transactions and ensure proper scheduling of transactions. In short, the DAG is a very promising and already working solution, with further room for improvement and development. There is no lack of uncertainty and doubt from the communities, but projects like IOTA show that such an approach can work.

It remains to be seen whether such a system can actually scale endlessly in practice as claimed by IOTA and other projects, but this question can only be answered by seeing how the network will behave with tens of thousands of nodes over the next few years.

Emanuele Pagliari
Emanuele Pagliari

Telecommunications engineer with a strong passion for technology. His adventure in the world of blogging started on GizChina.it in 2014 and then continued on LFFL.org and GizBlog.it. Emanuele is in the world of cryptocurrency as a miner since 2013 and today he follows the technical aspects related to blockchain, cryptography and dApp, also for applications in the Internet of Things.

We use cookies to make sure you can have the best experience on our site. If you continue to use this site we will assume that you are happy with it.