Permalink
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
65 lines (49 sloc) 9.43 KB

  BIP:              N/A
  Layer:            Consensus (hard fork)
  Title:            Blocktree: A Scaling Scheme for Blockchains
  Author:           Chaofan Li <chaof@tamu.edu>
  Discussions-To:   bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
  Comments-Summary: No comments yet.
  Comments-URI:     N/A
  Status:           Draft
  Type:             Standards Track
  Created:          2018-01-24
  License:          CC-BY-SA-4.0

Table of Contents

Abstract

This proposal aims to increase the transaction capacity of Bitcoin, by splitting the Bitcoin blockchain into two or more blockchains with almost the same protocol. Theoretically, the transactions capacity would double because of double block generation rate after one split. Several such binary splits would make the original blockchain evolve into an almost-balanced block-tree. The wallet then can send small transactions through only one blockchain. The fungibility would be good enough if the two blockchains used the same consensus rules.

Motivation

Many scaling plans and proposals for the capacity of Bitcoin have been proposed in past several years. In 2017, The scaling problem has become a major drawback for blockchains, causing congestions and increasing transaction fees for both Bitcoin and Ethereum, two largest blockchain systems in terms of market capitalizations.

Several BIPs have been proposed to increase the size of blocks or adjust the block size such as BIP 101, 102, 103, 105, 106 and 107, which would increase the transaction capacity of Bitcoin blockchain if deployed. After the segwit was deployed, the block size limit was increased up to 4MB. However, some people believe it is not enough and performed a hard fork resulting in a new cryptocurrency, Bitcoin Cash (BCH), with 8MB block size limit.

The main drawback of large block size might be the network bandwidth overhead. It is harder for nodes to synchronize with other nodes for larger blocks (e.g. 1GB block). So, I propose a new scaling scheme with no need to increase block size: voluntarily split the original blockchain into two independent blockchains, and possibly split more times to construct a block-tree. This would also distribute the mining power to several leaf blockchains, make it easier to mine and possibly attract more miners. A similar idea of tree-chains has been proposed in 2014 [1]. However, the tree-chain proposal complicates the problem trying to do inter-chain communication.

Specification

If a voluntary split was performed, the blockchain would split into two independent subsequent blockchains (sub-chains). One subsequent blockchain could also split into two independent subsequent blockchains later. The subsequent blockchains of blockchain A are defined to be all the sub-chains split from blockchain A. Except the original blockchain, every blocks in subsequent blockchains of the original one should include a block batch number (bbt), to identify the block is for that chain only. One example of such block batch numbers is shown below:

                                                --------
                         -------       -------<-|00|   |<-... 
---------       -------<-|0|   |<-...<-|0|   |  --------  
|Genesis|       |Split|  -------       -------<-|01|   |<-...
|       |<-...<-|     |                         --------
|block  |       |point|  -------       -------<-|10|   |<-...
---------       -------<-|1|   |<-...<-|1|   |  --------
                         -------       -------<-|11|   |<-...
                                                --------
To avoid imbalance or asymmetry, it is better to always binary-split all the leaf blockchains.

After several splits, the original blockchain would split into many subsequent blockchains. Then the leaf blockchain can be defined as one blockchain with no sub-chains at one point. All blocks should only be appended to a leaf blockchain. A transaction batch number (tbt) can be included into a transaction, meaning the transaction should only be valid for the corresponding blockchain, if itself is a leaf blockchain, or its subsequent leaf blockchains. If there was no batch number, the transaction would be valid for all leaf blockchain(s) and thus probably be included into all leaf blockchain(s). Miners should only broadcast valid blocks with bbt same as one of the leaf blockchains, and only include valid transactions that have matching tbt with the bbt of the block to broadcast. All blocks with invalid bbt or invalid transactions should be rejected by all nodes. Therefore, the node process for a leaf blockchain should verify that all tbt match the bbt and the bbt is exactly the same one as the corresponding leaf blockchain. Also, the tbt should be included into the signed data for verification preventing replay attacks between each other leaf blockchains.

Matching Criteria for Transaction Sequence Numbers

One transaction batch number (tbt) matches the block batch number (bbt), if and only if the tbt is a prefix of the bbt (empty is prefix of any number). For example, tbt 01 matches bbt 01, bbt 011 and bbt 010, but tbt 01 doesn't match bbt 00 and bbt 0. Empty tbt (i.e. no tbt) matches any bbt.

Amount Adjustment

The wallet should adjust the amount for one unspent transaction output (UTXO), according to the number of bits of the bbt. For instance, if there were two bits of bbt for the block containing the transaction, the amount should be divided by 4, or the binary point be moved two bits left. When sending out transactions, the amount could be calculated similarly with appropriate tbt included. e.g. If 1 BTC was to be sent out, the amount field could be 4 with btb 01 included. Then, the transaction would only be valid for the leaf blockchain 01 (or its subsequent leaf blockchains e.g. 010 and 011). If the transaction was finally included in matching leaf blockchain(s), which should always happen if the transaction fee was enough, the amount of 1 BTC should be properly shown by the wallet.

Practically, the node would probably have several independent child processes or threads corresponding to every leaf blockchains with independent global UTXO databases (or even simpler, several independent software executables for every leaf blockchains), which contain all the UTXO with tbt matching the bbt of the leaf blockchain (i.e., UTXO included in it and all its precedent blockchains. e.g., the UTXO in original blockchain would be in every leaf blockchains' global UTXO). Then, the amount adjustment is even simpler. All the amounts of UTXO in a global UTXO database of an independent node process corresponding to a leaf blockchain would be divided according to the leaf blockchain's bbt. After amount adjustment, the total BTC balance amount would be the sum of all the adjusted amount of UTXO for the address.

Rationale

If the two subsequent blockchains after one split had the same protocols except the batch numbers, they had no reason to have different value. After split, addresses would be valid on all sub-chains. For micropayments without exceeding the max balance of any one leaf blockchain, the transactions would only need to use one leaf blockchain. As long as the receiver had the private key, he/she could always get and spend the bitcoins sent to the address, regardless of which leaf blockchain it was included in. The users would't perceive the difference if most wallets and exchanges only showed the total balance amount rather than balances for every leaf blockchains. Also, if the wallets randomly selected a leaf blockchain to send transactions, as long as the balance was enough, the transactions would be evenly distributed among all the leaf blockchains.

If the bitcoin on every leaf blockchains had the same value initially, miners were also most likely to be equally distributed among all the leaf blockchains. If one leaf blockchain was faster, according to the difficulty adjustment scheme, it would become more difficult to mine. The leaf blockchains were likely to have similar block generation rates with similar difficulty and similar length. Otherwise, the miners would be attracted to the leaf blockchain easier to mine, and more miners will make the block generation rate increase and then, after difficulty adjustment, harder to mine. Equilibrium would be achieved.

Compatibility

It is backward-compatible with older versions of transactions, but not compatible with older versions of wallets. The older-version wallet might display wrong balance for an address, but it is still able to send acceptable transactions.

It is not backward-compatible with older versions of nodes. All nodes should upgrade to reject blocks with no matching batch number for one leaf blockchain. They also need to check all the transactions in one block has matching batch number with the block batch number, with above-specified matching criteria. The nodes could also split into several different versions to verify part of the leaf blockchains only.

Implementation and Deployment

The version number of blocks and transactions could be good options to store the batch numbers. If the lower 8 bits were used to represent the batch number, the batch number could follow a 1. E.g. batch number 00 would be 0000_0100, 01 be 0000_0101, and empty batch number be 0000_0001. Seven splits would be possible if 8 bits were reserved for the batch number.

References

  1. ^ Peter Todd. Re: [Bitcoin-development] Tree-chains preliminary summary. March 2014.