How does the Ethereum Homestead difficulty adjustment algorithm work?

Question

From From EIP 2, the Homestead difficulty adjustment algorithm is:

    block_diff = parent_diff + parent_diff // 2048 * 
      max(1 - (block_timestamp - parent_timestamp) // 10, -99) + 
      int(2**((block.number // 100000) - 2))

where // is the integer division operator, eg. 6 // 2 = 3, 7 // 2 = 3, 8 // 2 = 4.

How does this work?

(This question was prompted by the question What was the first block mined with Homestead?)

Other related Q&As:

• How is the Mining Difficulty calculated on Ethereum?
• What is the measured distribution of block times since Homestead?

Answer 1

Summary

If the timestamp difference (block_timestamp - parent_timestamp) is:

• < 10 seconds, the difficulty is adjusted upwards by parent_diff // 2048 * 1
• 10 to 19 seconds, the difficulty is left unchanged
• >= 20 seconds, the difficulty is adjust downwards proportional to the timestamp difference, from parent_diff // 2048 * -1 to a max downward adjustment of parent_diff // 2048 * -99

This is consistent with the statement from ethdocs.org - Ethereum Homestead - The Homestead Release:

EIP-2/4 eliminates the excess incentive to set the timestamp difference to exactly 1 in order to create a block that has slightly higher difficulty and that will thus be guaranteed to beat out any possible forks. This guarantees to keep block time in the 10-20 range and according to simulations restores the target 15 second blocktime (instead of the current effective 17s).

And from Ethereum Network Status, the average block time currently is 13.86 seconds.

---

Details

The difficulty adjustment formula:

    block_diff = parent_diff + parent_diff // 2048 * 
      max(1 - (block_timestamp - parent_timestamp) // 10, -99) + 
      int(2**((block.number // 100000) - 2))

where // is the integer division operator, eg. 6 // 2 = 3, 7 // 2 = 3, 8 // 2 = 4.

can be broken down into the following parts:

Sub-formula B - The difficulty bomb part, which increases the difficulty exponentially every 100,000 blocks.

+ int(2**((block.number // 100000) - 2))

The difficulty bomb won't be discussed here as it is already covered in the following Q&As:

• What is the "difficulty bomb" and what is the goal of it?
• When will the difficulty bomb make mining impossible?
• What if difficulty bomb makes mining impossible before POS release?

Sub-formula A - The difficulty adjustment part, which increases or decreases the block difficulty depending on the time between the current block timestamp and the parent block timestamp:

+ parent_diff // 2048 * max(1 - (block_timestamp - parent_timestamp) // 10, -99)

Subformula A1 - Lets separate out part of Subformula A

+ max(1 - (block_timestamp - parent_timestamp) // 10, -99)

and consider what the adjustment effect is due to the timestamp difference between the current block and the parent block:

When (block_timestamp - parent_timestamp) is

• 0, 1, 2, ..., 8, 9 seconds
  • A1 evaluates to max(1 - 0, -99) = 1
  • A evaluates to +parent_diff // 2048 * 1
• 10, 11, 12, ..., 18, 19 seconds
  • A1 evaluates to max(1 - 1, -99) = 0
  • A evaluates to +parent_diff // 2048 * 0
• 20, 21, 22, ..., 28, 29 seconds
  • A1 evaluates to max(1 - 2, -99) = -1
  • A evaluates to +parent_diff // 2048 * -1
• 30, 31, 32, ..., 38, 39 seconds
  • A1 evaluates to max(1 - 3, -99) = -2
  • A evaluates to +parent_diff // 2048 * -2
• 1000, 1001, 1002, ..., 1008, 1009 seconds
  • A1 evaluates to max(1 - 100, -99) = -99
  • A evaluates to +parent_diff // 2048 * -99
• > 1009 seconds
  • A1 evaluates to max(1 - {number greater than 100}, -99) = -99
  • A evaluates to +parent_diff // 2048 * -99

So, if the timestamp difference (block_timestamp - parent_timestamp) is:

• < 10 seconds, the difficulty is adjusted upwards by parent_diff // 2048 * 1
• 10 to 19 seconds, the difficulty is left unchanged
• >= 20 seconds, the difficulty is adjust downwards proportional to the timestamp difference, from parent_diff // 2048 * -1 to a max downward adjustment of parent_diff // 2048 * -99

---

The Source Code

From Go Ethereum - core/block_validator.go, lines 264-311:

func calcDifficultyHomestead(time, parentTime uint64, parentNumber, parentDiff *big.Int) *big.Int {
    // https://github.com/ethereum/EIPs/blob/master/EIPS/eip-2.mediawiki
    // algorithm:
    // diff = (parent_diff +
    //         (parent_diff / 2048 * max(1 - (block_timestamp - parent_timestamp) // 10, -99))
    //        ) + 2^(periodCount - 2)

    bigTime := new(big.Int).SetUint64(time)
    bigParentTime := new(big.Int).SetUint64(parentTime)

    // holds intermediate values to make the algo easier to read & audit
    x := new(big.Int)
    y := new(big.Int)

    // 1 - (block_timestamp -parent_timestamp) // 10
    x.Sub(bigTime, bigParentTime)
    x.Div(x, big10)
    x.Sub(common.Big1, x)

    // max(1 - (block_timestamp - parent_timestamp) // 10, -99)))
    if x.Cmp(bigMinus99) < 0 {
        x.Set(bigMinus99)
    }

    // (parent_diff + parent_diff // 2048 * max(1 - (block_timestamp - parent_timestamp) // 10, -99))
    y.Div(parentDiff, params.DifficultyBoundDivisor)
    x.Mul(y, x)
    x.Add(parentDiff, x)

    // minimum difficulty can ever be (before exponential factor)
    if x.Cmp(params.MinimumDifficulty) < 0 {
        x.Set(params.MinimumDifficulty)
    }

    // for the exponential factor
    periodCount := new(big.Int).Add(parentNumber, common.Big1)
    periodCount.Div(periodCount, ExpDiffPeriod)

    // the exponential factor, commonly referred to as "the bomb"
    // diff = diff + 2^(periodCount - 2)
    if periodCount.Cmp(common.Big1) > 0 {
        y.Sub(periodCount, common.Big2)
        y.Exp(common.Big2, y, nil)
        x.Add(x, y)
    }

    return x
}

Answer 2

Ethereum's algorithm would have been better if the max() had not been used. The parent_diff/2048*(1-t/10) could have been expanded to prevent the zero that results from integer division. This would have resulted in

diff = parent_diff + parent_diff/N - parent_diff*t/T/N

where t = parent solvetime T = target solvetime N = extinction coefficient aka "mean lifetime" aka number of block to "temper" or "buffer" the size of the response. It can't be too small or a negative difficulty can result from long solvetimes.

This is very close to the theoretically best algorithm which is an exponential moving average (EMA) that I and others have investigated. It's an approximation of the EMA by the taylor series expansion of the exponential function:

e^x = 1 + x + x^2/2! + ...

Where you use the approximation e^x = 1 + x in the EMA algorithm:

diff = parent_diff*( 1 - A + A*T/t )

where A = alpha = 1-e^(-t/T/N)

See https://github.com/zawy12/difficulty-algorithms/issues/17

This algorithm was discovered by Jacob Eliosoff who was already very familiar with EMA's for stock prices. He needed to modify it to fit difficulty, and the result turns out to be a known version that's mentioned in Wikipedia in regards to estimating computer performance:

https://en.wikipedia.org/wiki/Moving_average#Application_to_measuring_computer_performance

I say it's theoretically best because you can reduce N all the way down to "1" and the mean and median solvetimes are close to the expected T and ln(2)*T. So it's the best estimator (I know of) of guessing the current hashrate based on only the previous block.