zawy12 / difficulty-algorithms

See the Issues for difficulty algorithms
MIT License
107 stars 25 forks source link

Review of Orbital Coin's OSS difficulty algorithm #28

Open zawy12 opened 6 years ago

zawy12 commented 6 years ago

These are my comments each section of Orbital coin's difficulty algorithm. I've simplified the code for readability. There's no missing code.

//  POW only 
//  #######  Begin OSS algorithm #########
nTargetSpacing = 360;
nTargetTimespan = nTargetSpacing * 20

nActualTimespanShort = timestamps[-1] - timestamps[-5];
nActualTimespanLong =  timestamps[-1] - timestamps[-20];

/* Time warp protection */
nActualTimespanShort = max(nActualTimespanShort, (nTargetSpacing * 5 / 2));
nActualTimespanShort = min(nActualTimespanShort, (nTargetSpacing * 5 * 2));
nActualTimespanLong  = max(nActualTimespanLong,  (nTargetSpacing * 20  / 2));
nActualTimespanLong  = min(nActualTimespanLong,  (nTargetSpacing * 20  * 2));

The above prevents it from changing very much if the last 5 or 20 blocks were 2x too fast, or 2x too slow. For N=5 or 20, this is not good. nActualTimespan limits should be to prevent big problems, but with N=5 and 20, it gets activated a low. It limits how fast the algorithm can change, especially during a hash attack. BCH uses the same 2x factor, but they have N=144 and more importantly they are a large coin with stable hash rate. So it will not get activated unless there is a catastrophic change. BTC uses 4x as protection for catastrophic situations, again with a much larger N=2016.

/* The average of both windows */
nActualTimespanAvg = (nActualTimespanShort * (20 / 5) + 
      nActualTimespanLong) / 2;

This above gives equal weighting to the short and long windows. This is good It's like a really mild form of LWMA. I show at the bottom that it's good, so this idea could be used in Digishield coins to improve them.

/* 0.25 damping */
nActualTimespan = nActualTimespanAvg + 3 * nTargetTimespan;
nActualTimespan /= 4;

This is Digishield's 75% dampening, not 25%. It is saying "we believe the previous difficulty was 75% correct and we'll give the recent timestamps 25% vote on what the next difficulty should be. It's better than simple moving averages, but not as good as EMA and LWMA.

/* Oscillation limiters */
/* +5% to -10% */
nActualTimespanMin = nTargetTimespan * 100 / 105;
nActualTimespanMax = nTargetTimespan * 110 / 100;

if(nActualTimespan < nActualTimespanMin) nActualTimespan = nActualTimespanMin;
if(nActualTimespan > nActualTimespanMax) nActualTimespan = nActualTimespanMax;

Since the above comes after the 75% Digishield dampening, it's like limits that are 4x these limits when expressed in terms of the previous 2x limits. That is, they are basically +20% and -50% limits, so it is overriding most effects the 2x limits had. I confirmed this by testing. This is not how you want to limit difficulty changes. There should not be any limits except for extreme circumstances, otherwise you could have used a larger N to get the same benefits with fewer problems. The +5% limit would have enforced a 0.2% rise per block during hash attack attacks, if the big error in the last line of this code were not in place. That error prevents this error from causing a problem. Start up is like a hash attack and it takes Digishield 500 blocks to reach the correct difficulty with a 16% limit where this one has 5%, so if it were not for the last line of code, it would have taken Orbitcoin 1500 blocks. See this for a detailed review of the problem.

Making it asymmetrical with +5% and -10% instead of +10% / -10% causes two other problems. The first is that avg solvetime will be a little faster than target. The bigger problem is that it invites oscillations. It's slow to rise, so big miners stay on longer. It ends up with a longer delay which allows it to drop faster, especially since the larger limit is allowing it to drop faster. The extreme case was the fantastic failure of BCH's initial asymmetrical EDA. A milder case is what I allowed to happen to BTG by not removing the +16% and -32% limits from the Digishield code when i made it faster. These limits made it slower and with bad oscillations.

However these problems I normally expect from +5% and -10% limits did not occur in Orbitcoin because the of the next error. The combined errors gives significantly better results than either error alone, but still terrible results.

/* Retarget */
bnNew.SetCompact(pindexPrev->nBits);
bnNew = bnNew * nActualTimespan / nTargetTimespan;

//    ########   End OSS algorithm ###########

The above uses the previous target instead of doing like Digishield and using the avg of the previous difficulties. My testing indicates using the average of the past 20 instead of 1 or 5 is a LOT better. EMA is able to do this, but it's done in a very specific way.

The following code is what Digishield does, expressed to look like the OSS above. It's a lot simpler and gives a lot better results. I didn't include Digishield's limit because they are never activated except at start up where it causes a 500 block delay in coins reaching the correct difficulty. I've also removed the 6-block MTP delay.

nActualTimespan = timestamps[-1] - timestamps[-17];
nActualTimespan = ( nActualTimespan + 3*nTargetTimespan) / 4;
bnNew = Average_17_bnNew * nActualTimespan / nTargetTimespan;

The following compares OSS and this simplified version of Digishield/Zcash. Reminder: Digishield/Zcash is not as good as the Simple EMa and LWMA, especially with the MTP 6 that it normally has.

Constant hash rate OSS verses Digishield image image

Typical Hash attack OSS verses Digishield Digishield scores a lot better because it does not accidentally go low as often (which invites a hash attack) These are hash attacks based on simulation of miner motivation: they begin if D drops 15% below average, and end when it is 20% above average. These results are robust for a wide range of start and stop points.
image image

OSS worse WITHOUT the +5%/-10% limits This shows the results of OSS are worse if the 5%/-10% were not in place. image

Digishield worse WITH the +5% / -10% limits image

Digishield worse when using previous bnNew instead of avg image

Using OSS idea to improve Digishield The following is a modified Digshield using the 5/20 idea from OSS. I used 5/17. It is pretty much the same as Digishield, except with 1/2 the delays. If I lower the 17 to 14, it is very competitive to LWMA. It has fewer delays with slightly more blocks stolen, at the same speed of response and stability. image

Unified Equation for Difficulty Algorithms

next_D = avg(n Ds) *r / ( (r-1) + sum(n  w*STs)/sum(n w's)/T  ) 
r=1, w=1 is SMA
n=1, w=1 is EMA
w=1 is Digishield-type
r=1 is LWMA
all 3 variables are used OSS

w here is a weighting based on the n. Notice it's 1 for all but LWMA, which is a simple linear weighting, giving the more recent n's more weight. It can be added to code simply, but other weightings can't. Actually, this is an inferior form of the equation. It needs to be based on Targets.

next_T =  [(r-1) + sum(n  w*STs)/sum(n w's)/T]  / (avg(n Ds) *r)