Tuesday, September 15, 2015

BlockArrayChains

Background
-------------------------------------------------------------------------
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.

Friday, May 15, 2015

Why Bitcoin is a superior settlement system. Bitcoin and the CAP theorem.

    Bitcoin, despite being commonly referred to as a payment network is not. It is actually a settlement network that will allow for superior payment networks to be built on top of it. Jeff Garzik's tweet on this subject was particularly succinct: https://twitter.com/jgarzik/status/595606257936957440. So, now that we know what to compare Bitcoin to (other settlement mechanisms), one might wonder why Bitcoin is superior? I will argue that the answer lies in the CAP theorem: http://en.wikipedia.org/wiki/CAP_theorem.
    The CAP theorem states that a distributed database cannot be simultaneously: consistent, available, and partition tolerant. Since all systems (including traditional banking settlement systems and Bitcoin) must accept partitions due to both network related partitions and in the past even partitions due to time delays in settling between bank branches which might have been done overnight, a settlement system must make a design decision about whether it wants to prioritize consistency or availability. The traditional banking system has chosen availability and Bitcoin chose consistency. I will explain the consequences of those design decisions in this blog.
    To further expand on how traditional banking chose availability and Bitcoin chose consistency, we have to look at what happens when there is a partition. In the traditional banking system, individual banks are actually setup in a sort of permanent partition mode. This is probably for historical reasons due to the fact that in the past you would actually need to physically hand messages from one bank to another to determine state. They use what's known as fractional reserve banking, so they can create up to a certain amount of money at any given time as long as they meet certain reserve requirements. See http://en.wikipedia.org/wiki/Fractional-reserve_banking. When you go into a bank to request a car loan, the bank can actually loan you money that it doesn't have. This leads to the problem that occurs when many people want to make a withdrawal at the same time, you have a possibility that the bank may become insolvent. This led to the need for a central bank who has the ability to create unlimited money who could always loan a troubled bank money to fix the problems. The central bank also operates as the settlement network between banks because it can guarantee that when bank A sends money to bank B, the payment will always go through and is guaranteed by the central bank who can create money at will. Today there is a settlement network called Fedwire that facilitates these types of transactions. Other countries have similar systems. This system assumes permanent long term partitions and favors availability over consistency. What I mean by that is that you can always get a loan at bank (availability), but the money supply is highly inconsistent and actually cannot be known by any one person in real time because it depends on the up to the minute activities of each bank.
    Bitcoin, on the other hand, chooses consistency over availability. To just briefly describe how the Bitcoin network confirms transactions, there is a competition among all nodes on the network to solve a proof of work puzzle that includes all transactions that are to be confirmed. See the Bitcoin white paper for full details: https://bitcoin.org/bitcoin.pdf. If the Bitcoin network is partitioned (lets just say you can only connect to one node), your transaction cannot be committed to the network. So the Bitcoin network very clearly chooses consistency over availability. While some might argue that you can have competing blocks of which one or more will be orphaned, that's actually a slightly different scenario than what I'm describing because if you have connectivity to the entire network and you are not attempting a double spend, your transaction should be included in both of the competing chains.
    So, what are the consequences of this design decision you ask? First, there is a consistently known state of the Bitcoin money supply at any given point in time. Anyone can easily look at websites that display information about the network to determine how many bitcoins are in circulation. Also, we do not need to create a lender of last resort because members of the Bitcoin network can settle debts directly.
    The next question is: what trade-offs do we make by giving up availability? It turns out very few because of the way the system was designed and some things that can be implemented in the layer above the Bitcoin system. Since Bitcoin is implemented on the internet, network partitions fairly rare. They definitely happen, but the visa network and other payment networks already depend on the internet with acceptable results. In Bitcoin, blocks are solved on average every 10 minutes, so there is the question of how you can get instant payments. This again is a result of Bitcoin's insistence on consistency over availability. However, there are some possible solutions to this problem that are being implemented in the layers above the Bitcoin protocol. For instance, the lightning network https://lightning.network/ uses something called payment channels which allow you to settle instantly. There is also something called green address (https://greenaddress.it/en/) which allows you to add a trusted third party needs to be trusted to track double spends and ensure they don't occur. This is another way to prevent double spends.
    So, to summarize: Bitcoin chooses consistency over availability while the traditional banking system choose the opposite prioritization. This results in a system more suited to modern technology. Layers above the Bitcoin settlement network will be able to resolve all currently perceived problems.