src/kernel.cpp

   1 // Copyright (c) 2012-2013 The PPCoin developers
   2 // Distributed under the MIT/X11 software license, see the accompanying
   3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   4
   5 #include <boost/assign/list_of.hpp>
   6
   7 #include "kernel.h"
   8 #include "txdb.h"
   9
  10 extern unsigned int nStakeMaxAge;
  11 extern unsigned int nStakeTargetSpacing;
  12
  13 using namespace std;
  14
  15
  16 // Protocol switch time for fixed kernel modifier interval
  17 unsigned int nModifierSwitchTime  = 1413763200;    // Mon, 20 Oct 2014 00:00:00 GMT
  18 unsigned int nModifierTestSwitchTime = 1397520000; // Tue, 15 Apr 2014 00:00:00 GMT
  19
  20 // Note: user must upgrade before the protocol switch deadline, otherwise it's required to
  21 //   re-download the blockchain. The timestamp of upgrade is recorded in the blockchain
  22 //   database.
  23 unsigned int nModifierUpgradeTime = 0;
  24
  25 typedef std::map<int, unsigned int> MapModifierCheckpoints;
  26
  27 // Hard checkpoints of stake modifiers to ensure they are deterministic
  28 static std::map<int, unsigned int> mapStakeModifierCheckpoints =
  29     boost::assign::map_list_of
  30         ( 0, 0x0e00670bu )
  31         ( 12661, 0x5d84115du )
  32         (143990, 0x9c592c78u )
  33         (149000, 0x48f2bdc4u )
  34         (160000, 0x789df0f0u )
  35         (200000, 0x01ec1503u )
  36     ;
  37
  38 // Hard checkpoints of stake modifiers to ensure they are deterministic (testNet)
  39 static std::map<int, unsigned int> mapStakeModifierCheckpointsTestNet =
  40     boost::assign::map_list_of
  41         ( 0, 0x0e00670bu )
  42     ;
  43
  44 // Pregenerated entropy bits table (from genesis to #9689)
  45 //
  46 // Bits are packed into array of 256 bit integers:
  47 //
  48 // * array index calculated as nHeight / 256
  49 // * position of bit is calculated as nHeight & 0xFF.
  50 //
  51 const uint256 entropyStore[] = {
  52     uint256("0x4555b4dcc1d690ddd9b810c90c66e82b18bf4f43cc887246c418383ec120a5ab"),
  53     uint256("0xaa6d1198412fa77608addf6549c9198a22155e8afd7a9ded6179f6b7cfc66b0c"),
  54     uint256("0x9442fabfa4116fb14a9769c2eea003845a1f5c3a0260f36b497d68f3a3cd4078"),
  55     uint256("0x0e769042a9a98e42388195d699574b822d06515f7053ad884c53d7ee059f05b1"),
  56     uint256("0x7005aac20baf70251aebfe3f1b95987d83ef1e3e6963de8fed601d4dd07bf7cf"),
  57     uint256("0x58952c5c3de188f2e33c38d3f53d7bf44f9bc545a4289d266696273fa821be66"),
  58     uint256("0x50b6c2ed780c08aaec3f7665b1b6004206243e3866456fc910b83b52d07eeb63"),
  59     uint256("0x563841eefca85ba3384986c58100408ae3f1ba2ac727e1ac910ce154a06c702f"),
  60     uint256("0x79275b03938b3e27a9b01a7f7953c6c487c58355f5d4169accfbb800213ffd13"),
  61     uint256("0xd783f2538b3ed18f135af90adc687c5646d93aeaeaabc6667be94f7aa0a2d366"),
  62     uint256("0xb441d0c175c40c8e88b09d88ea008af79cbed2d28219427d2e72fda682974db8"),
  63     uint256("0x3204c43bd41f2e19628af3b0c9aca3db15bca4c8705d51056e7b17a319c04715"),
  64     uint256("0x7e80e6ab7857d8f2f261a0a49c783bd800b365b8c9b85cc0e13f73904b0dcaa9"),
  65     uint256("0xefaaee60ed82d2ad145c0e347941fdb131eb8fd289a45eef07121a93f283c5f1"),
  66     uint256("0x3efc86e4334da332c1fd4c12513c40cff689f3efdc7f9913230822adacdda4f9"),
  67     uint256("0xf0d6b8f38599a017fa35d1fbbf9ef51eca5ebc5b286aadba40c4c3e1d9bace0c"),
  68     uint256("0x286a67f27323486036a0a92d35382fc8963c0c00bad331723318b4b9fdb2b56e"),
  69     uint256("0xecbfaaa6567c54f08c4d5bd0118a2d7b58740f42cbfc73aa1536c1f5f76de87c"),
  70     uint256("0xf9a4de1c5c46520de5aaf10d3796cf0e27ddce98b3398357f5726a949664e308"),
  71     uint256("0xd75e6c4dc4be08401e3478d2467d9ab96a62af4f255c04a82c41af0de0a487bb"),
  72     uint256("0x1a82c3bc6ad6047294c16571b5e2b7316c97bf8813e7da15798b9820d67e39f2"),
  73     uint256("0xb49be0080de564e01829ded7e7971979565a741c5975dc9978dcc020192d396c"),
  74     uint256("0x0d8eed113be67663b5a15a0625a9b49792b5ea59c005c4f405914877acab7000"),
  75     uint256("0x8f9d46e2bc05a218ffa942965b747056197d393b097085523640cd59e07fe7c7"),
  76     uint256("0x7a63ab40bc7f40ac2ebe9ede438d97b45fa6ed6f8419016da8d5f7a670111dda"),
  77     uint256("0x63fbcc080448c43d6cf915c958314feff7a95a52ba43a68c05fc281d3a522d25"),
  78     uint256("0xf834cf824c326d3ea861ea1e85dc3289265e37045981e28208e7344a7f8081d7"),
  79     uint256("0xb4edc22ec98cc49b2f5af5bae3f52f5e6058280f74f2c432c2dd89ae49acceb8"),
  80     uint256("0x0fe596037dcf81bf5c64f39755261c404ed088af5c8c31dd7549b6657ee92365"),
  81     uint256("0xbbad51a0aeba254b01d18c328de9e932b9b859b61e622c325d64e2211b5e413d"),
  82     uint256("0xabf0194cc787be938bc51c7fdf1cae4ec79e65ebab8fa8b8f40541c44ef384b0"),
  83     uint256("0x83bc12d6fdbd3e854cb91c4ca7dfba3c38e8714121af88c8a8abdb33e5002438"),
  84     uint256("0x71a2513026cabaedcbe55aeb6dc8049e5b763a3f54f10c33dd333624f764b38c"),
  85     uint256("0xee6725632ff5c025dff6a18cd059875dcae20f399b03bccba13d9d5fcf6d9d9a"),
  86     uint256("0xa168a2741d1e7e50cc74b79f695c25ffd3576e6bd61353c2a20e569fd63b2dac"),
  87     uint256("0x6e462d2a87bfde9398b6747f94a8ed6a01e4d96c5b4372df5c910c106c48bd13"),
  88     uint256("0x8eeb696181957c4b22434028990f49cb30006827c73860e77e2eecf5c38be99d"),
  89     uint256("0x3188aaa65877b166f05cdc48f55b1f77a7d6fb221c395596d990ae5647e9ba96")
  90 };
  91
  92 // Whether the given block is subject to new modifier protocol
  93 bool IsFixedModifierInterval(unsigned int nTimeBlock)
  94 {
  95     return (nTimeBlock >= (fTestNet? nModifierTestSwitchTime : nModifierSwitchTime));
  96 }
  97
  98 // Get the last stake modifier and its generation time from a given block
  99 static bool GetLastStakeModifier(const CBlockIndex* pindex, uint64_t& nStakeModifier, int64_t& nModifierTime)
 100 {
 101     if (!pindex)
 102         return error("GetLastStakeModifier: null pindex");
 103     while (pindex && pindex->pprev && !pindex->GeneratedStakeModifier())
 104         pindex = pindex->pprev;
 105     if (!pindex->GeneratedStakeModifier())
 106         return error("GetLastStakeModifier: no generation at genesis block");
 107     nStakeModifier = pindex->nStakeModifier;
 108     nModifierTime = pindex->GetBlockTime();
 109     return true;
 110 }
 111
 112 // Get selection interval section (in seconds)
 113 static int64_t GetStakeModifierSelectionIntervalSection(int nSection)
 114 {
 115     assert (nSection >= 0 && nSection < 64);
 116     return (nModifierInterval * 63 / (63 + ((63 - nSection) * (MODIFIER_INTERVAL_RATIO - 1))));
 117 }
 118
 119 // Get stake modifier selection interval (in seconds)
 120 static int64_t GetStakeModifierSelectionInterval()
 121 {
 122     int64_t nSelectionInterval = 0;
 123     for (int nSection=0; nSection<64; nSection++)
 124         nSelectionInterval += GetStakeModifierSelectionIntervalSection(nSection);
 125     return nSelectionInterval;
 126 }
 127
 128 // select a block from the candidate blocks in vSortedByTimestamp, excluding
 129 // already selected blocks in vSelectedBlocks, and with timestamp up to
 130 // nSelectionIntervalStop.
 131 static bool SelectBlockFromCandidates(vector<pair<int64_t, uint256> >& vSortedByTimestamp, map<uint256, const CBlockIndex*>& mapSelectedBlocks,
 132     int64_t nSelectionIntervalStop, uint64_t nStakeModifierPrev, const CBlockIndex** pindexSelected)
 133 {
 134     bool fSelected = false;
 135     uint256 hashBest = 0;
 136     *pindexSelected = (const CBlockIndex*) 0;
 137     BOOST_FOREACH(const PAIRTYPE(int64_t, uint256)& item, vSortedByTimestamp)
 138     {
 139         if (!mapBlockIndex.count(item.second))
 140             return error("SelectBlockFromCandidates: failed to find block index for candidate block %s", item.second.ToString().c_str());
 141         const CBlockIndex* pindex = mapBlockIndex[item.second];
 142         if (fSelected && pindex->GetBlockTime() > nSelectionIntervalStop)
 143             break;
 144         if (mapSelectedBlocks.count(pindex->GetBlockHash()) > 0)
 145             continue;
 146         // compute the selection hash by hashing its proof-hash and the
 147         // previous proof-of-stake modifier
 148         uint256 hashProof = pindex->IsProofOfStake()? pindex->hashProofOfStake : pindex->GetBlockHash();
 149         CDataStream ss(SER_GETHASH, 0);
 150         ss << hashProof << nStakeModifierPrev;
 151         uint256 hashSelection = Hash(ss.begin(), ss.end());
 152         // the selection hash is divided by 2**32 so that proof-of-stake block
 153         // is always favored over proof-of-work block. this is to preserve
 154         // the energy efficiency property
 155         if (pindex->IsProofOfStake())
 156             hashSelection >>= 32;
 157         if (fSelected && hashSelection < hashBest)
 158         {
 159             hashBest = hashSelection;
 160             *pindexSelected = (const CBlockIndex*) pindex;
 161         }
 162         else if (!fSelected)
 163         {
 164             fSelected = true;
 165             hashBest = hashSelection;
 166             *pindexSelected = (const CBlockIndex*) pindex;
 167         }
 168     }
 169     if (fDebug && GetBoolArg("-printstakemodifier"))
 170         printf("SelectBlockFromCandidates: selection hash=%s\n", hashBest.ToString().c_str());
 171     return fSelected;
 172 }
 173
 174 // Stake Modifier (hash modifier of proof-of-stake):
 175 // The purpose of stake modifier is to prevent a txout (coin) owner from
 176 // computing future proof-of-stake generated by this txout at the time
 177 // of transaction confirmation. To meet kernel protocol, the txout
 178 // must hash with a future stake modifier to generate the proof.
 179 // Stake modifier consists of bits each of which is contributed from a
 180 // selected block of a given block group in the past.
 181 // The selection of a block is based on a hash of the block's proof-hash and
 182 // the previous stake modifier.
 183 // Stake modifier is recomputed at a fixed time interval instead of every
 184 // block. This is to make it difficult for an attacker to gain control of
 185 // additional bits in the stake modifier, even after generating a chain of
 186 // blocks.
 187 bool ComputeNextStakeModifier(const CBlockIndex* pindexCurrent, uint64_t& nStakeModifier, bool& fGeneratedStakeModifier)
 188 {
 189     nStakeModifier = 0;
 190     fGeneratedStakeModifier = false;
 191     const CBlockIndex* pindexPrev = pindexCurrent->pprev;
 192     if (!pindexPrev)
 193     {
 194         fGeneratedStakeModifier = true;
 195         return true;  // genesis block's modifier is 0
 196     }
 197
 198     // First find current stake modifier and its generation block time
 199     // if it's not old enough, return the same stake modifier
 200     int64_t nModifierTime = 0;
 201     if (!GetLastStakeModifier(pindexPrev, nStakeModifier, nModifierTime))
 202         return error("ComputeNextStakeModifier: unable to get last modifier");
 203     if (fDebug)
 204     {
 205         printf("ComputeNextStakeModifier: prev modifier=0x%016" PRIx64 " time=%s epoch=%u\n", nStakeModifier, DateTimeStrFormat(nModifierTime).c_str(), (unsigned int)nModifierTime);
 206     }
 207     if (nModifierTime / nModifierInterval >= pindexPrev->GetBlockTime() / nModifierInterval)
 208     {
 209         if (fDebug)
 210         {
 211             printf("ComputeNextStakeModifier: no new interval keep current modifier: pindexPrev nHeight=%d nTime=%u\n", pindexPrev->nHeight, (unsigned int)pindexPrev->GetBlockTime());
 212         }
 213         return true;
 214     }
 215     if (nModifierTime / nModifierInterval >= pindexCurrent->GetBlockTime() / nModifierInterval)
 216     {
 217         // fixed interval protocol requires current block timestamp also be in a different modifier interval
 218         if (IsFixedModifierInterval(pindexCurrent->nTime))
 219         {
 220             if (fDebug)
 221             {
 222                 printf("ComputeNextStakeModifier: no new interval keep current modifier: pindexCurrent nHeight=%d nTime=%u\n", pindexCurrent->nHeight, (unsigned int)pindexCurrent->GetBlockTime());
 223             }
 224             return true;
 225         }
 226         else
 227         {
 228             if (fDebug)
 229             {
 230                 printf("ComputeNextStakeModifier: old modifier at block %s not meeting fixed modifier interval: pindexCurrent nHeight=%d nTime=%u\n", pindexCurrent->GetBlockHash().ToString().c_str(), pindexCurrent->nHeight, (unsigned int)pindexCurrent->GetBlockTime());
 231             }
 232         }
 233     }
 234
 235     // Sort candidate blocks by timestamp
 236     vector<pair<int64_t, uint256> > vSortedByTimestamp;
 237     vSortedByTimestamp.reserve(64 * nModifierInterval / nStakeTargetSpacing);
 238     int64_t nSelectionInterval = GetStakeModifierSelectionInterval();
 239     int64_t nSelectionIntervalStart = (pindexPrev->GetBlockTime() / nModifierInterval) * nModifierInterval - nSelectionInterval;
 240     const CBlockIndex* pindex = pindexPrev;
 241     while (pindex && pindex->GetBlockTime() >= nSelectionIntervalStart)
 242     {
 243         vSortedByTimestamp.push_back(make_pair(pindex->GetBlockTime(), pindex->GetBlockHash()));
 244         pindex = pindex->pprev;
 245     }
 246     int nHeightFirstCandidate = pindex ? (pindex->nHeight + 1) : 0;
 247     reverse(vSortedByTimestamp.begin(), vSortedByTimestamp.end());
 248     sort(vSortedByTimestamp.begin(), vSortedByTimestamp.end());
 249
 250     // Select 64 blocks from candidate blocks to generate stake modifier
 251     uint64_t nStakeModifierNew = 0;
 252     int64_t nSelectionIntervalStop = nSelectionIntervalStart;
 253     map<uint256, const CBlockIndex*> mapSelectedBlocks;
 254     for (int nRound=0; nRound<min(64, (int)vSortedByTimestamp.size()); nRound++)
 255     {
 256         // add an interval section to the current selection round
 257         nSelectionIntervalStop += GetStakeModifierSelectionIntervalSection(nRound);
 258         // select a block from the candidates of current round
 259         if (!SelectBlockFromCandidates(vSortedByTimestamp, mapSelectedBlocks, nSelectionIntervalStop, nStakeModifier, &pindex))
 260             return error("ComputeNextStakeModifier: unable to select block at round %d", nRound);
 261         // write the entropy bit of the selected block
 262         nStakeModifierNew |= (((uint64_t)pindex->GetStakeEntropyBit()) << nRound);
 263         // add the selected block from candidates to selected list
 264         mapSelectedBlocks.insert(make_pair(pindex->GetBlockHash(), pindex));
 265         if (fDebug && GetBoolArg("-printstakemodifier"))
 266             printf("ComputeNextStakeModifier: selected round %d stop=%s height=%d bit=%d\n", nRound, DateTimeStrFormat(nSelectionIntervalStop).c_str(), pindex->nHeight, pindex->GetStakeEntropyBit());
 267     }
 268
 269     // Print selection map for visualization of the selected blocks
 270     if (fDebug && GetBoolArg("-printstakemodifier"))
 271     {
 272         string strSelectionMap = "";
 273         // '-' indicates proof-of-work blocks not selected
 274         strSelectionMap.insert(0, pindexPrev->nHeight - nHeightFirstCandidate + 1, '-');
 275         pindex = pindexPrev;
 276         while (pindex && pindex->nHeight >= nHeightFirstCandidate)
 277         {
 278             // '=' indicates proof-of-stake blocks not selected
 279             if (pindex->IsProofOfStake())
 280                 strSelectionMap.replace(pindex->nHeight - nHeightFirstCandidate, 1, "=");
 281             pindex = pindex->pprev;
 282         }
 283         BOOST_FOREACH(const PAIRTYPE(uint256, const CBlockIndex*)& item, mapSelectedBlocks)
 284         {
 285             // 'S' indicates selected proof-of-stake blocks
 286             // 'W' indicates selected proof-of-work blocks
 287             strSelectionMap.replace(item.second->nHeight - nHeightFirstCandidate, 1, item.second->IsProofOfStake()? "S" : "W");
 288         }
 289         printf("ComputeNextStakeModifier: selection height [%d, %d] map %s\n", nHeightFirstCandidate, pindexPrev->nHeight, strSelectionMap.c_str());
 290     }
 291     if (fDebug)
 292     {
 293         printf("ComputeNextStakeModifier: new modifier=0x%016" PRIx64 " time=%s\n", nStakeModifierNew, DateTimeStrFormat(pindexPrev->GetBlockTime()).c_str());
 294     }
 295
 296     nStakeModifier = nStakeModifierNew;
 297     fGeneratedStakeModifier = true;
 298     return true;
 299 }
 300
 301 // The stake modifier used to hash for a stake kernel is chosen as the stake
 302 // modifier about a selection interval later than the coin generating the kernel
 303 static bool GetKernelStakeModifier(uint256 hashBlockFrom, uint64_t& nStakeModifier, int& nStakeModifierHeight, int64_t& nStakeModifierTime, bool fPrintProofOfStake)
 304 {
 305     nStakeModifier = 0;
 306     if (!mapBlockIndex.count(hashBlockFrom))
 307         return error("GetKernelStakeModifier() : block not indexed");
 308     const CBlockIndex* pindexFrom = mapBlockIndex[hashBlockFrom];
 309     nStakeModifierHeight = pindexFrom->nHeight;
 310     nStakeModifierTime = pindexFrom->GetBlockTime();
 311     int64_t nStakeModifierSelectionInterval = GetStakeModifierSelectionInterval();
 312     const CBlockIndex* pindex = pindexFrom;
 313     // loop to find the stake modifier later by a selection interval
 314     while (nStakeModifierTime < pindexFrom->GetBlockTime() + nStakeModifierSelectionInterval)
 315     {
 316         if (!pindex->pnext)
 317         {   // reached best block; may happen if node is behind on block chain
 318             if (fPrintProofOfStake || (pindex->GetBlockTime() + nStakeMinAge - nStakeModifierSelectionInterval > GetAdjustedTime()))
 319                 return error("GetKernelStakeModifier() : reached best block %s at height %d from block %s",
 320                     pindex->GetBlockHash().ToString().c_str(), pindex->nHeight, hashBlockFrom.ToString().c_str());
 321             else
 322                 return false;
 323         }
 324         pindex = pindex->pnext;
 325         if (pindex->GeneratedStakeModifier())
 326         {
 327             nStakeModifierHeight = pindex->nHeight;
 328             nStakeModifierTime = pindex->GetBlockTime();
 329         }
 330     }
 331     nStakeModifier = pindex->nStakeModifier;
 332     return true;
 333 }
 334
 335 bool GetKernelStakeModifier(uint256 hashBlockFrom, uint64_t& nStakeModifier)
 336 {
 337     int nStakeModifierHeight;
 338     int64_t nStakeModifierTime;
 339
 340     return GetKernelStakeModifier(hashBlockFrom, nStakeModifier, nStakeModifierHeight, nStakeModifierTime, false);
 341 }
 342
 343
 344 // ppcoin kernel protocol
 345 // coinstake must meet hash target according to the protocol:
 346 // kernel (input 0) must meet the formula
 347 //     hash(nStakeModifier + txPrev.block.nTime + txPrev.offset + txPrev.nTime + txPrev.vout.n + nTime) < bnTarget * nCoinDayWeight
 348 // this ensures that the chance of getting a coinstake is proportional to the
 349 // amount of coin age one owns.
 350 // The reason this hash is chosen is the following:
 351 //   nStakeModifier: scrambles computation to make it very difficult to precompute
 352 //                  future proof-of-stake at the time of the coin's confirmation
 353 //   txPrev.block.nTime: prevent nodes from guessing a good timestamp to
 354 //                       generate transaction for future advantage
 355 //   txPrev.offset: offset of txPrev inside block, to reduce the chance of
 356 //                  nodes generating coinstake at the same time
 357 //   txPrev.nTime: reduce the chance of nodes generating coinstake at the same
 358 //                 time
 359 //   txPrev.vout.n: output number of txPrev, to reduce the chance of nodes
 360 //                  generating coinstake at the same time
 361 //   block/tx hash should not be used here as they can be generated in vast
 362 //   quantities so as to generate blocks faster, degrading the system back into
 363 //   a proof-of-work situation.
 364 //
 365 bool CheckStakeKernelHash(uint32_t nBits, const CBlock& blockFrom, uint32_t nTxPrevOffset, const CTransaction& txPrev, const COutPoint& prevout, uint32_t nTimeTx, uint256& hashProofOfStake, uint256& targetProofOfStake, bool fPrintProofOfStake)
 366 {
 367     if (nTimeTx < txPrev.nTime)  // Transaction timestamp violation
 368         return error("CheckStakeKernelHash() : nTime violation");
 369
 370     uint32_t nTimeBlockFrom = blockFrom.GetBlockTime();
 371     if (nTimeBlockFrom + nStakeMinAge > nTimeTx) // Min age requirement
 372         return error("CheckStakeKernelHash() : min age violation");
 373
 374     CBigNum bnTargetPerCoinDay;
 375     bnTargetPerCoinDay.SetCompact(nBits);
 376     int64_t nValueIn = txPrev.vout[prevout.n].nValue;
 377
 378     uint256 hashBlockFrom = blockFrom.GetHash();
 379
 380     CBigNum bnCoinDayWeight = CBigNum(nValueIn) * GetWeight((int64_t)txPrev.nTime, (int64_t)nTimeTx) / COIN / nOneDay;
 381     targetProofOfStake = (bnCoinDayWeight * bnTargetPerCoinDay).getuint256();
 382
 383     // Calculate hash
 384     CDataStream ss(SER_GETHASH, 0);
 385     uint64_t nStakeModifier = 0;
 386     int nStakeModifierHeight = 0;
 387     int64_t nStakeModifierTime = 0;
 388
 389     if (!GetKernelStakeModifier(hashBlockFrom, nStakeModifier, nStakeModifierHeight, nStakeModifierTime, fPrintProofOfStake))
 390         return false;
 391     ss << nStakeModifier;
 392
 393     ss << nTimeBlockFrom << nTxPrevOffset << txPrev.nTime << prevout.n << nTimeTx;
 394     hashProofOfStake = Hash(ss.begin(), ss.end());
 395     if (fPrintProofOfStake)
 396     {
 397         printf("CheckStakeKernelHash() : using modifier 0x%016" PRIx64 " at height=%d timestamp=%s for block from height=%d timestamp=%s\n",
 398             nStakeModifier, nStakeModifierHeight,
 399             DateTimeStrFormat(nStakeModifierTime).c_str(),
 400             mapBlockIndex[hashBlockFrom]->nHeight,
 401             DateTimeStrFormat(blockFrom.GetBlockTime()).c_str());
 402         printf("CheckStakeKernelHash() : check modifier=0x%016" PRIx64 " nTimeBlockFrom=%u nTxPrevOffset=%u nTimeTxPrev=%u nPrevout=%u nTimeTx=%u hashTarget=%s hashProof=%s\n",
 403             nStakeModifier,
 404             nTimeBlockFrom, nTxPrevOffset, txPrev.nTime, prevout.n, nTimeTx,
 405             targetProofOfStake.ToString().c_str(), hashProofOfStake.ToString().c_str());
 406     }
 407
 408     // Now check if proof-of-stake hash meets target protocol
 409     if (CBigNum(hashProofOfStake) > bnCoinDayWeight * bnTargetPerCoinDay)
 410         return false;
 411     if (fDebug && !fPrintProofOfStake)
 412     {
 413         printf("CheckStakeKernelHash() : using modifier 0x%016" PRIx64 " at height=%d timestamp=%s for block from height=%d timestamp=%s\n",
 414             nStakeModifier, nStakeModifierHeight,
 415             DateTimeStrFormat(nStakeModifierTime).c_str(),
 416             mapBlockIndex[hashBlockFrom]->nHeight,
 417             DateTimeStrFormat(blockFrom.GetBlockTime()).c_str());
 418         printf("CheckStakeKernelHash() : pass modifier=0x%016" PRIx64 " nTimeBlockFrom=%u nTxPrevOffset=%u nTimeTxPrev=%u nPrevout=%u nTimeTx=%u hashTarget=%s hashProof=%s\n",
 419             nStakeModifier,
 420             nTimeBlockFrom, nTxPrevOffset, txPrev.nTime, prevout.n, nTimeTx,
 421             targetProofOfStake.ToString().c_str(), hashProofOfStake.ToString().c_str());
 422     }
 423     return true;
 424 }
 425
 426
 427 #ifdef USE_ASM
 428
 429 // kernel padding
 430 static const uint32_t block1_suffix[9] = { 0x80000000, 0, 0, 0, 0, 0, 0, 0, 0xe0000000 };
 431 static const uint32_t block1_suffix_4way[4 * 9] = {
 432     0x00000080, 0x00000080, 0x00000080, 0x00000080,
 433     0, 0, 0, 0,
 434     0, 0, 0, 0,
 435     0, 0, 0, 0,
 436     0, 0, 0, 0,
 437     0, 0, 0, 0,
 438     0, 0, 0, 0,
 439     0, 0, 0, 0,
 440     0xe0000000, 0xe0000000, 0xe0000000, 0xe0000000
 441 };
 442
 443 // hash padding
 444 static const uint32_t block2_suffix[8] = { 0x80000000, 0, 0, 0, 0, 0, 0, 0x00010000 };
 445 static const uint32_t block2_suffix_4way[4 * 8] = {
 446     0x00000080, 0x00000080, 0x00000080, 0x00000080,
 447     0, 0, 0, 0,
 448     0, 0, 0, 0,
 449     0, 0, 0, 0,
 450     0, 0, 0, 0,
 451     0, 0, 0, 0,
 452     0, 0, 0, 0,
 453     0x00010000, 0x00010000, 0x00010000, 0x00010000
 454 };
 455
 456 extern "C" int sha256_use_4way();
 457
 458 extern "C" void sha256_init(uint32_t *state);
 459 extern "C" void sha256_transform(uint32_t *state, const uint32_t *block, int swap);
 460
 461 extern "C" void sha256_init_4way(uint32_t *state);
 462 extern "C" void sha256_transform_4way(uint32_t *state, const uint32_t *block, int swap);
 463
 464 bool fUse4Way = sha256_use_4way() != 0;
 465
 466 class ScanMidstateWorker
 467 {
 468 public:
 469     ScanMidstateWorker()
 470     { }
 471     ScanMidstateWorker(unsigned char *kernel, uint32_t nBits, uint32_t nInputTxTime, int64_t nValueIn, uint32_t nIntervalBegin, uint32_t nIntervalEnd)
 472         : kernel(kernel), nBits(nBits), nInputTxTime(nInputTxTime), bnValueIn(nValueIn), nIntervalBegin(nIntervalBegin), nIntervalEnd(nIntervalEnd)
 473     {
 474         solutions = vector<std::pair<uint256,uint32_t> >();
 475     }
 476
 477     void Do_4way()
 478     {
 479         SetThreadPriority(THREAD_PRIORITY_LOWEST);
 480
 481         // Compute maximum possible target to filter out majority of obviously insufficient hashes
 482         CBigNum bnTargetPerCoinDay;
 483         bnTargetPerCoinDay.SetCompact(nBits);
 484         uint256 nMaxTarget = (bnTargetPerCoinDay * bnValueIn * nStakeMaxAge / COIN / nOneDay).getuint256();
 485
 486         uint32_t state1[4 * 8] __attribute__((aligned(16)));
 487         uint32_t state2[4 * 8] __attribute__((aligned(16)));
 488         uint32_t blocks1[4 * 16] __attribute__((aligned(16)));
 489         uint32_t blocks2[4 * 16] __attribute__((aligned(16)));
 490
 491         vector<uint32_t> vRow = vector<uint32_t>(4);
 492         uint32_t *pnKernel = (uint32_t *) kernel;
 493
 494         for(int i = 0; i < 7; i++)
 495         {
 496             uint32_t nVal = pnKernel[i];
 497             fill(vRow.begin(), vRow.end(), nVal);
 498
 499             for (int j = 0; j < 4; j++)
 500             {
 501                 memcpy(&blocks1[i*4], &vRow[0], 16);
 502             }
 503         }
 504
 505         memcpy(&blocks1[28], &block1_suffix_4way[0], 36*4);   // sha256 padding
 506         memcpy(&blocks2[32], &block2_suffix_4way[0], 32*4);
 507
 508         // Search forward in time from the given timestamp
 509         // Stopping search in case of shutting down
 510         for (uint32_t nTimeTx=nIntervalBegin, nMaxTarget32 = nMaxTarget.Get32(7); nTimeTx<nIntervalEnd && !fShutdown; )
 511         {
 512             sha256_init_4way(state1);
 513             sha256_init_4way(state2);
 514
 515             blocks1[24] = nTimeTx;
 516             blocks1[25] = ++nTimeTx;
 517             blocks1[26] = ++nTimeTx;
 518             blocks1[27] = ++nTimeTx;
 519
 520             sha256_transform_4way(&state1[0], &blocks1[0], 1); // first hashing
 521
 522             for(int i=0; i<32; i++)
 523                 blocks2[i] = __builtin_bswap32(state1[i]);
 524
 525             sha256_transform_4way(&state2[0], &blocks2[0], 1); // second hashing
 526
 527             for(int nResult = 0; nResult < 4; nResult++)
 528             {
 529                 uint32_t nTime = blocks1[24+nResult];
 530                 uint32_t nHash = __builtin_bswap32(state2[28+nResult]);
 531
 532                 if (nHash <= nMaxTarget32) // Possible hit
 533                 {
 534                     uint256 nHashProofOfStake = 0;
 535                     uint32_t *pnHashProofOfStake = (uint32_t *) &nHashProofOfStake;
 536                     pnHashProofOfStake[7] = nHash;
 537
 538                     for (int i = 0; i < 7; i++)
 539                         pnHashProofOfStake[i] = __builtin_bswap32(state2[(i*4) + nResult]);
 540
 541                     CBigNum bnCoinDayWeight = bnValueIn * GetWeight((int64_t)nInputTxTime, (int64_t)nTimeTx) / COIN / nOneDay;
 542                     CBigNum bnTargetProofOfStake = bnCoinDayWeight * bnTargetPerCoinDay;
 543
 544                     if (bnTargetProofOfStake >= CBigNum(nHashProofOfStake))
 545                         solutions.push_back(std::pair<uint256,uint32_t>(nHashProofOfStake, nTime));
 546                 }
 547             }
 548         }
 549     }
 550
 551     void Do_generic()
 552     {
 553         SetThreadPriority(THREAD_PRIORITY_LOWEST);
 554
 555         // Init new sha256 context and update it
 556         //   with first 24 bytes of kernel
 557         SHA256_CTX workerCtx;
 558         SHA256_Init(&workerCtx);
 559         SHA256_Update(&workerCtx, kernel, 8 + 16);
 560         SHA256_CTX ctx = workerCtx;
 561
 562         // Sha256 result buffer
 563         uint32_t hashProofOfStake[8];
 564
 565         // Compute maximum possible target to filter out majority of obviously insufficient hashes
 566         CBigNum bnTargetPerCoinDay;
 567         bnTargetPerCoinDay.SetCompact(nBits);
 568
 569         uint256 nMaxTarget = (bnTargetPerCoinDay * bnValueIn * nStakeMaxAge / COIN / nOneDay).getuint256(),
 570             *pnHashProofOfStake = (uint256 *)&hashProofOfStake;
 571
 572         // Search forward in time from the given timestamp
 573         // Stopping search in case of shutting down
 574         for (uint32_t nTimeTx=nIntervalBegin, nMaxTarget32 = nMaxTarget.Get32(7); nTimeTx<nIntervalEnd && !fShutdown; nTimeTx++)
 575         {
 576             // Complete first hashing iteration
 577             uint256 hash1;
 578             SHA256_Update(&ctx, (unsigned char*)&nTimeTx, 4);
 579             SHA256_Final((unsigned char*)&hash1, &ctx);
 580
 581             // Restore context
 582             ctx = workerCtx;
 583
 584             // Finally, calculate kernel hash
 585             SHA256((unsigned char*)&hash1, sizeof(hashProofOfStake), (unsigned char*)&hashProofOfStake);
 586
 587             // Skip if hash doesn't satisfy the maximum target
 588             if (hashProofOfStake[7] > nMaxTarget32)
 589                 continue;
 590
 591             CBigNum bnCoinDayWeight = bnValueIn * GetWeight((int64_t)nInputTxTime, (int64_t)nTimeTx) / COIN / nOneDay;
 592             CBigNum bnTargetProofOfStake = bnCoinDayWeight * bnTargetPerCoinDay;
 593
 594             if (bnTargetProofOfStake >= CBigNum(*pnHashProofOfStake))
 595                 solutions.push_back(std::pair<uint256,uint32_t>(*pnHashProofOfStake, nTimeTx));
 596         }
 597     }
 598
 599     void Do()
 600     {
 601         if (fUse4Way)
 602             Do_4way();
 603         else
 604             Do_generic();
 605     }
 606
 607     vector<std::pair<uint256,uint32_t> >& GetSolutions()
 608     {
 609         return solutions;
 610     }
 611
 612 private:
 613     std::vector<std::pair<uint256,uint32_t> > solutions;
 614
 615     uint8_t *kernel;
 616     uint32_t nBits;
 617     uint32_t nInputTxTime;
 618     CBigNum  bnValueIn;
 619     uint32_t nIntervalBegin;
 620     uint32_t nIntervalEnd;
 621 };
 622
 623 #else
 624 class ScanMidstateWorker
 625 {
 626 public:
 627     ScanMidstateWorker()
 628     { }
 629     ScanMidstateWorker(unsigned char *kernel, uint32_t nBits, uint32_t nInputTxTime, int64_t nValueIn, uint32_t nIntervalBegin, uint32_t nIntervalEnd)
 630         : nBits(nBits), nInputTxTime(nInputTxTime), bnValueIn(nValueIn), nIntervalBegin(nIntervalBegin), nIntervalEnd(nIntervalEnd)
 631     {
 632         // Init new sha256 context and update it
 633         //   with first 24 bytes of kernel
 634         SHA256_Init(&workerCtx);
 635         SHA256_Update(&workerCtx, kernel, 8 + 16);
 636         solutions = vector<std::pair<uint256,uint32_t> >();
 637     }
 638
 639     void Do()
 640     {
 641         SetThreadPriority(THREAD_PRIORITY_LOWEST);
 642         SHA256_CTX ctx = workerCtx;
 643
 644         // Sha256 result buffer
 645         uint32_t hashProofOfStake[8];
 646
 647         // Compute maximum possible target to filter out majority of obviously insufficient hashes
 648         CBigNum bnTargetPerCoinDay;
 649         bnTargetPerCoinDay.SetCompact(nBits);
 650
 651         uint256 nMaxTarget = (bnTargetPerCoinDay * bnValueIn * nStakeMaxAge / COIN / nOneDay).getuint256(),
 652             *pnHashProofOfStake = (uint256 *)&hashProofOfStake;
 653
 654         // Search forward in time from the given timestamp
 655         // Stopping search in case of shutting down
 656         for (uint32_t nTimeTx=nIntervalBegin, nMaxTarget32 = nMaxTarget.Get32(7); nTimeTx<nIntervalEnd && !fShutdown; nTimeTx++)
 657         {
 658             // Complete first hashing iteration
 659             uint256 hash1;
 660             SHA256_Update(&ctx, (unsigned char*)&nTimeTx, 4);
 661             SHA256_Final((unsigned char*)&hash1, &ctx);
 662
 663             // Restore context
 664             ctx = workerCtx;
 665
 666             // Finally, calculate kernel hash
 667             SHA256((unsigned char*)&hash1, sizeof(hashProofOfStake), (unsigned char*)&hashProofOfStake);
 668
 669             // Skip if hash doesn't satisfy the maximum target
 670             if (hashProofOfStake[7] > nMaxTarget32)
 671                 continue;
 672
 673             CBigNum bnCoinDayWeight = bnValueIn * GetWeight((int64_t)nInputTxTime, (int64_t)nTimeTx) / COIN / nOneDay;
 674             CBigNum bnTargetProofOfStake = bnCoinDayWeight * bnTargetPerCoinDay;
 675
 676             if (bnTargetProofOfStake >= CBigNum(*pnHashProofOfStake))
 677                 solutions.push_back(std::pair<uint256,uint32_t>(*pnHashProofOfStake, nTimeTx));
 678         }
 679     }
 680
 681     vector<std::pair<uint256,uint32_t> >& GetSolutions()
 682     {
 683         return solutions;
 684     }
 685
 686 private:
 687     SHA256_CTX workerCtx;
 688     std::vector<std::pair<uint256,uint32_t> > solutions;
 689
 690     uint32_t nBits;
 691     uint32_t nInputTxTime;
 692     CBigNum  bnValueIn;
 693     uint32_t nIntervalBegin;
 694     uint32_t nIntervalEnd;
 695 };
 696
 697 #endif
 698 // Scan given kernel for solution
 699 bool ScanKernelForward(unsigned char *kernel, uint32_t nBits, uint32_t nInputTxTime, int64_t nValueIn, std::pair<uint32_t, uint32_t> &SearchInterval, std::vector<std::pair<uint256, uint32_t> > &solutions)
 700 {
 701     // TODO: custom threads amount
 702
 703     uint32_t nThreads = boost::thread::hardware_concurrency();
 704     uint32_t nPart = (SearchInterval.second - SearchInterval.first) / nThreads;
 705
 706
 707     ScanMidstateWorker *workers = new ScanMidstateWorker[nThreads];
 708
 709     boost::thread_group group;
 710     for(size_t i = 0; i < nThreads; i++)
 711     {
 712         uint32_t nBegin = SearchInterval.first + nPart * i;
 713         uint32_t nEnd = SearchInterval.first + nPart * (i + 1);
 714         workers[i] = ScanMidstateWorker(kernel, nBits, nInputTxTime, nValueIn, nBegin, nEnd);
 715         boost::function<void()> workerFnc = boost::bind(&ScanMidstateWorker::Do, &workers[i]);
 716         group.create_thread(workerFnc);
 717     }
 718
 719     group.join_all();
 720     solutions.clear();
 721
 722     for(size_t i = 0; i < nThreads; i++)
 723     {
 724         std::vector<std::pair<uint256, uint32_t> > ws = workers[i].GetSolutions();
 725         solutions.insert(solutions.end(), ws.begin(), ws.end());
 726     }
 727
 728     delete [] workers;
 729
 730     if (solutions.size() == 0)
 731     {
 732         // no solutions
 733         return false;
 734     }
 735
 736     return true;
 737 }
 738
 739 // Scan given midstate for solution
 740 bool ScanContextBackward(SHA256_CTX &ctx, uint32_t nBits, uint32_t nInputTxTime, int64_t nValueIn, std::pair<uint32_t, uint32_t> &SearchInterval, std::pair<uint256, uint32_t> &solution)
 741 {
 742     CBigNum bnTargetPerCoinDay;
 743     bnTargetPerCoinDay.SetCompact(nBits);
 744
 745     // Get maximum possible target to filter out the majority of obviously insufficient hashes
 746     CBigNum bnMaxTargetPerCoinDay = bnTargetPerCoinDay * CBigNum(nValueIn) * nStakeMaxAge / COIN / nOneDay;
 747     uint256 maxTarget = bnMaxTargetPerCoinDay.getuint256();
 748
 749     SHA256_CTX ctxCopy = ctx;
 750
 751     // Search backward in time from the given timestamp
 752     // Stopping search in case of shutting down
 753     for (uint32_t nTimeTx=SearchInterval.first; nTimeTx>SearchInterval.second && !fShutdown; nTimeTx--)
 754     {
 755         // Complete first hashing iteration
 756         uint256 hash1;
 757         SHA256_Update(&ctxCopy, (unsigned char*)&nTimeTx, 4);
 758         SHA256_Final((unsigned char*)&hash1, &ctxCopy);
 759
 760         // Restore context
 761         ctxCopy = ctx;
 762
 763         // Finally, calculate kernel hash
 764         uint256 hashProofOfStake;
 765         SHA256((unsigned char*)&hash1, sizeof(hashProofOfStake), (unsigned char*)&hashProofOfStake);
 766
 767         // Skip if hash doesn't satisfy the maximum target
 768         if (hashProofOfStake > maxTarget)
 769             continue;
 770
 771         CBigNum bnCoinDayWeight = CBigNum(nValueIn) * GetWeight((int64_t)nInputTxTime, (int64_t)nTimeTx) / COIN / nOneDay;
 772         CBigNum bnTargetProofOfStake = bnCoinDayWeight * bnTargetPerCoinDay;
 773
 774         if (bnTargetProofOfStake >= CBigNum(hashProofOfStake))
 775         {
 776             solution.first = hashProofOfStake;
 777             solution.second = nTimeTx;
 778
 779             return true;
 780         }
 781     }
 782
 783     return false;
 784 }
 785
 786 // Check kernel hash target and coinstake signature
 787 bool CheckProofOfStake(const CTransaction& tx, unsigned int nBits, uint256& hashProofOfStake, uint256& targetProofOfStake)
 788 {
 789     if (!tx.IsCoinStake())
 790         return error("CheckProofOfStake() : called on non-coinstake %s", tx.GetHash().ToString().c_str());
 791
 792     // Kernel (input 0) must match the stake hash target per coin age (nBits)
 793     const CTxIn& txin = tx.vin[0];
 794
 795     // First try finding the previous transaction in database
 796     CTxDB txdb("r");
 797     CTransaction txPrev;
 798     CTxIndex txindex;
 799     if (!txPrev.ReadFromDisk(txdb, txin.prevout, txindex))
 800         return tx.DoS(1, error("CheckProofOfStake() : INFO: read txPrev failed"));  // previous transaction not in main chain, may occur during initial download
 801
 802 #ifndef USE_LEVELDB
 803     txdb.Close();
 804 #endif
 805
 806     // Verify signature
 807     if (!VerifySignature(txPrev, tx, 0, MANDATORY_SCRIPT_VERIFY_FLAGS, 0))
 808         return tx.DoS(100, error("CheckProofOfStake() : VerifySignature failed on coinstake %s", tx.GetHash().ToString().c_str()));
 809
 810     // Read block header
 811     CBlock block;
 812     if (!block.ReadFromDisk(txindex.pos.nFile, txindex.pos.nBlockPos, false))
 813         return fDebug? error("CheckProofOfStake() : read block failed") : false; // unable to read block of previous transaction
 814
 815     if (!CheckStakeKernelHash(nBits, block, txindex.pos.nTxPos - txindex.pos.nBlockPos, txPrev, txin.prevout, tx.nTime, hashProofOfStake, targetProofOfStake, fDebug))
 816         return tx.DoS(1, error("CheckProofOfStake() : INFO: check kernel failed on coinstake %s, hashProof=%s", tx.GetHash().ToString().c_str(), hashProofOfStake.ToString().c_str())); // may occur during initial download or if behind on block chain sync
 817
 818     return true;
 819 }
 820
 821 // Get stake modifier checksum
 822 uint32_t GetStakeModifierChecksum(const CBlockIndex* pindex)
 823 {
 824     assert (pindex->pprev || pindex->GetBlockHash() == (!fTestNet ? hashGenesisBlock : hashGenesisBlockTestNet));
 825     // Hash previous checksum with flags, hashProofOfStake and nStakeModifier
 826     CDataStream ss(SER_GETHASH, 0);
 827     if (pindex->pprev)
 828         ss << pindex->pprev->nStakeModifierChecksum;
 829     ss << pindex->nFlags << pindex->hashProofOfStake << pindex->nStakeModifier;
 830     uint256 hashChecksum = Hash(ss.begin(), ss.end());
 831     hashChecksum >>= (256 - 32);
 832     return static_cast<uint32_t>(hashChecksum.Get64());
 833 }
 834
 835 // Check stake modifier hard checkpoints
 836 bool CheckStakeModifierCheckpoints(int nHeight, uint32_t nStakeModifierChecksum)
 837 {
 838     MapModifierCheckpoints& checkpoints = (fTestNet ? mapStakeModifierCheckpointsTestNet : mapStakeModifierCheckpoints);
 839
 840     if (checkpoints.count(nHeight))
 841         return nStakeModifierChecksum == checkpoints[nHeight];
 842     return true;
 843 }