Enabling Authenticated Query Services on Multi-dimensional Data in Collaborative Blockchain
摘要
Blockchain technology is an innovative way for distributed collaboration among untrusted parties to ensure secure data storage and sharing. The presence of malicious nodes poses the need to verify the correctness and completeness of results in query services. Moreover, in practical applications, data stored in blockchain often consists of multi-dimensional data, which has led to the study of authenticated queries on multi-dimensional data in blockchain. The main challenge arises from the curse of dimensionality, which degrades the query efficiency and can incur high verification costs. In this paper, we propose a framework called MLAQF that supports authenticated range queries on multi-dimensional data while reducing the query and verification costs. We devise a novel learn-based authenticated data structure tailored for multi-dimensional data, the LGM-tree, which integrates the grid indexing into the Merkle tree. We construct a cost model that enables the LGM-tree to adapt to both the data and query distributions. Based on the LGM-tree, the query problem is transformed into the classification problem that predicts the grid cells of data points in the result. We also present the query and verification schemes and discuss the security of our framework. Extensive evaluation of both real and synthetic datasets shows that our approach is superior to Merkle R-tree regarding query and verification overhead.