Wednesday, June 28, 2017

Zawy v2 difficulty algorithm

#!usr/bin/pseudo_perl
#
# Zawy v1b abd v2 difficulty algorithm
# Simple averaging window with option to use dynamic window size.
# Cite as "Zawy v1b N=8" if N=8 is chosen and "Zawy v2 N>=8" if dynamic option is chosen
# Credit karbowanec and sumokoin for using modifications of Zawy v1 after their hard forks 
# to protect against attacks that were the result of Cryptonote's default difficulty algorithm. 
# And for motivating me to do more work where Zcash left off.  
#
# Core code with fluff and dynamic option removed:  (TS=timestamps)
# TSL=10 if N>11 else TSL = N-2; # stops miner w/ 50% forward stamps from lowering  D>20%.
#  current_TS=previous_TS + TSL*T if current_TS > previous_TS + TSL*T;
#  current_TS=previous_TS - (TSL-1)*T if current_TS < previous_TS - (TSL-1)*T;
#  next_D = sum(last N Ds) *T / [max(last N TSs) - min(last N TSs] / (1+ln(2)/N)
# next_D = 2*previous_D  if next_D/previous_D > 2;
# next_D = 0.5*previous_D  if next_D/previous_D < 0.5;
#
# Changes:
# A preference for low N and letting difficulty change rapidly for hash-attack protection. 
# Included option for dynamic averaging window (probably inferior to simple low N).
# Includes timestamp limit for timestamp manipulation/error protection. 
# Added an adjustment factor to next_D that is important at low N: 1/(1+ln(2)/N). 
# This is due to the median of a Poisson being ln(2) of the mean.
# A rejection of medians which do not help and cause error via lack of resolution, 
#  including the "bad timestamp" excuse for using it. 
# Rejected dynamic modification to maxInc, maxDec, and TS limits based on recent history
# of D (as a way to let D drop after an attack). It either leaves a security hole or does 
# not have an effect.  Avg(solvetime) is still > TargetInterval if there is a hash attack but 
# I can't find a solution that does not have equally bad side effects.  
#
# Miners/pools should be asked to keep their timestamps accurate or it will help 
# attackers and block release will be slower.
# See verbose text at link below for explanations (if this is not verbose enough)
# https://github.com/seredat/karbowanec/commit/231db5270acb2e673a641a1800be910ce345668a#commitcomment-22615466

# Begin setting constants for this coin

T = 240;   # Target interval
MinimumHashAttackDuration = 8; # Sets N. See text below.
timestamps_are_provably_correct = "no";  #  "no" if miners or pools are assigning timestamps
employ_variable_averaging_window = "yes"; # see paragraph below

# End setting constants for this coin

# Modifications to the logic below this point is not recommended.
# Trying to fix something usually breaks something else. 

# Set averaging window based on MinimumHashAttackDuration. 
# N=17 is working in several coins, but it still allows some large on-off mining to rapidly
# "steal" blocks at low difficulty for N/2, leaving constant miners with higher D for N, delaying
# subsequent blocks. N=12 is low but not unwisely low. May cause 3x delays post attack verses 15x for N=17.
# N=8 might be best for small coins still having "hash attack" trouble at N=12. 
# N=8 has only 47% more >4*T solvetimes than N=30.  
# Even 4 can work, even with timestamp errors, if the rise & fall in D is 
# symmetrically limited to 2x & 0.5x per block. 
# There is desire to have low N because hash attacks with 
#  off time >= N and P=on time <=N, I have:
# blocks stolen at low D = P x [1 -(1-X)/2 - P/2N ]
# notice how low N is the only way to reduce attack profit. Stating attack length as Fraction of N:
# blocks stolen at low D = NF x [1 -(1-X)/2 - F/2 ]

N1=int(MinimumHashAttackDuration);
if ( N1 < 6) { N1 = 6; } # due to the way I have TSL, there's more risk to <6. 

# Variable averaging window option:
# It will be smoother most of the time, but takes ~N/4 blocks longer to respond and recover from 
#  sudden hash changes. Choosing the smallest N instead of this option is probably best unless
# you have a strong desire for a smoother difficulty when HR is stable.  
# Precise technical description: 
# Trigger to a lower N if a likely change in HR has occurred.  Checks all possible windows 
# from N1 to 2*N1, linearly decreasing the likeliness from 95% at N1 to 68% at 2*N1 and 
# resets window to the lowest N that triggers. After keeping that N window for N blocks
# to let strange events flush out it raises N by 1 each block until another trigger occurs. 
# It can easily reach 4N as the window if HR is stable.
# This option seems to increase solvetimes by another (1+ln(2)/N) factor which is not
# in this psuedocode for simplicity.

Smax=2; Smin=1; # STDevs range away from mean that will cause a trigger to lower N.

# TS limit to protect against timestamp manipulation & errors. 
if (timestamps_are_provably_correct == "yes" ) { TSL= 10; }   # similar to bitcoin
# next line stops miner w/ 50% forward stamps from lowering  D>20% if N1 is low. 
# steady steady D from miner with X% of network hash less than 50% who who always
# forward timestamping to the max is: SS D= correct D x [1 -(1 - 1/(1+TSL/N1) ) * X]
# Miner with X>50% can drop D to zero w/ forward timestamps at the following rate:
# next D=previous D x  [1/(1+TSL/N1)]^(2X-1)

else { TSL=10 if N1>12 else TSL = N1-1; }

# The following are fail-safes for low N when timestamps have errors.
# Bringing them closer to 1.0 as in other diff algos reduces hash attack protection. 
#  Not letting them be symmetrical may have problems. Example:
# Using maxDec < 1/maxInc allows +6xT timestamp manipulation to drop D faster than -5xT
# subsequent corrections from honest timestamp can bring it back up.
# Bringing them closer to 1 is similar to increasing N and narrowing the timestamp limits,
# but these values should be far enough away from 1 to let low N & TS limits do their job.

maxInc=  2; # max Diff increase per block 
maxDec= 1/maxInc;  # retains symmetry to prevent hacks and keep correct avg solvetime

# End setting of constants by the algorithm.

# definition: TS=timestamp

#  Begin actual algorithm

# Protect against TS errors by limiting how much current TS can differ from previous TS.
# This potentially slows how fast D can lower after a hash attack. The -1 is for complex reasons.

current_TS=previous_TS + TSL*T if current_TS > previous_TS + TSL*T;
current_TS=previous_TS - (TSL-1)*T if current_TS < previous_TS - (TSL-1)*T;

if (employ_variable_averaging_window == "yes") {
     for (I=N1 to N) { # check every window that is smaller than current window.
        # create linear function: STDev decreases as I (aka N) increases to N
         STDevs = Smax-(Smax-Smin)/(2*N1 - N1)*(I-N1); 
         NE = (max(last I timestamps) - min(last I timestmaps)) / T; # expected N for this time range
         if ( abs(I - NE) > STDevs*NE**0.5 ) { N=I;  wait=I; } # This is the core statistics. It's correct.
     }
}
else { N=N1; } 

next_D = sum(last N Ds) *T / [max(last N TSs) - min(last N TSs] / (1+ln(2)/N); 
# the above is same as the following. Credit karbowanec coin for sum & max-min simplification
#  next_D = avg(last N Ds) * T / avg(last N solvetimes) / (1+ln(2)/N)

next_D = 1.2\*avg(last N Ds) if next_D<=0;  # do not let it go negative.

# Increase size of N averaging window by 1 per block if it has been >=N blocks
# since the last trigger to N. This flushes out statistical accidents and < N attacks. 
if (employ_variable_averaging_window == "yes") { 
   if (wait > 0)  { wait=wait-1; } # do not increase N yet
   else {  N=N+1;  }  # resume increasing N every block

# Do not let D rise and fall too much as a security precaution
next_D = maxInc*previous_D  if next_D/previous_D > maxInc;
next_D = maxDec*previous_D if next_D/previous_D < maxDec;

No comments:

Post a Comment