Methods and apparatus for efficiently implementing a distributed database within a network

• US 10,375,037 B2
• Filed: 07/11/2018
• Issued: 08/06/2019
• Est. Priority Date: 07/11/2017
• Status: Active Grant

• Current Assignee: Hedera Hashgraph LLC
• Original Assignee: Swirlds, Inc.
• Inventors: Baird, III, Leemon C., Harmon, Mance
• Primary Examiner(s): Chang, Kenneth W
• Assistant Examiner(s): Lane, Gregory A
• Application Number:
  US16/032,652
• Publication Number:
  US 20190020629A1
• Time in Patent Office: 391 Days
• Field of Search: 713189
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: H04L 2209/04 Masking or blinding
• CPC Class Codes: H04L 63/0421 Anonymous communication, i.e. the party's identifiers are hidden from the other party or parties, e.g. using an anonymizer
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/0442 wherein the sending and receiving network entities apply asymmetric encryption, i.e. different keys for encryption and decryption cryptographic mechanisms or cryptographic arrangements for public-key encryption H04L9/30
• CPC Class Codes: H04L 63/06 for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/061 for key exchange, e.g. in peer-to-peer networks cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 9/0869 involving random numbers or seeds
• CPC Class Codes: H04L 9/12 Transmitting and receiving encryption devices synchronised or initially set up in a particular manner
• CPC Class Codes: H04L 9/3006 underlying computational problems or public-key parameters
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3297 involving time stamps, e.g. generation of time stamps
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees
• CPC Class Codes: H04W 12/02 Protecting privacy or anonymity, e.g. protecting personally identifiable information [PII]

Abstract

An apparatus includes a processor and a memory operatively coupled to the processor and associated with an instance of a distributed database at a first compute device. The processor is configured to select an anonymous communication path. Each blinded public key from a sequence of blinded public keys associated with the anonymous communication path is associated with a pseudonym of a compute device from a set of compute devices that implement the anonymous communication path. The processor is configured to generate an encrypted message encrypted with a first blinded public key. The processor is configured to generate an encrypted data packet including the encrypted message and a compute device identifier associated with a second compute device. The encrypted data packet is encrypted with a second blinded public key. The processor is configured to send the encrypted data packet to a third compute device.

Claims

1. An apparatus, comprising:

a memory associated with an instance of a distributed database at a first compute device configured to be included within a plurality of compute devices that implement the distributed database via a network operatively coupled to the plurality of compute devices; and

a processor operatively coupled to the memory, and configured to;

select an anonymous communication path associated with;

(a) a second compute device from the plurality of compute devices that implement the distributed database, and (b) a set of compute device identifiers, the anonymous communication path defined by a sequence of blinded public keys, each blinded public key from the sequence of blinded public keys associated with a pseudonym of a compute device from a set of compute devices that implement the anonymous communication path;

generate an encrypted message encrypted with a first blinded public key included in the sequence of blinded public keys, the first blinded public key associated with the second compute device, the first blinded public key being defined as a pair (B′

, H′

) based on a public key defined as a pair (B, H) and a random value (R), the pair (B′

, H′

) being defined as (B{circumflex over ( 

)}R, H{circumflex over ( 

)}R);

generate an encrypted data packet including the encrypted message and a compute device identifier from the set of compute device identifiers, the compute device identifier associated with the second compute device, the encrypted data packet encrypted with a second blinded public key from the sequence of blinded public keys; and

send the encrypted data packet to a third compute device from the set of compute devices that implement the anonymous communication path.

2. The apparatus of claim 1, wherein the random value (R) is a first random value (R1), the public key is generated by:

selecting a second random value (R2) from a predefined set of values (G) that is an algebraic group such that R2 is a generator for G;

selecting a third random value (R3) from the predefined set of values (G);

defining the public key as the pair (B, H) based on the second random value (R2) and the third random value (R3), the pair (B, H) being defined as (R2, R2{circumflex over ( 

)}R3),

the first random value (R1) is selected from the predefined set of values (G), the first random value (R1) being selected such that B{circumflex over ( 

)}R1 is a generator for G.

3. The apparatus of claim 2, wherein:

the predefined set of values (G) is chosen to be a set of numbers {1, 2, 3, . . . , 2P} for some prime P such that 2P+1 is prime;

a group operator * is defined to be multiplication modulo 2P+1;

an exponentiation is defined to be repeated multiplication modulo 2P+1; and

an element D of G is defined to be a generator if neither D{circumflex over ( 

)}2 nor D{circumflex over ( 

)}P are congruent to 1 modulo 2P+1.

4. The apparatus of claim 1, wherein the random value (R) is a first random value (R1), the processor is configured to generate the encrypted message (X, Y) by:

selecting a second random value (R2) from a predefined set of values (G) that is an algebraic group; and

encrypting a plaintext message (M) using the first blinded public key (B′

, H′

) and the second random value (R2) to define an encrypted ciphertext as (X, Y)=(B′

{circumflex over ( 

)}R2, M*H′

{circumflex over ( 

)}R2).

5. The apparatus of claim 1, wherein the random value (R) is a first random value (R1), the processor is configured to blind the encrypted message (X, Y) by using the first blinded public key (B′

, H′

) to generate a blinded encrypted message (X′

, Y′

) by;

selecting a second random value (R2) from a predefined set of values (G) that forms an algebraic group; and

defining the blinded encrypted message as (X′

, Y′

)=(X*(B′

{circumflex over ( 

)}R2), Y*(H′

{circumflex over ( 

)}R2)); and

the processor is configured to generate the encrypted data packet including the blinded encrypted message.

6. The apparatus of claim 1, wherein the encrypted data packet is a first encrypted data packet, the anonymous communication path is a first anonymous communication path, and the processor is further configured to:

receive a second encrypted data packet, from the second compute device and via a second anonymous communication path different from the first anonymous communication path; and

decrypt the second encrypted data packet with a private key specific to the first compute device.

7. The apparatus of claim 1, wherein the encrypted data packet is a first encrypted data packet, the anonymous communication path is a first anonymous communication path, the set of compute devices that implement the first anonymous communication path is a first set of compute devices, and the processor is further configured to:

receive from the second compute device, a second data packet, via a second anonymous communication path implemented by a second set of compute devices different from the first set of compute devices.

8. The apparatus of claim 1, wherein the set of compute device identifiers includes a sequence of encrypted compute device identifiers, each compute device identifier from the sequence of encrypted compute device identifiers encrypted with a different blinded public key selected from the sequence of blinded public keys.

9. The apparatus of claim 1, wherein the set of compute device identifiers includes a non-encrypted compute device identifier.

10. The apparatus of claim 1, wherein an Internet Protocol (IP) address of at least one compute device from the set of compute devices that implement the anonymous communication path remains undisclosed to the first compute device.

11. The apparatus of claim 1, wherein at least one compute device identifier from the set of compute device identifiers remains undisclosed to a fourth compute device that implements the anonymous communication path, the fourth compute device different from the second compute device and the third compute device.

12. The apparatus of claim 1, wherein a private key to decrypt messages encrypted with the first blinded public key is specific to the second compute device.

13. A non-transitory processor-readable medium comprising code which, when executed by a processor, causes the processor to:

select, at a first compute device, a first random value (R1) from a predefined set of values (G) that is an algebraic group such that R1 is a generator for G;

select a second random value (R2) from the predefined set of values (G);

define a public key as a pair (B, H) based on the first random value (R1) and the second random value (R2), the pair (B, H) being defined as (R1, R1{circumflex over ( 

)}R2);

send the public key (B, H) such that a second compute device securely provides a message (M) to the first compute device by;

selecting a third random value (R3) from the predefined set of values (G);

encrypting the message (M) using (1) a blinded public key (B′

, H′

) defined based on the public key (B, H) and (2) the third random value (R3), to define an encrypted ciphertext as (X, Y)=(B′

{circumflex over ( 

)}R3, M*H′

{circumflex over ( 

)}R3); and

sending the encrypted ciphertext (X, Y) to the first compute device;

receive the encrypted ciphertext (X, Y) from the second compute device; and

decrypt the encrypted ciphertext (X, Y) to identify the message (M) using the second random value (R2).

14. The non-transitory processor-readable medium of claim 13, wherein:

the predefined set of values (G) is chosen to be a set of numbers {1, 2, 3, . . . , 2P} for some prime P such that 2P+1 is prime;

a group operator * is defined to be multiplication modulo 2P+1;

an exponentiation is defined to be repeated multiplication modulo 2P+1; and

an element D of G is defined to be a generator if neither D{circumflex over ( 

)}2 nor D{circumflex over ( 

)}P are congruent to 1 modulo 2P+1.

15. The non-transitory processor-readable medium of claim 13, wherein the code to cause the processor to send the public key includes code to cause the processor to send the public key such that the second compute device securely provides the message (M) to the first compute device by:

blinding the encrypted cypertext (X, Y) by using the blinded public key (B′

, H′

) to generate a blinded encrypted message (X′

, Y′

) by;

selecting a fourth random value (R4) from the predefined set of values (G); and

defining the blinded encrypted message as (X′

, Y′

)=(X*(B′

{circumflex over ( 

)}R4), Y*(H′

{circumflex over ( 

)}R4)); and

generating an encrypted data packet including the blinded encrypted message; and

sending the encrypted ciphertext as the blinded encrypted message to the first compute device.

16. The non-transitory processor-readable medium of claim 13, wherein the blinded public key is defined by:

selecting a fourth random value (R4) from the predefined set of values (G) such that B{circumflex over ( 

)}R4 is a generator for G; and

defining the blinded public key as the pair (B′

, H′

) based on the public key and the fourth random value (R4), the pair (B′

, H′

) being defined as (B{circumflex over ( 

)}R4, H{circumflex over ( 

)}R4).

21. The non-transitory processor-readable medium of claim 13, wherein the blinded public key is defined by a third compute device.

17. A non-transitory processor-readable medium comprising code which, when executed by a processor, causes the processor to:

define an anonymous communication path with a sequence of blinded public keys for a set of compute devices from a plurality of compute devices that implement a distributed database, the set of compute devices define the anonymous communication path, each blinded public key from the sequence of blinded public keys is associated with a pseudonym of a different compute device from the plurality of compute devices that implement the distributed database;

generate a set of compute device identifiers including (1) an unencrypted compute device identifier identifying a compute device from the plurality of compute devices and (2) a sequence of encrypted compute device identifiers, each encrypted compute device identifier from the sequence of encrypted compute device identifiers encrypted with a different blinded public key from the sequence of blinded public keys;

provide the sequence of blinded public keys and the set of compute device identifiers to at least one compute device from the plurality of compute devices such that the at least one compute device can define a message to the processor for sending via the anonymous communication path;

receive, via the anonymous communication path, the message encrypted with a blinded public key from the sequence of blinded public keys; and

decrypt the message with a private key associated with the blinded public key from the sequence of blinded public keys.

18. The non-transitory processor-readable medium of claim 17, wherein the private key associated with the blinded public key from the sequence of blinded public keys is specific to the processor.

19. The non-transitory processor-readable medium of claim 17, wherein the at least one compute device is not included in the set of compute devices that implement the anonymous communication path.

20. The non-transitory processor-readable medium of claim 17, wherein each encrypted compute device identifier from the sequence of encrypted compute device identifiers is uniquely associated with a different compute device from the plurality of compute devices that implement the distributed database.