// Copyright (c) 2012-2013 The PPCoin developers // Copyright (c) 2014 The Blackcoin developers // Copyright (c) 2016 The Stratis developers // Copyright (c) 2018 The DNotes developers // Distributed under the MIT/X11 software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include #include "kernel.h" #include "txdb.h" using namespace std; // Get time weight int64_t GetWeight(int64_t nIntervalBeginning, int64_t nIntervalEnd) { // Kernel hash weight starts from 0 at the min age // this change increases active coins participating the hash and helps // to secure the network when proof-of-stake difficulty is low return nIntervalEnd - nIntervalBeginning - nStakeMinAge; } // Get the last stake modifier and its generation time from a given block static bool GetLastStakeModifier(const CBlockIndex* pindex, uint64_t& nStakeModifier, int64_t& nModifierTime) { if (!pindex) return error("GetLastStakeModifier: null pindex"); while (pindex && pindex->pprev && !pindex->GeneratedStakeModifier()) pindex = pindex->pprev; if (!pindex->GeneratedStakeModifier()) return error("GetLastStakeModifier: no generation at genesis block"); nStakeModifier = pindex->nStakeModifier; nModifierTime = pindex->GetBlockTime(); return true; } // Get selection interval section (in seconds) static int64_t GetStakeModifierSelectionIntervalSection(int nSection) { assert (nSection >= 0 && nSection < 64); return (nModifierInterval * 63 / (63 + ((63 - nSection) * (MODIFIER_INTERVAL_RATIO - 1)))); } // Get stake modifier selection interval (in seconds) static int64_t GetStakeModifierSelectionInterval() { int64_t nSelectionInterval = 0; for (int nSection=0; nSection<64; nSection++) nSelectionInterval += GetStakeModifierSelectionIntervalSection(nSection); return nSelectionInterval; } // select a block from the candidate blocks in vSortedByTimestamp, excluding // already selected blocks in vSelectedBlocks, and with timestamp up to // nSelectionIntervalStop. static bool SelectBlockFromCandidates(vector >& vSortedByTimestamp, map& mapSelectedBlocks, int64_t nSelectionIntervalStop, uint64_t nStakeModifierPrev, const CBlockIndex** pindexSelected) { bool fSelected = false; uint256 hashBest = 0; *pindexSelected = (const CBlockIndex*) 0; BOOST_FOREACH(const PAIRTYPE(int64_t, uint256)& item, vSortedByTimestamp) { if (!mapBlockIndex.count(item.second)) return error("SelectBlockFromCandidates: failed to find block index for candidate block %s", item.second.ToString()); const CBlockIndex* pindex = mapBlockIndex[item.second]; if (fSelected && pindex->GetBlockTime() > nSelectionIntervalStop) break; if (mapSelectedBlocks.count(pindex->GetBlockHash()) > 0) continue; // compute the selection hash by hashing its proof-hash and the // previous proof-of-stake modifier CDataStream ss(SER_GETHASH, 0); ss << pindex->hashProof << nStakeModifierPrev; uint256 hashSelection = Hash(ss.begin(), ss.end()); // the selection hash is divided by 2**32 so that proof-of-stake block // is always favored over proof-of-work block. this is to preserve // the energy efficiency property if (pindex->IsProofOfStake()) hashSelection >>= 32; if (fSelected && hashSelection < hashBest) { hashBest = hashSelection; *pindexSelected = (const CBlockIndex*) pindex; } else if (!fSelected) { fSelected = true; hashBest = hashSelection; *pindexSelected = (const CBlockIndex*) pindex; } } LogPrint("stakemodifier", "SelectBlockFromCandidates: selection hash=%s\n", hashBest.ToString()); return fSelected; } // Stake Modifier (hash modifier of proof-of-stake): // The purpose of stake modifier is to prevent a txout (coin) owner from // computing future proof-of-stake generated by this txout at the time // of transaction confirmation. To meet kernel protocol, the txout // must hash with a future stake modifier to generate the proof. // Stake modifier consists of bits each of which is contributed from a // selected block of a given block group in the past. // The selection of a block is based on a hash of the block's proof-hash and // the previous stake modifier. // Stake modifier is recomputed at a fixed time interval instead of every // block. This is to make it difficult for an attacker to gain control of // additional bits in the stake modifier, even after generating a chain of // blocks. bool ComputeNextStakeModifier(const CBlockIndex* pindexPrev, uint64_t& nStakeModifier, bool& fGeneratedStakeModifier) { nStakeModifier = 0; fGeneratedStakeModifier = false; if (!pindexPrev) { fGeneratedStakeModifier = true; return true; // genesis block's modifier is 0 } // First find current stake modifier and its generation block time // if it's not old enough, return the same stake modifier int64_t nModifierTime = 0; if (!GetLastStakeModifier(pindexPrev, nStakeModifier, nModifierTime)) return error("ComputeNextStakeModifier: unable to get last modifier"); LogPrint("stakemodifier", "ComputeNextStakeModifier: prev modifier=0x%016x time=%s\n", nStakeModifier, DateTimeStrFormat(nModifierTime)); if (nModifierTime / nModifierInterval >= pindexPrev->GetBlockTime() / nModifierInterval) return true; // Sort candidate blocks by timestamp vector > vSortedByTimestamp; vSortedByTimestamp.reserve(64 * nModifierInterval / GetTargetSpacing(pindexPrev->nHeight)); int64_t nSelectionInterval = GetStakeModifierSelectionInterval(); int64_t nSelectionIntervalStart = (pindexPrev->GetBlockTime() / nModifierInterval) * nModifierInterval - nSelectionInterval; const CBlockIndex* pindex = pindexPrev; while (pindex && pindex->GetBlockTime() >= nSelectionIntervalStart) { vSortedByTimestamp.push_back(make_pair(pindex->GetBlockTime(), pindex->GetBlockHash())); pindex = pindex->pprev; } int nHeightFirstCandidate = pindex ? (pindex->nHeight + 1) : 0; reverse(vSortedByTimestamp.begin(), vSortedByTimestamp.end()); sort(vSortedByTimestamp.begin(), vSortedByTimestamp.end()); // Select 64 blocks from candidate blocks to generate stake modifier uint64_t nStakeModifierNew = 0; int64_t nSelectionIntervalStop = nSelectionIntervalStart; map mapSelectedBlocks; for (int nRound=0; nRoundGetStakeEntropyBit()) << nRound); // add the selected block from candidates to selected list mapSelectedBlocks.insert(make_pair(pindex->GetBlockHash(), pindex)); LogPrint("stakemodifier", "ComputeNextStakeModifier: selected round %d stop=%s height=%d bit=%d\n", nRound, DateTimeStrFormat(nSelectionIntervalStop), pindex->nHeight, pindex->GetStakeEntropyBit()); } // Print selection map for visualization of the selected blocks if (LogAcceptCategory("stakemodifier")) { string strSelectionMap = ""; // '-' indicates proof-of-work blocks not selected strSelectionMap.insert(0, pindexPrev->nHeight - nHeightFirstCandidate + 1, '-'); pindex = pindexPrev; while (pindex && pindex->nHeight >= nHeightFirstCandidate) { // '=' indicates proof-of-stake blocks not selected if (pindex->IsProofOfStake()) strSelectionMap.replace(pindex->nHeight - nHeightFirstCandidate, 1, "="); pindex = pindex->pprev; } BOOST_FOREACH(const PAIRTYPE(uint256, const CBlockIndex*)& item, mapSelectedBlocks) { // 'S' indicates selected proof-of-stake blocks // 'W' indicates selected proof-of-work blocks strSelectionMap.replace(item.second->nHeight - nHeightFirstCandidate, 1, item.second->IsProofOfStake()? "S" : "W"); } LogPrintf("ComputeNextStakeModifier: selection height [%d, %d] map %s\n", nHeightFirstCandidate, pindexPrev->nHeight, strSelectionMap); } LogPrint("stakemodifier", "ComputeNextStakeModifier: new modifier=0x%016x time=%s\n", nStakeModifierNew, DateTimeStrFormat(pindexPrev->GetBlockTime())); nStakeModifier = nStakeModifierNew; fGeneratedStakeModifier = true; return true; } // Stake Modifier (hash modifier of proof-of-stake): // The purpose of stake modifier is to prevent a txout (coin) owner from // computing future proof-of-stake generated by this txout at the time // of transaction confirmation. To meet kernel protocol, the txout // must hash with a future stake modifier to generate the proof. uint256 ComputeStakeModifierV2(const CBlockIndex* pindexPrev, const uint256& kernel) { if (!pindexPrev) return 0; // genesis block's modifier is 0 CDataStream ss(SER_GETHASH, 0); ss << kernel << pindexPrev->bnStakeModifierV2; return Hash(ss.begin(), ss.end()); } // The stake modifier used to hash for a stake kernel is chosen as the stake // modifier about a selection interval later than the coin generating the kernel static bool GetKernelStakeModifier(uint256 hashBlockFrom, uint64_t& nStakeModifier, int& nStakeModifierHeight, int64_t& nStakeModifierTime, bool fPrintProofOfStake) { nStakeModifier = 0; if (!mapBlockIndex.count(hashBlockFrom)) return error("GetKernelStakeModifier() : block not indexed"); const CBlockIndex* pindexFrom = mapBlockIndex[hashBlockFrom]; nStakeModifierHeight = pindexFrom->nHeight; nStakeModifierTime = pindexFrom->GetBlockTime(); int64_t nStakeModifierSelectionInterval = GetStakeModifierSelectionInterval(); const CBlockIndex* pindex = pindexFrom; // loop to find the stake modifier later by a selection interval while (nStakeModifierTime < pindexFrom->GetBlockTime() + nStakeModifierSelectionInterval) { if (!pindex->pnext) { // reached best block; may happen if node is behind on block chain if (fPrintProofOfStake || (pindex->GetBlockTime() + nStakeMinAge - nStakeModifierSelectionInterval > GetAdjustedTime())) return error("GetKernelStakeModifier() : reached best block %s at height %d from block %s", pindex->GetBlockHash().ToString(), pindex->nHeight, hashBlockFrom.ToString()); else return false; } pindex = pindex->pnext; if (pindex->GeneratedStakeModifier()) { nStakeModifierHeight = pindex->nHeight; nStakeModifierTime = pindex->GetBlockTime(); } } nStakeModifier = pindex->nStakeModifier; return true; } // ppcoin kernel protocol // coinstake must meet hash target according to the protocol: // kernel (input 0) must meet the formula // hash(nStakeModifier + txPrev.block.nTime + txPrev.offset + txPrev.nTime + txPrev.vout.n + nTime) < bnTarget * nCoinDayWeight // this ensures that the chance of getting a coinstake is proportional to the // amount of coin age one owns. // The reason this hash is chosen is the following: // nStakeModifier: scrambles computation to make it very difficult to precompute // future proof-of-stake at the time of the coin's confirmation // txPrev.block.nTime: prevent nodes from guessing a good timestamp to // generate transaction for future advantage // txPrev.offset: offset of txPrev inside block, to reduce the chance of // nodes generating coinstake at the same time // txPrev.nTime: reduce the chance of nodes generating coinstake at the same // time // txPrev.vout.n: output number of txPrev, to reduce the chance of nodes // generating coinstake at the same time // block/tx hash should not be used here as they can be generated in vast // quantities so as to generate blocks faster, degrading the system back into // a proof-of-work situation. // static bool CheckStakeKernelHashV1(unsigned int nBits, const CBlock& blockFrom, unsigned int nTxPrevOffset, const CTransaction& txPrev, const COutPoint& prevout, unsigned int nTimeTx, uint256& hashProofOfStake, uint256& targetProofOfStake, bool fPrintProofOfStake) { if (nTimeTx < txPrev.nTime) // Transaction timestamp violation return error("CheckStakeKernelHash() : nTime violation"); unsigned int nTimeBlockFrom = blockFrom.GetBlockTime(); CBigNum bnTargetPerCoinDay; bnTargetPerCoinDay.SetCompact(nBits); int64_t nValueIn = txPrev.vout[prevout.n].nValue; uint256 hashBlockFrom = blockFrom.GetHash(); CBigNum bnCoinDayWeight = CBigNum(nValueIn) * GetWeight((int64_t)txPrev.nTime, (int64_t)nTimeTx) / COIN / (24 * 60 * 60); targetProofOfStake = (bnCoinDayWeight * bnTargetPerCoinDay).getuint256(); // Calculate hash CDataStream ss(SER_GETHASH, 0); uint64_t nStakeModifier = 0; int nStakeModifierHeight = 0; int64_t nStakeModifierTime = 0; if (!GetKernelStakeModifier(hashBlockFrom, nStakeModifier, nStakeModifierHeight, nStakeModifierTime, fPrintProofOfStake)) return false; ss << nStakeModifier; ss << nTimeBlockFrom << nTxPrevOffset << txPrev.nTime << prevout.n << nTimeTx; hashProofOfStake = Hash(ss.begin(), ss.end()); if (fPrintProofOfStake) { LogPrintf("CheckStakeKernelHash() : using modifier 0x%016x at height=%d timestamp=%s for block from height=%d timestamp=%s\n", nStakeModifier, nStakeModifierHeight, DateTimeStrFormat(nStakeModifierTime), mapBlockIndex[hashBlockFrom]->nHeight, DateTimeStrFormat(blockFrom.GetBlockTime())); LogPrintf("CheckStakeKernelHash() : check modifier=0x%016x nTimeBlockFrom=%u nTxPrevOffset=%u nTimeTxPrev=%u nPrevout=%u nTimeTx=%u hashProof=%s\n", nStakeModifier, nTimeBlockFrom, nTxPrevOffset, txPrev.nTime, prevout.n, nTimeTx, hashProofOfStake.ToString()); } // Now check if proof-of-stake hash meets target protocol if (CBigNum(hashProofOfStake) > bnCoinDayWeight * bnTargetPerCoinDay) return false; if (fDebug && !fPrintProofOfStake) { LogPrintf("CheckStakeKernelHash() : using modifier 0x%016x at height=%d timestamp=%s for block from height=%d timestamp=%s\n", nStakeModifier, nStakeModifierHeight, DateTimeStrFormat(nStakeModifierTime), mapBlockIndex[hashBlockFrom]->nHeight, DateTimeStrFormat(blockFrom.GetBlockTime())); LogPrintf("CheckStakeKernelHash() : pass modifier=0x%016x nTimeBlockFrom=%u nTxPrevOffset=%u nTimeTxPrev=%u nPrevout=%u nTimeTx=%u hashProof=%s\n", nStakeModifier, nTimeBlockFrom, nTxPrevOffset, txPrev.nTime, prevout.n, nTimeTx, hashProofOfStake.ToString()); } return true; } // DNotes kernel protocol // coinstake must meet hash target according to the protocol: // kernel (input 0) must meet the formula // hash(nStakeModifier + txPrev.block.nTime + txPrev.nTime + txPrev.vout.hash + txPrev.vout.n + nTime) < bnTarget * nWeight // this ensures that the chance of getting a coinstake is proportional to the // amount of coins one owns. // The reason this hash is chosen is the following: // nStakeModifier: scrambles computation to make it very difficult to precompute // future proof-of-stake // txPrev.block.nTime: prevent nodes from guessing a good timestamp to // generate transaction for future advantage, // obsolete since v3 // txPrev.nTime: slightly scrambles computation // txPrev.vout.hash: hash of txPrev, to reduce the chance of nodes // generating coinstake at the same time // txPrev.vout.n: output number of txPrev, to reduce the chance of nodes // generating coinstake at the same time // nTime: current timestamp // block/tx hash should not be used here as they can be generated in vast // quantities so as to generate blocks faster, degrading the system back into // a proof-of-work situation. // static bool CheckStakeKernelHashV2(CBlockIndex* pindexPrev, unsigned int nBits, unsigned int nTimeBlockFrom, const CTransaction& txPrev, const COutPoint& prevout, unsigned int nTimeTx, uint256& hashProofOfStake, uint256& targetProofOfStake, bool fPrintProofOfStake) { if (nTimeTx < txPrev.nTime) // Transaction timestamp violation return error("CheckStakeKernelHash() : nTime violation"); // Base target CBigNum bnTarget; bnTarget.SetCompact(nBits); // Weighted target int64_t nValueIn = txPrev.vout[prevout.n].nValue; CBigNum bnWeight = CBigNum(nValueIn); bnTarget *= bnWeight; targetProofOfStake = bnTarget.getuint256(); uint64_t nStakeModifier = pindexPrev->nStakeModifier; uint256 bnStakeModifierV2 = pindexPrev->bnStakeModifierV2; int nStakeModifierHeight = pindexPrev->nHeight; int64_t nStakeModifierTime = pindexPrev->nTime; // Calculate hash CDataStream ss(SER_GETHASH, 0); if (IsProtocolV3(nTimeTx)) ss << bnStakeModifierV2; else ss << nStakeModifier << nTimeBlockFrom; ss << txPrev.nTime << prevout.hash << prevout.n << nTimeTx; hashProofOfStake = Hash(ss.begin(), ss.end()); if (fPrintProofOfStake) { LogPrintf("CheckStakeKernelHash() : using modifier 0x%016x at height=%d timestamp=%s for block from timestamp=%s\n", nStakeModifier, nStakeModifierHeight, DateTimeStrFormat(nStakeModifierTime), DateTimeStrFormat(nTimeBlockFrom)); LogPrintf("CheckStakeKernelHash() : check modifier=0x%016x nTimeBlockFrom=%u nTimeTxPrev=%u nPrevout=%u nTimeTx=%u hashProof=%s\n", nStakeModifier, nTimeBlockFrom, txPrev.nTime, prevout.n, nTimeTx, hashProofOfStake.ToString()); } // Now check if proof-of-stake hash meets target protocol if (CBigNum(hashProofOfStake) > bnTarget) return false; if (fDebug && !fPrintProofOfStake) { LogPrintf("CheckStakeKernelHash() : using modifier 0x%016x at height=%d timestamp=%s for block from timestamp=%s\n", nStakeModifier, nStakeModifierHeight, DateTimeStrFormat(nStakeModifierTime), DateTimeStrFormat(nTimeBlockFrom)); LogPrintf("CheckStakeKernelHash() : pass modifier=0x%016x nTimeBlockFrom=%u nTimeTxPrev=%u nPrevout=%u nTimeTx=%u hashProof=%s\n", nStakeModifier, nTimeBlockFrom, txPrev.nTime, prevout.n, nTimeTx, hashProofOfStake.ToString()); } return true; } bool CheckStakeKernelHash(CBlockIndex* pindexPrev, unsigned int nBits, const CBlock& blockFrom, unsigned int nTxPrevOffset, const CTransaction& txPrev, const COutPoint& prevout, unsigned int nTimeTx, uint256& hashProofOfStake, uint256& targetProofOfStake, bool fPrintProofOfStake) { if (IsProtocolV2(pindexPrev->nHeight+1)) return CheckStakeKernelHashV2(pindexPrev, nBits, blockFrom.GetBlockTime(), txPrev, prevout, nTimeTx, hashProofOfStake, targetProofOfStake, fPrintProofOfStake); else return CheckStakeKernelHashV1(nBits, blockFrom, nTxPrevOffset, txPrev, prevout, nTimeTx, hashProofOfStake, targetProofOfStake, fPrintProofOfStake); } // Check kernel hash target and coinstake signature bool CheckProofOfStake(CBlockIndex* pindexPrev, const CTransaction& tx, unsigned int nBits, uint256& hashProofOfStake, uint256& targetProofOfStake) { if (!tx.IsCoinStake()) return error("CheckProofOfStake() : called on non-coinstake %s", tx.GetHash().ToString()); // Kernel (input 0) must match the stake hash target per coin age (nBits) const CTxIn& txin = tx.vin[0]; // First try finding the previous transaction in database CTxDB txdb("r"); CTransaction txPrev; CTxIndex txindex; if (!txPrev.ReadFromDisk(txdb, txin.prevout, txindex)) return tx.DoS(1, error("CheckProofOfStake() : INFO: read txPrev failed")); // previous transaction not in main chain, may occur during initial download // Verify signature if (!VerifySignature(txPrev, tx, 0, SCRIPT_VERIFY_NONE, 0)) return tx.DoS(100, error("CheckProofOfStake() : VerifySignature failed on coinstake %s", tx.GetHash().ToString())); // Read block header CBlock block; if (!block.ReadFromDisk(txindex.pos.nFile, txindex.pos.nBlockPos, false)) return fDebug? error("CheckProofOfStake() : read block failed") : false; // unable to read block of previous transaction // Min age requirement if (IsProtocolV3(tx.nTime)) { int nDepth; if (IsConfirmedInNPrevBlocks(txindex, pindexPrev, nCoinbaseMaturity - 1, nDepth)) return tx.DoS(100, error("CheckProofOfStake() : tried to stake at depth %d", nDepth + 1)); } else { unsigned int nTimeBlockFrom = block.GetBlockTime(); if (nTimeBlockFrom + nStakeMinAge > tx.nTime) return error("CheckProofOfStake() : min age violation"); } if (!CheckStakeKernelHash(pindexPrev, nBits, block, txindex.pos.nTxPos - txindex.pos.nBlockPos, txPrev, txin.prevout, tx.nTime, hashProofOfStake, targetProofOfStake, fDebug)) return tx.DoS(1, error("CheckProofOfStake() : INFO: check kernel failed on coinstake %s, hashProof=%s", tx.GetHash().ToString(), hashProofOfStake.ToString())); // may occur during initial download or if behind on block chain sync return true; } // Check whether the coinstake timestamp meets protocol bool CheckCoinStakeTimestamp(int nHeight, int64_t nTimeBlock, int64_t nTimeTx) { if (IsProtocolV2(nHeight)) return (nTimeBlock == nTimeTx) && ((nTimeTx & STAKE_TIMESTAMP_MASK) == 0); else return (nTimeBlock == nTimeTx); } bool CheckKernel(CBlockIndex* pindexPrev, unsigned int nBits, int64_t nTime, const COutPoint& prevout, int64_t* pBlockTime) { uint256 hashProofOfStake, targetProofOfStake; CTxDB txdb("r"); CTransaction txPrev; CTxIndex txindex; if (!txPrev.ReadFromDisk(txdb, prevout, txindex)) return false; // Read block header CBlock block; if (!block.ReadFromDisk(txindex.pos.nFile, txindex.pos.nBlockPos, false)) return false; if (IsProtocolV3(nTime)) { int nDepth; if (IsConfirmedInNPrevBlocks(txindex, pindexPrev, nCoinbaseMaturity - 1, nDepth)) return false; } else { if (block.GetBlockTime() + nStakeMinAge > nTime) return false; // only count coins meeting min age requirement } if (pBlockTime) *pBlockTime = block.GetBlockTime(); return CheckStakeKernelHash(pindexPrev, nBits, block, txindex.pos.nTxPos - txindex.pos.nBlockPos, txPrev, prevout, nTime, hashProofOfStake, targetProofOfStake); }