Adaptive difficulty

Adaptive difficulty is a bitcoin protocol change proposal by Iain Stewart, with the goal of letting the typical time interval from one block to the next adjust smoothly to prevailing network latency, while not compromising the strength of the blockchain, or the decentralized character of the network.

Background

The world is being wired up with ever faster connectivity. A merchant location in particular, where any kind of online transaction is desired, will usually have a fast link to either the net or specific counterparty bank(s), with paid-for higher bandwidth and lower latency than the usual domestic speeds. All but the smallest businesses where an internet presence is de rigeur now routinely choose to pay for a fast connection, sometimes choosing to pay a little extra for a guarantee of quick repair ("five nines" cover and the like).

It will therefore remain an expectation of customers that a merchant can process their transaction quickly as a matter of course. (With bitcoin, we do have the sub-community of users who desire strong anonymity and may use Tor/i2p, coin mixing services, and the like. They are tech-savvy and accept that these choices cause slowness. We can't expect that to become the broader expectation, however.)

The average 10-minute interval between blocks, and the need to wait a few blocks (6 is often cited) to achieve acceptable closeness to irreversibility of one's transaction, will likely be a barrier to ease of use in cases where an expectation of speed is firmly embedded in customers' and merchants' culture. (Even people who choose to slow down the submission of their transaction, in exchange for better anonymity for example, would still benefit from fast handling of their transaction once it has been submitted. They too may well grumble at the tens of minutes' to hours' delay on top of that of their own choosing.)

The 10-minute target interval could of course be changed, by sufficient consensus among miners and the community, to some other fixed value. Miners could boldly assert that the network latency between them "has reliably been such-and-such" (likely pleasantly short, since serious miners with their ASICs or whatever would want to pay for a fast net connection like any other net-centric business); and they could propose some multiple of this as a block interval. A change from one fixed value to another has its problems, though. A danger of choosing too short a value is that the network (of miners) fragments, into clusters who wastefully work on what they each sincerely believe is the most up-to-date block, and only later collectively purges the proliferation of short chains. The community's justified fear of this scenario would likely mean any future fixed target interval would always have to err on the side of caution (slowness).

But why have a fixed value at all? Can a protocol be fashioned where miners discover dynamically the interval that's in some sense the "best" choice, given the prevailing network latency between them? Such a protocol would have to avoid perverse incentives for any individual miner to influence the discovery process in a way that was good for that miner, but bad for the security of the blockchain.

One could imagine all sorts of formulae for deciding which way difficulty "should" go on a very fine scale (even from one block to the next) - whether similar or not-so-similar to the fortnightly difficulty adjustment already in place. The fortnightly (2016-block) adjustment is of course intended as a regulator of the impact of gradual network-wide growth or shrinkage of hash-rate, and not of moment-to-moment network latency (or of moment-to-moment anything else for that matter). But one could imagine similar attempts to measure, and adjust to, latency changes, by some clever formula.

Adaptive difficulty is not an attempt at such a formula. There are good grounds for believing that the (or a candidate) blockchain - as opposed to the blocktree held at any instant by any particular miner - simply cannot contain enough information to assist with latency discovery. Only the tree, and not any one chain, contains the kind of evidence that could assist with noticing the sort of wasteful fragmentation discussed above, for example. But to compute a network-influencing parameter according to the properties of a whole blocktree, and then embed it in any one would-be winning blockchain, would be dangerous. Even ignoring the fact that the blocktree differs from miner to miner, there would be no way, later, when the rest of the tree had died by neglect, to verify that the information embedded in the winning blockchain was correctly computed from a tree prevailing at the time - and not, for example, just made up by an attacker, who can later create a spurious tree (with false timestamps), at leisure, with bits and pieces dangling off various winning-chain blocks in whatever style it takes to make the attacker's made-up information seem to have been computed from that spurious tree.

What adaptive difficulty is, is something more radical than any such formula: a scheme where miners choose, and announce in the header, the difficulty of every block they proceed to try to solve. To those despairing that such anarchy could ever work, please read on! The regulatory function of the network - the assurance that it converges on a consensus best chain, with good immunity from attacks other than a 51% attack - is achieved by other aspects of the protocol. Out of anarchy, order will emerge.

Anarchy in the blockchain

Some general remarks first. The proof of work measure of a blockchain is its sum of difficulties, not its mere number of blocks. (The expected work cost of solving two blocks of difficulty d is the same as that of solving one block of difficulty 2d.) If, for example, generally prevailing difficulty is halved (by whatever means), the network will solve blocks of the new difficulty at twice the previous rate; and the average value of transaction fees available for reaping in the latest block will be halved. (The adaptive difficulty protocol will scale the coin-minting block reward to the difficulty too.) A chain of such new, cheaper blocks will grow at the same expected speed in sum-of-difficulty terms as ever; it is just the style of growth which will be different (twice as many blocks, of half the difficulty and average miner reward each). The economics of block solving will change in two, mutually cancelling, ways from a miner's perspective: each hash has twice the probability of solving a block, but the reward has halved. Miners should thus be broadly indifferent (ignoring network latency issues for now) to difficulty changes in either direction, so long as they are done in that reward-scaling style.

(.....got to here.....)

(uh, and now a pause folks, while I slowly learn "everything I never wanted to know about how to type in mathematical notation to a wiki but have been forced to find out"!)