SMA, H-SMA, and Tempered-SMA (Digishield)

[zawy12]

[ Edit: This article is a little dated. I now have all the equations in integer format and the solvetime limits limits should be -FTL and +6 (instead of +7 and -6) where FTL = future time limit nodes allow blocks to have and is 3xT as described on the LWMA page. Otherwise there is a timestamp exploit by > 50% miners that can greatly lower difficulty. ]

The simplest algorithm is the Simple Moving Average (SMA)::
next_D = avg(D) * T / avg(ST)
where D and ST are N of past difficulties and solvetimes. The N in the two averages cancel which can code and compute a little more efficiently as:
next_D = sum(D) * T / sum(ST)
Sum(D) is just the difference in total chain work between the first and last block in the averaging window. Sum(ST) is just the difference between the first and last timestamp. This is the same as finding your average speed by dividing the change in distance by the change in time at the end of your trip. I do not use this sum() method because it allows a bad timestamp to strongly affect the next block's difficulty in coins where future time limit is the normal 7200 seconds, and if T=120 and N=60 (in many of them).

The SMA is not very good because it is simply estimating the needed difficulty as it was N/2 blocks in the past. The others try to more accurately estimate current hash rate.

For whatever reason, using the average of the targets instead of the difficulties gives a more accurate avg solvetime when N is small. Since you have to invert the target to get the difficulty, this is the same as taking the harmonic mean of the difficulties.

# Harmonic mean aka Target SMA method
next_D = harmonic_mean(D) * T / avg(ST) 
# or
next_D = max_Target/avg(Target) * T / avg(ST)
# or 
next_Target = avg(Target) * avg(ST) / T

max_Target = 2^(256-x) where x is the leading zeros in the coin's max_Target parameter that allows difficulty to scale down.

The best way to handle bad timestamps without blocking reasonably-expected solvetimes requires going through a loop to find the maximum timestamp. There are other ways to deal with bad timestamps, but this is the best and safest.

SMA

# SMA difficulty algorithm (not a good method)
# This is for historical purposes. There is no reason to use it.
# height-1 = index value of the most recently solved block

# Set param constants:
T=<target solvetime>
# For choosing N and adjust, do not write these equations as code. Calculate N and adjust,
# round to integers, and leave the equation as a comment.
# N=int(40*(600/T)^0.3)
# adjust = 1/ (0.9966+.705/N) # keeps solvetimes accurate for 10<N<150

for (i=height-N; i<height; $i++) {
   avgD += D[i]/N; 
   solvetime = timestamp[i] - timestamp[i-1]
   avgST +=solvetime/N
}
next_D = avgD * T / avgST * adjust

# I've used avgD and avgST for math clarity instead of letting N's cancel with sumD/sumST

Harmomic SMA

# H-SMA or Target-SMA difficulty algorithm
# Harmonic mean of difficulties divided by average solvetimes
T=<target solvetime>
# Calculate N round to an integer, and leave the equation as a comment.
N=int(40*(600/T)^0.3)

# height-1 = index value of the most recently solved block
for (i=height-N; i<height; $i++) {
   sum_inverse_D += 1/D[i]; 
# alternate: avgTarget += Target[i]/N;
   solvetime = timestamp[i] - timestamp[i-1]
# Because of the following bad timestamp handling method,  do NOT block out-of-sequences 
#  timestamps. That is, you MUST allow negative solvetimes.
   if (solvetime > 7*T) {solvetime = 7*T; }
   if (solvetime < -6*T) {solvetime = -6*T; }
   avgST +=solvetime/N
}
harmonic_mean_D = N / sum_inverse_D
next_D = harmonic_mean_D * T / avgST * adjust
# alternate: next_Target = (avgTarget * avgST) / (N*N*T)  # overflow problem?

Digishield v3

Digishield v3 has a tempered-SMA that works a lot better than simple SMA algos .... provided the 2 mistakes in Digishield v3 are removed (remove the 6 block MTP delay and the 16/32 limits). The tempering enables fast response to hashrate increases while having good stability (smoothness). Its drawback compared to the others is 2x more delays after hash attacks. Even so, it's response speed plus stability can't be beat by LWMA and EMA unless they use its trick of tempering. It cost them some in delays, but they still have fewer delays than Digishield. The root problem is that although Digishield uses a small N to see more recent blocks than an SMA, it's still not optimally trying to estimate current hashrate like LWMA and EMA. PID and dynamic versions of LWMA and EMA can also beat Digishield without copying it. But Digishield is not far behind anyone of them if stability is more important to you than delays.

# Zawy modifed Digishield v3's (tempered SMA)
# [edit this is very dated. New versions revert to the target method and does better timestamp limits. ]
# 0.2523 factor replaces 0.25 factor to correct a 0.4% solvetime error. Half of this
# error results only because I used a difficulty instead of target calculation which 
# makes it an average D instead of the more accurate average target (which is harmonic mean of D.)
# This algo, removes POW limits, removes MTP, and employs bad timestamp protection 
# Since MTP was removed.  Height-1 = index value of the most recently solved block

T=<target solvetime>
# Recommended N for balance between the trade off between fast response and stability
# If T changes away from Zcash's T=150, the stability in real time will be the same.
# N=17 for T=150, N=11 for T=600
N=int(17*(150/T)^0.3)

for (i=height-N; i<height; $i++) { 
   sumD += D[i]; 
   solvetime = timestamp[i] - timestamp[i-1]
   if (solvetime > 7*T) {solvetime = 7*T; }
   if (solvetime < -6*T) {solvetime = -6*T; }
   sumST +=solvetime
}
sumST = 0.75*N*T + 0.2523*sumST # "Tempering" the SMA
next_D = sumD * T / sumST  

I've tried modifying the tempering and I can't make it better. I've tried using the tempering in non-SMA algos but there was no benefit. I tried using harmonic mean of difficulties, but it did not help.

Tempered SMA similarity EMA

Re-arranging Digishield's math gives:
next_D = avg(17 D) * 4 / ( 3 + avg(17 ST)/T)
The EMA can be expressed in something that looks suspiciously similar. The exact EMA uses an e^x. But e^x for small x is very close to 1+x. This is actually a vanilla EMA that's not as exact. It parallels Digishield (but is substantially better:
next_D = prev_D * 36 / ( 35 + prev_ST/T)