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.

EDIT 2012-11-22: My idea is essentially the same as that proposed by Meni Rosenfeld on the Bitcoin forums. Please read and enjoy and critique his adaptive difficulty proposal! (I'll leave this page here for historical completeness, but not continue working on it.) Iain Stewart 01:00, 23 November 2012 (GMT)

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

...and now for something completely different! (unpolished teaser for now...)

(Just to explain - I'm neglecting this adaptive difficulty stuff for a while [sorry!] because I seem to have almost accidentally invented [the bare beginnings of] a different system which protects against even a considerably-greater-than-50% attack! I don't want to create a page on it just yet before I thoroughly check that I'm not making a fool of myself... [well, I'll allow myself a stub, as a home for this teaser stuff: "proof of blockchain fair sharing"] ...but as a teaser description: it's of proof-of-stake flavour [which makes me nervous in some ways, but that's another story], and it relies on the fact that stakeholders are pseudonymously trackable, unlike proof-of-work contributors, and therefore a formula for blockchain height can reward closeness to fair-share proportions in such a way that a 90% attacker finds they can't stop the honest 10% contributing too-expensive-for-attacker-to-reverse blocks which, to the attacker's chagrin, incorporate the accumulated transactions the attacker has been endlessly reversing and re-excluding in an effort to ruin the credibility of Bitcoin. [And any change to the attacker's pseudonymous identity/identities destroys their bitcoin-days' stake and takes them out of the running as a big attacker for a long time.] - More to follow real soon now hopefully!)

(To expand a little on the above teaser: One might think that by reductio ad absurdum no system can protect against a >50% attack, because in a purported proof of immunity of the honest <50% from the malicious >50%, the labels "honest" and "malicious" ultimately have no technical meaning, and so just swapping the labels would, absurdly, give a second proof, saying that the <50% community can't "attack" [i.e. save us all from] the >50% community, in contradiction to the first proof. That reductio argument is false here - there is an asymmetry between the two communities' goals, as follows. [I'm talking about an attack to destroy the usability of Bitcoin. An attack to achieve double spending is a much lower-impact event, the analysis of which I'm therefore postponing, although on general grounds the situation is probably neither especially better nor worse than with other protocols.] The >50% "community" [the attacker(s)] is trying to exclude transactions - perhaps all of them, perhaps those of specific people it wants to harass, perhaps random ones just to create fear that "I could be next" - from entering the winning blockchain. Thus it has to achieve total exclusion of the would-be blocks originating from the <50% community, who keep including the transactions to try and earn an honest profit from the fees. By contrast, the <50% community [the just-trying-to-earn-a-living honest miners] doesn't have to achieve exclusion of the attacker's blocks - they're happy with a mixed blockchain where, reasonably often, another honest block gets in and stays in. So long as they can get transactions bedded down into the blockchain, they've avoided the ruining of Bitcoin as a usable system. It's this crucial asymmetry between the two communities which lets the honest miners win - a chain height formula which suitably rewards diversity of pseudonymous composition will stop even a 90% attacker "community" from achieving its, tougher, goal. I hope this indicates the general direction I'm headed. Iain Stewart 02:15, 21 May 2012 (GMT))