WO2023016426A1

WO2023016426A1 - Asynchronous binary agreement method and apparatus, and electronic device and storage medium

Info

Publication number: WO2023016426A1
Application number: PCT/CN2022/110993
Authority: WO
Inventors: 段斯斯; 张海滨
Original assignee: 清华大学; 山东区块链研究院
Priority date: 2021-08-12
Filing date: 2022-08-09
Publication date: 2023-02-16
Also published as: CN113810465A; CN113810465B

Abstract

Provided in the embodiments of the present application are an asynchronous binary agreement method and apparatus, and an electronic device and a storage medium, which are applied to any agreement node in a distributed system. The distributed system comprises at least N agreement nodes, wherein N ≥ 3f + 1, with f being an integer greater than 0. The method comprises: for a proposal, to be agreed, of any agreement node, determining an initial voting value corresponding to said proposal, and an initial auxiliary value, wherein a voting value comprises a first voting value and a second voting value, and the initial voting value is the first voting value or the second voting value; and cyclically executing agreement steps of each round until an agreement result for said proposal is obtained, wherein the agreement steps of each round comprise: broadcasting an agreement message of the current round, wherein the agreement message carries a voting value and an auxiliary value of the current round, and on the basis of received voting values and auxiliary values, which are broadcast by other agreement nodes, determining whether the agreement result is obtained.

Description

A kind of asynchronous binary consensus method, device, electronic equipment and storage medium

Cross References to Related Applications

This application is based on a Chinese patent application with application number 202110925730.2 and a filing date of August 12, 2021, and claims the priority of this Chinese patent application. The entire content of this Chinese patent application is hereby incorporated by reference into this application.

technical field

The present application relates to the field of computer technology, in particular to an asynchronous binary consensus method, device, electronic equipment and storage medium.

Background technique

Binary consensus is the main component of Byzantine Fault Tolerant Protocol (Byzantine Consensus, BFT). Currently known asynchronous Byzantine consensus protocols rely directly or indirectly on binary consensus, which enables distributed systems to reach consensus in an asynchronous environment. At the same time, binary consensus can also be used to construct state machine replication, and then use state machine replication to establish a foundation for distributed fault-tolerant systems. In addition, binary consensus can also be applied to technical fields such as databases. Therefore, the research on binary consensus is an important research direction in the industry at present.

Contents of the invention

The embodiment of the present application provides an asynchronous binary consensus method, device, electronic equipment and storage medium, which are used to solve the problem of low consensus efficiency in the prior art.

In order to achieve the above object, the application provides the following technical solutions:

According to the first aspect of the embodiments of the present application, an asynchronous binary consensus method is provided, which is applied to any consensus node in a distributed system, and the distributed system includes at least N consensus nodes, where N≥3f+ 1. The f is an integer greater than 0, and the method includes:

For the consensus proposal of any consensus node, determine the initial voting value corresponding to the consensus proposal, and the initial auxiliary value; wherein, the voting value includes the first voting value and the second voting value, and the auxiliary value includes the first voting value, The second voting value and empty, the initial voting value is the first voting value or the second voting value;

Each round of consensus steps is cyclically executed until the consensus result for the proposal to be consensus is obtained, wherein each round of consensus steps includes:

Carry the voting value and auxiliary value in the first type of consensus message for broadcast;

Receive the first type of consensus messages broadcast by other consensus nodes;

Re-determine the voting value and auxiliary value based on the received first type of consensus message, and broadcast the re-determined voting value and auxiliary value in the second type of consensus message;

After receiving the quorum of the second type of consensus messages, the public coin toss value of the current round of consensus is obtained, and based on the public coin toss value and the received second type of consensus messages, the consensus result or the first type of consensus in the next round of consensus is determined The voting value and auxiliary value carried by the message.

In the above solution, before re-determining the voting value and the auxiliary value based on the received first type of consensus message, it also includes:

If f+1 first-type consensus messages are received in the current consensus round, and the voting value in the f+1 first-type consensus messages is the same as the voting value broadcast by the local consensus in this round through the first-type consensus message If not, modify the local voting value to the voting value in the f+1 first-type consensus messages, and broadcast the first-type consensus message carrying the voting value and auxiliary value again.

In the above solution, the re-determining the voting value and the auxiliary value based on the received first type of consensus message includes:

After receiving a quorum of first-type consensus messages, if the quorum of first-type consensus messages carry the same voting value, add the voting value to the first set;

If the current consensus round is the first round, the voting value and the auxiliary value are re-determined as voting values in the first set.

In the above scheme, the method also includes:

If the current consensus round is not the first round, the voting value in the first set is compared with the public coin toss value of the previous round, and the voting value and auxiliary value are re-determined according to the comparison result and the first type of consensus message received.

In the above solution, the re-determining the voting value and the auxiliary value according to the comparison result and the received first type of consensus message includes:

In the case where the voting value in the first set is equal to the public coin toss value of the previous round, if the voting values carried in the received first type of consensus messages are all voting values in the first set, the auxiliary value carried are all voting values in the first set or empty, then determine the voting value and auxiliary value as the voting value in the first set; otherwise, determine the voting value as empty, and determine the auxiliary value as the first set Voting value in .

In the above scheme, the method also includes:

In the case that the voting value in the first set is not equal to the public coin toss value of the previous round, if the voting value and the auxiliary value carried in the received first type of consensus message are both voting values in the first set, Then determine the voting value and the auxiliary value as the voting value in the first set; otherwise, determine the voting value as empty, and determine the auxiliary value as the voting value in the first set.

In the above scheme, the determination of the consensus result or the voting value and auxiliary value carried by the first type of consensus message in the next round of consensus based on the public coin toss value and the received second type of consensus message includes:

Add the voting value in the received second type of consensus message to the second set, if there are more than the quorum of the second type of consensus messages received in the second type of consensus message are the same, and the second type of consensus message If the voting value in the consensus message is the same as the auxiliary value, the voting value in the second type of consensus message is compared with the current round of public coin toss value, if the voting value is the same as the current round of public coin toss value, the target consensus node determines the consensus result for that vote value;

If they are different, the voting value and the auxiliary value carried in the first type of consensus message in the next round are both determined as the voting value in the second type of consensus message.

In the above scheme, the method also includes:

If only legitimate second-type consensus messages have been received, the voting value in the second set is a voting value and empty, and there are at least a quorum of second-type consensus messages with auxiliary values of this kind of voting value, then Compare this voting value with the public coin toss value of the previous round of consensus and the public coin toss value of the current round of consensus;

If this kind of voting value is the same as the public coin toss value of the previous round of consensus and the public coin toss value of this round of consensus, then it is determined that the consensus result should be this kind of voting value; and/or the coin toss value of the current round of consensus is different, then the voting value and auxiliary value in the first type of consensus message in the next round are set to this kind of voting value.

In the above scheme, the method also includes:

If a quorum of legitimate second-type consensus messages is received, the auxiliary values carried by the quorum of second-type consensus messages are not all the same, the voting value in the second set is a voting value and empty, and the If the voting value is the same as the public coin toss value of the previous round of consensus, the voting value and auxiliary value in the first type of consensus message in the next round of consensus will be set as this kind of voting value.

In the above scheme, the method also includes:

If the received second consensus message includes two voting values; or, the quorum of legal second consensus messages received by the target node carry different auxiliary values, the voting value in the second set is a voting value and empty, and this type of voting value is different from the previous round of public coin toss; the public coin toss value of this round of consensus will be used as the voting value of the next round of the first type of consensus message; if the current round of consensus is the first round, the next round of consensus will be The auxiliary value in the first type of consensus message of a round is set as the public coin toss value of this round; if the current round of consensus is not the first round, the auxiliary value in the first consensus message of the next round is determined as the occurrence in the second set The number of times exceeds the value of the preset number of times.

According to the second aspect of the embodiments of the present application, an asynchronous binary consensus device is provided, the device is applied to any consensus node in a distributed system, and the distributed system includes at least N consensus nodes, where N≥3f+1, the f is an integer greater than 0, and the device includes:

The processing module is used to determine the initial voting value corresponding to the consensus proposal for any consensus node, and the initial auxiliary value; wherein, the voting value includes the first voting value and the second voting value, and the auxiliary value includes The first voting value, the second voting value and empty, the initial voting value is the first voting value or the second voting value; execute each round of consensus steps in a loop until the consensus result for the proposal to be consensus is obtained;

In each round of consensus:

The communication module is used to broadcast the voting value and auxiliary value in the first type of consensus message; receive the first type of consensus message broadcast by other consensus nodes; re-determine the voting value and auxiliary value based on the received first type of consensus message , and broadcast the re-determined voting value and auxiliary value in the second type of consensus message;

The processing module is also used to obtain the public coin toss value of the current round of consensus after receiving the quorum of the second type of consensus message, and determine the consensus result or the next The voting value and auxiliary value carried by the first type of consensus message in a round of consensus.

In the above scheme, the processing module is further configured to re-determine the voting value and the auxiliary value based on the received first-type consensus message, if f+1 first-type consensus messages are received in the current consensus round, and the If the voting value in the f+1 first-type consensus messages is the same as that of the local current round of consensus broadcast through the first-type consensus message, the local voting value is changed to the f+1 first-type consensus The voting value in the message; the communication module is also used to rebroadcast the first type of consensus message carrying the voting value and auxiliary value.

In the above scheme, the processing module is specifically configured to, after receiving a quorum of first-type consensus messages, and if the voting values carried by the quorum of first-type consensus messages are the same, set the voting value add to the first set;

In the above solution, the processing module is also used to compare the voting value in the first set with the public coin toss value of the previous round when the current consensus round is not the first round, and according to the comparison result and received The first type of consensus message re-determines the voting value and auxiliary value.

In the above solution, the processing module is specifically used for when the voting value in the first set is equal to the public coin toss value of the previous round, if the voting value carried in the received first type of consensus message is the The voting value in the first set, the auxiliary value carried is the voting value in the first set or empty, then the voting value and the auxiliary value are determined as the voting value in the first set; otherwise, the voting value is determined as NULL, and determine the auxiliary value as the voting value in this first set.

In the above scheme, the processing module is also used to: if the voting value carried in the received first type of consensus message and the auxiliary If the values are all voting values in the first set, then determine the voting value and the auxiliary value as the voting value in the first set; otherwise, determine the voting value as empty, and determine the auxiliary value as the first set Voting value in .

In the above scheme, the processing module is specifically used to add the voting value in the received second type of consensus message to the second set, if there are more than the quorum of the second type of voting value in the received second type of consensus message The consensus messages are the same, and the voting value in the second type of consensus message is the same as the auxiliary value, then compare the voting value in the second type of consensus message with the current round of public coin toss value, if the voting value is the same as the current round If the public coin toss values are the same, the target consensus node determines that the consensus result is the voting value; voting value.

In the above scheme, the processing module is further configured to: if only legal consensus messages of the second type have been received, the voting value in the second set is one type of voting value and empty, and there are at least a quorum of second-type consensus messages. The auxiliary value of the consensus message is the voting value, and the voting value is compared with the public coin value of the previous round of consensus and the public coin value of the current round of consensus;

In the above scheme, the processing module is further configured to: if a quorum of legitimate second-type consensus messages is received, and the auxiliary values carried by the quorum of second-type consensus messages are not all the same, the votes in the second set The value is a voting value and empty, and this voting value is the same as the public coin toss value of the previous round of consensus, then the voting value and auxiliary value in the first type of consensus message in the next round of consensus are set to this voting value value.

In the above solution, the processing module is further configured to if the received second consensus message includes two kinds of voting values; or, if the auxiliary value carried by the quorum of legitimate second-type consensus messages received by the target node is different, The voting value in the second set is a voting value and empty, and the voting value is different from the previous round of public coin toss; the public coin toss value of this round of consensus will be used as the vote for the next round of the first consensus message value; if the current round of consensus is the first round, the auxiliary value in the first type of consensus message in the next round will be set as the current round of public coin value; if the current round of consensus is not the first round, the next round of the first consensus The auxiliary value in is determined to be a value whose occurrence number in the second set exceeds a preset number of times.

According to a third aspect of the embodiments of the present application, a computer device is provided, including a memory, a processor, a communication interface, and a computer program stored in the memory and operable on the processor, wherein the processor executes the When the program is described, the steps of the method described in the first aspect above are realized.

According to a fourth aspect of the embodiments of the present application, there is provided a computer-readable storage medium, on which a computer program is stored, and when the program is executed by a processor, the steps of the method described in the above-mentioned first aspect are implemented.

By adopting the consensus method provided in the embodiment of this application, each consensus node broadcasts the voting value and auxiliary value without any public key cryptography, digital signature or threshold signature, so that each consensus node can quickly reach consensus proposals. Consensus greatly improves the consensus efficiency of each consensus node.

Description of drawings

The drawings described here are used to provide a further understanding of the application and constitute a part of the application. The schematic embodiments and descriptions of the application are used to explain the application and do not constitute an improper limitation to the application. In the attached picture:

Figure 1 is a schematic flow diagram of an asynchronous binary consensus method in the embodiment of this specification

FIG. 2 is a schematic diagram of a consensus node maintaining each ABA instance according to an embodiment of this specification;

FIG. 3 is a schematic flow diagram of a broadcast consensus message according to an embodiment of this specification;

Fig. 4 is a schematic diagram of each round of consensus process in the embodiment of this specification;

FIG. 5 is a schematic structural diagram of an asynchronous binary consensus device according to an embodiment of this specification;

Fig. 6 is a schematic structural diagram of a device for configuring the device of the embodiment of the present specification.

Detailed ways

Binary consensus is the main component of the Byzantine Fault Tolerant Protocol (BFT). Currently known asynchronous Byzantine consensus protocols rely directly or indirectly on binary consensus, which can enable distributed systems such as blockchains to be reached in an asynchronous environment. consensus. At the same time, binary consensus can also be used to construct state machine replication, and then use state machine replication to establish a foundation for distributed fault-tolerant systems. In addition, binary consensus can also be applied to technical fields such as databases.

In binary consensus, binary refers to two values, usually represented by 0 and 1. Each node in a distributed system can reach a consensus on one of the two values, and this value often has a certain value for a distributed system. important practical significance. Taking the application of binary consensus in the blockchain network as an example, the data of each node in the blockchain network needs to be consistent. If the binary consensus method is used, when each node reaches a consensus of 1 for a certain batch of transactions, each node will Store the data. When each node reaches a consensus of 0 for a certain batch of transactions, each node does not store the data, thus ensuring the consistency of the data stored by each node. It is understandable that if the execution efficiency of the binary consensus method is higher, the performance of the distributed system will be better. Therefore, how to improve the efficiency of the binary consensus method is an important research direction in the industry at present.

In view of the above problems, the embodiment of this application provides an asynchronous binary consensus method, which is applied to any consensus node in the distributed system. The node broadcasts consensus messages including voting values and auxiliary values, and based on other received The voting value sent by the consensus node and the auxiliary value determine the consensus result, so that each node in the system reaches a consensus.

