CN113783708A

CN113783708A - Re-voting binary consensus method and device based on reliable broadcast

Info

Publication number: CN113783708A
Application number: CN202110984391.5A
Authority: CN
Inventors: 张海滨; 段斯斯
Original assignee: Shandong Blockchain Research Institute; Tsinghua University
Current assignee: Shandong Blockchain Research Institute; Tsinghua University
Priority date: 2021-08-25
Filing date: 2021-08-25
Publication date: 2021-12-10
Anticipated expiration: 2041-08-25
Also published as: CN113783708B; WO2023024885A1

Abstract

The embodiment of the application provides a re-voting binary consensus method based on reliable broadcasting and a Byzantine fault-tolerant method, which are applied to any node in N consensus nodes, and the consensus method comprises the following steps: for a to-be-consensus proposal of any consensus node, determining an initial vote value of the to-be-consensus proposal; under the condition that the initial voting value is other voting values and meets a preset condition, determining the initial voting value as a priority voting value again; broadcasting an initial round of vote values to other nodes of the N consensus nodes based on a reliable broadcast RBC protocol; and determining the consensus situation of the proposal to be consensus based on the initial polling values broadcast by other consensus nodes. The method can enable each consensus node to quickly achieve consensus on the pending consensus offers, simultaneously improves the security of the consensus process, and in addition, if an unconditional and safe RBC protocol is adopted, the binary consensus method and the Byzantine fault-tolerant method are also unconditionally and safe.

Description

Re-voting binary consensus method and device based on reliable broadcast

Technical Field

The present application relates to the field of computer technologies, and in particular, to a reliable broadcast-based two-dimensional consensus method and apparatus for re-voting.

Background

The binary consensus is a main component of a byzantine fault-tolerant mechanism (BFT), and currently known asynchronous byzantine consensus protocols all rely directly or indirectly on the binary consensus, which enables a distributed system to achieve consensus in an asynchronous environment. Meanwhile, the binary consensus can also be used for constructing state machine replication (state machine replication), and further the state machine replication is used for establishing a foundation for the distributed fault-tolerant system. Therefore, the study on the binary consensus is an important research direction in the industry at present.

Disclosure of Invention

The embodiment of the application provides a reliable broadcast-based two-dimensional consensus method and device capable of re-voting, and is used for solving the problem of poor consensus security in the prior art.

According to a first aspect of the embodiments of the present application, a reliable broadcast-based two-element consensus method for re-voting is provided, where the method is applied to any one consensus node in a distributed system, where the distributed system includes N consensus nodes, where N ≧ 3f +1, and f is an integer greater than 0, and the method includes:

for a to-be-consensus proposal of any consensus node, determining an initial vote value of the to-be-consensus proposal; wherein, the initial voting value is a priority voting value or other voting values;

under the condition that the initial voting value is other voting values and meets a preset condition, determining the initial voting value as a priority voting value again;

broadcasting an initial round of vote values to other nodes of the N consensus nodes based on a reliable broadcast RBC protocol;

and determining the consensus situation of the proposal to be consensus based on the initial polling values broadcast by other consensus nodes.

According to a second aspect of the embodiments of the present application, there is provided a byzantine fault tolerance method, which is applied to any one consensus node in a distributed system, where the distributed system includes N consensus nodes, where N is greater than or equal to 3f +1, and f is an integer greater than 0, and the method includes:

determining the current proposal to be identified in a preset mode, and broadcasting the proposal to be identified to other nodes to be identified by using a reliable broadcast RBC protocol;

for the proposal to be consensus of any consensus node, the consensus result of the proposal to be consensus is determined by adopting the reliable broadcast-based re-voting binary consensus method.

According to a third aspect of the embodiments of the present application, there is provided a reliable broadcast-based two-dimensional consensus device for re-voting, which is applied to any one consensus node in a distributed system, where the distributed system includes N consensus nodes, where N is greater than or equal to 3f +1, and f is an integer greater than 0, and the device includes:

the processing module is used for determining an initial vote value of a to-be-consensus proposal aiming at the to-be-consensus proposal of any consensus node; wherein, the initial voting value is a priority voting value or other voting values; under the condition that the initial voting value is other voting values and meets a preset condition, determining the initial voting value as a priority voting value again;

a communication module for broadcasting the first round vote value to other nodes of the N consensus nodes based on a reliable broadcast RBC protocol;

the processing module is further configured to determine a consensus situation of the proposal to be consensus based on the first-round vote values broadcast by the other consensus nodes.

According to a fourth aspect of the embodiments of the present application, there is provided a byzantine fault-tolerant apparatus, which is applied to any one consensus node in a distributed system, where the distributed system includes N consensus nodes, where N is greater than or equal to 3f +1, and f is an integer greater than 0, the apparatus including:

the broadcast module is used for determining the proposal to be agreed in the consensus in a preset mode and broadcasting the proposal to be agreed to other consensus nodes by using a reliable broadcast RBC protocol;

and the consensus module is used for determining the consensus result of the proposal to be consensus by adopting the above reliable broadcast-based re-voted binary consensus method aiming at the proposal to be consensus of any consensus node.

By adopting the binary consensus method based on reliable broadcasting provided by the embodiment of the application, each consensus node utilizes the reliable broadcasting RBC protocol to broadcast the vote value, so that each consensus node can quickly achieve consensus on the to-be-consensus proposal, meanwhile, the security of the consensus process is improved, and the processing capacity of a distributed system is further improved.

Drawings

The accompanying drawings, which are included to provide a further understanding of the application and are incorporated in and constitute a part of this application, illustrate embodiment(s) of the application and together with the description serve to explain the application and not to limit the application. In the drawings:

fig. 1 is a schematic diagram of a consensus node maintaining respective RABA instances in an embodiment of the present disclosure;

fig. 2 is a flow chart illustrating a reliable broadcast-based two-element recognition method for re-voting according to an embodiment of the present disclosure;

fig. 3 is a flow chart of broadcast voting according to an embodiment of the present disclosure;

FIG. 4 is a flowchart illustrating another alternative reliable broadcast-based two-dimensional recognition method for re-voting according to an embodiment of the present disclosure;

fig. 5 is a schematic diagram illustrating that a consensus node maintains each RBC and RABA example in an embodiment of the present disclosure;

FIG. 6 is a schematic structural diagram of a Mercker tree in an embodiment of the present disclosure;

fig. 7 is a schematic structural diagram of a reliable broadcast-based two-dimensional recognition apparatus for re-voting according to an embodiment of the present disclosure;

fig. 8 is a schematic structural diagram of a byzantine fault-tolerant device according to an embodiment of the present disclosure;

fig. 9 is a schematic structural diagram of an apparatus for configuring a device according to an embodiment of the present disclosure.

Detailed Description

The binary consensus is an important component of a Byzantine fault tolerance mechanism BFT, and currently known asynchronous Byzantine consensus protocols all directly or indirectly rely on the binary consensus, so that block chains and other distributed systems can achieve consensus in an asynchronous environment. Meanwhile, the binary consensus can also be used for constructing state machine replication (state machine replication), and further the state machine replication is used for establishing a foundation for the distributed fault-tolerant system.

In the binary consensus, binary refers to two values, usually 0 and 1, and each node in the distributed system can agree on one of the two values, which is often of practical significance for the distributed system. Taking the application of the binary consensus to the blockchain network as an example, the data of each node in the blockchain network needs to be kept consistent, if the binary consensus method is utilized, when the consensus achieved by each node for a certain batch of transactions is 1, each node stores the data, and when the consensus achieved by each node for a certain batch of transactions is 0, each node does not store the data, so that the consistency of the data stored by each node is ensured. It can be understood that if the security of the binary consensus process is higher, the attack resistance of the distributed system is stronger and the performance is more excellent, so how to improve the security of the binary consensus is one of the important research directions in the industry at present.

In view of the above problems, an embodiment of the present application provides a reliable broadcast-based two-dimensional consensus method for re-voting, which is applied to any one consensus node in a distributed system, where the node broadcasts a vote value through a reliable broadcast RBC protocol, and determines a consensus result based on the received vote values broadcast by other consensus nodes, so that each node in the system achieves consensus, and meanwhile, the security of the consensus process is effectively improved.

The scheme in the embodiment of the application can be implemented by adopting various computer languages, such as object-oriented programming language Java and transliterated scripting language JavaScript.

In order to make the technical solutions and advantages of the embodiments of the present application more apparent, the following further detailed description of the exemplary embodiments of the present application with reference to the accompanying drawings makes it clear that the described embodiments are only a part of the embodiments of the present application, and are not exhaustive of all embodiments. It should be noted that the embodiments and features of the embodiments in the present application may be combined with each other without conflict.

To facilitate understanding of the contents of the present specification by those skilled in the art, terms referred to in the present specification will be described below.

In this specification, a proposal to be consensus-identified may be understood as data sent by any consensus node, and it is desirable that other consensus nodes participate in consensus on the data together, and the vote value is used to represent consensus opinions of the respective consensus nodes on the data, where the vote value includes two values, namely, the respective consensus nodes may have two consensus opinions together on the proposal to be consensus-identified, and the two values may be represented by 1 and 0 respectively in one embodiment, and may be represented by other forms and symbols in other embodiments.

