Method and system for querying a secure database located on an untrusted device
In general, embodiments of the invention relates to a method for managing data, the method includes obtaining, by an untrusted device and from a querying system, an item query, identifying a leaf block of a hierarchical block tree associated with the item query, identifying a plurality of indirect blocks that allow the querying system to calculate a top hash of the hierarchical block tree, and sending an item query response to the querying system, wherein the item query response specifies the leaf block, the plurality of indirect hashes corresponding to the plurality of indirect blocks, and a signature of the top hash, wherein the signature is obtained from a trusted system.
1. A method for managing data, the method comprising:
obtaining, by an untrusted device of a plurality of untrusted devices and from a querying system, an item query corresponding to an item;
identifying, by the untrusted device, a leaf block of a hierarchical block tree associated with the item query;
identifying, by the untrusted device, a plurality of indirect blocks that allow the querying system to calculate a top hash of the hierarchical block tree; and
sending, by the untrusted device, an item query response to the querying system, wherein the item query response specifies the leaf block, a plurality of indirect hashes corresponding to the plurality of indirect blocks, and a signature of the top hash, wherein the signature is obtained from a trusted system;
after the sending the item query response, obtaining, by the trusted system, an update to the item;
identifying, by the trusted system and in response to the update, the leaf block of the hierarchical block tree,
updating, by the trusted system, the leaf block based on the update to the item to obtain an updated hierarchical block tree, wherein the updated hierarchical block tree comprises a second top hash;
calculating, by the trusted system, a second signature using the second top hash and a private key of the trusted system; and
initiating, by the trusted system, a distribution of the updated hierarchical block tree using the second signature to the plurality of untrusted devices.
2. The method of claim 1 , further comprising:
obtaining, by the untrusted device and from the querying system, a second item query specifying an item identifier;
identifying a second leaf block of the hierarchical block tree that specifies a second item identifier associated with the second item query; and
in response to the identifying the second leaf block, sending a second item query response to the querying system, wherein the second item query response specifies the second leaf block, a second plurality of indirect hashes, and the signature of the top hash.
3. The method of claim 1 , wherein identifying the leaf block of the hierarchical block tree comprises:
identifying a top block of the hierarchical block tree;
identifying an indirect block associated with the top block logically associated with a covered range;
determining that an item identifier associated with the item query is within the covered range; and
identifying the leaf block that is associated with the indirect block.
4. The method of claim 3 , wherein the leaf block comprises an item range and wherein the item range is within the covered range.
5. The method of claim 4 , wherein a second leaf block in the hierarchical block tree comprises a second item range, wherein the second item range at least partially overlaps with the item range.
6. The method of claim 1 , wherein the leaf block comprises an item range and a list of item identifiers and wherein the item query specifies an item identifier within the item range.
7. The method of claim 1 , wherein the plurality of indirect hashes comprises a hash associated with a sibling block of the indirect block.
8. The method of claim 1 , wherein in the leaf block does not include an item identifier associated with the item query.
9. The method of claim 1 , wherein the item query comprises a hashed item identifier.
10. A system, comprising:
a plurality of untrusted devices, wherein an untrusted device of the plurality of untrusted devices comprises:
a processor;
memory comprising instructions, which when executed by the processor causes the untrusted device to perform a method, the method comprising:
obtaining, from a querying system, an item query;
identifying a leaf block of a hierarchical block tree associated with the item query;
identifying a plurality of indirect blocks that allow the querying system to calculate a top hash of the hierarchical block tree; and
sending an item query response to the querying system, wherein the item query response specifies the leaf block, a plurality of indirect hashes corresponding to the plurality of indirect blocks, and a signature of the top hash, wherein the signature is obtained from a trusted system;
the trusted system comprising:
a second processor; and
second memory comprising instructions, which when executed by the second processor causes the trusted system to perform a second method, the second method comprising:
after the sending the item query, obtaining an update to the item;
identifying, in response to the update, the leaf block of the hierarchical block tree,
updating the leaf block based on the update to the item to obtain an updated hierarchical block tree, wherein the updated hierarchical block tree corresponds to a second top hash;
calculating a second signature using the second top hash and a private key of the trusted system; and
initiating a distribution of the updated hierarchical block tree using the second signature to the plurality of untrusted devices.
11. The system of claim 10 , wherein the method further comprises:
obtaining, from the querying system, a second item query specifying an item identifier;
identifying a second leaf block of the hierarchical block tree that specifies a second item identifier associated with the second item query; and
in response to the identifying the second leaf block, sending a second item query response to the querying system, wherein the item query response specifies the second leaf block, a second plurality of indirect hashes, and the signature of the top hash.
12. The system of claim 10 , wherein identifying the leaf block of the hierarchical block tree comprises:
identifying a top block of the hierarchical block tree;
identifying an indirect block associated with the top block logically associated with a covered range;
determining that an item identifier associated with the item query is within the covered range; and
identifying the leaf block that is associated with the indirect block.
13. The system of claim 12 , wherein the leaf block comprises an item range and wherein the item range is within the covered range.
14. The system of claim 13 , wherein a second leaf block in the hierarchical block tree comprises a second item range, wherein the second item range at least partially overlaps with the item range.
15. The system of claim 10 , wherein the leaf block comprises an item range and a list of item identifiers and wherein the item query specifies an item identifier within the item range.
16. The system of claim 10 , wherein the plurality of indirect hashes comprises a hash associated with a sibling block of the indirect block.
17. The system of claim 10 , wherein in the leaf block does not include an item identifier associated with the item query.
18. The system of claim 10 , wherein the item query comprises a hashed item identifier.