New public blockchain protocol based on sharding and aggregate signatures

Abstract

Existing blockchains, especially public blockchains, face the challenges of scalability which means the processing capacity will not get better with the addition of nodes, making it somewhat infeasible for mobile computing applications. Some improved technologies are known to speed up processing capacity by shrinking the consensus group, increasing the block capacity and/or shortening the block interval. Even these solutions are met with major problems such as storage limitations and weak security. To face the realistic application scenarios for blockchain technology in the mobile realm, we propose a new public blockchain designed based on sharding, aggregate signature and cryptographic sortition which we call SAC. In SAC, the transaction rate increases with the number of shards while the length of the consensus signature is a constant. Meanwhile, in SAC, the assignment of consensus representatives is controlled by a verifiable random function, which can effectively solve the problem of centralized consensus. In addition, this paper analyzes the performance of SAC to give adequate comparison with other sharding technologies while also giving a rational security analysis. Our experimental results clearly show the potential applicability of this novel blockchain protocol to in mobile computation.

Keywords

Public blockchain aggregate signature cryptographic sortition mobile computing sharding

1. Introduction

Blockchain technology was originally introduced in the cryptocurrency Bitcoin created by Satoshi Nakamoto in [18]. Since then we have seen cryptocurrencies in which blockchain is the underlying technology start to emerge endlessly. Blockchain promotes the transformation of the notions of Internet of information to Internet of value. Intuitively, it is divided into Blockchain 1.0, Blockchain 2.0 and Blockchain 3.0. From these three versions comes programmable currency, programmable financial and programmable society respectively. Application is the core of Blockchain 3.0, but is sadly limited by low transaction rate. To meet actual needs, blockchain systems would like to be in the order of 100 s of transactions per second (TX/s), however for global payment networks, the rate would ideally be over $10, 000$ TX/s. The theoretical value of Bitcoin is very low at 7 TX/s, while Ethereum is slightly better at 15 TX/s. Ethereum achieves this higher rate by shortening the interval and including some “uncle blocks” [6]. The transaction processing capacity in current systems will never reach their full potential. Moreover, blockchain based simple games like cryptokitties will also experience congestion [4].

In order to maintain a unified chain, blockchain systems need to achieve a certain synchronization rate. At this time, the primary bottleneck is the broadcast delay. Thus, no matter what the consensus model is, be it proof of work (PoW), proof of stake (PoS), practical Byzantine fault-tolerant (PBFT) or delegate proof of stake (DPoS). All protocols need to make sure that the previous block has a certain synchronization rate. To achieve this goal, each block should not be too large and the block frequency must be limited. In [6], Decker et al. show that a message of 1 KB takes one second to reach 95% of the nodes, and a 1 MB block reaches the same percentage in less than 90 seconds. If the average transaction size is 1 KB, a 1 MB block will accommodate 1000 transactions. Therefore, in order to reduce the bifurcation probability, without any uncle blocks, it is appropriate to limit the transaction rate to 11 TX/s (1000 TX/90 s) for the blockchain system with consensus in whole network. If the propagation delay is not considered, the processing speed of users will become a new bottleneck of the transaction rate. Using the Internet median bandwidth 13 Mbps, a user can handle the upper limitation of transaction rates which is 13000 TX/s for 13 Mbps/(1 (KB/TX)) = 13000 TX/s. In case the transaction rate of the entire blockchain system is over 13000 TX/s, our options are to

reduce the block interval

increase the block capacity

However, using either of these methods will not allow users to catch up with the ledger growth rate. There are several solutions to increase transaction rates:

On the basis of the original architecture of blockchain, combining on-chain and off-chain which are known as state channels. It mainly consists of sidechain [10], lightning network [12], and Raiden network [8].

Increasing transaction rates by shrinking the consensus group, EOS [7] declared the average test transaction rate of eosio-dawn-3.0 at 3000 TX/s [15].

Using an aggregate signature to compress the transaction size which was introduced in [26]. Then, we can overthrow the existing architecture of blockchain, which is mainly the study of new distributed accounts, including Directed Acyclic Graphs (DAG) [21], byteball [2], IOTA [20], and Hashgraph [16], are all examples.

There are many concepts of public blockchains that adopt these three solutions, but there are still problems. For example, a system based on state channel faces the challenge of interaction between the states of off-chain and on-chain, and the improvement of transaction rate is also limited. EOS sacrifices part of the decentralization and will meet the ceiling of 13000 TX/s. IOTA adopts a centralized coordinator to solve the problems of availability of the system and the local security introduced, at the expense of the decentralized characteristics and the overall security of the system. Lastly are the solutions using sharding technologies, including OmniLedger [13], Zilliqa [24], Rchain [1] and a few others, breaking up the current limitations of non-scalability.

OmniLedger adopts a BFT consensus approach, which solves the operability of the epoch change by limiting the number of verifiers swapping out. In addition, for state sharding, OmniLedger solves the atomicity of cross-shard transactions through the client lock/unlock protocol, enabling clients to either submit a transaction completely across shards or obtain “rejection evidence” to cancel the state affected by partially completed transactions. This approach has the advantage the consistency problem is not a concern, and the consensus of state can be accomplished only on the basis of the information submitted by the client. Once the client crashes, the transactions themselves will be locked up.