Taking a blockchain scenario as an example, the to-be-consensus proposal may be a batch of transactions obtained by any consensus node from the local transaction pool, and it is expected that other consensus nodes may receive and store the batch of transactions, and the vote value is used to indicate whether each consensus node agrees to store the to-be-consensus proposal. In other application scenarios, the proposal to be commonly identified and the vote value may have different practical meanings, which is not limited in the present specification.

As shown in FIG. 1, a schematic diagram of a binary consensus instance to be performed by any node in a distributed system, which is based on reliable broadcast proposed by the present disclosure, is applied to each consensus node (including itself) by any node in the distributed systemThe two-element consensus method determines the consensus result of the proposal to be consensus proposed for the consensus node, and for convenience of description, any one of the consensus nodes is called a target node, such as RABA (random access ba) in the example in the figure₁-RABA_NRespectively, the schematic diagrams are that the N consensus nodes adopt a re-voting binary consensus method RABA for consensus, and the RABA₁The target node carries out binary consensus on the proposal to be consensus, RABA, proposed by the consensus node 1₂And performing binary consensus on the proposal to be consensus, which is proposed by the target node for the consensus node 2, and so on.

As can be seen from the schematic diagram, when performing consensus on each to-be-consensus proposal, the target node determines an initial vote value (0 or 1) as an input of the re-voted binary consensus method, and finally the re-voted binary consensus method proposed based on the description also obtains an output, that is, a consensus result (0 or 1) for the to-be-consensus proposal.

As shown in fig. 2, based on the above description, the present specification proposes a binary consensus method based on reliable broadcast, where the method is performed by any consensus node in a distributed system, where the distributed system includes at least N consensus nodes, where the consensus node refers to a node participating in a consensus process, and it is understood that there are other nodes that do not participate in the consensus process and that these nodes only receive and store the consensus result of the consensus node and do 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 achieve consensus, so the specification provides that the distributed system includes N consensus nodes, where f malicious nodes are allowed to exist at most in the N consensus nodes, N is greater than or equal to 3f +1, and f and N are integers greater than 0, for example, when N is 4, f is only 1, and when N is 8, f is 2 or 1. The value of f is preset in this specification to any positive integer corresponding to the value of N. For example, when N is 7, f may be set to 2.

The method is applied to any correct node in a plurality of consensus nodes in a distributed system, and it can be understood that other correct consensus nodes also execute the method asynchronously, when a target node obtains a consensus result for a to-be-consensus proposal proposed by any of the consensus nodes, the other correct consensus nodes finally obtain the same consensus result for the to-be-consensus proposal, and the distributed system may be a blockchain network or other distributed systems, which is not limited in this specification.

The method comprises the following steps:

s201, aiming at a proposal to be consensus of any consensus node, determining an initial vote value of the proposal to be consensus; wherein, the initial voting value is a priority voting value or other voting values;

s202, under the condition that the initial voting value is other voting values and meets a preset condition, determining the initial voting value as a priority voting value again;

s203, broadcasting the first round voting value to other nodes in the N common identification nodes based on a reliable broadcast RBC protocol;

and S204, determining the consensus condition of the proposal to be consensus based on the initial voting values broadcast by other consensus nodes.

As shown in fig. 1 and the description of fig. 1, the target node determines the consensus result for the candidate consensus proposition of each consensus node, and the consensus process to be performed for each candidate consensus proposition is described in fig. 2.

The two-element consensus method based on reliable broadcasting, which is proposed by the present specification, is executed according to consensus rounds, each round comprises a plurality of steps, and the above-mentioned S201-S204 are all steps executed by first-round consensus, and a certain probability is reached in each round of consensus process.

The contents of the above-mentioned S201-S202 can be referred to below, and will not be described in detail here.

In step S203, the target node may broadcast the local vote value to other consensus nodes, and receive the vote values broadcast by other consensus nodes. In order to improve security and avoid malicious nodes from intentionally tampering the vote value or pretending that other consensus nodes broadcast the vote value, each consensus node may broadcast the local vote value using a reliable broadcast RBC protocol. The reliable broadcast RBC protocol can ensure that the target node can reliably send messages to all the consensus nodes in the network and that the following properties are met: consistency (agent), that is, any two correct nodes receive the same message from the source node; uniformity (Totality), as long as one node receives a message from a source node, all correct nodes can eventually receive the message; activity (Validity), if the source node is correct, all correct nodes must receive messages that are identical to the messages sent by the source node.

Specific implementations of the reliable broadcast RBC protocol can refer to the related art, and are not described in detail herein. In this embodiment, various specific implementation manners may be adopted to implement the reliable broadcast RBC protocol, and this embodiment is not limited in this embodiment. The voting value is broadcast by adopting a reliable RBC protocol broadcasting mode, and compared with the common broadcast, the safety of the consensus process can be effectively improved.

In S203, that is, in the process of broadcasting the vote value in the first round, the target node broadcasts the vote value three times, the vote value broadcasted for the first time is referred to as a pre-vote value, the vote value broadcasted for the second time is referred to as a main vote value, and the vote value broadcasted for the third time is referred to as a final vote value, where in the first round, the initial vote value is the pre-vote value. In this specification, when the target node broadcasts the vote value three times, the reliable broadcast RBC protocol may be used for broadcasting.

In addition, considering that broadcasting through a reliable broadcast RBC protocol takes longer time compared with ordinary broadcasting, the description proposes that reliable broadcast RBC can be adopted only when a vote value is broadcasted for the third time in each round of consensus, that is, reliable broadcast RBC protocol can be adopted for broadcasting when a final vote value is broadcasted, and ordinary broadcasting forms are adopted when the rest two times of broadcasting.

In a specific embodiment, the target node may specifically execute the method described in fig. 3 to complete S203:

s301, broadcasting the initial voting value to other consensus nodes;

the target node may add the locally determined initial vote value to the first consensus message and transmit the first consensus message to other consensus nodes in the distributed system over the authentication channel. In one embodiment, the first common identification message may be a bval_rThe message in the format, wherein r is the number of the common identification rounds, the first round is 0, the increment is carried out by taking 1 as the step length, and the type of the message sent in the round is bval₀。

S302, determining a first-round main voting value based on the initial voting value and the initial voting values broadcast by other consensus nodes, and broadcasting the determined first-round main voting value to other consensus nodes;

it can be understood that all correct nodes in the distributed system execute the steps executed by the target node asynchronously, that is, other consensus nodes also send the first consensus message including the initial vote value; at this time, the target node receives the first consensus message sent by other consensus nodes, and further resolves the initial vote value. In the first round of consensus, the initial vote value is the pre-vote value.

In one embodiment, if the target node receives f +1 first consensus messages in the first round of consensus to resolve f +1 initial vote values, that is, the first consensus messages exceeding the number of malicious nodes, if the f +1 initial vote values are the same and different from the initial vote value of the local broadcast, the target node modifies the local initial vote value to the vote value corresponding to the f +1 initial vote values, and broadcasts the modified initial vote value again by using the first consensus messages. For example, if the target node receives f +1 bvals₀And (c) a message, wherein f +1 initial vote values carried in the f +1 messages are all 1, and the target node has broadcast an initial vote value of 0 once through the first consensus message, which is different from the f +1 initial vote values, so that the local initial vote value can be modified to 1, and the initial vote value of 1 is broadcast again through the first consensus message. The purpose of this step is to allow the consensus node to correct the local initial vote value.

The specific way of determining the first-round main voting value in this step is as follows: and if the target node determines that the local initial voting value is the priority voting value, adding the priority voting value into the first-round voting set, and determining the priority voting value as a first-round main voting value.

If the local initial voting value is other voting values, adding the 2f +1 initial voting values into a first-round voting set under the condition that 2f +1 initial voting values broadcasted by other consensus nodes are received and the 2f +1 initial voting values are all the same; and determines the value that was first added to the first-round voting set as the first-round master voting value.

For example, if the target node determines that the local initial vote value is a priority vote value of 1, then the priority vote value of 1 is added to the first-round voting set bset₀And determines that the priority vote value 1 is the main vote value.

If the target node determines that the local initial vote value is other vote values 0, after receiving 2f +1 first consensus messages and analyzing the received first consensus messages, the initial vote values carried in the first consensus messages are determined to be 1, and the initial vote value 1 can be added to the first round voting set bset₀If the vote value 1 is determined to be added to the first round voting set bset at this time₀If so, the priority vote value 1 is determined to be the main vote value.

In the above manner, the main vote value can be determined based on the local initial vote value and the initial vote values broadcast by other consensus nodes in the initial round of consensus.

And S303, determining a head-round final voting value based on the determined head-round main voting value and the head-round main voting values broadcast by other consensus nodes, and broadcasting the determined final voting value to other consensus nodes by using a reliable broadcast RBC protocol.

In this step, the target node may add the master vote value to the second consensus message aux₀The target node may also receive the main vote value broadcast by other consensus nodes, and in order to avoid malicious nodes from intentionally sending false votes, the target node may perform validity verification on the received first-round main vote value based on the first-round voting set, specifically, may be performed after receiving the main vote value broadcast by any one of the consensus nodesAnd after the main voting value is obtained, judging whether the main voting value is in a local first-round voting set, if so, indicating that the second consensus message is legal, namely the main voting value carried by the second consensus message is legal, and if not, indicating that the main voting value carried by the second consensus message is illegal.

The final vote value may be determined in this step in the following manner:

if the target node determines that the local first-turn main voting value is the priority voting value, determining that the final first-turn main voting value is the priority voting value;

for example, if the main vote value of the local broadcast is determined to be the priority vote value 1, then the top round final vote value is also determined to be the priority vote value 1.

In addition, if the local first-round main voting value is other voting values 0, carrying out validity verification on the received first-round main voting values broadcast by other consensus nodes based on the first-round voting set; in the event that N-f legitimate first-turn dominant vote values are received, a final vote value is determined based on the N-f legitimate first-turn dominant vote values.

The method specifically comprises the following steps: if the N-f legal first-turn main voting values are determined to be the same, determining the N-f main voting values as final voting values; if the N-f legitimate first-turn main vote values are not exactly the same, then the final vote value is determined to be a predefined value different from the priority vote value and the other vote values.

For example, if the received N-f legal primary vote values are all 1, the final vote value is determined to be 1. In another example, if some of the received N-f legal primary vote values are 1, and some are 0, the final vote value is determined to be x (, which is a predefined value).

After the final vote value is determined, the final vote value may be broadcast to other consensus nodes using the reliable broadcast RBC protocol, and in this step, the reliable broadcast RBC protocol may be implemented based on various implementation manners.

In addition, in order to improve security and achieve quantum attack resistance, quantum-secure RBCs may be used to broadcast vote values, for example, Bracha's broadcast or AVID RBCs may be used, and the binary consensus method provided in this specification may have quantum security by using this kind of reliable broadcast RBC protocol.

Further, in order to achieve unconditional security or information theory security, an unconditional secure reliable broadcast RBC protocol may be used to broadcast the vote value, for example, a Bracha's broadcast RBC protocol may be used, and the reliable broadcast RBC protocol is used to broadcast, so that the security of the consensus process is further improved no matter how strong the computation capability of the adversary is, the broadcast RBC protocol cannot be broken.

In the above S204, specifically, the consensus condition of the proposal to be consensus-identified may be determined based on the received initial final vote value broadcast by other consensus nodes, before that, validity verification still needs to be performed on the received final vote value, which may be that when the received final vote value is 0 or 1, if the final vote value is determined to be in the local initial voting set, the final vote value is determined to be legal, otherwise, the final vote value is determined to be illegal. If the received final voting value is a (predefined value), if the local first-round voting set comprises the prior voting value 1 and other voting values 0, the final voting value is determined to be legal, otherwise, the final voting value is determined to be illegal.

After the received final vote value is legally verified, the consensus condition can be determined under the condition that the N-f legal initial rounds of final vote values are received.

Specifically, under the condition that N-f legal initial-round final vote values are received, if the N-f initial-round final vote values are all the same, are priority vote values or other vote values, the N-f initial-round final vote values are determined to be the consensus result of the to-be-consensus proposal, and the N-f initial-round final vote values are determined to be the pre-vote values of the next consensus.

For example, if the final vote values of the received N-f legal initial rounds are all 1, the 1 is determined as the consensus result of the proposal to be consensus. After the consensus result is obtained, the target node still participates in the next round of consensus, and 1 can be determined as the pre-vote value of the next round of consensus.

In addition, if the values of the N-f initial final votes are not all the same, and there are f +1 initial final votes which are the same, are priority votes or other votes, determining the f +1 initial final votes as the next-round consensus pre-votes;

for example, if the values of the received N-f legal initial rounds of final votes are not all the same, where f +1 is 1, and there are no 2f +1 identical values, the target node determines that the initial round does not obtain the consensus result of the proposal to be consensus-identified, and therefore performs the next round of consensus, and determines 1 as the pre-vote value of the next round of consensus, and starts to perform the next round of consensus.

In addition, if f +1 identical vote values do not exist in the final vote values of the N-f legal initial rounds, the prior vote value is determined as the pre-vote value of the next round of consensus.

For example, if there are no f +1 vote values in the received N-f legal initial-round final vote values that are the same, the target node determines that the initial round does not obtain the consensus result of the proposal to be consensus-identified, and therefore to execute the next round of consensus, determines the priority vote value 1 as the pre-vote value of the next round of consensus, and starts executing the next round of consensus.

It can be understood that, in the initial consensus process, when determining that the local current vote value is the priority vote value, any consensus node directly sends the next-stage vote, and the value of the next-stage vote is also the priority vote value, for example, when determining that the local initial vote value is the priority vote value and broadcasting the initial vote value to other consensus nodes, the target node directly broadcasts the main vote value with the priority vote value to other consensus nodes, so that when determining the consensus result of the to-be-consensus proposal based on the final vote value broadcast by each consensus node, the general probability can achieve consensus based on the priority vote value, that is, the general probability can determine that the consensus result of the to-be-consensus proposal is the priority vote value, and the efficiency of achieving consensus on the priority vote value is high.

The above-mentioned S201 to S204 are the first round of consensus, and the following describes other round of consensus:

in the case that the first round does not achieve the consensus, the loop may be started to perform other rounds of consensus, which are shown in fig. 4, i.e., S401-S402, until a preset stop condition is reached:

s401, broadcasting the polling value of the current round to other nodes in the N common identification nodes based on a reliable broadcast RBC protocol;

s402, determining the consensus situation of the proposal to be consensus based on the received vote values of the current round broadcasted by other consensus nodes.

In 401, that is, in the other consensus rounds except the first round, the consensus nodes are all broadcast triple vote values, that is, broadcast pre-vote values, main vote values, and final vote values, and a reliable broadcast RBC protocol may be adopted when the triple vote values are broadcast.

Thus, a specific embodiment of S401 may be:

s401a, broadcasting the pre-voting value of the round to other consensus nodes;

s401b, determining a main voting value of the current round based on the pre-voting values of the current round broadcast by other consensus nodes, and broadcasting the determined main voting value to other consensus nodes;

s401c, determining the final vote value of the current round based on the main vote value of the current round broadcast by other consensus nodes, and broadcasting the determined final vote value to other consensus nodes by using a reliable broadcast RBC protocol.

S401a can refer to S301 above, and will not be described in detail here, except that the pre-vote in this step is determined based on the above round consensus result, and the pre-vote in S301 is an initial vote, and the process of determining the initial vote can refer to the following.

In S401b, specifically, if the target node receives f +1 first consensus messages in the current consensus round and parses f +1 pre-vote values, that is, the first consensus messages exceeding the number of malicious nodes, if the f +1 pre-vote values are the same and different from the pre-vote value broadcast in the local round, the target node modifies the local pre-vote value to the vote value corresponding to the f +1 pre-vote values in the local round, and broadcasts the modified pre-vote value again. For example, if the target node receives f +1 bvals_rAnd the f +1 pre-vote values carried in the f +1 messages are all 1, and the pre-vote value which has been broadcast once through the first consensus message in the current round of consensus of the target node is 0, which is different from the f +1 pre-vote values, namely the local pre-vote value in the current round of consensus can be modified to be 1, and the pre-vote value with the value of 1 is broadcast through the first consensus message again. This step is intended to allow the local node to correct the local pre-vote value.

In this step, the target node may add, to the voting set of the current round, the voting value corresponding to the 2f +1 current round of pre-voting values when receiving the 2f +1 first consensus messages, that is, the 2f +1 current round of pre-voting values, broadcast by other consensus nodes, and the 2f +1 current round of pre-voting values are all the same; and determines the value that was first added to the current round of voting sets as the current round of master voting values.

For example, the target node receives 2f +1 first consensus messages, analyzes the received first consensus messages, and determines that the pre-vote values carried in the received first consensus messages are all 1, so that the pre-vote value 1 may be added to the round voting set bset_rIf it is determined that 1 is the first to be added to the voting set bset at this time_rAnd if the value is the median value, determining that 1 is the main voting value.

In the above manner, the main vote value may be determined based on the received pre-vote value, and after the determination, the main vote value may be broadcast through the second consensus message.

In S401c, the target node may add the master vote value to the second consensus message aux_rThe second consensus information is legal, that is, the main vote value carried by the second consensus information is legal, if the main vote value carried by the second consensus information is not legal, and if the main vote value carried by the second consensus information is not legal, the target node receives the main vote value broadcast by other consensus nodesAnd (4) legality.

Under the condition that the N-f main vote values in the legal round are received, the final vote value can be determined based on the N-f main vote values in the legal round, and the method specifically includes: if the main voting values of the N-f legal current rounds are the same, determining the voting values corresponding to the N-f main voting values as final voting values; if the main voting values of the N-f legal rounds are not all the same, the final voting value is determined to be a predefined value different from the priority voting value and other voting values.

After the final vote value is determined, the final vote value may be broadcast to other consensus nodes using the reliable broadcast RBC protocol, and in this step, the reliable broadcast RBC protocol may be implemented based on various implementation manners. Similarly, in order to further improve the security, the RBC protocols in other rounds and the RBC protocol in the first round of consensus may be set to be unconditionally secure reliable broadcast RBC protocols or quantum secure reliable broadcast RBC protocols, where the reliable broadcast RBC protocols used in the first round of consensus and the other rounds of consensus are the same.

In the above S402, specific contents may refer to the contents of the above S204, and details are not described here, except that if f +1 identical vote values do not exist in the N-f legal initial-round final vote values received by the target node, a local coin throwing value is determined, and the local coin throwing value is determined as a pre-vote value identified in the next round, where the local coin throwing value is randomly determined by the target node, and may be a priority vote value or another vote value. For example, if there are no f +1 votes in the N-f legal current rounds of final votes that are the same, the target node determines that the current round does not obtain the consensus result of the proposal to be consensus, and therefore, to execute the next round of consensus, the target node randomly determines the local coin throwing value, determines the local coin throwing value as the pre-cast value of the next round of consensus, and starts to execute the next round of consensus. In the step, each consensus node determines the local money throwing value, and does not need to interact with other consensus nodes to obtain the public money throwing value, so that any encryption mechanism or encryption algorithm is not needed.

The above-mentioned S401-S402 are processes executed in each round of consensus except the first round, and when a preset stop condition is not reached, the S401-S402 are executed in a loop, where the preset stop condition may be that it is determined that the consensus result of the proposal to be consensus has been obtained in the previous round of consensus, and the current round has sent the final vote; and a stop instruction sent by a user can be received. In addition, the target node only obtains one consensus result for one pending consensus proposal, and does not obtain the consensus result again although participating in the next round of consensus after obtaining the consensus result, i.e. if any consensus node obtains the consensus result for one pending consensus proposal in the current round of consensus, the next round of consensus only performs S401, but not S402.

It can be understood that in each round of consensus process in this specification, three kinds of messages are respectively used for broadcasting for the pre-vote, the main vote and the final vote, so that each consensus node can determine the type of the received message to distinguish different types of votes, and this specification does not limit the specific type of each message. In addition, in addition to the pre-vote value, each consensus node can only broadcast a main vote value and a final vote value once during each round of consensus.

In the above consensus method, because each consensus node randomly determines a local rejection value as a pre-vote value for the next round of consensus when the consensus node does not reach the consensus in one round of consensus, it is not necessary to use cryptography to interact with other consensus nodes to generate a public rejection value (it is not necessary to use a cryptography principle to perform multiple interactions to obtain a common rejection value), therefore, in the above consensus method, if the reliable broadcast RBC protocol used is an unconditional secure RBC protocol, the consensus process of the above binary consensus method is independent of any cryptography assumption and only depends on an authentication channel, and thus is also unconditional secure (information-reliability secure).

The method is executed by any correct node in the consensus nodes, and other correct consensus nodes also execute the method asynchronously. In each round of consensus, the node only needs to broadcast the consensus information three times, and only needs to broadcast the consensus information three times by adopting a reliable broadcast RBC protocol, so that the safety of the consensus process can be effectively ensured, and the consensus efficiency can be ensured.

Meanwhile, the consensus method can ensure that the consensus nodes in the distributed system meet the following properties, namely the following technical effects: effectiveness: under the condition that the voting values broadcast by all correct nodes are v and other voting values are not broadcast again, the consensus results of all correct nodes are the voting values v; and (5) consistent termination: under the condition that the voting values broadcast by all correct nodes are the same value v and other voting values are not broadcast again, all correct nodes can terminate consensus operation, namely consensus is achieved; consensus property: if any correct node determines that a certain voting value v is a consensus result, other correct nodes terminating the consensus operation also determine that the voting value v is the consensus result; biased effectiveness: if f +1 correct nodes broadcast the voting value v, the correct nodes can determine that the voting value v is a consensus result when the consensus is terminated; terminating with bias: if Q is the set of correct nodes, where Q1 is the set of correct nodes that broadcast a vote value of 1 without rebroadcasting a vote value of 0, Q2 is the set of correct nodes that broadcast a vote value of 0 and rebroadcast a vote value of 1, if

And Q1 ═ Q2, then all correct nodes agree; integrity: the correct node agrees only once with a proposal.

Taking a blockchain scene as an example, a reprint binary consensus method based on reliable broadcast in the present specification is described below, and in the blockchain scene, the reprint binary consensus method based on reliable broadcast and a reliable broadcast RBC protocol may be combined to form a byzantine fault-tolerant method for solving a data consensus problem in a blockchain network, based on which, the present specification proposes a byzantine fault-tolerant method, which is applied to the distributed system, that is, any consensus node in the blockchain network, and the method includes:

acquiring the current to-be-identified proposal in a preset mode, and broadcasting the to-be-identified proposal to other common nodes by using a reliable broadcast RBC protocol;

for the candidate consensus proposal of any consensus node, determining the consensus result of the candidate consensus proposal by using the reliable broadcast-based re-voted binary consensus method.

It can be understood that each consensus node may maintain its own transaction pool locally, since each consensus node will receive the transaction requested by the client. After the target node acquires the transaction, the acquired transaction can be packaged into the current proposal to be identified. After the target node obtains the local to-be-identified proposal, the target node can broadcast the local to-be-identified proposal to other common identification nodes based on the reliable broadcast RBC protocol, and can receive the to-be-identified proposal broadcast by other common identification nodes based on the reliable broadcast RBC protocol.

The preset mode may be to randomly obtain a preset number of transactions from the local transaction pool, or to obtain a preset number of transactions from the local transaction pool in sequence. Of course, it is also possible to combine multiple acquisition modes: for example, it may be determined whether the number of consecutive times of acquiring transactions in a random acquisition manner reaches a preset number; if yes, determining that the plaintext transaction of the preset quantity stored in the local transaction pool earlier is acquired at this time and used as a proposal to be identified; if not, determining that the plaintext transaction of the preset quantity stored in the local transaction pool is randomly acquired at this time as the proposal to be identified. For example, a preset number of times may be set to 5, and if the transactions have been obtained in a random obtaining manner during 5 consecutive consensus processes, the transactions are obtained in a sequential selection manner this time, and the next consensus process is selected in a random selection manner, and recording of the consecutive number of times is restarted.

By adopting the combined mode, the random mode is adopted to carry out acquisition under most conditions, so that the situation that the same transaction is not acquired as much as possible as a proposal to be identified when each identified node is identified can be ensured, meanwhile, because the transaction is acquired in a plaintext mode, in order to avoid the malicious node from intentionally doing harm, namely, some transactions are not acquired intentionally to achieve identification, the random acquisition mode is switched to the sequential acquisition mode at the preset time node, and each identified node can acquire the transactions which are stored in the transaction pool earlier and are not identified all the time to carry out identification.

After each consensus node broadcasts the to-be-consensus proposal based on the reliable broadcast RBC protocol, an initial vote value of the to-be-consensus proposal can be determined based on the condition of receiving the to-be-consensus proposal aiming at any to-be-consensus proposal, further, the initial vote value can be adopted to continue to execute the initial consensus process of the re-voted binary consensus method based on the reliable broadcast, and when the initial consensus is not achieved, other rounds of consensus processes are continued to be executed until a preset stop condition is reached.

The determination of the initial vote value for the to-be-consensus proposal based on the condition of receiving the to-be-consensus proposal may specifically be:

under the condition that any consensus node receives a to-be-consensus proposal broadcast by reliably broadcasting an RBC protocol, if a consensus process is not started to be executed for the to-be-consensus proposal, namely, a two-element consensus method which can vote again and is proposed by the specification is not yet determined, or an initial vote value of the to-be-consensus proposal is not yet determined, determining the initial vote value of the to-be-consensus proposal as a priority vote value 1;

under the condition that the proposals to be consensus broadcasted by the N-f consensus nodes are received, determining the initial vote value of the proposals to be consensus which do not start to execute the consensus process as other vote values 0;

in addition, when the target node receives the to-be-consensus proposal broadcast by any consensus node through the reliable broadcast RBC protocol, if the consensus process is started to be executed for the to-be-consensus proposal and the consensus result of the to-be-consensus proposal is not obtained yet, the initial vote value of the to-be-consensus proposal is determined to be the priority vote value 1 again.

In this embodiment, in the case of receiving the to-be-consensus proposals broadcasted by the N-f consensus nodes, the initial vote value of the to-be-consensus proposal not yet starting to perform the consensus process is determined as the other vote value 0, and the reliable broadcast RBC protocol can ensure that the target node receives only one time when receiving any one of the to-be-consensus proposals, rather than receiving the same to-be-consensus proposal multiple times, therefore, after receiving any one of the to-be-consensus proposals, if the consensus process has already started for the to-be-consensus proposal, it is stated that the execution is started with the other vote value 0 as the initial vote value, and further, the initial vote value can be modified from the other vote value 0 to the prior vote value 1. Namely, the preset condition in S202 may be configured as: if the proposal to be agreed upon is received, and the consensus result of the proposal to be agreed upon is not obtained yet.

Taking N as 7 and f as 2 as an example, after receiving a to-be-consensus proposal broadcast by any consensus node, the target node determines whether to start performing a consensus process for the to-be-consensus proposal, if not, determines an initial vote value of the to-be-consensus proposal as a priority vote value 1, and continues to perform the re-voted binary consensus method provided in this specification to obtain a consensus result for the to-be-consensus proposal. In addition, when it is determined that N-f, that is, 7-2, to the to-be-consensus suggestions broadcasted by 5 consensus nodes are received, that is, the consensus process has started to be performed for the 5 to-be-consensus suggestions respectively with the priority vote value 1 as an input, the initial vote value of the remaining 2 to-be-consensus suggestions for which the consensus process has not started to be performed may be determined as the other vote value 0, and the consensus process may be started to be performed for the remaining 2 to-be-consensus suggestions. Meanwhile, after receiving the to-be-consensus proposal broadcast by any consensus node, if the consensus process is started for the to-be-consensus proposal, the initial vote value of the to-be-consensus proposal is other vote values 0, and the consensus result of the to-be-consensus proposal is not obtained yet, the target node determines the initial vote value of the to-be-consensus proposal as the priority vote value again.

As shown in fig. 5, there are 7 common nodes in the blockchain network, and each common node needs to be sent for 7 common nodesThe consensus proposals respectively reach consensus, as shown in the figure, 7 pairs of RBC + RABA instances need to be maintained, where RABA is a reliable broadcast-based re-voted binary consensus method proposed in this specification, where N is 7, f is 2, and the target node starts to execute a re-voted binary consensus algorithm RABA respectively for the to-be-consensus proposals of nodes 0 to 4 after receiving the 5 to-be-consensus proposals of nodes 0 to 4 through a reliable broadcast RBC protocol, that is, RABA₀-RABA₄Are set to 1 (priority vote value) and start execution, and RABAs corresponding to nodes 5 and 6 are directly input₅And RABA₆Is set to 0 (other vote value) and starts execution, i.e. in case of receiving the last one of the N-f consensus nodes' consensus proposals to be agreed upon, it starts triggering the start of execution of the remaining f consensus proposals that have not started execution of the RABA, as shown in the figure, starting RABA execution at node 3 with 1 as input₃Then RABA is added₅And RABA₆Are all set to 0, triggers the start of the execution of the RABA₅And RABA₆. In addition, RABA for node 5 and node 6₅And RABA₆After the input of (1) is set to 0, and no RABA has been obtained yet₅And RABA₆When the result is output, if the co-recognition proposals to be received by the node 5 and the node 6 are received again, the RABA can be used₅And RABA₆Is changed to 1, again triggers execution of the RABA₅And RABA₆To obtain RABA₅And RABA₆And outputting the result. By adopting the mode, the binary consensus process of each consensus proposal to be treated is basically processed and generated in parallel, and the consensus efficiency is further improved.

It will be appreciated that the above approach is merely an approach to determining an initial vote value in a blockchain network, and that in other distributed system scenarios, the initial vote value for a proposal to be consensus may also be determined from different data.

The present specification proposes that in order to enable each consensus node to quickly achieve consensus on the priority vote value in the initial consensus process, the target node is allowed to determine the initial vote value as the priority vote value again if it is determined that the predetermined condition is satisfied under the condition that the determined initial vote value is another vote value, and then perform the consensus process again. And under the condition that the preset conditions are not met, the target node is not allowed to modify the initial voting value, and different preset conditions can be flexibly configured in different application scenes of the distributed system. It can be understood that the above description only takes the application scenario of the blockchain network as an example, and in other application scenarios, different preset conditions may be configured according to different scenario requirements.

In a specific embodiment, in order to implement quantum security, the reliable broadcast RBC protocol used by each consensus node to broadcast the to-be-consensus proposal and the broadcast vote value may be a quantum-secure reliable broadcast RBC protocol, for example, the Bracha's broadcast and AVID RBC protocols may be used.

In a specific embodiment, the following specific implementation may be adopted to implement a reliable broadcast RBC protocol with quantum security, and the following describes a process of broadcasting a pending consensus proposal by using the AVID RBC protocol:

the target node can adopt erasure code processing to the proposal to be identified to obtain N data blocks; constructing a Merckel tree based on the obtained Hash values of the N data blocks to obtain root Hash and a Merckel proof of a Merckel path corresponding to each data block; and storing part of the N data blocks locally, and sending the Merckel paths corresponding to other data blocks, the root hash and other data blocks to other consensus nodes so that the other consensus nodes broadcast and verify the data blocks. As shown in fig. 6, taking a total of 4 consensus nodes (consensus node 1-consensus node 4) as an example, a target node is consensus node 1, where the consensus node 1 splits a local proposal to be consensus into 4 data blocks, namely data block 1-data block 4, after erasure code processing, Hash operation is performed on the 4 data blocks by using a preset Hash algorithm to obtain Hash values of the 4 data blocks, a merkel tree is constructed based on the Hash values of the 4 data blocks, the Hash value of the data block 1 is Hash1, the Hash value of the data block 2 is Hash2, the Hash value of the data block 3 is Hash3, the Hash value of the data block 4 is Hash4, Hash values of Hash1 and Hash2 are calculated to obtain Hash12, Hash3 and Hash4 are calculated to obtain Hash34, and Hash12 and Hash34 are calculated to obtain a root Hash tree, thereby obtaining the merkel tree. It is understood that the above is only 4 nodes, and in practical applications, a more complex merkel tree can be constructed according to different numbers of common nodes. After the mercker tree is constructed, the consensus node 1 can store the data block 1 locally, and send the data block 2, the Hash1, the Hash34 and the root Hash to the consensus node 2; sending the data block 3, the Hash4, the Hash12 and the root Hash to the consensus node 3; the data block 4, Hash3, Hash12 and root Hash are sent to the consensus node 4. Taking the content sent to the consensus node 2 as an example, the Hash1 and the Hash34 are the mercker certificates of the mercker paths corresponding to the data block 2. The consensus node 1 may send the above content to other consensus nodes in the format of a Rval message. After receiving the content sent by the consensus node 1, the other consensus nodes may broadcast the content to the other consensus nodes in an Echo message format. After receiving the Echo message, other common identification nodes may verify whether the message is legal, specifically, after receiving the message, for a data block in the message, verify by using a mercker certificate and a root hash of a mercker path corresponding to the data block; if the verification passes, the message is determined to be legitimate.

Continuing with the above example, after receiving the Echo message, the consensus node 3 determines that the message content is: the data block 4, the Hash3, the Hash12 and the root Hash can be calculated to obtain a Hash4, the Hash4 and the received Hash3 are calculated to obtain a Hash34, the Hash34 and the received Hash12 are calculated to obtain the root Hash, if the calculated root Hash is the same as the received root Hash, the Echo message is legal, and if the verification fails, the Echo message can be directly discarded to avoid tampering the message by a malicious node.

By the above-mentioned method, the consensus node 2-the consensus node 4 can receive all data blocks sent by the consensus node 1 (the target node) (in the case that no node intentionally sends no data block), any node can select any N-2f data blocks to restore the proposal to be consensus after receiving N-f Echo messages and under the condition that the N-f Echo messages are verified to pass, and can reconstruct the merkel tree, compare whether the root Hash of the reconstructed merkel tree is consistent with the root Hash in the previously received Echo, and broadcast the Ready message if the root Hash is consistent.

It can be understood that, although the target node 1 is described as an example, in the consensus method shown in this specification, each consensus node has no primary or secondary part, that is, any consensus node is a target node, and any consensus node can obtain a to-be-consensus proposal of other consensus nodes in the above manner; any consensus node sends the local to-be-consensus proposal to other consensus nodes in the above manner.

Each consensus node can send out local to-be-consensus suggestions at the same time, so that the target node may receive the to-be-consensus suggestions sent by different consensus nodes in sequence. After receiving the proposal to be consensus from other consensus nodes, the target node can determine the initial vote value of the proposal to be consensus.

The above method is a process of broadcasting the consensus proposal by using one of the specific quantum-safe RBC broadcasting protocols. Because the reliable broadcast RBC protocol adopts a hash algorithm, the reliable broadcast RBC protocol is quantum-safe.

In addition, in order to further improve the security, the reliable broadcast RBC protocol used by each consensus node for broadcasting the candidate consensus proposal and the broadcast vote value may be an unconditionally secure reliable broadcast RBC protocol, for example, a Bracha's broadcast protocol may be adopted.

It can be understood that if the combined manner of obtaining clear text transactions (i.e. random + sequential) proposed above in this specification is adopted, i.e. the transactions are not encrypted, and if the reliable broadcast RBC protocol used by each consensus node to broadcast the candidate consensus proposal and the broadcast vote value is unconditionally safe, the overall byzantine fault-tolerant method is unconditionally safe.

Similarly, if the combination method for obtaining plaintext transaction (i.e. random + sequential) proposed above in this specification is adopted, and if the reliable broadcast RBC protocol used by each consensus node to broadcast the proposal to be consensus and the broadcast vote value is a quantum-safe reliable broadcast RBC protocol, the overall byzantine fault-tolerant method is quantum-safe.

By adopting the Byzantine fault-tolerant method, N consensus results can be respectively obtained aiming at the proposals to be agreed proposed by N consensus nodes in the block chain network, and after the consensus results of the N proposals to be agreed are obtained, a set consisting of at least one proposal to be agreed with the consensus result as a priority vote value is determined as a set to be agreed; after all the to-be-consensus suggestions in the set are received, the to-be-consensus suggestions in the set are executed according to a preset sequence.

For example, after the consensus proposals made for all consensus nodes have agreed, each correct consensus node will get the same consensus result, resulting in a sequence comprising 0 and 1, e.g. co-existing at 7 consensus nodes P₁-P₇In which P is₁-P₆The consensus results for the corresponding 6 consensus proposals are 1, P₇If the consensus result of the corresponding proposal to be consensus is 0, then P is determined₁-P₆The corresponding set composed of the proposals to be identified is the set to be identified S, and at this time, any correct node to be identified will obtain such a set to be identified, but it may not receive some proposals to be identified in the set to be identified S yet, because it is the proposal to be identified broadcast by the reliable broadcast RBC protocol, it can be ensured that the node to be identified can receive all proposals to be identified in the set to be identified S certainly, based on which, the node to be identified can wait continuously, and after receiving all proposals to be identified in the set to be identified S, it can execute all proposals to be identified in the set to be identified S according to the preset execution sequence, i.e. execute P₁-P₆Is proposed.

In a blockchain network, 0 or 1 is used to indicate whether the corresponding consensus proposal is packed into blocks. For example, there are four consensus nodes, the consensus suggestion proposed by the consensus node 1 is P1, the consensus suggestion proposed by the consensus node 2 is P2, the consensus suggestion proposed by the consensus node 3 is P3, the consensus suggestion proposed by the consensus node 4 is P4, a 01 sequence is obtained after consensus is performed by using the above-mentioned byzantine fault-tolerant method, for example, the obtained sequence is (1,1,1,0), and the consensus result is that all the nodes pack P1, P2, and P3 into blocks and store the blocks in the local and non-storage P4, that is, each consensus node performs consistency processing on each consensus suggestion according to the consensus result, so as to ensure data consistency of each consensus node.

A specific embodiment of the reliable broadcast-based two-dimensional recognition method for re-voting in the present specification is described below from the viewpoint of code implementation:

the pseudo code is as follows:

in the above pseudo-code, for any b e {0,1},

in a message as a parameter, a symbol other than 0 and 1, e.g. final-vote_r() indicates that the vote was neither a vote for 0 nor a vote for 1; bset_rA vector (poly set) consisting of 0,1 and ≠ t; random () is a Random function, randomly generating 0 or 1.

(1) In the consensus 0 round, we define a new function broadcast-volume (v), which is triggered only in round 0. Once pro (v) is triggered, the broadcast-volume (v) function is launched and round 0 is started in succession. Once reprocess (v) is initiated, if the copy p_iStill in round 0, the broadcast-volume (v) function is started successively. Since consensus methods prefer to vote for 1, all correct copies will execute reprocess (1) only if process (0) was executed before.

(2) We define that the broadcast-vote (v) function triggers only at round 0, with the copy broadcasting a pre-vote₀(v) In that respect If v is 1, copy p_iAdding 1 to the set bset₀. If the copy has not previously broadcast a master votemain-vote₀(1) If yes, execute the broadcast main-vote₀(1) Operating; if the final voting vote-vote is not broadcast before the copy₀(1) Then RBC broadcast final-vote is executed₀(1) And (5) operating.

(3) Because each copy only broadcasts main-votes in each round_r() And final-vote_r() Once, we add some restrictions in the second and third stages. One copy if the main vote main-vote has not been broadcast before_r() Broadcast main-vote once_r() (ii) a Similarly, if a copy has not previously broadcast final-votes_r() Broadcast the final-vote once_r() (ii) a The common coin throw result of round 0 is set to 1 by default.

In other consensus rounds, each round is divided into three phases:

first stage

(1) Copy p_iInput iv for its r-th round_rBroadcast pre-vote_r(iv_r) Wherein iv is_r∈{0,1}。

(2) When the copy p_iF +1 pre-votes are received for the same value v in the same round number r_r(v) And no prior pre-votes for v in r rounds have been broadcast, copy p_iThe pre-vote is broadcast.

(3) When the copy p_i2f +1 pre-votes are received for the same value v in the same round number r_r(v) Then v is inserted into the set bset_rWherein bset_rIs a set consisting of 0 and 1.

Second stage

(1) When set bset_rNot null, copy p_iGet best_rAs v, broadcasts the main vote main-vote_r(v) In that respect A correct copy is accepted by the main vote-vote_r(v) If and only if v has been inserted before into the local set bset_rIn (1).

(2) When the copy p_iReceiving main votes main-votes from N-f different copies_r() And entering the third stage.

The third stage

(1) When the copy p_iReceiving N-f main votes of the same v in the same round number r_r(v) At message time, r-broadcast final vote final-vote for v in r round_r(v) Otherwise copy p_ir-final vote final-vote broadcast in r round_r(. 1) wherein

Is a symbol different from 0 and 1.

Final voting final-vote_r() The copy pi is valid only in the following cases:

for a vote final-vote_r(v) The copy pi has inserted v into bset_r

For final-vote_r(. about.), copy p_iBset of_rContaining 0 and 1

(2) When the copy p_ir-deliverer N-f final votes

A. If the N-f final votes for the same v in the same round number r, determining the v, and taking the v as the input of the next round;

B. if more than f +1 final votes for the same v in the same round number r exist, taking v as the input of the next round;

C. otherwise, a random number is generated as the input of the next round.

As shown in fig. 7, corresponding to the foregoing reliable broadcast-based two-element consensus voting method, the present specification further provides a reliable broadcast-based two-element consensus voting apparatus, which is applied to any one consensus node in a distributed system, where N is greater than or equal to 3f +1, and f is an integer greater than 0, and the apparatus includes:

a processing module 710, configured to determine, for a to-be-consensus proposal of any consensus node, an initial vote value of the to-be-consensus proposal; wherein, the initial voting value is a priority voting value or other voting values; under the condition that the initial voting value is other voting values and meets a preset condition, determining the initial voting value as a priority voting value again;

a communication module 720, configured to broadcast the first-round vote value to other nodes of the N consensus nodes based on a reliable broadcast RBC protocol;

the processing module 710 is further configured to determine a consensus condition of the to-be-consensus proposal based on the first-round vote values broadcast by the other consensus nodes.

In one embodiment, the processing module 710 is further configured to, in a case that the first round does not agree on the preferred vote value, cyclically execute other rounds of agreement steps until a preset stop condition is reached;

in other rounds of consensus steps:

the communication module 720 is configured to broadcast the polling value of the current round to other nodes of the N common nodes based on a reliable broadcast RBC protocol;

the processing module 710 is configured to determine a consensus condition of the to-be-consensus proposal based on the received vote values of the current round broadcasted by the other consensus nodes.

In one embodiment, the communication module 720 is configured to broadcast the initial vote value to other consensus nodes; invoking the processing module 710 to determine a first-round main voting value based on the initial voting value and the initial voting values broadcast by other consensus nodes, and broadcasting the determined first-round main voting value to other consensus nodes; invoking the processing module 710 to determine a head-round final vote value based on the determined head-round main vote value and the head-round main vote values broadcast by other consensus nodes, and broadcasting the determined final vote value to other consensus nodes by using a reliable broadcast RBC protocol.

In one embodiment, the reliable broadcast RBC protocol is an unconditionally secure reliable broadcast RBC protocol.

In an embodiment, the processing module 710 is configured to, when f +1 initial vote values broadcast by other consensus nodes are received, where the f +1 initial vote values are all the same and different from the initial vote value broadcast in the local round, modify the local initial vote value to a vote value corresponding to the f +1 initial vote values, and broadcast the modified initial vote value again.

In one embodiment, the processing module 710 is configured to add the priority vote value to the first-round voting set if the local initial vote value is the priority vote value, and determine the priority vote value as the first-round main vote value; if the initial voting values are other voting values, adding values corresponding to the 2f +1 initial voting values into a first-round voting set under the condition that 2f +1 initial voting values broadcasted by other consensus nodes are received and the 2f +1 initial voting values are all the same; and determines the vote value that was first added to the first-round voting set as the first-round master vote value.

In one embodiment, the processing module 710 is configured to determine that the initial final vote value is a priority vote value if the local initial main vote value is a priority vote value;

if the local first-round main voting value is other voting values, carrying out validity verification on the received first-round main voting values broadcasted by other consensus nodes based on the first-round voting set;

in the event that N-f legitimate first-turn dominant vote values are received, a final vote value is determined based on the N-f legitimate first-turn dominant vote values.

In an embodiment, the processing module 710 is configured to determine, if the N-f legal first-turn main vote values are all the same, that a value corresponding to the N-f main vote values is a final vote value; and if the N-f legal first-turn main voting values are not identical, determining that the final voting value is a predefined value different from the priority voting value and other voting values.

