A Sharding Scheme Based on Graph Partitioning Algorithm for Public Blockchain

Abstract

Blockchain technology, with its attributes of decentralization, immutability, and traceability, has emerged as a powerful catalyst for enhancing traditional industries in terms of optimizing business processes. However, transaction performance and scalability has become the main challenges hindering the widespread adoption of blockchain. Due to its inability to meet the demands of high-frequency trading, blockchain cannot be adopted in many scenarios. To improve the transaction capacity, researchers have proposed some on-chain scaling technologies, including lightning networks, directed acyclic graph technology, state channels, and sharding mechanisms, in which sharding emerges as a potential scaling technology. Nevertheless, excessive cross-shard transactions and uneven shard workloads prevent the sharding mechanism from achieving the expected aim. This paper proposes a graph-based sharding scheme for public blockchain to efficiently balance the transaction distribution. By mitigating cross-shard transactions and evening-out workloads among shards, the scheme reduces transaction confirmation latency and enhances the transaction capacity of the blockchain. Therefore, the scheme can achieve a high-frequency transaction as well as a better blockchain scalability. Experiments results show that the scheme effectively reduces the cross-shard transaction ratio to a range of 35%–56% and significantly decreases the transaction confirmation latency to 6 s in a blockchain with no more than 25 shards.