The solutions in the embodiments of the present application can be realized by using various computer languages, for example, the object-oriented programming language Java and the literal translation scripting language JavaScript.

In order to make the technical solutions and advantages in the embodiments of the present application clearer, the exemplary embodiments of the present application will be further described in detail below in conjunction with the accompanying drawings. Apparently, the described embodiments are only part of the embodiments of the present application, and Not an exhaustive list of all embodiments. It should be noted that, in the case of no conflict, the embodiments in the present application and the features in the embodiments can be combined with each other.

In order to facilitate those skilled in the art to understand the contents of this specification, the nouns involved in this specification are described below.

In this specification, the consensus proposal can be understood as the data sent by any consensus node, and it is hoped that other consensus nodes will participate in the consensus on the data, and the voting value is used to represent the consensus opinion of each consensus node on the data, where The voting value includes the first voting value and the second voting value, that is, each consensus node can have two kinds of consensus opinions on the consensus proposal. It means that in other embodiments, other forms and symbols can also be used for representation. This specification does not limit the specific forms of the first voting value and the second voting value, as long as it can be used to distinguish the first voting value and the second voting value Any value can be used. The auxiliary value is an auxiliary opinion proposed in this specification to assist each node to reach a consensus on the proposal to be consensus, which includes the first voting value, the second voting value and null.

Taking the blockchain scenario as an example, the pending consensus proposal can be a batch of transactions obtained by any consensus node from the local transaction pool, and it is hoped that other consensus nodes can receive and store the batch of transactions, and the voting value is used to represent the transaction value of each consensus node. Whether to agree to store the pending consensus proposal.

In other application scenarios, the consensus proposal and voting value will have other different actual meanings, which are not limited in this specification.

As shown in Figure 2, it is a schematic diagram of a binary consensus instance to be executed by any node in the distributed system,

Any node in the distributed system will use the asynchronous binary consensus method proposed in this note for each consensus node (including itself) to determine the consensus result of the consensus proposal proposed by the consensus node, as shown in the example ABA ₁ in the figure -ABA _n is a schematic diagram of the asynchronous binary agreement method ABA (asynchronous binary agreement) for N consensus nodes, ABA1 is a schematic diagram of the target node performing asynchronous binary consensus on the pending consensus proposal proposed by consensus node 1, and ABA2 is the target It is an indication that the node performs asynchronous binary consensus on the pending consensus proposal proposed by the consensus node 2, and so on.

It can be seen from the schematic diagram that the target node will determine an initial voting value (0 or 1) when performing consensus on each proposal to be consensus, and finally the binary consensus method proposed based on this description will also get The consensus result (0 or 1) for .

As shown in Figure 1, based on the above description, this specification proposes an asynchronous binary consensus method, which is a method executed by any consensus node in the distributed system. For the convenience of description, the consensus node is called the target node .

A distributed system includes at least N consensus nodes. A consensus node refers to a node that participates in the consensus process. It is understandable that there are usually other nodes that do not participate in the consensus in a distributed system. These nodes only receive and store the consensus node’s The consensus result does not participate in the consensus process; in addition, when there are too many malicious nodes or Byzantine nodes in the system, any consensus method cannot ensure that the consensus nodes in the system reach a consensus, so this specification stipulates that the distributed system includes N Consensus nodes, at most f malicious nodes are allowed to exist among the N consensus nodes, N≥3f+1, both f and N are integers greater than 0, and this method is applied to any of the plurality of consensus nodes For the correct node, it is understandable that other correct consensus nodes are also executing the above method asynchronously. When the target node proposes the consensus result of the pending consensus proposal for any consensus node, other correct consensus nodes will eventually get the same consensus proposal for the pending consensus proposal. consensus results.

The method includes:

S101, for any consensus node's pending consensus proposal, determine the initial voting value corresponding to the pending consensus proposal, and the initial auxiliary value;

According to the above Figure 2 and the description of Figure 2, it can be known that the target node will determine the consensus result for each consensus node’s proposal to be consensus, and Figure 1 describes the consensus process to be executed for each consensus proposal.

In this step, the initial voting value and the initial auxiliary value are determined for the consensus proposal. The initial auxiliary value can be empty by default, and the initial voting value can be determined according to different data in different application scenarios. For example, in a blockchain network, it can be determined according to whether the proposal to be consensus is received: if the target node receives the proposal to be consensus (broadcast by other consensus nodes through the reliable broadcast RBC protocol), then determine the The initial voting value is the first voting value. If it is determined that the consensus proposals from N-f consensus nodes have been received, the initial voting value of the unreceived consensus proposals can be set as the second voting value. In other application scenarios, the initial voting value of the proposal to be consensus can also be determined according to different data. In this specification, the first voting value is 1 and the second voting value is 0 as an example for illustration.

S102. Broadcast the current round of consensus messages, where the consensus messages carry voting values and auxiliary values;

S103, based on the received voting values and auxiliary values broadcast by other consensus nodes, determine whether to obtain a consensus result.

The consensus method proposed in this specification is executed in consensus rounds, each round includes the stage of exchanging voting values and auxiliary values with other consensus nodes, and the stage of determining the consensus result based on the interaction results after the interaction is completed, that is, S102-S103.

S102 and S103 are described in detail below:

In the above S102, the target node may specifically execute the method as described in Figure 3:

S301, carrying the voting value and the auxiliary value in the first type of consensus message for broadcasting;

If it is the first round of consensus, the target node can determine the initial voting value and initial auxiliary value according to the method described in S101 above; if it is not the first round of consensus, the method of determining the voting value and auxiliary value can refer to the section about S303 below, here Not detailed.

The target node can add the locally determined voting value and auxiliary value to the first type of consensus message, and transmit the first type of consensus message to other consensus nodes in the distributed system through the authentication channel. Of course, when there is no authentication channel, for To ensure the security of data transmission, cryptographic tools such as digital signatures or public key technology facilities can also be used to ensure the security of consensus message transmission, which is not limited in this specification.

In one embodiment, the first type of consensus message can be a message in bval _r format, and the target node can broadcast a message in the form of bval _r (est _r , maj _r ), where est _r is a voting value, maj _r is an auxiliary value, and voting The value est _r is a binary number (0 or 1), maj _r ∈ {0,1,⊥}, in round 0, maj _r can be set to empty, r is the number of consensus rounds, the first round is round 0, r increments in steps of 1.

S302, receiving the first type of consensus message broadcast by other consensus nodes;

It is understandable that all correct nodes in the distributed system are executing the steps performed by the target node, that is, other consensus nodes will also send the first type of consensus message including voting value and auxiliary value; at this time, the target node will receive To the first type of consensus messages sent from other consensus nodes.

In one embodiment, if the target node receives f+1 first-type consensus messages in the current consensus round, that is, the first-type consensus messages exceeding the number of malicious nodes, if the f+1 first-type consensus messages The voting value is the same and inconsistent with the voting value broadcast by the local consensus message of the first type of consensus in this round, and the target node modifies the local voting value of the current round to the same value as the voting value in f+1 first type consensus messages, And broadcast the first type of consensus message again. For example, if the target node receives f+1 bval _r (b,*) messages, and b is not equal to the voting value est _r of the target node’s first broadcast in the current round, the target node will broadcast

Where * can be 0, 1 or any value in the air,

The purpose of this step is to allow the local node to correct the local voting value.

S303. Re-determine the voting value and auxiliary value based on the received first-type consensus message, and broadcast the re-determined voting value and auxiliary value in the second-type consensus message.

