Recommended difficulty algorithm

[zawy12]

Dgenr8 emailed me for feedback. I emailed him my reasoning on why I think this simpler algo is the best. I've tested weighted solvetime methods and they seemed to be the same as just using 33% smaller window with a simple average. Also, he is using a type of avg(D/solvetime) instead of avg(D) / avg(solvetime). Those methods always gave me worse results. I've racked my brains for two months last year and 4 months this year on many ideas for improvement, but always came back to this.

# Zawy v6 difficulty algorithm
# see full discussion
# https://github.com/seredat/karbowanec/commit/231db5270acb2e673a641a1800be910ce345668a
# Commented version of this:
# https://github.com/seredat/karbowanec/commit/231db5270acb2e673a641a1800be910ce345668a#commitcomment-24807829
# D = difficulty, T=TargetInterval, TS=TimeStamp, ST=solveTime

T=600;
N=50;  # or 100 if you want it slower but smoother
X=10; # largest sudden hashrate multiple increases expected  
limit=X^(2/N); 

ST=0; D=0; 
for ( i=height;  i > height-N;  i--) { 
   ST += TS[i] - TS[i-1]; 
   D += D[i];
}
ST = T*limit if ST > T*limit; 
ST = T/limit if ST < T/limit; 

next_D = D * T / ST;

[dgenr8]

Copied from my response to Scott:

It seems crucial to me to use the D[i] in conjunction with the ST[i]. Every ST[i] carries information that should not be discarded or averaged out.

I think of the D[i] as modifiers to the ST[i]. We will be retargeting from D[144], but a minute spent hashing at a difficulty lower than D[144] is equivalent to some time shorter than a minute spent hashing at D[144]. And due to the properties of the exponential distribution, a simple multiplicative adjustment is correct.

ST[i] is used as if it was sampled from the block 144's distribution, when in fact it was mined at a different difficulty, so the adjustment is needed.

[zawy12]

You have a sum_i = N/2*(N+1) in tw-144. This comes from:

for i=1 to N
   sum_i += i
next i

I am reading tw-144 to be: [ edited to be correct ]

# tw-144 
#  ST=solvetime
N=144
sum_i = N/2*(N+1)
for i=1 to N+1 (from oldest to newest blocks)
  tw += ST[i] * i / D[i] 
next i
normalized_hashrate = sum_i / tw
next_D = 600 * normalized_hashrate

I can't get this to work at all. [edit: finally got it working]

[edit: ignore the rest of this post. I didn't realize avg(D/t) != 1/avg(t/D) ]

Avg (D/t) methods would be correct if solve time were a linear probability around the avg. The median solve time of a Poisson is ln(2)=0.693 of the avg. In other words it is skewed low. I worked a lot on this because I had reason to believe avg(D) / avg(t) is not ideal. So I mapped the poisson distributed D/t to a linear function, averaged it based on your exact same weighting equation, then unmapped it from the linear function back to a Poisson. It works good, but not better than my simple methods. Here it is. I did it this summer and called it Zawy v3c:

# Zawy v3c 
#  ST=solvetime
N=144
T=600
sum_i = N/2*(N+1)
for i=1 to 144 (from oldest to newest blocks)
  weighted_sum_hashrate += D[i] / ST[i] * i * 4 * (1-e^(-ST[i]/T)) * e^(-ST[i]/T))
next i
hashrate = weighted_sum_hashrate / sum_i
next_D = T * hashrate * 0.63

My derivation may have an error because the 0.63 was supposed to be 0.693. And the 0.63 may need to be modified for N > 30 to get average solvetime correct. You can't let timestamps go negative with this as in Zawy v6. It will work great with N=50. But please use Zawy v6 instead.

