State-of-the-art blockchain sharding solutions, such as Monoxide, can cause severely imbalanced distribution of transaction (TX) workloads across all blockchain shards due to the deployment policy of their accounts. Imbalanced TX distributions then producehot shards, in which the cross-shard TXs may experience an unlimited confirmation latency. Thus, how to address the hot-shard issue and how to reduce cross-shard TXs become significant challenges of blockchain sharding. Through reviewing the related studies, we find that a cross-shard TX protocol that can achieve workload balance among all shards and simultaneously reduce the quantity of cross-shard TXs is still absent from the literature. To this end, we propose BrokerChain, which is a cross-shard blockchain protocol dedicated to account-based state sharding. Essentially, BrokerChain exploits fine-grained state partition and account segmentation. We also elaborate on how BrokerChain handles cross-shard TXs through broker accounts. The security issues and other properties of BrokerChain are analyzed rigorously. Finally, we conduct comprehensive evaluations using an open-source blockchain sharding prototype namedBlockEmulator. The evaluation results show that BrokerChain outperforms other baselines in terms of transaction throughput, transaction confirmation latency, the queue size of the transaction pool, and workload balance.

Numerous blockchain simulators have been proposed to allow researchers to simulate mainstream blockchains. However, we have not yet found a testbed that enables researchers to develop and evaluate their new consensus algorithms or new protocols for blockchain sharding systems. To fill this gap, we developed BlockEmulator, which is designed as an experimental platform, particularly for emulating blockchain sharding mechanisms. BlockEmulator adopts a lightweight blockchain architecture so developers can only focus on implementing their new protocols or mechanisms. Using layered modules and useful programming interfaces offered by BlockEmulator, researchers can implement a new protocol with minimum effort. Through experiments, we test various functionalities of BlockEmulator in two steps. First, we prove the correctness of the emulation results yielded by BlockEmulator by comparing the theoretical analysis with the observed experiment results. Second, other experimental results demonstrate that BlockEmulator can facilitate measuring a series of metrics, including throughput, transaction confirmation latency, cross-shard transaction ratio, the queuing status of transaction pools, workload distribution across blockchain shards, etc. We have made BlockEmulator open-source in Github.

Cross-shard Transactions (CTXs) widely exist in sharded blockchains. CTXs have to endure large confirmation latency because they need to participate in consensus in both their source and destination shards. To diminish CTXs, plenty of state-of-the-art blockchain protocols have been proposed. For example, in BrokerChain [1], some intermediary broker accounts can help turn CTXs into intra-shard transactions through their voluntary liquidity services. Thereby, the original CTXs can be confirmed in blockchain shards quickly. However, we found that BrokerChain is impractical for a sharded blockchain because it does not consider how to recruit a sufficient number of broker accounts. Thus, blockchain clients do not have the motivation to provide token liquidity for others. To address this challenge, we design Broker2Earn, which is essentially a decentralized finance (DeFi) protocol that works as an incentive mechanism for blockchain users who choose to become brokers. Via participating in Broker2Earn, brokers can earn native revenues when they collateralize their tokens to the protocol. Furthermore, Broker2Earn can also benefit the sharded blockchain since it can efficiently spend each staked liquidity provided by brokers on diminishing CTXs. We formulate the core module of Broker2Earn into a revenue-maximization problem, which is proven NP-hard. To solve this problem, we design an online approximation algorithm using the relax-and-rounding technique. We also rigorously analyze the approximation ratio of our online algorithm. Finally, we conduct extensive experiments using real-world Ethereum transactions on both a transaction-driven simulator and an open-source blockchain testbed. The evaluation results show that the proposed Broker2Earn protocol demonstrates a near-optimal performance that outperforms other baselines, in terms of broker revenues and the usage of system liquidity.

In a sharded blockchain, transactions are processed by a number of parallel committees. Thus, the transaction throughput can be largely boosted. A problem is that some groups of blockchain nodes consume large latency to form committees at the beginning of each epoch. Moreover, the heterogeneous processing capabilities of different committees also result in imbalanced consensus latency. Such imbalanced two-phase latency brings a large cumulative age to the transactions pending in transaction pool. Consequently, the blockchain throughput can be significantly degraded. We believe that a good committee-scheduling strategy can reduce the cumulative age of transactions, and thus benefit the throughput. However, we have not yet found a committee-scheduling mechanism that works for accelerating block formation in the context of blockchain sharding. To this end, this paper studies a fine-balanced tradeoff between the transactions’ throughput and their cumulative age in a large-scale sharded blockchain. We formulate this tradeoff as a utility-maximization problem, which is proved NP-hard. To solve this problem, we propose an online distributed Stochastic-Exploration (SE) algorithm, which guarantees a near-optimal system utility. We then rigorously analyze three theoretical properties of the proposed algorithm, including the theoretical convergence time, the probability of committees’ failure due to Sybil attacks, as well as the performance perturbation brought by committees’ offline events. Finally, we evaluate the proposed algorithm using the dataset of real-world blockchain transactions. The simulation results demonstrate that the proposed SE algorithm outperforms other baselines in terms of system utility, the valuable degree of yielded solutions, latency, and throughput performance.