System and method for committing to a set

• US 7,831,573 B2
• Filed: 09/03/2004
• Issued: 11/09/2010
• Est. Priority Date: 08/12/2003
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Lillibridge, Mark David, Lukose, Rajan Mathew
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): Syed; Farhan M
• Application Number:
  US10/934,557
• Publication Number:
  US 20050038774A1
• Time in Patent Office: 2,258 Days
• Field of Search: 707/100, 707/101, 707/103.R
• US Class Current: 707/698
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

The disclosed embodiments relate to a system and method of committing to a data set, comprising forming a directed acyclic graph adapted to encode the data set, the directed acyclic graph having a plurality of pointers and a plurality of nodes wherein at least one node has multiple parents, the directed acyclic graph having at least one root node and a plurality of leaf nodes. Further, disclosed embodiments comprise committing to the directed acyclic graph to produce a committed-to data set and producing a plurality of proofs about the committed-to data set such that a combination of the plurality of proofs does not reveal information about which nodes have multiple parents, each proof comprising a trace from one of the plurality of nodes to at least one different node, the trace comprising the identities of the nodes and pointers traversed.

Claims

1. A computer-implemented method of committing to a data set, comprising:

forming, by said computer, a directed acyclic graph adapted to encode the data set, the directed acyclic graph having a plurality of pointers and a plurality of nodes wherein at least one node has multiple parents from the directed acyclic graph, the directed acyclic graph having at least one root node and a plurality of leaf nodes;

committing to the directed acyclic graph to produce, by said computer, a committed-to data set; and

producing, by said computer, a plurality of proofs about the committed-to data set such that a combination of the plurality of proofs does not reveal information about which nodes have multiple parents, each proof comprising a trace from one of the plurality of nodes to at least one different node, the trace comprising the identities of the nodes and pointers traversed,

wherein producing a plurality of proofs comprises producing multiple proofs each showing that a different given element is not present in the committed-to data set and limiting a number of these proofs produced per committed-to data set.

2. The method of claim 1, comprising using intrinsic references in the directed acyclic graph as pointers.

3. The method of claim 1, comprising forming a hash-based directed acyclic graph.

4. The method of claim 3, comprising committing to the hash-based directed acyclic graph by sending hashes of at least one root node.

5. The method of claim 1, wherein at least one of the pointers is blinded.

6. The method of claim 1, wherein at least one pointer holds ordinary commitments.

7. The method of claim 6, wherein the ordinary commitments are commitments to hashes, the hashes relating to the nodes being pointed to.

8. The method of claim 1, wherein at least one of the nodes contains a random value.

9. The method of claim 1, comprising forming a prefix directed acyclic graph.

10. The method of claim 1, comprising encoding information about the data set primarily in the plurality of leaf nodes.

11. The method of claim 1, wherein at most a specified number of elements may be proved to be in the committed-to data set.

12. The method of claim 1, wherein the trace is from a root node to a one of the plurality of leaf nodes.

13. A computer-implemented method of determining whether an item of information is included in a data set, the method configured to be stored on a tangible medium and comprising:

grouping, by said computer, binary values into a set comprising values that have the same first K bits ((1≦

K), wherein the set comprises a first subset of values associated with encoded items of information and a second subset of values not associated with encoded items of information; and

providing, by said computer, a proof that is used to test whether a value in the set is associated with the item of information, wherein K is selected such that a different proof can be used for each value in the set,

wherein providing the proof comprises producing multiple proofs each showing that a different given element is not present in the group and limiting a number of these proofs produced per set.

14. The method of claim 13, further comprising representing the values in the set as a hierarchical data structure comprising pointers that map each member of the set from a root node of the data structure to a leaf node of the data structure.

15. The method of claim 14, wherein the hierarchical data structure comprises a hashed directed acyclic graph.

16. The method of claim 14, wherein K is selected such that each value in the set is associated with a different combination of pointers.

17. The method of claim 14, further comprising associating the values in the second subset with a single leaf node.

18. The method of claim 14, wherein different combinations of pointers map members of the second subset from the root node to the same leaf node.

19. The method of claim 14, wherein the trace comprises a hash determined using a hash function with arguments that comprise a pointer associated with the value being tested for membership.

20. The method of claim 19, wherein the arguments of the hash function further comprise a random number associated with the pointer.

21. The method of claim 13, further comprising assigning a null value to the values in the second subset.

22. The method of claim 13, further comprising applying a random permutation to the values prior to the grouping of the values.

23. The method of claim 13, further comprising applying a limit to the size of the first subset.

24. The method of claim 13, further comprising assigning each member of the first subset a unique item number.

25. A system comprising

a bus;

a processor coupled to the bus; and

a memory unit coupled to the bus, said memory unit containing instructions configured to be stored on a tangible medium that when executed provide a computational method comprising;

encoding items of information as a first subset of a set of binary L-bit values, wherein the complement of the first subset forms a second subset of binary L-bit values not associated with encoded items of information;

identifying a group of values comprising the values in the first and second subsets that have the same first K kits (1≦

K≦

L); and

providing a proof that is used to test whether a value is associated with the item of information, wherein K is selected such that a different proof can be used for each value in the group,

wherein providing the proof comprises producing multiple proofs each showing that a different given element is not present in the group and limiting a number of these proofs produced per group.

26. The system of claim 25, wherein the values in the group are represented as a hierarchical data structure comprising pointers that map each member of the group from a root node to a leaf node of the data structure.

27. The system of claim 26, wherein the hierarchical data structure comprises a hashed directed acyclic graph.

28. The system of claim 26, wherein K is selected such that each value in the group is associated with a different combination of pointers.

29. The system of claim 26, wherein the values in the group that are not associated with encoded items of information are associated with a single leaf node.

30. The system of claim 26, wherein different combinations of pointers map the values in the group that are not associated with encoded items of information from the root node to the same leaf node.

31. The system of claim 26, wherein the proof comprises a hash determined using a hash function with arguments that comprise a pointer associated with the value being tested for membership.

32. The system of claim 31, wherein the arguments of the hash function further comprise a random number associated with the pointer.

33. The system of claim 25, wherein a random permutation is applied to the values before identifying the group.

34. The system of claim 25, wherein the size of the first subset is limited.

35. The system of claim 25, wherein each member of the first subset is assigned a unique item number.

37. The application instructions of claim 26, wherein the method further comprises representing the values in the set as a hierarchical data structure comprising pointers that map each member of the set from a node of the data structure to a leaf node of the data structure.

38. The application instructions of claim 37, wherein the hierarchical data structure comprises a hashed directed acyclic graph.

39. The application instructions of claim 37, wherein K is selected such that each value in the set is associated with a different combination of pointers.

40. The application instructions of claim 37, wherein the values in the set that are not associated with encoded items of information are associated with a single leaf node.

41. The application instructions of claim 37, wherein different combinations of pointers map the values in the set that are not associated with encoded items of information to the same leaf node.

42. The application instructions of claim 37, wherein the proof comprises a hash determined using a hash function with arguments that comprise a pointer associated with the value being tested for membership.

43. The application instructions of claim 42, wherein the arguments of the hash function further comprise a random number associated with the pointer.

36. A non-transitory computer readable medium containing application instructions where the instructions, when executed, effect a method of determining whether an item of information is included in a data set, the method comprising:

accessing binary L-bit values associated with encoded items of information;

grouping the binary values into a set comprising values that have the same first K bits ((1≦

K≦

L)), the set also comprising the L-bit values not associated with encoded items of information; and

providing a proof that is used to test whether a value in the set is associated with the item of information, wherein K is selected such that a different proof can be used for each value in the set,

wherein providing the proof comprises producing multiple proofs each showing that a different given element is not present in the group and limiting a number of these proofs produced per set.

44. The application instructions of claim 36, wherein the method further comprises applying a random permutation to the values prior to the grouping of values.

45. A system for determining whether an item of information is included in a data set, the system comprising:

means for encoding items of information as binary values;

means for grouping the binary values into a set comprising values that have the same first K bits (1≦

K), wherein the set comprises a first subset of values associated with encoded items of information and a second subset of values not associated with encoded items of information; and

means for providing a proof that is used to test whether a value in the set is associated with the item of information, wherein K is selected such that a different proof can be used for each value in the set,

wherein providing the proof comprises producing multiple proofs each showing that a different given element is not present in the group and limiting a number of these proofs produced per set.

46. The system of claim 45, further comprising means for representing the values in the set as a hierarchical data structure comprising pointers that map each member of the set from a root node of the data structure to a leaf node of the data structure.

47. The system of claim 45, further comprising means for randomly permuting the values prior to the grouping of values.

48. The system of claim 45, further comprising means for limiting the size of the first subset.

49. The system of claim 45, further comprising means for assigning each member of the first subset a unique item number.