Tuesday, August 1, 2017

difficulty algorithms

===============

# Zawy v1b difficulty algorithm (nice and simple)
# Based on next_diff=average(prev N diff) * TargetInterval / average(prev N solvetimes)
# Thanks to Karbowanec and Sumokoin for supporting, refining, testing, discussing, and using.
# Dinastycoin may be 3rd coin to use it, seeking protection that Cryptonote algo was not providing.
# Original impetus and discussion was at Zcash's modification of Digishield v3. The median method
# Zcash uses should be less accurate and should not be needed for timestamp error protection.
# Wider allowable limit for difficulty per block change provides more protection for small coins.
# Miners should be encouraged to keep accurate timestamps to help negate the effect of attacks.
# Large timestamp limits allows quick return after hash attack. Needed to prevent timestamp manipulation.
# (1+0.693/N) keeps the avg solve time at TargetInterval.
# Low N has better response to short attacks, but wider variation in solvetimes. 
# Sudden large 5x on-off hashrate changes with N=11 sometimes has 30x delays verses 
# 20x delays with N=17. But N=11 may lose only 20 bks in 5 attacks verse 30 w/ N=17.
# For more info: 
# https://github.com/seredat/karbowanec/commit/231db5270acb2e673a641a1800be910ce345668a
#
# D = difficulty, T = TargetInterval, TS = timestamp, TSL = timestamp limit

N=17;  # can possibly range from N=4 to N>30.  N=17 seems to be a good idea.
TSL=10 if N>11 else TSL = 0.8*N; # stops miner w/ 50% from lowering  D>25% w/ forward TS's.
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+1/N);
next_D = previous_D*1.2 if next_D < 0; 
next_D = 2*previous_D  if next_D/previous_D > 2;
next_D = 0.5*previous_D  if next_D/previous_D < 0.5;
==============

I had thought the following was best, but if I use v1b with N=8 and replace 1/(1+0.693/N) with
*0.89 then they are about the same.

===========
#  Zawy v1c difficulty algorithm  
# For more info: 
# https://github.com/seredat/karbowanec/commit/231db5270acb2e673a641a1800be910ce345668a
# D = difficulty, T = TargetInterval, TS = timestamp, TSL = timestamp limit
# N should not be changed
N=16;
M=int(N/2);
O=int(N/4);
k = 0.85; # adjustment to keep avg solvetime correct when hash rate is constant.
TSL=9; # should not be changed
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;
temp1=  k * sum(last N Ds) * T / [max(last N TSs) - min(last N TSs];
temp2 = k * sum(last M Ds) * T / [max(last M TSs) - min(last M TSs];
temp3 = k * sum(last O Ds) * T / [max(last O TSs) - min(last O TSs];
next_D = 1/3*(temp1+temp2+temp3);

==================


# Measures relative effectiveness of difficulty algorithm under attack scenarios.
# The algorithm with the lowest "attack" number wins.
# Getting blocks at low diff attracts attacks, so they are weighted same as long wait times.
for (  i = all block numbers )  { 
      for ( j=0 to 9 )  {  total_ST += ST[i+j]  }
      if  (10-total_ST/T) / SQRT(total_ST/T) > 2.5  sum_diff_was_too_low += total_ST/T/10 ;     
      if  (10-total_ST/T) / SQRT(total_ST/T) < -2.5  sum_diff_was_too_high += total_ST/T/10 ;     
}

=================
# zawy v3c  difficulty algorithm, 2nd best
# same as v3b with the following changes
# replace N=17 with
N=16 
sumNs = N/2*(N+1)

# totalHashrate = totalHashrate + D[i]/ST[i] * 4 * (1-e^(-ST[i]/T)) * e^(-ST[i]/T))
# is now

totalHashrate = totalHashrate + D[i]/ST[i] * 4 * (1-e^(-ST[i]/T)) * e^(-ST[i]/T))*(N+1-i)/sumNs
================
# Zawy v3b 
# ST=Solvetime, T=TargetInterval
# next_D = T * avg(N linearly mapped D/ST) 
# UNLESS past N/2 ST's are > 2.5 std devs too long (after an attack) 
# THEN use v1b for N/2 blocks:  next_D = T * avg(N/2 of D) / avg(N/2 of ST) / (1+0.69/(N/2))
N=16
M=int(N/2)

&correct_negative_solvetimes

# check to see if last M blocks were dropping significantly fast.
Mexpected = Sum(last  M ST's) / T
std_dev = (M - Mexpected) / SQRT(Mexpected)
if (std_dev > 2.1 OR wait > 0 ) then
    next_D = sum(last M Ds) * T / [max(last M timestamps) - min(last M timestamps] / (1+0.69/M)
    if (wait == 0) then (wait = M) else (wait=wait-1)
else 
   totalHashrate=0
   for i=1 to N
        totalHashrate = totalHashrate + D[i]/ST[i] * 4 * (1-e^(-ST[i]/T)) * e^(-ST[i]/T))
   next i
   next_D = T * 0.64 * totalHashrate / N  
end if
# finished

sub correct_negative_solvetimes {
# Eliminate negative ST before the mapping loop above. 
# N = number of block going in reverse.  N=1 is previous block.
# The following ST changes are permanent.

# Avg past 2 ST's if this ST is < 0.
if ST[1] < 0 then 
    if  ST[1] + ST[2] > 0 then 
        ST[1] = ( ST[1] + ST[2] ) / 2
        ST[2] = ST[1]
    else
         next_D=previous_D
         exit / return completely....get out of next_D routine
    end if
end if
if ST[2] < 0    #   ST[1]+ST[2] in previous block was neg. Previous ST[1] is now ST[2]
    if ST[1] + ST[2]  + ST[3]  > 0      
       ST[1] = ( ST[1] + ST[2]  + ST[3]  ) / 3
       ST[2] = ST[1] 
       ST[3] = ST[1] 
   else        # there were 2 or 3 negative timestamps in a row.
       # We don't know if ST[2] and ST[3] were early or if ST[4] and/or ST[5] were late.  
       # Best and safest thing is to make them median ST
        ST[1] =median ( ST[1] to ST[N] ) 
        ST[2] = ST[1]
        ST[3] = ST[1] 
    end if
end if
}


=========

#!/usr/bin/perl

# Zawy v1 algo for detecting hash attacks when diff algo is not responding fast enough (July 30, 2017)
# Let me know if there is an error:  zawy@yahoo.com
# Only detects when the diff algo is not responding fast enough.
# Prints a graphic to command line and writes block, solvetime, and difficulty to diff3.dat 
# For difficulty algorithm ideas (zawy v1c recommended)
# see https://github.com/seredat/karbowanec/commit/231db5270acb2e673a641a1800be910ce345668a

$instructions="
Detects hash attacks.
This diff3.pl file needs editing for the coin-cli location and the block interval.
Output goes to screen and diff3.txt
Command line format:
perl diff3.pl  
Default is past 500 blocks\n";

unless ($#ARGV == 1 or $#ARGV == -1) {   print $instructions; }

$coin_name='hush';
$dir="./$coin_name/src"; # Use "." if cli program is in same dir as this script. No ending "/".
$n=500; # number of blocks in past to look if start and end block not passed
$m=10; # Number of blocks to check for statistical aberration. Recommend m=10 to 15. 
# m < attack length is good. 
$ti=150; # the coin's targetinterval in seconds.  150 for 2.5 minute blocks.
$sd=3; # std devs of statistical significance.  Recommend sd=3.  See next paragraph.

# sd < 3 will result in too many false positives. sd = 4 will get only 1/4 of smart short 3x attacks
# The number of hits on accident are the 2*(one_tail_probability)*W/15*n/m
# where W=block in your diff algo averaging window.  sd=3 is 0.0015 for one_tail.  
# Expect to have a false appearance of attacks more often if W is larger or m is smaller.
# Short < W/2 attacks that are 2x network hashrate are detected 1/2 time and more often are just noise.
# But if m < 1.5 attack length, then sd=2.5 detects 80% of 2x attacks with minor false positives.
# Short 3x attacks are 80% detected with little error from noise.

if ($#ARGV == 1) { $n=$ARGV[1] - $ARGV[0]; }

@a=`$dir/hush-cli getinfo`;
foreach $a  (@a) { 
    if ($a=~s/.+blocks\"[^\d]+(\d+).+/$1/) {$height=$a;}
}
if ($#ARGV == 1) {$height=$ARGV[1]; }

for ($i=$height-$n-1;$i<$height;$i++) { 
   
   # print $i;
   $hash=`$dir/hush-cli getblockhash $i`;
   # print $hash;
   $info=`$dir/hush-cli getblock $hash`;
   $diff=$info;
   $diff=~s/.+"difficulty"\D+(\d+).+/$1/sg;
   $time=$info;
   $time=~s/.+"time"\D+(\d+).+/$1/sg;
   if ($i == $height-$n-1 ) { $prev_time=$time;next;  }
   # print "t: $time d: $diff\n";
   unless ($i==$height) {
      $t{$i} = $time-$prev_time;
      $neg{$i} = "negative" if $t{$i} <0;
      $d{$i} = int($diff);
   }
   $prev_time=$time;
 }
foreach $blk (sort keys %d) {
   $avg_diff= $avg_diff + $d{$blk}/$n; 
   $avg_t=$avg_t+$t{$blk}/$n;
   $j++;
   $sum_t=$sum_t+$t{$blk}; # add solvetimes
   $std_dev{$blk}="---";
   unless ($j < $m) {
      # take out oldest solvetime
      $sum_t=$sum_t-$t{$blk-$m};
      # do statistical calculation 
      $blks_expected=$sum_t/$ti;
      $est_diff_inc_needed{$blk} = $m/$blks_expected; 
      $std_dev=($m-$blks_expected)/($blks_expected)**0.5;
      if ($std_dev > $sd) {
         $std_dev{$blk}=int($std_dev*10)/10;  # store measured std dev if > sd
      }
      else  { $std_dev{$blk}="---"; }
   } 
}

open (F, ">diff3.txt") or die $!;
print F "height solvetime difficulty std_dev\n"; 

print "format: height, std dev if attack detected, scaled difficulty, solve time (amt diff needs increasing) difficulty\n";
foreach $blk (sort keys %d) {
    print "$blk $std_dev{$blk} " . 'O' x int($d{$blk}/$avg_diff*50) . ", $t{$blk} (" . int($est_diff_inc_needed{$blk}*100)/100 . ") $d{$blk} $neg{$blk}\n";
    print F "$blk $t{$blk} $d{$blk} $std_dev{$blk}\n";
}
close F;
print "avg difficulty: " . int($avg_diff) ."\n";
print "avg solvetime: " . int($avg_t) ."\n";
print $instructions;

No comments:

Post a Comment