From Blockchain to DAG (I)

Ledger Structure and Consensus Mechanism

Preface

The full name of DAG is Directed Acyclic Graph. It was originally a data structure in the computer field. In order to solve the problem of slow transaction speed of Bitcoin, it was re-proposed as an underlying ledger structure. In most of the introductions, DAG and blockchain are treated differently as two independent underlying ledger structures, and what's more, DAG is only regarded as a consensus mechanism. Qitmeer Network believe that BlockChain and DAG can be unified as one since both their technology are essential for the revolution of the digital world, but of course our view does not reflect the views of the general public, having said that, Qitmeer Network aims to educate the whole crypto-sphere on what DAG is all about and how DAG and BlockChain can co-exist and can also be unified.

To understand DAG, we first need to clarify two concepts: ledger structure and consensus mechanism.

As an underlying ledger structure, DAG has a consensus mechanism suitable for its own structure.

Blockchain is also an underlying ledger structure, but it is actually a special, simplified DAG, and its corresponding consensus mechanism is also a simplified version of the DAG consensus.

This article, as the first in the series, will help us understand the technical architecture of Qitmeer systematically by sorting out two concepts, namely ledger structure and consensus mechanism, from the working principles of Bitcoin and Ether, which we are familiar with.

1. How Bitcoin Works and its Performance

As the originator of blockchain technology, Bitcoin’s performance has long been unable to meet the current transaction needs, so congestion often occurs. Let’s take a look at the bookkeeping process of Bitcoin in the following picture:

Bitcoin's bookkeeping process：The miner node packs the transaction into the block, and makes this block a candidate block (block production process) by doing POW (proof of work) on the block; the candidate block is broadcast by the whole network and waits for confirmation by other miners. After the block is confirmed, it will be added to the longest chain.

Ideally, the next block can be packaged as a candidate block and broadcast after the previous block is confirmed and added to the chain by the entire network. If the block generation speed is too fast, the broadcast speed cannot keep up with the block generation speed; it will cause a new block to be dug out and broadcast before a block is confirmed by the whole network, which is a fork. Forking reduces the security of the network. In order to ensure network security, the Bitcoin block time is set to 10 minutes. And this setting also limits the ability of Bitcoin to process transactions, and its TPS is only about 7.

With the increase of nodes participating in bookkeeping, Bitcoin will still fork. Even if the malicious nodes are excluded, under normal circumstances, it is inevitable that two nodes will generate blocks almost at the same time. At this time, Bitcoin determines the main chain according to the "longest chain consensus", that is, after the fork, the node will continue mining based on one of the blocks, and then choose the longer chain as the main chain, which does not belong to the fork of the main chain Blocks will be discarded entirely. Due to accidental factors such as network delays, forks always occur from time to time, but the probability of forks occurring more than 6 times in a row is very small, so a block can be guaranteed to be in the "longest chain" after waiting for 6 blocks to be confirmed. , will not be tampered with.

Bitcoin adopts POW consensus (proof of work), and there are two main steps that take a lot of time.

One is to do proof of work (Time1), that is, to calculate the block hash value that meets the requirements. The second is the whole network broadcast (Time2), the process of waiting for other miners to confirm this block.

At the time of design, the block generation time of Bitcoin is set to 10 minutes (that is, 10 minutes of proof of work is required), and the size of each block is about 1MB, and a block can pack 2500-3000 transaction data. Although a single block can contain thousands of transaction information, it takes at least 10 minutes to complete a block, which leads to low transaction information recorded per unit time, that is, low TPS.

TPS (transaction per second) is a commonly used index to describe the performance of the blockchain. It refers to the number of transactions processed per second and is an important parameter to measure the throughput of a system.

Due to the slow block generation, the TPS of Bitcoin is only about 7. Therefore, the congestion of Bitcoin is often blamed on the POW consensus mechanism it uses. Some people will say that TPS can be increased by increasing the capacity of the block or increasing the speed of block generation, so that there will be no congestion. It’s a nice idea, but in practice it’s not so easy to increase transaction throughput. Increasing the block capacity will lead to an increase in Time2 (broadcasting time becomes longer), because a single block contains more bytes, and the required transmission time will correspondingly increase; although increasing the block production speed will make Time1 smaller , but when the block production speed is too fast and the broadcast speed cannot keep up, a new block will be dug out before a block is confirmed by the miners of the whole network, so a fork will appear. Forking reduces the security of the network. Please refer to the picture below:

Originally, the cost of modifying maliciously when there is no fork is no less than 51% of the HashRate of the entire network. Now after the fork, assume that the A chain gets 60% of the HashRate, and the B chain gets 40% of the HashRate. If you want to do evil and roll back the A chain to the B chain, you only need 11% of the HashRate of the entire network. So the fork reduces the cost of modifying maliciously and makes the network unsafe. Therefore, the 10-minute block time is a compromise between Bitcoin’s security and efficiency.

Therefore, it is not possible to increase the block capacity or increase the block out speed under POW. This will increase the possibility of forking and reduce the security of the network.

2. Bitcoin’s ledger structure and consensus mechanism

To summarize the above process we can know that the underlying ledger structure of Bitcoin is a single chain.

The consensus mechanism can be divided into two parts:

Block Consensus

That is, how to allocate packaging rights. Bitcoin is through POW (Proof of Work), and other common ones are POS (Proof of Stake), DPOS and so on.

Ledger Consensus

Ledger consensus, that is, each node confirms a valid ledger through this consensus, and this ledger cannot contain conflicting transactions. This set of consensus must be able to effectively eliminate malicious attacks and prevent "double spending" problems.

Satoshi Nakamoto introduced in the paper "Bitcoin: A Peer-to-Peer Electronic Cash System" that the essence of the Bitcoin workload proof mechanism is one CPU, one vote, and the longest chain contains the largest workload, so "most the decision of "people" can be expressed as the longest chain.

To be more specific, Bitcoin blocks are generated by miners' continuous mathematical operations, and each block must refer to the previous block, so the longest chain is also the most difficult to overthrow and tamper with, so nodes will always It is believed that the longest chain is the effective blockchain. Under normal circumstances, Bitcoin refers to the blockchain with the most accumulated difficulty and the chain that contains the most blocks as the main chain. Every Bitcoin (mining) node always chooses and tries to extend the main chain. Only miners who mine on the longest chain can be rewarded, which is what we often call the longest chain principle of Bitcoin.

Bitcoin’s ledger consensus is the "longest chain consensus".

3. Ethereum’s ledger structure and consensus mechanism

The operating principle of Ethereum is not much different from Bitcoin, so it will not be explained in detail here.

The underlying ledger structure of Ethereum has changed from a chain to a tree. The ledger consensus corresponding to the structure of the tree is "heaviest subtree consensus" (GHOST protocol: The Greedy Heaviest-Observed Sub-Tree).

Since Bitcoin uses the "longest chain consensus", as long as there is a fork, the security of the chain decreases, and the more forks there are, the less secure they become. This results in all the hashRate used to fork blocks being wasted. The GHOST protocol of Ethernet is that when there is a fork, the chain with the most sub-trees is the main chain. This way, even if there is a fork, the security will not be reduced; and the forked blocks (also called "uncle block") will also participate in the consensus with the ledger to help determine the main chain, so that this part of the HashRate will not be completely wasted.

As shown in the image above, the entire chain forks after block 0. If only honest nodes’ blocks are considered, according to Bitcoin’s longest chain principle, the main chain will be 0->1B->2D->3F->4C->5B. When a node does evil, the attacker provides a long chain 0->1A->2A->3A->4A->5A->6A. Under the longest chain consensus, the attack will succeed.

When considering the final subtree consensus: block 1B of the subtree contains 12 blocks, while block 1A of the attack chain only contains 6 blocks, the heaviest subtree consensus will select 1B as the block of the main chain, and then Further evaluation of the fork after 1B. By analogy, the final main chain will be 0->1B->2C->3D->4B. Uncle blocks originally invalidated under the longest chain consensus will be considered as "weights" and added to the calculation of the main chain, and the chain with the heaviest weight will eventually become the main chain. The uncle block must contain a valid block header, but the transactions recorded in it do not need to be confirmed, and the uncle block is not even required to be a valid block. Therefore, the heaviest subtree consensus only counts the number of uncle blocks, and the transaction information inside will not be added to the main chain, and the HashRate used to calculate this part of transaction information is still wasted. The block generation time of Ethereum is about 15 seconds. Although such a short block generation time compared with Bitcoin’s 10 minutes increases the possibility of forks, the use of the heaviest subtree consensus effectively guarantees the security of the main network. It also makes the TPS of Ethereum much higher than that of Bitcoin, which is about 30 to 40.

(1) Ethereum Block Consensus (Stake Proof Mechanism)

The Proof of Stake mechanism is an improved consensus mechanism designed to address the shortcomings of the Proof of Work mechanism. Its full English name is Proof of Stake, or POS for short, also known as the Proof of Stake mechanism. As the name implies, it is a consensus mechanism that determines the probability of successful mining based on the age of the currency held by investors (coin age = total amount of tokens pledged by miners * token holding time).

It can be simply understood that a POS token economic ecology is like a listed company with the same shares but different rights, and POS mining is like a dividend payment decision of a listed company, and every miner (coin holder) is a shareholder of the listed company. The accounting rights that miners compete for are like stock voting rights, and the probability of miners obtaining accounting rights is similar to the share of shareholders' voting rights (that is, the proportion of miners' voting rights to the overall voting rights). The number of tokens pledged by miners is the number of shares held by shareholders. Depending on the size of the pledged token share, some miners are major shareholders, and some miners are "small shareholders" or "minority shareholders". POS mining is also like depositing pledged tokens in a bank, and the bank pays interest based on the length of time and the amount of the deposit.

(2) How Proof-of-Stake Mechanism Works

Before starting to compete for block bookkeeping, the nodes with rights and interests put their rights into the POS mechanism, and at the same time their identity becomes a verifier. The POS mechanism randomly selects a bookkeeper according to how much the verifier bet. Block accounting. This randomness is not really random. It is generally proportional to the equity of the bet. Whoever has more equity has a greater probability of obtaining bookkeeping rights. If the selected bookkeeper has not kept the book for a period of time, the POS mechanism will re-select the bookkeeping node. When the block is completed, it will start to enter the next round of bookkeeping.

In the POS consensus, nodes compete for bookkeeping rights not by HashRate but by rights (tokens). POS also needs to calculate the hash value, but unlike PoW, it does not need continuous violent calculation to find the nonce value. The specific process is as follows:

Each node only needs to calculate Hash once in each round of consensus. The more rights and interests it has, the greater the chance of meeting the Hash target and the greater the chance of obtaining bookkeeping rights. It can be said that POS is a resource-saving consensus protocol. Equity is not only related to the number of tokens, but also related to the holding time of tokens. Therefore, the more tokens you hold and the longer the time, the greater the chance of obtaining bookkeeping rights.

The whole process can be simply summed up as follows: the token holders mortgage their tokens to obtain the opportunity to generate blocks, and then the POS consensus will use an election algorithm to select block miners from among them according to the ratio of the amount of tokens they hold. The miners complete the packaging transaction at the specified height, generate a new block, and broadcast the block. The broadcast block is verified by the validator. After the verification, the block is confirmed. This round of POS consensus process is completed.

（3）The difference between POS mechanism and PoW mechanism

The proof-of-work mechanism relies on HashRate when generating blocks, so that the creation of each bitcoin requires at least 100,000 kilowatt-hours of electricity (2022 data), which is equivalent to 6,600 gallons of gasoline. The proof-of-stake mechanism does not use HashRate as a resource when generating a block, but a node must provide a proof to create a block, so that the entire network agrees that it has a certain amount before creating this block. Treat the ownership of digital currency as a scarce resource to generate consensus .

Only those who hold digital currency can mint coins, and the currency can be mined without a lot of HashRate, avoiding the trend of "HashRate concentration" in the Bitcoin network and returning to the "decentralization" of the blockchain Essential requirements.

4. Qitmeer’s ledger structure and consensus mechanism.

1. BlockDAG ledger structure.

The underlying ledger structure of Qitmeer is BlockDAG (block graph), which is completely a block network system based on a directed acyclic graph structure. From the tree chain structure of Ethereum to a multi-dimensional directed acyclic graph structure, it is an upgrade and expansion of the blockchain system, which fully releases the performance of the blockchain. BlockDAG is based on the heaviest chain rule, which can achieve 51% fault tolerance comparable to Bitcoin. At the same time, the block graph structure realizes concurrent data transmission on the network, which greatly improves the transmission performance and can achieve a system throughput far exceeding that of Bitcoin and Ethereum. , under ideal conditions of bandwidth and propagation delay, TPS can reach 4000+. With the breakthrough of Meer Labs' research on high-speed subnets, the throughput of the entire system will be greatly improved.

BlockDAG’s collaborative model provides more fairness than blockchain’s competitive model. Concurrent blocks can be confirmed as long as they are legal. Regardless of how much HashRate it has, each node is rewarded according to its contribution. 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 local verification, network broadcast, and other local verification, which is equivalent to decentralizing transaction confirmation. Each node is doing a puzzle-like job. Splice your own transactions with those confirmed by others. As a result, the transaction throughput capability of the blockchain system is expanded, and the performance of the blockchain network is fundamentally improved.

2. Qitmeer Block Consensus and Reward Mechanism.

(2.1)Block Consensus and Reward Mechanism

Qitmeer Network is a high-performance blockchain network that uses the workload proof (PoW) consensus mechanism and the original Meer Keccak 256 workload proof algorithm, which is mainly used to find certain subgraphs in large pseudo-random graphs. Requires intensive memory operations. Improve the decentralization and security of the blockchain with a distributed node network.

Qitmeer focuses on fairness among all nodes, regardless of how much HashRate a node has. For miners with a strong HashRate, they may fight for block rewards. Block rewards are relatively rich, but the competition is fierce; for those miners with small HashRate, they still have the opportunity to share transaction fees, first come, first served.

Qitmeer Network self-developed new generation BlockDAG hybrid protocol, MeerDAG protocol. Indicate honest blocks in blue and dishonest blocks in red. Qitmeer Network only rewards blue squares. Miners are encouraged to work actively. Only based on the blue set strategy can greatly enhance security, but at the same time it will also discriminate against miners with weak HashRate or poor network connection. Maybe they are also honest miners, but they are still considered "dishonest" due to the constraints of the consensus protocol. Therefore, we can use transaction fees to compensate these honest miners.

The network relies on the hard work of miners to consolidate security. The competition in the BlockDAG model is not as fierce as that of the blockchain, so it is necessary to encourage miners to work actively to better maintain the security of the network's HashRate. Since passive work has a higher probability of being identified as a "red block", miners will try to avoid this.

(2.2) mining agreement

Mining process

Qitmeer supports the getblocktemplate mining protocol. It lets miners decide which transactions to put into blocks. Miners send requests to Qitmeer full nodes through getblocktemplate RPC.

Miners then initiate PoW using the data from the getblocktemplate RPC. If it gets the correct "answer", the underlying block is submitted via the submitblock RPC. The specific process is shown in the figure below.

Miner function

Qitmeer mining tool (Qitmeer-Miner) supports independent mining and mining pool mining.

Independent mode (Solo)

If a miner decides to mine meer (qitmeer native currency) without joining the pool, he will start the independent mining mode. Solo miners connect to a full node and call the RPC service to mine blocks. Solo miners recommend using NOYCE N57 integrated circuit HashRate machine to achieve higher efficiency.

Pool Mode (Pool)

Qitmeer mining pool supports stratum mining protocol like most PoW mining pools. Currently, the mining pools supporting Qitmeer include mainstream mining pools such as F2pool, Huobi Pool, Hashpool, and Meerpool.

(3) Qitmeer ledger consensus:

The MeerDAG consensus protocol is an innovative BlockDAG hybrid protocol that perfectly integrates the characteristics of GHOSTDAG+SPECTRE. GHOSTDAG is used as the basic protocol to achieve high-throughput linear sorting services, and the SPECTRE protocol is used as an auxiliary protocol to ensure fast confirmation of transactions. Its working principle will be explained in detail later.

5 . Summary

From the introduction of public blockchains such as Bitcoin, Ethereum, and Qitmeer, it can be found that:

the structure of the underlying ledger is closely related to the consensus mechanism.

Bitcoin is not scalable due to protocol constraints. According to the Nakamoto consensus, that is, the longest chain rule, the 1MB block size and 10-minute block rate limit Bitcoin can only reach a theoretical throughput of 7 transactions per second, no matter how large the bandwidth and how fast the propagation delay is. The most intuitive way to improve scalability is to reduce the block time or increase the block size. The reason why Satoshi Nakamoto did not adopt it is that it would lead to a fork, and at the same time, it would disperse the HashRate of the main chain, thus causing security holes.

Ethereum's GHOST protocol introduces the heaviest tree consensus to preserve forks without sacrificing security. Note that here the blockchain has been converted to a block tree. Since the largest subtree concentrates most of the HashRate, the security is as high as Bitcoin. The main chain refers to the block chain from the origin to the leaf with the largest number of children, and other blocks are off-chain blocks. Only main-chain blocks contribute to throughput, while off-chain blocks contribute to enhanced security. Due to the higher block rate, the block tree greatly improves the throughput.

However, there is still a waste of transactions in off-chain blocks, which should also help improve throughput. The BlockDAG protocol adopted by Qitmeer proposes a new ledger data structure, that is, each block confirms each unconfirmed block, and upgrades the block tree structure to a block graph.

From the development history of blockchain to BlockDAG, it can be seen that blockchain is a special case of BlockDAG in the low-throughput situation, which means that the two are essentially the same. Therefore, it is the closest scalability solution to the Bitcoin network.

BlockDAG is stable because it inherits all the long-proven stable properties of Bitcoin, and it is infinitely scalable at the protocol level, with only physical limitations such as bandwidth and propagation delay.

The basis for further expanding the performance of the public blockchain is an efficient and stable consensus protocol, so BlockDAG has become Qitmeer's preferred expansion solution.

Author: MO

Translation: Cai

References：

• [1] Wechat Official Accounts "Blockchain New View": From blockchain to DAG
• [2] CSDN Blogger Ziye: https://blog.csdn.net/u014264140/article/details/114006887
• [3] What determines the performance of the public chain - the misunderstood TPS: https://t.1yb.co/6cX
• [4] Ethereum Ghost Protocol and Uncle Blocks: https://blog.csdn.net/u014264140/article/details/114006887
• [5] GHOST，DAG，SPECTRE，PHANTOM & CONFLUX Technical Theory: https://www.jianshu.com/p/8734e06d558f
• [6] Qitmeer Team — "Qitmeer White Paper"