What the heck is a difficulty adjustment algorithm? And why do we need a new one?

2 263
Avatar for BitcoinOutLoud
3 years ago

I've recently uploaded a new video to my Bitcoin Out Loud YouTube channel. (It should show up on my LBRY channel in a day or two!)

[bad iframe src]

Here is the script for anyone interested:

In this video, I’ll be covering the proposal from Jonathan Toomim to adopt a new Difficulty Adjustment Algorithm this coming Bitcoin Cash upgrade in November 2020. But before we get to that, it may be a good idea to answer the question, what the heck is a difficulty adjustment algorithm? And why do we need a new one in the first place?

To start, let’s remember that Bitcoin groups transactions into blocks. These blocks are added to the “blockchain” only when a miner finds a solution to what is effectively a guessing game puzzle for that block. Check out the video about How Bitcoin Works on the Bitcoin.com channel for more details about why that’s the case.

In order to keep the average time between blocks the same and issue new coins into the supply at a predictable rate, we need a systematic way [aka an “algorithm”] to adjust the difficulty of that guessing game puzzle when there are more or less guesses being made on the network at once.

Originally, the “DAA” was pretty simple. Every two weeks, or 2016 blocks, check the average time between those 2016 blocks. If it averages less than ten minutes per block, increase the difficulty. If it averages more, decrease the difficulty. And while this algorithm worked fine for the most part, at least before Bitcoin split into BTC and BCH, it did have its own subtle consequences that you might not think of at first.

For example, since hashrate on the Bitcoin network has done much more increasing than decreasing, and the difficulty is only adjusted every two weeks, the average block time for Bitcoin has actually consistently been below 10 minutes on average.

And things got infinitely more complicated when the Bitcoin blockchain split into BTC and BCH. While before, miners simply mined Bitcoin if it was profitable, after the split, miners had the additional option of mining on one chain or the other.

Because of that, Bitcoin Cash almost certainly needed a new algorithm at the time of the split. Waiting 2016 blocks to adjust the difficulty could potentially result in the death of the chain. Those 2016 blocks, which normally would take 2 weeks to mine, could take two months or longer to mine if there is a significant drop in hashrate. And if the chain becomes unprofitable enough or a bad enough investment in the eyes of miners, then the chain could simply halt as no one continues to mine it. A potential delay of 2016 blocks is simply much too slow a response for a multi-Bitcoin ecosystem.

So a new algorithm was implemented but, unfortunately, it was far from perfect. This “Emergency Difficulty Algorithm” (or “EDA”) worked like the original algorithm, but also detected extreme cases of low hashrate in recent blocks and then lowered the difficulty significantly for the next block in those cases. This algorithm led to wild swings in difficulty and hashrate. Miners would take advantage of the low difficulty when the EDA “kicked in”, mining many blocks in a short period of time, and then they would simply leave the chain to mine BTC when the difficulty went back up and profitability went back down... Until, of course, the EDA kicked in again, which required a long period of slow blocks that were only produced at all because at least some miners mined BCH at a loss during that period of higher difficulty.

These “oscillations” between high and low hashrate led to much longer average confirmation times, since a transaction is much more likely to be sent during one of the long periods of slow blocks than in the short bursts of blocks that happen in between. They also caused significantly more blocks to be mined than one every ten minutes on average, which is the reason Bitcoin Cash is currently about a month ahead of BTC in terms of blocks and total number of coins.

It’s worth noting, though, that this issue isn’t really the fault of the miners. They don’t even have to “plan ahead” to “abuse” this problem. It happens naturally given the existence of miners who switch what they’re mining in the current moment simply depending on which chain is currently more profitable. It’s up to us to build a system where profit-seeking behavior benefits the system as a whole, or at least doesn’t disrupt it.

The EDA was quickly replaced with another new algorithm, this one built from scratch instead of modifying the old DAA, and it did perform much better, but it was and is still prone to “oscillations”, that is, swings between higher and lower difficulty and hashrate.

This new difficulty adjustment algorithm, which has been Bitcoin Cash’s algorithm for two and a half years now, recalculates the difficulty every single block, based on the average amount of time between the previous 144 blocks, which is about 1 day’s worth of blocks. Mr. Toomim does a great job explaining where these oscillations come from in his in-depth video, but here’s a condensed version:

Because the current algorithm averages the block times of the last 144 blocks, blocks leaving that 144 block window when a new block is mined have just as much effect on the difficulty as the block entering the window. Whenever a quickly mined block leaves the window, it causes a decrease in difficulty, because the average time between blocks goes up. That lower difficulty brings about another faster block.

Generally, whatever events took place 144 blocks ago are likely to be “echoed” in the present, and this continues as a positive feedback loop because, of course, that echo will eventually leave the 144 block window, creating its own echo. It’s really neat how you can see as he scrolls that whatever is happening at the lower-left where blocks are leaving the window is what you can expect to then happen with the new blocks in the upper-right.

In addition to degrading the user experience with long confirmation times, these oscillations make it more profitable for a miner to not mine BCH at all during points of high difficulty. This is a strategy that, if used by enough miners, could cause the death of the BCH chain as blocks stop coming in at all. We are very lucky to have miners who are invested in BCH enough in the long term to mine it at a loss to keep it functioning, and even point extra hashpower to the chain at great cost to themselves when a block hasn’t been found in an especially long time. But we should certainly not depend on the charity of miners to keep BCH working.

When it comes to alternatives, there are several options. For example, Real-time Targeting algorithms, or “RTT’s” take into account how long it’s been since the last block to determine the difficulty of the current one. While a neat idea, it’s a relatively large change to how Bitcoin works, and requires miners’ clocks to be well synchronized, which opens up the chain to a wide variety of potential problems and exploits.

Instead, let’s consider that the problem with the current algorithm is that data points leave the set abruptly. It’s abrupt because the algorithm is a “Simple Moving Average” algorithm, or SMA, where each block in the window is given equal weight.

To address the problem at its root, we can instead reduce the effect any given block has on the current difficulty as it gets older. If we do this “linearly”, with a constant decrease in influence, we get algorithms like lwma, which stands for linearly-weighted moving average, and the wt, or “weighted time”, family of algorithms.

Another option is to reduce the influence of a block exponentially as it gets older, which is what the EMA, or “exponential moving average” family of algorithms do. Algorithms in this class include Jacob Eliosoff’s ema-1d and simpexpt-1d, wtema from Tom Harding, and asert from Mark Lunderberg. EMA’s have some unique benefits when it comes to calculating the current difficulty.

So with all these options, what can we possibly do to figure out which one is best? Well it turns out, actually a lot. Open-source software, forked by Mr. Toomim from kyuupichan’s difficulty adjustment simulations, makes it much easier to compare the behavior of different algorithms with its graphical user interface, as well as an interface full of the user’s graphs.

And while I’m not an expert in the details, it does seem like this simulator was made with lots of important things in mind, like the option to set what percentage of miners mine BCH “steadily”, or no matter what, what percentage are “variable miners” which will switch partial hashrate back and forth depending on profitability, and what percentage are “greedy”, and will switch 100% of their hashpower depending on which chain is more profitable, given a threshold of, say, 3% greater profitability.

While models can not, of course, be perfect, they can still help us make as educated a decision as possible. The potential for oscillation problems with the current algorithm was, in fact, predicted before it was implemented back in 2017, using these tools.

The current DAA’s oscillations have even been getting worse over time, as more miners switch to more profitable strategies that involve switching chains depending on their relative profitability. The results of these simulations, along with the urgent nature of the current DAA’s problems, make it clear to me that we should absolutely change the DAA this coming upgrade. There are several drastically superior options, and it’s really just about deciding which of them to implement.

