A correction to BTC's difficulty algorithm about difficulty-algorithms HOT 7 OPEN

Even though I don't understand much. Thank you a lot for your time and effort to research and improve diff algo.

from difficulty-algorithms.

nice report. thanks!

from difficulty-algorithms.

Concerning Peter Wuille's post, here is the answer. Today, the parameter updating the difficulty is equal to n0*tau0 / (S_{n0-1}) with n0=2016, tau0=600 and S_n = time to mine n blocks. Let tau be the interblock time. Then 1/S_n follows an inverse Gamma process distribution with mean value 1/((n-1)*tau).

See : https://en.m.wikipedia.org/wiki/Inverse-gamma_distribution
Taking average, we see that the mean value of the parameter updating the difficulty is :
n0*tau0 / ((n0-2)*tau).

This quantity should be equal to 1. Otherwise, the difficulty would go to infinity or 0 almost surely by the strong law of numbers.

So,
tau = (n0*tau0) /(n0-2) = tau0 + 2*tau0 /(n0-2).

Finally, the time to mine n0 blocks is:
n0*tau = n0*tau0 + 2*tau0 +4*tau0/(n0-2)

The exact time to mine 2016 blocks in Bitcoin is: 2 weeks, 20 minutes and 1.19 seconds.

Note that if you want to get 2 weeks exactly, it is enough to take n0*tau0 / (S_{n0+1}) for the formula updating the difficulty.

However, this computation has been done assuming that all miners are honest (no selfish miner).

In fact, there is a flaw in the difficulty adjustment formula but it is not this one (replace S_{n0-1} by S_{n0+1}). The bug is that the difficulty parameter underestimates the true total hashing power of the network in presence of an attacker. According to me, it is the biggest theoretical flaw in Bitcoin.
We must count for orphan blocks. See our article where we explained that. Someone could write a BIP after reading it.

https://arxiv.org/abs/1805.08281

@CGrunspan

from difficulty-algorithms.

I found section 8 of the link to your research at the bottom very interesting (for others: his section 8 says miners should include orphan headers and difficulty is adjusted accordingly. The orphans show there is more network hashrate than normal difficulty calculates so normal difficulty algorithms have an error.)

Otherwise, the difficulty would go to infinity or 0 almost surely by the strong law of numbers.

Contrary to this statement, the law indicates it should only tend to the N/(N-2) error as we both conclude. Also, instead of taking too long, BTC is issuing blocks 6% too fast and LTC which does not have the 2016/2015 error is issuing blocks 2% too fast. I presume both are too fast because this is how much their hashrate is increasing per difficulty change, meaning the large error is due to the slow difficulty response.

Although I can't confirm your 2 eqs in the middle are algebraically correct, your initial equation and final statements are the same as my post.

from difficulty-algorithms.

I wrote: "This quantity should be equal to 1. Otherwise, the difficulty would go to infinity or 0 almost surely by the strong law of numbers."
You write : "Contrary to this statement..."
--> You have not understood my statement or may be, it's my english (sorry!). I never claimed that the difficulty will go to 0 or to infinity. On the contrary, it was a "Reductio ad absurdum".

Let d_n (resp. delta_n) be the n-th difficulty parameter (resp. difficulty adjustment parameter).

We have d_n/d_{n-1} = delta_n. So, if delta =E[delta_n] < 1 (Reductio ad absurdum), then we have by the inequality of arithmetic and geometric means (see https://en.m.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means):

d_n=dn/1 = \prod_{i=1}^n delta_i < (\sum_{i=1}^n delta_i/n) ^n

We have \sum_{i=1}^n delta_i/N - > delta <1 by the strong of numbers. So d_n-> 0.

This was just to justify E[delta_n] =1 used in the proof.

You write : "Although I can't confirm your 2 eqs in the middle are algebraically correct, your initial equation and final statements are the same as my post."
--> Is it the following equation that you don't understand?
tau = (n0*tau0)/(n0-2)

Here tau is the true mean interblock time. The equation comes from the fact that E[1/S_{k}] = 1/((k-1)*tau) since 1/S_k follows an inverse Gamma distribution with parameter (k, tau). See the link to Wikipedia I gave above. This implies :

E[n0 tau0 / (S_{n0-1})] =n0 tau0 E[1/S_{n0-1}] = n0 tau0 / ((n0-2) tau) which leads to
tau = (n0*tau0)/(n0-2)

from difficulty-algorithms.

This isn't a new error. It was known as early as 2016 (see https://arxiv.org/pdf/1708.05185.pdf).

from difficulty-algorithms.

Thanks for the correction. I'll update my writing.

from difficulty-algorithms.