Line data    Source code

       1             : // Copyright (c) 2009-2010 Satoshi Nakamoto
       2             : // Copyright (c) 2009-2015 The Bitcoin Core developers
       3             : // Distributed under the MIT software license, see the accompanying
       4             : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       5             : 
       6             : #include <pow.h>
       7             : 
       8             : #include <arith_uint256.h>
       9             : #include <chain.h>
      10             : #include <primitives/block.h>
      11             : #include <uint256.h>
      12             : 
      13             : #include <math.h>
      14             : 
      15           0 : unsigned int static KimotoGravityWell(const CBlockIndex* pindexLast, const Consensus::Params& params) {
      16           0 :     const CBlockIndex *BlockLastSolved = pindexLast;
      17           0 :     const CBlockIndex *BlockReading = pindexLast;
      18           0 :     uint64_t PastBlocksMass = 0;
      19           0 :     int64_t PastRateActualSeconds = 0;
      20           0 :     int64_t PastRateTargetSeconds = 0;
      21           0 :     double PastRateAdjustmentRatio = double(1);
      22           0 :     arith_uint256 PastDifficultyAverage;
      23           0 :     arith_uint256 PastDifficultyAveragePrev;
      24             :     double EventHorizonDeviation;
      25             :     double EventHorizonDeviationFast;
      26             :     double EventHorizonDeviationSlow;
      27             : 
      28           0 :     uint64_t pastSecondsMin = params.nPowTargetTimespan * 0.025;
      29           0 :     uint64_t pastSecondsMax = params.nPowTargetTimespan * 7;
      30           0 :     uint64_t PastBlocksMin = pastSecondsMin / params.nPowTargetSpacing;
      31           0 :     uint64_t PastBlocksMax = pastSecondsMax / params.nPowTargetSpacing;
      32             : 
      33           0 :     if (BlockLastSolved == nullptr || BlockLastSolved->nHeight == 0 || (uint64_t)BlockLastSolved->nHeight < PastBlocksMin) { return UintToArith256(params.powLimit).GetCompact(); }
      34             : 
      35           0 :     for (unsigned int i = 1; BlockReading && BlockReading->nHeight > 0; i++) {
      36           0 :         if (PastBlocksMax > 0 && i > PastBlocksMax) { break; }
      37           0 :         PastBlocksMass++;
      38             : 
      39           0 :         PastDifficultyAverage.SetCompact(BlockReading->nBits);
      40           0 :         if (i > 1) {
      41             :             // handle negative arith_uint256
      42           0 :             if(PastDifficultyAverage >= PastDifficultyAveragePrev)
      43           0 :                 PastDifficultyAverage = ((PastDifficultyAverage - PastDifficultyAveragePrev) / i) + PastDifficultyAveragePrev;
      44             :             else
      45           0 :                 PastDifficultyAverage = PastDifficultyAveragePrev - ((PastDifficultyAveragePrev - PastDifficultyAverage) / i);
      46           0 :         }
      47           0 :         PastDifficultyAveragePrev = PastDifficultyAverage;
      48             : 
      49           0 :         PastRateActualSeconds = BlockLastSolved->GetBlockTime() - BlockReading->GetBlockTime();
      50           0 :         PastRateTargetSeconds = params.nPowTargetSpacing * PastBlocksMass;
      51           0 :         PastRateAdjustmentRatio = double(1);
      52           0 :         if (PastRateActualSeconds < 0) { PastRateActualSeconds = 0; }
      53           0 :         if (PastRateActualSeconds != 0 && PastRateTargetSeconds != 0) {
      54           0 :             PastRateAdjustmentRatio = double(PastRateTargetSeconds) / double(PastRateActualSeconds);
      55           0 :         }
      56           0 :         EventHorizonDeviation = 1 + (0.7084 * pow((double(PastBlocksMass)/double(28.2)), -1.228));
      57           0 :         EventHorizonDeviationFast = EventHorizonDeviation;
      58           0 :         EventHorizonDeviationSlow = 1 / EventHorizonDeviation;
      59             : 
      60           0 :         if (PastBlocksMass >= PastBlocksMin) {
      61           0 :                 if ((PastRateAdjustmentRatio <= EventHorizonDeviationSlow) || (PastRateAdjustmentRatio >= EventHorizonDeviationFast))
      62           0 :                 { assert(BlockReading); break; }
      63           0 :         }
      64           0 :         if (BlockReading->pprev == nullptr) { assert(BlockReading); break; }
      65           0 :         BlockReading = BlockReading->pprev;
      66           0 :     }
      67             : 
      68           0 :     arith_uint256 bnNew(PastDifficultyAverage);
      69           0 :     if (PastRateActualSeconds != 0 && PastRateTargetSeconds != 0) {
      70           0 :         bnNew *= PastRateActualSeconds;
      71           0 :         bnNew /= PastRateTargetSeconds;
      72           0 :     }
      73             : 
      74           0 :     if (bnNew > UintToArith256(params.powLimit)) {
      75           0 :         bnNew = UintToArith256(params.powLimit);
      76           0 :     }
      77             : 
      78           0 :     return bnNew.GetCompact();
      79           0 : }
      80             : 
      81           2 : unsigned int static DarkGravityWave(const CBlockIndex* pindexLast, const Consensus::Params& params) {
      82             :     /* current difficulty formula, dash - DarkGravity v3, written by Evan Duffield - evan@dash.org */
      83           2 :     const arith_uint256 bnPowLimit = UintToArith256(params.powLimit);
      84           2 :     int64_t nPastBlocks = 24;
      85             : 
      86             :     // make sure we have at least (nPastBlocks + 1) blocks, otherwise just return powLimit
      87           2 :     if (!pindexLast || pindexLast->nHeight < nPastBlocks) {
      88           0 :         return bnPowLimit.GetCompact();
      89             :     }
      90             : 
      91           2 :     const CBlockIndex *pindex = pindexLast;
      92           2 :     arith_uint256 bnPastTargetAvg;
      93             : 
      94          50 :     for (unsigned int nCountBlocks = 1; nCountBlocks <= nPastBlocks; nCountBlocks++) {
      95          48 :         arith_uint256 bnTarget = arith_uint256().SetCompact(pindex->nBits);
      96          48 :         if (nCountBlocks == 1) {
      97           2 :             bnPastTargetAvg = bnTarget;
      98           2 :         } else {
      99             :             // NOTE: that's not an average really...
     100          46 :             bnPastTargetAvg = (bnPastTargetAvg * nCountBlocks + bnTarget) / (nCountBlocks + 1);
     101             :         }
     102             : 
     103          48 :         if(nCountBlocks != nPastBlocks) {
     104          46 :             assert(pindex->pprev); // should never fail
     105          46 :             pindex = pindex->pprev;
     106          46 :         }
     107          48 :     }
     108             : 
     109           2 :     arith_uint256 bnNew(bnPastTargetAvg);
     110             : 
     111           2 :     int64_t nActualTimespan = pindexLast->GetBlockTime() - pindex->GetBlockTime();
     112             :     // NOTE: is this accurate? nActualTimespan counts it for (nPastBlocks - 1) blocks only...
     113           2 :     int64_t nTargetTimespan = nPastBlocks * params.nPowTargetSpacing;
     114             : 
     115           2 :     if (nActualTimespan < nTargetTimespan/3)
     116           0 :         nActualTimespan = nTargetTimespan/3;
     117           2 :     if (nActualTimespan > nTargetTimespan*3)
     118           0 :         nActualTimespan = nTargetTimespan*3;
     119             : 
     120             :     // Retarget
     121           2 :     bnNew *= nActualTimespan;
     122           2 :     bnNew /= nTargetTimespan;
     123             : 
     124           2 :     if (bnNew > bnPowLimit) {
     125           0 :         bnNew = bnPowLimit;
     126           0 :     }
     127             : 
     128           2 :     return bnNew.GetCompact();
     129           2 : }
     130             : 
     131       98066 : unsigned int GetNextWorkRequiredBTC(const CBlockIndex* pindexLast, const CBlockHeader *pblock, const Consensus::Params& params)
     132             : {
     133       98066 :     assert(pindexLast != nullptr);
     134       98066 :     unsigned int nProofOfWorkLimit = UintToArith256(params.powLimit).GetCompact();
     135             : 
     136             :     // Only change once per interval
     137       98066 :     if ((pindexLast->nHeight+1) % params.DifficultyAdjustmentInterval() != 0)
     138             :     {
     139       97994 :         if (params.fPowAllowMinDifficultyBlocks)
     140             :         {
     141             :             // Special difficulty rule for testnet:
     142             :             // If the new block's timestamp is more than 2* 2.5 minutes
     143             :             // then allow mining of a min-difficulty block.
     144       97838 :             if (pblock->GetBlockTime() > pindexLast->GetBlockTime() + params.nPowTargetSpacing*2)
     145        2688 :                 return nProofOfWorkLimit;
     146             :             else
     147             :             {
     148             :                 // Return the last non-special-min-difficulty-rules-block
     149       95150 :                 const CBlockIndex* pindex = pindexLast;
     150    20674696 :                 while (pindex->pprev && pindex->nHeight % params.DifficultyAdjustmentInterval() != 0 && pindex->nBits == nProofOfWorkLimit)
     151    20579546 :                     pindex = pindex->pprev;
     152       95150 :                 return pindex->nBits;
     153             :             }
     154             :         }
     155         156 :         return pindexLast->nBits;
     156             :     }
     157             : 
     158             :     // Go back by what we want to be 1 day worth of blocks
     159          72 :     int nHeightFirst = pindexLast->nHeight - (params.DifficultyAdjustmentInterval()-1);
     160          72 :     assert(nHeightFirst >= 0);
     161          72 :     const CBlockIndex* pindexFirst = pindexLast->GetAncestor(nHeightFirst);
     162          72 :     assert(pindexFirst);
     163             : 
     164          72 :    return CalculateNextWorkRequired(pindexLast, pindexFirst->GetBlockTime(), params);
     165       98066 : }
     166             : 
     167       98072 : unsigned int GetNextWorkRequired(const CBlockIndex* pindexLast, const CBlockHeader *pblock, const Consensus::Params& params)
     168             : {
     169       98072 :     assert(pindexLast != nullptr);
     170       98072 :     assert(pblock != nullptr);
     171       98072 :     const arith_uint256 bnPowLimit = UintToArith256(params.powLimit);
     172             : 
     173             :     // this is only active on devnets
     174       98072 :     if (pindexLast->nHeight < params.nMinimumDifficultyBlocks) {
     175           0 :         return bnPowLimit.GetCompact();
     176             :     }
     177             : 
     178       98072 :     if (pindexLast->nHeight + 1 < params.nPowKGWHeight) {
     179       98066 :         return GetNextWorkRequiredBTC(pindexLast, pblock, params);
     180             :     }
     181             : 
     182             :     // Note: GetNextWorkRequiredBTC has it's own special difficulty rule,
     183             :     // so we only apply this to post-BTC algos.
     184           6 :     if (params.fPowNoRetargeting) {
     185           0 :         return bnPowLimit.GetCompact();
     186             :     }
     187             : 
     188           6 :     if (params.fPowAllowMinDifficultyBlocks) {
     189             :         // recent block is more than 2 hours old
     190           5 :         if (pblock->GetBlockTime() > pindexLast->GetBlockTime() + 2 * 60 * 60) {
     191           2 :             return bnPowLimit.GetCompact();
     192             :         }
     193             :         // recent block is more than 10 minutes old
     194           3 :         if (pblock->GetBlockTime() > pindexLast->GetBlockTime() + params.nPowTargetSpacing * 4) {
     195           2 :             arith_uint256 bnNew = arith_uint256().SetCompact(pindexLast->nBits) * 10;
     196           2 :             if (bnNew > bnPowLimit) {
     197           0 :                 return bnPowLimit.GetCompact();
     198             :             }
     199           2 :             return bnNew.GetCompact();
     200             :         }
     201           1 :     }
     202             : 
     203           2 :     if (pindexLast->nHeight + 1 < params.nPowDGWHeight) {
     204           0 :         return KimotoGravityWell(pindexLast, params);
     205             :     }
     206             : 
     207           2 :     return DarkGravityWave(pindexLast, params);
     208       98072 : }
     209             : 
     210             : // for DIFF_BTC only!
     211          72 : unsigned int CalculateNextWorkRequired(const CBlockIndex* pindexLast, int64_t nFirstBlockTime, const Consensus::Params& params)
     212             : {
     213          72 :     if (params.fPowNoRetargeting)
     214          72 :         return pindexLast->nBits;
     215             : 
     216             :     // Limit adjustment step
     217           0 :     int64_t nActualTimespan = pindexLast->GetBlockTime() - nFirstBlockTime;
     218           0 :     if (nActualTimespan < params.nPowTargetTimespan/4)
     219           0 :         nActualTimespan = params.nPowTargetTimespan/4;
     220           0 :     if (nActualTimespan > params.nPowTargetTimespan*4)
     221           0 :         nActualTimespan = params.nPowTargetTimespan*4;
     222             : 
     223             :     // Retarget
     224           0 :     const arith_uint256 bnPowLimit = UintToArith256(params.powLimit);
     225           0 :     arith_uint256 bnNew;
     226           0 :     bnNew.SetCompact(pindexLast->nBits);
     227           0 :     bnNew *= nActualTimespan;
     228           0 :     bnNew /= params.nPowTargetTimespan;
     229             : 
     230           0 :     if (bnNew > bnPowLimit)
     231           0 :         bnNew = bnPowLimit;
     232             : 
     233           0 :     return bnNew.GetCompact();
     234          72 : }
     235             : 
     236      726510 : bool CheckProofOfWork(uint256 hash, unsigned int nBits, const Consensus::Params& params)
     237             : {
     238             :     bool fNegative;
     239             :     bool fOverflow;
     240      726510 :     arith_uint256 bnTarget;
     241             : 
     242      726510 :     bnTarget.SetCompact(nBits, &fNegative, &fOverflow);
     243             : 
     244             :     // Check range
     245      726510 :     if (fNegative || bnTarget == 0 || fOverflow || bnTarget > UintToArith256(params.powLimit))
     246           4 :         return false;
     247             : 
     248             :     // Check proof of work matches claimed amount
     249      726506 :     if (UintToArith256(hash) > bnTarget)
     250      607566 :         return false;
     251             : 
     252      118940 :     return true;
     253      726510 : }