From Blockchain to DAG (II)
The Past and Present Life of MEERDAG
Preface
The development prospect of blockchain 3.0 was once hotly discussed, among which DAG is considered to be the most promising new generation of blockchain technology after Bitcoin and Ethereum. So what is the origin of DAG blockchain? What is its technical concept?
DAG and blockchain were originally two different technologies, but the combination of the two, the concept of "DAG blockchain" and its first appearance in the limelight, was made possible by two Israelis, Yonatan Sompolinsky and Aviv Zohar, the pioneers of this pioneering concept.
The GHOST protocol proposed by Aviv Zohar was adopted by Ethereum in the early stage. This protocol solves the security problems caused by chain forks. The data structure of the forked blockchain evolves from a single chain to a Tree chain. Later, Aviv Zohar further proposed the Inclusive protocol. Under the rules of the Inclusive protocol, the data structure of the blockchain evolves into a directed acyclic graph(DAG). With the continuous exploration of DAG by DAGlabs, the BlockDAG framework concept and technical architecture have been gradually established, during which the SPECTRE protocol, PHANTOM protocol and GHOSTDAG protocol were successively released.
Qitmeer was exploring consensus protocols that address scalability (availability) without sacrificing decentralization (partitioning fault-tolerance) and security (consistency) at the beginning of the project, and found that it coincided with the design philosophy of BlockDAG.
In a narrow sense, BlockDAG can be understood as a technical framework of a consensus protocol, which aims to further improve the DAG technology with high concurrency performance under the premise of ensuring decentralization and security. The proof-of-work-based PoW consensus mechanism can ensure that the blockchain network is sufficiently decentralized, so mining blocks to generate blocks has become an important technical feature, so it is called BlockDAG.
Qitmeer Team has made a lot of engineering-level optimizations for the consensus algorithms of GHOSTDAG and SPECTRE, and has created a MeerDAG protocol with its own characteristics by retaining the advantages of both protocols.
1. Basic structure of DAG
1.1 What does a DAG look like?
We are all very familiar with the data structure of the Merkle tree. Inside each block of Bitcoin, the Merkle tree is used to record transaction information, see the image below
It can be seen that the Merkle tree belongs to a directed tree structure, each vertex in the tree can only point to one previous vertex, and the entire data has an obvious flow direction. The DAG structure allows each vertex to point to multiple previous vertices, and the entire data flow also has an obvious direction. Another data structure is a directed graph. Unlike DAG, a directed graph allows data to flow back, and the data flow of the entire structure is not very obvious. See image 2 for the difference between the three.
1.2 Blockchain is a special DAG structure
After having an intuitive understanding of the DAG structure, let's sort out why blockchain is considered a special DAG structure?
Whether the blockchain forks is related to the speed of block generation and broadcasting speed. When the block production speed exceeds the broadcast speed, multiple blocks will be broadcast at the same time, and forks will occur. The more forks, the worse the security. In order to reduce forks, Bitcoin finds a balance between performance and security: a block is generated every ten minutes. Now let’s assume that the time for each block is long enough that no new block will be mined before the previous block is broadcast. Then the structure of this blockchain is a single chain, see image 3
In fact, due to network delays and other reasons, bifurcations will inevitably occur, so the actual blockchain structure will be as shown in image 4, and only one of the valid main chains (white) will be selected through the longest chain principle of the ledger consensus. The transaction information in the remaining blocks (red) is invalid and will not be adopted.
Now put aside the ledger consensus, that is, ignore how to select an effective main chain. From the perspective of the underlying network structure, a typical blockchain structure is shown in image 5, and a typical DAG structure is shown in image 6.
It can be seen that the only difference between the two structures is that the DAG block can point to multiple previous blocks, while the blockchain can only point to the only previous block. Specifically, the block header of the blockchain can only contain the hash value of one block, pointing to the only parent block; while the block header of the block under the DAG structure can contain the hash values of multiple blocks, pointing to different previous blocks. As shown in image 7.
Now we introduce the fork coefficient K, which refers to the number of forks that the network can allow.
When K=0, the entire network does not allow forks, as shown in image 3.
This network that does not allow forks is the blockchain.
Bitcoin meets this definition; although Ethereum has forks of uncle blocks, these uncle blocks are only used to judge the weight of the main chain, and they will not be added to the main chain in the end (uncle block records The transaction information is not included in the main chain), so Ethereum also meets this definition.
The K value of the DAG network must be an integer greater than 0. So from a structural point of view, DAG is an extension of the blockchain structure, and the blockchain is a special and simplified DAG.
1.3 The impact of DAG structure on performance
To put it simply, we can regard DAG as a network structure that allows forks, and the number of forks allowed is determined by the fork coefficient K.
So what exactly does a network that allows forks mean? It means that the speed of block generation can exceed the broadcast speed. On the one hand, this leads to more transactions packaged per unit time; on the other hand, when a block A is being broadcast by the entire network, another forked block B is also being broadcast by the entire network, and finally some nodes will only confirm A, other nodes will only confirm B, so DAG allows nodes in the network to record different information at the same time. The combination of these two aspects makes DAG present the characteristics of high concurrency and weak synchronization.
DAG is a kind of asynchronous bookkeeping, which can greatly improve the speed of network processing information, that is, TPS.
The blockchain is a network of strong synchronous bookkeeping, which requires each node in the network to record the same information at the same time. However, this requirement often limits the ability of the blockchain network to process information, making TPS relatively low.
So the question is, what kind of consensus should be used for this asynchronous bookkeeping network that allows forks? In the previous article, we will mention the DAG-based consensus mechanism in detail. The consensus mechanism is divided into block consensus and ledger consensus. The block consensus of DAG can be the same as that of blockchain. For example, POW is also used. Since forks are allowed, the block generation time can be set very short. The block consensus can also be different from the blockchain. For example, the IOTA project directly cancels the process of packaging and generating blocks. As long as a transaction occurs, it will be written to the network immediately (each block in the DAG diagram is not a block but a pen. transaction), thereby obtaining the ability of transaction processing at ultra-high speed.
DAG ledger consensus is much more complex than blockchain. How to prevent nodes from doing evil? How to screen when there are two contradictory transactions? How to prevent "double spending"? With the complexity of the underlying network structure, ledger consensus is also given higher requirements. It will be highlighted in subsequent articles.
1.4 TXDAG and BlockDAG
The difference between the generalized BlockDAG (block graph) and TxDAG (Transactional DAG, transactional DAG). Broadly or in terms of data structures, BlockDAG and TxDAG are just two different data structures. The difference is that the former will package multiple transactions into blocks, and the ledger is organized by blocks; while the latter has no concept of blocks, and the ledger is composed of transactions, which can also be understood as only one transaction in a block. Since the transaction has many common transaction descriptive information, that is, the header information, this part of information can be stored in the block, and the transaction only needs to save the different parts of the transaction, so that the HASH process (mining) is skipped and directly uploaded chain. Since BlockDAG not only retains the high concurrency of DAG, but also packs multiple transactions in one block, the storage efficiency and transmission efficiency of BlockDAG ledger will be higher than TxDAG.
1.5 Advantages of DAG
Compared with the blockchain, DAG is actually the difference between a graph and a chain. For a chain, it cannot only deal with one part, because there is only one in-degree and out-degree of the chain, and the nodes on the chain cannot be split into several Nodes to process, but it is possible for graphs, because graphs can have multiple out-degrees, then nodes connected by multiple out-degrees can be processed at the same time.
For the chain network, it is not that the processing ability of the nodes is not strong, but the chain structure cannot be calculated in parallel, and the time wasted is mainly waiting time: one is to initiate a transaction, which needs to be synchronized with all nodes; the other is the confirmation time, when there is a node confirmation that needs to be synchronized to the whole network. For DAG, there is no such problem. When the wallet initiates a transaction, it does not need to wait for how many transactions it has before. It only needs to go through partial verification, network broadcast, and other partial verification, which is equivalent to decentralizing the transaction confirmation. Nodes are doing work similar to puzzles, splicing their own transactions with those confirmed by others.
Therefore, it is concluded that DAG has the following advantages:
(1). Fast transaction speed
While achieving the same level of decentralization and security as Bitcoin and Ethereum, DAG local processing and parallel settlement can greatly increase transaction speed, making transaction throughput (TPS) and final delay more than two orders of magnitude promote.
(2). Strong expandability
Since DAG supports asynchronous bookkeeping, nodes in the network can process new transactions in parallel without waiting for data synchronization of other nodes, avoiding time waste, improving transaction efficiency, and allowing each node participating in bookkeeping to be greatly extended quickly. Therefore, DAG is very suitable for payment projects, such as cross-border micropayment and inclusive financial business scenarios advocated by Qitmeer Team.
(3). More difficult to modify maliciously
Compared with the chain structure, it is much more difficult to modify maliciously in a DAG because the DAG has many out-degrees and in-degrees, and if a node is modified, the corresponding in-degrees have to be modified.
2. Past and Present of MEERDAG
2.1 Origin of DAG Technology
In 2013 at bitcointalk.org, the famous birthplace of blockchain, an Israeli Hebrew University scholar with the ID Avivz78 proposed to introduce the DAG concept as a consensus algorithm into the blockchain structure and created the GHOST protocol.
After the GHOST protocol was proposed, Yonatan Sompolinsky proposed another new idea where the newly generated blocks point to all known forked end blocks, i.e., a block has multiple fathers, at which point
the block chain changes from a single chain to a structure consisting of multiple forked chains together, and such a chain structure is called DAG (directed acyclic graph).
In 2016, the SPECTRE technical protocol paper was released, which further improved the details of the technical architecture, formed the prototype of the first-generation blockDAG protocol, and proposed the grand idea of network delay without parameterization (or delay parameter adaptation).
In 2018, DAGlabs launched the PHANTOM protocol. Solved the problem that the SPECTRE protocol cannot trade linear sorting and continued to optimize it to form the GHOSTDAG protocol, which is the first industrial-grade BlockDAG protocol and also marks the maturity of BlockDAG.
At the end of the GHOSTDAG protocol paper, Yonatan Sompolinsky envisioned a possible protocol combining GHOSTDAG + SPECTRE, but did not introduce it in detail
3. Thoughts on MEERDAG’s technology selection
3.1 Thought about MEERDAG technology selection
In the first stage of Qitmeer Network, Mecca Network, it coincided with the upsurge of expansion technology exploration, faced with many mainstream expansion solutions on-chain and off-chain, when selecting Qitmeer public chain technology, it also faced difficult choice.
In terms of expansion technology selection, the industry is generally faced with an impossible triangle problem. It is impossible to achieve scalability (Scalability), decentralization (Decentralization), and security (Security) at the same time, and only two of the three can be achieved. The Qitmeer team at that time also faced such a problem. After studying many expansion solutions, a technology called BlockDAG was finally favored by the team.
3.2 Brief Introduction to SPECTRE Protocol
SPECTRE is a blockDAG protocol that supports fast confirmation. SPECTRE's consensus algorithm is a voting algorithm. Once a conflicting transaction is found, the block containing the conflicting transaction will be used as a candidate to accept votes from all blocks, with one vote for each block. SPECTRE's voting has an amplification effect. For example, a block will follow the majority of votes it has concentrated on in the past, so the convergence speed is very fast, and a slight difference in the number of votes can result in a huge advantage for the winner. Let the honest blocks vote for the honest blocks, and the later honest blocks will give the previous stacking power, so that malicious attacks will fail and the security of the network will be guaranteed.
SPECTRE can only guarantee fast confirmation of honest blocks. For two conflicting blocks whose release time is close, the confirmation time of SPECTRE is uncertain. This is the concept of weak activity proposed by SPECTRE, that is, it cannot be guaranteed that all blocks can be Final confirmation within a reasonable time.
SPECTRE is a consensus protocol based on the transaction system. In the transaction system, only evildoers can create double-spend transactions. That is to say, double spending transactions will not have much impact on honest blocks. In addition, making double-spend transactions is very strict on time control, and it is difficult to cause attacks under normal circumstances. Therefore, Qitmeer Team believes that the problem of weak activity of SPECTRE is acceptable in actual projects.
3.3 Brief Introduction to GHOSTDAG Protocol
As you can see from the SPECTRE profile above, SPECTRE is very good at troubleshooting conflicting transactions and defending against attacks. If a project is only used for payment purposes like Bitcoin, the fast confirmation of SPECTRE protocol is sufficient. But if you want to integrate smart contracts, SPECTRE can't do it.
Because SPECTRE can only do a relative sorting of conflicting transactions (judging the order of conflicting transactions), but it cannot do an absolute sorting for all blocks. Because the language of the smart contract must be Turing complete, just like we write a piece of computer program, we need to perform various operations in a strict order, so the network with smart contract function has a characteristic: the transactions in the network can be timed Do linear sorting (chronological) one after another.
In response, Yonatan Sompolinsky newly designed the GHOSTDAG protocol to form a linear order to the DAG blocks. SPECTRE and GHOSTDAG are two complete and independent protocols, not one complementing the other.
The mining mechanism of GHOSTDAG is the same as that of SPECTRE, which will generate the same type of DAG structure. The difference is that GHOSTDAG judges whether the block is honest or malicious by analyzing the block connectivity, sorts the blocks according to the classification, and generates a strict DAG block. The linear order of the conflicting transaction is judged by the linear order.
The GHOSTDAG protocol not only enables DAG to obtain transaction linear ordering capabilities, but also solves the weak activity problem of the SPECTRE protocol. The GHOSTDAG protocol is also the first blockDAG protocol that supports linear ordering of transactions.
3.4 MEERDAG Protocol
The possible protocol combining GHOSTDAG+SPECTRE that Yonatan Sompolinsky envisaged at the end of the GHOSTDAG protocol paper is more about providing guidance in terms of ideas, and the focus is on demonstrating the rigor of the algorithm, which involves many engineering practice issues and needs to be based on actual The situation is constantly practiced and tested, and one of the most typical problems is performance. If it is implemented directly according to the reference algorithm in the original text, the performance is almost unacceptable.
Qitmeer Team considers that the underlying application scenarios of the public chain are mainly inclusive finance, digital asset transactions, and supply chain management.
Considering the block reward mechanism and ledger consensus requirements for linear sorting capabilities, and at the same time taking into account the transaction confirmation speed that is more important to the value exchange experience.
The blue set (honest block) of GHOSTDAG is more difficult to stabilize and the confirmation time will be much longer than that of SPECTRE. However, since the block reward does not require high confirmation time, it will not affect the network. GHOSTDAG protocol is chosen as the base consensus protocol and SPECTRE protocol is chosen as the assisted consensus protocol.
MeerDAG, a hybrid consensus solution combining SPECTRE and GHOSTDAG, is a BlockDAG scaling solution that conforms to the classical blockchain settings (open, fair, secure, scalable) and is most compatible with the classical blockchain model UTXO. While the classic blockchain discards all blocks outside the longest chain, MeerDAG is a cooperative model that retains the SPECTRE protocol and keeps all blocks, so it can achieve high throughput and provide real transaction-level high throughput, as well as fast confirmation of blockchain transaction services. Secondly, BlockDAG is based on the heaviest chain rule and can achieve 51% fault tolerance comparable to Bitcoin. Furthermore, BlockDAG network does not have any special nodes, and does not require nodes to be online or not. In mining, this collaborative model achieves the ideal balance between security, openness, fairness, and scalability of classical blockchain metrics, and allows free access to the network through proof-of-work mechanisms.
During the period of Qitmeer Network Medina, the network introduced real computing power environment tests. The team continuously iterated the PoW algorithm and improved the efficiency of the algorithm, fully retained the advantages of the GHOSTDAG+SPECTRE protocol, and continuously reduced the difficulty of protocol implementation in engineering implementation. For example: according to the first version of GHOSTDAG Algorithm papers, the calculation of inverse cones needs to be exhaustive, and the algorithm complexity is O(n^3). After a large number of engineering-level tests, the complexity is reduced by two orders of magnitude to O(n), which greatly meets the usability requirements. Under the basic requirements of ensuring security, decentralization and fairness, TPS performance is maximized. Proposing its own solution for a high-performance blockchain network, Qitmeer Network aims to build a more efficient, secure, and open decentralized platform for decentralized applications.
Qitmeer Team innovatively combined the GHOSTDAG+SPECTRE protocol to form its own characteristic MeerDAG protocol, which became the technical prototype of the new generation of BlockDAG. The core positioning of Qitmeer's BlockDAG underlying network is to serve as a value circulation network. On the Layer 2 layer, it combines the MeerEVM-driven pluggable virtual machine system to build rich blockchain applications and embrace the entire blockchain ecology.
Reference：
[1] From blockchain to DAG (2) -- the basic structure of DAG, https://mp.weixin.qq.com/s/Mc2uEOLtT_Z3OMapNh1TGg
[2] From Blockchains to blockDAGs， https://www.youtube.com/watch?v=tk38AAV_whw
[3] Jeff Zhou：DAG high-speed asynchronous blockchain technology，https://www.jianshu.com/p/45d73e0e74ec
[4]GHOST, SPECTRE, PHANTOM Technicial Theory，https://mp.weixin.qq.com/s/nGR0ld73oXgs_p_MtDcv-Q
[5]Qitmeer Team – “Qitmeer White Paper”
