Signatures of updates exchanged in a binary data synchronization protocol

Patent metadata

Field	Value
Publication number	US-10038559-B2
Application number	US-201615284116-A
Country	US
Kind code	B2
Filing date	Oct 3, 2016
Priority date	Oct 2, 2015
Publication date	Jul 31, 2018
Grant date	Jul 31, 2018

Abstract

In a distributed system, data is shared between three or more electronic devices. The first device generates and signs an object that includes the data. A second device receives the signed object and determines whether the signed object is valid. If valid, the second device will generate a validated signed object and send it to a third device. The third device will validate the object by determining whether the object includes valid signatures of both the first and second devices.

First claim

The invention claimed is:

1. A method of sharing an object between electronic devices in a distributed system, the method comprising:
by a first electronic device that is associated with a sync group:
generating an object,
signing the object to create a signed object, and
transmitting the signed object to a second electronic device that is associated with the sync group;

by the second electronic device:
receiving the signed object,
determining whether the signed object is valid,
upon determining that the signed object is valid creating a validated signed object, and transmitting the validated signed object to a third electronic device that is associated with the sync group;

by the third electronic device:
receiving the validated signed object from the second device,
determining whether the validated signed object includes a valid signature of the first electronic device and a valid signature of the second electronic device, and
if the validated signed object includes the valid signature of the first electronic device and the valid signature of the second electronic device sending the validated signed object to an additional device associated with the sync group, otherwise not sending or using the validated signed object; and

by the second electronic device or the third electronic device:
receiving an entry that comprises the signed object or the validated signed object,
determining whether a lookup key for the entry ends in a value that matches a cryptographic hash of a corresponding entry that is stored in a data store, wherein the value includes a blessing pattern of the first device, a blessing pattern of a trusted re-signer, a sequence number, and a signature of the first device, and
only accepting the entry if the lookup key for the entry ends in the value, otherwise rejecting the entry.

2. The method of claim 1 , wherein generating the object and signing the object to create the signed object comprise, by the first electronic device:
granting a blessing to a storage service of the first electronic device;
creating the object with the data and the blessing; and
applying a signature to the object to yield the signed object.

3. The method of claim 1 , wherein the determining whether the signed object is valid comprises, by the second electronic device:
verifying whether a remote end of a remote procedure call associated with the signed object is authorized by an access control list for the data;
verifying that the remote end of the remote procedure call includes a public key of the first electronic device; and
using the public key of the first electronic device to verify a signature of the signed object.

4. The method of claim 3 , wherein the determining whether the signed object is valid further comprises, by the second electronic device:
extracting one or more blessing names from a blessing of the signed object; and
verifying that the extracted one or more blessing names satisfy the access control list.

5. The method of claim 1 , wherein creating the validated signed object comprises, by the second electronic device, creating the validated signed object to include:
the signed object;
one or more blessing names extracted from the signed object;
a public key of the second electronic device; and
a signature of the second electronic device.

6. The method of claim 1 , wherein:
determining whether the validated signed object includes the valid signature of the first electronic device and the valid signature of the second electronic device comprises determining, by the third electronic device, that the validated signed object includes the valid signature of the first electronic device but not the valid signature of the second electronic device; and
the method further comprises, by the third electronic device, requiring the second electronic device to provide an updated validated signed object with the valid signature of the second electronic device.

7. The method of claim 1 , wherein:
determining whether the validated signed object includes the valid signature of the first electronic device and the valid signature of the second electronic device comprises determining, by the third electronic device, that the validated signed object includes the valid signature of the second electronic device but not the valid signature of the first electronic device; and
the method further comprises, by the third electronic device, either ignoring the validated signed object or requiring the second electronic device to obtain a signature of the first electronic device for the validated signed object.

8. The method of claim 1 , further comprising, by the second electronic device or the third electronic device:
receiving a batch comprising a plurality of updated objects;
determining whether any row in the batch is in conflict due to a difference between a local version and a remote version of the row; and
for any row that is determined to be in conflict, adding the row to a closure.

9. The method of claim 1 , wherein the value also includes a public key.

10. The method of claim 1 , further comprising, by the second electronic device or the third electronic device:
receiving an entry that comprises the signed object or the validated signed object;
determining whether a lookup key for the entry includes a blessing pattern of a trusted re-signer; and
only accepting the entry if the lookup key for the entry includes the blessing pattern of the trusted re-signer, otherwise rejecting the entry.

11. A system of electronic devices, in which the system comprises:
a hardware processor; and
a memory device;
in which the system also includes program instructions that are configured to cause a processor of a second device in the system to share an object by:
receiving the object from a first electronic device of the system as a signed object,
determining whether the signed object is valid,
upon determining that the signed object is valid creating a validated signed object, and transmitting the validated signed object to a third electronic device that is associated with a sync group; and

the system also includes program instructions that are configured cause a processor of a the third electronic device in the system to share the object by:
receiving the validated signed object from the second device,
determining whether the validated signed object includes a valid signature of the first electronic device and a valid signature of the second electronic device, and
if the validated signed object includes the valid signature of the first electronic device and the valid signature of the second electronic device sending the validated signed object to an additional device associated with the sync group, otherwise not sending or using the validated signed object; and

the system also comprises additional program instructions configured to cause the second electronic device or the third electronic device to:
receive an entry that comprises the signed object or the validated signed object,
determine whether a lookup key for the entry ends in a value that matches a cryptographic hash of a corresponding entry that is stored in a data store, wherein the value includes a blessing pattern of the first device, a blessing pattern of a trusted re-signer, a sequence number, and a signature of the first device, and
only accept the entry if the lookup key for the entry ends in the value, otherwise reject the entry.

12. The system of claim 11 , wherein the system also includes program instructions that are configured to cause the first electronic device to generate the object and sign the object to create the signed object by:
granting a blessing

Assignees

• Google Llc

Inventors

• Burrows Michael
• Pucha Himabindu
• Daoud Raja
• Lodhia Jatin
• Taly Ankur

Classifications

• H04L63/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 title

• H04L9/3247 Primary

  involving digital signatures · CPC title

• G06F2221/2141

  Access rights, e.g. capability lists, access control lists, access tables, access matrices · CPC title

• G06F21/64 Primary

  Protecting data integrity, e.g. using checksums, certificates or signatures · CPC title

• G06F16/284

  Relational databases · CPC title