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.

A number of promising blockchain scalability technologies such as Rollups, facilitate the fast and cost-effective asset transfer by offloading transactions from a mainchain to sidechains. The proposed broker-based decentralized application (dApp) in this paper, named BrokerFi, also employs a sidechain approach that works as a Layer2 solution on top of a Layer1 blockchain. Comparing with conventional sidechain solutions, the distinct feature of BrokerFi is that the sidechain used in BrokerFi is a sharded blockchain, in which users can stably earn money without economic risks when they stake money to BrokerFi.BrokerFi is designed as a dApp that can offer functionalities to enable users to manage their digital assets and earn money if they join BrokerFi’s ecology. Users can change the native tokens issued by BrokerFi using their fiat money. Users can also choose to stake their money in the protocol of BrokerFi and earn profit. We mainly demonstrate the design of BrokerFi in this paper. The significant components of BrokerFi mainly include two parts, i.e., the frontend used by users, and the backend that provides fundamental functionalities for BrokerFi in a Layer2-like sidechain. Experiment results show that the proposed BrokerFi can help clients earn high revenue when their staked tokens follow a low variance.

Abstract syntax tree (AST) mapping algorithms are widely used to locate the code changes in a file revision by mapping the AST nodes of the source code before and after the code changes. A recent differential testing of three state-of- the-art AST mapping algorithms, i.e., GumTree, MTDiff, and IJM, reveals that the algorithms generate inaccurate mappings for a considerable number of file revisions. We find that the inaccurate mappings could be caused by the mutual influence: the mappings of lower-level AST nodes (e.g., tokens) have impacts on the mappings of higher-level AST nodes (e.g., statements) and vice versa. This mutual influence issue is rarely considered by existing algorithms. In this paper, we propose an algorithm, called iASTMapper, that iteratively map two ASTs based on the similarities between AST nodes. Given a file revision, we extract three types of AST nodes in different levels of program structures (i.e., tokens, statements, and inner-statements) from the ASTs of the two source code files. We first build mappings of the unchanged statements and inner-statements. Then, we use an iterative method to map the rest of the nodes without mapping. For each of the three types of nodes, we iteratively map the nodes based on their similarities measured using heuristic rules. We further use an iterative mechanism to connect the three iterative mapping processes by considering the mutual influence between the mappings of different types of nodes. Finally, a series of code edit actions are generated from the node mappings to help users understand and locate the code changes during revisions. We conduct experiments to compare iASTMapper with three baselines, i.e., GumTree, MTDiff, and IJM, by automatically evaluating 210,997 file revisions from ten Java projects. Furthermore, we manually evaluate the correctness of the code edit actions generated for 200 file revisions with 12 evaluators. The results demonstrate that iASTMapper outperforms the baselines. iASTMapper can generate shorter code edit actions by at least 1.29% than the baselines, with a high accuracy of 96.23%.