2.1. Increasing the Block Size

The most obvious solution is to increase the block size and there are multiple proposals on that [6][23]. One of the proposals, Bitcoin Cach (BCH), increases the block size to 8MB. While this can temporarily increase the mining capacity, the same problem will be faced again if the Bitcoin transactions grow continuously. But it is impractical to increase the block size continuously due to the network bandwidth limitation and propagation delay. [12] pointed out that each kilobyte in block size adds 80 ms delay until the majority knows about the block while another research [24] suggested 8ms of delay.

2.2. Decreasing the Block Mining Period

Another solution is to decrease the block confirmation time. The downside of this approach is the increased probability of fork and orphaned blocks. Currently, bitcoin block confirmation time is 10 minutes and forks are created a few times per week on the average. Litecoin has proven the viability of a shorter confirmation time of 2.5 minutes, where its probability of having a fork is not very different from Bitcoin’s. Ethreum’s mining period is much shorter, 14 seconds on the average, which increases the chance of orphaned blocks significantly (called uncle blocks) to near 2% [8]. Although the mining period is much shorter in Ethereum, the block size is also much smaller (less than 20kB) with about 200 transactions per block. This gives a 3 to 4 times higher processing rate (~15 transactions per second) than Bitcoin (3 to 7 transactions per second). The block mining period cannot be shortened infinitely either due to the network capacity and propagation delay, as it may cause too much instability to the mining network.

2.3. Alternative Data Structure for Blocks

Instead of putting the complete transaction information, only the most essential piece of information may be placed in the block. This reduces the amount of storage, and increases the number of transactions in the block. SegWit (segregated witness) moves some non-critical data, called witness data, out of transactions and off the Blockchain. While it can immediately increase the capacity, it will eventually face the same problem with the limited block size.

2.4. Off-Chain Transactions

Some methods are used to offload transactions from the blockchain, such as off-chain transactions [22][26], side chain, merged mining, etc. SegWit also allows a second layer such as the “lightning network” where sequences of transactions can be started on the blockchain, then continued outside of it without using network bandwidth. However, these methods do not address the capacity of the mining network itself directly. Other solutions have been proposed, such as separating the Bitcoin functions on different chains and blocks [14][15][18][20]. While they offer a scalable solution, they may depend on other factors such as a larger block size (e.g., 32 MB) to realize sufficient scalability.

2.5. Parallel Mining with Transaction Partitioning

Another approach is to allow multiple branches to confirm the blocks simultaneously on a disjoint set of transactions. Binary sharding has been discussed in the Ethereum community, but the details are still being developed. The idea of Tree Chain was proposed earlier [25], but was only conceptualized and has not progressed enough for further debate. It suggested a tree-structured blockchain where each branch can mine blocks, but the structure is static and cannot respond to the dynamically changing transaction load. The use of a DAG (Directed Acyclic Graph) structure instead of a tree structure has also been proposed. MultiChain [7][17] has an aspect of parallel mining, but it is across different blockchains, not in the same blockchain. These parallel mining techniques can increase the mining capacity without increasing the block size or reducing the block mining time, as shown in Fig. 3, but they also bring up some challenges as outlined in the next section.

Fig. 3

Single vs. Parallel Blockchain

3.1. Preventing Double Spending

In a traditional single-chained blockchain, parallel branches or fork may occur inadvertently while the blockchain information propagates throughout the mining network in p2p fashion. Since it can create a double spending problem, only one branch must be chosen. The mining network chooses the longest branch between them, and the orphaned blocks get invalidated. In parallel mining, multiple branches are created on purpose, and double spending may be possible if the same transaction gets included in multiple branches. To avoid this, the transactions must be divided into disjoint groups. Binary sharding based on the transaction ID or hash value can be employed for this purpose.

3.2. Authority to Create and Delete Chains

To cope with the varying transaction load, the number of parallel chains must be increased or decreased. In public Blockchain, this decision cannot be made by a single central authority. So the decision to create or delete the chains must be embedded in the Blockchain itself.

