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 class ScanMidstateWorker
 465 {
 466 public:
 467     ScanMidstateWorker()
 468     { }
 469     ScanMidstateWorker(unsigned char *kernel, uint32_t nBits, uint32_t nInputTxTime, int64_t nValueIn, uint32_t nIntervalBegin, uint32_t nIntervalEnd)
 470         : kernel(kernel), nBits(nBits), nInputTxTime(nInputTxTime), bnValueIn(nValueIn), nIntervalBegin(nIntervalBegin), nIntervalEnd(nIntervalEnd)
 471     {
 472         solutions = vector<std::pair<uint256,uint32_t> >();
 473     }
 474
 475     void Do_4way()
 476     {
 477         SetThreadPriority(THREAD_PRIORITY_LOWEST);
 478
 479         // Compute maximum possible target to filter out majority of obviously insufficient hashes
 480         CBigNum bnTargetPerCoinDay;
 481         bnTargetPerCoinDay.SetCompact(nBits);
 482         uint256 nMaxTarget = (bnTargetPerCoinDay * bnValueIn * nStakeMaxAge / COIN / nOneDay).getuint256();
 483
 484         uint32_t state1[4 * 8] __attribute__((aligned(16)));
 485         uint32_t state2[4 * 8] __attribute__((aligned(16)));
 486         uint32_t blocks1[4 * 16] __attribute__((aligned(16)));
 487         uint32_t blocks2[4 * 16] __attribute__((aligned(16)));
 488
 489         vector<uint32_t> vRow = vector<uint32_t>(4);
 490         uint32_t *pnKernel = (uint32_t *) kernel;
 491
 492         for(int i = 0; i < 7; i++)
 493         {
 494             uint32_t nVal = pnKernel[i];
 495             fill(vRow.begin(), vRow.end(), nVal);
 496
 497             for (int j = 0; j < 4; j++)
 498             {
 499                 memcpy(&blocks1[i*4], &vRow[0], 16);
 500             }
 501         }
 502
 503         memcpy(&blocks1[28], &block1_suffix_4way[0], 36*4);   // sha256 padding
 504         memcpy(&blocks2[32], &block2_suffix_4way[0], 32*4);
 505
 506         // Search forward in time from the given timestamp
 507         // Stopping search in case of shutting down
 508         for (uint32_t nTimeTx=nIntervalBegin, nMaxTarget32 = nMaxTarget.Get32(7); nTimeTx<nIntervalEnd && !fShutdown; nTimeTx+=4)
 509         {
 510             for (int n = 0; n < 4; n++)
 511                 blocks1[24+n] = nTimeTx + n;
 512
 513             sha256_init_4way(state1);
 514             sha256_init_4way(state2);
 515             sha256_transform_4way(&state1[0], &blocks1[0], 1); // first hashing
 516
 517             for(int i=0; i<32; i++)
 518                 blocks2[i] = __builtin_bswap32(state1[i]);
 519
 520             sha256_transform_4way(&state2[0], &blocks2[0], 1); // second hashing
 521
 522             for(int n = 0; n < 4; n++)
 523             {
 524                 uint32_t nTime = blocks1[24+n];
 525                 uint32_t nHash = __builtin_bswap32(state2[28+n]);
 526
 527                 if (nHash <= nMaxTarget32) // Possible hit
 528                 {
 529                     uint256 nHashProofOfStake = 0;
 530                     uint32_t *pnHashProofOfStake = (uint32_t *) &nHashProofOfStake;
 531                     pnHashProofOfStake[7] = nHash;
 532
 533                     for (int i = 0; i < 7; i++)
 534                         pnHashProofOfStake[i] = __builtin_bswap32(state2[(i*4) + n]);
 535
 536                     CBigNum bnCoinDayWeight = bnValueIn * GetWeight((int64_t)nInputTxTime, (int64_t)nTimeTx) / COIN / nOneDay;
 537                     CBigNum bnTargetProofOfStake = bnCoinDayWeight * bnTargetPerCoinDay;
 538
 539                     if (bnTargetProofOfStake >= CBigNum(nHashProofOfStake))
 540                         solutions.push_back(std::pair<uint256,uint32_t>(nHashProofOfStake, nTime));
 541                 }
 542             }
 543         }
 544     }
 545
 546     void Do_generic()
 547     {
 548         SetThreadPriority(THREAD_PRIORITY_LOWEST);
 549
 550         // Init new sha256 context and update it
 551         //   with first 24 bytes of kernel
 552         SHA256_CTX workerCtx;
 553         SHA256_Init(&workerCtx);
 554         SHA256_Update(&workerCtx, kernel, 8 + 16);
 555         SHA256_CTX ctx = workerCtx;
 556
 557         // Sha256 result buffer
 558         uint32_t hashProofOfStake[8];
 559
 560         // Compute maximum possible target to filter out majority of obviously insufficient hashes
 561         CBigNum bnTargetPerCoinDay;
 562         bnTargetPerCoinDay.SetCompact(nBits);
 563
 564         uint256 nMaxTarget = (bnTargetPerCoinDay * bnValueIn * nStakeMaxAge / COIN / nOneDay).getuint256(),
 565             *pnHashProofOfStake = (uint256 *)&hashProofOfStake;
 566
 567         // Search forward in time from the given timestamp
 568         // Stopping search in case of shutting down
 569         for (uint32_t nTimeTx=nIntervalBegin, nMaxTarget32 = nMaxTarget.Get32(7); nTimeTx<nIntervalEnd && !fShutdown; nTimeTx++)
 570         {
 571             // Complete first hashing iteration
 572             uint256 hash1;
 573             SHA256_Update(&ctx, (unsigned char*)&nTimeTx, 4);
 574             SHA256_Final((unsigned char*)&hash1, &ctx);
 575
 576             // Restore context
 577             ctx = workerCtx;
 578
 579             // Finally, calculate kernel hash
 580             SHA256((unsigned char*)&hash1, sizeof(hashProofOfStake), (unsigned char*)&hashProofOfStake);
 581
 582             // Skip if hash doesn't satisfy the maximum target
 583             if (hashProofOfStake[7] > nMaxTarget32)
 584                 continue;
 585
 586             CBigNum bnCoinDayWeight = bnValueIn * GetWeight((int64_t)nInputTxTime, (int64_t)nTimeTx) / COIN / nOneDay;
 587             CBigNum bnTargetProofOfStake = bnCoinDayWeight * bnTargetPerCoinDay;
 588
 589             if (bnTargetProofOfStake >= CBigNum(*pnHashProofOfStake))
 590                 solutions.push_back(std::pair<uint256,uint32_t>(*pnHashProofOfStake, nTimeTx));
 591         }
 592     }
 593
 594     void Do()
 595     {
 596         if (sha256_use_4way() != 0)
 597             Do_4way();
 598         Do_generic();
 599     }
 600
 601     vector<std::pair<uint256,uint32_t> >& GetSolutions()
 602     {
 603         return solutions;
 604     }
 605
 606 private:
 607     std::vector<std::pair<uint256,uint32_t> > solutions;
 608
 609     uint8_t *kernel;
 610     uint32_t nBits;
 611     uint32_t nInputTxTime;
 612     CBigNum  bnValueIn;
 613     uint32_t nIntervalBegin;
 614     uint32_t nIntervalEnd;
 615 };
 616
 617 #else
 618 class ScanMidstateWorker
 619 {
 620 public:
 621     ScanMidstateWorker()
 622     { }
 623     ScanMidstateWorker(unsigned char *kernel, uint32_t nBits, uint32_t nInputTxTime, int64_t nValueIn, uint32_t nIntervalBegin, uint32_t nIntervalEnd)
 624         : nBits(nBits), nInputTxTime(nInputTxTime), bnValueIn(nValueIn), nIntervalBegin(nIntervalBegin), nIntervalEnd(nIntervalEnd)
 625     {
 626         // Init new sha256 context and update it
 627         //   with first 24 bytes of kernel
 628         SHA256_Init(&workerCtx);
 629         SHA256_Update(&workerCtx, kernel, 8 + 16);
 630         solutions = vector<std::pair<uint256,uint32_t> >();
 631     }
 632
 633     void Do()
 634     {
 635         SetThreadPriority(THREAD_PRIORITY_LOWEST);
 636         SHA256_CTX ctx = workerCtx;
 637
 638         // Sha256 result buffer
 639         uint32_t hashProofOfStake[8];
 640
 641         // Compute maximum possible target to filter out majority of obviously insufficient hashes
 642         CBigNum bnTargetPerCoinDay;
 643         bnTargetPerCoinDay.SetCompact(nBits);
 644
 645         uint256 nMaxTarget = (bnTargetPerCoinDay * bnValueIn * nStakeMaxAge / COIN / nOneDay).getuint256(),
 646             *pnHashProofOfStake = (uint256 *)&hashProofOfStake;
 647
 648         // Search forward in time from the given timestamp
 649         // Stopping search in case of shutting down
 650         for (uint32_t nTimeTx=nIntervalBegin, nMaxTarget32 = nMaxTarget.Get32(7); nTimeTx<nIntervalEnd && !fShutdown; nTimeTx++)
 651         {
 652             // Complete first hashing iteration
 653             uint256 hash1;
 654             SHA256_Update(&ctx, (unsigned char*)&nTimeTx, 4);
 655             SHA256_Final((unsigned char*)&hash1, &ctx);
 656
 657             // Restore context
 658             ctx = workerCtx;
 659
 660             // Finally, calculate kernel hash
 661             SHA256((unsigned char*)&hash1, sizeof(hashProofOfStake), (unsigned char*)&hashProofOfStake);
 662
 663             // Skip if hash doesn't satisfy the maximum target
 664             if (hashProofOfStake[7] > nMaxTarget32)
 665                 continue;
 666
 667             CBigNum bnCoinDayWeight = bnValueIn * GetWeight((int64_t)nInputTxTime, (int64_t)nTimeTx) / COIN / nOneDay;
 668             CBigNum bnTargetProofOfStake = bnCoinDayWeight * bnTargetPerCoinDay;
 669
 670             if (bnTargetProofOfStake >= CBigNum(*pnHashProofOfStake))
 671                 solutions.push_back(std::pair<uint256,uint32_t>(*pnHashProofOfStake, nTimeTx));
 672         }
 673     }
 674
 675     vector<std::pair<uint256,uint32_t> >& GetSolutions()
 676     {
 677         return solutions;
 678     }
 679
 680 private:
 681     SHA256_CTX workerCtx;
 682     std::vector<std::pair<uint256,uint32_t> > solutions;
 683
 684     uint32_t nBits;
 685     uint32_t nInputTxTime;
 686     CBigNum  bnValueIn;
 687     uint32_t nIntervalBegin;
 688     uint32_t nIntervalEnd;
 689 };
 690
 691 #endif
 692 // Scan given kernel for solution
 693 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)
 694 {
 695     // TODO: custom threads amount
 696
 697     uint32_t nThreads = boost::thread::hardware_concurrency();
 698     uint32_t nPart = (SearchInterval.second - SearchInterval.first) / nThreads;
 699
 700
 701     ScanMidstateWorker *workers = new ScanMidstateWorker[nThreads];
 702
 703     boost::thread_group group;
 704     for(size_t i = 0; i < nThreads; i++)
 705     {
 706         uint32_t nBegin = SearchInterval.first + nPart * i;
 707         uint32_t nEnd = SearchInterval.first + nPart * (i + 1);
 708         workers[i] = ScanMidstateWorker(kernel, nBits, nInputTxTime, nValueIn, nBegin, nEnd);
 709         boost::function<void()> workerFnc = boost::bind(&ScanMidstateWorker::Do, &workers[i]);
 710         group.create_thread(workerFnc);
 711     }
 712
 713     group.join_all();
 714     solutions.clear();
 715
 716     for(size_t i = 0; i < nThreads; i++)
 717     {
 718         std::vector<std::pair<uint256, uint32_t> > ws = workers[i].GetSolutions();
 719         solutions.insert(solutions.end(), ws.begin(), ws.end());
 720     }
 721
 722     delete [] workers;
 723
 724     if (solutions.size() == 0)
 725     {
 726         // no solutions
 727         return false;
 728     }
 729
 730     return true;
 731 }
 732
 733 // Scan given midstate for solution
 734 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)
 735 {
 736     CBigNum bnTargetPerCoinDay;
 737     bnTargetPerCoinDay.SetCompact(nBits);
 738
 739     // Get maximum possible target to filter out the majority of obviously insufficient hashes
 740     CBigNum bnMaxTargetPerCoinDay = bnTargetPerCoinDay * CBigNum(nValueIn) * nStakeMaxAge / COIN / nOneDay;
 741     uint256 maxTarget = bnMaxTargetPerCoinDay.getuint256();
 742
 743     SHA256_CTX ctxCopy = ctx;
 744
 745     // Search backward in time from the given timestamp
 746     // Stopping search in case of shutting down
 747     for (uint32_t nTimeTx=SearchInterval.first; nTimeTx>SearchInterval.second && !fShutdown; nTimeTx--)
 748     {
 749         // Complete first hashing iteration
 750         uint256 hash1;
 751         SHA256_Update(&ctxCopy, (unsigned char*)&nTimeTx, 4);
 752         SHA256_Final((unsigned char*)&hash1, &ctxCopy);
 753
 754         // Restore context
 755         ctxCopy = ctx;
 756
 757         // Finally, calculate kernel hash
 758         uint256 hashProofOfStake;
 759         SHA256((unsigned char*)&hash1, sizeof(hashProofOfStake), (unsigned char*)&hashProofOfStake);
 760
 761         // Skip if hash doesn't satisfy the maximum target
 762         if (hashProofOfStake > maxTarget)
 763             continue;
 764
 765         CBigNum bnCoinDayWeight = CBigNum(nValueIn) * GetWeight((int64_t)nInputTxTime, (int64_t)nTimeTx) / COIN / nOneDay;
 766         CBigNum bnTargetProofOfStake = bnCoinDayWeight * bnTargetPerCoinDay;
 767
 768         if (bnTargetProofOfStake >= CBigNum(hashProofOfStake))
 769         {
 770             solution.first = hashProofOfStake;
 771             solution.second = nTimeTx;
 772
 773             return true;
 774         }
 775     }
 776
 777     return false;
 778 }
 779
 780 // Check kernel hash target and coinstake signature
 781 bool CheckProofOfStake(const CTransaction& tx, unsigned int nBits, uint256& hashProofOfStake, uint256& targetProofOfStake)
 782 {
 783     if (!tx.IsCoinStake())
 784         return error("CheckProofOfStake() : called on non-coinstake %s", tx.GetHash().ToString().c_str());
 785
 786     // Kernel (input 0) must match the stake hash target per coin age (nBits)
 787     const CTxIn& txin = tx.vin[0];
 788
 789     // First try finding the previous transaction in database
 790     CTxDB txdb("r");
 791     CTransaction txPrev;
 792     CTxIndex txindex;
 793     if (!txPrev.ReadFromDisk(txdb, txin.prevout, txindex))
 794         return tx.DoS(1, error("CheckProofOfStake() : INFO: read txPrev failed"));  // previous transaction not in main chain, may occur during initial download
 795
 796 #ifndef USE_LEVELDB
 797     txdb.Close();
 798 #endif
 799
 800     // Verify signature
 801     if (!VerifySignature(txPrev, tx, 0, MANDATORY_SCRIPT_VERIFY_FLAGS, 0))
 802         return tx.DoS(100, error("CheckProofOfStake() : VerifySignature failed on coinstake %s", tx.GetHash().ToString().c_str()));
 803
 804     // Read block header
 805     CBlock block;
 806     if (!block.ReadFromDisk(txindex.pos.nFile, txindex.pos.nBlockPos, false))
 807         return fDebug? error("CheckProofOfStake() : read block failed") : false; // unable to read block of previous transaction
 808
 809     if (!CheckStakeKernelHash(nBits, block, txindex.pos.nTxPos - txindex.pos.nBlockPos, txPrev, txin.prevout, tx.nTime, hashProofOfStake, targetProofOfStake, fDebug))
 810         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
 811
 812     return true;
 813 }
 814
 815 // Get stake modifier checksum
 816 uint32_t GetStakeModifierChecksum(const CBlockIndex* pindex)
 817 {
 818     assert (pindex->pprev || pindex->GetBlockHash() == (!fTestNet ? hashGenesisBlock : hashGenesisBlockTestNet));
 819     // Hash previous checksum with flags, hashProofOfStake and nStakeModifier
 820     CDataStream ss(SER_GETHASH, 0);
 821     if (pindex->pprev)
 822         ss << pindex->pprev->nStakeModifierChecksum;
 823     ss << pindex->nFlags << pindex->hashProofOfStake << pindex->nStakeModifier;
 824     uint256 hashChecksum = Hash(ss.begin(), ss.end());
 825     hashChecksum >>= (256 - 32);
 826     return static_cast<uint32_t>(hashChecksum.Get64());
 827 }
 828
 829 // Check stake modifier hard checkpoints
 830 bool CheckStakeModifierCheckpoints(int nHeight, uint32_t nStakeModifierChecksum)
 831 {
 832     MapModifierCheckpoints& checkpoints = (fTestNet ? mapStakeModifierCheckpointsTestNet : mapStakeModifierCheckpoints);
 833
 834     if (checkpoints.count(nHeight))
 835         return nStakeModifierChecksum == checkpoints[nHeight];
 836     return true;
 837 }