Statistical analysis of Bitcoin's difficulty retargeting

[domob]

In case someone is interested, I've written a paper about Bitcoin's difficulty retargeting.  It contains a model for Bitcoin mining, which explicitly focuses on the difficulty updates as well (they seem to be underrepresented in existing research).  The paper also proposes an alternative difficulty update strategy which gives more stable block times for longer periods of exponential growth.  The latter is quite interesting from an academic point of view, but not really relevant in practice.

The paper is published by Springer at http://link.springer.com/article/10.1007/s12083-015-0347-x, and the postprint is (without paywall) on my website at http://www.domob.eu/research/DifficultyControl.pdf.

EDIT: I should probably have added the abstract here:

Crypto-currencies like Bitcoin have recently attracted a lot of interest. A crucial ingredient into such systems is the “mining” of a Nakamoto blockchain. We model mining as a Poisson process with time-dependent intensity and use this model to derive predictions about block times for various hash-rate scenarios (exponentially rising hash rate being the most important). We also analyse Bitcoin’s method to update the “network difficulty” as a mechanism to keep block times stable. Since it yields systematically too fast blocks for exponential hash-rate growth, we propose a new method to update difficulty. Our proposed method performs much better at ensuring stable average block times over longer periods of time, which we verify both in simulations of artificial growth scenarios and with real-world data. Besides Bitcoin itself, this has practical benefits particularly for systems like Namecoin. It can be used to make name expiration times more predictable, preventing accidental loss of names.

(I hope this fits in this forum section since it is about "the Bitcoin network".  If not, feel free to move it somewhere else.)

[gmaxwell]

Thanks for taking the time to formalize your thoughts here.

I'm surprised that you didn't make any reference of control theory; which speaks substantially to this subject. In particular stability analysis with 'non-linear load' (e.g. miners that turn on and off based on profitability) is a critically interesting subject.

I would have liked to see more elaboration on strategic behavior.  Most schemes I've considered that had 'accessible non-linearity'  have possible mining strategies to increase income for a given amount of work (e.g. mining in fast/slow bursts-- forget what it does to the block speed; consider how much income you mae); I've assumed but by no means proven that this was true for all non-linear schemes.  E.g. the attacker doesn't care about manipulating the height so much as getting the most height done per unit work.  (And this is the part that control theory really doesn't speak to).

Another area is security against isolation attacks. The current system's slow, capped, linear adaptation requires considerable cost to create a 'plausible' fake blockchain for a partitioned victim. Faster updating schemes generally tend to be much weaker.

Were I a reviewer I would have squaked a bit about your comments about bitcoin's "exponential growth", we _know_ that the huge ramp in the last two years is from catching up to current technology and Bitcoin's wild increase in popularity and value. Right now the hashrate is stable to growing slightly, but perhaps slightly falling ( http://bitcoin.sipa.be/growth-10k.png ).  The whole premise of wanting to understand how things grow under exponential growth is reasonable;  but we have no evidence or physical basis to argue that the system can grow hashrate forever ("moore's law" is not a physical law, it's an observation about the density of transistors on cost effective process;  ... mining is far more energy limited than density limited though there are relations).   I don't object to the area of analysis, just that you've overplayed the premise somewhat.

Another interesting area is considering "cross effect", e.g. if you use a the null predictor model an exponential reality is pessimal. Well whats the pessimal reality with the exponential predictor? What if about a first order linear predictor? etc.  It would be interesting to see a matrix of "true system" vs "model" and how bad the results are. I know in other optimization problems I've faced the "stupid filter" also happened to be the most general and robust against model errors.

Instead of taking a 'proportional' control-- did you consider just including an integral term?  It would be interesting to know how much better the unpredicted change is if you're just adding back in a small amount of the total error so far. If so, I missed it.

The comments on consensus horrified me a bit:  It is not any harder to write exact numerical software, certainly no harder than 1000 other things which must be done exactly right in a cryptocurrency. These are cryptosystems after all! Every modern video codec and audio codec had normative numerical code...  The suggestion to commit to a value and then 'check it' with an error check would almost certainly leaves the system wide open to attack. Keep in mind an attacker can drive the system into a state that reveals very small differences between implementations.  Error analysis on non-exact code is fiendishly hard and there are often library/compiler bugs lurking in non-exact math code. Basically that suggestion takes a probably similar in difficulty to every other element of cryptosystem implementation and replaces it for one which is much harder.  

Doubly so because other considerations probably limit the range of your correction (otherwise partitioning attacks, incentives, and effects of noise pushing things wildly out are worse). This means your function probably only has to operate over a known, limited range, and some simple integer polynomial approximation is probably fine.

[Peter R]

Thanks for sharing the well-written paper, domob!  I appreciate your efforts to formalize these aspects of bitcoin mining and "derive predictions about block times for various hash-rate scenarios."

I have three comments:

1. You propose a scheme to achieve average block times closer to the 10-min target under exponentially-increasing network hash rates.  I think this is interesting, but--even ignoring the added complexity and stability ramifications--I'm not sure you can label this as an "improvement."¹

For example, assume there is a rapid increase in the price of bitcoin.  Further assume that the cost of mining hardware and the $/Ghash is constant.  Under these conditions, we'd expect the network hashrate to quickly rise (since mining suddenly becomes very profitable).  This leads to more bitcoins produced per day, thereby generating additional supply to partially meet the increased demand.  In other words, the fact that the average block time drops below 10 minutes has a negative feedback (stabilizing) effect on the price dynamics (volatility).  This seems like a good thing to me.  

2.  Like gmaxwell noted, I think Section 5 is incomplete without also viewing the problem through the lens of conventional PID (proportional-integral-derivative) control theory.  We can view the Satoshi difficulty retargeting algorithm as a proportional controller.  And a proportional controller will have a steady-state error under load.  To remove steady-state error, the standard technique is to add an integral term to the controller.  But this comes at the cost of decreased stability margins and extra system dynamics (e.g., new resonances).  So, how does your scheme compare to a PI controller?  How does your scheme affect the stability of the system?

In Section 6 (page 11) you consider an attacker that "has the capability to control the network hash rate R(t) arbitrarily within some bounds R_, R^-, R_ > 0."  Following what gmaxwell said, it would be very interesting to consider (a) schemes the attacker could user to increase his profit margins given the new dynamics, and (b) whether it's possible for the attacker to destabilize the network due to the reduced stability margins associated with the new difficulty-retargetting algorithm.

3.  I think a paper like this would be also a good place to describe the statistics around the choice of 2016 blocks for the retarget time.  Obviously there's a trade off: reduce the retarget time too much and there's not enough averaging; increase the retarget time too much and the network is very slow to adapt to changes in hash rate.  I'd be interested to see some mathematical analysis around this problem.


Great paper, by the way!  I assume that was a tremendous effort!!

¹I know you partially addressed this criticism by saying block-time deviations from the target are more of a problem for non-currency uses.

[domob]

Wow, thanks gmaxwell and Peter for the elaborate feedback!  That's definitely already more than I hoped to get here.  My research goals for this paper were:

• Develop a statistical model for block rate behaviour with Bitcoin's current difficulty adjustment, including for exponential hash rate behaviour.
• Try to find an alternative that counterbalances the too fast blocks in the latter scenario.

You are definitely right, analysis of PID controllers are something that would fit perfectly.  Unfortunately, I'm no expert in this area - most people in my community do optimal control with infinite-dimensional optimisation instead of "practical" approaches.  That's no valid argument, of course - another one is that I tried to match my goals stated above, and think that further things would be better in follow-up research since the paper got already relatively long as it is.

I would have liked to see more elaboration on strategic behavior.  Most schemes I've considered that had 'accessible non-linearity'  have possible mining strategies to increase income for a given amount of work (e.g. mining in fast/slow bursts-- forget what it does to the block speed; consider how much income you mae); I've assumed but by no means proven that this was true for all non-linear schemes.  E.g. the attacker doesn't care about manipulating the height so much as getting the most height done per unit work.  (And this is the part that control theory really doesn't speak to).

Another area is security against isolation attacks. The current system's slow, capped, linear adaptation requires considerable cost to create a 'plausible' fake blockchain for a partitioned victim. Faster updating schemes generally tend to be much weaker.

These are definitely interesting suggestions.  I did not take any game theory about profits into account - probably for two reasons:  Firstly because I'm from the Namecoin community and thus do not see currency as the main (or only) application; at least in the back of my mind, even though it still is for the miners.  Secondly because I'm not a game theorist; others (like the cited papers) are working on such strategies already and probably know much more about them than I do.  Nevertheless, this is definitely a good suggestion for further research and another paper.

Were I a reviewer I would have squaked a bit about your comments about bitcoin's "exponential growth", we _know_ that the huge ramp in the last two years is from catching up to current technology and Bitcoin's wild increase in popularity and value. Right now the hashrate is stable to growing slightly, but perhaps slightly falling ( http://bitcoin.sipa.be/growth-10k.png ).  The whole premise of wanting to understand how things grow under exponential growth is reasonable;  but we have no evidence or physical basis to argue that the system can grow hashrate forever ("moore's law" is not a physical law, it's an observation about the density of transistors on cost effective process;  ... mining is far more energy limited than density limited though there are relations).   I don't object to the area of analysis, just that you've overplayed the premise somewhat.

This is true.  I'm aware of this (although I have to admit that I did not really question the premise of exponential growth and just took it as research goal).  But I still think that exponential growth is, beside constant hash rate (which is trivial), the most interesting scenario to consider in theory - even if it may not be as important in practice as it was over the last years.

The comments on consensus horrified me a bit:  It is not any harder to write exact numerical software, certainly no harder than 1000 other things which must be done exactly right in a cryptocurrency. These are cryptosystems after all! Every modern video codec and audio codec had normative numerical code...  The suggestion to commit to a value and then 'check it' with an error check would almost certainly leaves the system wide open to attack. Keep in mind an attacker can drive the system into a state that reveals very small differences between implementations.  Error analysis on non-exact code is fiendishly hard and there are often library/compiler bugs lurking in non-exact math code. Basically that suggestion takes a probably similar in difficulty to every other element of cryptosystem implementation and replaces it for one which is much harder.  

Good points.  You definitely know much more about the practice of implementing consensus code than I do.  I mostly wanted to share my thoughts about this, but I definitely see the "suggested" alternative update strategy as an academic and theoretical thing - at least for now.  I tried to make clear that I did some mathematical analysis on it, but it still needs to be analysed against attacks and it also needs much more thought when actually implementing it in some way.  Maybe I did not make it as clear as I wanted to.  As a matter of fact, I would strongly object to implementing this as it is for Namecoin (which someone in the community suggested).  It would be much more practical to base name expiration off block timestamps instead (which is something I thought about and realised partly only after I had written the paper, though).

3.  I think a paper like this would be also a good place to describe the statistics around the choice of 2016 blocks for the retarget time.  Obviously there's a trade off: reduce the retarget time too much and there's not enough averaging; increase the retarget time too much and the network is very slow to adapt to changes in hash rate.  I'd be interested to see some mathematical analysis around this problem.

That's also an interesting point!  I guess one can do something similarly to what I have done for the expected value to derive also the variance of the block times and then analyse it in some way to find an "optimal" balance.  I initially wanted to consider also variances (at least a bit), but then the paper got longer than expected anyway and so I left it out for now.