Method and system for byzantine fault-tolerance replicating of data

Patent metadata

Field	Value
Publication number	US-11522698-B2
Application number	US-202017000409-A
Country	US
Kind code	B2
Filing date	Aug 24, 2020
Priority date	Nov 25, 2016
Publication date	Dec 6, 2022
Grant date	Dec 6, 2022

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

What is claimed is:

1. A method for byzantine fault-tolerance replicating of data on a plurality of n servers, the n 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 the steps of:
computing at least one random secret value for at least one respective counter value of 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 and the UMSC;
splitting the at least one random secret into a plurality of shares;
computing a server-specific authenticated encryption of each share of the at least one random secret, such that decryption can only be performed by the specified respective server, wherein during a later procedure the server-specific shares are used for verifying the request message; and
providing the computed server-specific shares and the computed commitment to the respective servers.

2. The method according to claim 1 , wherein the performing the preprocessing procedure further comprises precomputing a plurality of message authentication codes, each respective message authentication code corresponding to a respective counter value of the USMC.

3. The method according to claim 2 , wherein each respective message authentication code is computed using a respective random secret.

4. The method according to claim 3 , wherein the splitting the at least one random secret into a plurality of shares comprises splitting each respective random secret into a plurality of shares.

5. The method according to claim 4 , wherein the computing a server-specific authenticated encryption of each share of the at least one random secret comprises computing a server-specific authenticated encryption of each share of each respective random secret.

6. The method according to claim 5 , wherein each server-specific encryption of a share of a respective random secret corresponds to a respective BN, and wherein each server-specific encryption of a respective random secret utilizes, for the encryption, a public key of the respective corresponding BN or a pairwise symmetric encryption between the PN and the respective corresponding BN.

7. The method according to claim 1 , further comprising organizing, by the PN, the active BN into a spanning tree comprising nodes and rooted at the PN, wherein intermediate nodes of the spanning tree of active BN are configured to aggregate shares within the tree.

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

9. The method according to claim 2 , wherein splitting the at least one random secret into a plurality of shares comprises splitting each respective counter value of the USMC into a plurality of shares by utilizing an (f+1)-out-of-n secret sharing for each respective counter value of the USMC.

10. The method according to claim 9 , wherein for each respective counter value of the USMC, the TCE of the PN generates n random values and a polynomial, wherein each BN receives a share of a secret determined by evaluating the polynomial.

11. 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.

12. The method according to claim 11 , the method further comprising determining that the PN is faulty, performing a view change operation to select a new PN from the BN, and increasing the view number.

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 shares,
computing a server-specific authenticated encryption of each share, such that decryption can only be performed by the specified respective server, wherein during a later procedure the server-specific shares are used for verifying the request message, and
providing the computed server-specific shares and the computed commitment to the respective servers.

15. A non-transitory computer readable medium storing a program which, when executed, causes a computer to execute a method for byzantine fault-tolerance replicating of data on a plurality of n servers, the n servers comprising one primary node (PN) and n−1 backup nodes (BN), wherein f servers may arbitrarily fail, and wherein all n servers having a trusted computing entity (TCE), the method comprising:
performing, by the TCE of the PN, a preprocessing procedure comprising 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 shares,
computing a server-specific authenticated encryption of each share, such that decryption can only be performed by the specified respective server, wherein during a later procedure the server-specific shares are used for verifying the request message, and
providing the computed server-specific shares and the computed commitment to the respective servers.

16. The method according to claim 1 , further comprising:
receiving a plurality of messages from the respective servers, each of the messages comprising a respective share of the random secret;
reconstructing the random secret from the plurality of messages;
executing a request based on determining whether the reconstructed secret matches the computed commitment; and
sending the reconstructed random secret to the respective servers.

17. The system according to claim 14 , wherein the system is adapted to:
receive a plurality of messages from the respective servers, each of the messages comprising a respective share of the random secret;
reconstruct the random secret from the plurality of messages;
execute a request based on determining whether the reconstructed secret matches the computed commitment; and
send the reconstructed random secret to the respective servers.

18. The non-transitory computer readable medium according to claim 15 , further comprising code for causing the computer to execute operations comprising:
receiving a plurality of messages from the respective servers, each of the messages comprising a respective share of the random secret;
reconstructing the random secret from the plurality of messages;
executing a request based on determining whether the reconstructed secret matches the computed commitment; and
sending the reconstructed ra

Assignees

• Nec Corp

Inventors

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

Classifications

• H04L9/0869

  involving random numbers or seeds · CPC title

• H04L9/3073

  involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing · CPC title

• G06F11/1451

  by selection of backup contents · CPC title

• H04L9/3247

  involving digital signatures · CPC title

• G06F11/2097 Primary

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