A proposal of Bitcoin Cash difficulty adjustment algo

DAA spec sketch.md

Title: DAA improvement proposal (Billy the Algorithm)
Author: Karol Trzeszczkowski (Licho)
Status:
Type:
Created: 2020-05-01

Abstract

Current Bitcoin Cash difficulty adjustment algorithm exhibits oscillatory behavior that incentivize switch mining, causing irregular block times and increases the average transaction confirmation time. This document describes and specifies a new algorithm, that has no oscillatory behavior and possess all of the good qualities of the current algorithm.

Introduction

The fundamental role of a difficulty adjustment algorithm (DAA) is estimation of the computing power working on block production (hashrate) to keep the production steady in the changing environment. It has a crucial role in a blockchain life - it is responsible for currency emission schedule, chain shock tolerance and user experience. Dynamic DAA, adjusting difficulty on every block, tend to misinterpret some events for changes in the hashrate. Current Bitcoin Cash DAA misinterprets a hashrate spike or ditch event leaving the averaging window of 144 blocks as a change in the current computing power, affecting difficulty when it happens. It results in a change in relative coin profitability and incentivizes miners to switch a coin they are mining on. It creates a vicious cycle, where earlier spikes provoke new spikes. To solve this problem, many alternative algorithms were proposed. However none of them possess other positive qualities of the current DAA.

Requirements

A DAA should:

1. Accurately estimate the hashrate currently working on chain,
2. React symmetrically to hashrate changes,
3. Be deterministic - next work is known at the time of block construction,
4. Backward compatible,
5. Fast,
6. Be SPV-friendly,
7. Be simple, easy to understand and evaluate from the security point of view,
8. Be a low-pass filter,
9. Use integer math.
10. Keep the block production steady.

Algorithm Specification

Key feature of the proposed algorithm is performing exponential moving average on both difficulty and solve time separately. For this purpose an additional information, nAvgSolveTime shall be defined. It can be calculated iterating over the past blocks only once and then it can be held in memory and used to calculate the next nAvgSolveTime recursively.

Current block nAvgSolveTime is calculated from the previous block solve time and previous nAvgSolveTime by the equation:

current_nAvgSolveTime = α * previous_solve_time +(1-α) * previous_nAvgSolveTime,

where α is a coefficient in the interval (0,1).

To establish n-th previous_solve_time, first two suitable timestamps are chosen as median of timestamps at height n, n-1 and n-2 and median of timestamps at height n-1, n-2 and n-3.

t1 = median(t[n], t[n-1], t[n-2])

t2 = median(t[n-1], t[n-2], t[n-3])

previous_solve_time = t1-t2

Next block difficulty is calculated from the current block values difficulty and nAvgSolveTime by the equation:

next_difficulty = α * (current_difficulty / current_nAvgSolveTime) * BLOCK_INTERVAL + (1-α) * current_difficulty,

where α is the same as before and BLOCK_INTERVAL is the target solve time either equal to 600 or determined by the BLOCK_INTERVAL adjustment mechanism.

Rationale

This is an exponential moving average type algorithm. Normally (e.g.EMA-Z) exponential moving average DAA uses only one variable and on every iteration and adds a term weighted by the recent solve time. It breaks Req. 4 because it won't accept a negative solve time. This is different to what current BCH algorithm does - current BCH DAA averages both time and work done during that time period separately, with the same weight. The proposed algorithm is similar to this approach. Averaging both solve time and difficulty contains information of how much work was used to result in such a time (Req. 1). (current_difficulty / current_nAvgSolveTime) is a measure of the current hashrate. (current_difficulty / current_nAvgSolveTime) * BLOCK_INTERVAL can be interpreted as quantity proportional to the number of hashes done during the single BLOCK_INTERVAL period, if the hashrate is what we measured. Difficulty is then averaged by the partition of unit interval. The proposed algorithm also reduces the risk of having a negative weight, allowing for unordered solve times and preserving compatibility with the current ASIC circuits (Req. 4). Additional safeguard of median time of three blocks is added.