In one embodiment, the processing module 710 is configured to perform validity verification on the received current round final vote value based on the current round vote set;

under the condition that N-f legal initial-round final voting values are received, if the N-f initial-round final voting values are all the same and are priority voting values or other voting values, determining the voting values corresponding to the N-f initial-round final voting values as consensus results of the proposal to be identified, and determining the voting values corresponding to the N-f initial-round final voting values as pre-voting values of next-round consensus;

if the final voting values of the N-f legal initial rounds are not completely the same, and f +1 initial rounds have the same final voting value and are priority voting values or other voting values, determining the voting value corresponding to the f +1 initial rounds as a pre-voting value identified in the next round;

and if f +1 identical voting values do not exist in the final voting values of the N-f initial rounds, determining the priority voting value as a pre-voting value identified in the next round.

In an embodiment, the communication module 720 is specifically configured to broadcast the round of pre-voting values to other consensus nodes;

the processing module 710 is specifically configured to determine a main voting value of the current round based on the pre-voting values of the current round broadcast by other consensus nodes;

the communication module 720 is specifically configured to broadcast the determined master vote value to other consensus nodes;

the processing module 710 is specifically configured to determine a final vote value of the current round based on the main vote values of the current round broadcast by the other consensus nodes;

the communication module 720 is specifically configured to broadcast the determined final vote value to other consensus nodes by using a reliable broadcast RBC protocol.

The processing module 710 is specifically configured to modify the local pre-vote value to a value corresponding to the f +1 local pre-vote values if f +1 local pre-vote values broadcasted by other common identification nodes are received, where the f +1 local pre-vote values are all the same and different from the local pre-vote value broadcasted by the local node, and re-broadcast the modified pre-vote value.

In an embodiment, the processing module 710 is specifically configured to, when 2f +1 current round of pre-vote values broadcast by other consensus nodes are received and the 2f +1 current round of pre-vote values are all the same, add values corresponding to the 2f +1 current round of pre-vote values to a current round of voting set; the value that was first added to the current round of voting sets is determined to be the current round of master voting value.

In an embodiment, the processing module 710 is specifically configured to perform validity verification on the received main vote value of the current round based on the voting set of the current round; and under the condition that N-f legal main voting values are received, determining a final voting value based on the N-f legal main voting values.

In an embodiment, the processing module 710 is specifically configured to determine, if the N-f legal main vote values in the round are the same, values corresponding to the N-f main vote values as final vote values; and if the main voting values of the N-f legal current rounds are not completely the same, determining that the final voting value is a predefined value different from the priority voting value and other voting values.

In an embodiment, the processing module 710 is specifically configured to, when N-f current rounds of final vote values are received, determine that a value corresponding to the N-f current rounds of final vote values is a consensus result of the to-be-consensus proposal if the N-f current rounds of final vote values are all the same, and are a priority vote value or other vote values, and determine that a value corresponding to the N-f current rounds of final vote values is a pre-vote value for next consensus. If the final voting values of the N-f current rounds are not completely the same, and f +1 current rounds have the same final voting value, are priority voting values or other voting values, determining a value corresponding to the f +1 current rounds of final voting values as a next round of consensus pre-voting value; if f +1 identical voting values do not exist in the final voting values of the N-f current rounds, randomly determining a local coin throwing value, wherein the local coin throwing value is a priority voting value or other voting values, and determining the local coin throwing value as a pre-voting value identified by the next round.

As shown in fig. 8, this specification further provides a byzantine fault-tolerant apparatus, which is applied to any one consensus node in a distributed system, where the distributed system includes N consensus nodes, where N ≧ 3f +1, and f is an integer greater than 0, and the apparatus includes:

a broadcasting module 810, configured to determine a to-be-consensus proposal of the consensus in a preset manner, and broadcast the to-be-consensus proposal to other consensus nodes by using a reliable broadcast RBC protocol;

a consensus module 820 for determining a consensus result of the candidate consensus proposal for any of the consensus nodes by using the reliable broadcast based re-voted binary consensus method according to any of claims 1-14.

In an embodiment, the broadcasting module 810 is specifically configured to determine whether the number of consecutive times of acquiring the transaction in a random acquisition manner reaches a preset number; if yes, determining that the plaintext transaction of the preset quantity stored in the local transaction pool earlier is acquired at this time and used as a proposal to be identified; if not, determining that the plaintext transaction of the preset quantity stored in the local transaction pool is randomly acquired at this time as the proposal to be identified.

In one embodiment, the reliable broadcast RBC protocol is a quantum secure reliable broadcast RBC protocol.

The implementation processes of the functions and actions of the components in the device are specifically described in the implementation processes of the corresponding steps in the method, and are not described herein again.

For the device embodiments, since they substantially correspond to the method embodiments, reference may be made to the partial description of the method embodiments for relevant points. The above-described apparatus embodiments are merely illustrative. Some or all of the modules can be selected according to actual needs to achieve the purpose of the solution in the specification. One of ordinary skill in the art can understand and implement it without inventive effort.

Embodiments of the present specification also provide a computer device, which at least includes a memory, a processor and a computer program stored on the memory and executable on the processor, wherein the processor implements the aforementioned method when executing the program. The method at least comprises the reliable broadcast-based re-voting binary consensus method or the Byzantine fault-tolerant method.

Fig. 9 is a schematic diagram illustrating a more specific hardware structure of a computing device according to an embodiment of the present disclosure, where the computing device may include: a processor 1010, a memory 1020, an input/output interface 1030, a communication interface 1040, and a bus 1050. Wherein the processor 1010, memory 1020, input/output interface 1030, and communication interface 1040 are communicatively coupled to each other within the device via bus 1050.

The processor 1010 may be implemented by a general-purpose CPU (Central Processing Unit), a microprocessor, an Application Specific Integrated Circuit (ASIC), or one or more Integrated circuits, and is configured to execute related programs to implement the technical solutions provided in the embodiments of the present disclosure.

The Memory 1020 may be implemented in the form of a ROM (Read Only Memory), a RAM (Random Access Memory), a static storage device, a dynamic storage device, or the like. The memory 1020 may store an operating system and other application programs, and when the technical solution provided by the embodiments of the present specification is implemented by software or firmware, the relevant program codes are stored in the memory 1020 and called to be executed by the processor 1010.

The input/output interface 1030 is used for connecting an input/output module to input and output information. The i/o module may be configured as a component in a device (not shown) or may be external to the device to provide a corresponding function. The input devices may include a keyboard, a mouse, a touch screen, a microphone, various sensors, etc., and the output devices may include a display, a speaker, a vibrator, an indicator light, etc.

The communication interface 1040 is used for connecting a communication module (not shown in the drawings) to implement communication interaction between the present apparatus and other apparatuses. The communication module can realize communication in a wired mode (such as USB, network cable and the like) and also can realize communication in a wireless mode (such as mobile network, WIFI, Bluetooth and the like).

Bus 1050 includes a path that transfers information between various components of the device, such as processor 1010, memory 1020, input/output interface 1030, and communication interface 1040.

It should be noted that although the above-mentioned device only shows the processor 1010, the memory 1020, the input/output interface 1030, the communication interface 1040 and the bus 1050, in a specific implementation, the device may also include other components necessary for normal operation. In addition, those skilled in the art will appreciate that the above-described apparatus may also include only those components necessary to implement the embodiments of the present description, and not necessarily all of the components shown in the figures.

Embodiments of the present specification also provide a computer-readable storage medium on which a computer program is stored, which when executed by a processor implements the foregoing method. The method at least comprises the reliable broadcast-based re-voting binary consensus method or the Byzantine fault-tolerant method.

Computer-readable media, including both non-transitory and non-transitory, removable and non-removable media, may implement information storage by any method or technology. The 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 Discs (DVD) or other optical storage, magnetic cassettes, magnetic disk storage or other magnetic storage devices, or any other non-transmission medium that can be used to store information that can be accessed by a computing device. As defined herein, a computer readable medium does not include a transitory computer readable medium such as a modulated data signal and a carrier wave.

From the above description of the embodiments, it is clear to those skilled in the art that the embodiments of the present disclosure can be implemented by software plus necessary general hardware platform. Based on such understanding, the technical solutions of the embodiments of the present specification may be essentially or partially implemented in the form of a software product, which may be stored in a storage medium, such as a ROM/RAM, a magnetic disk, an optical disk, etc., and includes several instructions for enabling a computer device (which may be a personal computer, a server, or a network device, etc.) to execute the methods described in the embodiments or some parts of the embodiments of the present specification.

The systems, devices, modules or units illustrated in the above embodiments may be implemented by a computer chip or an entity, or by a product with certain functions. A typical implementation device is a computer, which may take the form of a personal computer, laptop computer, cellular telephone, camera phone, smart phone, personal digital assistant, media player, navigation device, email messaging device, game console, tablet computer, wearable device, or a combination of any of these devices.

