Method and system for byzantine fault-tolerance replicating of data on a plurality of servers

Patent metadata

Field	Value
Publication number	US-10049017-B2
Application number	US-201615575398-A
Country	US
Kind code	B2
Filing date	Oct 4, 2016
Priority date	Oct 4, 2016
Publication date	Aug 14, 2018
Grant date	Aug 14, 2018

Abstract

A method for byzantine fault-tolerant replication of data on a plurality of n servers by a client, wherein the n servers include one primary node (PN) and n−1 replica nodes (REPN), wherein f servers may arbitrarily fail, and wherein all n servers include a trusted computing entity (TCE), includes: performing a request procedure, performing a prepare procedure, performing a commit procedure, and performing a reply procedure. The request procedure includes providing a request message for requesting a certain operation, and transmitting the request message to all n servers. The prepare procedure includes computing a prepare message including at least part of the content of the request message and a unique identifier (UI), the UI being computed by the TCE, the UI being based on a cryptographic signature of the request message and a unique, monotonic, sequential counter (UMSC), and providing the prepare message to the REPN.

First claim

The invention claimed is:

1. A method for byzantine fault tolerant replication of data on a plurality of n servers by a client, wherein the n servers include one primary node (PN) n−1 replica nodes (REPN), wherein f servers may arbitrarily fail, and wherein all n servers include a trusted computing entity (TCE), the method comprising:
performing a request procedure,
performing a prepare procedure,
performing a commit procedure, and
performing a reply procedure,
wherein the request procedure comprises:
providing a request message for requesting a certain operation, and
transmitting the request message to all n servers,

wherein the prepare procedure comprises:
computing a prepare message including at least part of the content of the request message and a unique identifier (UI), the UI being computed by the TCE, the UI being based on a cryptographic signature of the request message and a unique, monotonic, sequential counter (UMSC), and
providing the prepare message to the REPN,

wherein the commit procedure comprises:
validating the prepare message by checking the UI,
upon positive verification of the prepare message, computing a commit message including the UI and content of the prepare message, wherein in case of computing the commit message by each of the REPN, the computed commit messages include all the same part of the content of the prepare message, and
multicasting the commit message by the PN or by each of the REPN, and

wherein the reply procedure comprises:
validating, by each server, the unique identifiers of received commit messages, when the number of valid received commits from different servers is greater than f, and
computing a reply message for the client.

2. The method according to claim 1 , wherein the unique identifier in the commit procedure comprises an aggregated signature received by the PN from the REPN, each REPN computing its own signature part being aggregated along the connections between the REPN to the PN.

3. The method according to claim 2 , wherein the aggregated signature is obtained using a collective signing procedure between the PN and each of the REPN.

4. The method according to claim 1 , wherein a result of the requested operation is included in the reply message, the result of the requested operation being computed by each of the REPN.

5. The method according to claim 4 , wherein each of the REPN computes its own signature part of the computed result and wherein the PN aggregates the signature parts of the result.

6. The method according to claim 3 , wherein upon invalidity of an aggregated signature, a binary search by the PN is performed on the received signature parts to identify and discard wrong signature parts.

7. The method according to claim 1 , wherein the connections between the servers are organized in a tree topology with the PN being the root of the tree or in a star topology with the PN being the center of the star.

8. The method according to claim 1 , wherein the TCE of the PN computes two initial counters, one representing a current hardware counter of said server, one a counter generated with a certain starting value and wherein during the prepare procedure, the unique identifier is signed by the TCE with both counters and wherein upon each reboot the starting value is increased by a certain defined value.

9. The method according to claim 1 , wherein the PN is selected out of servers and wherein, when the PN is determined to be faulty, a new PN out of the REPN is selected.

10. The method according to claim 9 , wherein a PN is determined faulty by an REPN by not receiving a prepare message after expiry of a certain time after receiving the request message.

11. The method according to claim 10 , wherein a new PN is selected by:
requesting a view change by an REPN after expiry of the certain time period by sending a change message to all other REPN,
multicasting a view change message, after having received f+1 change messages, by an REPN, a set of all messages since a last checkpoint was generated together with a checkpoint certificate,
selecting a new PN when having received f+1 view change messages and the new PN multicasts a new view message indicating that a new PN is established.

12. The method according to claim 1 , wherein at the beginning of a new view, the method further comprises:
generating a random ephemeral nonce and a counter with a certain starting value change by the TCE of the PN after each start of the PN;
computing a local signature on the counter and the generated nonce;
providing the local signature to all REPN;
verifying the provided signature by each of the REPN; and
whenever the REPN has received a different nonce from the PN, the REPN initiates a view change to select a new PN of the REPN.

13. The method according to claim 1 , wherein a view number is included into the messages for indicating a current view determining a certain server being the PN and other servers being REPN.

14. A system for byzantine fault tolerant replication of data, the system comprising:
a plurality of n servers, the n servers comprising one primary node (PN) and n−1 replica nodes, (REPN), wherein f servers may arbitrarily fail, and wherein all servers have a trusted computing entity (TCE),
a client being configured to perform a request procedure,
wherein the PN is configured to perform a prepare procedure,
wherein the PN or each of the REPN are configured to perform a commit procedure,
wherein the servers are configured to perform a reply procedure,
wherein the request procedure that the client is configured to perform comprises:
providing a request message for requesting a certain operation, and
transmitting the request message to all n servers,

wherein the prepare procedure that the PN is configured to perform comprises:
computing a prepare message including at least part of the content of the request message and a unique identifier (UI), the UI being computed by the TCE, the UI being based on a cryptographic signature of the request message and a unique, monotonic, sequential counter (UMSC), and
providing the prepare message to the REPN,

wherein the commit procedure that the PN or each of the REPN are configured to perform comprises:
validating the prepare message by checking the UI,
upon positive verification of the prepare message, computing a commit message including the UI and content of the prepare message, wherein in case of computing the commit message by each of the REPN, the computed commit messages include all the same part of the content of the prepare message, and
multicasting the commit message by the PN or by each of the REPN, and

wherein the reply procedure that the servers are configured to perform comprises:
validating, by each server, the unique identifiers of received commit messages, when the number of valid received commits from different servers is greater than f, and
computing a reply message for the client.

15. A non-transitory computer readable medium storing a program that when executed by a processor causes a computer to execute a method for byzantine fault tolerant replication of data on a plurality of n servers, the n servers comprising one primary node (PN) and n−1 replica nodes (REPN), wherein f servers may arbitrarily fail, and wherein all n servers have a trusted computing entity (TCE), the method comprising:
performing a request procedure,
performing a prepare procedure,
performing a commit procedure, and
performing a reply procedure,
wherein the request procedure comprises:
providing a request message for requesting a certain operation, and
transmitting

Assignees

• Nec Europe Ltd
• Nec Corp

Inventors

• Karame Ghassan
• Li Wenting
• Liu Jian
• Asokan Nadarajah
• Paverd Andrew

Classifications

• G06F11/187

  Voting techniques · CPC title

• G06F11/0709

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

• G06F2201/83

  the solution involving signatures · CPC title

• G06F11/07

  Responding to the occurrence of a fault, e.g. fault tolerance · CPC title

• H04L9/3247 Primary

  involving digital signatures · CPC title