Efficient and lightweight indexing approach for multi-dimensional historical data in blockchain

Abstract

In blockchain systems, stateful data are stored globally and sequentially in the form of key-value pairs. Indeed, in addition to being one-dimensional, values can be multi-dimensional. However, in blockchain systems, existing works only consider one-dimensional data to implement indexing approaches, as a result, these approaches perform poorly when extended to multi-dimensional and historical data. To overcome these issues, in this paper we propose two new indexing models for blockchain. The first model is Two-tier Deterministic Appended Only Skip List (TDASL) that improves from LineageChain (Ruan et al., 2019, 2021) by using an additional indexing layer on top of a skip list to quickly retrieve the state versions and by using prefixes to query multi-dimensional state versions. The second model is Predefined Partitioned -plus Tree (PPBPT), which paves the way of adopting -plus tree in blockchain by addressing the challenge of its heavy reconstruction cost upon updates. To do so, PPBPT copies a predefined -plus tree, which is used for generating indexes for blockchain historical data, thereby reducing reconstruction costs. We conduct extensive experiments to verify the effectiveness of the proposed approaches under various parameter settings. In blockchain systems, stateful data are stored globally and sequentially in the form of key-value pairs. Indeed, in addition to being one-dimensional, values can be multi-dimensional. However, in blockchain systems, existing works only consider one-dimensional data to implement indexing approaches, as a result, these approaches perform poorly when extended to multi-dimensional and historical data. To overcome these issues, in this paper we propose two new indexing models for blockchain. The first model is Two-tier Deterministic Appended Only Skip List (TDASL) that improves from LineageChain (Ruan et al., 2019, 2021) by using an additional indexing layer on top of a skip list to quickly retrieve the state versions and by using prefixes to query multi-dimensional state versions. The second model is Predefined Partitioned B-plus Tree (PPBPT), which paves the way of adopting B-plus tree in blockchain by addressing the challenge of its heavy reconstruction cost upon updates. To do so, PPBPT copies a predefined B-plus tree, which is used for generating indexes for blockchain historical data, thereby reducing reconstruction costs. We conduct extensive experiments to verify the effectiveness of the proposed approaches under various parameter settings.