TxAllo: Dynamic Transaction Allocation in Sharded Blockchain Systems

Abstract

The scalability problem has been one of the most significant barriers limiting blockchain adoption. Blockchain sharding is a promising approach to this problem. However, the sharding mechanism introduces a significant number of cross-shard transactions, which are expensive to process. This paper presents TxAllo to significantly reduce the number of cross-shard transactions and to improve blockchain scalability. In particular, we explore and define the transaction allocation problem and convert it to the community detection problem on a graph. TxAllo is a deterministic scheme to dynamically infer the allocation of accounts and their associated transactions with optimal system throughput. It considers both the number of cross-shard transactions and the workload balance among shards with fast execution. We evaluate the performance of TxAllo on an Ethereum dataset containing over 91 million transactions. Our evaluation results show that for a blockchain with 60 shards, TxAllo reduces the cross-shard transaction ratio from 98% (by using traditional hash-based allocation) to about 12%. In addition, we enable an adaptive model of TxAllo to perform updates according to the previous allocation results and the newly included transactions. Compared with other methods, the execution time of TxAllo is almost negligible. For example, when updating the allocation every hour, the execution of TxAllo only takes 0.5 seconds on average, whereas other concurrent works, such as Brokerchain (INFOCOM'22) leveraging the classic METIS method, require 422 seconds.