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, because off-chain computation capacity is always better and cheaper than on-chain computation, we could further reduce the on-chain cost at the expense of little off-chain verification performance. Thus, 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 63% and 48% of the gas consumption of the state-of-the-art approach GEM ^2∗ -tree with the dataset size of 10 ⁶ and 10 ⁸ , respectively. The KeyLink scheme is even more efficient, requiring only 29% and 18% of the gas consumption of GEM ^2∗ -tree with the dataset size of 10 ⁶ and 10 ⁸ , respectively.