The embodiments in the present specification are described in a progressive manner, and the same and similar parts among the embodiments are referred to each other, and each embodiment focuses on the differences from the other embodiments. In particular, for the apparatus embodiment, since it is substantially similar to the method embodiment, it is relatively simple to describe, and reference may be made to some descriptions of the method embodiment for relevant points. The above-described apparatus embodiments are merely illustrative, and the modules described as separate components may or may not be physically separate, and the functions of the modules may be implemented in one or more software and/or hardware when implementing the embodiments of the present disclosure. And part or all of the modules can be selected according to actual needs to achieve the purpose of the scheme of the embodiment. One of ordinary skill in the art can understand and implement it without inventive effort.

The foregoing is only a specific embodiment of the embodiments of the present disclosure, and it should be noted that, for those skilled in the art, a plurality of modifications and decorations can be made without departing from the principle of the embodiments of the present disclosure, and these modifications and decorations should also be regarded as the protection scope of the embodiments of the present disclosure.

Claims

1. A two-element consensus method capable of re-voting based on reliable broadcasting is characterized by being applied to any consensus node in a distributed system, wherein the distributed system comprises N consensus nodes, N is greater than or equal to 3f +1, f is an integer greater than 0, and the method comprises the following steps:

2. The method of claim 1, further comprising:

and under the condition that the first round does not achieve the consensus on the priority voting value, circularly executing other rounds of consensus steps until a preset stop condition is achieved, wherein the other rounds of consensus steps comprise:

broadcasting the polling value of the current round to other nodes in the N common identification nodes based on a reliable broadcast RBC protocol;

and determining the consensus situation of the proposal to be consensus based on the received vote values of the current rounds broadcasted by other consensus nodes.

3. The method according to claim 1, wherein the broadcasting of the first-round vote value to other nodes of the N consensus nodes based on a reliable broadcast RBC protocol comprises:

broadcasting the initial vote value to other consensus nodes;

determining a first-round main voting value based on the initial voting value and the initial voting values broadcast by other consensus nodes, and broadcasting the determined first-round main voting value to other consensus nodes;

and determining a head-round final voting value based on the determined head-round main voting value and the head-round main voting values broadcast by other consensus nodes, and broadcasting the determined final voting value to other consensus nodes by using a reliable broadcast RBC protocol.

4. The method of claim 3, wherein before determining the first-turn master vote value based on the initial vote value and the initial vote values broadcast by other consensus nodes, further comprising:

if f +1 initial voting values broadcasted by other consensus nodes are received, wherein the f +1 initial voting values are the same and different from the initial voting values broadcasted in the local round, modifying the local initial voting values into voting values corresponding to the f +1 initial voting values, and broadcasting the modified initial voting values again.

5. The method of claim 4, wherein determining a first-turn master vote value based on the initial vote value and initial vote values broadcast by other consensus nodes comprises:

if the local initial voting value is the priority voting value, adding the priority voting value into the first-round voting set, and determining the priority voting value as a first-round main voting value;

if the initial voting values are other voting values, adding values corresponding to the 2f +1 initial voting values into a first-round voting set under the condition that 2f +1 initial voting values broadcasted by other consensus nodes are received and the 2f +1 initial voting values are all the same; and determines the vote value that was first added to the first-round voting set as the first-round master vote value.

6. The method of claim 5, wherein determining a first-round final vote value based on the determined first-round main vote values and the first-round main vote values broadcast by other consensus nodes comprises:

if the main voting value of the local first round is the priority voting value, determining the final voting value of the first round as the priority voting value;

7. The method of claim 6, wherein determining a final vote value based on the N-f legitimate first-turn dominant vote values comprises:

if the N-f legal initial-round main voting values are the same, determining the value corresponding to the N-f main voting values as a final voting value;

and if the N-f legal first-turn main voting values are not identical, determining that the final voting value is a predefined value different from the priority voting value and other voting values.

8. The method of claim 7, wherein the identifying the proposal to be identified based on the first-round vote value broadcast by the other identifying nodes comprises:

carrying out validity verification on the received final voting value of the current round based on the voting set of the current round;

9. The method according to claim 2, wherein the broadcasting the poll of the current round to other nodes of the N consensus nodes based on the reliable broadcast RBC protocol comprises:

broadcasting the pre-voting value of the round to other consensus nodes;

determining a main voting value of the current round based on the pre-voting values of the current round broadcast by other consensus nodes, and broadcasting the determined main voting value to other consensus nodes;

and determining a final voting value of the current round based on the main voting values of the current round broadcast by other consensus nodes, and broadcasting the determined final voting value to other consensus nodes by using a reliable broadcast RBC protocol.

10. The method of claim 9, wherein prior to determining the round of master vote values based on the round of pre-vote values broadcast by the other consensus nodes, further comprising:

if f +1 local round pre-voting values broadcasted by other consensus nodes are received, the f +1 local round pre-voting values are the same and are different from the pre-voting values broadcasted by the local round, modifying the local pre-voting values into values corresponding to the f +1 local round pre-voting values, and broadcasting the modified pre-voting values again.

11. The method of claim 10, wherein determining the round of master vote values based on the round of pre-vote values broadcast by the other consensus nodes comprises:

under the condition that 2f +1 current-round pre-voting values broadcasted by other consensus nodes are received and the 2f +1 current-round pre-voting values are the same, adding values corresponding to the 2f +1 current-round pre-voting values into a current-round voting set;

the value that was first added to the current round of voting sets is determined to be the current round of master voting value.

12. The method of claim 11, wherein determining the round of final vote values based on the round of master vote values broadcast by the other consensus nodes comprises:

carrying out validity verification on the received main voting value in the current round based on the voting set in the current round;

and under the condition that N-f legal main voting values are received, determining a final voting value based on the N-f legal main voting values.

13. The method of claim 12, wherein determining a final vote value based on the N-f legitimate rounds of master vote values comprises:

if the main voting values of the N-f legal local rounds are the same, determining the values corresponding to the N-f main voting values as final voting values;

and if the main voting values of the N-f legal current rounds are not completely the same, determining that the final voting value is a predefined value different from the priority voting value and other voting values.

14. The method of claim 13, wherein the determining the consensus situation of the proposal to be consensus based on the received vote values of the current round broadcasted by the other consensus nodes comprises:

under the condition that N-f current-round final voting values are received, if the N-f current-round final voting values are the same, are priority voting values or other voting values, determining that the value corresponding to the N-f current-round final voting values is a consensus result of the to-be-consensus proposal, and determining the value corresponding to the N-f current-round final voting values as a pre-voting value of a next-round consensus;

if the final voting values of the N-f current rounds are not completely the same, and f +1 current rounds have the same final voting value, are priority voting values or other voting values, determining a value corresponding to the f +1 current rounds of final voting values as a next round of consensus pre-voting value;

if f +1 identical voting values do not exist in the final voting values of the N-f current rounds, randomly determining a local coin throwing value, wherein the local coin throwing value is a priority voting value or other voting values, and determining the local coin throwing value as a pre-voting value identified by the next round.

15. A Byzantine fault-tolerant method is applied to any one consensus node in a distributed system, the distributed system comprises N consensus nodes, wherein N is larger than or equal to 3f +1, f is an integer larger than 0, and the method comprises the following steps:

determining the proposal to be consensus in the consensus in a preset mode, and broadcasting the proposal to be consensus to other consensus nodes by using a reliable broadcast RBC protocol;

for a candidate consensus proposal of any consensus node, determining a consensus result of the candidate consensus proposal by using the reliable broadcast based re-voted binary consensus method according to any one of claims 1-14.

16. The method according to claim 15, wherein the predetermined manner comprises:

determining whether the continuous times of the transactions acquired in a random acquisition mode reach preset times or not;

if yes, determining that the plaintext transaction of the preset quantity stored in the local transaction pool earlier is acquired at this time and used as a proposal to be identified;

if not, determining that the plaintext transaction of the preset quantity stored in the local transaction pool is randomly acquired at this time as the proposal to be identified.

17. The method of claim 16, wherein said reliable broadcast RBC protocol is an unconditionally safe reliable broadcast RBC protocol.

18. The method of claim 16, wherein said reliable broadcast RBC protocol is a quantum secure reliable broadcast RBC protocol.

19. A two-element consensus device capable of re-voting based on reliable broadcasting is applied to any consensus node in a distributed system, wherein the distributed system comprises N consensus nodes, N is greater than or equal to 3f +1, f is an integer greater than 0, and the device comprises:

20. The Byzantine fault-tolerant device is applied to any one consensus node in a distributed system, the distributed system comprises N consensus nodes, wherein N is larger than or equal to 3f +1, f is an integer larger than 0, and the device comprises:

a consensus module for determining a consensus result of a candidate consensus proposal for any of the consensus nodes by using the reliable broadcast based re-voted binary consensus method according to any of claims 1-14.

21. A computer device comprising a memory, a processor, a communication interface and a computer program stored on the memory and executable on the processor, wherein the processor implements the method of any one of claims 1 to 14 or 15 to 18 when executing the program.

22. A computer-readable storage medium, on which a computer program is stored which, when being executed by a processor, carries out the method according to any one of claims 1 to 14 or 15 to 18.