Take a look at this table showing simulation results for 5 algorithms at three different block window sizes. While all of the algorithms result in average block times of very close to 600 seconds, you’ll notice that several of them actually have much longer average confirmation times. These are the SMA (or “simple-moving-average”) algorithms.

All of the other algorithms perform well, though asert does consistently have the edge.

The chart also shows how much more profitable it is to have one mining strategy over the others. Once again, the SMA algorithms are vastly outperformed by the other options, which keep the three types of mining much closer in profitability.

Since the non-SMA options do perform so similarly, it’s arguably more important to make the choice between them based on considerations other than their simulated performance as a DAA, and instead based in things like how much work they would be to implement, and how costly they are to run (in terms of processing resources). Mr. Toomim counts out lwma and wt because they “require sampling every block header in their windows (e.g. 288 blocks) in order to calculate the next block’s difficulty...” That left wtema and asert, which each only require sampling two block-headers.

If you’d like the details on how these two algorithms work, definitely check out Toomim’s original article on read.cash, but here are the two points that he thinks are most important when picking between the two: First, integer approximations are harder with asert, and apparently you shouldn’t use floating point math because different processors can differ slightly in how they handle it. Second, wtema has issues with singularities, where the algorithm fails completely given certain inputs, and negative timestamps, which is when a block has an earlier timestamp than one that is before it on the blockchain.

Both algorithms need to get more complex to work around their respective issues, but he argues that asert is the less problematic because it doesn’t require messing with other consensus rules, while wtema would require forbidding large negative solve times.

Mr. Toomim then covers picking an integer approximation method, deciding the half-life for the exponential function, picking a block height based activation over a “median time past” activation, testnet details, potential attacks, and how to mitigate those attacks, with his own links to even more information, all of which you should check out if you’re interested but, for the sake of brevity, I won’t get into any of that here.

In his conclusion, Mr. Toomim lists 12 desirable properties of a DAA, and I’ll just read them verbatim.

  1. It should be stable, and not prone to oscillations;

  2. It should keep confirmation times low;

  3. It should keep incentives for miners to perform hashrate shenanigans low;

  4. It should keep incentives for miners to perform timestamp manipulation shenanigans low;

  5. It should keep incentives for miners to perform selfish mining shenanigans low;

  6. Because of #3, #4, and #5, honest mining strategies with steady hashrate should get near-optimal income;

  7. The chain should recover quickly after sudden changes in hashrate and/or exchange rate;

  8. The average block interval should be kept close to the target (600 seconds);

  9. The algorithm should be mathematically simple and elegant;

  10. The algorithm should be easily understood and analyzed;

  11. The algorithm should be easy to implement elegantly and simply; and

  12. The algorithm should have few or no edge and corner cases.

It will be up to the rest of the development community to decide whether they accept these priorities, and whether or not they agree that asert fits them best.

Before finishing up, I want to just give Jonathan Toomim serious props for taking the initiative to create a proposal and put it out there. I also think it’s very reasonable that, as he’s mentioned elsewhere, he would be happy with many of the other options as well, suggesting that instead of trying to find the “best” algorithm, maybe we should just try to find the one that is acceptable to the largest number of relevant parties.

I hope that the discussion about the Bitcoin Cash DAA can remain reasonable and evidence-based, and then, once a decision needs to be made, I hope that that decision-making process can also remain reasonable, where everyone is willing to compromise at least a little bit.

$ 8.33
$ 4.42 from @TheRandomRewarder
$ 2.00 from @DavidRAllen
$ 1.00 from @JaimeMoksha
+ 4
Avatar for BitcoinOutLoud
3 years ago


Good article. Thanks a lot.

$ 0.00
3 years ago

It is worth pointing out that options like RTT can make difficulty more responsive to hashrate or exchange rate changes, but do not address the "echo problem" of the current DAA in any way. Since the "echos" are the main cause of our current trouble, RTT can only bring a very small improvement, while changing the DAA itself to something like ASERT brings a very large improvement.

$ 0.00
3 years ago