EMA-JE difficulty algorithm

[zawy12]

This one is here for historical purposes. The EMA-Z is preferred over this one because this one can't handle zero solvetimes, requires e^-x calculation, and can't be done with integer math. The WHM is the best one

# Jacob Eliosoff's EMA (exponential moving average) difficulty algorithm
# https://en.wikipedia.org/wiki/Moving_average#Application_to_measuring_computer_performance
# see https://github.com/zawy12/difficulty-algorithms/issues/1 for other algos
# ST = solvetime, T=target solvetime
# height = most recently solved block
# There's a "2" in the exponent below to make the above N comparable to SMA, WT-144, & WWHM
# MTP should not be used

T=<target solvetime>
# Ideal N appears to be N= 40 to 85 for T=600 to 60 by the following formula.
# see https://github.com/zawy12/difficulty-algorithms/issues/14

N=int(50*(600/T)^0.3)

# Choose a limit on on how large solvetimes can be based on keeping
# difficulty from dropping more than 20% per bad timestamp.
# Varies from 5 for N < 50 to 9 for N > 76.
# The way it is used in the code makes it a symmetrical limit.
limit = max(5,min(int(N/0.90)-N,9))

maxT=timestamp[height-limit-1]
for ( i = height - limit to i < height )  { maxT = max(maxT, timestamp[i]) }
ST = timestamp[height] - maxT 
ST = max(T/200,min(T*limit, ST))
next_D = previous_D * ( T/ST + e^(-ST*2/T/N) * (1-T/ST) )

[h4x3rotab]

Still confused by the following code:

previous_max=0,  max=0
for (i=height - 10 to i <= height ) {  
   if (previous_max < timestamp[i] ) { max = timestamp[i]  }
   ST = max - previous_max
   previous_max = max
}

1. Why do you choose the last 10 blocks to find the 1st and 2nd latest block time? I thought 3-4 blocks are fine as it's hard to manipulate all these blocks.
2. If I understand it correctly, the ST = max - previous_max and previous_max = max should be inside the if condition because otherwise previous_max will become max whenever the max is updated or not. Am I wrong?

previous_max=0,  max=0
for (i=height - 10 to i <= height ) {  
   if (max < timestamp[i] ) {
      max = timestamp[i] 
      ST = max - previous_max
      previous_max = max
   }
}

[zawy12]

Crap. I edited it above so maybe now it is right.

Concerning 10: I have seen 6 blocks in a row that tried to be older than MTP. Although a subsequent MTP may not be older than a previous MTP, maybe all coins do not follow that rule. I mean maybe there is a coin that could have -1000 from the previous timestamp 6 times in a row. We can't simply make them =0 because it would be subtracted from an honest timestamp after it which would be a large solvetime. If an attacker did a "negative" every other bock, difficulty could go to zero.

[zawy12]

Your method is not what I'm trying to do because if the most recent block is negative, then the ST is equal to the solvetime of the previous block.

The problem is that I was trying to copy Tom Harding's method that's used in the WHM to work on the EMA. This seems correct:

for ( i=height-10 to i<=height )  {
    if (timestamp[i] <= prev_max ) {  ST = 0 }
    else { 
           ST = timestamp[i] } - prev_max
           prev_max = timestamp[i]
   }
}

[zawy12]

Testing a sequence of blocks all with ST = T but there were two lies in the assigned timestamps:
1, 2, 3, 4, -3, 6, 7, -5, 9, 10,
Gives STs:
1,1,1,0,2,1,0,2,1
OK, I think that's the behavior I want.

Another test, forward stamps
1,2,3,4,10,6,7,11,15,10, 11,12,13,14,15,16
where first 10, 11, and 15 were lies. STs:
1,1,1,6,0,0,1,4,0,0,0,0,0,0,1
average of the 15 comes out correctly to be 1.

[zawy12]

Another testing of timestamps (again real ST for each is magically 1, and the guys out of sequence are the liars). Only 1, 2, 3 and last 15, 16, and 17 are correct
1,2,3,10,2,12,2,9,7,9,7,6,15,14,15,16,17
STs desired and should be given by above code:
1,1,7,0,2,0,0,0,0,0,0,3,0,0,1,1
There were 16 ST's and their average is again 1 like we wanted.

[h4x3rotab]

Thanks for the correction.

Another quest: by assigning 0 to ST, ST will always be 0 when the last block is lying (consider 1,2,3,4,5,6,7,8,9,1), though it will be clipped to T/200 later. In this case, ST is no longer the time between the 1st and 2nd latest block. Is that intended behavior?

[zawy12]

Yes. You made me realize I could simplify the code which I did. We just get the max time from previous blocks (i<height instead of i<=height in the loop) and subtract that from the most recent block after the loop. Plus I've put a tighter limit , changing the 8 to a 7.

[zawy12]

BTW here is the problem with simple ST=0 if ST<0 if a miner has 33% hashpower and always assigns blocks at -6xT:

timestamps:
2,3,4-6,5,6,7-6,8,9,10-6,11,12,1-6,14
STs:
1,0,7,1,0,7,1,07

Average ST = 2.67 so D = correct_D/2.67 at the end of N blocks, and about D/5 in 2N. It keeps driving difficulty down until everyone is solving in 0 time, but the solvetimes keep driving D down:

0,0,0-6,0,0,0-6
gives solvetimes
0,0,6,0,0,6

So difficulty will still keeping dropping to D/2 every N blocks.

[h4x3rotab]

Thank you for clarification. I’m working on the implementation for BTG testnet :)

…

On Wed, 20 Dec 2017 at 5:38 AM zawy12 ***@***.***> wrote: BTW here is the problem with simple ST=0 if ST<0 if a miner has 33% hashpower: timestamps: 2,3,4-6,5,6,7-6,8,9,10-6,11,12,1-6,14 STs: 1,0,7,1,0,7,1,07 Average ST = 2.67 so D = correct_D/2.67 at the end of N blocks, and about D/5 in 2N. It keeps driving difficulty down until everyone is solving in 0 time, but the timestamps are still bad: 0,0,0-6,0,0,0-6 gives solvetimes 0,0,6,0,0,6 So difficulty will still keeping dropping by D/2 every N blocks. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#4 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABR_7ui7sga_kAItdu5dmynQfmlEgBRQks5tCCzGgaJpZM4Q4FIS> .

[zawy12]

I found another timestamp cheat. Be sure to use new code on first post above. Your limit value should be 7

[h4x3rotab]

Just came up with another detailed question:

maxT=timestamp[height-limit-1]
for ( i = height - limit to i < height )  { maxT = max(maxT, timestamp[i]) }

If height is the height of the last solved block, the last a few blocks should be in the range [height-limit+1, height]. But the code here is [height-limit-1, height-1].

[zawy12]

Yes, that is my intention. The loop just finds the previous max.

[h4x3rotab]

Ah, just got it. But shouldn't it be [height-limit+1, height-1]?

BTW, I'm trying to convert all the float operations to fixed point. The exponent is the most hard one.

[zawy12]

if height = previous solved block then what I have is correct. If height = current block being solved, then what you have is correct.

For simplicity, maybe you should use WHM algorithm instead. Masari is having excellent success with it.

They chose it because they did not want to leave integer world.

[h4x3rotab]

Just finished the first implementation. The constants and the details may need to be further adjusted. The implementation is based on fixed point calculation and use Tyler series to calculate exp(). I've checked the precision and it looks perfect. However I didn't check the offset problem. Would you like to take a look?

h4x3rotab/BTCGPU@1f681b4

[zawy12]

Just to confirm things:  The following timestamp must be at nHeight. pindexLast->GetBlockTime() The T/200 could be set to 2 or 3, and probably 1 is fine. solve_time = std::max((uint64_t)(T / 200), std::min((uint64_t)(T * limit), solve_time));  // 200???? 3? You could set the following to limit=7 and it will work for all N > 50.  But limit =6 is safer for N<60.  The problem is if someone assigns timestamp 7xT into future, difficulty will drop about 7/50 = 14%.  With 6 it will be 12%.    int limit = std::min(7, std::max((N * 100 / 89) - N, 10)); I can't tell if your series expansion is correct, but I know the following works perfectly: e^x = 1+x+x^2/2 I expanded this to integer math here:#17 k= ST*T*M  // M=25 instead N=50next_target = prev_target / 2 * ( 2*(T*M)^2-2*T^2*M+k*(k+2*(T*M)^2-T^2*M) ) / (T*M)^2  The LWMA (WHM) is a little bit better than EMA and uses the same timestamp handling if you can't allow negative solvetimes.  Two monero coins are now using it with great success. #3

[h4x3rotab]

T/200: Opps! Mistake caught.
Series expansion: Compared with expl. If negative ST is allowed, it can be tweaked a little bit to work.

It has been a few weeks since I paid close attention to the algorithm experiments. This is just a proof-of-concept about implementing float operators by fixed point. As you mentioned, LWMA is actually better than this.

[zawy12]

BTC candy tells me this morning your LWMA is not working good for them on their live coin.  I am investigating it now.

[h4x3rotab]

Thank you! I will send you a dump of testnet timestamps and difficulties tomorrow.

…

On Tue, May 1, 2018 at 8:30 PM zawy12 ***@***.***> wrote: BTC candy tells me this morning your LWMA is not working good for them on their live coin. I am investigating it now. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#4 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABR_7qhLeTsRvAld2BBA-dRG6TYafwMEks5tuFV0gaJpZM4Q4FIS> .

[zawy12]

I finally determined that nothing was wrong with their LWMA.....they just have really bad mining situation They said it is doing better than digishield was doing. On Thursday, May 3, 2018, 3:39:46 PM EDT, h4x3rotab <notifications@github.com> wrote: Thank you! I will send you a dump of testnet timestamps and difficulties tomorrow.

On Tue, May 1, 2018 at 8:30 PM zawy12 ***@***.***> wrote: BTC candy tells me this morning your LWMA is not working good for them on their live coin. I am investigating it now. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#4 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABR_7qhLeTsRvAld2BBA-dRG6TYafwMEks5tuFV0gaJpZM4Q4FIS> .

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or mute the thread.