System and method for committing to a set

• US 20050038774A1
• Filed: 09/03/2004
• Published: 02/17/2005
• 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
• Granted Patent: US 7,831,573 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 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;

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.

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 plurality of 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, comprising producing a proof to show that a given element is not in the committed-to data set.

12. The method of claim 11, comprising producing multiple proofs each showing that a different given element is not present in the committed-to data set and limiting the number of these proofs produced per committed-to data set.

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

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

22. The method of claim 1, wherein the proof module is adapted to produce a trace from a root node to a one of the plurality of leaf nodes.

15. A system for committing to a data set, comprising:

a graph module adapted to form 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;

a commitment module adapted to commit to the directed acyclic graph to produce a committed-to data set; and

a proof module adapted to produce 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.

16. The system of claim 15, comprising a reference module adapted to use intrinsic references in the directed acyclic graph as pointers.

17. The system of claim 15, wherein the graph module is adapted to form a hash-based directed acyclic graph.

18. The system of claim 15, wherein the commitment module is adapted to commit to the hash-based directed acyclic graph by sending hashes of at least one root node.

19. The system of claim 15, comprising a blinding module adapted to blind at least one of the pointers.

20. The system of claim 15, wherein the graph module is adapted to form a prefix directed acyclic graph.

21. The system of claim 15, wherein the proof module is adapted to produce a proof to show that a given element is not in the committed-to data set.

23. A computer program for committing to a data set, comprising:

a tangible medium;

a graph module stored on the tangible medium, the graph module adapted to form 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;

a commitment module stored on the tangible medium, the commitment module adapted to commit to the directed acyclic graph to produce a committed-to data set; and

a proof module stored on the tangible medium, the proof module adapted to produce 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.

24. A method of verifying a plurality of proofs about a committed-to data set, comprising:

receiving hashes of at least one root node from a hash-based directed acyclic graph, the hash-based directed acyclic graph adapted to encode a data set, the hash-based directed acyclic graph having a plurality of pointers and a plurality of nodes wherein at least one node has multiple parents;

receiving a plurality of proofs about the hash-based directed acyclic graph 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; and

verifying the proofs.

25. The method of claim 24, comprising receiving a trace from a root node to one of a plurality of leaf nodes.

26. The method of claim 24, comprising verifying that a given element is not in the committed-to data set.

27. The method of claim 24, wherein at least one pointer in the hash-based directed acyclic graph is blinded.