Deadalnix’s Difficulty Algorithm Explained

Note: This article was originally published at Yours.org

The purpose of this article is to describe the difficulty targeting algorithm that has been proposed for Bitcoin Cash by Amaury Sechet (Deadalnix). The algorithm was originally announced on the bitcoin-ml mailing list on Aug 25 2017 [1], and was subsequently implemented at https://reviews.bitcoinabc.org/D571 [2]. I previously published an article outlining the difficulty targeting issue [3], the current article goes into more detail explaining the specifics of this particular proposal.

Another proposal by kyuupichan can be found at: https://reviews.bitcoinabc.org/D578 [4].

Goals

The goals of the design are:

  1. Adjust difficulty to hash rate to target a mean block interval of 600 seconds.
  2. Avoid sudden changes in difficulty when hash rate is fairly stable.
  3. Adjust difficulty rapidly when hash rate changes rapidly.
  4. Avoid oscillations from feedback between hash rate and difficulty.
  5. Be resilient to attacks such a timestamp manipulation.

Design Approach

Much of the design is based on the work of zawy12 [5].

The basic idea of this method is to look at a set of recent blocks, and estimate the hash rate that was used to produce them. Then the new difficulty target is calculated such that the hash rate will produce blocks at the desired rate.

Hash rate is estimated as work/time for each block. If you do a weighted average over time, the intermediate Time terms cancel out, and as a result, the formula for hash rate over an interval of blocks becomes

Hash Rate = delta(w)/delta(t)

where delta(w), is the amount of chainwork added to all the blocks in the measurement interval, and delta(t) is the difference between the timestamps of the first and last blocks in the set.

Once we know that hash rate, we can easily calculate the amount of work we expect to be produced in the 10 min target interval, as:

W = (hash rate) * (target interval)

To convert this amount of work into a “target”, we use the formula:

Target = (2²⁵⁶ / W) — 1

where “W” is the estimated amount of work needed to produce a hash under the Target value. This can be understood intuitively, since “W” is the number of 256-bit hashes produced, and 2²⁵⁶ is the maximum number of distinct hashes that exist, the target will be the ratio between these two numbers (adjusted down by 1, since the maximum numerical value that can be represented in 256 bits is 2²⁵⁶ — 1, and the minimum value is 0).

It should be noted that this method does not base the calculated difficulty target directly on the difficulty of the most recent block, as Bitcoin’s algorithm does currently. It uses difficulty for each block in the input set when calculating chain work, however.

The primary difference between the proposed algorithm and the zawy12 algorithm, is that Deadalnix uses two targeting windows. There is a sticky slow-target window to increase stability when hash rate is only changing slowly, and a fast-target window for when hash rate changes rapidly.

The slow-target (“intervalTarget”) is calculated, each block, over the previous 2016 blocks. This will give a stable output that does not change very quickly with variation in hash rate. The criteria for choosing the number of blocks for the window, are that it needs to be a fairly large number, and not a multiple of 13 (since the fast-target is based on a 13-block window). the number 2016 fulfills these criteria. (Note: this is calculated as a rolling calculation each block, which is different from the current Bitcoin algorithm that only calculates difficulty adjustments at the end of fixed 2016 block intervals).

The fast-target (“fastTarget”) is calculated in time-based manner. This means that rather than calculating over a set number of blocks, the target is calculated over a set time frame. A time of 130 minutes (the time to produce 13 blocks) was chosen, with a minimum of 5 blocks to avoid undersampling. Time-based sampling also means that downward difficulty adjustments can happen more quickly than upward adjustments, if measured per block. Measured by time, upward and downward adjustments rates are symmetric.

If the fast-target is within 25% of the slow-target, then the slow-target is used. This helps avoid rapid changes in difficulty due to hash rate variance.

If the fast-target is different from the slow-target by greater than 25%, then difficulty is set to the fast-target. This means difficulty will adjust up or down rapidly when there are sudden changes in hash rate, or when variance is especially high.

Specification

For each block, difficulty target is calculated as follows:

1. Targets are calculated over “target windows” of blocks with endpoints selected according to the median timestamp over three (3) blocks (implemented using the GetSuitableBlock function). This is done to lower the impact of skewed timestamps.

2. A slow-target is calculated over the previous 2016 blocks according to the formula:

slow-target = (2²⁵⁶ / W) — 1

where

W = Target Interval * delta(w)/delta(t)
Target Interval = 600 seconds.
delta(w) = (chain work of the last block in the set) — (chain work of the first block in the set)
delta(t) = (timestamp of the last block in the set) — (timestamp of the first block in the set)

3. A fast-target is calculated over the expected time to produce 13 blocks (130 minutes). The blocks that serve as endpoints of the calculation period can be found by working backward from the most recent block, and applying the following rules:

  • If the block height is less than 5 blocks from the last block, keep searching for older blocks
  • If the timestamp of the block is less that 130 minutes before the last block, keep searching
  • Set the beginning of the calculation window to the first block we find greater than 130 minutes prior to the last block in the calculation window.

(note: as before, these endpoints are selected according to the “median over 3 blocks” logic above)

The fast-target is then calculated over the selected blocks according to the same formula above:

fast-target = = (2²⁵⁶ / W) — 1

where

W = Target Interval * delta(w)/delta(t)
Target Interval = 600 seconds.
delta(w) = (chain work of the last block in the set) — (chain work of the first block in the set)
delta(t) = (timestamp of the last block in the set) — (timestamp of the first block in the set)

4. If fast-target differs from slow-target by less than (or equal to) 25% of the slow-target, then the difficulty of the next block is set to equal the slow-target.

5. If fast-target differs from slow-target by greater than 25% of the slow-target, then

the difficulty of the next block is set to equal the fast-target.

6. Finally, to prevent sudden changes in difficulty, the next target is bounded to a maximum 12.5% change from the target of the previous block. Also, a check is performed that the next target is not lower than the minimum bound allowed.

To Do

  • This proposal should be compared to alternatives such as kyuupichan’s proposal [4].
  • An activation plan for a hard fork to implement the new difficulty targeting algorithm needs to be defined.

References

[1] Mailing List announcement: https://lists.linuxfoundation.org/pipermail/bitcoin-ml/2017-August/000136.html

[2] Implementation: https://reviews.bitcoinabc.org/D571

[3] Previous article: https://medium.com/@Mengerian/bringing-stability-to-bitcoin-cash-difficulty-adjustments-eae8def0efa4

[4] kyuupichan proposal: https://reviews.bitcoinabc.org/D578

[5] Zawy12: https://github.com/seredat/karbowanec/commit/231db5270acb2e673a641a1800be910ce345668a#commitcomment-23056659

Acknowledgements

Thanks to Amaury Sechet for taking the time to explain his work to me, and to answer my questions. Any errors, however, are my own.