Best difficulty algorithm: Zawy v6

This page will not be updated anymore.

See this page for the best difficulty algorithms

# Tom Harold (Degnr8) "wt-144" 
# Modified by Zawy to be Weighted, weighted Harmonic Mean (WWHM)
# Zawy-selected N=30 and timestamp handling for all coins.
# No limits in rise or fall rate should be employed.
# MTP should not be used

# set constants
N=30
T=600 # (target solvetime)
adjust=0.98 # 0.98 for N=30
k = (N+1)/2 *adjust * T

# algorithm
d=0, t=0, j=0
for i = height - N+1 to height  # (N most recent blocks)
solvetime = TS[i] - TS[i-1] 
solvetime = 10*T if solvetime > 10*T
solvetime = -9*T if solvetime < -9*T
    j++
    t +=  solvetime * j 
    d +=D[i]
next i
t=T if t < T # in case of startup weirdness, keep t reasonable
next_D = d * k / t 
and apparently better and amazing in that there's not even a loop or looking at old data:

=======================

# Jacob Eliosoff  EMA (exponential moving average)
# ST = previous solvetime
# N=15 (Zawy-selected)
# MTP should not be used

ST = previous timestamp - timestamp before that
ST = max(T/50,min(T*10, ST))
next_D = previous_D * ( T/ST + e^(-ST/T/N) * (1-T/ST) )

The following is older text. The important stuff is above.

# Zawy v6 difficulty algorithm 
# Newest version of Zawy v1b
# Based on next_diff=average(prev N diff) * TargetInterval / average(prev N solvetimes)
# Thanks to Karbowanec and Sumokoin for supporting, testing, and using.
# (1+0.67/N) keeps the avg solve time at TargetInterval.
# Low N has better response to short attacks, but wider variation in solvetimes. 
# Sudden large 5x on-off hashrate changes with N=12 sometimes has 30x delays verses 
# 20x delays with N=18. But N=12 may lose only 20 bks in 5 attacks verse 30 w/ N=18.
# This allows timestamps to have any value, as long as > 50% of miners are
# approximately correct and as long as timestamps are ALLOWED to 
# be out of order to correct bad timestamps. 
# Miners with >50% can be prevented from driving difficulty down to 1 if
# nodes do like bitcoin and have a median time and forbid blocks to have a timestamp
# more than 2 hours ahead of that time. 
# For discussion and history of all the alternatives that failed: 
# https://github.com/seredat/karbowanec/commit/231db5270acb2e673a641a1800be910ce345668a
#
# D = difficulty, T=TargetInterval, TS=TimeStamp, ST=solveTime

N=16;  # Averaging window. Can conceivably be any N>6.  N=16 seems good for small coins.
X=6;  # Size of expected "hash attacks" as multiple of avg hashrate. X=6 for new small coins.

# An X too small is unresponsive. X too large is subject to timestamp manipulation.
# The following is how X is used.

limit=X^(2/N); # Protect against timestamp error. Limits avg_ST and thereby next_D.

# Instead of X and limit, there can be a limit on the individual TS's in relation 
# to previous block like this:
# R=6; # multiple of T that timestamp can be from expected time relative to previous TS.
# Then nodes enforce that the most recent block have a TS:
# TS = TS_previous_block +T+ R*T if TS > TS_previous_block +T+ R*T;
# TS = TS_previous_block +T-R*T if TS < TS_previous_block +T - R*T;
# 
adjust = 1/(1+0.67/N); # Keeps correct avg solvetime.

# get next difficulty

ST=0; D=0; 
for ( i=height;  i > height-N;  i--) {  # go through N most recent blocks
   # Note: TS's mark beginning of blocks, so the ST's below are shifted back 1
   # block from the D for that ST, but it does not cause a problem.
   ST += TS[i] - TS[i-1] ; # Note:  ST != TS
   D += D[i];
}
ST = T*limit if ST > T*limit; 
ST = T/limit if ST < T/limit; 

next_D = D * T / ST * adjust;   

# It is less accurate to use the following, even though it looks like the N's divide out:
# next_D = sum(last N Ds) * T / [max(last N TSs) - min(last N TSs];

