So given that large portions of the bitcoin community seem to be strongly attached to this notion that hard forks are an unforgivable evil, to the point that schemes containing hundreds of lines of code are deemed to be a preferred alternative, I thought that I'd offer an alternative strategy to increasing the bitcoin blockchain's throughput with nothing more than a soft fork - one which is somewhat involved and counterintuitive, but for which the code changes are actually quite a bit smaller than some of the alternatives; particularly, "upper layers" of the protocol stack should need no changes at all.

Notes:

• Unlike the "generalized softfork" approach of putting the "real" merkle root in the coinbase of otherwise mandatorily empty blocks, this strategy makes very little change to the semantics of the protocol. No changes to block explorers or wallets required.
• The point of this is largely academic, to show what is possible in a blockchain protocol. That said, if some segwit-as-block-size-increase supporters are interested in segwit because it increases the cap in a way that does not introduce a slippery slope, block time decreases are a viable alternative strategy, as there is a limit to how low block time can go while preserving safety and so the slippery slope has a hard stop and does not extend infinitely.
• My personal actual preference would be a simple s/1000000/2000000/g (plus a cap of 100-1000kb/tx to address ddos issues), though I also believe that people on all sides here are far too quick to believe that the other side is evil and not see that there are plenty of reasonable arguments in every camp. I recommend this, this and this as required reading.
• There's some chance that some obscure rule of the bitcoin protocol makes this all invalid, but then I don't know about it and did not see it in the code.

The attack vector is as follows. Instead of trying to increase the size of an individual block directly, we will create a softfork where under the softfork rules, miners are compelled to insert incorrect timestamps, so as to trick the bitcoin blockchain into retargeting difficulty in such a way that on average, a block comes every two minutes instead of once every ten minutes, thereby increasing throughput to be equivalent to a 5 MB block size.

First, let us go over the bitcoin block timestamp and difficulty retargeting rules:

• Every block must include a timestamp.
• This timestamp must at the least be greater than the median of the previous eleven blocks (code here and here)
• For a node to accept a block, this timestamp must be at most 2 hours ahead of the node's "network-adjusted time" (code here), which can itself be at most 70 minutes ahead of the node's timestamp (code here); hence, we can never go more than 3.17 hours into the future
• Every 2016 blocks, there is a difficulty retargeting event. At that point, we calculate D = the difference between the latest block time and the block time of the block 2016 blocks before. Then, we "clamp" D to be between 302400 and 4834800 seconds (1209600 seconds = 2 weeks is the value that D "should be" if difficulty is correctly calibrated). We finally adjust difficulty by a factor of 1/D: for example, if D = 604800, difficulty goes up by 2x, if D = 1814400, difficulty goes down by 33%, etc. (code here)

The last rule ensures that difficulty adjustments are "clamped" between a 4x increase and a 4x decrease no matter what.

So, how to we do this? Let's suppose for the sake of simplicity that in all examples the soft fork starts at unix time 1500000000. We could say that instead of putting the real time into blocks, miners should put 1500000000 (t - 1500000000) * 5; this would make the blockchain think that blocks are coming 5x as rarely, and so it would decrease difficulty by a factor of 5, so that from the point of view of actual time blocks will start coming in every two minutes instead of ten. However, this approach has one problem: it is not a soft fork. Users running the original bitcoin client will very quickly start rejecting the new blocks because the timestamps are too far into the future.

Can we get around this problem? You could use 1500000000 (t - 1500000000) * 0.2 as the formula instead, and that would be a soft fork, but that would be counterproductive: if you do that, you would instead reduce the real-world block throughput by 5x. You could try to look at schemes where you pretend that blocks come quickly sometimes and slowly at other times and "zigzag" your way to a lower net equilibrium difficulty, but that doesn't work: for mathematical reasons that have to do with the fact that 1/x always has a positive second derivative, any such strategy would inevitably gain more difficulty going up than it would lose coming down (at least as long as it stays within the constraint that "fake time" must always be less than or equal to "real time").

However, there is one clever way around this. We start off by running a soft fork that sets fake_time = 1500000000 (real_time - 1500000000) * 0.01 for as long as is needed to get fake time 12 weeks behind real time. However, we add an additional rule: every 2016th block, we set the block timestamp equal to real time (this rule is enforced by soft-fork: if you as a miner don't do this, other miners don't build on top of your block). This way, the difficulty retargeting algorithm has no idea that anything is out of the ordinary, and so difficulty just keeps adjusting as normal. Note that because the timestamp of each block need only be higher than the median of the timestamps of the previous 11 blocks, and not necessarily higher than that of the immediately previous block, it's perfectly fine to hop right back to fake time after those single blocks at real time. During those 12 weeks, we also add a soft-forking change which invalidates a random 20% of blocks in the first two weeks, a random 36% of blocks in the second two weeks, 50% in the third two weeks, etc; this creates a gap between in-protocol difficulty and de-facto difficulty that will hit 4x by the time we start the next step (we need this to avoid having an 8-week period where block throughput is at 250 kb per 10 minutes).

Then, once we have 12 weeks of "leeway", we perform the following maneuver. We do the first retarget with the timestamp equal to fake time; this increases difficulty by 4x (as the timestamp difference is -12 weeks, which gets clamped to the minimum of 302400 seconds = 0.5 weeks). The retarget after that, we set the timestamp 8 weeks ahead of fake time, so as to get the difficulty down 4x. The retargeting round after that, we determine the actual retargeting coefficient c that we want to have, and clamp it so that 0.5 <= c < 2. We set the block timestamp c * 2 weeks ahead of the timestamp of the previous retargeting block. Then, in the retargeting round after that, we set the block timestamp back at fake time, and start the cycle again. Rinse and repeat forever.

Diagram here: http://i.imgur.com/sqKa00e.png

Hence, in general we spend 2/3 of our retargeting periods in lower-difficulty mode, and 1/3 in higher-difficulty. We choose c to target the block time in lower-difficulty mode to 30 seconds, so that in higher-difficulty mode it will be two minutes. In lower-difficulty mode, we add another softfork change in order to make a random 75% of blocks that get produced invalid (eg. one simple way to do this is to just pretend that the difficulty during these periods is 4x higher), so the actual block time duing all periods will converge toward two minutes - equivalent to a throughput of 5 MB every ten minutes.

Note that a corollary of this is that it is possible for a majority of miners to collude using the technique above to make the block rewards come out 5x faster (or even more) than they are supposed to, thereby greatly enriching themselves at the expense of future network security. This is a slight argument in favor of bitcoin's finite supply over infinite supply models (eg. dogecoin), because in an infinite supply model this means that you can actually permanently expand issuance via a soft fork rather than just making the existing limited issuance come out faster. This is a quirk of bitcoin's difficulty adjustment algorithm specifically; other algorithms are immune to this specific trick though they may be vulnerable to tricks of their own.

Homework:

• Come up with a soft-fork strategy to change the mining algorithm to Keccak
• Determine the minimum block time down to which it is possible to soft-fork Ethereum using a timestamp manipulation strategy. Do the same for Kimoto Gravity Well or whatever your favorite adjustment algorithm of choice is.

EDIT:

I looked at the code again and it seems like the difficulty retargeting algorithm might actually only look 2015 blocks back every 2016 blocks rather than every 2016 blocks (ie. it checks the timestamp difference between block 2016*k 2015 and 2016*k, not 2016*k 2016 and 2016*k as I had assumed). In that case, the timestamp dance and the initial capacity adjustment process might actually be substantially simpler than I thought: it would simply be a one-step procedure of always setting the timestamp at 2016*k to equal real time and then setting the timestamp of 2016*k 2015 to whatever is convenient for achieving the desired difficulty adjustment.

EDIT 2:

I think I may have been wrong about the effectiveness of this strategy being limited by the minimum safe block time. Specifically, note that you can construct a soft fork where the in-protocol difficulty drops to the point where it's negligible, and say that all blocks where block.number % N != 0 have negligible difficulty but blocks where block.number % N = 0 are soft-forked to have higher de-facto difficulty; in this case, a miner's optimal strategy will be to simultaneously generate N-1 easy blocks and a hard block and if successful publish them as a package, creating a "de-facto block" of theoretically unlimited size.