  The scalability problem has been one of the most significant barriers
limiting the adoption of blockchains. 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 focuses on the transaction allocation problem to reduce the number
of cross-shard transactions for better scalability. In particular, we
systematically formulate the transaction allocation problem and convert it to
the community detection problem on a graph. A deterministic and fast allocation
scheme TxAllo is proposed to dynamically infer the allocation of accounts and
their associated transactions. It directly optimizes the system throughput,
considering both the number of cross-shard transactions and the workload
balance among shards.
  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 the meantime, the workload
balance is well maintained. 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.
