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 fixed 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.
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.
What is DAG
The term DAG stands for Directed Acyclic Graph. The structure on the far left of the image below is a simple graph made up of nodes and edges connecting the nodes. In a directed graph each connection has a direction, indicated by the arrows. A directed acyclic graph (DAG) does not allow cyclic relationships of nodes like the one you can see in the bottom part of the directed graph in the middle.
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 predecessors. 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.
The Miners of a Block-DAG
As you might know, there are miners 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 but also a number of miners that confirm that block, later on, 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.
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 it 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.
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 size 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, there is one main challenge to solve with such a Block-DAG protocol: 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.
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 more blocks are mined in the same period of time. 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.