Verifiable Arbitrary Queries With Zero Knowledge Confidentiality in Decentralized Storage

Blockchain-based data storage has become an emerging paradigm, providing a fair and transparent data platform for decentralized applications. However, how to achieve secure on-chain verification for arbitrary SQL queries in such a decentralized storage remains under-explored. Due to the limitations of authenticated data structure (ADS), existing works either do not consider arbitrary query verification issue or fail to achieve practical gas consumption efficiency. In this paper, we present a novel arbitrary query verification scheme for decentralized storage. The proposed scheme, named zkQuery, enables efficient public verification for arbitrary queries with zero-knowledge confidentiality. zkQuery is built from the ingenious synergy of techniques from both zero-knowledge proof and smart contract technology. The core idea is to delegate smart contracts to fairly execute results verification and utilize our tailored zero-knowledge proof protocol to facilitate arbitrary computation in a privacy-preserving manner. The verification protocols of zkQuery are highly customized for decentralized storage, where the complexity of on-chain verification can be completed in logarithmic time, significantly decreasing gas consumption. We rigorously provide security analysis and complete the prototype implementation. The extensive experiments over the NEAR blockchain show that zkQuery can gain at least 2× better performance than the baseline approach on all metrics.