3.3. Difficulty Level Adjustment

In Bitcoin, the difficulty level of the mining is adjusted periodically (about every two weeks) to make the average block confirmation time 10 minutes. Under parallel mining, the mining resources are divided into multiple groups, and consequently, the conformation time will increase with smaller resources. Therefore, the difficulty level must be reduced accordingly to maintain the 10-minute confirmation time.

3.4. Reward Re-allocation

With parallel mining, there are multiple branches at the same time. If the reward amount per block stays same, the total reward will increase, which will violate the design principle of the current Bitcoin system. To prevent it, the size of the reward must be divided by the number of parallel branches so that the total reward is same as in the single blockchain.

3.5. Risk of Unbalanced Mining

If the miners are not evenly distributed among the parallel branches, two problems may occur.

• •

  Over-mining on one branch: Intentionally or unintentionally, all miners may concentrate on one branch. Then the confirmation time for a block will be much shorter than 10 minutes. This increases the possibility of fork and more orphaned blocks, and cause starvation on the other branch where little mining operation is performed.

• •

  Easier 51% attack: A mega-miner can concentrate on one branch and launch a 51% attack more easily.

To avoid these risks, there must be a way to spread the miners evenly over the multiple parallel branches.

4.1. The Concept

A binary Blockchain increases the mining capacity by twice when the mining pool is split, or decreased when the pool is merged. A new blockchain is not created additively, but by a binary division of the existing chain. When there is a split, the level of chain increases. The level k = 0 for the single Blockchain. At first split, k=1, and there are 2 chains. At second split, k=2, and there are 4 chins, and so on.

Each subchain can be split further or merged independently based on its own transaction load. When it is split, both new blocks inherit the hash value from the parent block, thus maintaining the continuity of the blockchain. When two chains are merged, the merged chains inherit hash values from both parent blocks.

The key concepts of binary Blockchain are:

• •

  Binary sharding of transactions: The transactions can be divided into disjoint groups for each subchain based on their hash values with simple modulo operation by the level of subchain. We apply binary sharding as following.

  • ○

    The number of groups = 2^k

  • ○

    Group id for trans n = trans id % 2^k

• •

  Difficulty level adjustment: The difficulty level gets halved for each division. This increases the overall mining capacity by a factor of two.

  • ○

    Difficulty level at level k = original difficulty * 2^−k

• •

  Reward calculation: The reward gets halved for each division. This ensures that the amount of total rewards stays same as in the traditional blockchain regardless of the number of subchains.

  • ○

    Reward for mining a block at level k = original reward * 2^−k

• •

  Balanced mining: Balanced mining can be maintained systematically with the synch blocks. The distance between synch blocks increase by power of 2 after each division.

Although it may look similar, Binary blockchain is different from TreeChain in that the whole blockchain or each subchain can dynamically and independently increase or decrease. It is also different from side chain or data sharding.

4.2. Block Numbering

Since the blockchain is not linear any more, we need to number the blocks differently. We use a hierarchical numbering format of “n1.n2.n3.….”, where a division is marked by a period symbol (“.”) and each number indicates the location within the subchain. The block number increases only within the last subchain level. In Binary blockchain, two subchains (top and bottom) are created upon division, and we need to differentiate them. For that, we divide the numbers in two groups (odd and even) and assign them to each subchain. In the top subchain, the block numbers grow in even numbers (0, 2, 4, …), and in the bottom subchain, they grow in odd numbers (1, 3, 5, …). When the subchains are merged, the last level subchain block number is removed and the upper level subchain numbering continues. An example is shown in Fig. 4.

Fig. 4

Block Numbering Example

4.3. Synch Block Placement for Balanced Mining

Without any balancing mechanism, one subchain may progress rapidly and create instability in the P2P mining network. For example, after 4 splits, there will be 16 subchains and the block confirmation time can be 1/16 of 600 seconds, which is 38 seconds. This can cause some instability in the mining network, creating more forks within each subchain [13].

To ensure a balanced mining resource distribution and synchronous progress among the chains, we introduce a concept of synch blocks. A synch block inherits the hash values from all pre-synch blocks in the sibling chain. So until all pre-synch blocks are confirmed, no miner can proceed further. The synch blocks are placed as following. Let k be the level of the subchain. The main chain has the level of 0, and the first division creates level 1 subchains, etc. Then at level k, synch blocks are placed every 2^k block and the difficulty level is 2^−k of the original difficulty. Fig. 5 shows the example of level 1 subchain, where the synch blocks are placed every 2 blocks.

Fig. 5

Synch Blocks

The total amount of work between the synch blocks on Binary blockchain is equivalent to the amount of work for one block in traditional blockchain. Generally,

• •

  # of blocks between synch blocks at level k = 2^k

• •

  Total amount of work between synch blocks = 2^k * 2^−k = 1

• •

  Total amount of reward between synch blocks = 2^k * 2^−k = 1

For example, when there are two subchains, the difficulty level is halved, and the number of blocks between the synch blocks is two including. So the amount of work for two blocks is equivalent to the amount of work for one block in traditional chain.

With this scheme, even if all miners are concentrated on one subchain, the maximum number of blocks they can continuously confirm is equivalent to the amount of work in one block in a classical blockchain. For example, if there are 4 sub-branches, each block can take 2.5 minutes to mine if all miners work on this sub-chain. These 4 consecutive blocks acts like one regular block. The total amount of reward between synch blocks is also equivalent to the reward for one block in traditional blockchain.

The synchronization must be done at all levels to ensure global balancing for all subchains. For example, in a complete Binary blockchain at level k, the number of subchains is 2^k, and the synch blocks must inherit the hash values from all 2^k sibling blocks. This forces global synchronization across all subchains. Fig. 6 shows an example of global scale synchronization.

Fig. 6

Global Synchronization

4.4. Autonomous Decision for Split and Merge

In Binary blockchain, the decision to divide or merge is pre-determined by the blockchain itself, not arbitrarily by any individual. The split and merge decision is based on the mining congestion level, and the congestion information can be obtained directly from the blockchain itself. When there is a mining congestion, the transactions must wait longer time to be confirmed. Either a timestamp or the latest block number can be associated with each transaction. Then the average waiting time can be calculated for each block. Then the split and merge rules can be obeyed by all miners as following.

• •

  Split: When the average transaction time in confirmed blocks exceeds a threshold value (e.g., 20 minutes) for predefined periods (e.g., 3 blocks), the Blockchain is split into two.

• •

  Merge: When the average transaction times go below a certain threshold (e.g., 10 minutes) for multiple consecutive blocks for both chains, they are merged. If one of the subchains meets the merge condition, the merge occurs regardless of the transaction load of the other subchain. For simplicity, the merge can occur only at synch blocks.

5.1. Scalability

Currently Bitcoin mining network can process about 4 to 7 transactions per second. With Binary blockchain, with 10 divisions (2¹⁰ = 1,024 subchains), the capacity of the mining network can be increased to 3,000 transactions per second, matching the commercial credit card transaction speed (~2,000 per second).

5.2. Cost-Effectiveness

With Binary Blockchain, more transactions can be processed with the same amount of resources. This means the cost per transaction becomes lower. Under mining congestion, users are forced to pay a higher transaction fee to reduce confirmation time, but thanks to the increased capacity, the transaction fees can be kept at the same level.

5.3. DDoS Attack-Resistance

Since Binary blockchain can respond to the transaction load dynamically, the number of subchains is increased automatically during a DDoS period and decrease when the attack is finished. Thus it can effectively cope with a DDoS attack.

6.1. Scalability Analysis

In a traditional blockchain, the average mining throughput is given as following.

• •

  S_B = Max size of a block (Currently 1 MB)

• •

  S_T = Average size of each transaction (250 to 500 bytes)

• •

  T_B = Average block conformation period in seconds (600 seconds on average)

With the above typical values, the mining throughput is 3.33. (= 1 MB / 500 Bytes / 600). Multiple proposals are in play to increase the block size. If the block size gets increased, the throughput goes up linearly. For example, with a 4 KB block size, the throughput will be increased to about 13 transactions/sec.

In Binary block chain, the throughput is increased linearly with the number of subchains. For example, with 10 subchains the throughput is increased by 10 times, i.e., 33.3 transactions per second. Note that the number of subchains may not be a power of 2 because each subchain can be split independently.

6.2. Average Confirmation Time

For most Bitcoin users, the ultimate concern is the confirmation time for their transactions, not the mining network throughput. A normal queuing process does not apply because the confirmation is a result of random selection. Different miners receive a different set of transactions, called mempool [3], while transactions propagate throughout the P2P network. In particular, the confirmation time follows a geometric probability distribution. The average confirmation time depends on the overall transaction load in the whole Bitcoin mining network. The probability of being included in the next block for a transaction is N_B/N_T, where

• •

  N_T = Total number of pending transactions in the mining network

• •

  N_B = Number of transactions in each block

Let N_B/N_T be denoted by p1. If the number of incoming transactions per block confirmation period is always same as N_B, the total number of pending transactions (N_T) is constant. Then the probability to be included in the n-th block (= p_n) for a transaction is,

In a geometric distribution, the average and variance are given as following.

In case of Binary blockchain, the confirmation time is given as follows.

• •

  N_c = Number of subchains

• •

  [p_{1 *} N_c] = 1

The average and variance are given as following.

For a comparison, the confirmation times in both cases are shown in Table 2 under the following conditions.

• •

  N_T = 10,000

• •

  N_B = 2,000

• •

  N_C = 2

• •

  p₁ = 0.2 (= 2,000 / 10,000) for traditional blockchain, or

  p₁ = 0.4 (= 2,000 * 2 / 10,000) for Binary blockchain

The corresponding statistical values are given in Table 3. We can observe that the conformation time gets reduced greatly by increasing the throughput by twice.

6.3. Simulation Results

To test the scalability of the Binary blockchain, we performed simulation under the following conditions.

• •

  Total number of transactions per block = 500

• •

  Block confirmation period = 10 minutes (= 600 seconds)

• •

  Number of block periods = 50 (= 500 minutes)

• •

  Transaction fee = none (not considered)

We generated the transaction as following. First, we generated 500 transactions per block period with the initial transactions of 1,000. In each block, 500 transactions are selected randomly. In this case, there is no backlog and the behavior of the traditional and Binary blockchain was identical. Second, the transactions are generated uniformly at the speed of 1,000 transactions per second. Fig. 6 shows the result.

Fig. 6

Response to a Gradual Increase

Since there are 500 transactions not included in a block each period, it creates a gradually increasing mining congestion. The result is an increased average transaction confirmation time due to the growing waiting period. In case of Binary blockchain, when the average confirmation time is over 3,000 seconds continuously for 3 blocks, it divides the blockchain. Reversely, if the average confirmation time is below 1,500 seconds for 3 blocks continuously, it merged the subchains. The traditional blockchain shows gradually increasing average transaction confirmation time. The Binary blockchain shows quick drop in the average confirmation time after a division (around period 17) and consumes most of the backlogged transactions. At the lowest point (period 29), the confirmation time went down to 299 seconds. Then the subchains are merged, thereby having a more consistent average confirmation time within a range.

Third, we simulated a sudden surge of the transaction load such as in DDoS attack. Fig. 7 shows the result. In this case, there was a large amount of incoming transactions (up to 4000 transactions per block period) between the block periods 19 and 25. As expected, the traditional blockchain couldn’t handle the transaction load and the average confirmation time kept increasing. In Binary blockchain, the blockchain was divided first when the normal overload was observed (around period 17). Then when the surge hit, it divided again (around period 25) and reduced the confirmation time down to 637 seconds (period 37). Then it merged as the load subsided average and the transaction time went up to the normal range. This results show that Binary blockchain can adjust the capacity to the changing load effectively.

Fig. 7

Response to a Temporary