Zilliqa is available as the first practical sharding system, its hierarchical structure and data structure are very complete. However, compared with OmniLedger, there are still some problems, such as inability to deal with transactions when in epoch transformation and powerless to state sharding. In addition the use of double-layer PoW wastes energy. On the other hand, it is easier to recentre computing power to control a shard, which leads to the security risks of inter-shard consensus.

Rchain uses the idea of hierarchical directory structure to divide the address space and make the state sharding much easier to implement. For example, shard A and shard B are attached to the same parent shard C, then if Alice (belonging to A) wants to trade with Bob (belonging to B), the transaction message should be validated by both their parent shard C so that the state of C and all child shards of it will keep the same state. The above example is a single-layer cross-shard transaction scenario, and if a multi-layer cross-shard transaction is carried out, it needs to be completed through their smallest common ancestor shard. Therefore, if the cross-shard transaction is excessive, the burden of ancestor shard will increase. In addition, address registration requires minimizing the expected cross-shard transactions, so the relationship between nodes is easier to be detected, which can lead to privacy problems [25].

The underlying cryptographic algorithms used in these sharding technologies are based on the EC-schnorr algorithm and collective signature CoSi proposed by OmniLedger. In [22], Morita et al. mentions the problem of multi-interaction in EC-schnorr algorithm. As for asynchronous networks, BLS aggregate signature is more suitable without any interactiveness, as shown in [5,19].

In this paper, we present SAC, a new blockchain system based on sharding and aggregate signature, in an attempt to raise the threshold through sharding technology and shorten propagation delay and transaction size through BLS aggregate signature. Our novel approach here gives an inter-shard transaction rate that is at least triple to Zilliqa, and an overall transaction rate that is positively correlated with the number of shards. Compared with Zilliqa, users, with balanced accounts, can participate in the validators bootstrapping by paying a mortgage, so as to resist Sybil attacks. Secondly, SAC use cryptographic sortition (CS), instead of PoW, to elect validators and assign the shards of users. Specifically, a more suitable BFT consensus for the aggregated signature algorithm is proposed so that the cross-shard transaction can be introduced consistently. We also construct an alternation algorithm to avoid the idle phase during which the system cannot process transactions, a known issue with previous implementations of blockchain technology [9,27].

This paper only introduces the core modules, the data structure, and the application layer. However, although we do not describe the data structure itself in detail, we give sample transactions in Figs 1 to 4. The rest of the paper is organized as follow. Next, Section 2 introduces the preliminaries that will be used in this paper. We then give our public blockchain based on sharding and aggregate signatures is introduced in Section 3. Section 4 analyzes the performance and security of SAC. Finally, Section 5 concludes the paper.

2. Preliminaries

In this section, we first give some notations used in the rest of the paper. If S is a set, then $| S |$ means the number of elements in this set. And $s \overset{R}{\leftarrow} S$ denotes the operation of choosing an element s from S uniformly at random. Similarly, $s \overset{M}{\leftarrow} S$ denotes the operation of choosing the maximum element s from S. If $C$ is a set and c is an element, then $C \Leftarrow {C, c}$ denote the operation of adding c to $C$ .

2.1. Bilinear mapping

Let $G_{1}$ and $G_{2}$ be two multiplicative cyclic groups of prime order p, $g_{1}$ and $g_{2}$ are generators of $G_{1}$ and $G_{2}$ . ψ is a computable isomorphism from $G_{2}$ to $G_{1}$ , with $ψ (g_{2}) = g_{1}$ . A bilinear pairing is defined to be $\begin{matrix} (1) & ζ = (n, G_{1}, G_{2}, G_{T}, e, g_{1}, g_{2}), \end{matrix}$ where $G_{1} = ⟨ g_{1} ⟩$ , $G_{2} = ⟨ g_{2} ⟩$ and $G_{T}$ are multiplicative groups of order n. Let e: $G_{1} \times G_{2} ⟶ G_{T}$ be a map with the following properties:

1) Bilinear. $\forall u \in G_{1}$ , $v \in G_{2}$ and $a, b \in Z_{n}$ : $e (u^{a}, v^{b}) = e {(u, v)}^{a b}$

2) Non-degenerate. $e (g_{1}, g_{2}) \neq 1$

3) Computability. There is an efficient algorithm to compute $e (u, v)$ for all $u \in G_{1}$ , $v \in G_{2}$ , then e is a bilinear mapping.

2.2. Aggregate signature

Aggregate signature is a variant signature scheme used to aggregate any number of signatures into one signature. Suppose there are n users $U = {u_{1}, u_{2}, \dots, u_{n}}$ , n private keys $SK = {{sk}_{1}, {sk}_{2}, \dots, {sk}_{n}}$ , n public keys $PK = {{pk}_{1}, {pk}_{2}, \dots, {pk}_{n}}$ , n messages $M = {m_{1}, m_{2}, \dots, m_{n}}$ and n signatures $σ = {σ_{1}, σ_{2}, \dots, σ_{n}}$ of these messages in the system. Then the aggregator of the aggregate signature (here the aggregator can be arbitrary and does not need to be in $U$ ) can aggregate σ to a short signature $sig$ . Importantly, the aggregate signature is verifiable, namely, given a set of public keys $PK$ and its signatures σ of the original message set $M$ . It can be verified that the user $u_{i}$ has made a signature of message $m_{i}$ respectively. The execution of the aggregate signature is described in detail below.

$AS = (KeyGen, Sign, Verify, AggS, AggV)$ is a quintuple of polynomial time algorithm, details are as follows: $DS = (KeyGen, Sign, Verify)$ is a common signature scheme, also known as the benchmark for aggregate signature.

1) Aggregation signatures generation (AggS). Given multiple individual signatures $σ = {σ_{1}, σ_{2}, \dots, σ_{n}}$ where $σ_{i}$ is a signature on message $m_{i}$ signed by user $u_{i}$ with its private key ${sk}_{i}$ , $1 ⩽ i ⩽ | σ |$ and $| σ | > 2$ , the aggregation algorithm AggS condenses them into a compact aggregate signature $sig$ .

2) Aggregation signature verification (AggV). Suppose that each $u_{i}$ corresponds to a public-private key pair ${{pk}_{i}, {sk}_{i}}$ . If $AggV (PK, M, AggS) = 1$ , then return “ACCEPT”, otherwise return “REJECT”

Aggregate signature can also support incremental aggregation, so $σ_{1}$ and $σ_{2}$ can be aggregated to $σ_{12}$ , then $σ_{12}$ and $σ_{3}$ can be aggregated to $σ_{123}$ .

2.3. Cryptographic sortition

Cryptographic sortition is a technology that can be used to complete credible and verifiable lottery election by means of decentralization in distributed network. Algorand proposed by Sivio Micali in [11], applies cryptographic sortition to blockchain. In Algorand, the system needs to create and update a parameter called a “seed” that cannot be predicted or controlled by an attacker. During each round of consensus, Algorand releases a verifiable random function (VRF) based on the seed. Each user uses his public-secret key pair to perform the VRF to get a corresponding certificate. Users whose credentials meet certain conditions are identified as “verifiers” for this consensus round. Each verifier completes a bootstrap and publishes it with its own credentials. The verifier with the smallest dictionary order of credentials in this round is identified as the “leader”. The application of CS in blockchain has the following advantages:

The random nature of VRF determines that the election process of the “verifier” and the “leader” is difficult to be predicted and manipulated.

Validation of the election process is kept secret, only when a user publishes his credential can he prove his/her identity of verification. The information of his/her bootstrap message will be published. However, despite this fact an attacker can instantly corrupt the verifier, meaning the released bootstrap information can no longer be withdrawn.

The generation of leaders is generated by comparison after all verifiers publish their own certificates, which can be considered as a public election.

2.4. Threat model

We denote the number of Byzantine validators by f, and for PBFT the number of whole validators is more than $3 f + 1$ , so we suppose that $n = 4 f$ , where n is the number of whole validators and the factor 4 is an arbitrary constant bounded away from 3. Under these circumstances, honest nodes are reliable during consensus runs, and at most 25% of the nodes can be malicious and behave arbitrarily. We further assume that cryptographic primitives are secure since it is known that the computational co-Diffle–Hellman problem is hard, as given in [3].

3. A public blockchain scheme based on sharding and aggregate signature

In this section, we introduce a novel public blockchain scheme which we call SAC based on sharding technology. SAC combines cryptographic sortition, aggregate signature, and sharding technology. There is a special shard in the scheme, called decision shard, where the nodes are called decision committees (DC). And there are several common shards, among which the nodes are called common nodes including participants, verifiers and leaders. A unique leader and several verifiers in each shard form the common committee (CC). Without loss of generality we define that the size of a shard is represented by $n_{0}$ . Next, we will illustrate the scheme in following three subsections: network sharding in Section 3.1, transaction sharding in Section 3.2 and consensus layer lastly in Section 3.3.

3.1. Network sharding

Network sharding divides the whole network into smaller shards, which follows the basic idea of sharding. To prevent sybil-attacks and bias-attacks, the shard should slice the network in a random and unpredictable manner. Here we give some ideas. Bitcoin suggests the use of PoW, where miners compute a hash function thousands of times. PPCoin combines PoW and PoS to establish Sybil-resistant identtites. In SAC we build on what was accomplished in Algorand, by accessing users with weights. That is, only the users who own tokens can access the network. Given a set of weights $w_{i}$ and the weight of all users $W = \sum w_{i}$ , the probability that user i is selected to be the leader or verifiers is relevant to $\frac{w_{i}}{W}$ . As for unpredictability, a public known random $seed$ is chosen by a secure multi-party computation (MPC) protocol as given in [23].