After the target node receives the quorum of the first type of consensus message, it can re-determine the voting value and auxiliary value according to the received first type of consensus message, where the quorum is 2f+1, (including its own node), Unless otherwise specified, the quorum below is 2f+1.

Specifically, if the voting values in the 2f+1 first-type consensus messages are the same, the target node will add the voting values to the first set. For example, if the target node receives 2f+1 bval _r (b,*) messages, b∈{0,1}. Then the target node adds b to the first set bin_values _r . In addition, the target node also adds the auxiliary values in the above 2f+1 first-type consensus messages to the auxiliary value set majs. In this step, if a quorum of the same voting value is received, the voting value is stored in the first set, which means that most nodes in the system may have reached a consensus.

After storing the voting value in the first set, if the current consensus round is the first round, that is, round 0 (the consensus round starts from 0 and increments by 1), then the voting value and auxiliary value can be determined as the first set The voting value in , and broadcast the second type of consensus message; Continuing the above example, if b is added to the first set, that is, the set bin_values _r , you can re-determine that both the voting value and the auxiliary value are b, and start broadcasting the first set The second type of consensus message aux _r (b,b), where aux _r is the format of the second type of consensus message.

In addition, if the current consensus round is not the first round or the 0th round of consensus, the target node will compare the voting value in the first set with the public coin toss value of the previous round, and determine the second type of consensus based on the comparison result The voting value and auxiliary value carried in the message. Among them, the public coin toss value only has two values of 0 or 1. Each consensus node can obtain the same public coin toss value in a certain round, and the value of each round of coin toss is random. The method of obtaining the public coin toss value can be to use The interactive threshold pseudo-random number protocol, threshold signature protocol, trusted platform (TEE) and other methods are implemented. For specific content, please refer to related technologies, which will not be described in detail here.

The way to determine the voting value and auxiliary value carried in the second type of consensus message according to the comparison result is as follows:

One case is, if the voting value in the first set is equal to the public coin toss value of the previous round, and the voting values carried in the received first type of consensus message are all the voting values in the first set, the carried If the auxiliary values are all voting values in the first set or empty, the voting value and auxiliary value in the second type of consensus message are determined as the voting values in the first set and broadcast; if other voting values are received value of the first type of consensus message, the voting value in the second type of consensus message is set to be empty, and the auxiliary value in the second type of consensus message is set as the voting value in the first set. Continuing the above example, if the voting value in the first set is b, the value of the public coin toss in the last round is S _r-1 , if b=S _r-1 , and the target node has only received bval _r (b,b) and bval _r (b,⊥) messages, broadcast aux _r (b,b) directly, and broadcast aux _r (⊥,b) if the first type of consensus message carrying other voting values is also received.

Another situation is that if the voting value in the first set is not equal to the public coin toss value of the previous round, and the voting value and auxiliary value carried in the first type of consensus message received by the target node are both the first set In the case of the voting value in the second consensus message, set the voting value and auxiliary value in the second type of consensus message as the voting value in the first set and broadcast it; If one type of consensus message is used, the voting value in the second type of consensus message is set to be empty, and the auxiliary value in the second type of consensus message is set as the voting value in the first set. Continuing the above example, if the voting value in the first set is b, the value of the public coin toss in the last round is S _r-1 , if

in,

Since the coin toss value has only two values, 0 or 1, and the voting value has only two values, 0 or 1, so when the voting value b is not equal to the coin toss value S _r-1 , it is equal to 1-S _r-1 , that is

In this case, and the target node has only received the bval _r (b, b) message, it will broadcast aux _r (b, b) directly. If it has also received the first type of consensus message carrying other voting values or auxiliary values, Then broadcast aux _r (⊥,b).

Each consensus node broadcasts the second consensus information only once per round. The above method is a method for the target node to determine the voting value and auxiliary value carried in the second type of consensus message.

When the target node sends the second type of consensus message, since other consensus nodes will also send the second type of consensus message asynchronously, the target node will receive the second type of consensus message sent by other consensus nodes. After the target node receives the consensus messages sent by other consensus nodes, it can first delete some obviously illegal second-type consensus messages. According to the above content, since the correct consensus node will only broadcast aux _r (b,b) And the second type of consensus message of aux _r (⊥,b), so when receiving a message carrying other voting values or auxiliary values, it can be discarded directly, because the voting value in the second type of consensus message is stored in the first set Therefore, after receiving the second type of consensus message, the first set can be used to determine legal and illegal messages.

In the above S103, the target consensus node determines whether to obtain a consensus result based on the received voting value and auxiliary value. If no consensus result is obtained, it determines the next round of voting value and auxiliary value, and restarts execution of S101.

The following is a detailed description of how the target consensus node determines the consensus result based on the received voting value and auxiliary value, and determines the next round of voting value and auxiliary value:

After the target node receives a quorum of second-type consensus messages, it can store the voting value and auxiliary value in the second-type consensus messages received in the second set vals _r and the third set avals _r respectively, and obtain The unified public coin toss value of all consensus nodes in this round. For example, after the target node receives 2f+1 aux _r () messages, it can store the voting value and auxiliary value in the received aux _r () messages into the sets vals _r (second set) and avals _r ( in the third set). The target node can determine the consensus result, or the voting value and auxiliary value carried by the first type of consensus message in the next round of consensus according to the situation of the second type of consensus message received:

(a) If there are more than quorum of the second consensus messages received by the target node that are the same, and the voting value in these second consensus messages is the same as the auxiliary value, the target node will The voting value in the second type of consensus message is compared with the current round of public coin toss value. If the voting value is the same as the current round of public coin toss value, the target consensus node determines that the consensus result is the voting value; if not, the target node will The voting value and auxiliary value carried in the first type of consensus message in the next round are set as the voting value in these second type of consensus messages, and the next round of consensus is started.

For example, if the target node receives a quorum of aux _r (b,b) information, the target node will compare b with the current round of public coin toss S _r . If b=S _r , the target node determines that the consensus result is b; otherwise, the target node sets both est _r+1 and maj _r+1 to b, and enters the next round of consensus.

(b) If the target node has only received legitimate second-type consensus messages, and the voting value in the second set is a voting value and empty, and there are at least a quorum of second-type consensus messages whose auxiliary values are For this type of voting value, compare this type of voting value with the public coin value of the previous round of consensus and the current round of consensus. If this type of voting value is the same as the public coin toss value of the previous round and this round, the target node determines that the consensus result should be this type of voting value. If the currency values are different, the target consensus node will set the voting value and auxiliary value in the first type of consensus message in the next round as this type of voting value, and start the next round of consensus.

For example, if the target node has only received aux _r (b,*) and aux _r (⊥,*), and there is at least a quorum of second-class consensus messages for aux _r (*,b), then the target node compares b with Two rounds of public coin flips S _{r - 1} are compared with S _r . If b=S _r-1 and b=S _r , the target node determines that the consensus result is b, otherwise the target node sets both est _r+1 and maj _r+1 to b, and enters the next round.

(c) If the target node has received a quorum of legitimate second-type consensus messages, the auxiliary values carried by the quorum of second-type consensus messages are different, and the voting value in the second set is a voting value and empty, And this type of voting value is the same as the previous round of public coin toss, the target consensus node will set the voting value and auxiliary value in the first type of consensus message in the next round of consensus as this type of voting value, and start the next round of consensus. For example, if the target node receives Nf aux _r (b,*) and aux _r (⊥,*) messages, which contain both aux _r (*,0) and aux _r (*,1), and b=S _{r -1} , the target node sets both est _r+1 and maj _r+1 to b, and enters the next round of consensus.

(d) If the second type of consensus message received by the target node does not belong to the above three situations, that is, if the received second consensus message includes two voting values; The auxiliary value carried by the second type of consensus message is different, the voting value in the second set is a kind of voting value and empty, and the voting value of this type is different from the value of the last public coin toss. Then the target node can use the current round of public coin toss value as the voting value of the next round of the first type of consensus message. In addition, if the current consensus round is the first round, the target node will also set the auxiliary value in the first type of consensus message in the next round as the public coin value of the current round. If the current consensus round is not the first round, the target node will set the auxiliary value of the next round The auxiliary value in the first consensus message is set to the value whose occurrence times in the second set exceeds the preset number, and enters into the next round of consensus.

For example, if the second consensus message received by the target node does not belong to the above three situations, the target node will use the current round of public coin toss value as the next round input (ie set est _r+1 to S _r ). In addition, if the number of rounds r=0, the target node sets maj _r+1 as S _r ; if r>0, the target node sets maj _r+1 as majority(vals _r ), where majority(vals _r )=b , b ∈ {0, 1}, representing the majority of occurrences of b in vals _r , that is, the number of b in vals _r is not less than

If there is no such b, let majority(vals _r )=⊥.

It can be understood that the above method is the method executed by any correct node among the consensus nodes, and other correct consensus nodes are also executing the above method asynchronously. Using the above method, each consensus node in the distributed system in an asynchronous environment can Quickly reach a consensus state on a certain value, where the probability of reaching a consensus in the first round is 1-(1/2) ¹ , the probability of reaching a consensus in the second round is 1-(1/2) ² ... and so on, that is, with the consensus With the increase in the number of rounds, the probability of reaching a consensus increases exponentially. The average number of rounds to complete the consensus is two rounds, that is, the mathematical expectation of the total number of running rounds is two rounds, and only 2-3 steps need to be executed in each round, which greatly improves the Consensus efficiency of distributed systems in an asynchronous environment, and the above-mentioned consensus method does not need to rely on any public key cryptography, does not need to assume digital signatures, or threshold signatures, and only needs to determine a fair coin toss. Experiments have proved that the proposed The asynchronous binary consensus method is currently the most efficient binary consensus method.

As shown in Figure 4, it is a schematic diagram of each round of consensus process in the above 102-103, that is, each consensus node first adds the voting value and auxiliary value to the first type of consensus message and broadcasts it to other nodes, and based on the information broadcast by other consensus nodes The first type of consensus message determines the voting value and auxiliary value carried by the second type of consensus message, and finally determines the consensus result based on the interactive voting value and auxiliary value.

Combining the above Figure 2 and Figure 4, after reaching a consensus on the consensus proposals put forward by all consensus nodes, each correct consensus node will get the same consensus result, which is a sequence containing 0 and 1. Further, corresponding transaction processing can be performed based on the sequence. Still taking the blockchain network as an example, 0 or 1 is used to indicate whether to pack the corresponding consensus proposal into blocks. For example, there are four consensus nodes. The consensus proposal proposed by consensus node 1 is P1, the consensus proposal proposed by consensus node 2 is P2, the consensus proposal proposed by consensus node 3 is P3, and the consensus proposal proposed by consensus node 4 is P4. Using the above consensus The method obtains a 01 sequence after consensus, for example, the obtained sequence is (1,1,1,0), then the consensus result reached is that all nodes pack P1, P2, and P3 into blocks and store them locally without storing P4, that is, each According to the consensus results, the consensus nodes have carried out consistent processing on each consensus proposal to ensure the data consistency of each consensus node.

In order for those skilled in the art to understand the above consensus method more clearly, the following takes the blockchain scenario as an example to explain the process of the target node receiving the pending consensus proposal from other consensus nodes and sending the pending consensus proposal to other consensus nodes:

The target node can randomly obtain a preset number of transactions from the local transaction pool, or preferentially obtain a preset number of transactions stored earlier according to the order in which the transactions are stored. It is understandable that since each consensus node will receive the transaction requested by the client, each consensus node can maintain its own transaction pool locally. After the target node obtains the transaction, it can package the obtained transaction into the consensus proposal for this time. After the target node obtains the local pending consensus proposal, it can broadcast the local pending consensus proposal to other consensus nodes based on the reliable broadcast RBC protocol, and can also receive the pending consensus proposal broadcast by other consensus nodes based on the reliable broadcast RBC protocol. The following is an example of a specific implementation of the reliable broadcast RBC protocol:

The target node can use erasure coding to process the consensus proposal to obtain N data blocks; build a Merkle tree based on the hash values of the obtained N data blocks, and obtain the root hash and the Merkle tree corresponding to each data block. Merkel proof of Merkel path; save some of the N data blocks locally, and send other data blocks, root hashes, and Merkel paths corresponding to other data blocks to other consensus nodes, so that Other consensus nodes broadcast and verify the data block. Taking a total of 4 consensus nodes (consensus node 1-consensus node 4) as an example, the target node is consensus node 1, and consensus node 1 splits the local pending consensus proposal into 4 data blocks after processing with erasure codes, which are respectively Data block 1-data block 4, use the preset Hash algorithm to perform Hash operation on the 4 data blocks, get the Hash values of the 4 data blocks, and build a Merkle tree based on the hash values of the 4 data blocks, the data block The Hash value of 1 is Hash1, the Hash value of data block 2 is Hash2, the Hash value of data block 3 is Hash3, and the Hash value of data block 4 is Hash4. Calculate Hash1 and Hash2 to get Hash12, and calculate Hash3 and Hash4 to get Hash34, calculate Hash12 and Hash34 to get the root Hash, so as to get the Merkle tree. It can be understood that the above only takes 4 nodes as an example. In practical applications, more complex Merkle trees can be constructed according to different numbers of consensus nodes. After building the Merkle tree, consensus node 1 can store data block 1 locally, send data block 2, Hash1, Hash34 and root Hash to consensus node 2; send data block 3, Hash4, Hash12 and root Hash To consensus node 3; send data block 4, Hash3, Hash12 and root Hash to consensus node 4. Take the content sent to consensus node 2 as an example, where Hash1 and Hash34 are the Merkel proofs of the Merkel path corresponding to data block 2. Consensus node 1 can send the above content to other consensus nodes in Rval message format. After other consensus nodes receive the above content sent by consensus node 1, they can broadcast the above content to other consensus nodes in Echo message format. After receiving the Echo message, other consensus nodes can verify whether the message is legal. Specifically, after receiving the message, for the data block in the message, use the Merkle proof of the Merkle path corresponding to the data block , root hash for verification; if the verification is passed, it is determined that the message is legal.

Continuing the above example, after receiving the Echo message, the consensus node 3 determines that the content of the message is: data block 4, Hash3, Hash12 and root Hash, then it can calculate the data block 4 to get Hash4, and combine Hash4 with the received Hash3 is calculated to get Hash34, and Hash34 is calculated with the received Hash12 to get the root Hash. If the calculated root Hash is the same as the received root Hash, it means that the Echo message is legal. If the verification fails, the root Hash can be discarded directly. Echo messages to avoid tampering of messages by malicious nodes.

Through the above method, consensus node 2-consensus node 4 can receive all data blocks sent by consensus node 1 (target node) (in the case that no node intentionally does not send data blocks), any node can receive N-f Echo After the message, and the N-f Echo messages are all verified, select any N-2f data blocks to restore the consensus proposal, and the Merkle tree can be reconstructed, and the root of the reconstructed Merkle tree can be compared Whether the Hash is consistent with the root Hash in the Echo received before, and if it is consistent, the Ready message will be broadcast.

It is understandable that, although the above description takes target node 1 as an example, in the consensus method shown in this specification, each consensus node has no primary and secondary distinction, that is, any consensus node is a target node, and any consensus node Nodes can obtain consensus proposals from other consensus nodes through the above methods; any consensus node can also send local consensus proposals to other consensus nodes through the above methods.

Each consensus node can send local pending consensus proposals at the same time, so the target node may successively receive pending consensus proposals sent by different consensus nodes. After receiving any pending consensus proposal from other consensus nodes, the target node can determine the initial voting value of the pending consensus proposal, for example, determine the initial voting value as the first voting value 1, and execute the S101-S103, that is, the initial voting value of each pending consensus proposal can be determined according to the reception of the pending consensus proposal to trigger the execution of the asynchronous binary consensus method proposed in this specification, and then the pending consensus broadcast by each consensus node in the blockchain network can be Consensus proposals reach consensus separately.

It can be understood that the above is only a specific implementation manner of the reliable broadcast RBC protocol, and the reliable broadcast RBC protocol can also be implemented in other ways. For specific content of the reliable broadcast RBC protocol, reference can be made to related technologies, which is not limited in this specification. The above is also an example of applying the asynchronous binary consensus method proposed in this specification to the blockchain network. In other application scenarios, the initial voting value of any proposal to be consensus can also be determined based on different data, and trigger the execution The asynchronous binary consensus method proposed in this specification enables each consensus node to reach a consensus.

The following describes S101-S103 of this manual from the perspective of code implementation:

The pseudocode is as follows:

In the above pseudo code, any b∈{0,1};

* When used as a parameter in a message, it can represent b,

or ⊥; for example, aux _r (*,b) might represent

or aux _r (⊥,b); bval _r (b,*) might represent

or bval _r (b,⊥); aux _r () can represent aux _r (*,*); vals is a vector (multiset) consisting of 0, 1 and ⊥. V ₁ (vals)=b if and only if the vals set contains only b, b∈{0,1,⊥}; V ₁ (vals,b)=t if and only if the vals contains only b or only b With ⊥, where b∈{0, 1}, b appears t times in vals. majority(vals)=b,b∈{0,1}, which means that b appears in the majority of vals, that is, the number of b in vals is not less than

If there is no such b, let majority(vals)=⊥.

In the above pseudo-code, there are two message types: bval _r () and aux _r (), in each round, replica (node) p _i has an input value est _r and an auxiliary input value maj _r. where est _r is a binary number (0 or 1), maj _r ∈ {0,1,⊥}. The steps of the r-round agreement are as follows:

(1) In round r, p _i (target node) first broadcasts bval _r (est _r ,maj _r ) message. In round 0, maj _r is set to ⊥. A correct replica in round r does not change its maj _r .

a. If the replica p _i receives f+1 bval _r (b,*) messages, and b is not equal to the input est _r of the replica, the replica will broadcast bval _r

b. If replica p _i receives 2f+1 bval _r (b,*) messages, b∈{0,1}. Then p _i adds b to the set bin_values _r .

In addition, _pi checks the maj _r variable values in the received 2f+1 bval _r (b,*) messages and stores these values in the set majs.

Set r(b) to 1 when the following conditions are satisfied.

If r=0, set r(b) to 1 regardless of b=1 or b=0;

If r > 0, the replica p _i compares b with the value S _{r - 1} of the public toss of round r–1.

If b=Sr-1, and p _i has only received bval _r (b,b) and bval _r (b,⊥) messages, then set r(b) to 1;

like

And _pi has only received bval _r (b,b) messages (that is, V1(majs)=b), then r(b) is set to 1. After p _i receives sf+1 bval _r (b,*) messages, if r(b)=1, then broadcast aux _r (b,b); otherwise broadcast aux _r (⊥,b). A correct replica sends only one aux _r () message per round.

(2) When p _i receives the aux _r () message, only when both V1 and V2 belong to the set bin_values _r , can it receive the corresponding aux _r (v1, v2) message. Copies in the form of

or messages like aux _r (*,⊥), because according to our agreement, these messages are not legally proposed according to the agreement. In addition, if the replica has set r(b)=1 in the current round, the later received

The message will be discarded.

After receiving Nf aux _r () messages, p _i stores the first variable and the second variable in the aux _r () messages into the sets vals _r and avls _r respectively, obtains the public coin toss value, makes a judgment and enters the next round. At this point, there are four situations:

a. If p _i receives a quorum (because N=3f+1, the quorum is 2f+1=nf) aux _r (b,b) information, p _i compares b with the public coin toss S _r . If b=Sr, pi decides b; otherwise, pi sets both est _r+1 and maj _r+1 to b, and enters the next round.

b. If _pi only receives aux _r (b,*) and aux _r (⊥,*), and there are at least quorum messages in the format of aux _r (*,b), then _pi will combine b and two A round of public coin tosses _Sr-1 is compared with _Sr. If b=Sr _-1 and b= _Sr , _pi determines b. Otherwise, p _i sets both est _r+1 and maj _r+1 to b, and enters the next round.

c. If p _i receives Nf aux _r (b,*) and aux _r (⊥,*) messages, which contain both aux _r (*,0) and aux _r (*,1), and b=S _{r -1} , then p _i sets both est _r+1 and maj _r+1 to b, and enters the next round.

d. If none of the three cases apply, p _i uses the public coin toss value of the current round as the input for the next round (that is, set est _r+1 to S _r ). In addition, if the number of rounds r=0, p _i sets maj _r+1 as S _r ; if r>0, sets maj _r+1 as majority(vals _r ).

Subsequently, p _i enters r+1 rounds.

As shown in Figure 5, corresponding to the aforementioned asynchronous binary consensus method, this specification also provides an asynchronous binary consensus device, which is characterized in that the device is applied to any consensus node in the distributed system , the distributed system includes at least N consensus nodes, where N≥3f+1, the f is an integer greater than 0, and the device includes:

The processing module 520 is configured to determine an initial voting value corresponding to the consensus proposal for any consensus node, and an initial auxiliary value; wherein, the voting value includes a first voting value and a second voting value, and the auxiliary value Including the first voting value, the second voting value and empty, the initial voting value is the first voting value or the second voting value; execute each round of consensus steps in a loop until the consensus result for the proposal to be consensus is obtained;

In each round of consensus:

The communication module 510 is used to broadcast the consensus message of the current round, and the consensus message carries the voting value of the current round and the auxiliary value;

The processing module 520 is further configured to determine whether to obtain a consensus result based on the received voting values and auxiliary values broadcast by other consensus nodes.

In one embodiment, the communication module 510 is specifically configured to broadcast the voting value and auxiliary value in the first type of consensus message; receive the first type of consensus message broadcast by other consensus nodes;

The processing module 520 is specifically configured to re-determine the voting value and the auxiliary value based on the received first type of consensus message,

The communication module 510 is configured to broadcast the re-determined voting value and auxiliary value in the second type of consensus message.

In one embodiment, the processing module 520 is further configured to receive f+1 first-type consensus messages in the current consensus round, and the voting values in the f+1 first-type consensus messages are the same, Different from the voting value broadcast by the first type of consensus message in the local current round of consensus, the local voting value is modified to the voting value in the f+1 first type of consensus message; the communication module 510 is used to broadcast again The first type of consensus message carrying voting value and auxiliary value.

In one embodiment, the processing module 520 is specifically configured to, after receiving a quorum of first-type consensus messages, and if the voting values carried by the quorum of first-type consensus messages are the same, The vote value is added to the first set;

If the current consensus round is the first round, the voting value and the auxiliary value are determined as voting values in the first set.

In one embodiment, the processing module 520 is specifically configured to: if the voting value carried in the received first type of consensus message is are all voting values in the first set, and the auxiliary values carried are all voting values in the first set or empty, then the voting value and auxiliary value are determined as the voting values in the first set; otherwise, the voting The value is determined to be null, and the auxiliary value is determined to be the voting value in the first set.

In one embodiment, the processing module 520 is specifically configured to: if the vote value carried in the received first type of consensus message is not equal to the value of the public coin toss in the previous round value and the auxiliary value are voting values in the first set, then determine the voting value and the auxiliary value as the voting value in the first set; otherwise, determine the voting value as empty, and determine the auxiliary value as the voting value in the first set The vote value in the first set.

In one embodiment, the processing module 520 is specifically configured to determine whether to obtain a consensus result based on the vote value and auxiliary value in the received second type of consensus message.

In one embodiment, the processing module 520 is specifically configured to add the voting value in the received second type of consensus message to the second set when a quorum of the second type of consensus messages is received, And determine the public coin toss value of this round of consensus based on the preset algorithm;

If there are more than a quorum of the second type of consensus messages received in the second type of consensus messages that are the same, and the voting value in the second type of consensus messages is the same as the auxiliary value, then the second type of consensus messages in the second type of consensus messages The voting value is compared with the current round of public coin toss value. If the voting value is the same as the current round of public coin toss value, the target consensus node determines that the consensus result is the voting value;

In one embodiment, the processing module 520 is specifically configured to: if only legal consensus messages of the second type have been received, the voting value in the second set is one voting value and empty, and there are at least a quorum The auxiliary value of the second type of consensus message is the voting value, and the voting value is compared with the public coin toss value of the previous round of consensus and the public coin toss value of the current round of consensus;

In one embodiment, the processing module 520 is specifically configured to, if a quorum of legal second-type consensus messages are received, and the auxiliary values carried by the quorum of second-type consensus messages are not all the same, the second set The voting value in is a voting value and empty, and this voting value is the same as the public coin toss value of the previous round of consensus, then the voting value and auxiliary value in the first type of consensus message in the next round of consensus are set to the voting value.

In one embodiment, the processing module 520 is specifically configured to use the public coin toss value of the current round of consensus as the next round of the first type of consensus message when the received second type of consensus message does not satisfy the above-mentioned embodiment if the current round of consensus is the first round, then set the auxiliary value in the first type of consensus message in the next round as the public coin toss value of the current round; if the current round of consensus is not the first The auxiliary value in the common message is determined as a value whose occurrence times in the second set exceeds a preset number of times.

For the implementation process of the functions and effects of each module in the above device, please refer to the implementation process of the corresponding steps in the above method for details, and details will not be repeated here.

As for the device embodiment, since it basically corresponds to the method embodiment, for related parts, please refer to the part description of the method embodiment. The device embodiments described above are illustrative only. Part or all of the modules can be selected according to actual needs to achieve the purpose of the solution in this specification. It can be understood and implemented by those skilled in the art without creative effort.

The embodiment of this specification also provides a computer device, which at least includes a memory, a processor, and a computer program stored in the memory and operable on the processor, wherein the aforementioned method is implemented when the processor executes the program. The method includes at least the method shown in FIG. 1 above.

FIG. 6 shows a schematic diagram of a more specific hardware structure of a computing device provided by the embodiment of this specification. The device may include: a processor 1010 , a memory 1020 , an input/output interface 1030 , a communication interface 1040 and a bus 1050 . The processor 1010 , the memory 1020 , the input/output interface 1030 and the communication interface 1040 are connected to each other within the device through the bus 1050 .

The processor 1010 may be implemented by a general-purpose CPU (Central Processing Unit, central processing unit), a microprocessor, an application-specific integrated circuit (Application Specific Integrated Circuit, ASIC), or one or more integrated circuits, and is used to execute related programs to realize the technical solutions provided by the embodiments of this specification.

The memory 1020 can be implemented in the form of ROM (Read Only Memory, read-only memory), RAM (Random Access Memory, random access memory), static storage device, dynamic storage device, etc. The memory 1020 can store operating systems and other application programs. When implementing the technical solutions provided by the embodiments of this specification through software or firmware, the relevant program codes are stored in the memory 1020 and invoked by the processor 1010 for execution.

The input/output interface 1030 is used to connect the input/output module to realize information input and output. The input/output/module can be configured in the device as a component (not shown in the figure), or can be externally connected to the device to provide corresponding functions. The input device may include a keyboard, mouse, touch screen, microphone, various sensors, etc., and the output device may include a display, a speaker, a vibrator, an indicator light, and the like.

The communication interface 1040 is used to connect a communication module (not shown in the figure), so as to realize the communication interaction between the device and other devices. The communication module can realize communication through wired means (such as USB, network cable, etc.), and can also realize communication through wireless means (such as mobile network, WIFI, Bluetooth, etc.).

Bus 1050 includes a path that carries information between the various components of the device (eg, processor 1010, memory 1020, input/output interface 1030, and communication interface 1040).

It should be noted that although the above device only shows the processor 1010, the memory 1020, the input/output interface 1030, the communication interface 1040 and the bus 1050, in the specific implementation process, the device may also include other components. In addition, those skilled in the art can understand that the above-mentioned device may only include components necessary to implement the solutions of the embodiments of this specification, and does not necessarily include all the components shown in the figure.

The embodiment of the present specification also provides a computer-readable storage medium, on which a computer program is stored, and when the program is executed by a processor, the aforementioned method is implemented. The method includes at least the method shown in FIG. 1 above.

Computer-readable media, including both permanent and non-permanent, removable and non-removable media, can be implemented by any method or technology for storage of information. Information may be computer readable instructions, data structures, modules of a program, or other data. Examples of computer storage media include, but are not limited to, phase change memory (PRAM), static random access memory (SRAM), dynamic random access memory (DRAM), other types of random access memory (RAM), read only memory (ROM), Electrically Erasable Programmable Read-Only Memory (EEPROM), Flash memory or other memory technology, Compact Disc Read-Only Memory (CD-ROM), Digital Versatile Disc (DVD) or other optical storage, A magnetic tape cartridge, disk storage or other magnetic storage device or any other non-transmission medium that can be used to store information that can be accessed by a computing device. As defined herein, computer-readable media excludes transitory computer-readable media, such as modulated data signals and carrier waves.

It can be known from the above description of the implementation manners that those skilled in the art can clearly understand that the embodiments of this specification can be implemented by means of software plus a necessary general hardware platform. Based on this understanding, the essence of the technical solutions of the embodiments of this specification or the part that contributes to the prior art can be embodied in the form of software products, and the computer software products can be stored in storage media, such as ROM/RAM, A magnetic disk, an optical disk, etc., include several instructions to make a computer device (which may be a personal computer, a server, or a network device, etc.) execute the methods described in various embodiments or some parts of the embodiments of this specification.

The systems, devices, modules, or units described in the above embodiments can be specifically implemented by computer chips or entities, or by products with certain functions. A typical implementing device is a computer, which may take the form of a personal computer, laptop computer, cellular phone, camera phone, smart phone, personal digital assistant, media player, navigation device, e-mail device, game control device, etc. desktops, tablets, wearables, or any combination of these.

Each embodiment in this specification is described in a progressive manner, the same and similar parts of each embodiment can be referred to each other, and each embodiment focuses on the differences from other embodiments. In particular, as for the device embodiments, since they are basically similar to the method embodiments, the description is relatively simple, and for relevant parts, please refer to part of the description of the method embodiments. The device embodiments described above are only illustrative, and the modules described as separate components may or may not be physically separated, and the functions of each module may be integrated in the same or multiple software and/or hardware implementations. Part or all of the modules can also be selected according to actual needs to achieve the purpose of the solution of this embodiment. It can be understood and implemented by those skilled in the art without creative effort.

The above is only the specific implementation of the embodiment of this specification. It should be pointed out that for those of ordinary skill in the art, without departing from the principle of the embodiment of this specification, some improvements and modifications can also be made. These Improvements and modifications should also be regarded as the scope of protection of the embodiments of this specification.

Claims

An asynchronous binary consensus method, characterized in that it is applied to any consensus node in a distributed system, and the distributed system includes at least N consensus nodes, where N≥3f+1, and f is greater than 0 Integer, the methods include:

For the consensus proposal of any consensus node, determine the initial voting value corresponding to the consensus proposal, and the initial auxiliary value; wherein, the voting value includes the first voting value and the second voting value, and the auxiliary value includes the first voting value, The second voting value and empty, the initial voting value is the first voting value or the second voting value;

Each round of consensus steps is cyclically executed until the consensus result for the proposal to be consensus is obtained, wherein each round of consensus steps includes:

Carry the voting value and auxiliary value in the first type of consensus message for broadcast;

Receive the first type of consensus messages broadcast by other consensus nodes;

Re-determine the voting value and auxiliary value based on the received first type of consensus message, and broadcast the re-determined voting value and auxiliary value in the second type of consensus message;

After receiving the quorum of the second type of consensus messages, the public coin toss value of the current round of consensus is obtained, and based on the public coin toss value and the received second type of consensus messages, the consensus result or the first type of consensus in the next round of consensus is determined The voting value and auxiliary value carried by the message.
The method according to claim 1, further comprising:

If f+1 first-type consensus messages are received in the current consensus round, and the voting value in the f+1 first-type consensus messages is the same as the voting value broadcast by the local consensus in this round through the first-type consensus message If not, modify the local voting value to the voting value in the f+1 first-type consensus messages, and broadcast the first-type consensus message carrying the voting value and auxiliary value again.
The method according to claim 2, wherein the re-determining the voting value and the auxiliary value based on the received first type of consensus message includes:

After receiving a quorum of first-type consensus messages, if the quorum of first-type consensus messages carry the same voting value, add the voting value to the first set;

If the current consensus round is the first round, the voting value and the auxiliary value are re-determined as voting values in the first set.
The method according to claim 3, further comprising:

If the current consensus round is not the first round, the voting value in the first set is compared with the public coin toss value of the previous round, and the voting value and auxiliary value are re-determined according to the comparison result and the first type of consensus message received.
The method according to claim 4, characterized in that, re-determining the voting value and the auxiliary value according to the comparison result and the received first type of consensus message, including:

In the case where the voting value in the first set is equal to the public coin toss value of the previous round, if the voting values carried in the received first type of consensus messages are all voting values in the first set, the auxiliary value carried are all voting values in the first set or empty, then determine the voting value and auxiliary value as the voting value in the first set; otherwise, determine the voting value as empty, and determine the auxiliary value as the first set Voting value in .
The method according to claim 5, further comprising:

In the case that the voting value in the first set is not equal to the public coin toss value of the previous round, if the voting value and the auxiliary value carried in the received first type of consensus message are both voting values in the first set, Then determine the voting value and the auxiliary value as the voting value in the first set; otherwise, determine the voting value as empty, and determine the auxiliary value as the voting value in the first set.
The method according to claim 6, characterized in that, based on the public coin toss value and the situation of the second type of consensus message received, determine the consensus result or the voting value carried by the first type of consensus message in the next round of consensus and Auxiliary values, including:

Add the voting value in the received second type of consensus message to the second set, if there are more than the quorum of the second type of consensus messages received in the second type of consensus message are the same, and the second type of consensus message If the voting value in the consensus message is the same as the auxiliary value, the voting value in the second type of consensus message is compared with the current round of public coin toss value, if the voting value is the same as the current round of public coin toss value, the target consensus node determines the consensus result for that vote value;

If they are different, the voting value and the auxiliary value carried in the first type of consensus message in the next round are both determined as the voting value in the second type of consensus message.
The method according to claim 7, further comprising:

If only legitimate second-type consensus messages have been received, the voting value in the second set is a voting value and empty, and there are at least a quorum of second-type consensus messages with auxiliary values of this kind of voting value, then Compare this voting value with the public coin toss value of the previous round of consensus and the public coin toss value of the current round of consensus;

If this kind of voting value is the same as the public coin toss value of the previous round of consensus and the public coin toss value of this round of consensus, then it is determined that the consensus result should be this kind of voting value; and/or the coin toss value of the current round of consensus is different, then the voting value and auxiliary value in the first type of consensus message in the next round are set to this kind of voting value.
The method according to claim 8, further comprising:

If a quorum of legitimate second-type consensus messages is received, the auxiliary values carried by the quorum of second-type consensus messages are not all the same, the voting value in the second set is a voting value and empty, and the If the voting value is the same as the public coin toss value of the previous round of consensus, the voting value and auxiliary value in the first type of consensus message in the next round of consensus will be set as this kind of voting value.
The method according to claim 9, further comprising:

If the received second consensus message includes two voting values; or, the quorum of legal second consensus messages received by the target node carry different auxiliary values, the voting value in the second set is a voting value and empty, and this type of voting value is different from the previous round of public coin toss; the public coin toss value of this round of consensus will be used as the voting value of the next round of the first type of consensus message; if the current round of consensus is the first round, the next round of consensus will be The auxiliary value in the first type of consensus message of a round is set as the public coin toss value of this round; if the current round of consensus is not the first round, the auxiliary value in the first consensus message of the next round is determined as the occurrence in the second set The number of times exceeds the value of the preset number of times.
An asynchronous binary consensus device, characterized in that the device is applied to any consensus node in a distributed system, and the distributed system includes at least N consensus nodes, where N≥3f+1, and the f is an integer greater than 0, and the device includes:

The processing module is used to determine the initial voting value corresponding to the consensus proposal for any consensus node, and the initial auxiliary value; wherein, the voting value includes the first voting value and the second voting value, and the auxiliary value includes The first voting value, the second voting value and empty, the initial voting value is the first voting value or the second voting value; execute each round of consensus steps in a loop until the consensus result for the proposal to be consensus is obtained;

In each round of consensus:

The communication module broadcasts the voting value and auxiliary value in the first type of consensus message; receives the first type of consensus message broadcast by other consensus nodes; re-determines the voting value and auxiliary value based on the received first type of consensus message, and Carry the re-determined voting value and auxiliary value in the second type of consensus message for broadcast;

The processing module is also used to obtain the public coin toss value of the current round of consensus after receiving the quorum of the second type of consensus message, and determine the consensus result or the next The voting value and auxiliary value carried by the first type of consensus message in a round of consensus.
A computer device, comprising a memory, a processor, a communication interface, and a computer program stored on the memory and operable on the processor, wherein the processor implements any one of claims 1 to 10 when executing the program the method described.
A computer-readable storage medium, on which a computer program is stored, and when the program is executed by a processor, the method according to any one of claims 1 to 10 is realized.