Additionally, EMA algorithms do not average difficulty, but target, which is inversely proportional to solve probability, thus nonlinear. As a result, expected time goes down faster than it goes up. Difficulty, being a proxy to projected work necessary to solve a block is directly proportional to solve probability. Using it results in a symmetric, linear response of the proposed algorithm (Req. 2), although there is the additional minor nonlinearity in both approaches originating from faster sampling during a hashrate spike and slower sampling during a hashrate ditch. The effect is still few times smaller than in the current DAA. In a scenario of 10 days 10x hashrate increase and then back to the previous hashrate value the described algorithm made on average 5x smaller error than the current DAA.

Next, difficulty can be easily calculated based on the data contained in the header. It is deterministic (Req. 3.), SPV friendly (Req. 6.), fast (Req. 5) can be implemented using integer math (Req. 9) and is indeed simple to understand and evaluate (Req. 7).

Finally, the constant nAvgSolveTime value is a discrete low-pass filter of the solve time signal with the cutoff frequency of:

fc = α/[(1-α)2π ΔT]

where ΔT is 600 seconds. Filtered data is then used for difficulty adjustment. (Req. 9)

Hashrate estimation

The requirement 1. states that the algorithm should estimate the hashrate currently working on chain. It seems circular, because work is estimated from the difficulty that we adjust. It is not the case because after the target is established the process that leads to finding another block is known. It is known how many operations will it take to solve the block the moment we set the target, therefore solve time carries the information about the hashrate. This is also why req. 3. is important. Requirement 1. is equivalent to preventing so called "DAA gaming". Gaming means tricking the algorithm, that the hashrate working on chain is different that it is. Current BCH DAA is a finite response low-pass filter and the miners reacting to changes are equivalent to Inductance in a circuit, so a narrow band of resonant frequencies may appear near the cutoff frequency, opening opportunity for gaming. The proposed algorithm has infinite response, thus events fade away smoothly. Since all frequencies are dampened, there should be no amplification and no resonance, provided the smoothing parameter α is large enough.

Timestamp attacks

Reverse timestamp attack:

In case of a single out of order timestamps surrounded by steady solve times, median of three timestamps makes a one previous_solve_time equal to zero and next one is two times larger. Following the equation for current_nAvgSolveTime, the zero time will decrease the nAvgSolveTime variable by α and the doubled solve time will even out the difference to be α² times higher than when no attack occurs. α is a small parameter so the square of it is accordingly smaller. The difficulty is first increased by α²/(1-α) and then evened out differing by a factor of the third order of α. For α around 0.01 the difficulty drop is of the order 0.000001.

Forward Time Limit attack:

MAX_FUTURE_BLOCK_TIME constant for Bitcoin Cash is 2 hours. A single timestamp like this would be worked around with the median so the behavior is identical as in reverse timestamp attack. If however two subsequent blocks were around such time in future, the 20x block solve time would increase the nAvgSolveTime by 21α, a zero solve time as before and a single negative previous_solve_time decreasing nAvgSolveTime by-18α. For α=0.01 it would mean multiplying nAvgSolveTime by a factor of 1.19, 0.99 and 0.80. Resulting change in averaged solve time is 0.94. Difficulty is initially decreased by 0.8% and finally increased by 0.06%. Two blocks with 2 hours future time would affect the current DAA decreasing difficulty by 8%. Proposed algorithm performs an order of magnitude better.

Further reading: attacks described by Zawy12.

Trade-offs

The obvious trade-off that is made is adding a new variable to be kept in memory. Some thin wallets do check difficulty so they would have to be updated to store the nAvgSolveTime once it is initially calculated.

Summary

The proposed algorithm fulfills the requirements listed at the beginning and the trade-offs are not prohibitive to implement it.

Acknowledgments

I want to thank @huckfinne for financially supporting my continuous work on BCH and Checksum0 for the exhaustive answers to my questions. Thanks to Imaginary username for the initial review of this document and the suggested simplification of this scheme. Also thanks for zawy12 for all the work he published. Thanks to Amaury Séchet for the review and suggestion of BLOCK_INTERVAL adjustment mechanism.

I edited my comment to address the MAX_FUTURE_BLOCK_TIME objection 9 minutes before you raised it. The MAX_FUTURE limit refers to the clock time at the time the block is received, not the time it is mined. If you can mine 10 blocks off of the genesis block (i.e. timestamps 11 years ago), and send those to someone, and either create a chain with absurd (negative?) difficulties, or crash their client, that's a problem.

Singularities are very bad. You need to avoid them in the consensus rules, not make them hard to exploit with node policy.

The algorithm applies α ² smooting to time fluctuations

That smoothing is a delay. That slows the impulse response, and makes more of the total response come later. And importantly, it changes the shape of the impulse response function such that the peak of the impulse response function happens with a delay of several blocks. That delay adds a resonant mode, and makes oscillations possible.

please give yourself more time for evaluating my proposal

It doesn't matter what I say. Why don't you just go implement it in https://github.com/jtoomim/difficulty/tree/comparator and see what happens?

The reason why we sometimes get negative timestamp deltas is because not all mining nodes have their clocks set correctly.

Define correctly! This is a distributed system. Bitcoin is a clock. Imagine someone sending you a block with a timestamp 2h in future. You will not be allowed to correct it. You'll have to mine next one 2h+1s.

Why don't you just go implement it in https://github.com/jtoomim/difficulty/tree/comparator and see what happens?

I made my own simulator to avoid digging through Kyuupichans code and measured a bit different metrics. Why don't you contribute to the proposal by making the simulation in your comparator that you know well? This way your check will be independent of mine and unbiased. I'd be honored to put your name on this spec. Teamwork ftw!

You'll have to mine next one 2h+1s.

If someone sends you a block that is 2h1s in the future, you ignore it. If they send it to you again a second later, you accept it.

If someone mines a block with a timestamp that's 2h ahead of your clock, they're risking you ignoring that block, mining a sibling, and you starting an orphan race with them. If your clock doesn't agree with theirs, you risk triggering orphan races unnecessarily. In non-selfish-mining scenarios, that is bad for both of you.

This creates an incentive system where it's in everybody's interest to have their clocks synchronized as well as possible. They can do this with apt-get install nptd.

None of this is new. Many other coins already have monotonically increasing timestamp requirements. Ethereum, for example, is one of them. Ethereum also has a very narrow window for timestamps that will be accepted, as per node policy.

It's also possible to allow block times to be equal to the previous block's time. I actually prefer this, as it is less likely to result in problems on testnet and regtest mode in which several blocks can be mined per second.

Why don't you contribute to the proposal by making the simulation in your comparator that you know well?

Frankly, because I do not expect the results to be good. I don't want to spend time on dead ends. I've already spent a lot more time on this than I wanted to.

And I do not believe in doing other people's work for them. It's your idea; showing that it is not oscillatory is your obligation, not mine.