Firstly, let us assume there is at least l node in the network, then if $l ⩽ n_{0}$ , the nodes will behave the same as a typical blockchain system such as Algorand. However, if $l > n_{0}$ , there must be m shards, without any intersection, dominating different nodes. We can calculate m as follows: $\begin{matrix} (2) & m = \{\begin{matrix} \frac{l}{n_{0}} + 1 & if existing k make l = k \cdot n_{0}, \\ \frac{l}{n_{0}} + 2 & other . \end{matrix} \end{matrix}$

3.1.1. Bootstrap

At the beginning of the r-th round, there must be a bootstrap for the decision leader, decision verifiers, common leaders, common verifiers and common participants through Algorithm 1 using VRF. The user, with private key $sk$ , public key $pk$ and weight w, runs the algorithm for a $role$ as given above.

Algorithm 1

Bootstrap algorithm

For the specific purpose of sortition, we set an expected value m, which means that we hope to draw m weights among all weights. In this way, in our sortition, according to the probability of $p = \frac{m}{W}$ , let each participant i do draws for $w_{i}$ times based on their own $w_{i}$ . In this way, all participants will draw a total of W times.

A hash result $hash$ and a proof π come out of VRF as the certification. To select the user in proportion to their tokens, we consider the binomial distribution $\begin{matrix} (3) & B (k, w, p) = (\binom{w}{k}) p^{k} {(1 - p)}^{(w - k)}, \end{matrix}$ where $B \sum_{k = 0}^{k = w} (k, w, p) = 1$ , the weight of a user decides how many consecutive intervals are separated of $[0, 1]$ . Each part can be denoted by $\begin{matrix} (4) & I_{j} = [\sum_{k = 0}^{j} B (k, w, p), \sum_{k = 0}^{j + 1} B (k, w, p), j \in (1, 2, \dots, w)], \end{matrix}$ where $\frac{hash}{2^{hashlen}}$ falls. Then the user has the selection voucher j, which decides whether he/she can get the role.

3.1.2. Cryptographic sortition

After broadcasting the bootstrap message, and the $(r - 1)$ -th round receives ${DC}_{r - 1}$ . It will run the cryptographic sortition algorithm (Algorithm 2 and Algorithm 3) and write this message to their $database$ .

Algorithm 2

Cryptographic sortition algorithm

Algorithm 3

Cryptographic sortition algorithm cont

Fig. 1.

Architecture diagram of SAC.

$DC$ uses a verifying function to prove the validity of the bootstrapping, called VerifyVRF, and if this function runs successfully, the value of VerifyVRF is 1. An adversary without private key $sk$ can not forge a VRF that can be verified by ${VerifyVRF}_{pk}$ . Then, the number of selected sub-users of the user is obtained according to a process similar to the sortition (0 means that the user is not drawn at all), which is compared with the j value broadcast by the user with the message to verify its correctness. For $hash$ is uniformly distributed between 0 and $2^{hashlen} - 1$ , then $\frac{hash}{2^{hashlen - {log}_{2} m}}$ is uniformly distributed between 0 and $m - 1$ , through which the user can be divided into different shards essentially uniformly.

After the algorithm, the architecture of the network sharding is given as in Fig. 1. The entire network will be randomly and unpredictably divided into multiple sub-networks, that is, a shard. Each shard passes the cryptographic sortition (CS) to elect the “verifier” and the “leader”. There is one decision shard and multiple common shards, and the decision committees in the decision shard can update the global state.

Adopting the ideas given in Zilliqa, the ${DC}_{r - 1}$ runs a consensus on the database and formats a ${DC}_{r} - block$ , the hash of which will be patched into the header of block constructed in round r.

3.1.3. Assigning new nodes

During the r-th round, when new node joins the system, it is assigned to a common shard according to the characteristics of the hash of ${DC}_{r} - block$ . The assigning algorithm is introduced in Algorithm 4.

Algorithm 4

Assigning new nodes

3.2. Transaction sharding

Transactions can be processed in parallel under the scheme of sharding. Usually, the network sharding is the basic of transaction sharding. In this subsection we describe three types of transactions according to whether the input addresses are in the same inter-shard. For the purpose of making explanations simple, we will use the abstraction $({add}_{A}, v_{A}; {add}_{B}, v_{B}) \to ({add}_{C}, v_{C}; {add}_{D}, v_{D})$ to indicate a transaction from A and B to C and D respectively, where the input and output balance out, that is $v_{A} + v_{B} = v_{C} + v_{D}$ . If A, B, C and D are in the same shard, the transaction will be called an inter-shard transaction; if A and B are in the same shard but at least one of C and D is in another shard, it will be called an input-shard-identical transaction; if A and B are in different shards, it will be called an input-shard-different transaction.

3.2.1. Inter-shard transaction

In each round, only the address related to the public key in a shard can submit transactions to the common committee of this shard. If A, B, C and D are in the same shard, then the transaction, with a stable state, will be broadcast to a inter-shard transaction pool. The state includes the input address, input value and transfer volume of the input entities. Recall that the state is denoted by $({add}_{A}, v_{A}, n_{A}; {add}_{B}, v_{B}, n_{B})$ . When collecting enough inter-shard transactions, the leader will run a consensus protocol (BFT like protocol will be introduced in Section 3.3) to form a $IS - Block$ , the header which consists of the hash of ${DC}_{r} - block$ , the aggregate signature, Merkle-tree root of the transaction, and some other parameters like timestamp, etc. Note that $IS - Block$ does not have an independent signature for each transaction, though it has ever been existed in the transaction pool. Instead, it contains a BLS aggregate signature by all the input entities. After the block has been confirmed, the leaders and verifiers update the inter-shard state according to the content of the block, and at the beginning of the next round, CC will notify decision committees to update the global state. The outline is shown in Fig. 2.

Fig. 2.

Inter-shard transaction.

3.2.2. Input-shard-identical transaction

In this type, A and B are in the same shard, but at least one shard between C and D is in another shard. Without loss of generality, we suppose D is in another shard called $D - shard$ . As shown in Fig. 3, if A, B, and C are in the same shard, perform the process described in Fig. 2 first, and then D is supposed to submit the transaction into the input-shard identical transaction pool, so the leader could patch it into a $raw - ISI - block$ , and broadcast it to verifiers for consensus. When a shard reaches consensus on a $ISI - block$ , its leader broadcasts the block to $DC$ . Then, DC updates the global state and delivers the latest state information to the $D - shard$ . This type only needs two one-way propagations, which will not waste many interactive resources.

Fig. 3.

Input-shard-identical transaction.

3.2.3. Input-shard-different transaction

As shown in Fig. 4, if A and B are not in the same shard, then A is supposed to submit the transaction information to the input-shard-different transaction pool, which contains the BLS signature for each input. We use $A - shard$ to denote the shard where A located, $B - shard$ similarly. The leader of $A - shard$ runs a consensus from a $raw - ISD - block$ to a $pre - ISD - block$ including $({add}_{A}, v_{A}; {add}_{B}, v_{B}) \to ({add}_{C}, v_{C}; {add}_{D}, v_{D})$ transaction and broadcasts it to DC which will broadcast the transaction further to $B - shard$ . Only the verifying of A’s state is needed for the CC of $A - shard$ , because after a period of time, the one of $B - shard$ will verify the state of B. If verification is successful, they will sign it and update the state as well as broadcast it to $DC$ . The $DC$ processes it on the whole the same except signing by their private key and passing it to $A - shard$ . So the committee of $A - shard$ will reconstruct a $ISD - block$ from the received message and $pre - ISD - block$ .

This block includes not only an aggregate signature of all inter-shard input parties, a consensus signature of committee of this shard, but also a consensus signature of other relative shards and the consensus signature of $DC$ .

Fig. 4.

Input-shard-different transaction.

If C and D are also in different shards from A, then the $ISD - block$ will be broadcast to DC and further to $C - shard$ and $D - shard$ just like the process described in Fig. 3.

3.3. Consensus layer

3.3.1. Aggregate-signature algorithm in consensus

The signature algorithm considered in this paper is mainly composed of Key Generation algorithm, Signing algorithm, Verification algorithm, Aggregate algorithm and Aggregate Verification algorithm.

KeyGen: Pick a random $sk \overset{R}{\leftarrow} Z_{p}$ and compute $pk = g_{2}^{sk}$ . The public key is $pk \in G_{2}$ . The secret key is $sk$ .

Sign: Let H: ${0, 1}^{*} \to G_{1}$ be a hash function and $T / B$ be a transaction or a block which depending on the occasion. Each common user or committee member computes $h = H ((T / B) ‖ v)$ , using its private key $sk$ , then computes signature $σ = h^{sk}$ .

Verify: Given a public key $pk$ , transaction T or block B, signature σ, the verifier computes $h = H ((T / B) ‖ pk)$ . If $e (σ, g_{2}) = e (h, pk)$ is true, accept it, otherwise, reject it. And we use $Verify (T / B, σ, pk)$ to signify the process.

AggS: Let the aggregation set be $U = {u_{1}, u_{2}, \dots, u_{k}}$ and the corresponding signature be $σ = {σ_{1}, σ_{2}, \dots, σ_{k}}$ and the message set be $T / B = {{(T / B)}_{1}, {(T / B)}_{2}, \dots, {(T / B)}_{k}}$ . Compute aggregate signature $sig = \prod_{i = 1}^{k} σ_{i}$ .

AggV: Given aggregate signature $sig$ , message set is $T / B$ and the public key set $V = {{pk}_{1}, {pk}_{2}, \dots, {pk}_{k}}$ of signers, compute $h_{i} = H ((T_{i} / B_{i}) ‖ {pk}_{i})$ . If $e (sig, g_{2}) = \prod_{i = 1}^{k} e (h_{i}, {pk}_{i})$ is true, accept it, otherwise, reject it. And we use $AggV (T / B, sig, V)$ to signify the process.

3.3.2. Construction of a raw-block

Let $T = {T_{1}, T_{2}, \dots, T_{n}}$ delegate the transactions which the leader will pack. So the public keys set of input entities can be denoted by $\begin{matrix} (5) & V = {{pk}_{1}^{1}, {pk}_{1}^{2}, \dots, {pk}_{1}^{s_{1}}, \dots, {pk}_{n}^{1}, {pk}_{n}^{2}, \dots, {pk}_{n}^{s_{n}}}, \end{matrix}$ where $s_{i}$ is the number of inter-shard input addresses of transaction $T_{i}$ , and ${pk}_{i} = {{pk}_{i}^{1}, {pk}_{i}^{2}, \dots, {pk}_{i}^{s_{i}}}$ relating to the same transaction $T_{i}$ . $X = {{sk}_{1}^{1}, {sk}_{1}^{2}, \dots, {sk}_{1}^{s_{1}}, \dots, {sk}_{n}^{1}, {sk}_{n}^{2}, \dots, {sk}_{n}^{s_{n}}}$ are the corresponding private keys. The function Merkle-tree is used to compute the Merkle-tree root of a set of son nodes. Then, how to pack a raw-block will be showed through Algorithm 5 below in stand-alone mode.

Algorithm 5

Construction of raw-block

3.3.3. Byzantine-agreement of an inter-shard

Suppose the cardinal of i-th inter-shard is $n_{i}$ , $U = {u_{1}, u_{2}, \dots, u_{n_{i}}}$ , $V = {{pk}_{1}, {pk}_{2}, \dots, {pk}_{n_{i}}}$ and $X = {{sk}_{1}, {sk}_{2}, \dots, {sk}_{n_{i}}}$ denote the verifier set of a shard, its corresponding public key set and private key set respectively. $pk$ and $sk$ denote the leader u’s corresponding keys. $B_{i}$ represents a counting set that records whether each verifier has verified and given a valid response, with initial values of 0, and changing to 1 if a verifier completes the verification and gives a response.

The j-th verifier of this shard verifies the block formed by the leader. It mainly includes information such as the block format, the validity of the transaction, the validity of the BLS aggregate signature, the signature of leader and so on. If the verification passes, then they compute $W_{j} = H {(B ‖ {pk}_{j})}^{{sk}_{j}}$ , where B is the raw-block generated by leader, and send $({pk}_{j}, W_{j})$ to u. Then u computes $num = \sum_{j = 1}^{n_{i}} B_{j}$ . If $num ⩾ 2 / 3 n_{i}$ , then compute $W = \prod_{B}^{j = 1} W_{j}$ . The specific syntax is shown in Algorithm 6.

Algorithm 6

Byzantine agreement of inter-shard

3.3.4. Byzantine-agreement among shards

When the leader of decision receives an $IS - block$ or an $ISI - block$ or a $pre - ISD - block$ , the leader will check the block format, the validity of the transaction, the validity of the BLS aggregate signature formed by the inter-shard leader and so on. Then the leader will run the consensus the same as the above algorithm and update the global state.

4. Analysis of SAC

In this section, we use the pairing-based cryptography (PBC) library based on GNU multiple precision arithmetic (GMP) library to construct a prototype system, and test the performance of transaction process and consensus. We compare those with the simplified Zilliqa test system and some with the Bitcoin system, drawing a conclusion that SAC can effectively solve the problem of low-performance and unscalability. Also, Section 4.3 gives some security analysis and comparisons among some different sharding technologies, pointing out the crucial problems of consensus design.

4.1. Analysis of transaction performance

In cases where public key and signature are the key considerations, the block of fixed length in SAC can accommodate more transactions. The transaction data structure is given in Table 1.

Table 1
Complete transaction data structure of SAC

Data name Data size (byte) Data

vinA_nSequence 4 00000000000000000000000000000000

vinA_serial_number 4 00000000000000000000000000000000

vinA_value 4 00000000000000000000000000001010

Data name	Data size (byte)	Data
vinA_nSequence	4	00000000000000000000000000000000
vinA_serial_number	4	00000000000000000000000000000000
vinA_value	4	00000000000000000000000000001010

Table 1

(Continued)

Data name	Data size (byte)	Data
vinA_public_key	128	[2633292501362035284617336373913198122844093788 71998620087886870535850576731956721388902598497 14556230300874231534914803506378513120642157422 87757855135760, 26655007677271418092120736475461407104625189814 63826594 99475528516279296310836905028662564983 9074755679233878 902559582143470498687967409505 137628462438904]
vinA_signature	128	[1327068157858206533169808623167370398349890622 54673726330343372451332027624248802057362603097 42067423734837230655573031989262214659789612668 48906361811892, 68307742728181741935970701125980311185535874285 68496514250273323950736121061489931801159692372 99547173927020366774718196907546363823914085700 8387547591617]
vinB_nSequence	4	00000000000000000000000000000000
vinB_serial_number	4	00000000000000000000000000000001
vinB_value	4	00000000000000000000000000010100
vinB_public_key	128	[7003584829506761760811195465165348539400433205 37009004714122185870020830891487268112180158381 12301711910772189179469497641611382884340292786 89448088417868, 10750518382059970522086301237505238509778387806 82215746854720285874504590959162582863132737929 14131622266244755963177053010931319386528938493 0953600509097]
vinB_signature	128	[4474403041724393485821533978231175743441803027 29548451102768713015785111570329879543206395369 05890904191557874887047037956011210132419002657 94671635487974, 33686374020294575468679573519351697243893708579 30319484444702328048232129406255568423996997315 02509161893692458418707534054214869633933780952 8280005085519]
voutC_serial_number	4	00000000000000000000000000000000
voutC_value	4	00000000000000000000000000001111
voutC_public_key	128	[7053078177063106619861932698937878724447464673 00618316198956169859226422793074335486790333037 22714300660553907150308430841351379958983117576 99451782112811, 74281884911246246510581682411047570711769699945 70242522514868853832742321608001004988176092524 19025531219173852112493994873945076375148842872 2712744280747]
voutD_serial_number	4	00000000000000000000000000000001
voutD_value	4	00000000000000000000000000001111
voutD_public_key	128	[7863590569747262692463417103952904957893063921 86290093282559430677100301976411842533480598070 60308438444968616619880870593478032149067671140 13126195659712, 91491513275217974355717732423404105513555799629 23066611911016184111850015257684056279541945998 67324988866545360038499469069608860628963566043 475846847146]
transaction_aggregate_signature	128	[7687718334397074347649522243950938088594142606 17463090668435441693060464419865840541026897492 52965654398580029100856250368466133100503315205 92759530688359, 78257529033486561863531155011660956200926053105 22087074596955730279906291306432512503826046463 07387322169850531126211641477296831919602677833 7872226385548]

The short parts are represented in binary, and the points on the elliptic curve such as public key and the BLS signature are represented in demical.

Fig. 5.

Block body data size.

Take the binary-in-binary-out transaction as an example, SAC’s transaction size is 632 bytes, and the transaction size without aggregate signature is 120 bytes. Bitcoin’s P2PK transaction size is 344 bytes and Zilliqa’s is 376 bytes. With the increase of transaction numbers, the trend of block body data size is shown in Fig. 5.

Although Bitcoin and Zilliqa take advantage of a single complete transaction, as the number of transactions increases, there is only one aggregate signature in a block. SAC has the smallest average transaction size among the three systems. For a 1MB block, SAC blocks can accommodate more than 8000 transactions, without regard to the compressed point on the elliptic curve. This makes the transaction rate improve more than three times that of Zilliqa. As for other sharding technologies, Omniledger and Rchain do not provide the data structure of a transaction, making it impossible to compare here.

Fig. 6.

Interaction cost.

4.2. Analysis of consensus performance

Zilliqa and Omniledger uses multiple Schnorr signatures inspired by ByzCoin [14,17], which signs the same message. Meanwhile, it needs cooperation and interaction between multiple parties, which is unacceptable in blockchain and other similar distributed systems. However, SAC adopts an aggregate signature, which reduces the signature length without the interaction between participants. A given Zilliqa leader must process 256 bytes of input and sends 192 bytes of output for three interactions when communicating with a verifier, while SAC’s input is 256 bytes with no need for interaction. Therefore, with the increase of verifiers, the interaction cost is shown in Fig. 6.

We further test the consensus performance using the SAC prototype system and Zilliqa test network by multiple virtual machines, mainly aiming at inter-shard consensus. In the absence of Byzantine nodes, it is found that with the increase of consensus nodes, consensus performance is shown in Fig. 7. We can clearly see the lower time cost with a variety of verifier numbers in play.

Fig. 7.

Consensus performance.

In SAC, the consensus performance mainly depends on the verification efficiency of BLS signatures and network congestion. For current hardware conditions, $70, 000$ secp256k1 signatures or $8, 000$ BLS signatures can be verified per second. Therefore, in Zilliqa, it is mainly limited by the network congestion because of the interaction cost.

4.3. Analysis of security

Security analysis of BLS aggregate signatures has been carried out in detail in [5] based on the computational co-Diffle–Hellman problem and the security analysis of the application of cryptographic sortition in blockchain, which is also introduced in detail in [11]. We will not repeat it here. We focus on the security of the Byzantine protocols.

Intuitively, we can find that a leader node or most of the verifier federation can presumably conduct bad behavior. Attacks such as double spending can be carried out. In addition, it can lead to a certain round of consensus failure, transaction suspension and other bad behavior, causing harm to the system. Aiming at this situation, we set the punishment mechanism and all nodes are up for election to pay the deposit in advance. Once finding a node conducting bad behaviour, the system will confiscate all of his deposits and cancel the qualification of participation on the network. So the adversary pays the price of being an attacker which far outweighs its benefits. As for the suspended transaction under attack, it will follow the next round to complete the consensus and be eventually confirmed. If the leader fails to generate a block, it will trigger a round change phase similar to PBFT.

Besides, non-interactive signatures keep the atomicity of a transaction. According to Zilliqa’s white paper, we find that a few united Byzantine nodes may clog under a multi-signature scheme, leading to a ceaseless loop, which is caused by the non-atomic nature of a signature.

In short, in SAC, the random assignment of consensus representatives is controlled by a verifiable random function, which can effectively solve the problem of centralized consensus; in the selection of committees, through cryptographic sortition, users are the only ones who know whether they are members of the committee. The malicious people don’t even know who the committee members are, so they cannot be bribed or launched denial-of-service attacks; the setting of the punishment mechanism also makes the system more secure; the fixed-length blocks in SAC can accommodate more transactions, which can greatly increase Increased transaction rate; interaction costs (including expenses and time-consuming) are also significantly reduced compared to other blockchains.

5. Conclusion

Currently in the world of blockchain, the application of public blockchain continues to be faced with many challenges. Our main focus in this paper is a new public blockchain scheme based on sharding and BLS aggregate signature which also uses cryptographic sortition, called SAC. We have given experimental results primarily comparing our scheme with Zilliqa, showing that our scheme has better transaction rate. We also give an in-depth analysis of the security and consensus protocol of SAC, showing its superiority in both areas compared to current schemes.

Footnotes

Acknowledgements

We acknowledge the support provided by the State Key Laboratory of Mathematical Engineering and Advanced Computing. And this research work is supported by the Innovative Research Groups of the National Natural Science Foundation of China (Grant No. 61521003), Intergovernmental Special Programme of National Key Research and Development Programme (2016YFE0100300, 2016YFE0100600) and National Scientific Fund Programme for Young Scholar (61672470).

References

A visualization for the future of blockchain consensus, [Online], Available: https://medium.com/rchain-cooperative/a-visualization-for-the-future-of-blockchain-consensus-b6710b2f50d6.

Anton, Byteball: A decentralized system for storage and transfer of value, [Online], Available: https://byteball.org/Byteball.pdf.

Boneh,

Lynn and

Shacham, Short signatures from the Weil pairing, presented at Asiacrypt 2001, [Online], Available: http://crypto.stanford.edu/~dabo/pubs.html.

crypto-cryptokitties, 2017, Available: https://medim.com/taipei-ethereum-meetup/crypto-cryptokitties-a011d56d7579.

Dan

et al., Aggregate and verifiably encrypted signatures from bilinear maps, in: Lecture Notes in Computer Science, Vol. 3536, 2003, pp. 416–432.

Decker and

Wattenhofer, Information propagation in the Bitcoin network, presented at 13-th IEEE Conference on Peer-to-Peer Computing, [Online]. doi:10.1109/P2P.2013.6688704.

EOS.IO technical white paper v2, 2018, Available: https://github.com/EOSIO/Documentation/blob/master/TechnicalWhitePaper.md.

Hertig, Ethereum scaling advances with ‘first’ off-blockchain payments, Accessed on: Aug 11, 2016, [Online], Available: http://www.coindesk.com/ethereum-scaling-advances-first-off-blockchain-payments/.

Homayoun,

Dehghantanha,

R.M.

Parizi and

K.K.R.

Choo, A blockchain-based framework for detecting malicious mobile applications in app stores, arXiv preprint, arXiv:1906.04951, 2019.

10.

Hueber, The blockchain and the sidechain innovations for the electronic commerce beyond the Bitcoin’s framework, International Journal of Transitions & Innovation Systems 6(1) (2018).

11.

Jing and

Micali, ALGORAND: The efficient and democratic ledger, Accessed on: Jul 5, 2016, [Online], Available: https://arxiv.org/abs/1607.01341.

12.

Joseph and

Thaddeus, The Bitcoin lightning network: Scalable off-chain instant payments, Accessed on: Jan 14, 2016, [Online], Available: http://lightning.network/lightning-network-paper.pdf.

13.

Kokoris-Kogias

et al., OmniLedger: A secure, scale-out, decentralized ledger via sharding, presented at 2018 IEEE Symposium on Security and Privacy, [Online]. doi:10.1109/SP.2018.000-5.

14.

Kokoris-Kogias

et al., Enhancing Bitcoin security and performance with strong consistency via collective signing, presented at 25th USENIX Security Symposium, [Online], Available: https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/kogias.

15.

Larimer, EOSIO Dawn 3.0 now available, 2018, [Online], Available: https://medium.com/eosio/eosio-dawn-3-0-now-available-49a3b99242d7.

16.

Leemonp, The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance, Accessed on: May 31, 2016, [Online], Available: https://www.hederahashgraph.com/whitepaper.

17.

Morita,

J.C.N.

Schuldt,

Matsuda et al., On the security of the Schnorr signature scheme and DSA against related-key attack, in: Information Security and Cryptology, Springer International Publishing, 2015, pp. 20–35.

18.

Nakamoto, Bitcoin: A peer-to-peer electronic cash system, 2008 Octomber.

19.

R.M.

Parizi,

Dehghantanha,

K.K.R.

Choo and

Singh, Empirical vulnerability analysis of automated smart contracts security testing on blockchains, in: Proceedings of the 28th Annual International Conference on Computer Science and Software Engineering, IBM Corp., 2018, October, pp. 103–113.

20.

Serguei, The tangle, Accessed on: Oct 1, 2017, [Online], Available: http://iotatoken.com/IOTA%20Whitepaper.pdf.

21.

Sompolinsky and

Zohar, PHANTOM: A scalable BlockDAG protocol, IACR Cryptology ePrint Archive 104, 2018.

22.

Syta

et al., Keeping authorities “honest or bust” with decentralized witness cosigning, presented at 2016 IEEE Symposium on Security and Privacy, [Online], Available: https://ieeexplore.ieee.org/document/7546521.

23.

Syta

et al., Scalable bias-resistant distributed randomness, presented at 2017 IEEE Symposium on Security and Privacy, [Online]. doi:10.1109/SP.2017.45.

24.

The ZILLIQA Team, The ZILLIQA technical whitepaper, Accessed on: Aug 10, 2017, [Online], Available: https://docs.zilliqa.com/whitepaper.pdf.

25.

Yazdinejad,

R.M.

Parizi,

Dehghantanha and

K.K.R.

Choo, Blockchain-enabled authentication handover with efficient privacy protection in SDN-based 5G networks, arXiv preprint, arXiv:1905.03193 2019.

26.

Yuan,

M.X.

Xu and

X.M.

Si, Research on a new signature scheme on blockchain, Security and Communication Networks 2 (2017), 1–10.

27.

Zhang,

R.M.

Parizi and

K.K.R.

Choo, A pentagon of considerations towards more secure blockchains, IEEE Blockchain Technical Briefs, 2018.

New public blockchain protocol based on sharding and aggregate signatures

Abstract

Keywords

1. Introduction

2. Preliminaries

2.1. Bilinear mapping

2.2. Aggregate signature

2.3. Cryptographic sortition

2.4. Threat model

3. A public blockchain scheme based on sharding and aggregate signature

3.1. Network sharding

3.1.1. Bootstrap

3.2.1. Inter-shard transaction

3.3.1. Aggregate-signature algorithm in consensus

3.3.2. Construction of a raw-block

4. Analysis of SAC

4.1. Analysis of transaction performance

Table 1 Complete transaction data structure of SAC Data name Data size (byte) Data vinA_nSequence 4 00000000000000000000000000000000 vinA_serial_number 4 00000000000000000000000000000000 vinA_value 4 00000000000000000000000000001010

5. Conclusion

Footnotes

Acknowledgements

References

Table 1
Complete transaction data structure of SAC

Data name Data size (byte) Data

vinA_nSequence 4 00000000000000000000000000000000

vinA_serial_number 4 00000000000000000000000000000000

vinA_value 4 00000000000000000000000000001010