SP-Chain: Boosting Intra-Shard and Cross-Shard Security and Performance in Blockchain Sharding

Abstract

A promising way to overcome the scalability limitations of the current blockchain is to use sharding, which is to split the transaction processing among multiple, smaller groups of nodes. A well-performed blockchain sharding system requires both high performance and high security in both intra- and cross-shard perspectives. However, existing protocols either have issues on protecting security or trade off great performance for security. In this paper, we propose SP-Chain, a blockchain sharding system with enhanced Security and Performance for both intra- and cross-shard perspectives. For intra-shard aspect, we design a two-phase concurrent voting scheme to provide high system throughput and low transaction confirmation latency. Moreover, we propose an efficient unbiased leader rotation scheme to ensure high performance under malicious behavior. For cross-shard aspect, a proof-assisted efficient cross-shard transaction processing mechanism is proposed to guard the cross-shard transactions with low overhead. We implement SP-Chain based on Harmony, and evaluate its performance via large-scale deployment. Extensive evaluations suggest that SP-Chain can process more than 10,000 tx/sec under malicious behaviors with a confirmation latency of 7.6s in a network of 4,000 nodes.

1 Introduction

Since the advent of Bitcoin [27], blockchain systems have continued to have a significant impact on society. However, the low system throughput and high transaction confirmation delays of such systems greatly hinder their usability across various infrastructures and applications. Consequently, sharding [8, 23], a promising blockchain scaling solution, has been proposed. Herein, the entire blockchain state is divided into multiple non-overlapping shards, each maintained by a group of nodes.

Performance and security are critical areas of concern in blockchain sharding systems [23, 17]. To improve sharding performance and security, considerations need to be made from both intra-shard and cross-shard perspectives. In blockchain sharding, each shard must not only handle transactions within the shard but also transmit a large number of cross-shard transactions to other shards [37, 33, 12, 19]. However, as will be discussed below, existing protocols either have issues ensuring security within and between shards or sacrifice significant performance for security.

Intra-shard security and performance: Within each shard, a specific leader is typically selected to propose blocks. Malicious leaders or attacks on leaders can severely affect intra-shard security and performance. Specifically, most existing sharding protocols [23, 17, 38, 12, 18] require each shard’s leader to produce blocks within a certain time frame and to know the next leader in advance. This allows attackers to easily launch targeted attacks on the leaders [20], weakening system security (for example, colluding with the leader for Byzantine behavior or launching DDoS attacks against the leader). Moreover, when a leader is found to be malicious or under attack, a complex view change process is required to elect a new leader [5], thereby reducing system performance.

Another issue is that many existing sharding protocols adopt generic Byzantine Fault Tolerance (BFT) consensus protocols (such as PBFT) [6] for intra-shard consensus, requiring extensive communication among shard members. Specifically, BFT-type consensus protocols typically require multi-stage communication (such as pre-preparation, preparation, commit) to ensure security in poor network connectivity and high latency situations. However, these protocols are inefficient when applied to blockchain sharding. In sharding systems, each shard generally has high network connectivity and a low and fixed message propagation cap [37, 17, 13, 38, 21]. Under such conditions, a more efficient consensus protocol with less communication overhead can be proposed for sharding systems.

Cross-shard security and performance: Many cross-shard transactions occur in blockchain sharding systems. Malicious leaders may send incorrect cross-shard transactions to other shards [38]. Because each shard maintains information isolation, the shard receiving the transaction cannot verify the validity of the cross-shard transaction, endangering system security. However, some existing sharding protocols ignore how to ensure the security of cross-shard transactions [37, 17, 12]. Other solutions [33, 38, 18] require each cross-shard transaction to be accompanied by a large amount of additional proof information to ensure security, bringing excessive overhead to the system.

To simultaneously improve intra-shard and cross-shard performance and security, the following challenges need to be addressed. First, how to design a secure and efficient leader election protocol that can both resist attacks on leaders and efficiently elect new leaders. Second, how to design an efficient intra-shard consensus protocol that takes advantage of the characteristics of sharding systems. Third, how to design efficient and secure cross-shard transaction processing mechanisms. To address these challenges, we propose the following design points:

Random Leader Rotation. To address the first challenge, the leader of each shard is frequently, randomly, and automatically changed. Specifically, leaders are rotated with each block as the cycle. To prevent attackers from knowing subsequent leaders in advance, leaders are selected based on distributed randomness only before each block is proposed. To ensure performance and security during the distributed randomness generation process, we propose a chain-based randomness generation mechanism. Herein, nodes within each shard use the signature information of previously confirmed blocks to efficiently generate unbiased distributed randomness. In addition, the automatic leader rotation mechanism eliminates the originally complex view change process, further improving the efficiency of leader election.

Two-Phase Concurrent Voting. To address the second challenge, we propose an efficient consensus mechanism suitable for sharding systems with low communication overhead. By utilizing the advantages of a small number of nodes, good network connectivity, and a high synchronization rate within each shard, we propose a synchronous consensus protocol that compresses the previous preparation and commit stages into one without violating security. Therefore, we reduce the 3 rounds of communication required by traditional consensus protocols to 2, thus accelerating the speed of intra-shard consensus.

To further improve consensus efficiency, we parallelize steps that are executed serially in traditional consensus protocols. In traditional protocols, the leader first packages transactions into a block. Then, the leader broadcasts the block. Nodes receiving the block will vote and reach a consensus. After reaching a consensus, nodes insert the block into the blockchain. Our concurrent voting protocol parallelizes these steps. Specifically, when a shard’s leader produces a new block, the members of that shard vote on and reach a consensus on the previous block. Also, while the leader broadcasts the new block, each node inserts the previous block into the blockchain. This proposed scheme provides fast block generation and confirmation rates, bringing high throughput and low latency to the system.

Proof-Assisted Efficient Cross-Shard Transaction Processing. To address the third challenge, we require cross-shard transactions to carry batched and pruned proofs for forwarding. Specifically, to allow shards to safely verify the received cross-shard transactions, we require cross-shard transactions to carry proof [25], demonstrating their validity in the sending shard. To reduce the additional overhead that proof brings to network transmission, we propose a batch proof mechanism. In this scheme, the transactions sent to the same shard are accompanied by one pruned proof (instead of each transaction requiring separate proof). This proof can help nodes batch verify the validity of all transactions sent to the same shard.

In response to the above challenges, we propose SP-Chain, a secure and efficient blockchain sharding system that enhances both intra-shard and inter-shard security and performance. Specifically, the leader rotation protocol provides a secure and efficient intra-shard leader election, the two-phase concurrent voting consensus protocol improves intra-shard consensus efficiency, and the proof-assisted efficient cross-shard transaction processing ensures cross-shard transaction security without excessive communication overhead.

We implemented the prototype of SP-Chain based on Harmony [1], a well-known public blockchain sharding project that was ranked among the top 50 in the cryptocurrency space in terms of market capitalization. We conducted extensive experiments with different numbers of shards on Amazon EC2. The experimental results show that SP-Chain can still maintain high efficiency under malicious behavior. In a network with 4,000 nodes, its throughput exceeds 10,000 tx/sec, and the transaction confirmation delay is 7.6 seconds.

2 Background and Related Work

2.1 Blockchain Sharding

In traditional blockchain protocols [27, 34], all network nodes have to agree on all the transactions. This scheme leads to very low throughput and high latency for transactions to be packed into blocks and confirmed. An alternative way is to partition nodes into disjoint shards and let each shard maintain the states of a subgroup of users [23]. Under this method, the throughput increases proportionally to the number of committees. The transaction confirmation latency is also reduced since one committee has fewer nodes. This technique is known as sharding and is considered an excellent way to help blockchain scale well.

A well-performed blockchain sharding system needs to ensure good security as well as high performance. Unlike traditional blockchain systems, in blockchain sharding systems, there are a large number of cross-shard transactions that are transmitted among shards [33, 17, 37, 28, 14, 19, 29]. Nodes need to not only process transactions within a shard, but also handle transactions across shards. Therefore, it is neccesary to consider both intra- and cross-shard aspects when analyzing the security and performance of blockchain sharding. However, previous works have problems with both intra- and cross-shard security and performance.

Issues from Intra-Shard Aspect. Existing sharding works reach consensus with limited efficiency. A major reason is that most of them [23, 17, 13, 9, 38, 12, 14, 18, 22] use BFT-typed consensus protocols suitable for scenarios with poor network conditions. Those protocols usually require multiple rounds of communication ($\geq$3) to reach consensus, slowing down the efficiency of reaching consensus. However, it is widely accepted that the network synchronization is good within each shard [37, 13, 38, 21, 17, 35]. In [37], authors apply a BFT-typed consensus protocol that is suitable for good network condition, yet their protocol still require complex communication. Authors in [2] also propose a consensus protocol for good network condition, but their protocol requires view change to change the leader under malicious cases, reducing efficiency. Some works [33] use Proof-of-Work (PoW) protocol as their intra-shard consensus. However, PoW-based protocol typically has low performance as it cannot guarantee instant finality, and it is easy to fork. In SP-Chain, we exploit the good and synchronous network condition in each shard and propose the two-phase concurrent voting consensus protocol. It reduces the number of communication rounds in consensus (2 rounds) under synchronous network without compromising security, and parallelizes the steps that need to be executed serially in the traditional consensus process, thus significantly improving the consensus efficiency.

In previous sharding systems, the leader is vulnerable to be attacked. The reason is that, in existing protocols [23, 37, 17, 12, 18, 14], a leader keeps producing blocks for a period of time and the rotation of the leader can be known in advance, leaving the chance for attackers to attack the leader. Moreover, when the leader is found to be malicious or attacked, their consensus protocols perform a complex view change process to replace the leader, which is inefficient. In SP-Chain, we design an unbiased distributed randomness generation scheme with low overhead, and propose an efficient and secure leader rotation mechanism based on our consensus protocol and the distributed randomness.

Issues from Cross-Shard Aspect. Cross-shard transaction processing is a significant part of the blockchain sharding system. However, existing cross-shard transaction processing schemes still have drawbacks on protecting security, or they increase large amount of communication overhead when securing transactions. OmniLedger [17] requires an honest client to participate during the cross-shard transaction process. A malicious client can lock the cross-shard transactions and obstruct their executions. Such behavior brings troubles for both system security and efficiency. Some works [37, 13, 12, 18] does not consider the leader to be evil when dealing with cross-shard transactions, making the cross-shard transaction execution less secure. Other works [33, 38] proposes to attach proofs to each cross-shard transaction to protect security. However, this mechanism increases the lots of communication overhead, reducing system efficiency. In SP-Chain, to protect the security of cross-shard transactions with high efficiency, we propose the proof-assisted efficient cross-shard transaction processing mechanism. In this mechanism, pruned Merkle proofs [25] are generated for transactions sent to different shards. With such design, one pruned proof is attached to a batch of transactions to verify them together, reducing the overhead.

2.2 Distributed Randomness

Distributed randomness is often used by blockchain to generate random groups or to elect leaders. However, existing distributed randomness generation methods either can be biased or involve high communication complexity. Algorand [11] proposes to use the verifiable random function (VRF) [26] to randomly select committee members. However, the randomness (seed) used in VRF can be biased by the adversary. Elastico [23] uses PoW results to generate randomness, which can be biased by adversaries. Ouroboros [16] uses the publicly verifiable secret sharing (PVSS) scheme [4] to generate the random seed for leader selection. Omniledger [17] and Gosig [20] leverages VRF [32] for its unbiased leader selection. Rapidchain exploits verifiable secret sharing (VSS) [10] for cryptographic sortition. However, these schemes involve high communication complexity ($O(n^{2})$) and thus not efficient. In SP-Chain, nodes use unbiased signature information from already confirmed blocks to quickly generate distributed randomness. This mechanism needs no extra communication among nodes and thus allows efficient and secure production of distributed randomness for leader election.

3 System and Threat Model

3.1 System Model

SP-Chain proceeds in epochs. There are multiple slots $t$ in each epoch $e$. We assume there are $n$ nodes in the network for each epoch (noting that $n$ might be changing as epoch changes). Each node is given a public/secret key pair $(PK,SK)$ through a Public-Key Infrastructure (PKI) [38]. All nodes are partitioned into $m$ shards (a.k.a. committees). Thus, there are $k=n/m$ nodes (a.k.a. members) in each shard, including one leader. To prevent Sybil attack, each node is required to generate a Sybil-proof identity when joining the system, leveraging the techniques in [17] and [37].

Our network model is similar to many previous works [37, 13, 38]. Specifically, the authenticity of all messages disseminated in the network is protected by the signature of the sender. The connections between honest nodes are well connected. Like many sharding-related studies [37, 13, 38, 21], we use a synchronous gossip protocol [15] to transmit messages across the network. This means that, within a pre-known, fixed amount of time $\Delta$, any message that is sent or forwarded by an honest node will be delivered to all honest nodes, i.e., the communication network is synchronous within each shard. To address the issue of poor responsiveness existing in any synchronous consensus and achieve long-term responsiveness, we require each shard to agree on a new $\Delta$ for about once a week, which is a similar approach to existing works [37]. In addition to the intra-shard consensus, the rest of SP-Chain is built on the assumption of a partial-synchronous network. Without loss of generality and similar to many other blockchain systems [37, 17, 23, 13, 38, 33], all nodes that participated in our system have equivalent and enough computational resources.

SP-Chain adopts the account model to represent the state of the blockchain, where each account has its own states. The states of one account are maintained by one certain shard, for computation and storage scalability. Which shard an account’s state should be stored by is determined by its address. The account address is mapped to a shard based on the output of a random oracle (e.g., the remainder of the account address divided by the number of shards). When an account initiates a transaction, that transaction is routed to the corresponding shard based on the address of its sender account. How to design smarter allocation mechanisms for accounts and transactions (e.g., [7, 30, 14, 19]) is orthogonal to this work and will therefore be discussed in our future work.

3.2 Threat Model

We build a similar threat model as previous works do [37, 13, 38]. In our model, there exists a Byzantine adversary who can take control of $<1/3$ fraction of the total nodes. Similar to the previous works, the communication channel is synchronous in one shard. Therefore, each shard can achieve an optimal fault resiliency of 1/2. Corrupted (Byzantine) nodes may collude and behave arbitrarily, such as generating and sending invalid messages (transaction manipulation), sending messages to different nodes with different values (equivocation), or not sending any or all of the messages (silence attack). Other nodes besides the above are called honest nodes, they will always obey the protocol and do not do anything beyond what is specified.

We assume the adversary is mildly-adaptive, which is a similar assumption to most existing blockchain sharding works, meaning that the adversary can only corrupt a fixed set of nodes at the beginning of each epoch (e.g., one day) and the set of corrupted nodes remains unchanged within an epoch. Moreover, we allow the adversaries to have stronger attack ability than previous studies, who can launch target attack on leaders. For example, an adversary can bribe a leader and change the leader to a Byzantine node, or it can launch DDoS attacks against a leader so the leader’s message cannot be transmitted to others. Also, all nodes can access to a collision-resistant external random oracle, similar to other works [37, 38].

4 System Overview

SP-Chain consists of four main components, leader rotation, intra-shard consensus, cross-shard transaction processing, and shard reconfiguration, shown in Fig. 1. Our protocol selects a new leader in each slot to propose one block in each shard based on unbiased randomness. Then, the intra-shard consensus is executed. When the consensus is reached, the (cross-shard) transactions are sent and executed. Each epoch consists of multiple slots followed by a reconfiguration phase, during which the shard members are reshuffled. We now explain each component and the design intuition in more detail.

Leader Rotation. To prevent attacks on the leaders and maintain high performance when leaders are malicious or attacked, we propose the leader rotation scheme. The leaders are changed frequently and randomly to prevent the attackers from knowing the leaders and launching targeted attacks. In each slot, each shard elects a new leader among the nodes. To ensure the security of the leader rotation process, the leader shall be elected based on an unbiased randomness retrieved from the confirmed block. Our distributed randomness generation scheme guarantees high efficiency when electing the new leader, as no extra communications are required. More importantly, as the leaders are rotated automatically in each slot (no matter it is malicious or honest), the view change process is eliminated, achieving high efficiency even under attacks.

Intra-Shard Consensus. To boost the intra-shard consensus performance, we propose the two-phase concurrent voting consensus protocol. We leverage the features of good network synchronization within each shard, and propose an efficient synchronous consensus protocol with less rounds of communication. Moreover, we parallelize the steps that are processed serially in the traditional consensus, and propose the concurrent voting protocol to ensure high block generation and confirmation speed, hence improving system performance.

Cross-Shard Transactions. After a block in a shard is confirmed, the cross-shard transactions are sent to corresponding shards. We should efficiently resist the malicious behaviors of leaders in cross-shard transaction processing. Therefore, we propose the proof-assisted cross-shard transaction processing scheme. In this mechanism, the transactions in a block are divided into batches according to the different shards to which they are sent. One pruned proof is generated and attached for one batch of transactions to reduce the overhead. The shard who receives the cross-shard transactions then verifies them based on the proof and packs them into the block.

Shard Reconfiguration. Reconfiguration happens at the end of each epoch. During the reconfiguration phase, all the shards reshuffle their shard members. SP-Chain applies the Cuckoo rule [31, 37] for reconfiguration to allow the shard’s nodes to change.

Figure 1: Overview of SP-Chain.

5 Protocol Design

This section presents the detailed design of SP-Chain. We first describe our two-phase concurrent voting intra-shard consensus in Sec. 5.1. Based on the proposed consensus protocol, we describe the leader rotation mechanism in Sec. 5.2. Next, we describe how cross-shard transactions are efficiently and securely processed in Sec. 5.3. Finally, finish this section by briefly describing the shard reconfiguration in Sec. 5.4.

5.1 Intra-Shard Consensus

Our intra-shard consensus mechanism has two major design points: (1) Based on the feature that each shard contains a small number of nodes and has a good network synchronization rate, we design an efficient synchronous voting consensus protocol with two-phase communication; (2) Based on the two-phase voting, we propose the concurrent voting scheme that converts the serially executed steps in traditional consensus into parallel.

Two-Phase Voting. Our two-phase voting consensus protocol is divided into: phase 1, transaction package and block broadcast; phase 2, voting and block insertion. It is essentially a synchronous consensus mechanism, which achieves optimal resiliency of 1/2 in each shard and hence, allows total resiliency of 1/3 [37]. Details of the mechanism are described as follows.

Transaction Package and Block Broadcast. In each slot, the current leader packs the transactions into a block, and broadcasts the block and a simple block digest to its committee. The digest of a block mainly contains the current block number and slot number, the block hash, and the leader’s identity. The digest is used to do some pre-validation of the block. Since the size of the block digest is small, the member will receive the digest first. As there is a definite delay upper bound in the synchronous network model, we define the broadcast delay upper bound of the block digest as $\triangle_{d}$, which means every member in the shard will receive the block digest within $\triangle_{d}$ after the leader broadcasts the block and the digest. We also define the broadcast delay upper bound of the block and digest as $\triangle_{b}$, meaning that each member will receive the block and the digest within $\triangle_{b}$ after the leader broadcasts them.

Our consensus mechanism does not require clock synchronization between nodes. Suppose that a member in a shard receives the block digest at $\delta_{i}<\triangle_{d}$ moment after the broadcast. At that moment, it will start its clock and wait for the broadcasted block. Note that there is no requirement for all members to synchronize network clock information, as clock synchronization is impractical for a decentralized system like blockchain. We only require that each node’s time flow rate is consistent, which is a reasonable assumption [2].

Voting and Block Insertion. In normal case, after a member waits for $\triangle_{b}$, it will vote on the block. Members will verify whether the transactions are valid and broadcast voting information to the network. We define the delay upper bound of broadcasting voting information as $\triangle_{v}$. Since the clocks between nodes are not synchronized, each node during the voting process needs to wait for $\triangle_{d}+\triangle_{v}$ to ensure that every member of the shard receives the voting information of other members. After the waiting time, if more than $k/2$ ($k$ is the number of nodes in each shard) of the votes are received to approve the block, the member commit the block to its local ledger. Otherwise, it will treat the block as invalid and enter the next time slot.

Remarks. There are usually 3 rounds of communication (e.g., pre-prepare, prepare, commit) in previous consensus protocols [23, 17, 13, 38] under partial-synchronous network. In our proposed protocol, there are 2 rounds of communication. The first round is block broadcast, which is similar to the pre-prepare phase in previous consensus. The second round is voting, which can be seen as the compaction of the prepare and commit phase. The two-phase voting consensus protocol exploits the features of the synchronous network in each shard, such as the guaranteed delay upper bound and the high connectivity between honest nodes. In this synchronous network context, the proposed protocol reduces the communication overhead without compromising security. More importantly, our design leverages the fact that each shard consists of a small number of nodes. This feature keeps $\triangle_{d}$, $\triangle_{b}$ and $\triangle_{v}$ at a small value, which shortens the interval of each slot and improves the protocol efficiency.

Concurrent Voting. To shorten the delay of each slot and further improve system performance, we propose a concurrent voting scheme based on two-phase voting, shown in Fig. 2. In each slot, the consensus protocol can be generally divided into four serially executed steps: transaction package, block broadcast, voting, and block insertion. With concurrent voting mechanism, these steps are broken down and reorganized. Specifically, in slot $t$, when the leader is packing transactions for the newly proposed block $b_{t}$, the members in the meantime are voting for the last proposed block $b_{t-1}$ (if the leader in slot $t-1$ did not propose a block, the value should be $b_{t-2}$). Additionally, when the leader broadcasts block $b_{t}$, members insert block $b_{t-1}$ at the same time.

Design Challenges. The concurrent voting brings additional design challenges. Details are described as follows.

First, the concurrent voting enables the leader to pack the transactions into block $b_{t}$ when the members are voting for block $b_{t-1}$. However, in concurrent voting, the leader when generating block $b_{t}$ cannot decide which block should $b_{t}$ be chained after, as the voting for the last block is not over yet. Therefore, after packing transactions, the leader should wait for the voting finish to finally seal the block $b_{t}$. The voting contains the voter’s signature, current slot number, and the hash of the latest valid block the voter thinks. When the voting phase is over, the leader decides which block should $b_{t}$ be chained after, according to the voting results (e.g., when more than $k/2$ of the members think $b_{t-1}$ is valid, then $b_{t}$ is chained after $b_{t-1}$). The leader then constructs the block header and finish the transaction packaging.

Second, if block $b_{t-1}$ is invalid, the transactions in block $b_{t}$ might need to be re-packed in concurrent voting, which damage the system performance. To address this, the leader’s transaction packaging for block $b_{t}$ needs to be executed after it receives the broadcast of block $b_{t-1}$. After the leader for generating block $b_{t}$ receives the broadcast for $b_{t-1}$, it first verifies $b_{t-1}$ and packs transactions which are mutually exclusive to the transactions in $b_{t-1}$ (e.g., transactions sent by different accounts). In this way, the block $b_{t}$ can be generated successfully no matter the block $b_{t-1}$ is valid or not.

Remarks. Our concurrent voting is different from previous pipelined consensus protocols [20, 36], where they focus on the parallelization of the communication. In concurrent voting, we decouple the consensus process in a more fine-grained way, where both communication and computation are parallelized. Also noting that the computation power is usually assumed to be sufficient. Therefore, the network is the bottleneck, rather than computation. Hence, in practice, the transaction package and block insertion (computation) take less time than voting and block broadcasting, respectively. Finally, since each node’s clock is not synchronized, a node may receive a vote (or digest) before its waiting time $\triangle_{d}+\triangle_{v}$ (or $\triangle_{d}$) is over. In this case, the node verifies the received message while waiting for the waiting time to end.

Figure 2: Overview of concurrent voting.

5.2 Leader Rotation

Based on the concurrent voting consensus protocol, we now propose the random leader rotation mechanism to determine each block’s producer securely and efficiently. When a node enters a new slot, it will judge whether to be the new leader through distributed randomness generation. Each leader is responsible for proposing one new block. To prevent malicious nodes from biasing the result of leader rotation, the choice of randomness is critical. Therefore, we propose an unbiased distributed randomness generation scheme that can ensure the security of leader rotation.

Chain-Based Randomness Generation. At the beginning of each slot, a new random number is calculated to elect the leader of that slot. Specifically, when a node starts slot $t$, it extracts the signature information from the latest confirmed block (e.g., $b_{t-2}$, as the consensus is not reached for $b_{t-1}$ due to concurrent voting). Each node uses the signature information and the current slot number $t$ as a seed, input the seed to a publicly known pseudo-random number generation function (i.e., the random oracle mentioned in Sec. 3.2). This function will uniformly map the value of the seed to one of the nodes. The selected person is the leader in slot $t$ and is responsible for generating block $b_{t}$.

Choice of Signature Information. The most crucial point in the above process is the choice of signature information. When the selected signature information is not biased, it can be ensured that the leader election is unbiased. For this reason, we design that when $l_{t}$ (leader of slot $t$) generates a block, it will sign the current slot number $t$ and leave the signature information $SIG_{l_{t}}(t)$ in the block header, shown in Fig. 3. In this way, each member can use the signature from the latest confirmed block (e.g., $SIG_{l_{t-2}}(t-2)$) as the seed to calculate the new leader. For example:

$$l_{t}=F(SIG_{l_{t-2}}(t-2),t),$$ (1)

where $F(\cdot)$ is the random oracle that uniformly maps the input to one of the leader candidates.

5.3 Cross-Shard Transactions

The processing of cross-shard transactions should ensure safety and efficiency simultaneously. Specifically, since each shard does not know other shards’ state, a shard that receives cross-shard transactions (a.k.a. destination shard) cannot directly verify whether the received cross-shard transactions are confirmed in the source shard (shard that sends cross-shard transactions). A malicious leader can therefore send arbitrary cross-shard transactions or generate dummy signatures to deceive the destination shards [38]. To prevent such problems, we design a low-overhead, proof-assisted cross-shard transaction processing scheme to achieve the purpose of ensuring security while maintaining high efficiency.

We leverage the Merkle Tree to verify the correctness of a transaction. A straightforward idea is to attach a proof (i.e., a complete Merkle path) to each cross-shard transaction so that the destination shard can verify the validity of the cross-shard transaction, but this approach introduces lots of overhead. To reduce the overhead, our main idea is that, for the transactions in a block, we arrange them and construct Merkle Tree according to different shards. Based on the constructed Merkle Tree, the transactions sent to the same shard are attached with one pruned Merkle proof together. One such proof can be used to verify this batch of transactions simultaneously.

Construction of Merkle Tree. The transactions packed into a block are no longer randomly arranged and constructed into a Merkle Tree as traditional approaches. In SP-Chain, transactions sent to the same shard will be sorted first according to their transaction hash values, as shown in Fig. 3. The sorted transactions sent to the same shard will then be constructed into a Merkle Subtree. Different Merkle Subtrees (representing transactions sent to different shards) will be merged into a complete Merkle Tree, including transactions sent to all shards. The Merkle root of the complete Merkle Tree will be written into the block header and verified by members during consensus.

Sending of Cross-Shard Transactions. After a block is confirmed by consensus, the leader producing the block will send the cross-shard transactions contained in the block to the corresponding shards. While sending cross-shard transactions, the leader will broadcast the block header to all other shards. To enable cross-shard transactions to be verified by the destination shard, the leader also needs to broadcast the roots of all Merkle Subtrees to the network. In our design, cross-shard transactions sent to the same shard will be sent in batch. Moreover, the Kademlia routing algorithm [24] is used for the routing of cross-shard transactions.

Receipt and Verification of Cross-Shard Transactions. After receiving the messages mentioned above, the destination shard reconstructs the corresponding Merkle Subtree root, and then reconstructs the Merkle Tree root based on other received Merkle Subtree roots. After the reconstruction, any node in the destination shard can judge whether the received transactions are modified by comparing the reconstructed Merkle Tree root with the Merkle Tree root in the signed block header. To prevent the leader from forging shard members and signatures, a shard member table (see Sec. 5.4 for details) is maintained by each node. The table contains the valid public keys of all nodes in all shards. In this way, after receiving the header, the destination shard can check whether there is an illegal member’s signature by comparing the member table.

Figure 3: Structure overview of a block.

5.4 Shard Reconfiguration

The main components of our shard reconfiguration are similar to RapidChain [37], which includes: 1) Offline PoW to prevent Sybil attacks; 2) Epoch randomness generation; 3) Committee reconfiguration; 4) node fast initialization after joining the committee. The main difference between our design and theirs lies in the epoch randomness generation. The epoch randomness is used to solve the offline PoW and reshuffle shard members. In SP-Chain, for efficiency and security, we use our chain-based randomness to generate epoch randomness. Specifically, since the block headers are broadcasted (Sec. 5.3), the reference committee [37, 1] can collect the seed information in all confirmed blocks in the last epoch. The reference committee then XOR the seeds to obtain a new epoch seed and use it to generate the epoch random number. Each new node can request the randomness of this epoch as a fresh PoW puzzle. Additionally, during shard reconfiguration, node change information (join or leave) will be broadcast. According to the node change information, each shard generates a state block containing the shard member table (of all shards).

6 Security and Performance Analysis

We first analyze the system failure probability during each epoch. Under negligible system failure probability, we then analyze the security for our main components and discuss their overhead.

6.1 Epoch Security

We first calculate the failure probability of each epoch. Similar to previous works [9, 37, 17, 23], we use the hypergeometric distribution for calculation. In particular, let $X$ be a random variable representing the number of Byzantine nodes assigned to a shard of size $k=n/m$, given the overall network size of $n$ nodes among which up to $f$ nodes are Byzantine. The failure probability for the system in each epoch is at most:

$$Pr[X\geq\lfloor k/2\rfloor]=m\cdot\stackrel{{\scriptstyle[}}{{x}}=\lfloor k/2\rfloor]{k}{\sum}\frac{{f\choose x}{n-f\choose k-x}}{{n\choose k}}.$$ (2)

Ensuring Negligible Failure Probability. We should carefully choose the shard size to bound the failure probability of the system to be negligible. As will be explained in Sec. 7.1, our choice of shard size can limit the failure probability to be less than $2^{-20}\approx 9\cdot 10^{-7}$ (time-to-failure of more than 4580 years for one-day epoch), which is a wide-adapted probability threshold [9, 37].

Under negligible epoch failure probability, we next analyze the security and performance of our system.

6.2 Analysis of Randomness Generation

In this part, we mainly analyze our chain-based distributed randomness generation scheme’s security and performance, as it affects the leader rotation results. We will show that our scheme possesses unbiasability, unpredictability, verifiability, and scalability [32].

Unbiasability: The generated randomness represents an unbiased, uniformly random value, except with negligible probability. In our chain-based distributed randomness generation scheme, the slot information $t$ is publicly known and cannot be manipulated. The random oracle that uniformly maps the seed to the leader is also publicly known, so it cannot be manipulated and corrupted by a single node. Therefore, we will show that the signature information used in the randomness generation process cannot be biased, except with negligible probability.

First, according to Sec. 3, each newly joined node generates a Sybil-resistant identity, and is assigned a key pair by PKI, and will be randomly assigned to a specific shard. Second, according to the shard reconfiguration, nodes will update their shard member table before each epoch. Therefore, except with negligible probability, a leader cannot generate multiple legal identities/signatures in the same shard. Even if a malicious leader generates multiple legal signatures in some ways (e.g., bribing other node’s identity), as long as the total number of malicious nodes in a single shard does not exceed $k/2$, our system can guarantee security. In this case, the randomness generation process still cannot be biased. Because a malicious node cannot control the signature output, and the signature needs to be verified by all nodes in the shard. Therefore, the chain-based distributed randomness generation scheme is unbiased.

Unpredictability. No party learns anything about the generated randomness, except with negligible probability, until the last confirmed block is determined. At the beginning of slot $t$, each node will use the signature information on the latest confirmed block to determine the new leader. Therefore, the new randomness cannot be predicted until the last confirmed block is determined. The decision of the last confirmed block is carried out in $t-1$ slot. Therefore, before the start of $t-1$ slot, the new randomness cannot be predicted except with negligible probability.

Verifiability. The generated randomness is third-party verifiable. The random oracle, shard member information, leader candidate list, and the generated blocks are all publicly known. Therefore, anyone can verify the randomness generation process.

Scalability. The randomness generation process is highly scalable. Since our random number generation scheme only requires nodes to obtain information from the past blockchain and perform distributed calculations, no additional communication overhead is introduced during the randomness generation process. This is a considerable advantage compared to the $O(k^{2})$ communication overhead introduced in the previous works. Therefore, our randomness generation mechanism is highly scalable.

6.3 Analysis of Intra-Shard Consensus

We now analyze the security of our intra-shard consensus, i.e., the two-phase concurrent voting protocol and the leader rotation scheme.

Safety of Intra-Shard Consensus. Safety here means that all honest nodes in each shard agree on the same state of the shard (i.e., no forks or inconsistencies in each shard). We will prove that any honest node can receive the votes from all other honest nodes within the waiting time $\triangle_{d}+\triangle_{b}+\triangle_{v}$, and reach a consensus. Similar to the previous assumptions, our intra-shard consensus is based on the synchronous network model. Suppose that an honest node $i_{first}$ receives the digest first at time $t_{0}$, and another honest node $i_{last}$ receives the digest last at time $t_{0}+\delta$. It is obvious that $\delta\leq\triangle_{d}$. Suppose that in the worst case, $\delta=\triangle_{d}$. Then when $i_{last}$ waits for $\triangle_{b}$ and starts voting, $i_{first}$ has waited for $\triangle_{b}+\triangle_{d}$ (has started voting and broadcasted its vote). At this time, $i_{first}$ needs to wait for $\triangle_{v}$ to ensure that it can receive the vote broadcasted by $i_{last}$. Therefore, it can be proved that any honest node can receive the votes of all honest nodes and reach a consensus during the waiting time.

Our protocol is secure under various malicious behaviours. First, when a malicious leader tries to send messages with different values to different nodes (equivocation attack), all the honest nodes will notice that via different block digests. If the equivocation attack is detected, each node immediately launches the voting process without waiting for $\triangle_{b}$, and the voting procedure can still be finished within the waiting time. When a malicious node tries to send different votes, this behavior will also be discovered by honest nodes and the malicious node’s vote will be treated as invalid. Second, when a malicious leader fails to send messages (silence attack), then none of the nodes in the shard will receive the valid block during the waiting time. After the waiting time (i.e., period of one slot), a new leader will be elected and a new round of consensus will automatically start. When malicious nodes launch silence attacks, this behavior will not affect consensus reaching as long as the number of per-shard malicious nodes does not exceed $k/2$. This is because honest nodes can always collect enough valid votes to reach consensus within the waiting time. Third, when a malicious leader (or node) tries to send invalid messages (e.g., transaction manipulation, forging signatures), honest nodes will detect such malicious behaviours during voting process, since nodes will verify every received messages. In summary, when the malicious nodes in the shard does not exceed $k/2$, the malicious behaviours cannot pass our intra-shard consensus, our two-phase concurrent voting thus maintain safety against various typical Byzantine behaviours.

Liveness of Intra-Shard Consensus. Liveness here represents the system’s responsiveness and that it keeps making progress (i.e., all valid blocks are eventually added to the chain of each shard). Note that the expectation round for an honest leader is around two in the worst case ($<k/2$ malicious nodes per shard). According to the leader rotation scheme we proposed, no matter the current leader is good or bad, a new leader will be automatically elected at the beginning of a new slot. In our intra-shard consensus protocol, every honest node has the same view on the validity of the proposed block in each slot. Therefore, no matter whether the leader is malicious or not, all honest nodes will automatically elect the next leader after the voting period. Therefore, a valid block will eventually be produced by an honest leader.

Network condition may change over time. SP-Chain applies similar solutions to previous works [37, 13] to alleviate such responsiveness issue of synchronous consensus. Specifically, SP-Chain runs a pre-scheduled consensus among shard members about every week to agree on a new $\Delta$ so that the system adjusts its consensus speed with the latest average delay of the network. It can make the protocol responsive to long-term, more robust changes of the network as technology advances, ensuring that messages will be delivered to the whole shard within the time limit. If the network changes unexpectedly, nodes may find that the intra-shard consensus is temporarily suspended, as they may not receive enough votes during the waiting time. They will then agree on a new $\Delta$ to recover the protocol in time. As a result, our intra-shard consensus can alleviate the responsiveness issue and ensure liveness.

6.4 Analysis of Cross-Shard Transactions

We now analyze the security and overhead of our cross-shard transaction processing scheme.

Security of Cross-Shard Transactions. In SP-Chain, cross-shard transactions can guarantee eventual atomicity like other works [33, 1]. Similar to the design of [33], cross-shard transactions are divided into two parts: withdrawal and deposit. In the source shard, the sender’s fund will be withdrawn first. When the source shard confirms the withdrawal, the deposit part will be sent to the destination shard and wait for execution. It is possible that the destination shard’s current leader is malicious and does not execute the deposit. However, sooner or later, an honest leader will be elected to execute the deposit and eventually achieve the transaction’s atomicity. Another possibility is that the leader in the source shard does not send the deposit part. In this case, the clients (users who send transactions) can inform the shard node that it has not received the corresponding deposit. So that the deposit part is resent, and the eventual atomicity is achieved.

In the process of cross-shard transactions, malicious leaders may tamper with cross-shard transactions. In this case, the destination shard nodes can verify whether the cross-shard transactions have been tampered with through the Merkle proof. Moreover, in our scheme, each node updates and maintains the shard member table of all shards in each epoch. Therefore, the malicious leader cannot deceive the destination shard’s nodes by forging the signature information. In summary, our cross-shard transaction processing scheme guarantees security.

Communication Overhead Analysis. Suppose a block contains a total of $N$ cross-shard transactions, where the number of cross-shard transactions sent to shard $j$ is $N_{j}$. In our design, since we organize the Merkle tree according to shards, we only need to send the root of each Merkle subtree to verify cross-shard transactions. Therefore, for each cross-shard transaction, the additional communication overhead is $O(m/N_{j})$. Correspondingly, in [33], the extra communication overhead of each cross-shard transaction is $O(log_{2}(N))$. There might be thousands of transactions in a block, and most of them are cross-shard [33, 37, 17]. However, there usually are only dozens of shards at most. Therefore, our cross-shard processing scheme has a lower overhead under general cases.

(a) Latency of broadcasting a digest.

(b) Latency of broadcasting a block (w/ digest).

(c) Latency of broadcasting a vote.

Figure 4: Latency of broadcasting a digest, a block (with digest), and a vote.

7 Implementation and Evaluation

7.1 Experimental Setup

We implement SP-Chain based on Harmony [1], one of the most advanced and well-known public blockchain sharding projects within top 50 market cap in cryptocurrency. SP-Chain is implemented in Go language with 5,000+ lines of code. We implement BLS aggregated signature [3] in the prototype to reduce the signature size for better performance. As a public blockchain sharding system, we implement a similar incentive mechanism to Harmony in our prototype. We choose to mainly use Harmony as the baseline protocol to compare the performance with SP-Chain. The main protocols in SP-Chain can be easily applied to most existing sharding systems to improve system performance. We choose Harmony as the baseline mainly for fair comparison. Besides Harmony, we also make a generic comparison of SP-Chain with some other related works.

The choice of the experimental environment is similar to that in previous work [37]. Specifically, we deploy SP-Chain on Amazon EC2 with up to 32 machines, each running up to 125 SP-Chain nodes. Therefore, the total network size scales up to 4,000 nodes. The machine is selected as c5.24xlarge, each with a 96-core processor and a 25-Gbps communication link. To simulate geographically-distributed nodes, we consider a latency of 100 ms for every message and a bandwidth of 20 Mbps for each node. In each shard, we assume that when the adversaries observe the leader, they have the ability to attack it in the next slot. Moreover, in each shard, the total malicious nodes are less than half of all nodes in a shard. We set each transaction size to 512 bytes, and each block contains up to 4,096 transactions, resulting in a block size of 2MB.

TABLE I: Choice of # of nodes per shard and corresponding failure probability.

# of shards	4	6	8	10	12	14	16
# of nodes per shard	170	190	210	220	225	230	250
Failure probability	4.6	8	5	5	8	6	2
($\cdot 10^{-7}$)

Figure 5: Throughput comparison results.

Figure 6: Transaction confirmation latency comparison results.

Figure 7: Throughput breakdown.

Choice of Shard Size. We first determine the number of nodes per shard based on Equation 2. The rule for selecting the shard size is: the failure probability of each shard should be less than $2^{-20}\approx 9\cdot 10^{-7}$ (time-to-failure of more than 4580 years for one-day epoch) [9, 37]. Table I shows the choice of shard size under different shard numbers and the corresponding failure probability. Results show that our choice of shard size makes the probability of failure less than $9\cdot 10^{-7}$ at any scale, ensuring the security of the system. The following experiments will be conducted based on the shard size determined by Table I.

TABLE II: Choice of $\triangle_{d}$, $\triangle_{b}$ and $\triangle_{v}$.

# of shards	4	6	8	10	12	14	16
# of nodes	170	190	210	220	225	230	250
per shard
$\triangle_{d}$ (ms)	445	446	476	497	512	538	564
$\triangle_{b}$ (ms)	2496	2737	2825	3236	3286	3397	3518
$\triangle_{v}$ (ms)	541	542	581	616	626	651	683

Choice of $\triangle$. The broadcast upper bound latency of digest, block and vote ($\triangle_{d}$, $\triangle_{b}$ and $\triangle_{v}$) are the 3 most important parameters in our system. To determine them, we evaluate the actual time spent in broadcasting digests, blocks, and votes in the system, and show the experimental results in Fig. 4. Specifically, the bottom/top of each bar is the minimum/maximum delay in the broadcast, and the horizontal line connected to each bar is the average delay. Based on the measured actual broadcast delay, we set the broadcast delay upper bound as $delay_{max}+\sigma$. Where $delay_{max}$ is the actual maximum broadcast delay, $\sigma$ is the standard deviation obtained by fitting the broadcast delay to a normal distribution. Table II shows the calculated delay upper bounds $\triangle_{d}$, $\triangle_{b}$ and $\triangle_{v}$ under different shard sizes. By default, we will conduct experiments based on these values.

TABLE III: Generic comparison of SP-Chain with several existing blockchain sharding systems.

System	Performance		Security
	Throughput (tx/s)	Latency (s)	Unbiased randomness	Resist malice during	High efficiency
				cross-shard tx	under malice
Monoxide (1800 nodes)	600	15	Do not require	$\surd$
RepChain (1800 nodes)	5628	58.2
RapidChain (1800 nodes)	4220	8.5	$\surd$
RapidChain (4000 nodes)	7380	8.8
SP-Chain (1800 nodes)	6650	6.4	$\surd$	$\surd$	$\surd$
SP-Chain (4000 nodes)	10305	7.6

7.2 System Throughput

We evaluate the throughput and scalability of SP-Chain under different scales. Fig. 5 shows the comparison results, where the purple bar is SP-Chain, and the yellow bar is Harmony. The figure shows that the throughput of SP-Chain can reach up to $2.8\times$ of Harmony. Under the network scale of 4,000 nodes, SP-Chain’s throughput is $2.6\times$ of Harmony (10,305 vs 3,901). Moreover, according to the Table III, SP-Chain’s throughput is better than several other existing works. Furthermore, Fig. 5 shows that the throughput of SP-Chain increases linearly with the expansion of the network scale. The above results indicate the superior throughput and scalability of SP-Chain.

7.3 Transaction Latency

In this section, we evaluate the transaction confirmation delay of SP-Chain. Figure 6 shows the comparison results. The transaction confirmation delays in SP-Chain are all less than half of that in Harmony. Under the network scale of 4,000 nodes, the delay of SP-Chain is only 0.48 (7.6s vs 15.7s) of Harmony. As the number of shards increases, the confirmation latency in both SP-Chain and Harmony increases as well. This is mainly because that as the number of shards increases, the number of nodes inside each shard also increases, so the intra-shard consensus takes longer time to finish. Furthermore, according to the Table III, the transaction delay of SP-Chain is also the lowest in those existing works.

7.4 System Decomposition

In this section, we decompose SP-Chain and evaluate the impact of different system components on the throughput in detail. We mainly analyze how much the system throughput is improved by concurrent voting and leader rotation.

Concurrent Voting and Leader Rotation. Fig. 7 shows the SP-Chain throughput results after removing the concurrent voting or leader rotation mechanism. The blue/green bar indicates the case that concurrent voting/leader rotation is removed from SP-Chain. The results show that the concurrent voting mechanism can increase throughput by up to 22%. The leader rotation mechanism increases the throughput by up to 37%. This is mainly because, with the leader rotation mechanism, the system eliminates the view change process. Under the case where the leaders are attacked by adversaries, the system’s efficiency is thus greatly increased. Under the network scale of 4,000 nodes, the concurrent voting and leader rotation mechanism increases the system throughput by 20% (10,305 vs 8,612) and 34% (10,305 vs 7,692), respectively. In summary, the concurrent voting and leader rotation mechanism improves the throughput of the system significantly.

8 Conclusions

We present SP-Chain, a sharding-based blockchain system with scalability, high throughput, low latency and reliable security. We exploit blockchain sharding systems’ features and design an intra-shard consensus protocol called concurrent voting for the sharding system. This protocol can significantly improve system performance. Based on this protocol, we propose an unbiased leader rotation scheme. It can help the system maintain high efficiency in the presence of malicious behaviors. An efficient and verifiable cross-shard transaction processing mechanism ensures the security of cross-shard transactions. We have implemented a prototype of SP-Chain. Our empirical evaluation demonstrates that SP-Chain scales smoothly to network sizes of up to 4,000 nodes showing better performance than previous works.

Mingzhe Li is currently a Scientist with the Institute of High Performance Computing (IHPC), A*STAR, Singapore. He received his Ph.D. degree from the Department of Computer Science and Engineering, Hong Kong University of Science and Technology in 2022. Prior to that, he received his B.E. degree from Southern University of Science and Technology. His research interests are mainly in blockchain sharding, consensus protocol, blockchain application, network economics, and crowdsourcing.

You Lin is currently a master candidate with Department of Computer Science and Engineering, Southern University of Science and Technology. He received his B.E. degree in computer science and technology from Southern University of Science and Technology in 2021. His research interests are mainly in blockchain, network economics, and consensus protocols.

Jin Zhang is currently an associate professor with Department of Computer Science and Engineering, Southern University of Science and Technology. She received her B.E. and M.E. degrees in electronic engineering from Tsinghua University in 2004 and 2006, respectively, and received her Ph.D. degree in computer science from Hong Kong University of Science and Technology in 2009. Her research interests are mainly in mobile healthcare and wearable computing, wireless communication and networks, network economics, cognitive radio networks and dynamic spectrum management.

Wei Wang is currently an associate professor with Department of Computer Science and Engineering, Hong Kong University of Science and Technology. He received the Ph.D. degree from the Department of Electrical and Computer Engineering, University of Toronto in 2015. Prior to that, he obtained the B.Eng. and M.Sc. degrees from Shanghai Jiao Tong University. He is also affiliated with HKUST Big Data Institute. His research interests cover the broad area of networking and distributed systems, with a special focus on big data and machine learning systems, cloud computing, and computer networks.