Line data Source code
1 : // Copyright (c) 2009-2010 Satoshi Nakamoto 2 : // Copyright (c) 2009-2014 The Bitcoin developers 3 : // Copyright (c) 2016-2021 The PIVX Core developers 4 : // Distributed under the MIT software license, see the accompanying 5 : // file COPYING or http://www.opensource.org/licenses/mit-license.php. 6 : 7 : #include "chain.h" 8 : #include "legacy/stakemodifier.h" // for ComputeNextStakeModifier 9 : 10 : 11 : /** 12 : * CChain implementation 13 : */ 14 42550 : void CChain::SetTip(CBlockIndex* pindex) 15 : { 16 42550 : if (pindex == nullptr) { 17 483 : vChain.clear(); 18 483 : return; 19 : } 20 42067 : vChain.resize(pindex->nHeight + 1); 21 316325 : while (pindex && vChain[pindex->nHeight] != pindex) { 22 274258 : vChain[pindex->nHeight] = pindex; 23 274258 : pindex = pindex->pprev; 24 : } 25 : } 26 : 27 1682 : CBlockLocator CChain::GetLocator(const CBlockIndex* pindex) const 28 : { 29 1682 : int nStep = 1; 30 1682 : std::vector<uint256> vHave; 31 1682 : vHave.reserve(32); 32 : 33 1682 : if (!pindex) 34 355 : pindex = Tip(); 35 16162 : while (pindex) { 36 15978 : vHave.push_back(pindex->GetBlockHash()); 37 : // Stop when we have added the genesis block. 38 15978 : if (pindex->nHeight == 0) 39 : break; 40 : // Exponentially larger steps back, plus the genesis block. 41 14480 : int nHeight = std::max(pindex->nHeight - nStep, 0); 42 28960 : if (Contains(pindex)) { 43 : // Use O(1) CChain index if possible. 44 13544 : pindex = (*this)[nHeight]; 45 : } else { 46 : // Otherwise, use O(log n) skiplist. 47 936 : pindex = pindex->GetAncestor(nHeight); 48 : } 49 14480 : if (vHave.size() > 10) 50 6260 : nStep *= 2; 51 : } 52 : 53 3364 : return CBlockLocator(vHave); 54 : } 55 : 56 83043 : const CBlockIndex* CChain::FindFork(const CBlockIndex* pindex) const 57 : { 58 83043 : if (pindex == nullptr) 59 : return nullptr; 60 82725 : if (pindex->nHeight > Height()) 61 41521 : pindex = pindex->GetAncestor(Height()); 62 165508 : while (pindex && !Contains(pindex)) 63 188 : pindex = pindex->pprev; 64 : return pindex; 65 : } 66 : 67 10040 : CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime) const 68 : { 69 10040 : std::vector<CBlockIndex*>::const_iterator lower = std::lower_bound(vChain.begin(), vChain.end(), nTime, 70 178720 : [](CBlockIndex* pBlock, const int64_t& time) -> bool { return pBlock->GetBlockTimeMax() < time; }); 71 10040 : return (lower == vChain.end() ? nullptr : *lower); 72 : } 73 : 74 : /** Turn the lowest '1' bit in the binary representation of a number into a '0'. */ 75 6306870 : int static inline InvertLowestOne(int n) { return n & (n - 1); } 76 : 77 : /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */ 78 6314050 : int static inline GetSkipHeight(int height) 79 : { 80 6314050 : if (height < 2) 81 : return 0; 82 : // Determine which height to jump back to. Any number strictly lower than height is acceptable, 83 : // but the following expression seems to perform well in simulations (max 110 steps to go back 84 : // up to 2**18 blocks). 85 6306870 : return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height); 86 : } 87 : 88 808997 : const CBlockIndex* CBlockIndex::GetAncestor(int height) const 89 : { 90 808997 : if (height > nHeight || height < 0) { 91 : return nullptr; 92 : } 93 : 94 : const CBlockIndex* pindexWalk = this; 95 : int heightWalk = nHeight; 96 3653532 : while (heightWalk > height) { 97 2845113 : int heightSkip = GetSkipHeight(heightWalk); 98 2845113 : int heightSkipPrev = GetSkipHeight(heightWalk - 1); 99 2845113 : if (heightSkip == height || 100 1235680 : (heightSkip > height && !(heightSkipPrev < heightSkip - 2 && heightSkipPrev >= height))) { 101 : // Only follow pskip if pprev->pskip isn't better than pskip->pprev. 102 1507244 : pindexWalk = pindexWalk->pskip; 103 1507244 : heightWalk = heightSkip; 104 : } else { 105 1337869 : assert(pindexWalk->pprev); 106 : pindexWalk = pindexWalk->pprev; 107 : heightWalk--; 108 : } 109 : } 110 : return pindexWalk; 111 : } 112 : 113 683357 : CBlockIndex* CBlockIndex::GetAncestor(int height) 114 : { 115 683357 : return const_cast<CBlockIndex*>(static_cast<const CBlockIndex*>(this)->GetAncestor(height)); 116 : } 117 : 118 623828 : void CBlockIndex::BuildSkip() 119 : { 120 623828 : if (pprev) 121 1247330 : pskip = pprev->GetAncestor(GetSkipHeight(nHeight)); 122 623828 : } 123 : 124 56668 : CBlockIndex::CBlockIndex(const CBlock& block): 125 56668 : nVersion{block.nVersion}, 126 : hashMerkleRoot{block.hashMerkleRoot}, 127 : hashFinalSaplingRoot(block.hashFinalSaplingRoot), 128 56668 : nTime{block.nTime}, 129 56668 : nBits{block.nBits}, 130 113336 : nNonce{block.nNonce} 131 : { 132 56668 : if(block.nVersion > 3 && block.nVersion < 7) 133 5397 : nAccumulatorCheckpoint = block.nAccumulatorCheckpoint; 134 56668 : if (block.IsProofOfStake()) 135 8589 : SetProofOfStake(); 136 56668 : } 137 : 138 0 : std::string CBlockIndex::ToString() const 139 : { 140 0 : return strprintf("CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)", 141 0 : pprev, nHeight, 142 0 : hashMerkleRoot.ToString(), 143 0 : GetBlockHash().ToString()); 144 : } 145 : 146 221886 : FlatFilePos CBlockIndex::GetBlockPos() const 147 : { 148 221886 : FlatFilePos ret; 149 221886 : if (nStatus & BLOCK_HAVE_DATA) { 150 206732 : ret.nFile = nFile; 151 206732 : ret.nPos = nDataPos; 152 : } 153 221886 : return ret; 154 : } 155 : 156 84902 : FlatFilePos CBlockIndex::GetUndoPos() const 157 : { 158 84902 : FlatFilePos ret; 159 84902 : if (nStatus & BLOCK_HAVE_UNDO) { 160 2772 : ret.nFile = nFile; 161 2772 : ret.nPos = nUndoPos; 162 : } 163 84902 : return ret; 164 : } 165 : 166 8 : CBlockHeader CBlockIndex::GetBlockHeader() const 167 : { 168 8 : CBlockHeader block; 169 8 : block.nVersion = nVersion; 170 8 : if (pprev) block.hashPrevBlock = pprev->GetBlockHash(); 171 8 : block.hashMerkleRoot = hashMerkleRoot; 172 8 : block.nTime = nTime; 173 8 : block.nBits = nBits; 174 8 : block.nNonce = nNonce; 175 8 : if (nVersion > 3 && nVersion < 7) block.nAccumulatorCheckpoint = nAccumulatorCheckpoint; 176 8 : if (nVersion >= 8) block.hashFinalSaplingRoot = hashFinalSaplingRoot; 177 8 : return block; 178 : } 179 : 180 0 : int64_t CBlockIndex::MaxFutureBlockTime() const 181 : { 182 0 : return GetAdjustedTime() + Params().GetConsensus().FutureBlockTimeDrift(nHeight+1); 183 : } 184 : 185 0 : int64_t CBlockIndex::MinPastBlockTime() const 186 : { 187 0 : const Consensus::Params& consensus = Params().GetConsensus(); 188 : // Time Protocol v1: pindexPrev->MedianTimePast + 1 189 0 : if (!consensus.IsTimeProtocolV2(nHeight+1)) 190 0 : return GetMedianTimePast(); 191 : 192 : // on the transition from Time Protocol v1 to v2 193 : // pindexPrev->nTime might be in the future (up to the allowed drift) 194 : // so we allow the nBlockTimeProtocolV2 (PIVX v4.0) to be at most (180-14) seconds earlier than previous block 195 0 : if (nHeight + 1 == consensus.vUpgrades[Consensus::UPGRADE_V4_0].nActivationHeight) 196 0 : return GetBlockTime() - consensus.FutureBlockTimeDrift(nHeight) + consensus.FutureBlockTimeDrift(nHeight + 1); 197 : 198 : // Time Protocol v2: pindexPrev->nTime 199 0 : return GetBlockTime(); 200 : } 201 : 202 : enum { nMedianTimeSpan = 11 }; 203 : 204 352189 : int64_t CBlockIndex::GetMedianTimePast() const 205 : { 206 352189 : int64_t pmedian[nMedianTimeSpan]; 207 352189 : int64_t* pbegin = &pmedian[nMedianTimeSpan]; 208 352189 : int64_t* pend = &pmedian[nMedianTimeSpan]; 209 : 210 352189 : const CBlockIndex* pindex = this; 211 4220290 : for (int i = 0; i < nMedianTimeSpan && pindex; i++, pindex = pindex->pprev) 212 3868090 : *(--pbegin) = pindex->GetBlockTime(); 213 : 214 352189 : std::sort(pbegin, pend); 215 352189 : return pbegin[(pend - pbegin) / 2]; 216 : } 217 : 218 175180 : unsigned int CBlockIndex::GetStakeEntropyBit() const 219 : { 220 175180 : unsigned int nEntropyBit = ((GetBlockHash().GetCheapHash()) & 1); 221 175180 : return nEntropyBit; 222 : } 223 : 224 34522 : bool CBlockIndex::SetStakeEntropyBit(unsigned int nEntropyBit) 225 : { 226 34522 : if (nEntropyBit > 1) 227 : return false; 228 34522 : nFlags |= (nEntropyBit ? BLOCK_STAKE_ENTROPY : 0); 229 34522 : return true; 230 : } 231 : 232 : // Sets V1 stake modifier (uint64_t) 233 34522 : void CBlockIndex::SetStakeModifier(const uint64_t nStakeModifier, bool fGeneratedStakeModifier) 234 : { 235 34522 : vStakeModifier.clear(); 236 34522 : const size_t modSize = sizeof(nStakeModifier); 237 34522 : vStakeModifier.resize(modSize); 238 34522 : std::memcpy(vStakeModifier.data(), &nStakeModifier, modSize); 239 34522 : if (fGeneratedStakeModifier) 240 4358 : nFlags |= BLOCK_STAKE_MODIFIER; 241 : 242 34522 : } 243 : 244 : // Generates and sets new V1 stake modifier 245 34522 : void CBlockIndex::SetNewStakeModifier() 246 : { 247 : // compute stake entropy bit for stake modifier 248 34522 : if (!SetStakeEntropyBit(GetStakeEntropyBit())) 249 0 : LogPrintf("%s : SetStakeEntropyBit() failed\n", __func__); 250 34522 : uint64_t nStakeModifier = 0; 251 34522 : bool fGeneratedStakeModifier = false; 252 34522 : if (!ComputeNextStakeModifier(pprev, nStakeModifier, fGeneratedStakeModifier)) 253 0 : LogPrintf("%s : ComputeNextStakeModifier() failed \n", __func__); 254 34522 : return SetStakeModifier(nStakeModifier, fGeneratedStakeModifier); 255 : } 256 : 257 : // Sets V2 stake modifiers (uint256) 258 6659 : void CBlockIndex::SetStakeModifier(const uint256& nStakeModifier) 259 : { 260 6659 : vStakeModifier.clear(); 261 6659 : vStakeModifier.insert(vStakeModifier.begin(), nStakeModifier.begin(), nStakeModifier.end()); 262 6659 : } 263 : 264 : // Generates and sets new V2 stake modifier 265 6659 : void CBlockIndex::SetNewStakeModifier(const uint256& prevoutId) 266 : { 267 : // Shouldn't be called on V1 modifier's blocks (or before setting pprev) 268 6659 : if (!Params().GetConsensus().NetworkUpgradeActive(nHeight, Consensus::UPGRADE_V3_4)) return; 269 6659 : if (!pprev) throw std::runtime_error(strprintf("%s : ERROR: null pprev", __func__)); 270 : 271 : // Generate Hash(prevoutId | prevModifier) - switch with genesis modifier (0) on upgrade block 272 6659 : CHashWriter ss(SER_GETHASH, 0); 273 6659 : ss << prevoutId; 274 6659 : ss << pprev->GetStakeModifierV2(); 275 13318 : SetStakeModifier(ss.GetHash()); 276 : } 277 : 278 : // Returns V1 stake modifier (uint64_t) 279 34587 : uint64_t CBlockIndex::GetStakeModifierV1() const 280 : { 281 34587 : if (vStakeModifier.empty() || Params().GetConsensus().NetworkUpgradeActive(nHeight, Consensus::UPGRADE_V3_4)) 282 0 : return 0; 283 34587 : uint64_t nStakeModifier; 284 34587 : std::memcpy(&nStakeModifier, vStakeModifier.data(), vStakeModifier.size()); 285 34587 : return nStakeModifier; 286 : } 287 : 288 : // Returns V2 stake modifier (uint256) 289 25948 : uint256 CBlockIndex::GetStakeModifierV2() const 290 : { 291 25948 : if (vStakeModifier.empty() || !Params().GetConsensus().NetworkUpgradeActive(nHeight, Consensus::UPGRADE_V3_4)) 292 219 : return UINT256_ZERO; 293 25729 : uint256 nStakeModifier; 294 25729 : std::memcpy(nStakeModifier.begin(), vStakeModifier.data(), vStakeModifier.size()); 295 25729 : return nStakeModifier; 296 : } 297 : 298 41476 : void CBlockIndex::SetChainSaplingValue() 299 : { 300 : // Sapling, update chain value 301 41476 : if (pprev) { 302 41160 : if (pprev->nChainSaplingValue) { 303 41160 : nChainSaplingValue = *pprev->nChainSaplingValue + nSaplingValue; 304 : } else { 305 0 : nChainSaplingValue = nullopt; 306 : } 307 : } else { 308 316 : nChainSaplingValue = nSaplingValue; 309 : } 310 41476 : } 311 : 312 : //! Check whether this block index entry is valid up to the passed validity level. 313 184111 : bool CBlockIndex::IsValid(enum BlockStatus nUpTo) const 314 : { 315 184111 : assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed. 316 184111 : if (nStatus & BLOCK_FAILED_MASK) 317 : return false; 318 183628 : return ((nStatus & BLOCK_VALID_MASK) >= nUpTo); 319 : } 320 : 321 : //! Raise the validity level of this block index entry. 322 : //! Returns true if the validity was changed. 323 124038 : bool CBlockIndex::RaiseValidity(enum BlockStatus nUpTo) 324 : { 325 124038 : assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed. 326 124038 : if (nStatus & BLOCK_FAILED_MASK) 327 : return false; 328 124038 : if ((nStatus & BLOCK_VALID_MASK) < nUpTo) { 329 124038 : nStatus = (nStatus & ~BLOCK_VALID_MASK) | nUpTo; 330 124038 : return true; 331 : } 332 : return false; 333 : } 334 : 335 : /** Find the last common ancestor two blocks have. 336 : * Both pa and pb must be non-nullptr. */ 337 703077 : const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb) 338 : { 339 703077 : if (pa->nHeight > pb->nHeight) { 340 0 : pa = pa->GetAncestor(pb->nHeight); 341 703077 : } else if (pb->nHeight > pa->nHeight) { 342 30699 : pb = pb->GetAncestor(pa->nHeight); 343 : } 344 : 345 703147 : while (pa != pb && pa && pb) { 346 70 : pa = pa->pprev; 347 70 : pb = pb->pprev; 348 : } 349 : 350 : // Eventually all chain branches meet at the genesis block. 351 703077 : assert(pa == pb); 352 703077 : return pa; 353 : } 354 : 355 :