Kyuupichan’s Difficulty Algorithm Explained

Mengerian
Mengerian
Oct 14, 2017 · 4 min read

Note: This article was previously published at Yours.org

This article describes the difficulty targeting algorithm proposed for Bitcoin Cash by Kyuupichan (Neil Booth), announced and then updated on the bitcoin-ml mailing list [1, 2], and implemented at https://reviews.bitcoinabc.org/D578 [3].

A previous article described another proposal by Deadalnix [4].

Goals

The goals of Kyuupichan’s design are:

  1. Have an algorithm that is simple to understand, and easy to implement for SPV clients.
  2. Retain a long-term mean block interval of about 600 seconds.
  3. Adjust difficulty each block if necessary, but only by small fraction, using a 6-block window to avoid oscillations. Adjustments can happen in either direction.
  4. Be resilient to attacks such a timestamp manipulation and speeding up the coin emission schedule.

Design Approach

Kyuupichan’s algorithm takes a different approach than Deadalnix’s. Instead of calculating an estimated hash rate, and then using that as the basis of calculating a target, this algorithm starts with the difficulty target of the last block, and then “nudges” it up or down, depending on the observed timestamps of past blocks. In this way it acts as a “feedback” mechanism.

It avoids instability in the difficulty target by limiting these nudges to fairly small changes of about 0.4% for upward adjustments, and 1.6% for downward adjustments.

In order to reduce the impact of timestamp manipulation, this algorithm uses a 6-block Median Time Past (MTP) for measuring time intervals. This is that same MTP measure that is used for the current Emergency Difficulty Adjustment (EDA) in Bitcoin Cash.

One of the problems these types of feedback mechanisms often have, is that they can have periodic oscillations based on the sample size. For example, with a 6-block sample set, you would end up with oscillations with a 6 block period. This algorithm avoids that by leaving the target unchanged in the middle of the range. So as long as average block times fall within a set range, difficulty is left unchanged.

Having this range where difficulty remains unchanged opens a possibility for miner collusion to increase inflation. For example, miners could produce blocks such that timestamps are just within the bottom of the range, which would allow them to produce blocks at a faster rate than target without triggering any target nudges. In order to deal with this possibility, the algorithm also checks the longer-term block history, over the previous 2016 blocks, and increases the difficulty by a further 0.4% if the average time between blocks is 5% less than expected.

Specification

This algorithm bases some calculations on Median Time Past (MTP), which returns the median timestamp of the last 11 blocks (ending with the block under consideration). This is believed to be resilient to timestamp manipulation, and always increases monotonically due to consensus rules.

  1. Set an initial value for next-target (nTarget) to the target of the last block.
  2. Find the difference between the timestamp of the last block, and the one 2016 blocks previous. If this value is less than 95% of the target block spacing (10 min) multiplied by 2016, the reduce next-target by next-target with bitwise shift 8 bits to the right (about 0.4% reduction).
  3. Find the difference between the MTP of the last block, and the one 6 blocks before.
  4. If the difference in MTP is less than 30 minutes, next-target is decreased by itself with bitwise shift 8 bits to the right (about a further 0.4%).
  5. If this difference is greater than 128 minutes, nTarget is increased by nTarget with bitwise shift 6 bits to the right (about 1.6%).
  6. Return next-target as the difficulty target of the block.

Next Steps

Both Deadalnix’s and Kyuupichan’s proposals have undergone some testing through simulation. Python code for simulating Kyuupican’s algorithm is available on Github [5], and simulation results for Deadalnix’ algorithm were posted to the mailing list [6].

A great way to help advance this issue would be for people to scrutinize these simulation results, and run their own versions of the simulation. Ideally, the algorithms should perform well in the current minority situation, where relative hash rate can come and go quickly, as well as in potential future scenarios if Bitcoin Cash becomes a majority. An ideal algorithm will adjust rapidly to changes in hash rate, and maintain a stable equilibrium when hash rate is steady.

It would be good to simulate and analyze any other potential options as well, such as Tom Zander’s proposal [7].

The algorithms should be analyzed for their resilience to timestamp manipulation, and for their resistance to potential collusion by miners to manipulate difficulty up or down. Other potential problems should also be considered, such as the theoretical concern that a short retargeting window may make the system more vulnerable to selfish mining.

One of the goals of Kyuupichan’s algorithm is to be easy to implement for SPV clients. It would be useful to assess to what degree the various proposals differ in that regard. If we are looking at a choice of a better-performing but harder to implement option, compared to a simpler option that performs somewhat worse, we need to get a sense of the relative weight of those characteristics.

It is becoming apparent that it is very important to fix the Bitcoin Cash difficulty targeting algorithm. With careful design, it should be possible to implement an algorithm that solves the immediate problem of hash rate instability, while also serving Bitcoin Cash well into the foreseeable future.

References

[1] Kyuupichan initial proposal to bitcoin-ml: https://lists.linuxfoundation.org/pipermail/bitcoin-ml/2017-October/000305.html

[2] Kyuupichan updated proposal to bitcoin-ml: https://lists.linuxfoundation.org/pipermail/bitcoin-ml/2017-October/000328.html

[3] Kyuupichan implementation: https://reviews.bitcoinabc.org/D578

[4] Article on Deadalnix proposal: https://www.yours.org/content/deadalnix-s-difficulty-algorithm-explained-ac50eb2b1f16/

[5] Kyuupicahn simulation code: https://github.com/kyuupichan/difficulty/blob/master/mining.py

[6] Deadalnix simulation results: https://lists.linuxfoundation.org/pipermail/bitcoin-ml/attachments/20170825/00497371/attachment-0001.ods

[7] Tom Zander proposal: https://www.yours.org/content/bitcoin-cash-and-the-emergency-difficulty-adjustment-02b267a22e8a

https://twitter.com/AntonyZegers

More From Medium

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade