Skip to content

Instantly share code, notes, and snippets.

@sipa
Last active February 20, 2019 23:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save sipa/1a70884abe6d0a7cddc340c99f741a41 to your computer and use it in GitHub Desktop.
Save sipa/1a70884abe6d0a7cddc340c99f741a41 to your computer and use it in GitHub Desktop.
Bitcoin difficulty adjustment

Oddities of Bitcoin's difficulty adjustment

Honest behavior

Bitcoin's difficulty adjustment formula kicks in every 2016 blocks. Let's group these in periods. Blocks 0-2015 are period 0, blocks 2016-4031 are period 1, and so on.

The difficulty of period p is the difficulty of period p-1 multiplied by 2 weeks divided by the difference between the timestamps of block 2016p-2016 and block 2016p-1.

This difference only observes the time taken by 2015 blocks. As a result we expect the retargetting interval to actually target a block time of (2 weeks)/2015.

If we look at the actual distribution of observable timestamp differences, we find that this is incorrect. The distribution of the duration of each individual block, assuming a difficulty that exactly corresponds to the actual hashrate, is an exponential distribution with λ = 1/600s. The sum of 2015 independent instances of this is an Erlang distribution with k=2015 and λ = 1/600s. The mean of this distribution is (2 weeks)/2015 as estimated before, but this is fact the wrong metric to look at.

With credit to Ian Goldberg, the difficulty adjustment formula uses the inverse of the observed difference. As a result, we care about the expected value of this inverse. An intuitive way to see this that if we approximate the Erlang distribution of observed periods with a Gaussian distribution (which is likely true given the Central Limit Theorem) which is symmetric, 75% and 125% of (2 weeks)/2015 should be equally probable. As a result, the inverse being 1.333 and 0.8 times 2015/(2 weeks) will be equally probable as well - but the 1.333 side is wider than the 0.8 side. This asymmetry introduces a bias.

The correct interblock time under the formula above, assuming constant hashrate and honest timestamps, is 600(2016/2014) seconds. [this](E(2016600/(X)) where X~ErlangDistribution(2015,2014/(2016600))) Wolfram Alpha expression shows that the average difficulty adjustment is one whenever the interblock time is equal to that value above. So we expect difficulties such that the interblock times oscillates around 600(2016/2014) seconds. Simulations show that this is indeed the case.

This means that the average retarget interval under constant hashrate and honest timestamps takes 2 weeks, 20 minutes, and 1.191658 seconds.

Timewarp attacker behavior

When trying to exploit the timewarp vulnerability, an (100% hashrate) attacker will try to maximize the time difference between the first and the last block in every period. He can do this by keeping the end of the interval honest, but minimizing the first one.

The timestamp of the first block is constrained by the MedianTimePast rule, but this rule is satisfied by simply increasing the timestamp by 1 seconds once every 6 blocks, with the exception of setting the timestamp of the last block in every period to the current time. Given sufficient amounts of time, this permits bringing the difficulty down to one.

Limiting the timewarp difficulty factor

When an additional rule is introduced that constrains the first block in every period to be larger than the previous period's last blocks' timestamp minus 600s, the attacker cannot bring the interblock time below 599.999851 seconds.

To analyze this, note that the first block of the previous period is now equal to the last block of the period before that minus 600s. As the last block of 2 periods ago had an honest timestamp as well, this means that the difference between the first and last block of the previous period is actually an Erlang distribution with k=2016 plus 600 seconds.

Wolfram Alpha fails to compute this directly, as seen here. However, with manual simplications the same factor 1 can be obtained in this case.

The expected interblock time under attack, with a maximum timestamp jump back of 600c seconds seems to be given by 600/(2015!/(c^2015*e^c*Ei(-c) + sum((2014-i)!*(-c)^i,i=0..30)) / 2016). Substitute c for a specific value.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment