On replacing difficulty algorithm in context of hard forks

[freetrader]

I am opening up a discussion here on possible replacements of the standard Bitcoin difficulty algorithm.

Such a replacement may become necessary for a full fork that retains the current PoW function, since such a chain fork might find itself in various "interesting" hashpower situations, starting from a low hashpower base, to potentially rapid increases and fluctuations (esp. if various infrastructure such as miners and/or pools are attacked).

I am currently investigating the suitability of Dark Gravity Wave v3 (DGW3) algorithm which is used in a number of other coins, notably Dash (it was written by the Dash Developer). This algorithm retargets at every block using a moving average over the last N blocks, resulting in a much more agile difficulty.
So far, I have simulated against the historical Bitcoin block data to compare how the algorithm would fare. See graphs below.

Suggestions for other algorithms of potential interest would be most welcome.

 

[freetrader]

Algorithm: Dark Gravity Wave 3 with 144-block look-back

The following graph shows a plot of the historic difficulty (in red) laid over the difficulty values calculated by DGW3 using a 144-block look-back (in green).
Standard DGW3 as used in Dash works with a 24-block look-back (which works out to 1hr in Dash terms).

Zooming in somewhere on the middle shows how the DGW3 difficulty varies substantially w.r.t. the "baseline" historic 2016-block algorithm.

Below an image from the early difficulty growth phase:

When there is marked growth, the DGW3 difficulty quite visibly leads (stays above) the historic difficulty.

 

[cbeast]

I don't know much about frequency feedback loops over networks, but what problem would this solve in Bitcoin?

 

[VeritasSapere]

@cbeast This is specifically for a minority hard fork of Bitcoin. The slow adjustment time for difficulty in Bitcoin opens up an attack vector when hashing power is able to switch across at key times.

@freetrader I have to admit the actual maths and coding for this change is way beyond my understanding, however I think what matters is whether the emission of coins is on schedule over the long term, if it does lead slightly ahead like you say can the underlying maths be adjusted in order to make it consistent with Bitcoin's current emission? I always thought that these type of difficulty adjustments should correct themselves over time towards the correct emission rate. I suppose for alt coins this does not matter as much since the emission rate is whatever the difficulty algorithm produces, whereas with what we are doing we need to replicate the emission rate of Bitcoin exactly.

DGW has been used in many alternative cryptocurrencies, I am curious to see comments on this from more people with deep technical backgrounds that might even be familiar with the intricacies and nuances of DGW3.

I suggested DGW because it seems to solve this problem that a SHA256 genesis fork would face, I do not know if it would be easier just adjusting Bitcoins difficulty adjustments to be faster compared to using this already existing solution. Or even implementing something similar independently.

 

[freetrader]

In my view, the way to stay as close to the original emission schedule of Bitcoin simply translates into:

Regulate difficulty so that block are emitted at somewhat regular 10 minute intervals (subject to the random process nature of block discovery of course).

To measure our success in meeting that goal, we can historical data and analyse the distribution of block intervals in statistical terms.

Then we can run some other algorithm over it, measure the statistics again and compare.

If we are close as far as the statistics go, then it means long-term we should satisfy a very similar emission schedule (as long as other things like the halving points are kept constant).
I'm not too worried about perfection initially since fine-tuning adjustments to the difficulty algorithm can always be delivered by later hard forks.

---

