On Sharding Across Heterogeneous Blockchains
Yuechen Tao, Bo Li, Baochun Li
Abstract
Heterogeneous blockchains are expected to be increasingly deployed in real-world applications, making cross-chain transaction confirmations essential. Currently, confirmations for cross-chain transactions are usually accomplished through an intermediary, such as a relay chain, which may well become a performance bottleneck. Sharding has been widely used to improve the blockchain throughput through parallel transaction validations by distributing transactions into multiple sub-communities, Yet, when sharding technique is directly applied over a relay chain, it results in an excessive number of cross-shard transactions, offsetting the throughput improvement.In this paper, we propose Sliver, a novel transaction distribution mechanism specifically designed for improving the relay chain throughput for the first time. We first capture and leverage the unique characterization of transaction dependency on the relay chain, and place those transactions with dependency into one shard. Consequently, this completely eliminates cross-shard transactions. However, due to the varying nature of transaction dependency, such a transaction placement can lead to a highly skewed distribution in terms of the number of transactions (i.e., shard size) to be validated in different shards, which negatively affects the relay chain throughput. We proceed to formulate the transaction distribution as an integer optimization problem with a lexicographical minimization objective for achieving a balanced shard size. While such a problem is proved to be NP-hard, we are able to mathematically transform it to a linear programming (LP) formulation by incorporating several unique properties in the integer optimization formulation, which can then be efficiently solved using off-the-shelf LP solvers. Theoretical and experimental analyses show that Sliver is extremely efficient in solving the assignment problem and the throughput can be 5 × that of the state-of-the-art under various configurations.