All you need to do is to create a function like next_bits_wtema (https://github.com/jtoomim/difficulty/blob/comparator/mining.py#L289) and add it to the Algos dictionary (https://github.com/jtoomim/difficulty/blob/comparator/mining.py#L475).

The first-order EMA should have an impulse response function that takes the shape e^-x, or similar to the gamma distribution with k=1.

The second order EMA you're proposing will have a shape similar to the PDF of the Gamma distribution with k=2.

https://en.wikipedia.org/wiki/Gamma_distribution

In order to avoid oscillations and resonant frequencies, the impulse response function for the DAA's filter must be monotonically decreasing, with a peak as soon after the impulse as possible (ideally, the next block). The k=1 gamma distribution meets that requirement. But k=2 does not.

Your use of a 2nd-order EMA changes the shape of the impulse response function, and adds a peak at around 1/alpha blocks. This creates a resonant frequency at around fc = α/[(1-α)2π ΔT]. This oscillation will show up whenever you have miners who switch chains based on real-time profitability comparisons between BTC and BCH.

It's a PITA to accurately simulate multiple chains and the fluctuating exchange rate and hashrates between them. Did you do that in your simulator? If not, you won't see the oscillations.

The simulator code I linked do does exactly that.

@jtoomim it seems that you are right about it. Thank you for pointing out my errors.

@jtoomim I went with your advice and implemented the algorithm in your awesome comparator. Some oscillations appeared indeed. I didn't think it actually originates from doing a nested average so just for testing I removed the median and I added different weighting in the next_difficulty equation.

next_difficulty = α * (current_difficulty / current_nAvgSolveTime) * BLOCK_INTERVAL + β* current_difficulty,

β = (1-alpha)^(previous_solve_time / BLOCK_INTERVAL)

The reason to do it is to account for faster sampling when the blocks are faster. This is only approximate because α in the first term stays untouched. The rationale for beta is that when you sample two times faster the exponent is 1/2 so applying it two times will be equivalent to a single sample with exponent 1.

When I did it (I also had to decrease α), the oscillations disappeared and the response is almost identical to wtema, except the fuzz from approximated first term.

This is obviously not a final solution to the problem, as I still haven't evaluated this approach against all the requirements and attacks, it just shows what is the actual origin of oscillations here and a heavy negative weight would probably ruin it entirely. The similarity between this approach and wtema is astonishing, I wonder if I can somehow prove those are equivalent and wtema isn't calculating something erroneous and works by accident, as I initially thought.

next_difficulty = α * (current_difficulty / current_nAvgSolveTime) * BLOCK_INTERVAL + β* current_difficulty,
β = (1-alpha)^(previous_solve_time / BLOCK_INTERVAL)

This β stuff looks weird. I don't think it's "different weighting" -- I think it is itself a filter. You've got two terms in the first equation. The first is weighted by α, and the second is weighted by β. But α + β != 1 except when previous_solve_time == BLOCK_INTERVAL.

It's also very different from what you had before. Beta seems to be doing all of the work here. I think that with this formula, the first term is irrelevant. You could probably change the first line to

next_difficulty = α * current_difficulty + β * current_difficulty

and it would still work, but with even less oscillation tendency, and less tendency for overshoot. However, if you instead did

next_difficulty = (1-β) * (current_difficulty / current_nAvgSolveTime) * BLOCK_INTERVAL + β* current_difficulty,

The oscillation should come back again.

Basically, β seems to be saying, "if our block took twice as long to mine as the target, decrease difficulty by a multiple of α or alpha; if our block took half as long to mine as the target, increase difficulty by a multiple of α/2". That sets up an independent, highly-responsive 1-block-delay feedback loop on difficulty which should totally drown out the slow feedback loop you get from current_nAvgSolveTime.

if I can somehow prove those are equivalent and wtema isn't calculating something erroneous and works by accident, as I initially thought.

wtema is an EMA on target. You're thinking of doing some sort of EMA-like-thing on difficulty. Difficulty is the reciprocal of target. wtema works because the approximation 1 / (1+x) ≈ 1 - x works very well for small values of x. Since the EMA is part of a feedback loop (hashrate comes or goes based on difficulty), the small-signal response is what matters most.

β = (1-alpha)^(previous_solve_time / BLOCK_INTERVAL)

Keep in mind that this needs to be eventually implemented in integer math. Exponentiation should be avoided if possible.

This β stuff looks weird. I don't think it's "different weighting" -- I think it is itself a filter. You've got two terms in the first equation. The first is weighted by α, and the second is weighted by β. But α + β != 1 except when previous_solve_time == BLOCK_INTERVAL.

the full form of EMA is

if you actually go ahead and modify the averaging to irregular sampling you replace one (1- α) in all the terms after p1 in numerator with β. You have to take this into account in the denominator. The sum that gave you 1/α is modified and the correction to the final equation is of the order of O(α³) edit: sorry O(α²) The restriction to α + β != 1 is no longer valid for the average like this, doing both terms with beta completely defeats the purpose I did it in the first place.

Keep in mind that this needs to be eventually implemented in integer math. Exponentiation should be avoided if possible.

This is obviously not a final solution to the problem

I think you're confusing yourself by trying to use the non-recursive form, and thinking of the denominator and numerator separately.

A recursive EMA has two terms: the current value, and the recursive previous filter output. This is much simpler to deal with than an infinite number of previous terms.

An EMA would always have the sum of the weights be equal to 1. This is true for an LWMA and SMA as well. If the sum of the weights is not 1, then you're no longer averaging the terms, and you're doing something other than an MA.

That's not necessarily bad. It's just weird.

If you are unable to transition from regular form to recursive form and verify my approach then I don't really have time to guide you through this. Sorry.

@jtoomim, I'm sorry I was rude, the words about confusing got me irritated. I present the full irregular sampling idea here
https://bitcoincashresearch.org/t/irregular-sampling-for-exponential-moving-average-in-daa/50
Hope it will be clear what I am doing now.

Yes, that makes it much clearer what happened. You applied two approximation steps in the denominator but not the numerator. Those approximations have a larger error margin than you realized, and are the reason why α + β != 1 in most circumstances, and also why your code performs like a first-order EMA rather than a second-order EMA.

Changing it makes no impact on the result