I am still playing with DGW3, to see what impacts the parameters like amount of look-behind have. I am planning to validate my simulation against Dash historical data today (to see that I've not introduced any bugs which skew the result) and create some likely synthetic scenarios (e.g. incl. attacks etc.) to see how it responds under adverse circumstances. Those scenarios should be re-usable for evaluating other algorithms, incl. a "sped-up" version of the current algorithm. We can then better compare various algorithms.

At the same time I can't spend too much time on this either. So I will soon open up the code and datasets which I'm using to simulate this, so others can join.

I see this as an area where research can benefit Bitcoin beyond just a hypothetical upcoming hard fork.

 

[YarkoL]

(Moved here from the ANN thread

If you think changing it is desirable, and perhaps it is, since this kind of coin can be easily wrecked by multipool dropping in for a quick visit - instead of Dark Gravity Wave consider Ray Dillinger's (aka Cryddit's) MIDAS. It is designed to deal with the same problem, large fluctuations in hashrate as DGW, Kimotos Gravity Wave, Digishield etc, but does it more elegantly.

Here is Cryddit's hand held walkthrough on how to implement MIDAS:
http://dillingers.com/blog/2015/04/21/altcoin-difficulty-adjustment-with-midas/

There is an additional pro and con here.
Con: To my knowledge, it hasn't been used before, so some sanity checks on testnet are must.
Pro: Public image benefit. Those other algos are strongly associated with altcoins, whereas Cryddit is one of the first people to get involved with Bitcoin, at the time when the network was basically Hal and Satoshi. Even though he was at it only for a short period, I'd love to see him get some appreciation.

 

[freetrader]

I'd like to share a little about the DGW algorithm (this applies only to v3).
Now, I've only looked at it briefly, but the math does not seem that complex.

Here is what is does in effect:

Let's assume we are using a look-back over a total of 5 blocks only.

Then the difficulty adjustment that it makes is proportional to a kind of continued fraction (or maybe rather: a rational function?) like this:

In the above, x(n) is the most recent block, x(n-1) is the previous one, etc.
The more you look back, the deeper your fraction gets.

If anyone here knows more about maths, perhaps this is a well-known function.
I'd appreciate any pointers.
[doublepost=1458121852][/doublepost]@YarkoL - fantastic input, thanks for that. I will certainly have a look at MIDAS. After playing around with various lookback settings, DGW3 indeed struck me as a little twitchy, although that's purely a subjective opinion at this stage.

 

[YarkoL]

@freetrader
Thanks! Actually the prime motivation for Cryddit to devise this algo was to ward off so-called time warp attack (while stabilizing the difficulty when hashrate changes rapidly), which is a technique where you prepare a fork with faked timestamps to get a longer chain at very little cost. It was succesfully deployed by BitcoinExpress against some smaller alts (he later tried to attack Monero with it and failed). The commonly used alternative diff adjustment algos are somewhat more vulnerable to the attack, esp when the hashrate is low.

 

[freetrader]

@YarkoL : Thanks for the background. I am interested in whether there are tools (or some good description) in how to construct a timewarp attack timestamp series.
I'm aware that DGW v3 was modified to somewhat counter this type of attack, although I'm not familiar with how they evolved it (didn't look back, hehe).

My simulation currently does not have any concept of wallclock time vs. the ntime, neither does it do mediantime filtering as in real Bitcoin.

I guess it may not yet be capable of properly reproducing & analysing such attacks, but perhaps it can be extended w/o too much difficulty.

It's Python code, so it'll take me a little time to port MIDAS as well.

 

[YarkoL]

@freetrader
I'm lousy with python, but very interested in seeing your simulation code. In fact it would be a blast to compare different diff algos graphically.

 

[freetrader]

Bookmarking a github comment providing a good overview of difficulty algorithms:

https://github.com/zcash/zcash/issues/147#issuecomment-200331246

Source, @janko33 in https://bitco.in/forum/threads/securing-against-malicious-majority-of-hashpower.1333/#post-26135

 

[greatwolf]

I'd like to share a little about the DGW algorithm (this applies only to v3).

Then the difficulty adjustment that it makes is proportional to a kind of continued fraction (or maybe rather: a rational function?) like this:

In the above, x(n) is the most recent block, x(n-1) is the previous one, etc.
The more you look back, the deeper your fraction gets.

If anyone here knows more about maths, perhaps this is a well-known function.
I'd appreciate any pointers.

I think the above can be describe with this equation

 

[freetrader]

@greatwolf,

I get a 'Page not found' for the image you tried to share...

 

[Erdogan]

I am sceptical to adjusting the difficulty in a largeblock hardfork. The difficulty is slow to adjust for a reason: We want the adjustment to be slow to avoid oscillations, there are possible attacks, and there will be less stability in the probability of finality of payment per number of confirmations.

Also, the slow adjustment we have is a guard against not so well founded forks.

With 1 block per hour, the blocks need only be 6 MB to take just as many transactions as today's system. And zeroconf works just as brilliantly. And with less than 1/6 of the hashrate, it has less chance of success. I would say you need at least a few percent of the hashrate. Not changing the difficulty would send a strong positive signal.

 

[freetrader]

It might be an option to have a faster retargeting only for a short period and then revert back to the current 2016 blocks algorithm.

Not strongly dropping the initial difficulty makes a same-POW HF seems impossible to me. Attracting 1/6 of the hashrate right off the bat -- that seem very optimistic. None of the current large miners have signaled even that much for Classic, just as an example.

 

[greatwolf]

Sorry, somehow that image wasn't showing up:

Hopefully this time it sticks.

 

[Erdogan]

It might be an option to have a faster retargeting only for a short period and then revert back to the current 2016 blocks algorithm.

Not strongly dropping the initial difficulty makes a same-POW HF seems impossible to me. Attracting 1/6 of the hashrate right off the bat -- that seem very optimistic. None of the current large miners have signaled even that much for Classic, just as an example.

We have had 3-5 % for Classic