From blockchain to DAG (III)
MEERDAG Consensus Mechanism
Detailed explanation of SPECTRE protocol technology
Preface
Project Vision: Based on the underlying technology of blockchain, Qitmeer network will create a high-dimensional digital world led by users and open-source developers with open collaboration, privacy protection, and ecological co-construction, bringing a new paradigm to Web3 and the future of Islamic finance. infrastructure. With the image of shared governance, openness and inclusiveness, Qitmeer Team encourages partners with common mission and values to build a high-performance public blockchain that is decentralized and ecologically prosperous.
Since the birth of Bitcoin ten years ago, the infrastructure of the blockchain has been continuously iterated, and various public chain projects have emerged one after another. The Impossible Triangle has always been the technical bottleneck that all public chain teams want to overcome. In order to promote its high performance, some public chain projects have sacrificed some degree of decentralization and used a smaller group of entities to control the network. Although such a public chain network runs fast, its foundation is built on top of a building in the air.
Qitmeer insists on openness, fairness, security, and scalability as the core indicators of an excellent public chain. We believe that meeting the above indicators is the ideal classic blockchain setting of Satoshi Nakamoto. The Qitmeer consensus mechanism follows the classic blockchain setting: nodes can freely enter and exit the network through proof of work, ensuring that the network will not be controlled by a single entity, and truly realizing the decentralization ideal of Satoshi Nakamoto; the cooperative model miners based on BlockDAG (Block Directed Acyclic Graph) can fairly obtain corresponding rewards according to their contributions; the graph ledger structure can achieve security equivalent to that of Bitcoin, and at the same time due to the fast confirmation and high throughput of the blockDAG, the throughput is basically only limited by the physical characteristics of the network, maximizing the efficiency of network operation.
The MeerDAG hybrid consensus protocol used by Qitmeer integrates multiple advantages of GHOSTDAG and SPECTRE to guarantee the security and efficiency of the network and fast transaction confirmation.
It is one of the few high performance public chains that have pioneered the integration of blockDAG protocol. Here is a detailed introduction to the SPECTRE protocol of MEERDAG consensus mechanism.
1. SPECTRE Protocol of MEERDAG Consensus Mechanism
From the previous article “From Blockchain to DAG (II)-- The Past and Present Life of MEERDAG”, we know that the heaviest subtree principle (GHOST) improves chain security by taking the chain with the heaviest number of forked blocks as the main chain. Although the forked block is included in the block count, the transaction information contained in the block is all discarded, which actually causes a waste of node performance. In order to maximize the performance of the blockchain, blockDAG came into being, evolving the tree chain structure of GHOST into the form of a block graph. BlockDAG's blocks all point to all blocks in the previous level, and each forked block is packed with transaction information without being rounded off. Asynchronous accounting of block packaging nodes, different nodes can record different information at the same time. Therefore, the number of transactions that can be packaged per unit time is more, which improves the network concurrency capability. The SPECTRE protocol conforms to this structure, so it does not propose the concept of selecting the main chain, but focuses on resolving conflicting transactions and preventing malicious attacks. It needs to be stated here that there is a major premise for all discussion book consensus to be effective: most nodes in the network are honest.
The SPECTRE protocol is relatively complex, and will be described in the following four aspects, including how it outputs blocks, how it resolves conflicting transactions and generates trusted transaction sets, and how it prevents network attacks.
(1) SPECTRE—block output
In the SPECTRE protocol, when a block is generated, it points to the end blocks of all known forks.
In Picture 1 below, the left one describes the Bitcoin generating block, when there is a fork, the new block will choose to generate a new block based on one of them, while in SPECTRE, a new block will be generated based on all the blocks at the end of the fork. At the same time, when a new block is generated, the node should immediately send the new block (including the information based on which blocks are generated) to the nodes connected to itself.
The SPECTRE protocol strips miners of the requirement to maintain transactions that do not conflict
Bitcoin is like an authoritative ledger, as long as it is recorded in it, it must be true (regardless of forks and malicious attacks), while the DAG generated by SPECTRE is like an unauthoritative ledger, and the transaction information inside may conflict (The two “ number 1” blocks in Picture 1 above may contain conflicting transaction information).
Under this protocol, the mining nodes are only responsible for rapidly mining blocks (capable of reaching one block per second), and the conflicting transactions that may be included in the fork are not processed in the mining phase, maximizing the speed of recording transactions and giving a data structure like DAG a tradeoff ability to process transactions. The SPECTRE protocol data structure is shown in Picture 2.
(2) How SPECTRE resolves conflicting transactions
SPECTRE excludes conflicting transactions by inter block voting, as in Picture 3.
The transaction information recorded in block X is that transaction x occurred before transaction y, which is recorded as x<y; the transaction information recorded in block Y is that transaction y occurred before transaction x, which is recorded as y<x, the two transactions conflict with each other. Voting process:
block X and block Y vote for themselves respectively. The blocks generated after block X are called the future blocks of X. Looking back at these future blocks, we find that 6, 7, and 8 can only be traced back to X, so these three blocks all vote for X, marked in blue.
Similarly, when looking back at the future blocks of block Y, it is found that 9, 10, and 11 can only vote for Y, which is marked in red.
Future block 12 can be traced back to both X and Y, and it will cast the same result X as the previous round of voting.
The dotted line in the picture is the last round of voting. According to the principle of the minority obeying the majority, the result of the voting is X.
The blocks generated before X or Y are called the past blocks of X or Y. These blocks will respectively count the votes of their corresponding future blocks, and then vote for the option with more votes.
Thus, blocks 1 to 5 are all voted to X, the transaction x<y is considered valid, and y<x is discarded.
(3) SPECTRE—Generating trusted transaction sets
The SPECTRE trusted transaction sets (blue sets) is equivalent to the transaction set formed in the Bitcoin chain exceeding the current 6 blocks.
The blockchain is a ledger in terms of digital cryptocurrency. The currency owned by each account is obtained from the transaction information on the ledger. Therefore, it is very important to obtain definite and impossible-to-change transaction information, the SPECTRE trusted transaction set generation process is as follows:
Traversing blocks, extracting transaction information in sequence, and adding non-conflicting transactions to the non-conflicting transaction set.
Add conflicting transactions that result in insufficient account balances to the conflicting transaction sets.
According to the above voting algorithm, the conflicting transactions are voted in sequence to generate a sequence set of conflicting blocks and determine which transaction is valid.
Add transactions with valid votes to the non-conflicting transaction set.
In the non-conflicting transaction set, the transactions that exceed a certain period of time are formed into a trusted transaction set. That is, the transaction information of the transaction pool is basically impossible to be tampered with.
SPECTRE does not sort all blocks, and all blocks do not have a complete linear order, there are only block order pairs that determine the order of conflicting information.
The height in Bitcoin represents the linear order. The transaction information in the low-height block is prior to the information in the high-height block. The high-height block cannot contain transactions that conflict with the low-height block, However, SPECTRE has a large number of forks, and the height of the block cannot represent the linear order. The transaction information of the previous block does not necessarily precede the transaction information of the subsequent forked block. The validity of the transaction information is determined by the voting algorithm. The block voting algorithm is fast, and it includes all forked blocks, so there is no fork risk faced by Bitcoin (waiting for 6 blocks), and the transaction confirmation time can reach 10 seconds.
(4) Anti-"double spend" attack
Picture 4 shows an unsuccessful "double spend" attack, which is divided into three stages.
Source: Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar，《SPECTRE:Serialization of Proof-of-work Events: Confifirming Transactions viaRecursive Elections》
In the first stage, the attacker secretly prepares a block Y, which contains the transaction y<x. Then the attacker continues to secretly produce blocks 13 and 14. These newly produced blocks will definitely refer to the attack block, but some of them will also refer to the blocks of honest nodes, such as 13; the purpose is to "incite" these honest blocks to vote for Y in the subsequent voting process, such as honest block 4, at the end of the first stage, only 13, 14, and 4 of the future blocks of 4 will vote for Y.
But this kind of "incitement" is invalid in SPECTRE's voting rules, because there are always more honest nodes than evil nodes. Generally speaking, the efficiency of honest nodes producing blocks will be higher than that of evil nodes, so even in a short period of time, the "incitement" was successful, it can still be corrected in the follow-up process.
After the second phase begins, the normal transaction x<y is recorded in block X. The attacker's goal is to wait for x<y to be confirmed in the ledger by several blocks, and then exchange the tokens gained from this transaction for fiat currency or some kind of service for profit; and then release his attack block to make the entire ledger roll back and determine that the transaction x<y is invalid. After the rollback, the tokens that were originally transferred out for exchange return to their accounts and can be used repeatedly, i.e. "double spend" (the same money is spent twice).
But this attack will not succeed in SPECTRE voting. In the second stage, the attacker continues to secretly produce blocks 15, 16, and 17. Since honest nodes do not know these secret blocks, the blocks generated by honest nodes will not refer to them. In the third stage, the attacker continues to produce blocks and uploads all previously secretly produced blocks to the network in an attempt to legitimize his attack block and roll back the entire ledger.
At this time, the analysis of the picture shows that: Y's future blocks 13-19 can only be traced back to Y, so vote for Y. X's future blocks 6-10 can only be traced back to X, so vote for X. By counting the respective future blocks of X’s past blocks 1 to 4, it can be concluded that most of the future blocks voted for X, so they will also vote for X. It is here that the vote that block 4 was ""incited" in the first stage is corrected, because 9 of the 16 future blocks of 4 voted for X (block X plus blocks 5-12 ), more than 7 voted for Y (blocks 13-19), so 4 will eventually vote for X. Blocks 11 and 12 can be traced back to both X and Y, so they respectively cast the same results as the previous round of voting. According to the principle of the minority obeying the majority, the previous round of voting also has a majority of blocks voting for X, so 11 and 12 will eventually vote for X as well.
Combining the votes of all blocks, the vast majority voted for X, and the final ledger will record x<y and discard y<x, and the "double spend" attack did not work.
(5) Anti-censorship attack
Compared with the well-known "double spend" attack, censorship attack (censorship attack) is much stranger. Unlike the "double spend" attack, the attacker of censorship will continue to generate blocks but will not immediately publish these blocks in the network, see Picture 5.
Source: Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar, “SPECTRE:Serialization of Proof-of-work Events: Confifirming Transactions viaRecursive Elections”
At the current stage, the attacker continues to generate blocks 12 to 16, but these blocks are not associated with block X, they will neither refer to X nor trace back to X, this means that these blocks may be "incited" to vote for Y in the future. At some point in the future, the attacker uploads a block Y containing conflicting transactions, and all future blocks of Y will vote for Y, such as 17, 18.
The past block 16 that is not related to X will be “incited” to vote for Y at this time because most of the future blocks of 16 also voted for Y. Those blocks that are not related to X and have the possibility of "incitement" reduce the security of the network. When verifying transactions, honest miners will find that there are many blocks that are not related to X in the network, which will make the transaction of X The credibility is reduced, which may increase the time to confirm the transaction.
Because whether it is a blockchain or a DAG, new transactions need to refer to past transactions to complete verification (referencing previous blocks through the hash value recorded in the block header), and these past transactions must be trustworthy.
In SPECTRE's voting rules, even in the face of censorship attacks, transactions can be confirmed immediately. 16 to 18 all voted for Y. Blocks 2 to 9 are blocks that can only be traced back to X, so they vote for X. Blocks 1, 12-15 all vote for X, because the votes for the future blocks to which they belong are counted separately, and the votes for X account for the majority. Blocks 10 and 11 can be traced back to both X and Y. According to the result of the last vote, they will vote for X according to the majority principle. In the end, more blocks are voted for X, and the attack fails.
(6) Application and Deficiency of SPECTRE Protocol
From the above analysis, it can be seen that SPECTRE can well eliminate conflicting transactions and resist attacks; at the same time, it can quickly confirm transactions. In general networks, in order to ensure that most nodes can spread throughout the entire network within this delay, the delay time needs to be as large as possible. The calculation of the confirmation time is based on the delay time, so the confirmation time will increase accordingly.
The confirmation speed of SPECTRE only depends on the propagation delay of the node itself, and it can approach the limit value of the confirmation speed as much as possible, only limited by the bandwidth and propagation delay, so as to give full play to the network performance.
SPECTRE is naturally a ledger consensus for simple payment transactions in Islamic finance,
but if you want to integrate smart contract functionality, SPECTRE is not up to the task because it can only do a relative ordering of conflicting transactions (to judge the order of conflicting transactions), cannot do an absolute ordering of all blocks. Therefore, in order to give full play to the performance of the SPECTRE protocol, we abstract the idea of the full sequence of the SPECTRE protocol as part of the MeerDAG consensus, and drive the pluggable virtual machine (MeerEVM) container to realize the expansion of other public chain ecology. This is because when the Qitmeer Team established the project, it considered that the direction of network application was oriented towards Islamic finance, which required the underlying network of BlockDAG to become an efficient and secure value flow layer.
But for BlockDAG that allows forks, sequential can only be achieved through ledger consensus. SPECTRE cannot be used for smart contracts precisely because it is not sequential, but the block reward mechanism requires linear sorting capabilities, so Qitmeer Team introduced the sequential ledger consensus GHOSTDAG based on SPECTRE. The GHOSTDAG protocol of the MEERDAG consensus mechanism will be explained in next articles.
[1] GHOST, DAG, SPECTRE, PHANTOM and CONFLUX technical theory: ，https://www.jianshu.com/p/8734e06d558f
[2] Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar，SPECTRE:
Serialization of Proof-of-work Events: Confifirming Transactions via
Recursive Elections
[3] The magical use of DAG (3) - the extension of the Bitcoin protocol: https://mp.weixin.qq.com/s/KeQDVQMJLQlyXQcywfE8sQ
[4] Simple and easy-to-understand blockchain expansion solution - BlockBeats ((https://www.theblockbeats.info/tw/news/31571))
