One of the main engineering challenges in the blockchain space is scalability. Scalability refers to the development of technologies or protocols that can handle more transactions in a given amount of time. While traditional payment networks like Visa can handle thousands of transactions per second, most blockchains can only handle a handful of transactions in the same period of time. This is due to their decentralized nature. All nodes on the network process all the transactions in parallel. This means, the least performant node is the limiting factor for the overall performance of the network. In order to maintain a high level of decentralization, a large node count is important, hence raising the minimum requirements for nodes is problematic, if they are not rewarded accordingly.

We are working on two scaling solutions: Sidechains and a Block-DAG protocol. This article will take a look at the latter, while we have dedicated a different article to our Sidechain development project.

What is DAG?

The term DAG stands for Directed Acyclic Graph. The structure on the left of the image below is a simple graph made up of nodes, with edges connecting the nodes. In a directed graph, each connection has a direction, as indicated by the arrows in the image in the center. A directed acyclic graph (DAG) does not allow cyclic relationships between nodes, like the one you can see in the diamond-shaped part of the directed graph in the middle.

DAG DAG

There are two different ways to set up a DAG to be used for a cryptocurrency. The nodes can be comprised of individual transactions, or they can be blocks containing a number of transactions. The first notable DAG protocol was IOTA’s Tangle. In the Tangle, each node is made up of a transaction. Each transaction references two prior transactions and has a small Proof-of-Work attached to it.

Horizen is considering the use of a Block-DAG protocol. Each node in the DAG is a block, similar to a block in the blockchain. It also has a block header containing important information like a timestamp and references to previous blocks as well as a set of transactions. The main difference, when compared to a block in a blockchain, is that a block in the Block-DAG can contain references to more than one predecessor. This allows the data structure to become two-dimensional when compared to the one-dimensional or linear data structure of a blockchain. We only change the data structure compared to a blockchain but keep the same consensus mechanism, Proof-of-Work, to have the network agree on a single transaction history.

chain DAG chain DAG

The Miners of a Block-DAG

As you will remember from our explanation in the Beginner’s Technology section, there are miners <haven’t found this URL in the advanced section> in traditional Proof-of-Work blockchains that secure the ledger with large amounts of computing power. Miners are incentivized to do this work by being rewarded with newly-created coins. There will also be miners in our Block-DAG protocol. What we change on a fundamental level is the data structure of the transaction record. The consensus mechanism used by the network to come to an agreement on the order of transactions remains the same, namely Proof-of-Work.

A difference in the reward structure of our DAG compared to a blockchain, is that not only the miner that solves a block gets a reward for that particular block. A number of miners that subsequently confirm that block also will receive a reward in the form of newly-created coins. This incentivizes the miners to reference all unreferenced blocks. Newly-created blocks that are not referenced by any other block yet are called leaves of the DAG.

Mining in the Horizen Block-DAG will be similar to traditional mining, but we expect more blocks to be mined in total with an overall lower difficulty, which should lead to greater mining decentralization as fewer miners will need to join mining pools.

leaves leaves

Horizen addresses another adaption that needs to be made regarding the Longest Chain Rule used in blockchains to determine which branch, or fork, is the valid one in case of a chain split. In our DAG, there is a slightly more complex algorithm determining the validity of two conflicting blocks, based on how often each was confirmed. The basic principle of the Longest Chain Rule or Nakamoto Consensus remains. The more confirmations a block in the DAG has, the higher the probability of it being the valid block out of two conflicting ones.

Difficulty Adjustment

We modified the difficulty-adjustment algorithm for our Block-DAG. The difficulty determines how hard it is to create a new block and in turn, how many blocks are created in a given amount of time. Usually, the difficulty is adjusted by comparing the time it should take miners on average to create a new block and the time it does take them in reality. If blocks are created too often, the difficulty is increased. If it takes the miners too long, the difficulty is decreased.

We plan to base our difficulty adjustment for the Block-DAG not only on the time it takes to mine new blocks, but also on the sizes of the last blocks. When several blocks hit the block size limit in a row, this is an indicator of high network activity. This would traditionally mean that it takes longer for valid transactions to be included in a block. In our DAG, the difficulty decreases in case of high network activity, which allows miners to produce more blocks within the same period of time. As a result, more transactions can be processed in the same amount of time and overall throughput is increased. This mechanism allows our DAG to dynamically handle varying network activity without sacrificing security.

The Main Challenge

From an engineering perspective, the primary challenge to overcome with a Block-DAG protocol is establishing an order throughout all blocks. While the order of blocks is always given in a linear blockchain, it needs to be established in a DAG by a set of predefined rules. Block ordering in our DAG will be based on the intersection of blocks. A valid transaction can be included in two different valid blocks in a DAG. By looking at the “overlap” in transactions of a set of blocks, one can establish a final order throughout the set.

Summary

The throughput achieved by a Block-DAG motivates us to make this protocol a reality in the Horizen ecosystem. Most DAG-based ledgers are Transaction-DAGs while we are working on a Block-DAG.

Mining in our Block-DAG will be similar to traditional mining with slight adaptions made to the reward structure. We adapted the Longest Chain Rule slightly, so it works in a DAG context, and designed a new algorithm to determine the mining difficulty based not only on block production time, but also on the number of transactions per block. If blocks hit the block size limit it indicates high network activity and difficulty will decrease, so the rate at which blocks are mined increases. The main challenge of designing the Block-DAG protocol is establishing a linear order throughout all blocks, based on the overlap of transactions that are included in more than one block.