Tuesday, September 15, 2015


One of the major problems with Bitcoin revolves around scaling. There have been numerous proposals with respect to scaling. Some proposals involve a layer on top of Bitcoin (e.g. Lightning Network, Thunder Network, StrawPay, etc). Others are actual changes to the Blockchain data structure itself (e.g. TreeChains, SideChains). In this blog, I will propose a new data structure which is an alternative to these proposals on a more fundamental level. I will refer to this new data structure as an BlockArrayChain.

Motivation for BlockArrayChain data structure
The Blockchain is basically a linked list of a block which includes a hash of a set of transactions with a nonce which generates a hash value below a specified difficulty. The reason for the controversy around increasing the block size is because there is a trade off between increasing the block size and the decentralization of the network. The BlockArrayChain is designed in such a way that instead of a single block at each node in the list there is an array of blocks at each link in the list. This way, each array consists n blocks of a set size (e.g. 1mb). I will explain in detail how the BlockArrayChain works later, but for now I will describe the benefits of such a data structure. The basic benefit is that we can maintain the current level of decentralization by keeping individual blocks at 1mb, but still allow the size of the Blockchain to grow much larger. It's important to note that the BlockArrayChain does not change storage requirements as each node would still need to store all blocks (including each block in an array of blocks), but as has been noted the main issue with increasing the block size centers around the bandwidth required to send blocks across the network and the CPU time required to validate large blocks and for them to propagate through the network. It is also important to note that the same pruning techniques used in pruning could be used with BlockArrayChains. Therefore, there are significant benefits to implementing BlockArrayChains.

Detailed description of BlockArrayChain
To simply things, think of a block in the current Bitcoin Blockchain as the following:
1.) A current hash
2.) A prev hash
3.) A Nonce
4.) A set of transactions (each of which includes a TXID which is a hash of the individual transaction)

A BlockArrayChain is similar however, instead of a single prev hash it includes all prev hashes from an array of blocks that preceded it. Note: to save space would could make it a hash of the list of prev hashes or something of the sort.

To summarize a BlockArrayChain would include the following data:
A set of blocks that include:
1.) A current hash
2.) A list (or hash of) of the previous hashes
3.) A Nonce
4.) Number of blocks targeted in the array
5.) A set of transactions (the TXIDs are partitioned across the array of blocks such that each block contains their appropriate proportion of transactions).

Note that miners may choose any number of blocks to include in the array. The current hash is adjusted downward based on the number of blocks included in the array. So the difficulty required for an array of 3 blocks is 1/3 that of a single block so it's equally beneficial to mine various numbers of blocks. It would rationally be set based on the number of transactions that are unconfirmed at any given time.

Any number of blocks may be chosen by miners in the new set of blocks. This brings up the possibility that miners may attempt to mine a different number of array elements at any given level. This is resolved exactly the same way that orphans are resolved in Bitcoin.

A rational miner would attempt to mine the fewest number of blocks that allow all transactions to fit in them. As soon as a single block is mined, it is rational for miners to continue mining that number of entries in the array until that full array is found (there is a case where very high transaction fees make it more attractive to drop the smaller array, but generally with today's large block rewards, that's not an important consideration. The system still works in that case as well). At this point, the miners would move on the the next array of blocks in the same manner. Since miners would work on different array elements, the orphan rate would be unchanged from the traditional Blockchain orphan rates at any given size.

See figure below for an outline of what this would look like graphically.
At level "A", there is only a single block, at "B", there are two blocks. At "C", there are three blocks and at D, back to two blocks.

No comments: