Kimoto Gravity Well simplier alternative

[Nite69]

Basicly KGW is just calculating running average, min x hours, up to y days. Then, it limits the max change with the horizon.
However, the calculated average block time should be weighted so the latest block times affects more than the older block times. KGW does not do this.

This is the alternative:

In the simplest theorethical implementation:

Count from the block 0: TimeAverage = (TimeAverage + LastBlockTime)/2

Cannot do that in practise; it would weigth the latest block time too much (50%), and also we cannot walk throught the blockchain everytime we start over, so

Code:

FilterAttenuation = 8
Walkingblock = (block@heightof(currentblock-(FilterAttenuation*2)))
TimeAverage = Walkingblock.time
while Walkingblock.heigth < currentblock.height
{
   Walkingblock = Walkingblock.next;
   TimeAverage = (TimeAverage*(FilterAttenuation-1) + Walkingblock.time)/FilterAttenuation;
}  

Actually this simulates quite well RC circuits commonly used on electorics to filter signals.

What do you think? I think it is a lot simpler and more effective that KGW.

Edit:

I assume WalkingblockTime is Walkingblock.time.

Ty, fixed! (also the missing parenthesis)

[AfrikaMan]

Basicly KGW is just calculating running average, min x hours, up to y days. Then, it limits the max change with the horizon.
However, the calculated average block time should be weighted so the latest block times affects more than the older block times. KGW does not do this.

This is the alternative:

In the simplest theorethical implementation:

Count from the block 0: TimeAverage = (TimeAverage + LastBlockTime)/2

Cannot do that in practise; it would weigth the latest block time too much (50%), and also we cannot walk throught the blockchain everytime we start over, so

Code:

FilterAttenuation = 8
Walkingblock = (block@heightof(currentblock-(FilterAttenuation*2))
TimeAverage = Walkingblock.time
while Walkingblock.heigth < currentblock.height
{
   Walkingblock = Walkingblock.next;
   TimeAverage = (TimeAverage*(FilterAttenuation-1) + WalkingblockTime)/FilterAttenuation;
}  

Actually this simulates quite well RC circuits commonly used on electorics to filter signals.

What do you think? I think it is a lot simpler and more effective that KGW.

I assume WalkingblockTime is Walkingblock.time.

Interesting algorithm. I agree KGW could be simplified by a weighted average calculation.

It looks like it should work well. One question, why does the algorithm go back 2 * FilterAttenuation blocks and not FilterAttenuation blocks only?

[Nite69]

It looks like it should work well. One question, why does the algorithm go back 2 * FilterAttenuation blocks and not FilterAttenuation blocks only?

Because otherwise the first block time in the loop would be weighted as much as the last.

[Crypto-t]

Looks good, an enhanced "KGW".

[david123]

I think there's a parenthesis missing..

Code:

Walkingblock = (block@heightof(currentblock)-(FilterAttenuation*2))

I also like the idea of simplifying/generalizing KGW, but I'm not sure if this while-loop
will provide the best self-regulation. I'm not criticizing, I just have to think longer about it..
Can you say more about this rc circuit stuff and why you came up with precisely this algorithm?

[MeGaDoOm]

can't the last/total difficulty be added somewhere in each (last) block? Thus eliminating the while loop.
Because the larger the blockchain becomes, the longer the while loop would take...

[Nite69]

I think there's a parenthesis missing..

Code:

Walkingblock = (block@heightof(currentblock)-(FilterAttenuation*2))

I also like the idea of simplifying/generalizing KGW, but I'm not sure if this while-loop
will provide the best self-regulation. I'm not criticizing, I just have to think longer about it..
Can you say more about this rc circuit stuff and why you came up with precisely this algorithm?

I once just needed a fast and simple algorithm to filter AD input on a low end microcontroller.
Been using it since allways when needed to filter some rieal time signal.

You can simulate it quite easily on a spreadsheet.

[Nite69]

can't the last/total difficulty be added somewhere in each (last) block? Thus eliminating the while loop.
Because the larger the blockchain becomes, the longer the while loop would take...

Yes, if you have real time signal, you don't need the loop, you can allways use the previous average value.

But since one should be able to jump in the middle of blockchain, it is easer to start from fixed point backwards, 2 x attenuation souds feasible. The loop is allways the same length,  on this case, 16 rounds.

And yes, you adjust every block.

[FoBoT]

Actually this simulates quite well RC circuits commonly used on electorics to filter signals.

well done, using existing solutions to improve crypto A++

[david123]

You can simulate it quite easily on a spreadsheet.

That would be nice to see, a worked-out example for some small numbers. Also, it should be a matter of some minutes
to write a small script so one can compare next difficulty by KGW and your proposal for some existing KGW-coins. This might also
be nice in order to compare the effect of different settings for FilterAttenuation..

I don't see a problem in the while-loop by the way. Just, when calculating an averaged mean, one could make use of a
"weighting function" without necessarily doing a loop. I mean, technically you do a loop, but without any recursive definition of variables.
So your loop with the (FilterAttenuation-1) - 1 - setting should correspond to
a certain weighting function, so one could rewrite it and eliminate this loop. Then one could also experiment with other weighting functions.

[HashEngineering]

The KimotoGravityWell is an interesting algorithm to be sure and it appears to be the most complicated difficulty adjustment algorithm out there.  It is also the slowest.  This doesn't matter on a desktop machine perhaps, but on Android devices it really drains the battery.  Part of that has do with with the parameters (Megacoin can go back over as many as the past 4032 blocks).  Calculating the difficulty on an android phone can take as much as 1 second for a block.  Other coins that use the KGW are using different parameters so that they do not review as many of the previous blocks.

Would this proposed algorithm be any more efficient?  The KGW uses block solving times to determine when to stop going back in the block chain, but the next difficulty calculations are based on the difficulties of the previous blocks (all calculated with 256 bit integers).  This has to be much slower than a weighted average of block times (which could be 32 or 64 bit - something that most processors can do on their own without using a slower BIGNUM library).

[Nite69]

The KimotoGravityWell is an interesting algorithm to be sure and it appears to be the most complicated difficulty adjustment algorithm out there.  It is also the slowest.  This doesn't matter on a desktop machine perhaps, but on Android devices it really drains the battery.  Part of that has do with with the parameters (Megacoin can go back over as many as the past 4032 blocks).  Calculating the difficulty on an android phone can take as much as 1 second for a block.  Other coins that use the KGW are using different parameters so that they do not review as many of the previous blocks.

Would this proposed algorithm be any more efficient?  The KGW uses block solving times to determine when to stop going back in the block chain, but the next difficulty calculations are based on the difficulties of the previous blocks (all calculated with 256 bit integers).  This has to be much slower than a weighted average of block times (which could be 32 or 64 bit - something that most processors can do on their own without using a slower BIGNUM library).

Sure it would be more efficient. Of course, when estimating needed difficulty, the latest block tells more about the present hashing power than than the older blocks. So they should also be weighted more on the calculations. And blocks 4032 behind does not tell anything new about current hashing power.

And no doubt, plain integer math needs a lot less CPU than floats. Actually, if you tune it, you don't even need multiply/divide, plain rotate will suffice (along with add/sub). Btw, the algorithm at the original post can be tuned to be better (it loses some accuracy which can be preserved, 3 bits at att 8 etc.), but I wanted to offer first very easily understable version.

But this has not ever been tested on coins. It should be tuned and tested carefully. I assume 8 is way too small attenuate. And using this could rise unknown threats, as BCX has shown us.

But that what you said about android with KGW, it worries me a lot..

[Cryddit]

I looked at KGW and aside from the code being very (alarmingly) complex it's got a mathematical property I don't like.

Depending on the timing of blocks, chain #1 can do less total hashing while getting more blocks and a supposedly higher proof of work than chain #2, and arrive at the same final hour.  This happens when chain #2 has blocks at even intervals, while chain #1 has long intervals punctuated by occasional backwards-in-time intervals.  Backwards-in-time blocks are allowed, up to the average time of the previous several blocks - and if they've got long intervals, you can get a long way backward in time with one jump.

Instead of tracing the ridiculously complex code, I actually tried testing it with random intervals, and within a few hours of testing chain splits (two chains from the same starting point) on a FakeCoin with 2-second target intervals, I saw a sequence that had more total hashes and less proof of work (and less blocks) than another sequence.  After a bunch more tests, it seems to happen whenever the backward-in-time jumps are more than 5 blocks apart and work less well the further apart they are than that. 

It looks like somebody with considerably less than half of the hashing power of the network could execute a 51% attack against a KGW blockchain.

[Nite69]

I looked at KGW and aside from the code being very (alarmingly) complex it's got a mathematical property I don't like.

Depending on the timing of blocks, chain #1 can do less total hashing while getting more blocks and a supposedly higher proof of work than chain #2, and arrive at the same final hour.  This happens when chain #2 has blocks at even intervals, while chain #1 has long intervals punctuated by occasional backwards-in-time intervals.  Backwards-in-time blocks are allowed, up to the average time of the previous several blocks - and if they've got long intervals, you can get a long way backward in time with one jump.

Instead of tracing the ridiculously complex code, I actually tried testing it with random intervals, and within a few hours of testing chain splits (two chains from the same starting point) on a FakeCoin with 2-second target intervals, I saw a sequence that had more total hashes and less proof of work (and less blocks) than another sequence.  After a bunch more tests, it seems to happen whenever the backward-in-time jumps are more than 5 blocks apart and work less well the further apart they are than that. 

It looks like somebody with considerably less than half of the hashing power of the network could execute a 51% attack against a KGW blockchain.

like this:
https://bitcointalk.org/index.php?topic=504103.msg5589177#msg5589177

[MMos]

I believe the retarget time implementation that Digibyte have is far more advanced and satisfies the requirement to defend against multipool attacks.

I think the retarget system it has will become the new standard over KGW

[Nite69]

It looks like somebody with considerably less than half of the hashing power of the network could execute a 51% attack against a KGW blockchain.

The flaw is basicly on the fact that maximum increase/decrease on the diff change is limited (for a good reason anyway). Based on this, one can generate low diff with several steps and then go back to real time with one step. Ie. he gets a 'reward' five times, but is 'punished' only once. That one step backward should end up with the same diff which was before the steps to future. Unfortunatey, since the max change in diff is 20%, it won't be.

[Nite69]

I believe the retarget time implementation that Digibyte have is far more advanced and satisfies the requirement to defend against multipool attacks.

I think the retarget system it has will become the new standard over KGW

Actually, I simulated both Dogecoin's digishield (which is digibyte's retarget attenuated) and my suggestion; it turned out that digishield achieves exactly what I was after with my suggestion.

After a while pondering, I found out the reason: the diff adjustment preserves the same information I calculated on the loop. So there was double feedback.. and my version started to oscillate!

Here is the libreoffice calc file:

https://app.younited.com/?shareObject=0a3e7dde-f7b8-ce05-3672-131a90c58ca3

[Cryddit]

The simplest way to protect against the time warp exploit, in all its forms, is with a simple rule about blocks whose timestamp is before the previous block.

Just make an adjustment to the difficulty baseline so they don't get the benefit of difficulty adjustments made after their own timestamp. 

In other words,  if a new block is timestamped prior to the previous four, you proceed as if the base difficulty were the same as it was prior to those four blocks.

poof, every time warp exploit in the world becomes impossible.

[eduffield]

Due to exploits found in KGW, I've implemented a new difficulty retargeting algorithm called DarkGravityWave.

What is DarkGravityWave? It uses multiple exponential moving averages and a simple moving average to smoothly adjust the difficulty. This implementation is far more simplistic and better suited to adjust difficulty than KGW and also fixes all known exploits.

Here's the commit if you're interested:

https://github.com/evan82/darkcoin/commit/07c99052edc617975cdcbe4482e02c52e2d1fbf5

[Nite69]

Due to exploits found in KGW, I've implemented a new difficulty retargeting algorithm called DarkGravityWave.

What is DarkGravityWave? It uses multiple exponential moving averages and a simple moving average to smoothly adjust the difficulty. This implementation is far more simplistic and better suited to adjust difficulty than KGW and also fixes all known exploits.

Here's the commit if you're interested:

https://github.com/evan82/darkcoin/commit/07c99052edc617975cdcbe4482e02c52e2d1fbf5

But the problem is that KGW retargets every block, but allows timestamps backwards over more than 1 block. I don't see how this is fixed in DGW, can you explain?