Assumption: This article is for those, who already understand the bitcoin protocol and aware of the block size controversy. Details of the problem statement can be found in BIP 100. Satoshi's opinion regarding block size can be found here. I will be directly going into the solution without explaining the problem in details.
Solution: Difficulty changes at every 2016 block, i.e. at every 2016 block each full node does a calculation to find the next target. We will do just another calculation here. Nodes will also calculate what % of blocks in the last difficulty period is higher than 90% of the maximum block size, which is 1 MB for now. If it is found that more than 90% blocks in the last difficulty period is higher than 90% of the maximum block size, then double the maximum block size. If not, then calculate what % of blocks in the last difficulty period is less than 50% of the maximum block size. If it is higher than 90%, then half the maximum block size. If none of the above condition satisfies, keep the maximum block size as it is.
Please note that, while calculating the % of blocks, it is better to take into account the first 2000 of the 2016, than the whole of 2016. This helps to avoid the calculation mistake if some of the last few blocks get orphaned.
Reasoning: This solution is derived directly from the indication of the problem. If transaction volume increases, then we will naturally see bigger blocks. On the contrary, if there are not enough transaction volume, but maximum block size is high, then only few blocks may sweep the mempool. Hence, if block size is itself taken into consideration, then maximum block size can most rationally be derived. Moreover, this solution not only increases, but also decreases the maximum block size, just like difficulty.
Arguement 1: A miner with 11% of hash power could sabotage block size increases by only ever mining empty blocks.
Arguement 2: The interplay between the random distribution of transaction arrival and the random distribution of block times may lead to false signals.
Here is my take on the above arguements...
Counter Arguement 1: First, I would like to argue from economics' point of view. If someone wants to hold back the block size increase with 11% hash power by mining empty blocks, he has to sacrifice Tx fees, which is not economical. 11% hash power will most likely be a pool and pool miners will find out soonthat they are losing Tx fees because of pool owner's intention. Hence, they'll switch pool and pool owner will lose out. This is the same reason why 51% attack will never happen, even if a pool gets more than 51% hash power.
Next, I would like to propose a slightly modified technical solution to this problem in algorithmic format...
If more than 50% of block's size, found in the first 2000 of the last difficulty period, is more than 90% MaxBlockSize
Double MaxBlockSize
Else if more than 90% of block's size, found in the first 2000 of the last difficulty period, is less than 50% MaxBlockSize
Half MaxBlockSize
Else
Keep the same MaxBlockSize
This is how, those who want to stop increase, need to have more than 50% hash power. Those who want to stop decrease, need to have more than 10% hash power, but must mine more than 50% of MaxBlockSize in all blocks. In this approach, not only miners, but also the end user have their say. Because, end users will fill up the mempool, from where miners will take Tx to fill up the blocks. Please note that, taking first 2000 of the last 2016 blocks is important to avoid data discrepancy among different nodes due to orphan blocks. It is assumed that a chain can not be orphaned after having 16 confirmation.
Counter Arguement 2: True, that the randomness might not always give the perfect signal. But, this imperfection is inherent to bitcoin's design. Following are two such instances...
1. Target Calculation - Due to random spread of hashes sometimes blocks are found fast, while it delays sometimes. Target is calculated from the average and corrects itself at every difficulty change.
2. Block Hash Distribution - With same hash power, miners sometimes win blocks faster than other. This is again due to the randomness of nonce to hash relationship.
In our case as well, the maximum block size derived at each difficulty might not be perfect due to random distribution of transaction arrival and the random distribution of block times. But, it will self correct itself at every difficulty.
August 21, 2015 Update: The above solution was posted in bitcointalk, where users goatpig & DumbFruit came up with two different interesting arguements. The main arguements are as follows...
Arguement by goatpig: The block size max cap increment percentage should not be a constant. Rather, it needs to be derived from the network. Moreover, counting individual block size creates space for spammers to game the system. Hence averaging is a better option.
Arguement by DumbFruit: Blocks need to be almost full, so that there is always a fee pressure on transactions. As the block reward will diminsh with time, collection from fees should rise for the survival of miners, who protect bitcoin network.
To counter the above arguements, I am proposing another slightly modified solution. This will trigger maximum block size increase if...
i. Average block size of last two difficulty period is greater than 50% of maximum block size
ii. Total block size in last difficulty preiod is greater than total block size in last but one difficulty preiod
iii. Total transaction fee in last difficulty preiod is greater than total transaction fee in last but one difficulty preiod
This will trigger maximum block size decrease if...
i. Average block size of last two difficulty period is less than 50% of maximum block size
ii. Total block size in last difficulty preiod is less than total block size in last but one difficulty preiod
iii. Total transaction fee in last difficulty preiod is less than total transaction fee in last but one difficulty preiod
Increase or decrease maximum block size cap in the same ratio of total block size increase or decrease in the last difficulty preiod over last but one difficulty preiod
Please note that, while calculating last two difficulty period, we are considering the first 4016 of the 4032 blocks, rather than the whole of 4032. This helps to avoid the calculation mistake if some of the last few blocks get orphaned.
Following is the above solution in algorithmic format...
TotalBlockSizeInLastButOneDifficulty = Sum of all Block size of first 2008 blocks in last 2 difficulty period
TotalBlockSizeInLastDifficulty = Sum of all Block size of second 2008 blocks in last 2 difficulty period (This actually includes 8 blocks from last but one difficulty)
TotalTxFeeInLastButOneDifficulty = Sum of all Tx fees of first 2008 blocks in last 2 difficulty period
TotalTxFeeInLastDifficulty = Sum of all Tx fees of second 2008 blocks in last 2 difficulty period (This actually includes 8 blocks from last but one difficulty)
If ( ( (Sum of first 4016 block size in last 2 difficulty period)/4016 > 50% MaxBlockSize) AND (TotalTxFeeInLastDifficulty > TotalTxFeeInLastButOneDifficulty) AND (TotalBlockSizeInLastDifficulty > TotalBlockSizeInLastButOneDifficulty) )
MaxBlockSize = TotalBlockSizeInLastDifficulty * MaxBlockSize / TotalBlockSizeInLastButOneDifficulty
Else If ( ( (Sum of first 4016 block size in last 2 difficulty period)/4016 < 50% MaxBlockSize) AND (TotalTxFeeInLastDifficulty < TotalTxFeeInLastButOneDifficulty) AND (TotalBlockSizeInLastDifficulty < TotalBlockSizeInLastButOneDifficulty) )
MaxBlockSize = TotalBlockSizeInLastDifficulty * MaxBlockSize / TotalBlockSizeInLastButOneDifficulty
Else
Keep the same MaxBlockSize