Saturday, July 15, 2017

Best difficulty algorithm: Zawy v6

```# 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)
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];

```

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)

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.