Verifiable Publish/Subscribe Queries over Outsourced Data Streams

Today’s data streaming platforms, such as Twitter, Facebook, and Bitcoin, continuously generate a massive amount of data at an unprecedented scale. For example, over 500 million tweets are posted on Twitter each day1 and over 200,000 transactions are managed by Bitcoin each day.2 Building publish/subscribe systems for these platforms that allow subscribers to filter relevant data objects has many real-world applications. For example, Twitter users may want to be updated with tweets on a specific event (e.g., “apartment rental”); Bitcoin users may want to be kept abreast of transactions issued by specific parties (e.g., angel investors). To support millions of subscription queries, outsourcing publish/subscribe query processing to a third-party cloud has been deemed a desirable solution to scaling up systems. However, the outsourcing of query processing naturally raises the issue of trust, making it indispensable for subscribers to verify the results returned by the cloud.

Despite extensive research on authenticated query processing for outsourced databases, there is limited work on outsourced data streams, which pose new challenges. First, data streams are unbounded and arrive online continuously, which renders inapplicable previous techniques that count on authenticated data structures (ADSs) built on a fixed dataset. We need to design new ADSs that support incremental online aggregation. Second, besides the soundness of individual query results, subscribers must be able to verify the temporal completeness (i.e., that there are no missing results in between stream updates). Third, query authentication must be lightweight in support of real-time streaming services. Fourth, the system should be scalable to handle a large number of subscription queries simultaneously.

In this project, we take a first step to comprehensively investigate the problem of authenticating publish/subscribe queries regarding outsourced data streams. We will leverage the notion of the blockchain to design novel data structures, security primitives, and query authentication techniques. The research agenda of this project is planned as follows: 1) optimization of the blockchain structure for data streams in support of verifiable publish/subscribe queries; 2) development of accumulator-based ADSs and query authentication algorithms for the verification of Boolean-based subscription queries in both real-time and lazy authentication modes; 3) study of novel query indexing techniques for scalable authentication; 4) extension of the proposed techniques to top-k publish/subscribe queries and historical time-window queries; 5) security analysis and performance evaluation of the proposed solutions under real-world settings.