INTERACTIVE PROOF TO VALIDATE OUTSOURCED DATA STREAM PROCESSING

• US 20120143830A1
• Filed: 12/02/2010
• Published: 06/07/2012
• Est. Priority Date: 12/02/2010
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Cormode, Graham, Yi, Ke
• Granted Patent: US 8,538,938 B2
• Time in Patent Office: Days
• US Class Current: 707/687
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries

Abstract

A method for validating outsourced processing of a data stream arriving at a streaming data warehouse of a data service provider includes a proof protocol. A verifier acting on behalf of a data owner of the data stream may interact with a prover acting on behalf of the data service provider. The verifier may calculate a first root hash value of a binary tree during single-pass processing of the original data stream with limited computational effort. A second root hash value may be calculated using the proof protocol between the verifier and the prover. The prover is requested to provide certain queried values before receiving random numbers used to generate subsequent responses dependent on the provided values. The proof protocol may be used to validate the data processing performed by the data service provider.

Claims

1. A method for analyzing a data stream, the method comprising:

receiving, from a prover configured to process the data stream, a first data block and a sibling data block, wherein the first data block and the sibling data block are associated with a first level of a binary tree of hash values;

calculating a current hash value using the first data block, the sibling data block, and a first random number; and

processing a next level in the binary tree, wherein the processing of the next level in the binary tree comprises;

sending, to the prover, a current random number and a request for a sibling hash value, wherein the sibling hash value is a sibling of the current hash value;

receiving the sibling hash value;

determining a subsequent random number; and

calculating a subsequent hash value using the current hash value, the sibling hash value, and the subsequent random number.

2. The method of claim 1, further comprising:

determining a calculated root hash value for the binary tree by;

recursively performing the processing for a number of successive levels in the binary tree, wherein in each iteration of the processing;

the current hash value is replaced with a parent hash value; and

the number of successive levels is dependent on a number of data sources associated with the data stream.

3. The method of claim 2, further comprising:

comparing the calculated root hash value and a previously stored root hash value for a match; and

when the match is observed, validating the data stream.

4. The method of claim 3, further comprising:

when the match is not observed, invalidating the data stream.

5. The method of claim 1, further comprising:

sending a query to the prover to provide the first data block.

6. The method of claim 5, wherein sending the query to the prover includes sending a query selected from the group of data stream queries consisting of:

index, predecessor, dictionary, range, range-sum, self join size, frequency moment, and inner product.

7. The method of claim 1, wherein a hash value for a sibling pair X and Y is given by:

(X+R*Y)modulo P,

wherein R is a random variable and P is a prime number.

8. A computer system for validating a data stream, comprising:

a processor configured to access memory media;

wherein the memory media include instructions executable by the processor to;

store a first root hash for the data stream, wherein the first root hash corresponds to a number of levels in a binary tree;

calculate a second root hash for the data stream using a proof protocol and a prover associated with a data service provider receiving the data stream, the proof protocol comprising instructions executable by the processor to;

receive, from the prover, a first data block in the binary tree and a second data block that is a sibling of the first data block;

calculate a first hash value using the first data block, the second data block, and a first random number that is kept confidential with respect to the prover;

after calculating the first hash value, calculate a hash value for a next level in the binary tree, the calculating of the hash value for the next level comprising instructions executable by the processor to;

send, to the prover, a random number used to calculate a previous hash value and a request for a sibling hash value;

receive the sibling hash value from the prover; and

calculate a parent hash value using the previous hash value, the sibling hash value, and a next random number that is kept confidential with respect to the prover; and

recursively perform the calculating of the hash value for the next level for successive levels in the binary tree, using a preceding parent hash value as the previous hash value and a new random number as the next random number, until the second root hash for the binary tree is obtained; and

determine whether the first root hash matches the second root hash.

9. The computer system of claim 8, wherein the memory media further include instructions executable by the processor to:

when the first root hash matches the second root hash, validate that the data service provider is accurately processing the data stream.

10. The computer system of claim 8, wherein the memory media further include instructions executable by the processor to:

when the first root hash does not match the second root hash, return a fail result for the proof protocol.

11. The computer system of claim 8, wherein the number of levels in the binary tree depends on a number of data sources associated with the data stream, wherein each data source contributes a respective data block to the data stream, and wherein the proof protocol further includes instructions executable by the processor to:

send, prior to the receiving the first data block and the second data block from the prover, a query to the prover for the first data block, wherein the query includes a query selected from the group of data stream queries consisting of;

index, predecessor, dictionary, range, range-sum, self join size, frequency moment, and inner product.

12. The computer system of claim 8, wherein the instructions executable by the processor to calculate a hash value for a sibling pair X and Y use an algorithm given by:

(X+R*Y)modulo P,

wherein R is a random variable and P is a prime number.

13. The computer system of claim 12, wherein a range for R and a value for P are selected based on a desired degree of security for the proof protocol, wherein a larger range of R and a greater value of P increase the degree of security.

14. Computer-readable memory media, including instructions for validating a data stream arriving at a data service provider, the instructions executable to:

store a first root hash value for the data stream, wherein the first root hash value is derived based on a number of levels in a binary tree;

calculate a second root hash value for the data stream using a proof protocol and a prover associated with the data service provider, the proof protocol comprising instructions executable to;

receive, from the prover, a first data block in the binary tree and a second data block that is a sibling of the first data block;

calculate a first hash value using the first data block, the second data block, and a first random number that is kept confidential with respect to the prover;

after calculating the first hash value, processing a next level in the binary tree by;

sending, to the prover, a random number used to calculate a current hash value;

receiving a sibling hash value from the prover; and

calculating a parent hash value using the current hash value, the sibling hash value, and a next random number that is kept confidential with respect to the prover; and

recursively perform the processing the next level in the binary tree for successive levels in the binary tree, using a preceding parent hash value as the current hash value and a new random number as the next random number, until the second root hash value for the binary tree is obtained.

15. The memory media of claim 14, further comprising instructions executable to:

determine whether the first root hash value matches the second root hash value.

16. The memory media of claim 15, further comprising instructions executable to:

when the first root hash value matches the second root hash value, validate that the prover accurately reproduced data blocks associated with the data stream; and

when the first root hash value does not match the second root hash value, return a fail result for the proof protocol.

17. The memory media of claim 14, wherein the proof protocol further includes instructions executable to:

send, prior to the receiving the first data block and the second data block from the prover, an indication of the proof protocol to the prover, the indication specifying instructions executable by the prover to respond to the proof protocol.

18. The memory media of claim 14, further comprising instructions executable to:

after executing the proof protocol, generate new random numbers for calculating the first root hash value for respective levels in the binary tree; and

record an indication of the random numbers associated with the first root hash value for use in subsequent iterations of the proof protocol.

19. The memory media of claim 14, wherein the number of levels in the binary tree depends on a number of data sources associated with the data stream, wherein each data source contributes a respective data block to the data stream, and wherein the proof protocol further includes instructions executable by the processor to:

send, prior the receiving the first data block and the second data block from the prover, a query to the prover for at least the first data block, wherein the query includes a query selected from the group of data stream queries consisting of;

index, predecessor, dictionary, range, range-sum, self join size, frequency moment, and inner product.

20. The memory media of claim 14, wherein instructions executable to calculate a hash value for a sibling pair X and Y use an algorithm given by:

(X+R*Y)modulo P,

wherein R is a random variable and P is a prime number.