I believe if you check your other methods that are using avg(D/t) with a constant hashrate and a lower N, you will see problems with median not being at 0.693 of mean, and your Std Dev will not be correct (it's supposed to be equal to the mean). My method of avg(D) / avg(t) is only ~5% off on these numbers at N=30.

You avg(D/t) method might be causing the oscillations you mentioned. There are no oscillations in mine that are not desired oscillations that are responding correctly to hash attacks.

[zawy12]

I should mention sumocoin and karbowanek switched to this simple average with N=30 and N=17 because cryptonote's N=300 was too long. They had to fork to fix it. N=144 is not safe if there is a coin with the same POW and is a lot bigger. Only BTC can get away with N=2016 and not even make it a rolling average. It's going to be interesting for BTC's delays if miners really try to stick with 2x for 2 weeks, then jump on top of BTC at an unusually low difficulty for the first time in its life, and then leave suddenly after 2016, causing the delays. Actually, it could end up being very interesting for both coins since they both have the terrible difficulty algorithm that no alt could survive with it.

[zawy12]

[edited: deleted a repeat of my confusion about tw-144]

We're both correctly calculating a weighted average which is:

for i=1 to N
   sum_weighted_function += i * Function[i]
   sum_weights += i
next i
average_weighted_function = sum_weighted_function / sum_weights

The sum_weights = N/2*(N+1) which is what we both have. But zawy v3c weights D[i]/STW[i] and wt-144 weights the inverse ST[i]/D[i]. ( Zawy v3c STW[i] is a weighted probability distribution of ST[i] )

More generally "i" can be a function w(x) so we are basically doing this integral:

[zawy12]

Here is Zawy v6 with N=30 in response to 10x attacks. Notice how smooth the difficulty is when hashrate is constant.

[dgenr8]

@zawy12 Could you look at the code in this repository and try to frame your arguments in that context? So far we have more than a half dozen people doing this. It would be spectacular if you could implement your best suggestion and even more spectacular if it greatly out-performed everything else.

There you should also find:

• The implementation of wt-144 (in the next_bits_wt function). It looks like you are off by a factor of N (with no custom weighting the sum of "weights" is already N). Negative timestamps are handled.

• At steady-state with no hashrate variation, wt-144 has mean~=stddev~=608s, median ~=412s (while 415s = 600*ln(2)). This is due to slightly noisy difficulty which is an unavoidable cost of fast reaction time, but a good tradeoff since blocktimes are already noisy.

[zawy12]

Here's how I would reduce your code from 22 to 7 lines. Preventing negative solvetimes prevents good timestamps from erasing the effect of bad timestamps, so I took that out. Also, your if-else for limit precision did the same calculation for both the if and the else, so I took that out.

I'll work on trying to confirm your results.

def next_bits_wt(msg, block_count, limit_precision):
    timespan = 0
    for i in range(-block_count, 0):
        target_i = bits_to_target(states[i].bits)
        time_i = (states[i].timestamp - states[i-1].timestamp) * target_i
        timespan += time_i * (1+i/(block_count +1)) 
    target = timespan * 2 // 600 // block_count
    return target_to_bits(target)

Here's where I've discussed why negative solvetimes should not be removed.

[zawy12]

[edit: ignore the paragraph below. The code below is correct. ] My reading of the code is the same as my reading of the article. Implementing it in my spreadsheet still does not give me anything that's correct. In my terminology where timespan=1/dt and target = 1/next_D it looks like:

# tw-144
for i in range(-N, 0):
  tw += ST[i] * (1+i/(N+1)) / D[i]
next_D = 600 * N / 2 / tw

[dgenr8]

Your implementation crashes as it returns a float, but this is easily fixed. @dagurval Is testing removal of fixed point math as part of an optimization across steps 1-3 that was delayed to avoid clouding the design of the algorithm. These changes are already in the c++ implementation https://reviews.bitcoinabc.org/D622.

The code you removed did not simply set negative times to zero. It carried forward the previous timestamps thereby distributing their effect across future blocks. This is tested by the dr100 scenario and similar scenarios and has produced excellent results (no effect on mean blocktime). Without it, your implementation increases the mean blocktime to the 650s range in this scenario.

[zawy12]

If the timestamps are sequential, my modification should give the same result. If some timestamps were negative, I would need to see how negative timestamps are being generated to see if it is a real scenario. The random variation in solvetime due to a miner's clock error needs to be based off of a real clock time for a given hashrate, not the previous timestamp. Otherwise 650 in your simulation could be 600 in real time, and the 600 for the other might have actually been 550. I find it hard to believe you've changed the mathematical definition of average and got better results.

I can't check tw-144 unless I can see the math well enough to write my own code and scenarios for it. I would not be checking it if I ran your code. But if you write my code, you could compare my algo with yours. But I would still want to run my own scenarios.

[zawy12]

Your method of weighting is a really good one. I had tried it before and concluded it was not better than just going with a window that was about 2/3 smaller. I am combing it with Zawy v6 and it looks nice. It does not provide as good protection against hash attacks, but its statistics are a little bit better over a wider range of conditions. I still can't figure out what the rest of tw144 is doing, so for all I know it is like Zawy v6 with your weighting factors.

Here's Zawy v6 at N=17 w/o the weighting and Zawy v6 N=30 with tw144 weighting factors.

The previous chart above shows Zawy v6 with N=30 w/o weighting for comparison.

When the statistics of 1 good algo are better than another good algo, it usually means the one with worse statistics is providing better protection against hash attacks. Not providing as good protection means the attacks will occur more often, so the real world live statistics may be the same.

[dgenr8]

@zawy12 In the dr100 scenario, @kyuupichan has a small amount of hashrate produce minimal (MTP + 1s) timestamps. This naturally generates lots of negative differences as the honest timestamps are interspersed.

The simulation uses honest timestamps as real ("wall") time, which seems correct to me. So two timestamps are tracked, which are different when fake timestamps have been produced.

I already ran your code with the dr100 scenario, that's where I got the 650s figure.

[zawy12]

I finally got 144 working. Apparently there is a big difference between avg(D/t) like I have always tried in the past and 1/avg(t/D). So, what you're doing is a big discovery for me. I'll have to say tw144 is a little better. Congrats. In the charts below Zawy v6 appears to have better hash rate protection, but there are many things to consider and many different ways I look at the data. For a given protection against hash attacks, smoothness, and staying on correct average solvetime, tw144 wins the overall comparison.

[zawy12]

Zcash uses Digisheild v3 "modified". Bitcoin Gold is going to use it because they can just copy the code over. On the surface is it a N=17 but it is tempered and they have a 5 block delay from using MTP block as the most recent block. I hope you are not doing that with tw-144. Zcash's algo acts like a N=63 from the tempering and delay. I am mentioning it for comparison. HUSH copied them. Both of these N=63 algos typically change difficulty from 0.8 to 1.2 during a day. A lot of this change is from about 2 hash attacks per day that begin when their difficulty is accidentally low.

By beginning mining when difficulty is accidentally low (or about to go low) a hash-attack can always get up to 1/3 [edit, no maybe only 20%] of the coins issued at "zero excess difficulty cost". So the tradeoff in choosing N becomes choosing between smooth difficulty and fast post-attack recovery. Larger N with better avg solvetime and std dev means more blocks with a post-attack delay. Not longer delays for a given attack profile, but more blocks with that delay.

Your TW is nice because it goes up in a nice linear fashion that does not overshoot and comes down fast.

The following 3x attacks are the kind I would expect based on HUSH and Zcash observations. Ethereum miners are the source of big miners affecting Zcash, and Zcash affects HUSH. So there is a huge pool of miners, but they see 5x hash attacks only once every few days. Usually it is 2x and 3x two or three times per day, loosing 5% to 15% of blocks unfairly from constant miners to large transient miners.

I had to do a 0.99 adjust on TW-50 to get avg solve time correct.

[dgenr8]

I've been wary to add a goal-seeked factor to make the mean come out exactly right. The risk is that it's an artifact of the specific test scenarios. Also, since growing hashrate has caused the observed mean to undershoot for a long time, why go out of the way to preserve that?

[zawy12]

@The error at low N implies the algo is not perfect, but anything more perfect will require some messy math. I only include it since solvetime is important to people.

The avg error on an exponentially increasing hashrate is not cumulative, so the difficulty does not get behind more than 1/2 N. It is only behind as a result of the hashrate pulling ahead during the window. For example, a ramp of 1.004 increase per block results in avg ST being 1.004^(-50/2) too low, or about that. I wonder if a realistic hourly pull back on the upward slope will all but erase the error. Any fix would be worse than the problem. Mathematically, we assume downward trends would be as common, or likely, so "there is no error" in a way.

These are minor things, but I wanted to clarify I do not see any theoretical problem that needs any adjustment. What you have is probably the theoretically best thing there is. [ edit: other than N being determined dynamically based on statistical aberrations, aka zawy v2 which is very messy. ]

Any constant in a difficulty algorithm is evidence of a developer messing something up, so it's great you have no constants except N. The 2*tw and the N+1 are mathematical requirements resulting from the calculus definition of "average" (image above). I can get rid of the 2 and the straggling 1's:

# Degnr8 TW (time-weighted) difficulty algorithm
for  i = 1 to N   (oldest to newest block in the N window)
    tw += i * ST[i] / D[i] 
    j += i 
next_D = T * j / tw 

tw-144 is a N=145 average.

[zawy12]

I tested it. tw-144 has no problem with bad timestamps. There was a slight error in your algo for some reason. It needed an extra 1 in a very specific place. I can't derive it, but it fixed a round off error I saw. Also, my equation above that i copied to the mailist has a big gaff. Here's the gaff corrected with the extra 1 that was needed. You effectively have a (N+1) * N / 2 but for some reason it needs to be 1 + (N+1) * N / 2

# Degnr8 TW (time-weighted) difficulty algorithm
for  i = 1 to N   (oldest to newest block in the N window)
    tw += i * ST[i] / D[i] 
    j += i 
next_D = T *j / tw 

I can't see right away how to get this change into your code.

[dgenr8]

@zawy12 Could you explain in more detail why the +1 was needed? The ABC unit test starts with a scenario with a bunch of 600s blocks and simply j (in your notation) is the factor that makes it work.

[zawy12]

edit: Nevermind, I found my error.

I was testing negative stamps and with all solvetimes at 1 and difficulty all at 1.  So I was expecting your algo at N=50 to always return 1.  But it returned the following and settled on 0.99965. I just guessed and threw in the 1 and it corrected.

[zawy12]

Full specification with timestamp protection.

# Degnr8 difficulty algorithm 
# Zawy timestamp limits,  "keep out-of-order timestamps" 
# set constants
T=600
N=50
k=N*(N+1)/2 # normalizes the weighted average
X=10 # max hash attacks expected
limit = X^(3/N) # limits timestamp errors w/o slowing response

# begin algorithm 
for  i = -N+1 to 0   (oldest to newest block in the N window)
    j++
    t += j * ST[i] / D[i] 
next i  
t = 1 if t <1
next_D = T * k / t
next_D = D[0]*limit if next_D > D[0]*limit
next_D = D[0]/limit if next_D < D[0]/limit