System and method for ending view change protocol

Patent metadata

Field	Value
Publication number	US-10877829-B2
Application number	US-202016902401-A
Country	US
Kind code	B2
Filing date	Jun 16, 2020
Priority date	Mar 18, 2019
Publication date	Dec 29, 2020
Grant date	Dec 29, 2020

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for performing view change. One of the methods is to be implemented on a blockchain and performed by a first node of N nodes in a view change protocol. The method includes: multicasting a view change message to at least some of the N nodes; obtaining, respectively from at least Q second nodes of the N nodes, at least Q echo messages each comprising: a consistent current view known to the second node indicating a primary node designated among the N nodes, and a consistent current sequence number known to the second node, the current sequence number associated with a latest transaction or a latest block, the current sequence number is larger than a first sequence number known to the first node; and responsive to obtaining the at least Q echo messages, ending the view change protocol.

First claim

The invention claimed is:

1. A computer-implemented method, comprising:
obtaining, by a second node of a number (N) of nodes, a view change message from a first node of the N nodes, wherein:
N is an integer greater than or equal to four,
the N nodes maintain a blockchain by executing a Practical Byzantine Fault Tolerance-based consensus algorithm,
one of the N nodes is designated as a primary node,
(N−1) of the N nodes other than the designated primary node are designated as backup nodes,
the second node of the N nodes is in a normal operation protocol of the Practical Byzantine Fault Tolerance-based consensus algorithm, and
the first node of the N nodes is in a view change protocol of the Practical Byzantine Fault Tolerance-based consensus algorithm;
in response to the view change message, determining, by the second node, a current status of the second node; and
in response to determining that the current status is the normal operation protocol, transmitting, by the second node, to the first node an echo message for the first node to exit the view change protocol based on receiving Q consistent echo messages from Q second nodes,
the echo message comprising (1) a current view known to the second node indicating the primary node designated among the N nodes and (2) a current sequence number known to the second node,
the current sequence number corresponding to a newest block of the blockchain or a newest transaction committed by the second node in the execution of the Practical Byzantine Fault Tolerance-based consensus algorithm,
wherein a number (F) of tolerable non-functioning nodes is (N−1)/3 rounded down to the nearest integer, and Q is (N+F+1)/2 rounded up to the nearest integer.

2. The method of claim 1 , wherein the current sequence number is larger than a first sequence number known to the first node.

3. The method of claim 2 , wherein:
the current sequence number known to the second node is (n+1);
the first sequence number known to the first node is n;
the current view known to the second node is v; and
when in the view change protocol, the first node has a first view larger than v.

4. The method of claim 2 , wherein:
the first sequence number corresponds to a height of a first copy of the blockchain maintained by the first node; and
the current sequence number corresponds to a height of a second copy of the blockchain maintained by the second node.

5. The method of claim 2 , wherein:
the first sequence number corresponds to a sequence number of a newest transaction committed by the first node; and
the current sequence number corresponds to a sequence number of the newest transaction committed by the second node.

6. The method of claim 1 , wherein the echo message comprises a digital signature certifying that the current view and the current sequence number are both known to the second node.

7. The method of claim 1 , wherein the echo message further comprises a digest of the newest block or the newest transaction.

8. The method of claim 7 , wherein the digest comprises a hash value of the newest block or the newest transaction.

9. The method of claim 7 , wherein the digest comprises a Merkle root of the newest block, and the newest block is known to the second node but unknown to the first node.

10. A non-transitory computer-readable storage medium storing instructions executable by one or more processors, wherein execution of the instructions causes the one or more processors to perform operations comprising:
obtaining, at a second node of a number (N) of nodes, a view change message from a first node of the N nodes, wherein:
N is an integer greater than or equal to four,
the N nodes maintain a blockchain by executing a Practical Byzantine Fault Tolerance-based consensus algorithm,
one of the N nodes is designated as a primary node,
(N−1) of the N nodes other than the designated primary node are designated as backup nodes,
the second node of the N nodes is in a normal operation protocol of the Practical Byzantine Fault Tolerance-based consensus algorithm, and
the first node of the N nodes is in a view change protocol of the Practical Byzantine Fault Tolerance-based consensus algorithm;
in response to the view change message, determining, by the second node, a current status of the second node; and
in response to determining that the current status is the normal operation protocol, transmitting, by the second node, to the first node an echo message for the first node to exit the view change protocol based on receiving Q consistent echo messages from Q second nodes,
the echo message comprising (1) a current view known to the second node indicating the primary node designated among the N nodes and (2) a current sequence number known to the second node,
the current sequence number corresponding to a newest block of the blockchain or a newest transaction committed by the second node in the execution of the Practical Byzantine Fault Tolerance-based consensus algorithm,
wherein a number (F) of tolerable non-functioning nodes is (N−1)/3 rounded down to the nearest integer, and Q is (N+F+1)/2 rounded up to the nearest integer.

11. The non-transitory computer-readable storage medium of claim 10 , wherein the current sequence number is larger than a first sequence number known to the first node.

12. The non-transitory computer-readable storage medium of claim 11 , wherein:
the current sequence number known to the second node is (n+1);
the first sequence number known to the first node is n;
the current view known to the second node is v; and
when in the view change protocol, the first node has a first view larger than v.

13. The non-transitory computer-readable storage medium of claim 11 , wherein:
the first sequence number corresponds to a height of a first copy of the blockchain maintained by the first node; and
the current sequence number corresponds to a height of a second copy of the blockchain maintained by the second node.

14. The non-transitory computer-readable storage medium of claim 11 , wherein:
the first sequence number corresponds to a sequence number of a newest transaction committed by the first node; and
the current sequence number corresponds to a sequence number of the newest transaction committed by the second node.

15. The non-transitory computer-readable storage medium of claim 10 , wherein the echo message comprises a digital signature certifying that the current view and the current sequence number are both known to the second node.

16. The non-transitory computer-readable storage medium of claim 10 , wherein the echo message further comprises a digest of the newest block or the newest transaction.

17. The non-transitory computer-readable storage medium of claim 16 , wherein the digest comprises a hash value of the newest block or the newest transaction.

18. The non-transitory computer-readable storage medium of claim 16 , wherein the digest comprises a Merkle root of the newest block, and the newest block is known to the second node but unknown to the first node.

19. A system comprising one or more processors and one or more non-transitory computer-readable memories coupled to the one or more processors and configured with instructions executable by the one or more processors to cause the system to perform operations comprising:
obtaining, at a second node of a number (N) of nodes, a view change message from a first node of the N nodes, wherein:
N is an integer greater than or equal to four,
the N nodes maintain a blockchain by executing a Practical By

Assignees

• Advanced New Technologies Co Ltd

Inventors

• Yang Dayi

Classifications

• H04L9/50

  using hash chains, e.g. blockchains or hash trees · CPC title

• H04L1/1621

  Group acknowledgement, i.e. the acknowledgement message defining a range of identifiers, e.g. of sequence numbers · CPC title

• G06F11/0709 Primary

  in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems · CPC title

• G06F11/14 Primary

  Error detection or correction of the data by redundancy in operations (error detection or correction of the data by redundancy in hardware G06F11/16) · CPC title

• H04L9/3247

  involving digital signatures · CPC title