diff --git a/src/addrman.cpp b/src/addrman.cpp index 35aeae56f..4b890bb50 100644 --- a/src/addrman.cpp +++ b/src/addrman.cpp @@ -1,716 +1,711 @@ // Copyright (c) 2012 Pieter Wuille // Copyright (c) 2012-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include #include #include #include #include int CAddrInfo::GetTriedBucket(const uint256 &nKey) const { uint64_t hash1 = (CHashWriter(SER_GETHASH, 0) << nKey << GetKey()) - .GetHash() .GetCheapHash(); uint64_t hash2 = (CHashWriter(SER_GETHASH, 0) << nKey << GetGroup() << (hash1 % ADDRMAN_TRIED_BUCKETS_PER_GROUP)) - .GetHash() .GetCheapHash(); return hash2 % ADDRMAN_TRIED_BUCKET_COUNT; } int CAddrInfo::GetNewBucket(const uint256 &nKey, const CNetAddr &src) const { std::vector vchSourceGroupKey = src.GetGroup(); uint64_t hash1 = (CHashWriter(SER_GETHASH, 0) << nKey << GetGroup() << vchSourceGroupKey) - .GetHash() .GetCheapHash(); uint64_t hash2 = (CHashWriter(SER_GETHASH, 0) << nKey << vchSourceGroupKey << (hash1 % ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP)) - .GetHash() .GetCheapHash(); return hash2 % ADDRMAN_NEW_BUCKET_COUNT; } int CAddrInfo::GetBucketPosition(const uint256 &nKey, bool fNew, int nBucket) const { uint64_t hash1 = (CHashWriter(SER_GETHASH, 0) << nKey << (fNew ? 'N' : 'K') << nBucket << GetKey()) - .GetHash() .GetCheapHash(); return hash1 % ADDRMAN_BUCKET_SIZE; } bool CAddrInfo::IsTerrible(int64_t nNow) const { // never remove things tried in the last minute if (nLastTry && nLastTry >= nNow - 60) { return false; } // came in a flying DeLorean if (nTime > nNow + 10 * 60) { return true; } // not seen in recent history if (nTime == 0 || nNow - nTime > ADDRMAN_HORIZON_DAYS * 24 * 60 * 60) { return true; } // tried N times and never a success if (nLastSuccess == 0 && nAttempts >= ADDRMAN_RETRIES) { return true; } if (nNow - nLastSuccess > ADDRMAN_MIN_FAIL_DAYS * 24 * 60 * 60 && nAttempts >= ADDRMAN_MAX_FAILURES) { // N successive failures in the last week return true; } return false; } double CAddrInfo::GetChance(int64_t nNow) const { double fChance = 1.0; int64_t nSinceLastTry = std::max(nNow - nLastTry, 0); // deprioritize very recent attempts away if (nSinceLastTry < 60 * 10) { fChance *= 0.01; } // deprioritize 66% after each failed attempt, but at most 1/28th to avoid // the search taking forever or overly penalizing outages. fChance *= std::pow(0.66, std::min(nAttempts, 8)); return fChance; } CAddrInfo *CAddrMan::Find(const CNetAddr &addr, int *pnId) { std::map::iterator it = mapAddr.find(addr); if (it == mapAddr.end()) { return nullptr; } if (pnId) { *pnId = (*it).second; } std::map::iterator it2 = mapInfo.find((*it).second); if (it2 != mapInfo.end()) { return &(*it2).second; } return nullptr; } CAddrInfo *CAddrMan::Create(const CAddress &addr, const CNetAddr &addrSource, int *pnId) { int nId = nIdCount++; mapInfo[nId] = CAddrInfo(addr, addrSource); mapAddr[addr] = nId; mapInfo[nId].nRandomPos = vRandom.size(); vRandom.push_back(nId); if (pnId) { *pnId = nId; } return &mapInfo[nId]; } void CAddrMan::SwapRandom(unsigned int nRndPos1, unsigned int nRndPos2) { if (nRndPos1 == nRndPos2) { return; } assert(nRndPos1 < vRandom.size() && nRndPos2 < vRandom.size()); int nId1 = vRandom[nRndPos1]; int nId2 = vRandom[nRndPos2]; assert(mapInfo.count(nId1) == 1); assert(mapInfo.count(nId2) == 1); mapInfo[nId1].nRandomPos = nRndPos2; mapInfo[nId2].nRandomPos = nRndPos1; vRandom[nRndPos1] = nId2; vRandom[nRndPos2] = nId1; } void CAddrMan::Delete(int nId) { assert(mapInfo.count(nId) != 0); CAddrInfo &info = mapInfo[nId]; assert(!info.fInTried); assert(info.nRefCount == 0); SwapRandom(info.nRandomPos, vRandom.size() - 1); vRandom.pop_back(); mapAddr.erase(info); mapInfo.erase(nId); nNew--; } void CAddrMan::ClearNew(int nUBucket, int nUBucketPos) { // if there is an entry in the specified bucket, delete it. if (vvNew[nUBucket][nUBucketPos] != -1) { int nIdDelete = vvNew[nUBucket][nUBucketPos]; CAddrInfo &infoDelete = mapInfo[nIdDelete]; assert(infoDelete.nRefCount > 0); infoDelete.nRefCount--; vvNew[nUBucket][nUBucketPos] = -1; if (infoDelete.nRefCount == 0) { Delete(nIdDelete); } } } void CAddrMan::MakeTried(CAddrInfo &info, int nId) { // remove the entry from all new buckets for (int bucket = 0; bucket < ADDRMAN_NEW_BUCKET_COUNT; bucket++) { int pos = info.GetBucketPosition(nKey, true, bucket); if (vvNew[bucket][pos] == nId) { vvNew[bucket][pos] = -1; info.nRefCount--; } } nNew--; assert(info.nRefCount == 0); // which tried bucket to move the entry to int nKBucket = info.GetTriedBucket(nKey); int nKBucketPos = info.GetBucketPosition(nKey, false, nKBucket); // first make space to add it (the existing tried entry there is moved to // new, deleting whatever is there). if (vvTried[nKBucket][nKBucketPos] != -1) { // find an item to evict int nIdEvict = vvTried[nKBucket][nKBucketPos]; assert(mapInfo.count(nIdEvict) == 1); CAddrInfo &infoOld = mapInfo[nIdEvict]; // Remove the to-be-evicted item from the tried set. infoOld.fInTried = false; vvTried[nKBucket][nKBucketPos] = -1; nTried--; // find which new bucket it belongs to int nUBucket = infoOld.GetNewBucket(nKey); int nUBucketPos = infoOld.GetBucketPosition(nKey, true, nUBucket); ClearNew(nUBucket, nUBucketPos); assert(vvNew[nUBucket][nUBucketPos] == -1); // Enter it into the new set again. infoOld.nRefCount = 1; vvNew[nUBucket][nUBucketPos] = nIdEvict; nNew++; } assert(vvTried[nKBucket][nKBucketPos] == -1); vvTried[nKBucket][nKBucketPos] = nId; nTried++; info.fInTried = true; } void CAddrMan::Good_(const CService &addr, bool test_before_evict, int64_t nTime) { int nId; nLastGood = nTime; CAddrInfo *pinfo = Find(addr, &nId); // if not found, bail out if (!pinfo) { return; } CAddrInfo &info = *pinfo; // check whether we are talking about the exact same CService (including // same port) if (info != addr) { return; } // update info info.nLastSuccess = nTime; info.nLastTry = nTime; info.nAttempts = 0; // nTime is not updated here, to avoid leaking information about // currently-connected peers. // if it is already in the tried set, don't do anything else if (info.fInTried) { return; } // find a bucket it is in now int nRnd = insecure_rand.randrange(ADDRMAN_NEW_BUCKET_COUNT); int nUBucket = -1; for (unsigned int n = 0; n < ADDRMAN_NEW_BUCKET_COUNT; n++) { int nB = (n + nRnd) % ADDRMAN_NEW_BUCKET_COUNT; int nBpos = info.GetBucketPosition(nKey, true, nB); if (vvNew[nB][nBpos] == nId) { nUBucket = nB; break; } } // if no bucket is found, something bad happened; // TODO: maybe re-add the node, but for now, just bail out if (nUBucket == -1) { return; } // which tried bucket to move the entry to int tried_bucket = info.GetTriedBucket(nKey); int tried_bucket_pos = info.GetBucketPosition(nKey, false, tried_bucket); // Will moving this address into tried evict another entry? if (test_before_evict && (vvTried[tried_bucket][tried_bucket_pos] != -1)) { LogPrint(BCLog::ADDRMAN, "Collision inserting element into tried table, moving %s to " "m_tried_collisions=%d\n", addr.ToString(), m_tried_collisions.size()); if (m_tried_collisions.size() < ADDRMAN_SET_TRIED_COLLISION_SIZE) { m_tried_collisions.insert(nId); } } else { LogPrint(BCLog::ADDRMAN, "Moving %s to tried\n", addr.ToString()); // move nId to the tried tables MakeTried(info, nId); } } bool CAddrMan::Add_(const CAddress &addr, const CNetAddr &source, int64_t nTimePenalty) { if (!addr.IsRoutable()) { return false; } bool fNew = false; int nId; CAddrInfo *pinfo = Find(addr, &nId); // Do not set a penalty for a source's self-announcement if (addr == source) { nTimePenalty = 0; } if (pinfo) { // periodically update nTime bool fCurrentlyOnline = (GetAdjustedTime() - addr.nTime < 24 * 60 * 60); int64_t nUpdateInterval = (fCurrentlyOnline ? 60 * 60 : 24 * 60 * 60); if (addr.nTime && (!pinfo->nTime || pinfo->nTime < addr.nTime - nUpdateInterval - nTimePenalty)) { pinfo->nTime = std::max((int64_t)0, addr.nTime - nTimePenalty); } // add services pinfo->nServices = ServiceFlags(pinfo->nServices | addr.nServices); // do not update if no new information is present if (!addr.nTime || (pinfo->nTime && addr.nTime <= pinfo->nTime)) { return false; } // do not update if the entry was already in the "tried" table if (pinfo->fInTried) { return false; } // do not update if the max reference count is reached if (pinfo->nRefCount == ADDRMAN_NEW_BUCKETS_PER_ADDRESS) { return false; } // stochastic test: previous nRefCount == N: 2^N times harder to // increase it int nFactor = 1; for (int n = 0; n < pinfo->nRefCount; n++) { nFactor *= 2; } if (nFactor > 1 && (insecure_rand.randrange(nFactor) != 0)) { return false; } } else { pinfo = Create(addr, source, &nId); pinfo->nTime = std::max((int64_t)0, (int64_t)pinfo->nTime - nTimePenalty); nNew++; fNew = true; } int nUBucket = pinfo->GetNewBucket(nKey, source); int nUBucketPos = pinfo->GetBucketPosition(nKey, true, nUBucket); if (vvNew[nUBucket][nUBucketPos] != nId) { bool fInsert = vvNew[nUBucket][nUBucketPos] == -1; if (!fInsert) { CAddrInfo &infoExisting = mapInfo[vvNew[nUBucket][nUBucketPos]]; if (infoExisting.IsTerrible() || (infoExisting.nRefCount > 1 && pinfo->nRefCount == 0)) { // Overwrite the existing new table entry. fInsert = true; } } if (fInsert) { ClearNew(nUBucket, nUBucketPos); pinfo->nRefCount++; vvNew[nUBucket][nUBucketPos] = nId; } else if (pinfo->nRefCount == 0) { Delete(nId); } } return fNew; } void CAddrMan::Attempt_(const CService &addr, bool fCountFailure, int64_t nTime) { CAddrInfo *pinfo = Find(addr); // if not found, bail out if (!pinfo) { return; } CAddrInfo &info = *pinfo; // check whether we are talking about the exact same CService (including // same port) if (info != addr) { return; } // update info info.nLastTry = nTime; if (fCountFailure && info.nLastCountAttempt < nLastGood) { info.nLastCountAttempt = nTime; info.nAttempts++; } } CAddrInfo CAddrMan::Select_(bool newOnly) { if (size() == 0) { return CAddrInfo(); } if (newOnly && nNew == 0) { return CAddrInfo(); } // Use a 50% chance for choosing between tried and new table entries. if (!newOnly && (nTried > 0 && (nNew == 0 || insecure_rand.randbool() == 0))) { // use a tried node double fChanceFactor = 1.0; while (1) { int nKBucket = insecure_rand.randrange(ADDRMAN_TRIED_BUCKET_COUNT); int nKBucketPos = insecure_rand.randrange(ADDRMAN_BUCKET_SIZE); while (vvTried[nKBucket][nKBucketPos] == -1) { nKBucket = (nKBucket + insecure_rand.randbits( ADDRMAN_TRIED_BUCKET_COUNT_LOG2)) % ADDRMAN_TRIED_BUCKET_COUNT; nKBucketPos = (nKBucketPos + insecure_rand.randbits( ADDRMAN_BUCKET_SIZE_LOG2)) % ADDRMAN_BUCKET_SIZE; } int nId = vvTried[nKBucket][nKBucketPos]; assert(mapInfo.count(nId) == 1); CAddrInfo &info = mapInfo[nId]; if (insecure_rand.randbits(30) < fChanceFactor * info.GetChance() * (1 << 30)) { return info; } fChanceFactor *= 1.2; } } else { // use a new node double fChanceFactor = 1.0; while (1) { int nUBucket = insecure_rand.randrange(ADDRMAN_NEW_BUCKET_COUNT); int nUBucketPos = insecure_rand.randrange(ADDRMAN_BUCKET_SIZE); while (vvNew[nUBucket][nUBucketPos] == -1) { nUBucket = (nUBucket + insecure_rand.randbits( ADDRMAN_NEW_BUCKET_COUNT_LOG2)) % ADDRMAN_NEW_BUCKET_COUNT; nUBucketPos = (nUBucketPos + insecure_rand.randbits( ADDRMAN_BUCKET_SIZE_LOG2)) % ADDRMAN_BUCKET_SIZE; } int nId = vvNew[nUBucket][nUBucketPos]; assert(mapInfo.count(nId) == 1); CAddrInfo &info = mapInfo[nId]; if (insecure_rand.randbits(30) < fChanceFactor * info.GetChance() * (1 << 30)) { return info; } fChanceFactor *= 1.2; } } } #ifdef DEBUG_ADDRMAN int CAddrMan::Check_() { std::set setTried; std::map mapNew; if (vRandom.size() != nTried + nNew) { return -7; } for (const auto &entry : mapInfo) { int n = entry.first; const CAddrInfo &info = entry.second; if (info.fInTried) { if (!info.nLastSuccess) { return -1; } if (info.nRefCount) { return -2; } setTried.insert(n); } else { if (info.nRefCount < 0 || info.nRefCount > ADDRMAN_NEW_BUCKETS_PER_ADDRESS) { return -3; } if (!info.nRefCount) { return -4; } mapNew[n] = info.nRefCount; } if (mapAddr[info] != n) { return -5; } if (info.nRandomPos < 0 || info.nRandomPos >= vRandom.size() || vRandom[info.nRandomPos] != n) { return -14; } if (info.nLastTry < 0) { return -6; } if (info.nLastSuccess < 0) { return -8; } } if (setTried.size() != nTried) { return -9; } if (mapNew.size() != nNew) { return -10; } for (int n = 0; n < ADDRMAN_TRIED_BUCKET_COUNT; n++) { for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) { if (vvTried[n][i] != -1) { if (!setTried.count(vvTried[n][i])) { return -11; } if (mapInfo[vvTried[n][i]].GetTriedBucket(nKey) != n) { return -17; } if (mapInfo[vvTried[n][i]].GetBucketPosition(nKey, false, n) != i) { return -18; } setTried.erase(vvTried[n][i]); } } } for (int n = 0; n < ADDRMAN_NEW_BUCKET_COUNT; n++) { for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) { if (vvNew[n][i] != -1) { if (!mapNew.count(vvNew[n][i])) { return -12; } if (mapInfo[vvNew[n][i]].GetBucketPosition(nKey, true, n) != i) { return -19; } if (--mapNew[vvNew[n][i]] == 0) { mapNew.erase(vvNew[n][i]); } } } } if (setTried.size()) { return -13; } if (mapNew.size()) { return -15; } if (nKey.IsNull()) { return -16; } return 0; } #endif void CAddrMan::GetAddr_(std::vector &vAddr) { unsigned int nNodes = ADDRMAN_GETADDR_MAX_PCT * vRandom.size() / 100; if (nNodes > ADDRMAN_GETADDR_MAX) nNodes = ADDRMAN_GETADDR_MAX; // gather a list of random nodes, skipping those of low quality for (unsigned int n = 0; n < vRandom.size(); n++) { if (vAddr.size() >= nNodes) { break; } int nRndPos = insecure_rand.randrange(vRandom.size() - n) + n; SwapRandom(n, nRndPos); assert(mapInfo.count(vRandom[n]) == 1); const CAddrInfo &ai = mapInfo[vRandom[n]]; if (!ai.IsTerrible()) { vAddr.push_back(ai); } } } void CAddrMan::Connected_(const CService &addr, int64_t nTime) { CAddrInfo *pinfo = Find(addr); // if not found, bail out if (!pinfo) { return; } CAddrInfo &info = *pinfo; // check whether we are talking about the exact same CService (including // same port) if (info != addr) { return; } // update info int64_t nUpdateInterval = 20 * 60; if (nTime - info.nTime > nUpdateInterval) { info.nTime = nTime; } } void CAddrMan::SetServices_(const CService &addr, ServiceFlags nServices) { CAddrInfo *pinfo = Find(addr); // if not found, bail out if (!pinfo) { return; } CAddrInfo &info = *pinfo; // check whether we are talking about the exact same CService (including // same port) if (info != addr) { return; } // update info info.nServices = nServices; } void CAddrMan::ResolveCollisions_() { const int64_t adjustedTime = GetAdjustedTime(); for (std::set::iterator it = m_tried_collisions.begin(); it != m_tried_collisions.end();) { int id_new = *it; bool erase_collision = false; // If id_new not found in mapInfo remove it from m_tried_collisions. auto id_new_it = mapInfo.find(id_new); if (id_new_it == mapInfo.end()) { erase_collision = true; } else { CAddrInfo &info_new = id_new_it->second; // Which tried bucket to move the entry to. int tried_bucket = info_new.GetTriedBucket(nKey); int tried_bucket_pos = info_new.GetBucketPosition(nKey, false, tried_bucket); if (!info_new.IsValid()) { // id_new may no longer map to a valid address erase_collision = true; } else if (vvTried[tried_bucket][tried_bucket_pos] != -1) { // The position in the tried bucket is not empty // Get the to-be-evicted address that is being tested int id_old = vvTried[tried_bucket][tried_bucket_pos]; CAddrInfo &info_old = mapInfo[id_old]; // Has successfully connected in last X hours if (adjustedTime - info_old.nLastSuccess < ADDRMAN_REPLACEMENT_SECONDS) { erase_collision = true; } else if (adjustedTime - info_old.nLastTry < ADDRMAN_REPLACEMENT_SECONDS) { // attempted to connect and failed in last X hours // Give address at least 60 seconds to successfully connect if (GetAdjustedTime() - info_old.nLastTry > 60) { LogPrint(BCLog::ADDRMAN, "Swapping %s for %s in tried table\n", info_new.ToString(), info_old.ToString()); // Replaces an existing address already in the tried // table with the new address Good_(info_new, false, GetAdjustedTime()); erase_collision = true; } } } else { // Collision is not actually a collision anymore Good_(info_new, false, adjustedTime); erase_collision = true; } } if (erase_collision) { m_tried_collisions.erase(it++); } else { it++; } } } CAddrInfo CAddrMan::SelectTriedCollision_() { if (m_tried_collisions.size() == 0) { return CAddrInfo(); } std::set::iterator it = m_tried_collisions.begin(); // Selects a random element from m_tried_collisions std::advance(it, insecure_rand.randrange(m_tried_collisions.size())); int id_new = *it; // If id_new not found in mapInfo remove it from m_tried_collisions. auto id_new_it = mapInfo.find(id_new); if (id_new_it == mapInfo.end()) { m_tried_collisions.erase(it); return CAddrInfo(); } CAddrInfo &newInfo = id_new_it->second; // which tried bucket to move the entry to int tried_bucket = newInfo.GetTriedBucket(nKey); int tried_bucket_pos = newInfo.GetBucketPosition(nKey, false, tried_bucket); int id_old = vvTried[tried_bucket][tried_bucket_pos]; return mapInfo[id_old]; } diff --git a/src/chain.h b/src/chain.h index 644b0d985..5439332b5 100644 --- a/src/chain.h +++ b/src/chain.h @@ -1,426 +1,432 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_CHAIN_H #define BITCOIN_CHAIN_H #include #include #include #include +#include // for ReadLE64 #include #include #include #include #include #include #include /** * Maximum amount of time that a block timestamp is allowed to exceed the * current network-adjusted time before the block will be accepted. */ static constexpr int64_t MAX_FUTURE_BLOCK_TIME = 2 * 60 * 60; /** * Timestamp window used as a grace period by code that compares external * timestamps (such as timestamps passed to RPCs, or wallet key creation times) * to block timestamps. This should be set at least as high as * MAX_FUTURE_BLOCK_TIME. */ static constexpr int64_t TIMESTAMP_WINDOW = MAX_FUTURE_BLOCK_TIME; /** * Maximum gap between node time and block time used * for the "Catching up..." mode in GUI. * * Ref: https://github.com/bitcoin/bitcoin/pull/1026 */ static constexpr int64_t MAX_BLOCK_TIME_GAP = 90 * 60; /** * The block chain is a tree shaped structure starting with the genesis block at * the root, with each block potentially having multiple candidates to be the * next block. A blockindex may have multiple pprev pointing to it, but at most * one of them can be part of the currently active branch. */ class CBlockIndex { public: //! pointer to the hash of the block, if any. Memory is owned by this //! CBlockIndex const uint256 *phashBlock; //! pointer to the index of the predecessor of this block CBlockIndex *pprev; //! pointer to the index of some further predecessor of this block CBlockIndex *pskip; //! height of the entry in the chain. The genesis block has height 0 int nHeight; //! Which # file this block is stored in (blk?????.dat) int nFile; //! Byte offset within blk?????.dat where this block's data is stored unsigned int nDataPos; //! Byte offset within rev?????.dat where this block's undo data is stored unsigned int nUndoPos; //! (memory only) Total amount of work (expected number of hashes) in the //! chain up to and including this block arith_uint256 nChainWork; //! Number of transactions in this block. //! Note: in a potential headers-first mode, this number cannot be relied //! upon unsigned int nTx; //! (memory only) Number of transactions in the chain up to and including //! this block. //! This value will be non-zero only if and only if transactions for this //! block and all its parents are available. Change to 64-bit type when //! necessary; won't happen before 2030 unsigned int nChainTx; //! Verification status of this block. See enum BlockStatus BlockStatus nStatus; //! block header int32_t nVersion; uint256 hashMerkleRoot; uint32_t nTime; uint32_t nBits; uint32_t nNonce; //! (memory only) Sequential id assigned to distinguish order in which //! blocks are received. int32_t nSequenceId; //! (memory only) block header metadata uint64_t nTimeReceived; //! (memory only) Maximum nTime in the chain up to and including this block. unsigned int nTimeMax; void SetNull() { phashBlock = nullptr; pprev = nullptr; pskip = nullptr; nHeight = 0; nFile = 0; nDataPos = 0; nUndoPos = 0; nChainWork = arith_uint256(); nTx = 0; nChainTx = 0; nStatus = BlockStatus(); nSequenceId = 0; nTimeMax = 0; nVersion = 0; hashMerkleRoot = uint256(); nTime = 0; nTimeReceived = 0; nBits = 0; nNonce = 0; } CBlockIndex() { SetNull(); } explicit CBlockIndex(const CBlockHeader &block) { SetNull(); nVersion = block.nVersion; hashMerkleRoot = block.hashMerkleRoot; nTime = block.nTime; nTimeReceived = 0; nBits = block.nBits; nNonce = block.nNonce; } FlatFilePos GetBlockPos() const { FlatFilePos ret; if (nStatus.hasData()) { ret.nFile = nFile; ret.nPos = nDataPos; } return ret; } FlatFilePos GetUndoPos() const { FlatFilePos ret; if (nStatus.hasUndo()) { ret.nFile = nFile; ret.nPos = nUndoPos; } return ret; } CBlockHeader GetBlockHeader() const { CBlockHeader block; block.nVersion = nVersion; if (pprev) { block.hashPrevBlock = pprev->GetBlockHash(); } block.hashMerkleRoot = hashMerkleRoot; block.nTime = nTime; block.nBits = nBits; block.nNonce = nNonce; return block; } uint256 GetBlockHash() const { return *phashBlock; } int64_t GetBlockTime() const { return int64_t(nTime); } int64_t GetBlockTimeMax() const { return int64_t(nTimeMax); } int64_t GetHeaderReceivedTime() const { return nTimeReceived; } int64_t GetReceivedTimeDiff() const { return GetHeaderReceivedTime() - GetBlockTime(); } static constexpr int nMedianTimeSpan = 11; int64_t GetMedianTimePast() const { int64_t pmedian[nMedianTimeSpan]; int64_t *pbegin = &pmedian[nMedianTimeSpan]; int64_t *pend = &pmedian[nMedianTimeSpan]; const CBlockIndex *pindex = this; for (int i = 0; i < nMedianTimeSpan && pindex; i++, pindex = pindex->pprev) { *(--pbegin) = pindex->GetBlockTime(); } std::sort(pbegin, pend); return pbegin[(pend - pbegin) / 2]; } std::string ToString() const { return strprintf( "CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)", pprev, nHeight, hashMerkleRoot.ToString(), GetBlockHash().ToString()); } //! Check whether this block index entry is valid up to the passed validity //! level. bool IsValid(enum BlockValidity nUpTo = BlockValidity::TRANSACTIONS) const { return nStatus.isValid(nUpTo); } //! Raise the validity level of this block index entry. //! Returns true if the validity was changed. bool RaiseValidity(enum BlockValidity nUpTo) { // Only validity flags allowed. if (nStatus.isInvalid()) { return false; } if (nStatus.getValidity() >= nUpTo) { return false; } nStatus = nStatus.withValidity(nUpTo); return true; } //! Build the skiplist pointer for this entry. void BuildSkip(); //! Efficiently find an ancestor of this block. CBlockIndex *GetAncestor(int height); const CBlockIndex *GetAncestor(int height) const; }; /** * Maintain a map of CBlockIndex for all known headers. */ struct BlockHasher { - size_t operator()(const uint256 &hash) const { return hash.GetCheapHash(); } + // this used to call `GetCheapHash()` in uint256, which was later moved; the + // cheap hash function simply calls ReadLE64() however, so the end result is + // identical + size_t operator()(const uint256 &hash) const { + return ReadLE64(hash.begin()); + } }; typedef std::unordered_map BlockMap; extern BlockMap &mapBlockIndex; extern CCriticalSection cs_main; inline CBlockIndex *LookupBlockIndex(const uint256 &hash) { AssertLockHeld(cs_main); BlockMap::const_iterator it = mapBlockIndex.find(hash); return it == mapBlockIndex.end() ? nullptr : it->second; } arith_uint256 GetBlockProof(const CBlockIndex &block); /** * Return the time it would take to redo the work difference between from and * to, assuming the current hashrate corresponds to the difficulty at tip, in * seconds. */ int64_t GetBlockProofEquivalentTime(const CBlockIndex &to, const CBlockIndex &from, const CBlockIndex &tip, const Consensus::Params &); /** * Find the forking point between two chain tips. */ const CBlockIndex *LastCommonAncestor(const CBlockIndex *pa, const CBlockIndex *pb); /** * Check if two block index are on the same fork. */ bool AreOnTheSameFork(const CBlockIndex *pa, const CBlockIndex *pb); /** Used to marshal pointers into hashes for db storage. */ class CDiskBlockIndex : public CBlockIndex { public: uint256 hashPrev; CDiskBlockIndex() { hashPrev = uint256(); } explicit CDiskBlockIndex(const CBlockIndex *pindex) : CBlockIndex(*pindex) { hashPrev = (pprev ? pprev->GetBlockHash() : uint256()); } ADD_SERIALIZE_METHODS; template inline void SerializationOp(Stream &s, Operation ser_action) { int _nVersion = s.GetVersion(); if (!(s.GetType() & SER_GETHASH)) { READWRITE(VARINT(_nVersion, VarIntMode::NONNEGATIVE_SIGNED)); } READWRITE(VARINT(nHeight, VarIntMode::NONNEGATIVE_SIGNED)); READWRITE(nStatus); READWRITE(VARINT(nTx)); if (nStatus.hasData() || nStatus.hasUndo()) { READWRITE(VARINT(nFile, VarIntMode::NONNEGATIVE_SIGNED)); } if (nStatus.hasData()) { READWRITE(VARINT(nDataPos)); } if (nStatus.hasUndo()) { READWRITE(VARINT(nUndoPos)); } // block header READWRITE(this->nVersion); READWRITE(hashPrev); READWRITE(hashMerkleRoot); READWRITE(nTime); READWRITE(nBits); READWRITE(nNonce); } uint256 GetBlockHash() const { CBlockHeader block; block.nVersion = nVersion; block.hashPrevBlock = hashPrev; block.hashMerkleRoot = hashMerkleRoot; block.nTime = nTime; block.nBits = nBits; block.nNonce = nNonce; return block.GetHash(); } std::string ToString() const { std::string str = "CDiskBlockIndex("; str += CBlockIndex::ToString(); str += strprintf("\n hashBlock=%s, hashPrev=%s)", GetBlockHash().ToString(), hashPrev.ToString()); return str; } }; /** * An in-memory indexed chain of blocks. */ class CChain { private: std::vector vChain; public: /** * Returns the index entry for the genesis block of this chain, or nullptr * if none. */ CBlockIndex *Genesis() const { return vChain.size() > 0 ? vChain[0] : nullptr; } /** * Returns the index entry for the tip of this chain, or nullptr if none. */ CBlockIndex *Tip() const { return vChain.size() > 0 ? vChain[vChain.size() - 1] : nullptr; } /** * Returns the index entry at a particular height in this chain, or nullptr * if no such height exists. */ CBlockIndex *operator[](int nHeight) const { if (nHeight < 0 || nHeight >= (int)vChain.size()) { return nullptr; } return vChain[nHeight]; } /** Compare two chains efficiently. */ friend bool operator==(const CChain &a, const CChain &b) { return a.vChain.size() == b.vChain.size() && a.vChain[a.vChain.size() - 1] == b.vChain[b.vChain.size() - 1]; } /** Efficiently check whether a block is present in this chain. */ bool Contains(const CBlockIndex *pindex) const { return (*this)[pindex->nHeight] == pindex; } /** * Find the successor of a block in this chain, or nullptr if the given * index is not found or is the tip. */ CBlockIndex *Next(const CBlockIndex *pindex) const { if (!Contains(pindex)) { return nullptr; } return (*this)[pindex->nHeight + 1]; } /** * Return the maximal height in the chain. Is equal to chain.Tip() ? * chain.Tip()->nHeight : -1. */ int Height() const { return vChain.size() - 1; } /** Set/initialize a chain with a given tip. */ void SetTip(CBlockIndex *pindex); /** * Return a CBlockLocator that refers to a block in this chain (by default * the tip). */ CBlockLocator GetLocator(const CBlockIndex *pindex = nullptr) const; /** * Find the last common block between this chain and a block index entry. */ const CBlockIndex *FindFork(const CBlockIndex *pindex) const; /** * Find the earliest block with timestamp equal or greater than the given. */ CBlockIndex *FindEarliestAtLeast(int64_t nTime) const; }; #endif // BITCOIN_CHAIN_H diff --git a/src/hash.h b/src/hash.h index 395e54cc6..445b55a18 100644 --- a/src/hash.h +++ b/src/hash.h @@ -1,199 +1,209 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_HASH_H #define BITCOIN_HASH_H +#include #include #include #include #include #include #include #include typedef uint256 ChainCode; /** A hasher class for Bitcoin's 256-bit hash (double SHA-256). */ class CHash256 { private: CSHA256 sha; public: static const size_t OUTPUT_SIZE = CSHA256::OUTPUT_SIZE; void Finalize(uint8_t hash[OUTPUT_SIZE]) { uint8_t buf[CSHA256::OUTPUT_SIZE]; sha.Finalize(buf); sha.Reset().Write(buf, CSHA256::OUTPUT_SIZE).Finalize(hash); } CHash256 &Write(const uint8_t *data, size_t len) { sha.Write(data, len); return *this; } CHash256 &Reset() { sha.Reset(); return *this; } }; /** A hasher class for Bitcoin's 160-bit hash (SHA-256 + RIPEMD-160). */ class CHash160 { private: CSHA256 sha; public: static const size_t OUTPUT_SIZE = CRIPEMD160::OUTPUT_SIZE; void Finalize(uint8_t hash[OUTPUT_SIZE]) { uint8_t buf[CSHA256::OUTPUT_SIZE]; sha.Finalize(buf); CRIPEMD160().Write(buf, CSHA256::OUTPUT_SIZE).Finalize(hash); } CHash160 &Write(const uint8_t *data, size_t len) { sha.Write(data, len); return *this; } CHash160 &Reset() { sha.Reset(); return *this; } }; /** Compute the 256-bit hash of an object. */ template inline uint256 Hash(const T1 pbegin, const T1 pend) { static const uint8_t pblank[1] = {}; uint256 result; CHash256() .Write(pbegin == pend ? pblank : (const uint8_t *)&pbegin[0], (pend - pbegin) * sizeof(pbegin[0])) .Finalize((uint8_t *)&result); return result; } /** Compute the 256-bit hash of the concatenation of two objects. */ template inline uint256 Hash(const T1 p1begin, const T1 p1end, const T2 p2begin, const T2 p2end) { static const uint8_t pblank[1] = {}; uint256 result; CHash256() .Write(p1begin == p1end ? pblank : (const uint8_t *)&p1begin[0], (p1end - p1begin) * sizeof(p1begin[0])) .Write(p2begin == p2end ? pblank : (const uint8_t *)&p2begin[0], (p2end - p2begin) * sizeof(p2begin[0])) .Finalize((uint8_t *)&result); return result; } /** Compute the 160-bit hash an object. */ template inline uint160 Hash160(const T1 pbegin, const T1 pend) { static uint8_t pblank[1] = {}; uint160 result; CHash160() .Write(pbegin == pend ? pblank : (const uint8_t *)&pbegin[0], (pend - pbegin) * sizeof(pbegin[0])) .Finalize((uint8_t *)&result); return result; } /** Compute the 160-bit hash of a vector. */ inline uint160 Hash160(const std::vector &vch) { return Hash160(vch.begin(), vch.end()); } /** Compute the 160-bit hash of a vector. */ template inline uint160 Hash160(const prevector &vch) { return Hash160(vch.begin(), vch.end()); } /** A writer stream (for serialization) that computes a 256-bit hash. */ class CHashWriter { private: CHash256 ctx; const int nType; const int nVersion; public: CHashWriter(int nTypeIn, int nVersionIn) : nType(nTypeIn), nVersion(nVersionIn) {} int GetType() const { return nType; } int GetVersion() const { return nVersion; } void write(const char *pch, size_t size) { ctx.Write((const uint8_t *)pch, size); } // invalidates the object uint256 GetHash() { uint256 result; ctx.Finalize((uint8_t *)&result); return result; } + /** + * Returns the first 64 bits from the resulting hash. + */ + inline uint64_t GetCheapHash() { + uint8_t result[CHash256::OUTPUT_SIZE]; + ctx.Finalize(result); + return ReadLE64(result); + } + template CHashWriter &operator<<(const T &obj) { // Serialize to this stream ::Serialize(*this, obj); return (*this); } }; /** * Reads data from an underlying stream, while hashing the read data. */ template class CHashVerifier : public CHashWriter { private: Source *source; public: explicit CHashVerifier(Source *source_) : CHashWriter(source_->GetType(), source_->GetVersion()), source(source_) {} void read(char *pch, size_t nSize) { source->read(pch, nSize); this->write(pch, nSize); } void ignore(size_t nSize) { char data[1024]; while (nSize > 0) { size_t now = std::min(nSize, 1024); read(data, now); nSize -= now; } } template CHashVerifier &operator>>(T &&obj) { // Unserialize from this stream ::Unserialize(*this, obj); return (*this); } }; /** Compute the 256-bit hash of an object's serialization. */ template uint256 SerializeHash(const T &obj, int nType = SER_GETHASH, int nVersion = PROTOCOL_VERSION) { CHashWriter ss(nType, nVersion); ss << obj; return ss.GetHash(); } uint32_t MurmurHash3(uint32_t nHashSeed, const std::vector &vDataToHash); void BIP32Hash(const ChainCode &chainCode, uint32_t nChild, uint8_t header, const uint8_t data[32], uint8_t output[64]); #endif // BITCOIN_HASH_H diff --git a/src/uint256.h b/src/uint256.h index ed90e4d2f..a9a23693c 100644 --- a/src/uint256.h +++ b/src/uint256.h @@ -1,171 +1,161 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_UINT256_H #define BITCOIN_UINT256_H -#include - #include #include #include #include #include #include /** Template base class for fixed-sized opaque blobs. */ template class base_blob { protected: static constexpr int WIDTH = BITS / 8; uint8_t data[WIDTH]; public: base_blob() { memset(data, 0, sizeof(data)); } explicit base_blob(const std::vector &vch); bool IsNull() const { for (int i = 0; i < WIDTH; i++) { if (data[i] != 0) { return false; } } return true; } void SetNull() { memset(data, 0, sizeof(data)); } inline int Compare(const base_blob &other) const { for (size_t i = 0; i < sizeof(data); i++) { uint8_t a = data[sizeof(data) - 1 - i]; uint8_t b = other.data[sizeof(data) - 1 - i]; if (a > b) { return 1; } if (a < b) { return -1; } } return 0; } friend inline bool operator==(const base_blob &a, const base_blob &b) { return a.Compare(b) == 0; } friend inline bool operator!=(const base_blob &a, const base_blob &b) { return a.Compare(b) != 0; } friend inline bool operator<(const base_blob &a, const base_blob &b) { return a.Compare(b) < 0; } friend inline bool operator<=(const base_blob &a, const base_blob &b) { return a.Compare(b) <= 0; } friend inline bool operator>(const base_blob &a, const base_blob &b) { return a.Compare(b) > 0; } friend inline bool operator>=(const base_blob &a, const base_blob &b) { return a.Compare(b) >= 0; } std::string GetHex() const; void SetHex(const char *psz); void SetHex(const std::string &str); std::string ToString() const { return GetHex(); } uint8_t *begin() { return &data[0]; } uint8_t *end() { return &data[WIDTH]; } const uint8_t *begin() const { return &data[0]; } const uint8_t *end() const { return &data[WIDTH]; } unsigned int size() const { return sizeof(data); } uint64_t GetUint64(int pos) const { const uint8_t *ptr = data + pos * 8; return uint64_t(ptr[0]) | (uint64_t(ptr[1]) << 8) | (uint64_t(ptr[2]) << 16) | (uint64_t(ptr[3]) << 24) | (uint64_t(ptr[4]) << 32) | (uint64_t(ptr[5]) << 40) | (uint64_t(ptr[6]) << 48) | (uint64_t(ptr[7]) << 56); } template void Serialize(Stream &s) const { s.write((char *)data, sizeof(data)); } template void Unserialize(Stream &s) { s.read((char *)data, sizeof(data)); } }; /** * 160-bit opaque blob. * @note This type is called uint160 for historical reasons only. It is an * opaque blob of 160 bits and has no integer operations. */ class uint160 : public base_blob<160> { public: uint160() {} explicit uint160(const std::vector &vch) : base_blob<160>(vch) {} }; /** * 256-bit opaque blob. * @note This type is called uint256 for historical reasons only. It is an * opaque blob of 256 bits and has no integer operations. Use arith_uint256 if * those are required. */ class uint256 : public base_blob<256> { public: uint256() {} explicit uint256(const std::vector &vch) : base_blob<256>(vch) {} - - /** - * A cheap hash function that just returns 64 bits from the result, it can - * be used when the contents are considered uniformly random. It is not - * appropriate when the value can easily be influenced from outside as e.g. - * a network adversary could provide values to trigger worst-case behavior. - */ - uint64_t GetCheapHash() const { return ReadLE64(data); } }; /** * uint256 from const char *. * This is a separate function because the constructor uint256(const char*) can * result in dangerously catching uint256(0). */ inline uint256 uint256S(const char *str) { uint256 rv; rv.SetHex(str); return rv; } /** * uint256 from std::string. * This is a separate function because the constructor uint256(const std::string * &str) can result in dangerously catching uint256(0) via std::string(const * char*). */ inline uint256 uint256S(const std::string &str) { uint256 rv; rv.SetHex(str); return rv; } inline uint160 uint160S(const char *str) { uint160 rv; rv.SetHex(str); return rv; } inline uint160 uint160S(const std::string &str) { uint160 rv; rv.SetHex(str); return rv; } #endif // BITCOIN_UINT256_H