mochimodev
commented
4 years ago This is a really good discussion, thank you. This sort of oscillation is referred to as "global synchronization" where states of congestion across an information system use naive pruning mechanics such that all participants in a resource-constrained system respond to the stimulus of increased competition for a resource at about the same time by drawing down their consumption of it, and likewise they increase their consumption when the resource is less constrained. In this case "block solves" are the consumed resource and difficulty represents the availability of the resource for modelling purposes.
Separately, I don't know if you are aware, but Mochimo uses a mid-block difficulty adjustment algorithm. I think you mentioned that no systems are using one, but ours is working extremely well, and we mint exactly 256 reward blocks per day as designed, and with very little drift.
In the previous issue BCH needs a new DA I discuss the source of oscillations in DAs. This details the source of those observations.
Summary: Simple Moving Average (SMA) difficulty algorithms cause dying oscillations in difficulty in response to sudden hashrate changes due to not taking the slope of solvetimes into account. Miner "momentum" or "friction" to joining and/or leaving (hysteresis) due to reward/difficulty ratio changes can sustain an oscillation who's size is related to the amount of momentum. The "momentum" in this context partly refers to the number of blocks delayed until a hashrate change, but is related more to the size of the hashrate change. A one-block delay with 5x hashrate change can sustain a sizable oscillation indefinitely, allowing the attacker to get lower-than-average difficulty. Profit margins due to better or worse reward/difficulty ratios can attract or dissuade an "exponential" (i.e. some non-linear function) amount of hashrate, so a 5x hashrate change is not unusual in small coins. The non-linearity in the relationship between hashrate and reward/difficulty is a major contributing cause of oscillations. Bad oscillations are caused in all algos if large miners stay on beyond the point that makes sense in terms of profit, and come back before it has dropped low enough for other miners to be interested. Bad oscillations are also caused by algorithms that do not use the most recent solvetimes in the averaging window, especially in SMAs. This causes positive feedback which can get the chain stuck as has happened in basically all Cryptonote/Monero clones that have a ~5% delay from "cut" and "lag". Forced delays can also cause mild oscillations in fast algorithms that are only partially a SMA (Digishield with a 6-block MTP delay, 10% of its 17x4 effective window). The oscillations in SMA's are a harmonic of the difficulty window averaging, cycling at 1x, 2x, or 3x the number of blocks in the window due to fast solvetimes rolling out the back of the window, canceling the effect of new fast solvetimes, keeping difficulty stable during a subsequent attack.
SMAs perpetuate oscillations in hashrate (aka on-off mining, aka hash-attacks) when there is non-dedicated hashrate available. If price suddenly rises there can be a large influx of hashrate. Hashrate is a nonlinear function of reward per difficulty due to a small increase in the ratio being a substantially larger profit margin. The converse applies if price falls. By not taking the slope of hashrate (usually by just looking at solvetimes instead of the more precise hashrate =1/avgTarget/avgSolvetime*(N-1)/N ) BTC & SMAs are estimating the hashrate as it was at the midpoint of their averaging window in the past. There's an inherent delay. If there is a substantial hashrate change the difficulty will reach the correct value faster than the difficulty window because the hashrate increase is more than linear. If hashrate increases were linear with the reward (in exchange dollars) per difficulty ratio, then it would take longer than the difficulty window and an oscillation would not occur. But since a large hashrate increase occurs, it reaches the "break even with other coins" ratio sooner. Digishield benefits from this effect by from being 4x slower than its averaging window of N=17. SMA & BTC reach break-even slowly, but not as slow as their full window from not taking slope into account, so miners have time to leaving without sending difficulty too high. By not taking slope into account, it almost can't overshoot unless a big miner has momentum for some reason and makes it overshoot, suffering a difficulty higher than is logically profitable, assuming he can switch coins easily & quickly. Algos with a slope adjustment must not overshoot on their own (EMA & LWMA do not), trying to predict miner behavior ahead of time.
Side Note: Momentum, Friction, and PID controllers in Difficulty
It should be assumed there is no momentum or friction in miner motivation (logical profit says there shouldn't be if he can change coins quickly... but often they do display momentum or friction i.e. they are slow to join or leave), so a PID or PD controller should not help because they are needed in cases of momentum and/or friction, and will cause oscillations if they assume there is momentum and/or friction when there is not (the D in PID is derivative aka slope and can have a constant that overshoots). Looking at recent past cycles to measure and remember momentum and friction and adjust accordingly seems like more complexity for DAs than should be used.....and opens a vulnerability: if it assumes or calculates miner behavior for the next few blocks and therefore responds ahead of time, miners will do the opposite to exploit it. But the fact that there is a kind miner momentum or friction or hysteresis in starting and stopping is the primary factor that causes oscillations in simple moving averages.
[newer comments on this: SMA is like an electronic circuit or rod being struck that has a natural frequency of oscillation. N=144 SMA has harmonics at 144, 72, 36 and even 18-block cycles at times. It does not "cause" oscillations any more than a rod causes oscillations in itself. The problem is that it does not stop ringing if "struck" with a price change or a big miner making a somewhat random decision to start or stop mining. It does not inject an assumption like feed-forward controller, try to predict the future ("D" in PID), or add "energy" like the "i" and "D" gain constants in a PID controller. It's passive. Price changes or miners inject the "energy" that causes it to ring.
RC filters seem like a good parallel to ASERT's "low-pass filter" parameter, but the math does not indicate a good parallel. Vout = Vin (1-e^(-t/RC)) instead of next_D = previous_D [e^(-t) / e^(-1) ]^(1/N) where N = mean lifetime = "RC". ( I've scaled t/T in ASERT to just a "t" in blocks unit and N is in blocks because R and C units are already scaled to its "t" seconds. )
end update ]
Getting back on track...
Continuing where I left off, let's assume we have the common situation where a fairly sudden and large hashrate increase (> 2x hashrate baseline) has increased difficulty to match an exchange price increase. Many of the original opportunists will leave as it rises because they typically have a default or preferred coin, so it can even out smoothly. But sometimes miners can have momentum to staying aka friction to leaving aka 1/2 of a hysteresis in reverting to their previous coin, causing it to overshoot which can begin an oscillation. But I'll assume that does not occur. Everything is fine until those fast solvetimes that mark the beginning of the hashrate increase start to roll out the back of the averaging window. Difficulty will start to drop despite it currently being at the correct level. To keep difficulty stable, miners would have to solve blocks just as fast as the original hash-attack, but they can't because difficulty is near the correct level instead of being way low, so it must continue drop,at the same rate it rose, if miners rejoin at the same rate they left. a symmetrical rise and fall like this without miner momentum will oscillate maybe only a little for one cycle and not be noticeable in the 2nd cycle (2x to 3x the window length). Miner momentum that lets difficulty rise or drop "too far" will sustained an oscillation that will be limited to the amount of the momentum. The momentum is a function of both the number of blocks delayed to a response, and the size of the response.
Sustained oscillations caused by momentum are exacerbated by the non-linearity of hashrate changes caused by slightly more (or less) profit being attractive to a LOT more (or less) hashrate). It is common in alts to see 3x more hashrate join when there is a 30% drop in difficulty, and it can go to 1/3 when difficulty is 30% higher.
The summary above mentions an algorithm may not look at the most recent solvetimes and this has the same effect of miner momentum, but unlike miner momentum instead of just sustaining an oscillation that is "proportional" to the momentum, it can draw in more hashrate with each cycle (positive feedback) by overshooting to the upside and downside until the chain is stuck. An algorithm that uses the slope can prevent that error from getting out of control. To explain this effect further: miner motivation that is delayed (the"delay to respond" part of their "momentum") is self-correcting: it will cause the difficulty to drop further in a cycle, but as it drops further, that delay is reduced due to desire for the higher profit. A fixed 10-block delay in what solvetimes are included will still be there no matter how low the difficulty drops, or rises.
BTC adjusting only once per 2016 blocks is a 1-week delay in measuring current hashrate, but it's not a delay that ignores the most recent solvetimes when it changes, so it does not amplify oscillations. It certainly is not as good as a simple moving average, but it also does not have the SMA effect of the previous attack's solvetimes rolling out the back of the window preventing difficulty from rising during a current attack. But it can definitely have an oscillation from the non-linear amount of hashrate that comes and goes in response to difficulty. It could perpetually overshoot and undershoot alternatively every 2016 blocks.
All these oscillations are only present when there is "non-dedicated" hashrate that can come and go, and usually requires > 2x the baseline hashrate for it to be noticeable.
This article was motivated by my recent observations of BCH. It is a good case study. The difficulty was not changing much (+/- 5%). The miners were not waiting for difficulty to drop much at all (small momentum). The hashrate changes were not super large (compared to small coins I deal with). They were "only" about 6x the average (about 12x the "dedicated" miners). So the delay*hashrate change factor for momentum was not really big. There is a forced delay in the algorithm that adds some positive feedback, but it's only 2 blocks on a window of 144 (1.5%), not like Cryptonote's 6% (~45 blocks on N=720). But BCH and Cryptonote are 24 hour windows. Really time has no effect in the math, but the number of blocks. But time has a big effect on the reward/difficulty ratio, so we can expect bigger prices changes per difficulty window size which kicks off the oscillations.
Update: When I wrote the above 3 days ago I could see the harmonics of BCH oscillations had an element of 3 cycles per 144 blocks, but the major swings were 2x per days. It looked like BCH was in serious danger. But then the 3rd harmonic got a lot bigger and seems to have helped reduce the other swings by "taking energy away from them". The following chart shows the 3rd harmonic clearly picking up and seeming to take some steam out of the others. Notice it is a log scale, so these are not minor swings.
The following chart with a linear scale and a longer averaging period to smooth things out shows how the severity of the situation was reduced.
This chart is from the summer shows only 1 cycle per 144.
I was able to partially model the 2nd harmonic BCH oscillations by specifying a miner motivation rule that said "if difficulty is <130% of what the baseline (dedicated) hashrate alone would have, then begin 8x hashrate, and stop when it is 132%. " Miners are probably joining and slowly than this simple on-off, which could be a way to model the 2nd harmonic better. The on-off miners get an avg difficulty 5% below avg while the other miners have to pay 5% above avg.
Using LWMA with the same miner motivation profile did not have any oscillations. This is not proof that 8x hashrate can't find a way to get unfair profit (compared to dedicated miners) out of LWMA, but the difficulty in doing so by modelling, and knowing Cryptonote's 24 hr avg was terrible, is why I've recommended it.