Post
Topic
Board Altcoin Discussion
Re: Kimoto Gravity Well simplier alternative
by
Cor2
on 20/03/2014, 00:32:51 UTC
Here is a proposal for a simple algorithm as alternative to KGW, that should be fairly resistant to time-travel exploits,
while producing a stable and fast-re-targeting diff.
The assumption is that most block finders are honest (with their time stamp) as a majority-attack can always be designed to wreak havoc,
the issue here is to avoid an easy exploitation of the re-target by making it as redundant as possible while still maintaining agility:
 (The integer N should be a multiple of 4, for example 32)

- take the last 1.5*N block interval values (the difference between the time stamps of adjacent blocks)
- store the interval values in a double linked list

- go through this list and remove the highest 0.25*N and the lowest 0.25*N interval values (including negative values) which will remove noise and correct time travel intervals (both the before and after intervals).

- calculate the average of the remaining N block intervals (add all intervals and divide by N)
- calculate the average of the most recent 0.5*N block intervals
- calculate the average of the most recent 0.25*N block intervals
- add the first two averages, divide by 2, add the last average to it and again divide by 2
This is now a nice number for the actual block finding time that is weighed towards the later block intervals and filtered from noise and time travel events. The diff can now be lowered/increased based directly on the ratio between this avg block finding time and the designed block time.
The response time for new intervals (if they are not caught by the filter) is quick, since they count heavily (4x more than intervals older than 1/2 N).
If network hash rate would suddenly change dramatically, it might take up to 1/4 N blocks before the diff responds since the new values are initially filtered out. If N is 32 for example and the normal block finding time is 1 minute, then a dramatic change of an order of magnitude change would cause either (for increased hash rate) more than 8 blocks found within 1 minute before the diff will quickly start rising, so within 2 minutes the block finding rate will seriously slow down again for a 10x increase in network hash rate. When the network suddenly loses 90% of hash rate, the avg block find time goes to 10 min and about 1.5 hour goes by before the filter will let the extreme large intervals show up, but then the diff will quickly lower and the block find time return to normal.
Time travel effects are essentially eliminated: every single time travel event (up to 8 in a 48 block interval when N is 32) will show a very low or negative interval and a very high interval which are both filtered out.
This simple algo does not protect against an attacker that manages to inject a continuous sequence of blocks showing large or very small time increments, but the assumption is that the majority of the network is submitting blocks with correct time stamp.
It definitely will protect against the random jumps in diff due to looking only at the last 1 or 2 blocks
Also the algo is so simple that it hardly takes any processing time and very little memory.
What do you think? Let me know.