=============== post to Bitcoing Gold github: That was Digishield's reasoning. In reading the history of the Digishield development, it gives the impression the asymmetry caused problems, so they added the "tempering" to "fix" it, maybe not realizing this fix was just making it so slow the 32/16 became irrelevant. Either way, the main problem is the opposite: not returning to normal difficulty fast enough after a big hash miner leaves, causing long delays between blocks. Bitcoin Cash tried to solve this by doing the reverse asymmetry of dropping a LOT faster than it rises. This has caused oscillations and issuing coins too fast, and a few blocks every 2 cycles with really long delays. Asymmetry in the allowed rise and fall will change how fast coins are issued at the least, requiring an adjustment factor. Rising fast protects your constant miners, although if a large miners come on and off at the right times and have a bigger coin to always return for a base profit, they can always get 1/3 of the coins issued at "zero excess cost" in difficulty (the difficulty algo was not rising fast enough to adjust to the increase in hashrate). The only thing that can help is to have a shorter averaging window to respond faster, but it turns out this also allows more frequent accidental drops in difficulty and if they simply attack more often for shorter periods, they can still get 1/3 of the block for "zero excess cost". Approximately, they just need to attack for 1/2 a window averaging period and stay off the next full averaging period, or just choosing when difficulty seems a little low on accident. Dropping fast prevents a lot of long-delay blocks after an attack and prevents your constant miners from suffering a long period of high difficulty. By leaving in the +/- 16% limit I am only trying to prevent catastrophic attacks on the timestamp. For example, if the code keeps bitcoin's node-enforced 2 hour limit on how far forward miners assign timestamps, and if a pool has >50% hashrate, then after a few blocks they would "own" the MTP (median time past) and can set it to 2 hours ahead of time (12 blocks). Zcash will likely reduce this to 900 seconds which is close to the 1000 seconds I recommended before they launched a year ago. Their current limit might be 3600 seconds. It appears BTCG copied Zcash's difficulty code. It should be kept in mind Zcash is 2.5 minute blocks, so if BTCG is using a stricter time limit than BTC like Zcash, it should not go below 3600 seconds. Zcash can do a 900 second limit because that is 6 blocks for them. An equivalent time in BTCG is 3600 seconds. With N=40 like I've proposed, the 2-hour limit would allow a miner with 10x the normal hashrate to make the difficulty think it needs to drop to 40/(40+12) = 77% of correct difficulty when they begin to own MTP. After 12 blocks difficulty would be low by ```40^12 / [(40+12)*(40+11)*(40+10)*(40+9)*.... = 17%``` of the normal difficulty which is only 1.7% of the correct difficulty if they have 10x the normal hashrate. By limiting the drop to 16% per block, difficulty will get down to 43% instead of 17%. A tighter limit of +/- 12% instead of 16% may be good (69% would be the low). This is with bitcoin's 2-hour limit. I think BTCG has copied Zcash so maybe it is reduced to 1 hours. The +/- 12% is stricter than a 1 hour limit, so changing from 2 hour to 1 hour will help at a limit like +/- 16%, but not make a different at +/- 12%. A 1 hour limit on time with no other limit would allow a timestamp attacker to get difficulty down to 61% which is why I said the +/- 12% in allowing 69% drop is stricter (better). The two don't combine to help. Using the MTP like Zcash and probably BTCG does prevents < 50% miners from manipulating the timestamp. But it makes the difficulty 5 blocks slower in responding. There is a fix to this that would require more code changes. See my [Zawy v6](http://zawy1.blogspot.com/2017/07/best-difficulty-algorithm-zawy-v1b.html) I'll show the +/- 12% (or 16%) does not prevent the N=40 from responding as fast as it can. ( I'm going to edit my previous post to recommend 12% instead of keeping the 16%. ) Let's say an attack has 10x the normal hashrate. With N=40, the avg time it takes the difficulty to completely respond to meet the challenge is 40 blocks. So it will rise, on avg, this much per block: 10^(1/40). In my testing, it appeared a limit on the rise equal to 10^(2/40) = 12.2% was only reached about 10% of the time. I don't expect BTGC to experience a 10x "attack" very often so 12% with N=40 seems correct. Another way to reduce the effect of timestamp manipulation is to limit how far the next timestamp can be from previous timestamp. I've found a good choice to be +/- 6*T from where you expected the solve to occur and where T = 600 seconds for BTCG. You expect the solve to be 600 seconds from previous timestamp, so you would limit the timestamps to 600 +/- 3600 the previous timestamp. This allows timestamps to be out of order which is important in Zawy v6, but if BTCG does like Zcash and uses the MTP protection / delay AND the nodes are enforcing the +3600 limit based on real time instead of comparing to the previous timestamp, then you can set the minimum to 1 second after the previous timestamp. Otherwise, without the nodes enforcing a real UST time limit, a miner with with >20% hashrate could drive difficulty to "0" in a few hours or days if a "negative" timestamp from previous one is not allowed even if using MTP and a 3600 forward time limit.

Without nodes enforcing real time and letting miners set the time, any >50% attacker can drive difficulty to zero with any algorithm. BTW if you have a real time available to nodes, you do not need consensus (i.e. POW mining) because you could create a synchronous deterministic network which does not have the Byzantine of FLP problems.

The +/- 6*T limit works out to be about the same as the 10^(2/N) limit. They overlap, so it is not an additive benefit.

I tried many different schemes for difficulty such as a dynamic averaging window, least squares fitting, and most-recent-block-more-heavily-weighted. Nothing worked better than simple:
```next_D=avg(past N D) * T / avg(past N solvetimes) / (1+0.67/N)```
with the two options for solvetime limits above (+/- 3600 on each solvetime or X^(2/N) and X^(-2/N) on the average, where X is the expected max hash attack size as a multiple of baseline hashrate). The (1+0.67/N). Note that ```next_D= sum(N D's) * T / [max timestamp - min timestamp]``` as is usually used is not as accurate if timestamps are being manipulated. The implied N's in the denominator of my averages will not cancel during a manipulation as this alternative equation assumes .

Difficulty has a seductive illusion of being "improvable". Any "fix" that tries to predict attacker behavior without employing a symmetrical "fix" to counter him acting exactly the opposite (and everywhere in between) will leave an exploitable hole or cause an undesirable side effect. Any fix that is symmetrical is limited in scope before it has undesirable side effects. We want fast response to changes in hashrate and a smooth difficulty when hashrate is constant. My best theoretical approach was a dynamic averaging window in Zawy v2 that triggers on various measures detecting a change in hashrate. For complex reasons, this still does not do better than simple average.

========
post to Zcash github:

Any upper limit you apply to timestamps should be reflected in a lower limit. For example, you could follow the rule that the next timestamp is limited to +/- 750 seconds from the previous timestamp +150 seconds (+900 / -600). If you don't allow the "negative" timestamp (-600 from previous timestamp) AND if miners can assign timestamps without a real-time limit from nodes, then a miner or pool with > 20% of the network hashrate can drive the difficulty as low as he wants, letting everyone get blocks as fast as he wants, in less than a day.

A symmetrical limit on timestamps allows honest miner timestamps to completely erase the effect of bad timestamps. ( You do not need to wait 6 blocks for MTP like Zcash does in delaying the use of timestamps for difficulty, see footnote. ) If you allow the symmetrical "negative" timestamps, you do not need nodes to have the correct time with NTP or GPS unless miners collude with > 51% agreement on setting the timestamps further and further ahead of time to drive difficulty down. It's a real possibility if miners decide they do not like a certain fork due to not providing them with enough fees.

But if you do not allow the apparently negative solvetimes, you better do like ETH and depend on 3rd parties for your node times in order to limit how low a timestamp manipulator can drive your difficulty.

But if your nodes have an accurate time, you do not need mining. The only fundamental reason for mining is to act as a timestamp server to prevent double spending. If you have an accurate time on all nodes, then you can make it a synchronous network to eliminate the need for consensus to eliminate the need for byzantine protection via POW.

BTC and ETH depend on nodes to limit the future time assigned to blocks. Zooko was the only one here who seemed to know there is something wrong about strong reliance on nodes having the correct time. The extent to which BTC and ETH need those forward-time limits to be enforced by real time is the extent to which they do not need mining.

Footnote:
MTP does not stop a 25% attacker who can set timestamps > 4 blocks ahead if other miners are not allowed to assign a "negative" timestamp to eliminate the error in the next block. But if you allow the "negatives" then MTP is not needed. Putting your tempering aside, this assumes you use

next_D = avg(D's) * T / avg(solvetimes, allowing negative solvetime)
instead of

next_D=sum(D's) * T / [max(Timestamps) - min(Timestamps) ]
because the N's of the denominator and number of the first equation do not cancel like you would think and hope (in order to use the second equation) when there are bad timestamps at the beginning and end of the window. With the MTP, your difficulty is delayed 5 blocks in responding to big ETH miners who jump on about twice a day. That's like a gift to them at the expense of your constant miners.

Also, your tempered N=17 gives almost the same results as a straight average N=63. I would use N=40 instead, without the tempering. It should reduce the cheap blocks the big ETH miners are getting.

Your 16% / 32% limits are rarely reached due to the N=63 slowness. This is good because it is a symmetry problem, although it would not be as bad as BCH. Use "limit" and "1/limit" where limit = X^(2/N) where N=63 for your current tempering and X = the size of the larger ETH attackers as a fraction of your total hashrate, which is about 3. This allows the the fastest response up or down at N for a given X with 80% probability. Change the 2 to 3 to get a higher probability of an adequately-fast response. The benefit is that it is a really loose timestamp limit on individual values, as long as the aggregate is not too far from the expected range.