Adaptive difficulty

From Bitcoin Wiki
Revision as of 01:36, 7 May 2012 by Ids (talk | contribs) (→‎Background: grammar and wording tweaks)
Jump to navigation Jump to search

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 decentralization of the network (in particular the ability of small miners to join in).

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, from a spurious tree grown later (with false timestamps), at leisure, with bits and pieces dangling off various winning-chain blocks at its inventor's whim.

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

(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!)