Research On Blockchain Sharding Technology Based On Graph Partition And MPT Tree

In recent years,the rise of the Web3.0 concept has made it a common goal to build an open and intelligent Internet.Blockchain,as a secure,trusted,and decentralized distributed database,has introduced new possibilities for the underlying protocols of the future Internet.However,the current throughput and transaction latency of blockchain are insufficient to support the massive global network traffic.Sharding technology,which can theoretically achieve linear scalability of blockchain,has become a hot research topic in blockchain scalability.Although there have been many research works on blockchain sharding technology,and some systems have been successfully deployed,these solutions mostly have unresolved issues.This dissertation investigate blockchain sharding systems from the following aspects and propose specific solutions:(1)This dissertation presents a blockchain sharding scheme that addresses the issues of uneven shard loads,high proportion of cross-shard transactions,and large reconfiguration overhead in blockchain network sharding.The proposed scheme is based on a stream-based graph partitioning algorithm,drawing on the concept of balanced graph partitioning in distributed systems and utilizing the transaction graph of the blockchain network for network sharding.The scheme introduces a time-decaying counter to accurately predict the load status of shards and calculates the weight of each incoming transaction on each shard in real-time,aiming to reduce the replication factor and improve load balancing.Experimental results demonstrate the effectiveness of this scheme in terms of load balancing,cross-shard transaction proportion,and reconfiguration overhead.(2)This dissertation proposes a cross-shard transaction protocol based on MerklePatricia Tree(MPT)and a shard asynchronous reconfiguration mechanism to address the issues of atomicity of cross-shard transactions and large reconfiguration delay in state-sharding of blockchain.This dissertation extends the basic structure of MPT,adding records of amount locking and shard information.The cross-shard transaction protocol locks transactions using the amount locking records in the MPT and guarantees the atomicity of cross-shard transactions through a combination of two-phase commit protocol and failure rollback mechanism.In the asynchronous reconfiguration mechanism,this dissertation designs a new structure called state-block,which includes a global MPT,and publishes snapshots of global account states in state-block.Nodes can quickly perform shard reconfiguration based on the snapshot without waiting for lengthy data replication time,thus achieving asynchronous execution of shard reconfiguration and data replication.Experiments show that the proposed cross-shard transaction protocol and shard-asynchronous reconfiguration mechanism have significant advantages in throughput,transaction latency,and reconfiguration delay.