-
Notifications
You must be signed in to change notification settings - Fork 25
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Ethereum's DA is very similar to EMA #45
Comments
zawy12
changed the title
Ethereum's difficulty algorithm is a messed-up EMA
How Ethereum messed up their difficulty algorithm
Jul 26, 2019
zawy12
changed the title
How Ethereum messed up their difficulty algorithm
how Ethereum almost had a -good difficulty algorithm
Jul 26, 2019
zawy12
changed the title
how Ethereum almost had a -good difficulty algorithm
how Ethereum almost had a good difficulty algorithm
Jul 26, 2019
zawy12
changed the title
how Ethereum almost had a good difficulty algorithm
How Ethereum almost had a good difficulty algorithm
Jul 26, 2019
zawy12
changed the title
How Ethereum almost had a good difficulty algorithm
Ethereum's difficulty similarity to EMA
Aug 17, 2019
zawy12
changed the title
Ethereum's difficulty similarity to EMA
Ethereum's DA is very similar to EMA
Aug 17, 2019
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This issue has been closed because of prior errors and the issue after this one replaces this article.
This link explains why ETH's difficulty algorithm is the way it is:
https://github.com/ethereum/EIPs/blob/master/EIPS/eip-2.md
In particular, they did not want the difficulty to precisely change with timestamp or miners would start (and did start) assigning lowest timestamp to get higher work. By lumping solvetimes into larger groups that have the same effect on difficulty, manipulation is reduced but not prevented. It stops the biggest problem which was all miners assigning a +1 second timestamp. Part of the problem is that it's looking at current solvetime instead of previous solvetime. That has good and bad effects as discussed in my TSA article. The bigger problem seems to be that the solvetime is too fast.
Ethereum's difficulty algorithm without the difficulty bomb is:
diff = parent_diff + parent_diff / 2048 *
max(1 - (block_timestamp - parent_timestamp) // 10, -99)
A stack exchange answer explains the above. See also my article on ETH's DA for a more detailed exploration.
If the integer division that makes fast solvetimes = 0 and if max is not used it is:
diff = parent_diff * (1 + 1/2048 - 1/10/2048 )
This is the same as the simplified EMA:
diff = parent_diff + parent_diff/N - parent_diff*t/T/N
where
t = parent solvetime
T = target solvetime
N = extinction coefficient aka "mean lifetime" aka number of block to "temper" or "buffer" the size of the response. It can't be too small or a negative difficulty can result from long solvetimes.
This is very close to the theoretically best algorithm which is an exponential moving average (EMA) that I and others have investigated. It's an approximation of the EMA by the taylor series expansion of the exponential function:
e^x = 1 + x + x^2/2! + ...
Where you use the approximation e^x = 1 + x in the EMA algorithm:
diff = parent_diff*( 1 - A + A*T/t )
where
A = alpha = 1-e^(-t/T/N)
See #17
This algorithm was discovered by Jacob Eliosoff who was already very familiar with EMA's for stock prices. He needed to modify it to fit difficulty, and the result turns out to be a known version that's mentioned in Wikipedia in regards to estimating computer performance:
https://en.wikipedia.org/wiki/Moving_average#Application_to_measuring_computer_performance
I say it's theoretically best because you can reduce N all the way down to "1" and the mean and median solvetimes are close to the expected T and ln(2)*T. So it's the best estimator (I know of) of guessing the current hashrate based on only the previous block.
In practice, miner motivation and the way the LWMA responds makes the LWMA a little bit better algorithm. And the EMA can't be used for Cryptonote coins because the timestamps are at the beginning of the block solve, not when the block was found, so there is a 1-block delay that causes substantial oscillations, especially if N is less than 100 in order to be reasonably fast.
ETH's DA has an average solvetime of 14.6 seconds, so to compare it to EMA, I use T=15.
The text was updated successfully, but these errors were encountered: