New Gas-Efficient Authenticated Range Query Schemes in Hybrid-Storage Blockchain

Blockchain is a promising technology that ensures data integrity for applications. However, the expensive cost of blockchain storage makes putting all data on-chain impossible. Hybrid-storage blockchain (HSB) can alleviate this problem by storing the data content off-chain and the data hash on-chain while using an authenticated data structure (ADS) in the smart contract to ensure the integrity of data storage and retrieval. The key challenge in HSB is minimizing the maintenance cost of ADS on-chain. In this paper, we focus on the authenticated range query in HSB and propose a new scheme named UpOnFly to efficiently maintain the root of the MB-tree as ADS for any dynamic changes without using all the data or storing internal nodes of the tree in the smart contract. Furthermore, without sacrificing much off-chain verification performance, we propose another new scheme named KeyLink that decouples the on-chain ADS and the off-chain index and only maintains the order of all data keys in the smart contract, in which the ADS maintenance cost is significantly reduced and will not increase with the dataset size. Extensive experimental results demonstrate that the UpOnFly scheme requires only <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$63\%$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$48\%$</tex-math></inline-formula> of the gas consumption of the state-of-the-art approach <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$GEM^{2*}$</tex-math></inline-formula>-tree with the dataset size of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$10^6$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$10^8$</tex-math></inline-formula>, respectively. The KeyLink scheme is even more efficient, requiring only <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$29\%$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$18\%$</tex-math></inline-formula> of the gas consumption of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$GEM^{2*}$</tex-math></inline-formula>-tree with the dataset size of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$10^6$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$10^8$</tex-math></inline-formula>, respectively.