Closed ignopeverell closed 7 years ago
ummjackson
commented
7 years ago We ended up going with a slight variation on DigiShield back in the day for Dogecoin: https://github.com/dogecoin/dogecoin/commit/8da45ed40ba5ce2bc5e52f125dbc0a146c0e2a79#diff-305a16b05c141aa11176807bc4726611R33
ignopeverell
commented
7 years ago DoggieShield, cool. Had any gripes with it? Noticed large spikes when larger miners would move in or out?
ignopeverell
commented
7 years ago After some review, all difficulty algos are fairly similar:
ummjackson
commented
7 years ago Break down sounds on point @ignopeverell... as for DigiShield in Doge I don't think we've had any issues but I'm honestly not sure how it works with regards to AuxPoW. Let me ask for the core team.
ignopeverell
commented
7 years ago Thanks for chiming in and let me know what Doge core comes back with.
In the meantime, it seems the Digishield+GravityWave approach chosen by Zcash is the most pragmatic. Averaging difficulty over last N blocks limits spikes and taking medians to calculate the elapsed time prevents time warp attacks. Dampening leads to smoother variation and less signal truncation from the bounds. A larger N has roughly the same effect as a shorter one with dampening, except the shorter one favors recent data.
There an interesting variation in AntiGravityWave on Viacoin where instead of a simple targets average, it's a moving average with less and less importance given to older blocks:
https://github.com/viacoin/viacoin/blob/473e3cbb4f6c295da3f5f65fb5c9718b38a5e8f5/src/pow.cpp#L112
Going past 72 blocks however seems overkill, as the last one will only count for 1/72 and will be negligible.
ignopeverell
commented
7 years ago Actually scratch my last, the moving weighted average comes from DarkGravityWave. Looks like AntiGravityWave just fixed the off-by-one bug on CountBlocks and adjusted the bounds to factors of 2 instead of 3.
ignopeverell
commented
7 years ago Thought about this for some more time. Now I understand why there's so little research on this topic: a good algorithm has to identify whether a series matches a Poisson distribution over a very small sample size. Something that no self-respecting researcher would want to do. I suspect one could train a neural network to take fairly good decisions on target adjustments. Definitely overkill.
So here's what I think we'll keep:
I don't think we should keep the moving weighted average. The error in approximating the ideal distribution is the same over the whole period and the moving window N already truncates older results.
EdgarCloggs
commented
7 years ago Hi Igno et al.,
How bad of an idea is it to utilize several difficulty adjustment algorithms? This gives us a chance to utilize the outputs of each to come to more complete agreement on increase/decrease in difficulty?
Adjustment Algorithms (A, B, C, D) modified to take in n (number of last blocks to evaluate) as aparameter: A = Dark Gravity Wave B = Bitcoin's Standard Difficulty Algorithm C = Digishield/Dogeshield D = Our own Difficulty Adjustment Algorithm
Every 23 Blocks Calculate Difficulty: 1) Produce a difficulty Increase/Decrease taking into account last 23 Blocks
My thinking is if we can produce several difficulty increase/decrease averages over several different block ranges with multiple algorithms. It would allow us to pick a better value for difficulty increase/decrease. In the above scenario we produce difficulty adjustments using ~ 4 different timescales, at each timescale we then calculate an average increase/decrease using 4 different algorithms and return it for later processing. After each of the timescales is calculated and averaged, we can take the averages derived from looking at ranges: 23, 230, 2300, and 23000 then use these averages to calculate a better difficulty change i, if i is a decrease greater than 33%, i = 33% decrease, if i is an increase greater than 16% i = 16% Increase
The main downside I see, other than this being more code to maintain is that the difficulty readjustment calculation would be magnitudes slower when compared to just having one Difficulty adjustment algorithm produce a difficulty over only a single range.
Cheers, Edgar
legerde
commented
7 years ago If I am overstepping my bounds, please let me know.. I come from the aerospace industry. I've meant to write a detailed whitepaper on my idea for difficulty adjusting but I haven't. I'll outline briefly here. I dont expect anyone to want to use this idea, but I would love to implement it.
The algorithm deduces a statistical profile / normal distribution. Given this normal distribution, if you have an unusually fast black, or slow block, you can tell the "probability" that it was actually a hash power increase, or just a statistically abnormal block. These statistical gaussian distributions are able to be used to compute current difficulty, and rate-of-change of difficulty (2-state kalman filter). They are also hard to fool, because if hash power has a large step-function response, it can respond to that (in both directions) using statistically significant metrics.
Kalman filters are an entire field in and of itself. Anyone wanting to learn a bit about them can check out this wonderful online book (Chapter 4 is a good place to start): https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Python/blob/master/04-One-Dimensional-Kalman-Filters.ipynb
Thank you all for the work you are doing. I am excited about the future.
On Mon, Jun 19, 2017 at 1:29 PM, Edgar Cloggs notifications@github.com wrote:
Hi Igno et al.,
How bad of an idea is it to utilize several difficulty adjustment algorithms? This gives us a chance to utilize the outputs of each to come to more complete agreement on increase/decrease in difficulty?
Adjustment Algorithms (A, B, C, D) modified to take in n (number of last blocks to evaluate) as aparameter: A = Dark Gravity Wave B = Bitcoin's Standard Difficulty Algorithm C = Digishield/Dogeshield D = Our own Difficulty Adjustment Algorithm
Every 23 Blocks Calculate Difficulty:
- Produce a difficulty Increase/Decrease taking into account last 23 Blocks
- e = (A(23) + B(23) + C(23) + D(23))/4
- Produce a difficulty Increase/Decrease taking into account last 230 Blocks
- f = (A(230) + B(230) + C(230) + D(230))/4
- Produce a difficulty Increase/Decrease taking into account last 2300 Blocks
- g = (A(2300) + B(2300) + C(2300) + D(2300))/4
- Produce a difficulty Increase/Decrease taking into account last 23000 Blocks
- h = (A(23000) + B(23000) + C(23000) + D(23000))/4
- i = (e+f+g+h)/4
- i > 33% Down i = 33% adjustment Downward
- i > 16% Up i = 16.6% adjustment Upward
My thinking is if we can produce several difficulty increase/decrease averages over several different block ranges with multiple algorithms. It would allow us to pick a better value for difficulty increase/decrease. In the above scenario we produce difficulty adjustments using ~ 4 different timescales, at each timescale we then calculate an average increase/decrease using 4 different algorithms and return it for later processing. After each of the timescales is calculated and averaged, we can take the averages derived from looking at ranges: 23, 230, 2300, and 23000 then use these averages to calculate a better difficulty change i, if i is a decrease greater than 33%, i = 33% decrease, if i is an increase greater than 16% i = 16% Increase
The main downside I see, other than this being more code to maintain is that the difficulty readjustment calculation would be magnitudes slower when compared to just having one Difficulty adjustment algorithm produce a difficulty over only a single range.
Cheers, Edgar
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/ignopeverell/grin/issues/62#issuecomment-309544551, or mute the thread https://github.com/notifications/unsubscribe-auth/AAMvocjpi4zeB7qm-uGSKlsQIX-3b-zfks5sFswSgaJpZM4N7vVX .
ignopeverell
commented
7 years ago @legerde if you're willing to try implementing it and compare against the current algorithm when exposed to a Poisson distribution of block time with wide variations due to miners coming in and out, I'd be be at the very least interested in seeing the results. But not promising anything on adopting it.
daira
commented
7 years ago I and @str4d designed/implemented the changes to the difficulty adjustment for Zcash. So, I may be biased, but I've been extremely happy with how that algorithm worked out in practice. The Zcash block time is as close to target as you could reasonably expect, modulo variation that seems reasonable for a Poisson distribution offset by propagation time, and it has been pretty robust against various attempted timewarp attacks and against coin-hopping behaviour by miners.
The parameters in https://github.com/ignopeverell/grin/issues/62#issuecomment-308924422 seem reasonable. The window should probably be larger than ours given your shorter target block time (1 min vs 2.5 min if I understand correctly); I'd consider making this larger than 23 blocks.
There are two other changes I would consider making to the algorithm with the benefit of hindsight:
Just after launch the adjustment was a little slow to keep up with the very large increases in hash power coming online at that point, resulting in a faster-than-target mining period for (I can't remember exactly, but probably) a few hours. We predicted this, and it didn't have any long-term negative effect to speak of, but a few things could be done to mitigate it for a new coin. For instance, the difficulty of the Zcash genesis block was too low, and that was a significant factor in the adjustment taking a while to catch up. Also consider having a period of zero mining rewards (not low rewards as Zcash had; that didn't help the excessive price speculation), in order to shake out bugs and allow mining power to come online more gradually while reducing perception-of-losing-out. (But don't increase the adjustment bounds to try to allow faster adjustment; that led to some oscillation in our simulations.)
There is more that could be done to resist timewarp attacks. We retained the 1-hour limit on future-dated (relative to local clock) block times from Bitcoin, and should have decreased that significantly. We had a large miner exploit future-dating of timestamps right up to the 1-hour limit for a while; they stopped (I think because they realised it wasn't actually helping them much), but it is still undesirable to allow this if there are any features that expose timestamps.
daira
commented
7 years ago Also: I believe that combining algorithms as https://github.com/ignopeverell/grin/issues/62#issuecomment-309544551 suggests, does not help. It makes the combined algorithm more difficult to analyse and increases the risk of bugs, without significantly improving stability or attack-resistance. Admittedly, that's just my opinion and not based on empirical observation (you don't get enough chances to test out algorithms on mainnets of real coins to make such observations, unfortunately).
ignopeverell
commented
7 years ago @daira thank you very much for dropping by and sharing lessons from your launch, that's really appreciated!
Our block time is still under discussion, @apoelstra would prefer something longer I believe, so the constant of 23 could still change. But thanks for pointing that out, I'll keep in mind it will need to be adjusted.
Regarding difficulty adjustments at the start of the chain, the genesis block may not have a lot of impact as we default on returning the min difficulty for the first 23 blocks (as we don't have enough data to feed the algo). Maybe we could differentiate the min difficulty from the difficulty returned when there isn't enough data (which would be higher).
The zero reward period suggestion is interesting, how would you get away with the absence of coins to test transactions? Just grant the genesis block reward to a developer? Did you get any longer-lasting negative impact from the relatively high mining power coming online so quickly?
Also good point about future-dated blocks. We limit it at 12 block intervals, so 12 min at our current block time. I'm hoping that's a sane enough value.
Finally, I agree with you about combining algos, it just seems like unnecessary complication.
zawy12
commented
7 years ago Karbowanek and Sumokoin came across my comments at Monero that were the result of work I did on Zcash. They were having big problems with Cryptonote having such a large window of N=300. Implementing the simple routine I wanted Zcash to follow more closely solved their problems. I see Zcash had problems from not following my final recommendations. I tried to get them to go to a smaller window to prevent the first problem Daira mentions above. I don't know why they got oscillations (and were still getting them after release) but it may be from not having symmetrical allowed increase and decrease, or by using median instead of average. (average handles forward timestamps fine if there are symmetrical +/-30% to 50% limits on next_diff because the next block with an equally large negative value corrects the bad timestamp) I also recommended that they reduce the amount of error allowed in timestamps (the 2nd problem). I made enough mistakes in my initial posts that I'm sure they were tired of sifting the good from the bad in my posts. For example, the SQRT avg(D)/avg(T) is smoother, but it gets left behind with a hashrate that continually increases, so that was a bad idea.
After much more work on it recently with Karbowanek, I specified more clearly what it should be to protect small coins and calling it "zawy v1b difficulty algorithm":
I've also settled on N=12. But it's possible N=8 is best for small coins.
I tried all kinds of other possibilities and it shows I was not able to find something better. This included dynamic averaging window, a method using discrete hashrate measurements that allowed avg(D/T) based on the probability distribution instead of the simple avg(D)/avg(T), and a method to trigger to smaller window if post-attack was detected to get difficulty down. This last one does not help more than v1b with small N because of timestamp manipulation. I also tried measuring the slope and using least squares curve fitting to predict what the next diff should be, but they did not help. FWIW, the hashrate based on a single measurement is approximately D/T * (1+ln(2))/2 due to the median of Poisson being ln(2)=0.693 of the mean. Also, despite my comments last year, "timewarp" as it was meant in bitcoin is not possible when the windows have a rolling average.
My first post in the thread gives a general overview of the problems. Other posts in that thread calculate how many blocks hash-attacks get for "free", explain why anyone with >60% can make difficulty go to zero in a few hours (unless the stars or other oracle are used as a timestamp), and why you should not make your increase rate be anything other than the inverse of your decrease rate.
Here is a script in that thread to determine if a coin has been subject to hash-attacks by block-exploring the JSON output of the [coin]-cli program.
There is a routine to that you should use to measure the success of a difficulty algorithm.
zawy12
commented
7 years ago @legerde I tried what you're describing because avg(D) / avg(T) method used everywhere is not mathematically equal to the desired avg(D/T). But a straight avg(D/T) gives terrible results due to it being a Poisson. So I derived the equation based on the probabilities and my result is here. I call it a "discrete-based average" or "avg of the linearly mapped D/T's". There should be something wrong with my derivation because the "unmapping" factor was supposed to be ln(2) = 0.693 but to get a good average and median it needed to be fudged to 0.625 but I believe the correct derivation will not change things much. It was about the same as the regular average when the avg has ~25% higher N. This method had about 2% improvement in std dev and median, but the same improvement is seen with a larger N for the simple avg. It is interesting it could do the same thing as the avg with a smaller N, but I could not find a way to capitalize on it.
I tried detect and respond to step functions when looking at 1/2 N blocks for an increase or decrease from previous 1/2 N, and it works great when the attack is >N. The problem is that attacks like to last N/2 (before difficulty rises) and the results are worse than leaving it alone. Checking N/4 blocks compared to the previous N/4 blocks works great. Any attacks are going quit after ~N/8 blocks, or definitely by N/4 blocks. It is more unstable during constant hashrate, jumping up 3x on occasion for 1 block. You can lower this only by sacrificing the ability to detect a hash rate change. The trade off is so equal and opposite that it measures all the same as just using N/2 blocks as your window and leaving it alone. N/2 also will have a lower std dev when hash rate is constant, so it's better.
Any attempt to adjust based on a portion of the N blocks increases the amount of damage a timestamp manipulation can do, but when combined with a limit on the rise and fall in the difficulty per block the damage is erased in the next block (when using averages). If two blocks forward stamped blocks in a row come in often, then they have more than 50% and this ruins both median and average methods, driving difficulty to zero if they wish.
@ignopeverell It can be rough-checked to see if it is following Poisson by seeing if std dev = mean and if median = 0.693 of the mean. The avg(D) / avg(T) method gets ~ correct median (0.693 of average) but results in a few percent longer average solvetime. The average solvetime can be corrected (at a small cost to the median accuracy) by dividing by (1+0.67/N). The way Zcash uses a median appears to have a similar corrective effect. The std dev is around 7% above the expected std dev = mean for Poisson. In short, the usual method is pretty darn close to resulting in a Poisson distribution of solve times. I checked the Zcash's distribution and it followed a Poisson. After much effort, I've decided there is no solution for protecting against hash attacks other than going to smaller window which causes a larger variation in solvetime (15% too-high std dev at N=8 verses 7% too-high at N=17).
LONG story short: use nextD=Target *avg(D) / avg(solvetime). Specifically my Zawy v1b:
next_D=TargetInterval * avg(past N D's) / [ max(past N timestamps) - min(past N timestamps) ]
edit: correction: do not use the equation above. see post below.
N=8 for really small coins, N=17 for medium size coins
don't use medians, use 1/(1+0.67/N) factor to adjust next_D
allowed rise and fall: symmetrical with 2x and 0.5x of previous_D
allowed timestamps: +10xTargetInterval and -9x from previous timestamp unless N <12 then +0.8*NxTargetInterval and 1 minus that for the allowed negative. Minus two can be argued, but I want to be sure the negative stamp can erase the overly positive one.
one more thing: next_D=1.2*previous_D if next_D < 0. This can easily happen if someone send a large negative timestamp
ignopeverell
commented
7 years ago @zawy12 is the window size block time dependent? Or the block time doesn't matter?
zawy12
commented
7 years ago TargetInterval of blocks in seconds doesn't matter at all. [ edit: I was completely wrong in this statement]
zawy12
commented
6 years ago @ignopeverell I was mistaken to say TargetInterval has no effect. The algorithm is choosing a balance between fast response and not too much random variation. Miners are motivated by Price/Difficulty ratio. Price changes in real time and we want a fast response to it. So if I'm trying to balance this fast response with random variation, time becomes a factor. I wrote an article trying to determine what the relationship is. Approximately, it is like this:
new_N = old_N * (old_T / new_T) ^0.5
tromp
commented
6 years ago It's interesting to compare our Difficulty Adjustment (DA) with that of ZCash [1] and Bitcoin Cash [2].
| Coin | ZCash | Grin | BCash |
|---|---|---|---|
| Blocktime | 150 | 60 | 600 |
| Window | 17 | 60 | 144 |
| MedianOf | 11 | 11 | 3 |
| DAMP | 4 | 3 | 1 |
| AvgOf | Target | Diff | Diff |
| Diff&TS | async | async | sync |
In Zcash, the TS window can be wildly out of sync with the Difficulty window. It considers difficulties from blocks -17..-1, but could pick timestamp from blocks -27 and -11. BCash first picks the median timestamps, and then picks the blocks between them. Considering that dampening is a mild complication, do we have evidence that it performs noticeably better than not dampening?
[1] page 42 of https://github.com/zcash/zips/blob/master/protocol/protocol.pdf [2] https://medium.com/@Mengerian/dgenr8s-difficulty-adjustment-algorithm-explained-e77aa47eb281
zawy12
commented
6 years ago The Zcash/Digishield dampening performs a lot better than simple moving averages. It has longer delays than EMA and LWMA. It beats EMA in stability which reduces accidentally low occurrences that attract temporary increases in hash rate which results in delays when the "attackers" leave. Even with fewer attacks, it ends up having more total delays than EMA. LWMA ties Digishield on stability while having 1/2 as many delays. This is based a process: Normalize their "N" parameter until they all have the same response to 2x to 5x attacks that last from 10 to 30 blocks (very typical of what Zcash and other coins see). I average the values they have at the end of the step function to make sure it is about the same value. Any of them can be faster or slower based on the N. Speed comes at a price of stability. You get speed proportional to 1/N and stability with SQRT(N). Then, to check overall performance, I model real attacks that being when difficulty is 0.7 to 0.95 of the baseline difficulty. The attacks can be 2x to 25x hashrate which occurs in small coins. The attack lasts until the difficulty reaches 1.1 to 5x the baseline difficulty. I have metrics that measure delays and "blocks stolen at low difficulty", which ranks the results. This turns out to be the same as the winning algo having the lowest root-mean-square of the error between where the difficulty should be based on the hash rate and where the difficulty is. And for a given speed of response, the winner can be identified apparently just as well by just choosing the one with the lowest standard deviation when the hash rate is constant (since it drops lower less often, it will attract fewer hash attacks and therefore score better). I remove the 5 or 6 block delay Zcash code has so that the Digishield algo has a fair chance of winning. I cover these algorithms at the links below. A comparison is made in the LWMA link.
Digishield, SMA, and harmonic SMA LWMA (9 Monero clones, BTG and Bitcoin Candy will be using it) EMA Simple EMA math discussion EMA PID controller (No real benefit) Handling Bad timestamps Selecting best N
zawy12
commented
6 years ago Despite some of my critical and errant comments above (last August, before I learned a lot more), Zcash's version of Digishield is a lot better than SMA and the N=17 was very well chosen for T=150 second blocks. Twice as many delays sounds bad, but getting the right N value as a balance between stability and speed makes it not too far from the best that can be done. Only a major change such as Andrew Stone's reduction of difficulty during long solvetimes and recent Bobtail research (including 5 to 40 solves in header of each block to greatly narrow solvetime range) can do better.
Although Monero and BCH's 24 hour window for SMA looks nice and smooth and they have not had bad delays, it's not optimal and a graveyard of Monero clones from hash-attacks show it's a really bad idea unless you are nearly as big as the biggest coin for a given POW. But I don't think a coin's stability should be relying on maintaining that position when it doesn't need to.
zawy12
commented
6 years ago The reverse process for objectively determining the best algorithm can be used: Adjust their N parameter until the competing algorithms have the same StdDev when the hash rate is constant. The one with the fastest response to the "hash attacks" you expect is the winner, which is LWMA with Digishield again tying for 2nd place with EMA and clearly beating SMAs, even with the SMA is done correctly in terms of target instead of difficulty (harmonic mean of difficulties). For whatever reason, the proper SMA is
target = avg(target) * avg(solvetime) / T
which is not the inverse of the typical SMA because avg(D) != 1/avg(target)
But harmonic_mean(D) = 1/avg(target)
The reason SMA is not good is because it is getting the avg hashrate as it was N/2 blocks in the past, while EMA and LWMA are estimating current HR. Digishield is not quite as good because it's tempering it's calculation of 17/2 blocks in the past, but a lot better than SMA because an equivalent-speed SMA is N = 4x17 = 68 which is 34 block behind.
Current one is a little too lightweight. Zcash has gone through a fair amount of analysis:
https://github.com/zcash/zcash/issues/147
They ended up going with a heavily tweaked version of Digishield, with tuned up parameters. Viacoin also has an interesting improvement over DarkGravityWave:
https://github.com/viacoin/viacoin/blob/master/src/pow.cpp#L80
We should shamelessly port an existing algo instead of re-inventing the wheel.