Daily Archives: 21 April, 2015

Altcoin Difficulty Adjustment With MIDAS

Fixing Difficulty Adjustment
Okay, I promised I’d give a way to fix the difficulty retargeting issue. Here it is.

Go to the file src/pow.cpp. Delete the function GetNextWorkRequired.

Replace it with the code attached to this post.

MIDAS or Multi Interval Difficulty Adjustment System is my own invention. It responds very well to sudden changes in hashing power whether up or down. Emergency adjustments if needed usually kick in within ten blocks, and in non-emergencies it’s got a responsive but gradual and well-damped adjustment.

Additionally, it makes an effort to keep the block chain height approximately synchronized with real time – although real time here should be thought of more in terms of calendar date than clock time. If it’s more than two weeks behind, MIDAS will be trying to make block times about 10% faster than nominal, and if it’s more than two weeks ahead, it will be trying to make block times about 10% slower than nominal. In between, there’s a linear interpolation between those speeds – meaning the point toward which MIDAS regulates will be exactly the nominal block time whenever there’s an exact correspondence between block height and real time. Whenever the hashing rate has been reasonably steady for the last month or so, the correspondence between block height and actual time should be within a few hours.

This was originally proposed as a reaction to (and replacement for) the first version of the Kimoto Gravity Well algorithm, which was extremely “twitchy” in that whenever two blocks arrived whose timestamps were too close together, or reversed in sequence, it would make extreme adjustments to the difficulty rate. By checking multiple different intervals and making adjustments only when there is agreement as judged by several intervals as to which way and approximately how extreme the adjustment should be, MIDAS both avoids twitchiness and permits fairly extreme adjustments when they are actually needed.

Because the intervals it checks have no common divisor, it is also extremely resistant to timewarp attacks; there are no “harmonics” for an attacker to exploit that would allow bogus timestamps at particular intervals to reinforce each other leading to spurious adjustments, and no way for a bogus timestamp to cause a disproportional difficulty adjustment.

In my opinion, MIDAS is something that almost every altcoin ought to have; I believe it to be better behaved than anything else I know of that’s in use.

Setting Parameters – Block Intervals

Back in the file ChainParams.cpp, there are some parameters you can change that will change the behavior of your difficulty retargeting. The most important one is nTargetSpacing, in all three of the parameters initializers. For Bitcoin this is set (in all three places) to 600 (10 * 60) because the Bitcoin protocol is built around ten-minute blocks and there are 600 seconds in a block. If you want six-minute blocks for Newcoin, set it to 360 (6 * 60) instead. Most alts make this faster, which tends to centralize mining at places with good connectivity because the shorter the block time is, the more likely the miner is to get an orphan block due to otherwise-insignificant differences in network lag. If you make the block times too short, the network won’t be able to synchronize because blocks won’t even be able to cross the network before another block is found.

Setting Parameters – Adjustment Interval
The second is the nAdjustmentInterval, which is set directly below nTargetSpacing in all three blocks. MIDAS uses this variable for an entirely different purpose than Bitcoin’s difficulty adjustment algorithm used it for. In MIDAS, this is the period over which the block intervals are regulated +- 10% depending on how far the block height is from correspondence with the timestamps. From Bitcoin’s code this is 60 * 60 * 24 * 7 — one week’s worth of seconds. I’m doubling that value.

MIDAS stretches or shrinks blocks slightly as it seeks to make (genesis time + block height * nTargetSpacing) approximately equal to the timestamps of the blocks it’s receiving. nTargetSpacing, or the nominal block time, given our value of 6 minutes, is 360 seconds. In fact, the block intervals that MIDAS will regulate toward range from 324 (360-36) seconds if it’s a full adjustment period or more behind, to 396 (360+36) seconds if it’s a full adjustment period or more ahead. In between, there’s a smooth interpolation, so as long as the correspondence is reasonably close we should never be regulating toward an interval more than a few seconds longer or shorter than 360. If you make the adjustment interval very short, then newcoin will be more aggressive about keeping block height and time synchronized, and likely to regulate around both the longest and the slowest target within the same day. Smaller differences in correspondence would result in greater differences in the block timing, but unless much further ahead or behind, smaller differences in the block times that MIDAS regulates to achieve.

The Code:

// This is MIDAS (Multi Interval Difficulty Adjustment System), a novel getnextwork algorithm.  It responds quickly to
// huge changes in hashing power, is immune to time warp attacks, and regulates the block rate to keep the block height
// close to the block height expected given the nominal block interval and the elapsed time.  How close the
// correspondence between block height and wall clock time is, depends on how stable the hashing power has been.  Maybe
// Bitcoin can wait 2 weeks between updates but no altcoin can.

// It is important that none of these intervals (5, 7, 9, 17) have any common divisor; eliminating the existence of
// harmonics is an important part of eliminating the effectiveness of timewarp attacks.
void avgRecentTimestamps(const CBlockIndex* pindexLast, int64_t *avgOf5, int64_t *avgOf7, int64_t *avgOf9, int64_t *avgOf17)
{
  int blockoffset = 0;
  int64_t oldblocktime;
  int64_t blocktime;

  *avgOf5 = *avgOf7 = *avgOf9 = *avgOf17 = 0;
  if (pindexLast)
    blocktime = pindexLast->GetBlockTime();
  else blocktime = 0;

  for (blockoffset = 0; blockoffset < 17; blockoffset++)
  {
    oldblocktime = blocktime;
    if (pindexLast)
    {
      pindexLast = pindexLast->pprev;
      blocktime = pindexLast->GetBlockTime();
    }
    else
    { // genesis block or previous
    blocktime -= Params().TargetSpacing();
    }
    // for each block, add interval.
    if (blockoffset < 5) *avgOf5 += (oldblocktime - blocktime);
    if (blockoffset < 7) *avgOf7 += (oldblocktime - blocktime);
    if (blockoffset < 9) *avgOf9 += (oldblocktime - blocktime);
    *avgOf17 += (oldblocktime - blocktime);    
  }
  // now we have the sums of the block intervals. Division gets us the averages. 
  *avgOf5 /= 5;
  *avgOf7 /= 7;
  *avgOf9 /= 9;
  *avgOf17 /= 17;
}


unsigned int GetNextWorkRequired(const CBlockIndex *pindexLast, const CBlockHeader *pblock)
{
    int64_t avgOf5;
    int64_t avgOf9;
    int64_t avgOf7;
    int64_t avgOf17;
    int64_t toofast;
    int64_t tooslow;
    int64_t difficultyfactor = 10000;
    int64_t now;
    int64_t BlockHeightTime;

    int64_t nFastInterval = (Params().TargetSpacing() * 9 ) / 10; // seconds per block desired when far behind schedule
    int64_t nSlowInterval = (Params().TargetSpacing() * 11) / 10; // seconds per block desired when far ahead of schedule
    int64_t nIntervalDesired;

    unsigned int nProofOfWorkLimit = Params().ProofOfWorkLimit().GetCompact();

    if (pindexLast == NULL)
        // Genesis Block
        return nProofOfWorkLimit;

    
    if (Params().AllowMinDifficultyBlocks())
    {
        // Special difficulty rule for testnet: If the new block's timestamp is more than 2* TargetSpacing then allow
        // mining of a min-difficulty block.
        if (pblock->nTime > pindexLast->nTime + Params().TargetSpacing() * 2)
           return nProofOfWorkLimit;
        else
        {
            // Return the last non-special-min-difficulty-rules-block
           const CBlockIndex* pindex = pindexLast;
           while (pindex->pprev && pindex->nHeight % nIntervalDesired != 0 && pindex->nBits == nProofOfWorkLimit)
               pindex = pindex->pprev;
           return pindex->nBits;
        }
    }

    // Regulate block times so as to remain synchronized in the long run with the actual time.  The first step is to
    // calculate what interval we want to use as our regulatory goal.  It depends on how far ahead of (or behind)
    // schedule we are.  If we're more than an adjustment period ahead or behind, we use the maximum (nSlowInterval) or minimum
    // (nFastInterval) values; otherwise we calculate a weighted average somewhere in between them.  The closer we are
    // to being exactly on schedule the closer our selected interval will be to our nominal interval (TargetSpacing).

    now = pindexLast->GetBlockTime();
    BlockHeightTime = Params().GenesisBlock().nTime + pindexLast->nHeight * Params().TargetSpacing();
    
    if (now < BlockHeightTime + Params().AdjustmentInterval() && now > BlockHeightTime )
    // ahead of schedule by less than one interval.
    nIntervalDesired = ((Params().AdjustmentInterval() - (now - BlockHeightTime)) * Params().TargetSpacing() +  
                (now - BlockHeightTime) * nFastInterval) / Params().AdjustmentInterval();
    else if (now + Params().AdjustmentInterval() > BlockHeightTime && now < BlockHeightTime)
    // behind schedule by less than one interval.
    nIntervalDesired = ((Params().AdjustmentInterval() - (BlockHeightTime - now)) * Params().TargetSpacing() + 
                (BlockHeightTime - now) * nSlowInterval) / Params().AdjustmentInterval();

    // ahead by more than one interval;
    else if (now < BlockHeightTime) nIntervalDesired = nSlowInterval;
    
    // behind by more than an interval. 
    else  nIntervalDesired = nFastInterval;
    
    // find out what average intervals over last 5, 7, 9, and 17 blocks have been. 
    avgRecentTimestamps(pindexLast, &avgOf5, &avgOf7, &avgOf9, &avgOf17);    

    // check for emergency adjustments. These are to bring the diff up or down FAST when a burst miner or multipool
    // jumps on or off.  Once they kick in they can adjust difficulty very rapidly, and they can kick in very rapidly
    // after massive hash power jumps on or off.
    
    // Important note: This is a self-damping adjustment because 8/5 and 5/8 are closer to 1 than 3/2 and 2/3.  Do not
    // screw with the constants in a way that breaks this relationship.  Even though self-damping, it will usually
    // overshoot slightly. But normal adjustment will handle damping without getting back to emergency.
    toofast = (nIntervalDesired * 2) / 3;
    tooslow = (nIntervalDesired * 3) / 2;

    // both of these check the shortest interval to quickly stop when overshot.  Otherwise first is longer and second shorter.
    if (avgOf5 < toofast && avgOf9 < toofast && avgOf17 < toofast)
    {  //emergency adjustment, slow down (longer intervals because shorter blocks)
      LogPrintf("GetNextWorkRequired EMERGENCY RETARGET\n");
      difficultyfactor *= 8;
      difficultyfactor /= 5;
    }
    else if (avgOf5 > tooslow && avgOf7 > tooslow && avgOf9 > tooslow)
    {  //emergency adjustment, speed up (shorter intervals because longer blocks)
      LogPrintf("GetNextWorkRequired EMERGENCY RETARGET\n");
      difficultyfactor *= 5;
      difficultyfactor /= 8;
    }

    // If no emergency adjustment, check for normal adjustment. 
    else if (((avgOf5 > nIntervalDesired || avgOf7 > nIntervalDesired) && avgOf9 > nIntervalDesired && avgOf17 > nIntervalDesired) ||
         ((avgOf5 < nIntervalDesired || avgOf7 < nIntervalDesired) && avgOf9 < nIntervalDesired && avgOf17 < nIntervalDesired))
    { // At least 3 averages too high or at least 3 too low, including the two longest. This will be executed 3/16 of
      // the time on the basis of random variation, even if the settings are perfect. It regulates one-sixth of the way
      // to the calculated point.
      LogPrintf("GetNextWorkRequired RETARGET\n");
      difficultyfactor *= (6 * nIntervalDesired);
      difficultyfactor /= avgOf17 +(5 * nIntervalDesired));
    }

    // limit to doubling or halving.  There are no conditions where this will make a difference unless there is an
    // unsuspected bug in the above code.
    if (difficultyfactor > 20000) difficultyfactor = 20000;
    if (difficultyfactor < 5000) difficultyfactor = 5000;

    uint256 bnNew;
    uint256 bnOld;

    bnOld.SetCompact(pindexLast->nBits);

    if (difficultyfactor == 10000) // no adjustment. 
      return(bnOld.GetCompact());

    bnNew = bnOld / difficultyfactor;
    bnNew *= 10000;

    if (bnNew > Params().ProofOfWorkLimit())
      bnNew = Params().ProofOfWorkLimit();

    LogPrintf("Actual time %d, Scheduled time for this block height = %d\n", now, BlockHeightTime );
    LogPrintf("Nominal block interval = %d, regulating on interval %d to get back to schedule.\n", 
          Params().TargetSpacing(), nIntervalDesired );
    LogPrintf("Intervals of last 5/7/9/17 blocks = %d / %d / %d / %d.\n",
          avgOf5, avgOf7, avgOf9, avgOf17);
    LogPrintf("Difficulty Before Adjustment: %08x  %s\n", pindexLast->nBits, bnOld.ToString());
    LogPrintf("Difficulty After Adjustment:  %08x  %s\n", bnNew.GetCompact(), bnNew.ToString());

    return bnNew.GetCompact();
}