1. Proof of Work (PoW)
Bitcoin (Bitcoin) proposed by Satoshi Nakamoto in 2009 is the earliest application of blockchain technology. It uses PoW as the consensus algorithm. The core idea is to obtain accounting rights and Bitcoin rewards through computing power competition among nodes. . In PoW, different nodes compete to calculate solutions to mathematical problems based on specific information. This math problem is difficult to solve, but the results are easy to verify. The node that solves the math problem first can create the next block and receive a certain amount. Coin rewards. Satoshi Nakamoto designed this mathematical problem in Bitcoin using the [4] mechanism. This section will explain the PoW algorithm used by Bitcoin as an example. The consensus steps of PoW are as follows:
After the last block is generated, the node collects the transactions to be confirmed across the entire network, records the eligible transactions into the transaction memory pool, and then updates and calculates the root value of the transactions in the memory pool and writes it into the block header;
Fill in the block version number, hash value of the previous block, timestamp, current target hash value, random number and other information in the block header, as shown in Table 1.1;
Table 1.1 Block header information
The random number nonce takes a value between 0 and 232, and the block header information is hashed. When the hash value is less than or equal to the target value, the block is packaged and broadcast, and accounting is completed after verification by other nodes;
If a hash value that meets the requirements cannot be calculated within a certain period of time, repeat step 2. If other nodes complete the calculation during the calculation process, restart from step 1.
The average time it takes for Bitcoin to generate a block is 10 minutes. If you want to maintain this speed, you need to adjust the target value (difficulty) based on the current computing power of the entire network [5]. Difficulty is a description of how difficult it is to calculate a block that meets the requirements. When calculating blocks of the same height, the difficulty of all nodes is the same, which also ensures the fairness of mining. The relationship between difficulty and target value is:
Difficulty value = maximum target value/current target value (1.1)
The length of the maximum target value and the current target value are both 256 bits. The maximum target value is the target value when the difficulty is 1, which is 2224.Assume that the current difficulty is, the computing power is, the current target value is, and the average calculation time to discover a new block is, then
According to the design of Bitcoin, the system adjusts the current target value every 2016 blocks (approximately 2 weeks). The node calculates the adjusted difficulty value according to formula (1.4) based on the actual block production time of the first 2016 blocks. If the actual production time is less than 2 weeks, increase the difficulty value; if the actual production time is greater than 2 weeks, decrease the difficulty value. value. According to the longest chain principle, there is no need for nodes to synchronize difficulty information, and all nodes will obtain the same difficulty value after a certain period of time.
In a blockchain using PoW, a fork may occur when two blocks of the same height are generated close to each other due to network delays and other reasons. That is, different miners calculate blocks that meet certain height requirements and are confirmed by nodes closer to them. Nodes in the entire network will continue mining according to the block received first based on the time when the block is received. . In this case, whichever block's subsequent blocks appear first will become longer, and this block will be included in the main chain. Nodes mining on non-main chain will switch to the main chain to continue mining. .
The PoW consensus algorithm uses computing power as the basis for competing for accounting rights, and workload as a guarantee of security. All miners follow the longest chain principle. The newly generated block contains the hash of the previous block. All existing blocks form a chain. The length of the chain is proportional to the amount of work. All nodes trust the longest blockchain. If an organization acquires enough computing power, it can launch an attack on the Bitcoin network. When an attacker has enough computing power, he can calculate the latest block first, thereby mastering the longest chain. At this time, most of the blocks on the Bitcoin main chain are generated by it. He can deliberately refuse to confirm certain transactions and perform double-spend attacks. This affects the trustworthiness of the Bitcoin network, but this behavior can also cause losses to attackers. By solving the one-dimensional random walk problem, the relationship between the probability of successful attack by malicious nodes and computing power can be obtained:
Figure 1.1 Attacker’s computing power and attack success probability
2. Proof of Stake (PoS)
As more and more people participate in Bitcoin mining, many problems with PoW have gradually emerged. For example, as the competition for computing power rapidly intensifies, the energy consumed to obtain tokens increases significantly, and accounting rights gradually accumulate a large amount of computing power. Power “pools” are concentrated [6-9]. To this end, researchers are trying to use new mechanisms to replace proof of work. The concept of PoS was mentioned in the earliest Bitcoin project, but it was not used due to reasons such as robustness. The earliest application of PoS is (). PoS proposed the concept of the currency era. Coin age is the accumulation of the product of holding tokens and holding time. The calculation is shown in equation (1.4). The competition in the currency era replaces the competition in computing power, so that blockchain proof no longer relies solely on workload, effectively solving the resource waste problem of PoW.
Holding time refers to the time since a currency was last traded on the network. The longer the coins held by each node, the more rights it has in the network. At the same time, holders of the currency will also be ranked according to currency age. obtain certain benefits. In the design of Peercoin, it does not completely break away from proof of work. Obtaining the accounting rights of the PoS mechanism also requires simple hash calculation:
where is the hash value obtained by the fuzzy sum of the weight factor, the unconsumed output value and the current time. At the same time, the computing power of each node is limited. It can be seen that currency age is inversely proportional to calculation difficulty. In PoS, the security of the blockchain increases as the value of the blockchain increases. Attacks on the blockchain require attackers to accumulate a large amount of currency age, which means they need to hold a large amount of digital currency for a long enough period of time. This also greatly increases the difficulty of the attack. Compared with PoW, blockchain systems using PoS may face long-range attacks (Long Range) and disinterested attacks (at Stake).
In addition, many coins also use PoS, but the methods of allocating accounting rights are different. For example, Future Coin (Nxt) and Black Coin (Nxt) combine the rights owned by nodes and use random algorithms to allocate accounting rights. Ethereum is also gradually adopting PoS instead of PoW.
3. Delegated Proof of Stake (DPoS)
When Bitcoin was designed, it was hoped that all mining participants would use CPUs for calculations, and that the computing power would match that of the nodes. Each node has ample opportunity to participate in the decision-making of the blockchain. With the development of technology, a large number of mining machines using GPU, FPGA, ASIC and other technologies have emerged. The computing power is concentrated in the hands of participants with a large number of mining machines, while the opportunities for ordinary miners to participate are greatly reduced.
In a blockchain using DPoS, each node can vote for representatives based on the stake they own. The n nodes that participate in the election and receive the most votes in the entire network obtain accounting rights and generate blocks in a predetermined order. and thus obtain certain rewards. Successfully elected representative nodes need to pay a certain deposit and must ensure online time. If the node that is supposed to generate a block at a certain moment fails to perform its duties, he will be disqualified as a representative and the system will continue to vote for new representatives. to replace him.
All nodes in DPoS can independently select voting objects, and the elected representatives are accounted for in order, which saves computing resources compared to PoW and PoS. Moreover, the number of consensus nodes is limited, and the efficiency has also been improved. Moreover, every participating node has voting rights. When there are enough nodes in the network, the security and decentralization of DPoS are also guaranteed.
4. Practical Byzantine Fault Tolerance Algorithm (PBFT)
In the PBFT algorithm, all nodes run under the same configuration and have a master node and other nodes as backup nodes. The primary node is responsible for sorting client requests and sending them to the backup node in order. There is the concept of View, and in each view, all nodes process messages normally. But when the backup node detects an abnormality in the primary node, it will trigger the view change (View) mechanism, replace the next numbered node as the primary node, and enter a new view. In PBFT, the main process from the client sending a request to receiving a reply is shown in Figure 4.1[10][11]. Information is exchanged between servers three times. The entire process includes the following five stages:
Figure 4.1 PBFT execution process
Currently, Byzantine fault-tolerant algorithms represented by PBFT are used by many blockchain projects. In the alliance chain, the PBFT algorithm was first adopted by the Hyper project. Version 0.6 adopts the PBFT consensus algorithm and integrates authorization and endorsement functions into the consensus node. All nodes are consensus nodes. This design results in excessive node burden and has a great impact on TPS and scalability. . Versions after 1.0 have separated the functions of nodes. Nodes are divided into three endorsement nodes (), ordering nodes () and block nodes (). The functional separation of nodes improves the efficiency of consensus to a certain extent. .
The [12] algorithm used by the project combines the PBFT and PoS algorithms, and selects some consensus nodes for BFT consensus through token mortgage. It weakens the asynchronous assumption on the basis of PBFT and incorporates the concept of lock. Consensus nodes in a partially synchronized network can reach consensus through two-phase communication. The system can tolerate 1/3 of failed nodes without causing a fork. Based on [13], the blockchain structure of the blockchain is integrated into each stage of BFT. In each stage, the signature confirmation of the previous block and the construction of the new block are carried out simultaneously, making the execution of the algorithm more efficient. For simplicity, threshold signatures [14] are also used to reduce the message complexity of the algorithm.
5.Paxos and Raft
The consensus algorithm is a set of mechanisms designed to ensure the accuracy and consistency of stored information. In traditional distributed systems, the most commonly used consensus algorithm is the Paxos-based algorithm. After the Byzantine Generals Problem [3] was proposed, the Paxos algorithm was proposed in 1990 to solve the system consistency problem under specific conditions. In 1998, the Paxos paper [15] was reorganized and published, and in 2001 Paxos was briefly explained [16]. Subsequently, Paxos dominated the field of consensus algorithms and was adopted by many companies, such as Tencent, Alibaba’s X-Paxos, Amazon’s AWS, and Google [17]. This type of algorithm can quickly complete data synchronization in a distributed system when the number of nodes is limited and relatively trustworthy, while being able to tolerate crash failures. In other words, in a traditional distributed system, there is no need to consider the malicious tampering of data by participating nodes, and only need to be able to tolerate downtime errors on some nodes. However, the Paxos algorithm is too theoretical and is very difficult to understand and implement in engineering. et al. In 2013, he published a paper proposing the Raft algorithm [18]. Raft has the same effect as Paxos and is more convenient for engineering implementation.
The leader occupies an absolute dominant position in Raft and must ensure the absolute security of server nodes. Once a leader is maliciously controlled, huge losses will be caused. And the transaction volume is limited by the maximum throughput of the node. Currently, many alliance chains use the Raft algorithm to improve consensus efficiency without considering the issue of Byzantine fault tolerance.
6. Consensus algorithm combined with VRF
In the existing alliance chain consensus algorithm, if the number of nodes participating in the consensus increases, the communication between nodes will also increase, and the performance of the system will also be affected. If some nodes are selected from many candidate nodes to form a consensus group for consensus and the number of consensus nodes is reduced, the performance of the system can be improved. But this will reduce security. The higher the proportion of malicious nodes among candidate nodes, the greater the probability that the selected consensus group will not function properly. In order to select a consensus group that can operate normally from the candidate nodes and ensure the high availability of the system, on the one hand, it is necessary to design a suitable random election algorithm to ensure the randomness of the selection and prevent malicious nodes from attacking the system. On the other hand, it is necessary to increase the proportion of honest nodes among candidate nodes and increase the probability of honest nodes being selected into the consensus group.
Currently, public blockchains are usually based on the PoS algorithm. Staking tokens increases the entry barrier for consensus nodes and increases the cost of malicious nodes through economic games. Then, among some of the nodes that pass the screening, a random election algorithm is used to select qualified nodes. Randomly select some nodes among the candidate nodes for consensus.
Dodis et al. Verifiable random functions (VRF) were proposed in 1999 [19]. Verifiable random functions are an application of zero-knowledge proof, that is, in a public-private key system, the person holding the private key can generate random numbers according to specific rules without using the private key and a piece of known information. Disclosure of private keys. Under the premise, the person holding the private key can prove to others the correctness of the random number generation. VRFs can be constructed using RSA or elliptic curves. In 2002, Dodis et al. proposed a verifiable random function construction method based on difficulty problems [20]. Currently, verifiable random functions are used in both the key transmission field and the blockchain field. with applications [21]. The specific process of verifiable random function is as follows:
In public chains, VRF has been applied in some projects. VRF is mostly combined with PoS algorithm. All nodes that want to participate in the consensus pledge a certain number of tokens to become candidate nodes, and then randomly select some from many candidate nodes through VRF. Consensus node. New nodes in the network must first perform PoW, and existing nodes in the network verify the new node's PoW and authorize it to join the network. The consensus algorithm VBFT designed by the blockchain project combines VRF, PoS and BFT algorithms. VRF randomly selects consensus nodes among many candidate nodes and determines the order of consensus nodes, which can reduce the impact of malicious forks on the blockchain system. Impact ensures the fairness and randomness of the algorithm. The Turing Award winner and others proposed [22] to combine PoS and VRF. Nodes can become candidate nodes by staking tokens, and then use the non-interactive VRF algorithm to select some nodes to form a consensus committee. These nodes will then implement a consensus algorithm similar to PBFT and be responsible for the rapid verification of transactions. When the nodes are honest nodes, they can Ensure the normal operation of the system. In the second version proposed by Praos [24] et al. [23], introduced VRF to replace pseudo-random numbers to select the master node in a shard. Taking the VRF algorithm used by the equal algorithm as an example, the main process is as follows:
In VRFs designed and used by public chains, the probability of a node being selected as an accounting node is often positively related to the tokens it holds. The consensus node range of the public chain cannot be determined in advance. All nodes that meet the currency holding conditions may become consensus nodes. The system needs to select some nodes from a random number of participating nodes for consensus. Compared with the public chain, the number of nodes participating in the consensus of the alliance chain is limited, and the nodes are known. In this case, the nodes of the alliance chain can interact through the known node list, which can effectively prevent problems that may arise during the design of the public chain VRF. Witch attack problem.
7. Formula algorithm combined with sharding technology
Sharding technology is a technology in databases that divides data in the database into multiple parts and then stores them in multiple servers. Improve the search performance of the server through distributed storage of data. In blockchain, sharding technology is a mechanism that distributes transactions to multiple consensus groups composed of subsets of nodes for confirmation, and finally aggregates all results for confirmation. Sharding technology has already had some applications in blockchain, and many blockchains have designed their own sharding solutions.
Lu et al. A protocol was proposed in 2017, which was the first to apply sharding technology to the blockchain [25]. First, compete to become the accounting node in the network through the PoW algorithm. These nodes are then assigned to different shard committees based on predetermined rules. Each sharding committee internally executes traditional Byzantine fault-tolerant consensus algorithms such as PBFT and packages them to generate transaction sets. When multiple nodes sign the transaction set, the transaction set is submitted to the consensus committee. After the consensus committee verifies the signature, all transaction sets are finally packaged into blocks and recorded on the blockchain.
The usability of sharding technology in blockchain is verified. Within a certain scale, sharding technology can scale throughput nearly linearly. However, using PoW to elect consensus nodes also causes the random number generation process and PoW competition for consensus nodes to take too long, resulting in high transaction delays. In addition, the PBFT algorithm used within each shard has high communication complexity. Latency can also be high when the number of nodes in a single shard is high.
Based on,-et al. proposed [26] to use a cryptographic lottery protocol instead of PoW to select the group of validators, and then classify the validators into different shards through the protocol [27]. . In sharding, the PBFT-based consensus algorithm is still used as the consensus algorithm in sharding [28], and a protocol is introduced to handle cross-shard transactions. The communication complexity between nodes during the consensus process is relatively high. When the number of nodes within a shard increases and the volume of cross-shard transactions increases, system TPS will drop significantly.
Proposed by Wang et al. 2019[29]. Introducing sharding technology into the PoW blockchain system and proposing the Chu ko-nu mining algorithm solves the problem of computing power dispersion caused by sharding and allows each miner to work on different shards at the same time. Sharding improves the TPS of PoW without reducing security.
![Lawyers' Interpretation｜Illustration Of Key Contents Of The "E-Commerce Law"](http://www.ethospool.com/zb_users/theme/suiranx_light/image/random_img/5.jpg "Lawyers' Interpretation｜Illustration Of Key Contents Of The "E-Commerce Law"")
评论列表