Trusted Sliding-Window Aggregation over Blockchains

Blockchain that continuously generates infinite transactions is widely applied to many decentralized applications. Applications generally focus more on the most recent transaction data to discover trends and make predictions, and thus there is an increasing demand for sliding-window aggregation over blockchains (e.g., a continuous query for the moving average of Bitcoin transaction volume over the last 24 hours). Blockchain submits transactions by block periodically, which makes it work well for sliding-window aggregation. However, the mutual distrust between blockchain nodes makes users consider both query efficiency and query authentication (e.g., simple payment verification (SPV) in Bitcoin). Aggregate B-tree can process sliding-window aggregation in a multi-query setting efficiently. In order to achieve authenticated sliding-window aggregation, a naive scheme may incorporate the Merkle tree into the aggregate B-tree, but that will complicate the index structure, and couple query logic and verification logic. In this paper, we propose a novel authenticated sliding-window aggregation scheme that separates query authentication from query processing. By designing a separate encoded Merkle tree, verification logic can authenticate query results of the aggregate B-tree by itself, without affecting query logic. We also develop an optimized scheme based on FiBA and software guard extensions (SGX), which further reduces aggregate and digest update costs. Security analysis and empirical study validate the robustness and practicality of the proposed scheme.