System and method for ending view change protocol

Patent metadata

Field	Value
Publication number	US-10725843-B2
Application number	US-202016735457-A
Country	US
Kind code	B2
Filing date	Jan 6, 2020
Priority date	Mar 18, 2019
Publication date	Jul 28, 2020
Grant date	Jul 28, 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 consensus method comprising:
multicasting a view change message to at least some of a number (N) of nodes,
wherein the N nodes maintain a blockchain by executing a Practical Byzantine Fault Tolerance-based consensus algorithm, N is at least four, one of the N nodes is designated as a primary node, (N−1) of the N nodes are designated as backup nodes, and
the method is performed by a first node of the N nodes that is in a view change protocol of the Practical Byzantine Fault Tolerance-based consensus algorithm;
obtaining, respectively from at least a quorum number (Q) of second nodes of the N nodes, at least Q echo messages each comprising
(1) a consistent current view known to the second node indicating the primary node designated among the N nodes and
(2) a consistent current sequence number known to the second node, the current sequence number associated with a latest block or a latest transaction committed by the second node,
wherein the current sequence number is larger than a first sequence number known to the first node,
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; and
responsive to obtaining the at least Q echo messages, ending the view change protocol.

2. The method of claim 1 , wherein:
the at least Q echo messages are respectively sent by the at least Q second nodes to the first node in response to the at least Q second nodes obtaining the view change message.

3. The method of claim 1 , wherein:
the current sequence number comprises a height of a second copy of the blockchain maintained by the second node; and
the first sequence number comprises a height of a first copy of the blockchain maintained by the first node.

4. The method of claim 1 , wherein:
the current sequence number comprises a sequence number of the latest transaction committed by the second node; and
the first sequence number comprises a sequence number of a latest transaction committed by the first node.

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

6. The method of claim 1 , wherein:
the echo message further comprises a digest of the latest block or the latest transaction.

7. The method of claim 6 , wherein:
the digest comprises a hash value of the latest block or the latest transaction.

8. The method of claim 6 , wherein:
the digest comprises a Merkle root of a block of the latest block known to the second node but unknown to the first node.

9. The method of claim 1 , wherein ending the view change protocol comprises:
synchronizing a first copy of the blockchain maintained by the first node with a second copy of the blockchain maintained by second node; and
exiting the view change protocol to enter a normal operation protocol using the current view for the first node.

10. The method of claim 1 , wherein:
the designation of the primary node is different in different views;
the current sequence number known to the at least Q second nodes is (n+1);
the first sequence number known to the first node is n;
the current view for the at least Q second nodes is v; and
when in the view change protocol, the first node has a first view larger than v.

11. 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:
multicasting a view change message to at least some of a number (N) of nodes,
wherein the N nodes maintain a blockchain by executing a Practical Byzantine Fault Tolerance-based consensus algorithm, N is at least four, one of the N nodes is designated as a primary node, (N−1) of the N nodes are designated as backup nodes, and
the storage medium corresponds to a first node of the N nodes that is in a view change protocol of the Practical Byzantine Fault Tolerance-based consensus algorithm;
obtaining, respectively from at least a quorum number (Q) of second nodes of the N nodes, at least Q echo messages each comprising
(1) a consistent current view known to the second node indicating the primary node designated among the N nodes and
(2) a consistent current sequence number known to the second node, the current sequence number associated with a latest block or a latest transaction committed by the second node,
wherein the current sequence number is larger than a first sequence number known to the first node,
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; and
responsive to obtaining the at least Q echo messages, ending the view change protocol.

12. The storage medium of claim 11 , wherein:
the at least Q echo messages are respectively sent by the at least Q second nodes to the first node in response to the at least Q second nodes obtaining the view change message.

13. The storage medium of claim 11 , wherein:
the current sequence number comprises a height of a second copy of the blockchain maintained by the second node; and
the first sequence number comprises a height of a first copy of the blockchain maintained by the first node.

14. The storage medium of claim 11 , wherein:
the current sequence number comprises a sequence number of the latest transaction committed by the second node; and
the first sequence number comprises a sequence number of a latest transaction committed by the first node.

15. The storage medium of claim 11 , wherein:
the echo message comprises a digital signature certifying the current view and the current sequence number both known to the second node.

16. 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:
multicasting a view change message to at least some of a number (N) of nodes,
wherein the N nodes maintain a blockchain by executing a Practical Byzantine Fault Tolerance-based consensus algorithm, N is at least four, one of the N nodes is designated as a primary node, (N−1) of the N nodes are designated as backup nodes, and
the system corresponds to a first node of the N nodes that is in a view change protocol of the Practical Byzantine Fault Tolerance-based consensus algorithm;
obtaining, respectively from at least a quorum number (Q) of second nodes of the N nodes, at least Q echo messages each comprising
(1) a consistent current view known to the second node indicating the primary node designated among the N nodes and
(2) a consistent current sequence number known to the second node, the current sequence number associated with a latest block or a latest transaction committed by the second node,
wherein the current sequence number is larger than a first sequence number known to the first node,
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; and
responsive to obtaining the at least Q echo messages, ending the view change protocol.

17. The system of claim 16 , wherein:
the at least Q echo messages are respectively sent by the at least Q second nodes to the first node in response to the at least Q second nodes obtaining the view change message.

Assignees

• Alibaba Group Holding Ltd

Inventors

• Yang Dayi

Classifications

• H04L9/50

  using hash chains, e.g. blockchains or hash trees · 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

• G06F11/0709 Primary

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

• H04L9/3239

  involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD · CPC title

• G06F11/182

  based on mutual exchange of the output between redundant processing components · CPC title