Method and system for byzantine fault-tolerance replicating of data

Patent metadata

Field	Value
Publication number	US-10797877-B2
Application number	US-201616081429-A
Country	US
Kind code	B2
Filing date	Nov 25, 2016
Priority date	Nov 25, 2016
Publication date	Oct 6, 2020
Grant date	Oct 6, 2020

Abstract

A method for byzantine fault-tolerance replicating of data on a plurality of n servers includes performing a preprocessing procedure. The n servers include one primary node (PN) and n−1 backup nodes (BN), wherein f servers may arbitrarily fail, and wherein all n servers have a trusted computing entity (TCE). The preprocessing procedure is performed by the TCE of the PN and includes computing a random secret value for a unique, monotonic, sequential counter (UMSC) to be assigned with a request message for requesting an operation to be performed, computing a commitment for the random secret value and the UMSC, and splitting the random secret value into a plurality of shares. The preprocessing procedure further includes computing a server-specific authenticated encryption of each share, and providing the computed server-specific shares and the computed commitment to the respective servers.

First claim

The invention claimed is:

1. A method for byzantine fault-tolerance replicating of data on a plurality of n servers, then servers comprising one primary node (PN) and n−1 backup nodes (BN), wherein f servers may arbitrarily fail, and wherein all n servers have a trusted computing entity (TCE), the method comprising:
performing, by the TCE of the PN, a preprocessing procedure comprising:
computing a random secret value for a unique, monotonic, sequential counter (UMSC) to be assigned with a request message for requesting an operation to be performed,
computing a commitment for the random secret value and the UMSC,
splitting the random secret value into a plurality of server-specific shares,
computing an authenticated encryption of each respective server-specific share, wherein each authenticated encryption of a respective server-specific share can only be decrypted by a corresponding respective server, wherein each respective server-specific share is configured to be used for verifying the request message, and
providing each authenticated encryption of a respective server-specific share and the computed commitment to a corresponding the respective server;

collecting, by the PN, a number of server-specific shares, each collected server-specific share being decrypted by a respective BN;
reconstructing, by the PN, the random secret value based on the collected server-specific shares and/or a respective server-specific share corresponding to the PN; and
verifying, by the PN, the reconstructed secret by using the reconstructed secret to open the computed commitment,
wherein the PN is configured to perform the operation when the reconstructed secret is verified.

2. The method according to claim 1 , wherein the PN receives the request message and computes a prepare message including at least content of the request message and a unique identifier (UI), the UI being computed by the TCE of the PN, the UI being based on a cryptographic signature of the request message and the UMSC, and wherein the PN provides the prepare message to the BN.

3. The method according to claim 1 , further comprising at least one of the steps of:
transmitting, by broadcasting, the opened commitment to the BN, and
comparing, by each of the BN, the received transmitted opened commitment with the computed commitment provided during the preprocessing phase.

4. The method according to claim 2 , further comprising validating, by each respective BN, the prepare message by checking the UI by the TCE of each respective BN, and
performing, by the BN upon a positive result of the validating, the operation.

5. The method according to claim 1 , wherein if the number of collected server-specific shares is smaller than the number n, then an integrity of each collected share is checked by the PN prior to reconstructing the random secret value.

6. The method according to claim 1 , wherein the computing the authenticated encryption of each respective server-specific share uses a public key of each BN or a pairwise symmetric encryption between the PN and each of the BN.

7. The method according to claim 1 , wherein active BN are detected by the PN, and wherein only the active BN are used for performing at least one step of the method, and wherein the active BN may be organized by the PN into a spanning tree comprising nodes and rooted at the PN, wherein communication may be performed along the spanning tree of active BN by aggregating shares by intermediate nodes within the tree.

8. The method according to claim 7 , wherein the PN is selected from the n server,
wherein, when the PN is determined to be faulty, a new PN is selected from the active BN, and
wherein the PN is determined to be faulty by a reply message not being received after expiry of a certain time period after the request message is transmitted.

9. The method according to claim 8 , wherein the new PN is selected by the steps of:
a) requesting, by a BN after expiry of the certain time period, a view change by sending a view change message to all other BN,
b) choosing, as a new PN, a BN being active and closest to the old PN according to a distance parameter,
c) computing, by the new PN, a history message comprising information of the latest local counter value and requesting history information about communication performed between the new PN and the old PN and the new PN and other BN,
d) sending the history message to all other BN by the new PN,
e) computing, by each of the BN after verifying the received request history information, a view change message,
f) providing the computed view change message to all other BN after having verified the request history information of a received history message,
g) upon having received f matching view change messages, by a BN, and having a verified request history, processing the verified history, and
h) upon having received f matching view change messages by the new PN, the new PN provides view change messages to the f BN indicating that a new PN is established.

10. The method according to claim 1 , wherein a faulty BN is identified by the steps of:
a) upon at least one of sending and receiving, of a message, starting a timer by a BN, associated with each directly connected BN,
b) when not receiving a valid share from a directly connected BN before expiry of the timer for the directly connected BN, providing a suspect message at least to the PN indicating a possible failure of the directly connected BN,
c) upon receiving, by the PN, at least one suspect message, determining the possibly faulty BN and selecting a replacement BN for the determined faulty BN, and
d) providing information about the replacement BN to the other BN, such that the determined faulty BN is ignored by the other BN.

11. The method according to claim 7 , wherein directly connected BN are children of the PN and wherein a suspect message is provided to a parent of the PN and wherein a suspect message is provided along the tree to the PN.

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

13. The method according to claim 1 , wherein upon valid verification of the reconstructed secret the PN performs a request, and
wherein a result of the performed request is transmitted to the BN together with an increased counter value.

14. A system for byzantine fault-tolerance replicating of data on a plurality of servers by a client, the system comprising:
n servers including one primary node (PN) and n−1 backup nodes (BN), wherein f servers may arbitrarily fail, and wherein all n servers have a trusted computing entity (TCE),
wherein the TCE of the PN is adapted to perform the steps of:
computing a random secret value for a unique, monotonic, sequential counter (UMSC), to be assigned with a request message for requesting an operation to be performed,
computing a commitment for the random secret value and the UMSC,
splitting the random secret value into a plurality of server-specific shares,
computing an authenticated encryption of each respective server-specific share, wherein each authenticated encryption of a respective server-specific share can only be decrypted by a corresponding respective server, wherein each respective server-specific share is configured to be used for verifying the request message, and
providing each authenticated encryption of a respective server-specific share and the computed commitment to a corresponding respective server, and

wherein the PN is adapted to perform the steps of:
collecting a number of server-specific shares, e

Assignees

• NEC Laboratories Europe GmbH
• Nec Corp

Inventors

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

Classifications

• G06F11/1451

  by selection of backup contents · CPC title

• H04L9/321 Primary

  involving a third party or a trusted authority · CPC title

• H04L9/0869

  involving random numbers or seeds · CPC title

• G06F11/2097 Primary

  maintaining the standby controller/processing unit updated (initialisation or re-synchronisation thereof G06F11/1658 and subgroups) · CPC title

• G06F11/1469

  Backup restoration techniques · CPC title