Classification of Analytic Consensus Algorithms (Part 1)
—— Classification of Part1 Consensus ——
From the slow development of the early distributed consensus algorithm to the flourishing of blockchain consensus today, the development of consensus algorithm has gone through about forty years. Different consensus algorithms have different emphases, so the problems and environments they face are also different. This article will classify consensus algorithms from the following different perspectives:
▲Fault tolerance type
According to whether Byzantine errors are tolerated, consensus algorithms can be divided into two categories.
1) Byzantine fault-tolerant consensus algorithms: PBFT, PoW, PoS, DPoS
2) Non-Byzantine fault-tolerant consensus algorithms: Paxos, Raft
Whether to tolerate Byzantium marks whether the algorithm can be applied to low-trust networks. Generally speaking, the Byzantine fault-tolerant algorithm must be used in the public chain environment, while in the alliance chain, it can be selected according to the degree of trust between the alliance participants.
▲ Algorithm determinism
According to the certainty of the algorithm, the consensus algorithm can be divided into two categories.
1) Deterministic consensus algorithms: Paxos, Raft, PBFT
2) Probabilistic consensus algorithm: PoW, partial PoS
Deterministic consensus means that once the consensus decision is reached, there is no possibility of rollback. This category is usually the traditional distributed consensus algorithm and its improved version. Probabilistic means that the consensus decision that has been reached will be rolled back with a certain probability in the future. Although this probability will tend to be 0 over time, this type of blockchain is usually applied to the public chain. consensus algorithm.
▲The main selection strategy
According to the strategy of selecting the leader, consensus algorithms can be divided into two categories.
1) Election consensus algorithms: Raft, PBFT
2) Proof consensus algorithms: PoW, PoS
Election-type consensus refers to the selection of block-producing nodes by voting. The same node can exist as a block-producing node for multiple consecutive rounds. This category is usually the traditional distributed consensus algorithm and its improved version. The proof-type consensus algorithm means that the block-producing nodes need to prove that they have a certain ability in a certain way, so as to obtain the right to produce blocks. This type of consensus algorithm usually has different block-producing nodes in each round, thus ensuring The fairness of block rights is usually applied to public chains.
—— Part2 Non-Byzantine Fault Tolerant Consensus Algorithm——
Paxos
Paxos is the first consensus algorithm that can guarantee correctness and fault tolerance under the asynchronous network model. Prior to this, FLP explicitly pointed out that in an asynchronous network model, as long as there are node failures, it is impossible to have a consensus algorithm that can be terminated. Therefore, Paxos also made a certain sacrifice: Paxos sacrificed a certain amount of activity to ensure the security of the system, that is, when the system is in an asynchronous state, the advancement of the consensus is suspended, and as long as more than half of the nodes return to the synchronous state, they can Promote consensus and complete termination.
image description
Figure 1. Basic Paxos consensus process
text
Raft
Paxos is indeed a very influential consensus algorithm, which can be said to have laid the foundation for distributed consensus algorithms. However, due to its difficulty in understanding and implementation, it is very difficult to implement a complete Paxos algorithm. Therefore, there have been many Paxos variants, the most famous of which is the Raft consensus algorithm.
Raft is a consensus algorithm for managing log replication, designed to be easy to understand. It has the fault tolerance and performance of Paxos, the difference is that it decomposes the consistency problem into three relatively independent sub-problems, namely leader election (leader election), log replication (log replication) and security (safety). This makes Raft better understood and easier to apply to the establishment of actual systems.
In Raft, each node must be in one of the following three states: Leader (master node), Candidate (candidate node), Follower (slave node). Under normal circumstances, only one node is the Leader, and the remaining nodes are Followers. The Leader is responsible for processing all requests from the client (if a client communicates with the Follower, the Follower will forward the information to the Leader), generates log data (corresponding to packaging in the blockchain) and broadcasts it to the Follower node. Followers are passive: they will not actively send any requests, and can only receive log data from the Leader in one direction. Candidate is a transitional state that occurs during the process of electing the next Leader. Any node can become a Candidate and become a Leader after discovering the failure of the primary node.
The Raft algorithm divides time into terms (terms) of any length. Terms of office are represented by consecutive numbers. Every term begins with an election. If a candidate wins the election, it serves as leader for the remainder of the term. In some cases, the votes will be divided, and it is possible that no leader will be elected, then another term will start, and the next election will begin immediately.
image description
text
Summarize
Both Paxos and Raft are Crash Fault Tolerance consensus, which is a non-Byzantine fault-tolerant technology. Non-Byzantine means that there is a crash fault in the distributed system, but there is no malicious (corrupt) node scenario (that is, the message may be lost or repeated, but there is no error message), and it is a distributed consensus field. Most common question. Compared with Paxos, Raft is more concise, while ensuring the same fault tolerance and performance.
text
PoW
Proof of Work (PoW) was first mentioned in an academic paper [3] by Cynthia Dwork and Moni Naor in 1993, and the concept of "Proof of Work" was formally proposed by Markus Jakobsson and Ari Juels in the same year[ 4]. At first, PoW was mainly used to prevent spam. In 2008, PoW was applied to the Bitcoin system as a consensus algorithm. PoW has the following three basic attributes:
1) Mathematical puzzle: The PoW consensus algorithm designs a mathematical puzzle (Mathematical Puzzle), which requires nodes to consume certain computing resources to obtain a solution to the puzzle before generating a new block, thereby broadcasting the block to the network, and other nodes can It is easy to verify the validity of this solution.
2) Hash algorithm: Hash algorithm (Hash Algorithm) is an algorithm that can transform an input of any length into a fixed-length output, which can be recorded as y = hash(x), and the output y obtained by different input x vary. In addition, y can be quickly calculated when x is known, but in the case of known y, x can only be inversely deduced by exhaustive methods. Because the hash algorithm has the characteristics of fast forward and difficult reverse, the hash algorithm is often used to design the mathematical problems of PoW.
3) Block generation: In a round of block generation, the system adjusts the difficulty value of the mathematical problem by setting conditions on the output value. After the node successfully solves the problem and passes the verification on the chain, it will receive corresponding rewards.
Before generating a new block, PoW will preset the target value, and require the hash value calculated by the block producing node to be less than the target value to represent the difficulty of PoW. In order to generate blocks and get rewards, block producers first collect a set of transactions and pack them into a block, and start trying to solve mathematical problems to produce blocks.
During this period, the block producing node needs to generate random numbers, perform multiple rounds of hash operations with the current block data and the hash of the previous block, and calculate the hash value of the current block:
Until the current block hash meets the conditions:
image description
text
PoS
The aforementioned proof-of-work consensus algorithm uses computing power to compete for the qualification of the "leader". However, a large amount of resources are wasted in the process of proof-of-work, which makes it difficult to be accepted by larger-scale applications. In this regard, some people began to try to directly use "Stake" as the standard for the election of "Leader" qualifications, and subsequently produced the Proof of Stake (PoS) consensus algorithm.
The idea of PoS comes from society: the more shares a person owns, the higher the dividends and dividends he will receive. If the blockchain system is also maintained in this way, it does not require excessive resource consumption, and it can also cause natural inflation of blockchain assets. Nodes participate in the consensus by investing a certain amount of tokens, and obtain the right to package new blocks and receive rewards according to the token holdings. Currently, Ethereum also has an Ethereum 2.0 plan to switch to PoS.
In order to describe the status of token holdings, the PoS consensus algorithm introduces the concept of "coin age". Coin-age indicates how long a node holds a part of the pass. When the node invests the pass as a "share", this part of the pass begins to accumulate the coin-age. The calculation method of the coin-age is as follows:
After using this part of the pass, whether it is used for block generation or simple transactions, the currency age corresponding to this part of the pass will be destroyed. In the original PoS consensus algorithm, coin age is an important criterion for judging. The higher the coin age used by nodes when generating blocks, the easier it is to generate blocks, which can restrict short-term speculation to a certain extent.
When the PoS consensus algorithm generates blocks, it will take into account both the coin age and the difficulty of hash operations, so that nodes only need to consume very little computing resources to complete block generation.
DPoS
In the Delegated Proof of Stake (DPoS) consensus algorithm [5], electors elect representatives, who directly generate blocks, and electors indirectly exercise the right to compete for blocks through electing representatives. The delegated proof-of-stake consensus algorithm actually restricts candidates through a series of selection rules and formulates a set of voting rules. Ordinary participants select delegators from candidates through voting, and delegators will produce blocks. Delegators who do not meet the requirements will be revoked and new delegators will be re-elected.
DPoS retains certain centralization features, so it can guarantee high-efficiency transaction throughput, and the speed can be compared with common centralized institutions, such as Visa, Mastercard, etc. In this algorithm, the characteristic of decentralization is mainly reflected in the controllability of the right to generate blocks. That is, shareholders vote to select their trusted representative nodes, and the representative nodes maintain the blockchain data.
——Part4 Summary——
The consensus algorithms mentioned above are mostly used in public chain scenarios, such as Bitcoin, Ethereum, etc. Due to the large scale of nodes in public chain scenarios, it is difficult to adopt a deterministic distributed consensus algorithm. PoW achieves higher security and decentralization through proof of work. Compared with PoW, PoS sacrifices a certain amount of security to reduce energy consumption, while DPoS uses a more radical way to elect less nodes to improve consensus efficiency.
About the Author
About the Author
references
Consensus Algorithm Research Group of the Basic Platform Department of FunChain Technology
references
[1]Lamport L. Paxos made simple[J]. ACM Sigact News, 2001, 32(4): 18-25.
[2] Chandra T D, Griesemer R, Redstone J. Paxos made live: an engineering perspective[C]//Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. 2007: 398-407.
[3] Dwork C, Naor M. Pricing via processing or combatting junk mail[C]//Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1992: 139-147.
[4] Jakobsson M, Juels A. Proofs of work and bread pudding protocols[M]//Secure Information Networks. Springer, Boston, MA, 1999: 258-272.
[5]Delegated Proof of Stakehttps://github.com/dacplayproject/cpp-play/wiki/Delegated-Proof-of-Stake
