Mere DAG ？MeerDAG！
DAG is a strange and aslo a familiar concept. When the scalability technology of BlockChain is mushrooming in 2020, and Ethereum was trying to reach a thousand-level TPS with the wind of ZK-Rollup, talking about DAG seems to be a bit out of time. In fact, this is a misunderstanding of DAG technology. As a technological framework, it is in the data structure layer of the whole BlockChain architecture, and represents a technical idea that will not become obsolete no matter how to improve it. Just like PoW and PoS, it is difficult to say which is better or worse as a consensus framework in the current technology landscape, but the key is what the specific implementation is.
The technology architecture is layered, although it involves specific implementation, it is impossible to achieve complete independence between the various layers, but from the perspective of architectural design, it can be basically considered that the technology of each layer is not dependent on each other, in more professional terms is orthogonal. Orthogonality is like the familiar Cartesian coordinate system, where the x-axis and y-axis are different dimensions and do not affect each other. Similarly, DAG, as a data structure layer, does not affect the combination with other layers, for example, DAG technology combined with ZK-Rollup will further improve transactions throughput. This also answers the questions of many friends, now using ZK-rollup or lightning network or sharding technology can easily break through the thousands of TPS, there is still a bottleneck in single node computing power due to the design of DAG, then what is the significance of studying of DAG?
In any technical architecture, the robustness of any link is very important, especially as the bottom of the data structure. In familiar words, the body is the capital of the revolution, just as there are now a variety of transport substitutes, far beyond the limits of human’s own physiological speed, but we still pursue higher, faster and stronger Olympic spirit. Similarly, we are studying DAG to provide a more robust data structure for the BlockChain network, and combining other technologies on top of that is like added the firepower. Ethereum 2.0 is the most vivid example, Ethereum data structure is actually a BlockDAG with a lot of restrictions and this doesn’t affect the conversion of Ethereum consensus framework into PoS to save energy and greatly improve the execution efficiency of smart contract and transactions through sharding, channels and ZK-Rollup on layer2.
Similarly, Qitmeer team put consensus protocol in a crucial position when they designed technology architecture. Because consensus protocol is the skeleton of the whole architecture so that this architecture must to be fully optimized. Consensus protocol also is the skeleton of the technical architecture. All the modules was implemented around the protocol. Therefore, Qitmeer has formulated very strict design principles at the beginning of protocol design.
1. Fully Decentralized
Decentralization is not only the spirit of BlockChain, but also the source of network security. Because no matter how high the consensus index of consensus plugin is, 30% or 50%, if the network itself isn’t decentralized, then the attack cost formed by attackers uniting a few consensus nodes will be much lower.
2. Robust Data Structure
Although BlockChain contains chain in its name, this chain only represents the one-way verification relationship between adjacent blocks at the micro level guaranteed by cryptographic algorithms, so the structure itself has very high security. As long as this security setting is not violated, there is no strict requirement whether it is chain-type or graph-type at macro level. So we do hope that the data structure itself can break the protocol constraints, and accommodate more transactions in unit time under the requirements of ensuring safety and other technical indicators.
3. Security
MeerDAG should guarantee 50% of consensus security.
4. Pluggable
Pluggable means that the coupling degree between modules is very low, and the modules can be replaced at any time as needed. The pluggable design not only makes the architecture more flexible, but more importantly, it makes the modules as simple as possible, thus enhancing the overall robustness.
5. Fairness
It should ensure that the resources contributed to the network are roughly balanced with the benefits obtained, and the nodes should take the risk that match with its own resources.
Although hese five principles are strict, they make the direction of consensus design clearer. Qitmeer gives its own solutions for the above 5 principles.
Decentralized
The requirement of decentralization made us choose POW for the consensus framework. PoS has many advantages like saving resources and Qitmeer team has also been focusing on the development of PoS consensus plugin, and has been taking PoS as a long-term goal, just like Ethereum developed from PoW to Pos.
But on the point of decentralization, no particularly ideal PoS solution has been found yet. One of the most critical issues is how to solve the first asset allocation.
PoW is to use computing power to get the right to allocate assets, and computing power is a physical resource, which belongs to off-chain resources, and the acquisition is roughly the same. But PoS is to use the equity to get the right to allocate the assets on the chain, and equity itself is an on-chain asset, which falls into the trap of whether there is a chicken or an egg first?
So the mainstream PoS consensus will cut the cake in the genesis block and distribute all the equity, but the process of cutting this cake is actually a centralized process. So Qitmeer finally chose PoW as the framework of consensus plugin.
Data Structure
At present, the mainstream data structure in the blockchain world is chain-type and graph-type, and the graph-type is mainly DAG. In fact, which solution data structure adopted is not the core issue, the key point is to see what kind of problems can be solved by different data solutions. Blockchain is a distributed network, in the process of production and release of blocks, due to the existence of time delay in calculation and transmission of blocks, each node must get the blocks asynchronously, asynchronous means that the order of transactions is uncertain, so there is a need for a unified rule to ensure that the final order of transactions received by each node is the same, which is the consensus plugin. In order to solve the problem of consensus, the traditional chain structure artificially increased the blocks’ production efficiency, which ensures that in a relatively long period of time, almost only one block can be generated and transmit to the whole network.
Then if I cancel this artificial block cycle to let the blocks transmit to the whole network immediately after they generated, although the transmission of transactions will cause the nodes received asynchronously because of the time delay, the transactions itself has a strict dependency verification between input & output, finally the nodes can still reach a consensus, and the network processing efficiency can be infinitely close to the physical limit of bandwidth. This is the basic principle of studying DAG, but observant friends might found that now the ledger structure is no more the chain-type but graphy-type, and this graphy is definitely one-way due to the transaction dependency, which is the Directed Acyclic Graph.
Qitmeer teamwork was bullish on the future of DAG consequently. At that time, mainstream DAG network used transaction-based DAG that each transaction in the ledger was connected to each other without the concept of blocks. The efficiency of network communication and ledger storage of this design was not high, for example, if the transaction is compared to a person, the block is compared to a car, which is more efficient? Multiple people to take a bus or for everyone to drive a private car? More importantly, these are not compatible with POW consensus plugin, which is the basis of decentralization we mentioned before, so Qitmeer didn’t adopt it.
Qitmeer eventually discovered the data structure of BlockDAG. There is a difference of only a single word between BlockDAG and BlockChain, which indeed shows that there are many commonalities between them. In essence, BlockChain is a special kind of BlockDAG, so its data structure is different from the other special ledgers. BlockDAG is homologous to Bitcoin’s classic blockchain model, so it naturally carries all of Bitcoin’s verified excellent features, such as PoW, one-way verification between blocks, and it is an expansion of BlockChain that can accommodate forks to achieve higher transaction throughput.
BlockDAG is not a specific consensus protocol but a consensus protocol framework or model that uses a mining-based graphical block ledger. In general, BlockDAG has high requirements for security of consensus plugin, ensures the safety of 50% computing power, this will be mentioned later. Decentralization, high security and high transaction efficiency have finally moved Qitmeer.
Security
The observant friends will ask, why Bitcoin didn’t use BlockDAG initially since it has so many advantages? It is true, but the cost of using BlockDAG is that there will be more forks in the ledger, in other words, the computing power of each fork will be reduced, so the risk of network attack will be increased. And this is why Bitcoin would rather sacrifice transaction throughput to ensure security. So there are actually quite a few DAG networks, most of them still choose one centralized secondary chain to protect the network from attacks. However, this is in conflict with the principle of decentralization that we pursue. Without the premise of decentralization, the discussion about chain-type or graph-type is meaningless. In extreme cases, if the network has a consensus node, even the chain structure can also handle all the transactions at high speed, is it still BlockChain?
After identifying BlockDAG as data model, an important issue is how to solve the problem of security caused by forking. It is a good thing that some research institutes are exploring a high security consensus protocol based on BlockDAG data structure when the concept of BlockDAG was proposed at the same time, and almost all the important papers are originated from DAGlabs. The framework of BlockDAG was established by the the earlier Inclusive Protocol, Inclusive Protocol Consensus Plugin and rewards, etc. The later papers related to BlockDAG were based on this framework. Although inclusive is a programmatic paper, there are details still need to be improved, for example, at the core level of consensus plugin, there is only a rough graphical ergodic algorithm, no engineering feasibility. However, Inclusive also provides valuable reference for Qitmeer, especially in the aspect of reward design, which will be mentioned in terms of fairness later.
Since then GHOST has proposed a tree-shaped DAG solution, and its consensus plugin solved the biggest security problem of BlockDAG, and reached 50% computing power comparable to Bitcoin. Since then BlockDAG has entered the mainstream BlockChain vision. One of the most representative is that Ethereum adopts GHOST as the consensus protocol and this became the most important reason why Ethereum can increase the cycle of block generation in 10 seconds level. But unfortunately, Ethereum adopted a conservative strategy which limited GHOST Protocol’s concurrency, so that the performance of GHOST Protocol didn’t fully exploited.
One possible reason is that, in GHOST protocol tree-shaped DAG only the transactions on main chain are packaged into the ledger, and the transactions on others forked chains are abandoned, this will cost huge waste when there is high transaction concurrency. It is interesting to note that the previous inclusive protocol has put forward an assumption of standard BlockDAG, which will study how to make the transactions in all blocks participate in the consensus. But later GHOST protocol brings the problem of wasting transactions while it solved the security problem. Probably the solution hasn’t been found at that time to not only fully use all blocks’ throughput but also ensure the security. Compared with security and scalability, security should be given priority. Moreover, compared with the classic BlockChain protocol, GHOST Protocol has a very high speed for transactions.
The later SPECTRE procotol perfectly solved the problem of wasting transactions on the forked chain, and its ledger model is no more the tree-shaped DAG but a standard BlockDAG which means a complete DAG graph, the advantage is that the utilization rate of the transaction is further improved. SPECTRE is not perfect enough, SPECTRE protocol cannot guarantee the linear ordering of all the transactions although the consensus plugin ensures that the repeat transaction will not exist. However, at that time, it was the general trend for blockchain systems to support smart contracts while the first layer smart contract in BlockChain system requires the linear ordering of all transactions. More important is that Qitmeer’s reward mechanism is to encourage miners to mining actively, and it has strict requirement about the ordering of transactions. So Qitmeer only uses the characteristics of quick confirmation of SPECTRE’s consensus plugin for reference, and optimizes the speed of MeerDAG’s confirmation.
In 2018, DAGlabs launched phantom protocol, which solved the problem that transactions cannot ordered linearly in SPECTRE protocol, this is the first industrial-grade BlockDAG protocol. Later on, Phantom did some optimization and fixed some problems, and GhostDAG protocol has emerged, which marks the maturity of BlockDAG protocol. Qitmeer’s consensus protocol is also based on GhostDAG and makes a lot of improvements, and this is one of the few industrial-grade implementations of the GhostDAG protocol.
The GhostDAG protocol papers is more of a guide in terms of ideas, but after all, the focus is still on the rigorism of proving algorithm. Many problems in engineering will not be considered too much in papers. One of the most typical problems is performance, if we implement it directly according to the original reference plugin, the performance is almost unacceptable. As everyone knows, ledger database of BlockChain will become larger and larger over time, and every single transaction needs to be confirmed through all the nodes. Once problems of performance arise, it will certainly be used by attackers, resulting in the paralysis of the whole network. So the performance problems in the BlockChain network is essentially a security problem.
At that time, Qitmeer team had made a lot of optimization directly against GhostDAG&SPECTRE, reduced the complexity for 2 levels to meet the requirements of engineering level.
Pluggable
Pluggable means blocks can be substituted freely between themselves and this is the cultural embodiment from Qitmeer’s engineers. In addition to the touchable experience and efficiency, the invisible pursuit from engineers is framework design. There is also a relatively practical reason is that Qitmeer is exploring a brand new way, even what is going to happen and which new technology is going to integrated are still unknown. But Qitmeer team has reached a consensus on keeping an open mind that we will positively accept all the high quality and mature technology, so that we have to provide interfaces on framework design for the new coming technologies.
The most typical manifestation of Qitmeer’s pluggability is our abstraction of the consensus plugin, which means that any protocol that is compatible with the BlockDAG framework can be replaced. Therefore, Qitmeer quickly implemented the consensus plugin of SPECTRE & GhostDAG, and even implemented a version of Conflux based on Conflux paper to check the stability of pluggablity before Conflux protocol had an official implementation.
Qitmeer’s pluggable design is best known to the community for its mining algorithm. Qitmeer is a hybrid mining algorithm, which is a reflection of Qitmeer’s open spirit and its desire to be as rich as possible in the mining ecosystem, and the need for Qitmeer to make flexible adjustments in the early stages of growth according to the development of the network. Qitmeer’s mining algorithm has implemented CPU-friendly Blake2bd, GPU-friendly Cuckoo Cycle and FPGA-friendly keccak256, and it also supports hybrid mining with multiple algorithms simultaneously, and each algorithm adjustment is relatively smooth.
One recent manifestation of Qitmeer pluggability is the replacement of the network library with libp2p. The framework code of Qitmeer is migrated from Btcd, after a period of testing, it is found that the stability and connectivity of the network did not meet the engineering requirements of the BlockDAG network. Because BlockDAG is required to carry highly concurrent block requests, the MeerDAG protocol has ensured that there is no upper limit for transaction throughput, so the bottleneck will only be in the connectivity of the network itself. Qitmeer cannot improve the physical limit of network, but it can still optimize the network library and improve the network utilization, to make the transaction throughput close to the limit of the network as much as possible. Libp2p is a network library open sourced from IPFS project. In addition to the connectivity optimization, it also supports many advanced attributes, such as support for URL-like network protocols, which makes it convenient to connect intranet nodes in the network and can give full play to the computing power of the nodes to achieve load balancing. Thanks to Qitmeer’s pluggable design, the libp2p migration went very smoothly and was completed in two weeks, and there was no major compatibility issues after the migration.
Qitmeer’s pluggable design also answers many people’s concerns about why Qitmeer does not prioritize the optimization of the two-layer network, which does not require a network-wide consensus for each transaction because the computation is off the chain, and the natural speed can reach a theoretically unlimited expansion without considering physical factors such as network congestion and machine computing power, etc. For example, if Qitmeer used sharding or lightning networks first in order to increase transaction throughput, it could easily reach thousands or even tens of thousands of TPS. But this is not very meaningful. So the more critical question is not what Qitmeer should do first and later but whether Qitmeer can do it. Or to think in another way, if it’s the same sharding or two-layer chain, in the case of the same security, do you want the TPS of each sharding or two-layer chain to be in the thousands or only a few dozen? This depends on whether the protocol framework of Qitmeer is flexible enough, and that is, pluggable or not. In fact, Qitmeer’s smart contract is cross-chain, and it can also be considered as 2 layer, so from this point, TPS can be as high as it wants. Although cross-chain and 2 layer smart contract are not new concepts, and may be misunderstood by the community that Qitmeer has done nothing in terms of smart contract design. But if Qitmeer positioned smart contracts as cross-chain, it would have to ensure an open interface in data structure and protocol design. As an obscure example, Qitmeer’s blocks are reserved with a field similar to the Ether state root, which provides various possibilities for smart contract extensions.
Fairness
BlockDAG is naturally more fair than BlockChain under the same circumstances. Because of its high mining blocks rate, although the probability remains constant, the miners can get the expected benefits in a very short period of time. The principle of mining pools is similar. Instead of increasing the mining success rate of miners, mining pools reduce the mining risk. But fairness is a systematic project involving mining algorithms, economic models, consensus algorithms, reward mechanisms, etc. So it cannot totally ensure the fairness only by the rate of block’s generation. The economic model will have a special article on fairness, and the fairness of the mining algorithm has also been introduced in previous articles, here we focus on the fairness of the reward mechanism.
The principle of a reasonable reward mechanism is getting more pay for more work done, and then try to balance interests of each role in the ecology. BlockDAG is much more complex than BlockChain in terms of reward design. Blockchain naturally solves the problem of transaction ordering because there is only one chain. However, BlockDAG suffers from the problem that a single transaction exists in multiple blocks of the same height. Then the order of transactions in these blocks becomes very crucial.
Qitmeer has been weighing whether to choose SPECTRE or GhostDAG for the core consensus plugin in the beginning. SPECTRE has advantage of fast transaction confirmation and it has been mature for two years. It doesn’t support transaction linearly ordered, however Qitmeer didn’t consider to implement the layer1 smart contract due to the stability of its underlying network, so it doesn’t matter if the transaction can not be linearly ordered. At the same time, GhostDAG (which is Phantom at that time) supports transaction linearly ordered to provides more space for the future network scalability. The shortage of GhostDAG is that there was not enough market maturity validation, if there is problem with protocol, this problem will be fatal. The decisive factor for MeerDAG to adopt the hybrid protocol with GhostDAG as the main part and SPECTRE as the auxiliary part is the reward mechanism design. In order to encourage miners to contribute to the network actively, the basis of Qitmeer reward mechanism requires that the order of any two transactions to be certain, and who packages the transaction first will get more rewards. Qitmeer has taken significant risks for the reward mechanism, which shows that the Qitmeer’s team is serious about fairness. Therefore, the current mechanism of transaction fees is first come first served, and only gives to miners who pack first, introducing a certain competition so that miners can be more motivated to provide security to the network. The idea of first-come, first-served originated from Inclusive’s paper, but, the reference consensus plugin provided by Inclusive at that time was too simple to have the value of engineering level. Qitmeer provides a best practice for this first-come, first-served idea by introducing the GhostDAG consensus plugin.
BlockDAG’s reward mechanism is also more complex than BlockChain’s in terms of the design of transaction fees. Miners are profit-oriented, so if there is no reasonable incentive mechanism, they will naturally pack transactions with high fees, which will result in a very high overlap of transactions in blocks, and the high overlap of transactions will greatly reduce the advantages of BlockDAG’s high scalability, and it is unfair to users with low fees. To take an extreme example, if all miners mining the same, then BlockDAG would degenerate into a blockchain. It is even impossible to cancel the transaction fees to avoid transactions overlap, which might lose miners’ enthusiasm of packing and likely just mining the empty blocks. Inclusive came up with this problem first but Inclusive did not provide a final solution, only an idea to change the packing priority of transactions by weithting. Qitmeer believes in simplicity and has adopted a simplest implementation that the transaction fee is proportional to the probability of the transaction fee being packed. For example, if the transaction fee of A is twice as high as that of B, the probability of being packed is correspondingly doubled, so that the duplication rate of the same transaction in the block will be significantly reduced. Of course, it doesn’t rule out that the miners will change the code privately to undermine fairness. But according to the first-come, first-served rule as we mentioned before, miners risk failing to compete for transaction fees, and the higher the fee , the more competitive the transaction and the greater the risk of failure. Therefore, it is more rational to accept the default setting. In addition to solving the problem of duplicate transactions, this ensures fairness for both miners and users, as it ensures that miners are still incentivized by fees and that users still have a probability of being packaged if fees are not high.
MeerDAG is not only DAG, but also the result of Qitmeer team fighting for countless days and nights towards their small goal of “building a usable BlockChain”. MeerDAG is also DAG, an inclusive public BlockChain that returns to the most genuine DAG. This is the original intention of MeerDAG.
