MeerDAG Consensus Protocol — “Ledger Temporality”
MeerDAG is an innovative BlockDAG ledger consensus protocol that uses unique classification algorithms and topological rules. 🌎As the first layer core framework for blockchain technology, MeerDAG provides an entirely new solution to solve the scaling problem in the Nakamoto Consensus. This protocol is designed to address the challenges that PoW (Proof of Work) -based blockchain networks face when processing large-scale transactions and data.🚁
MeerDAG integrates the mainstream EVM technology architecture in its second layer framework to achieve compatibility with the Ethereum ecosystem, enabling it to undertake and drive a thriving decentralized economic system. The flexibility and compatibility of the design make it a promising blockchain technology that is expected to play a key role in solving the performance problems of existing blockchain networks.
Please note that this article assumes that you already have basic knowledge of Satoshi Nakamoto consensus (such as Bitcoin). If not, you can refer to our consensus article to learn relevant knowledge.
🚤Bitcoin scalability problem
🥊Bitcoin’s classic blockchain architecture relies on a consensus rule of 51 percent security, which prevents malicious nodes from tampering with ledger information as long as the longest chain on the network is created by an honest miner. However, there are some problems with the Satoshi consensus.
Transaction latency problem
Nodes need to wait for new blocks to be validated before they can confirm the longest chain. This verification process takes time, so transaction confirmation can be slow. Any classic blockchain faces this problem because the latency between blocks is often much greater than the time it takes for the entire network to validate a new block.
Isolated blocks
When two honest miners create blocks at the same time, the blocks compete with each other until one of them is discarded. Such discarded blocks are often referred to as isolated blocks, which reduces the performance output of the network.
Overcoming this throughput/security trade-off is the primary motivation behind the MeerDAG Consensus protocol.
DAG expansion
The DAG structure uses the simplest scaling idea, which is to allow parallel blocks. The core idea is very simple: instead of having any block point to a single parent block, allow it to point to multiple parent blocks, so that the blocks in the network have the structure of a strip rather than a chain.
🚂The throughput of a blockchain network can be likened to the number of lanes on a highway. Since Bitcoin uses a single-chain structure, only one block can be allowed at a time, like a one-way street. The MeerDAG consensus protocol used by Qitmeer allows multiple blocks to be allowed at the same time, like a two-way eight-lane highway.
Existing problem
This scaling method also introduces some problems, one of which is the obvious problem of double-flower attacks. Allowing multiple parallel blocks increases the likelihood of processing transactions that contain conflicts. The key to solving the transaction conflict problem is to maintain the absolute order of blocks in the DAG, which is a complex task.🚨
In a single chain structure, the relative order between blocks is unambiguous because each block has an explicit parent block. But in DAG, we can only determine the relative order between certain subsets of blocks, but not between other subsets of blocks, which is called partial ordering. In blockchain transactions, partial ordering is unacceptable because it leads to an unclear order of transactions, which raises transaction conflict issues.
Blue: clear relative order; Orange: unclear relative order.
In the figure above, we see that the blue blocks have a clear relative order because they are directly or indirectly connected. However, the relative order between the orange blocks is not clear because there is no such direct or indirect connection between them.
These problems all point to a common challenge: solving the absolute order problem between DAG blocks. Specifically, we need to rebuild the DAG structure to ensure that each block has a clear order of creation, thus solving the transaction conflicts and double-spending problems that the DAG structure can cause.
However, how to achieve this absolute ordering is not a simple matter. This involves choosing the appropriate collation, a choice that will directly affect the success or failure of MeerDAG. Let’s explore one way to solve this challenge.
🚤Qitmeer Network sequencing ideas
Judge red and blue blocks
In order to solve the sorting problem in the BlockDAG consensus protocol, the MeerDAG protocol introduces the GHOSTDAG protocol and undergoes in-depth optimization. It determines the “red block” (invalid block) and “blue block” (honest block) in the block graph network based on the connectivity between honest blocks.
The connectivity is determined by a parameter called the k value, and the connectivity of the “blue block” must meet the subset requirements of the maximum k-cluster.
The set of all blue blocks is called the largest k-cluster subset, written as MSCk, and all blocks in the set are recorded in the ledger.🧩
In short, if the connectivity between the blocks generated by malicious nodes and those generated by honest nodes is low, they will be marked as red blocks, indicating invalid. Conversely, if the connectivity between the blocks generated by honest nodes is high, they will be marked as blue blocks, indicating honest blocks. This mechanism ensures that only honest blocks are recognized and recorded in the MeerDAG network.
Classification algorithm and blue block subset
The MeerDAG protocol refers to the GHOSTDAG protocol and designs a classification algorithm to find the subset of blocks that contain the most honest nodes interconnected with each other. In this process, certain conditions (k value requirements) need to be met, and voting is performed according to the trend of connectivity from high to low, effectively distinguishing the subset of blocks from honest nodes and those from malicious nodes. The core goal of this algorithm is to find the largest subset of k-clusters, namely MSCk (blue block subset).
As shown in the figure below, the blocks generated by honest nodes are marked in blue, and the blocks generated by attacking nodes are marked in red. All sets that meet the requirements of the figure belong to the maximum subset of 3-cluster, that is, all blue blocks belong to MSC3.
Application example of MeerDAG protocol in a DAG graph with k = 3:
The maximum 3-cluster subset of the DAG graph MSC3 = {Genesis, D, H, K, M, C, E, I}.
Sequencing idea 1: Using topological rules to establish timing
In blockchain networks, topological sorting is a key sorting method used to arrange vertices on DAG into a linear sequence. It’s core principle is to prioritize selecting vertices without entrance as the starting point, gradually removing the sorted vertices, and selecting the next vertex without entrance, repeating this process until all vertices are sorted.
🚂The MeerDAG protocol adopts the idea of topological sorting in practical applications to establish the timing of blocks in the blockchain network. In this sorting, blue blocks are usually prioritized, while red blocks are usually ranked after blue blocks due to their low connectivity.
Using Figure 7: An example of a DAG graph with k = 3 to illustrate. According to topological rules, first, the blue blocks in MSC3 are topologically sorted Genesis- > D- > E- > C- > I- > H- > K- > M. Then, the black border blocks that are not in MSC3 are sorted and added to the blue block arrangement. Finally, the linear sorting result of the entire network is Genesis- > D- > E- > C- > I- > H- > K- > M- > B- > F- > L- > J. At the same time, transactions are automatically sorted within each block according to the order in which they appear.
However, it should be clear that this result is not unique, and there are multiple possible topological sorting methods. One of the final output results of DAG can also be: Genesis- > D → C → G → B → F → I → E → J → H → K.
In summary, the reason why the MeerDAG protocol chooses to use topological rules to determine timing has extremely important theoretical and practical significance. This innovative mechanism will make the BlockDAG field a leader in one-layer expansion solutions.
Topological sorting not only helps to meet the high requirements of block reward mechanism and ledger consensus for linear sorting, but also effectively handles the complexity of DAG network data structures, ensuring the order of transactions and blocks in the BlockDAG network, thus laying a solid foundation for the operation of the entire system, improving network stability and transaction throughput.
Sequencing idea 2: Determine a main chain
Another way to establish temporal sequence is to determine a main chain and sort all blocks according to a set of deterministic rules. This method calculates the main chain in the block DAG and uses this main chain to construct a sorting algorithm. One possible method is to use the GHOST protocol to calculate the connectivity score weight and identify the main chain in the block DAG to complete the sequencing.
In the above figure, starting from block G and moving forward, there are 3 blocks to choose from, with weights of (381,765,381), so the heaviest one is 765. Keep moving forward until you reach the finish line and build the main chain (green). The final main chain order is Genesis- > 765- > 380- > 192- > 113- > 78- > 38- > 20- > 11- > 3.
This method selects a core anchor chain of the block DAG and uses this path to construct sorting. It should be noted that there are still some potential challenges with this method. By default, it is assumed that each connected block has the same weight, which may provide opportunities for potential attackers, especially when the convergence speed of the network is slow. Therefore, further research and improvement are needed to ensure the security and stability of the network and maximize the advantages of sorting algorithms.
Summary
🎡The importance of the ledger temporality of the MeerDAG protocol is not only limited to improving blockchain performance, but also to maintaining the interests of participants such as miners and node operators in the blockchain network, achieving an ideal balance of classic blockchain metrics of security, openness, fairness, and scalability.
As an innovative blockchain one-layer scaling technology, it will enhance the scalability of the entire Qitmeer Network and meet the needs of different business scenarios through more flexible and scalable cross-chain synchronous consensus with the layer2 data layer in the future. It not only provides strong support for solving the multiple challenges faced by the current blockchain field, but also provides valuable experience and inspiration for the development of BlockDAG frontier fields.
