diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp index 260c6a6551..9f7bfdac1a 100644 --- a/src/blockencodings.cpp +++ b/src/blockencodings.cpp @@ -1,272 +1,272 @@ // Copyright (c) 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 #include #include #include #include #include #include #include #include CBlockHeaderAndShortTxIDs::CBlockHeaderAndShortTxIDs(const CBlock &block) : nonce(GetRand(std::numeric_limits::max())), shorttxids(block.vtx.size() - 1), prefilledtxn(1), header(block) { FillShortTxIDSelector(); // TODO: Use our mempool prior to block acceptance to predictively fill more // than just the coinbase. prefilledtxn[0] = {0, block.vtx[0]}; for (size_t i = 1; i < block.vtx.size(); i++) { const CTransaction &tx = *block.vtx[i]; shorttxids[i - 1] = GetShortID(tx.GetHash()); } } void CBlockHeaderAndShortTxIDs::FillShortTxIDSelector() const { CDataStream stream(SER_NETWORK, PROTOCOL_VERSION); stream << header << nonce; CSHA256 hasher; hasher.Write((uint8_t *)&(*stream.begin()), stream.end() - stream.begin()); uint256 shorttxidhash; hasher.Finalize(shorttxidhash.begin()); shorttxidk0 = shorttxidhash.GetUint64(0); shorttxidk1 = shorttxidhash.GetUint64(1); } uint64_t CBlockHeaderAndShortTxIDs::GetShortID(const uint256 &txhash) const { static_assert(SHORTTXIDS_LENGTH == 6, "shorttxids calculation assumes 6-byte shorttxids"); return SipHashUint256(shorttxidk0, shorttxidk1, txhash) & 0xffffffffffffL; } ReadStatus PartiallyDownloadedBlock::InitData( const CBlockHeaderAndShortTxIDs &cmpctblock, const std::vector> &extra_txns) { if (cmpctblock.header.IsNull() || (cmpctblock.shorttxids.empty() && cmpctblock.prefilledtxn.empty())) { return READ_STATUS_INVALID; } if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > config->GetMaxBlockSize() / MIN_TRANSACTION_SIZE) { return READ_STATUS_INVALID; } assert(header.IsNull() && txns_available.empty()); header = cmpctblock.header; txns_available.resize(cmpctblock.BlockTxCount()); int64_t lastprefilledindex = -1; for (size_t i = 0; i < cmpctblock.prefilledtxn.size(); i++) { auto &prefilledtxn = cmpctblock.prefilledtxn[i]; if (prefilledtxn.tx->IsNull()) { return READ_STATUS_INVALID; } // index is a uint32_t, so can't overflow here. lastprefilledindex += prefilledtxn.index + 1; if (lastprefilledindex > std::numeric_limits::max()) { return READ_STATUS_INVALID; } if (uint32_t(lastprefilledindex) > cmpctblock.shorttxids.size() + i) { // If we are inserting a tx at an index greater than our full list // of shorttxids plus the number of prefilled txn we've inserted, // then we have txn for which we have neither a prefilled txn or a // shorttxid! return READ_STATUS_INVALID; } txns_available[lastprefilledindex] = prefilledtxn.tx; } prefilled_count = cmpctblock.prefilledtxn.size(); // Calculate map of txids -> positions and check mempool to see what we have // (or don't). Because well-formed cmpctblock messages will have a // (relatively) uniform distribution of short IDs, any highly-uneven // distribution of elements can be safely treated as a READ_STATUS_FAILED. std::unordered_map shorttxids( cmpctblock.shorttxids.size()); uint32_t index_offset = 0; for (size_t i = 0; i < cmpctblock.shorttxids.size(); i++) { while (txns_available[i + index_offset]) { index_offset++; } shorttxids[cmpctblock.shorttxids[i]] = i + index_offset; // To determine the chance that the number of entries in a bucket // exceeds N, we use the fact that the number of elements in a single // bucket is binomially distributed (with n = the number of shorttxids // S, and p = 1 / the number of buckets), that in the worst case the // number of buckets is equal to S (due to std::unordered_map having a // default load factor of 1.0), and that the chance for any bucket to // exceed N elements is at most buckets * (the chance that any given // bucket is above N elements). Thus: P(max_elements_per_bucket > N) <= // S * (1 - cdf(binomial(n=S,p=1/S), N)). If we assume blocks of up to // 16000, allowing 12 elements per bucket should only fail once per ~1 // million block transfers (per peer and connection). if (shorttxids.bucket_size( shorttxids.bucket(cmpctblock.shorttxids[i])) > 12) { return READ_STATUS_FAILED; } } // TODO: in the shortid-collision case, we should instead request both // transactions which collided. Falling back to full-block-request here is // overkill. if (shorttxids.size() != cmpctblock.shorttxids.size()) { // Short ID collision return READ_STATUS_FAILED; } std::vector have_txn(txns_available.size()); { LOCK(pool->cs); const std::vector> &vTxHashes = pool->vTxHashes; for (auto txHash : vTxHashes) { uint64_t shortid = cmpctblock.GetShortID(txHash.first); std::unordered_map::iterator idit = shorttxids.find(shortid); if (idit != shorttxids.end()) { if (!have_txn[idit->second]) { txns_available[idit->second] = txHash.second->GetSharedTx(); have_txn[idit->second] = true; mempool_count++; } else { // If we find two mempool txn that match the short id, just // request it. This should be rare enough that the extra // bandwidth doesn't matter, but eating a round-trip due to // FillBlock failure would be annoying. if (txns_available[idit->second]) { txns_available[idit->second].reset(); mempool_count--; } } } // Though ideally we'd continue scanning for the // two-txn-match-shortid case, the performance win of an early exit // here is too good to pass up and worth the extra risk. if (mempool_count == shorttxids.size()) { break; } } } for (auto &extra_txn : extra_txns) { uint64_t shortid = cmpctblock.GetShortID(extra_txn.first); std::unordered_map::iterator idit = shorttxids.find(shortid); if (idit != shorttxids.end()) { if (!have_txn[idit->second]) { txns_available[idit->second] = extra_txn.second; have_txn[idit->second] = true; mempool_count++; extra_count++; } else { // If we find two mempool/extra txn that match the short id, // just request it. This should be rare enough that the extra // bandwidth doesn't matter, but eating a round-trip due to // FillBlock failure would be annoying. Note that we don't want // duplication between extra_txns and mempool to trigger this // case, so we compare hashes first. if (txns_available[idit->second] && txns_available[idit->second]->GetHash() != extra_txn.second->GetHash()) { txns_available[idit->second].reset(); mempool_count--; extra_count--; } } } // Though ideally we'd continue scanning for the two-txn-match-shortid // case, the performance win of an early exit here is too good to pass // up and worth the extra risk. if (mempool_count == shorttxids.size()) { break; } } LogPrint(BCLog::CMPCTBLOCK, "Initialized PartiallyDownloadedBlock for block %s using a " "cmpctblock of size %lu\n", cmpctblock.header.GetHash().ToString(), - GetSerializeSize(cmpctblock, SER_NETWORK, PROTOCOL_VERSION)); + GetSerializeSize(cmpctblock, PROTOCOL_VERSION)); return READ_STATUS_OK; } bool PartiallyDownloadedBlock::IsTxAvailable(size_t index) const { assert(!header.IsNull()); assert(index < txns_available.size()); return txns_available[index] != nullptr; } ReadStatus PartiallyDownloadedBlock::FillBlock( CBlock &block, const std::vector &vtx_missing) { assert(!header.IsNull()); uint256 hash = header.GetHash(); block = header; block.vtx.resize(txns_available.size()); size_t tx_missing_offset = 0; for (size_t i = 0; i < txns_available.size(); i++) { auto &txn_available = txns_available[i]; if (!txn_available) { if (vtx_missing.size() <= tx_missing_offset) { return READ_STATUS_INVALID; } block.vtx[i] = vtx_missing[tx_missing_offset++]; } else { block.vtx[i] = std::move(txn_available); } } // Make sure we can't call FillBlock again. header.SetNull(); txns_available.clear(); if (vtx_missing.size() != tx_missing_offset) { return READ_STATUS_INVALID; } CValidationState state; if (!CheckBlock(block, state, config->GetChainParams().GetConsensus(), BlockValidationOptions(*config))) { // TODO: We really want to just check merkle tree manually here, but // that is expensive, and CheckBlock caches a block's "checked-status" // (in the CBlock?). CBlock should be able to check its own merkle root // and cache that check. if (state.CorruptionPossible()) { // Possible Short ID collision. return READ_STATUS_FAILED; } return READ_STATUS_CHECKBLOCK_FAILED; } LogPrint(BCLog::CMPCTBLOCK, "Successfully reconstructed block %s with %lu txn prefilled, %lu " "txn from mempool (incl at least %lu from extra pool) and %lu txn " "requested\n", hash.ToString(), prefilled_count, mempool_count, extra_count, vtx_missing.size()); if (vtx_missing.size() < 5) { for (const auto &tx : vtx_missing) { LogPrint(BCLog::CMPCTBLOCK, "Reconstructed block %s required tx %s\n", hash.ToString(), tx->GetId().ToString()); } } return READ_STATUS_OK; } diff --git a/src/coins.cpp b/src/coins.cpp index 35fa0ead19..b60aac2b47 100644 --- a/src/coins.cpp +++ b/src/coins.cpp @@ -1,348 +1,348 @@ // 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 #include bool CCoinsView::GetCoin(const COutPoint &outpoint, Coin &coin) const { return false; } BlockHash CCoinsView::GetBestBlock() const { return BlockHash(); } std::vector CCoinsView::GetHeadBlocks() const { return std::vector(); } bool CCoinsView::BatchWrite(CCoinsMap &mapCoins, const BlockHash &hashBlock) { return false; } CCoinsViewCursor *CCoinsView::Cursor() const { return nullptr; } bool CCoinsView::HaveCoin(const COutPoint &outpoint) const { Coin coin; return GetCoin(outpoint, coin); } CCoinsViewBacked::CCoinsViewBacked(CCoinsView *viewIn) : base(viewIn) {} bool CCoinsViewBacked::GetCoin(const COutPoint &outpoint, Coin &coin) const { return base->GetCoin(outpoint, coin); } bool CCoinsViewBacked::HaveCoin(const COutPoint &outpoint) const { return base->HaveCoin(outpoint); } BlockHash CCoinsViewBacked::GetBestBlock() const { return base->GetBestBlock(); } std::vector CCoinsViewBacked::GetHeadBlocks() const { return base->GetHeadBlocks(); } void CCoinsViewBacked::SetBackend(CCoinsView &viewIn) { base = &viewIn; } bool CCoinsViewBacked::BatchWrite(CCoinsMap &mapCoins, const BlockHash &hashBlock) { return base->BatchWrite(mapCoins, hashBlock); } CCoinsViewCursor *CCoinsViewBacked::Cursor() const { return base->Cursor(); } size_t CCoinsViewBacked::EstimateSize() const { return base->EstimateSize(); } SaltedOutpointHasher::SaltedOutpointHasher() : k0(GetRand(std::numeric_limits::max())), k1(GetRand(std::numeric_limits::max())) {} CCoinsViewCache::CCoinsViewCache(CCoinsView *baseIn) : CCoinsViewBacked(baseIn), cachedCoinsUsage(0) {} size_t CCoinsViewCache::DynamicMemoryUsage() const { return memusage::DynamicUsage(cacheCoins) + cachedCoinsUsage; } CCoinsMap::iterator CCoinsViewCache::FetchCoin(const COutPoint &outpoint) const { CCoinsMap::iterator it = cacheCoins.find(outpoint); if (it != cacheCoins.end()) { return it; } Coin tmp; if (!base->GetCoin(outpoint, tmp)) { return cacheCoins.end(); } CCoinsMap::iterator ret = cacheCoins .emplace(std::piecewise_construct, std::forward_as_tuple(outpoint), std::forward_as_tuple(std::move(tmp))) .first; if (ret->second.coin.IsSpent()) { // The parent only has an empty entry for this outpoint; we can consider // our version as fresh. ret->second.flags = CCoinsCacheEntry::FRESH; } cachedCoinsUsage += ret->second.coin.DynamicMemoryUsage(); return ret; } bool CCoinsViewCache::GetCoin(const COutPoint &outpoint, Coin &coin) const { CCoinsMap::const_iterator it = FetchCoin(outpoint); if (it == cacheCoins.end()) { return false; } coin = it->second.coin; return !coin.IsSpent(); } void CCoinsViewCache::AddCoin(const COutPoint &outpoint, Coin coin, bool possible_overwrite) { assert(!coin.IsSpent()); if (coin.GetTxOut().scriptPubKey.IsUnspendable()) { return; } CCoinsMap::iterator it; bool inserted; std::tie(it, inserted) = cacheCoins.emplace(std::piecewise_construct, std::forward_as_tuple(outpoint), std::tuple<>()); bool fresh = false; if (!inserted) { cachedCoinsUsage -= it->second.coin.DynamicMemoryUsage(); } if (!possible_overwrite) { if (!it->second.coin.IsSpent()) { throw std::logic_error( "Adding new coin that replaces non-pruned entry"); } fresh = !(it->second.flags & CCoinsCacheEntry::DIRTY); } it->second.coin = std::move(coin); it->second.flags |= CCoinsCacheEntry::DIRTY | (fresh ? CCoinsCacheEntry::FRESH : 0); cachedCoinsUsage += it->second.coin.DynamicMemoryUsage(); } void AddCoins(CCoinsViewCache &cache, const CTransaction &tx, int nHeight, bool check) { bool fCoinbase = tx.IsCoinBase(); const TxId txid = tx.GetId(); for (size_t i = 0; i < tx.vout.size(); ++i) { const COutPoint outpoint(txid, i); bool overwrite = check ? cache.HaveCoin(outpoint) : fCoinbase; // Always set the possible_overwrite flag to AddCoin for coinbase txn, // in order to correctly deal with the pre-BIP30 occurrences of // duplicate coinbase transactions. cache.AddCoin(outpoint, Coin(tx.vout[i], nHeight, fCoinbase), overwrite); } } bool CCoinsViewCache::SpendCoin(const COutPoint &outpoint, Coin *moveout) { CCoinsMap::iterator it = FetchCoin(outpoint); if (it == cacheCoins.end()) { return false; } cachedCoinsUsage -= it->second.coin.DynamicMemoryUsage(); if (moveout) { *moveout = std::move(it->second.coin); } if (it->second.flags & CCoinsCacheEntry::FRESH) { cacheCoins.erase(it); } else { it->second.flags |= CCoinsCacheEntry::DIRTY; it->second.coin.Clear(); } return true; } static const Coin coinEmpty; const Coin &CCoinsViewCache::AccessCoin(const COutPoint &outpoint) const { CCoinsMap::const_iterator it = FetchCoin(outpoint); if (it == cacheCoins.end()) { return coinEmpty; } return it->second.coin; } bool CCoinsViewCache::HaveCoin(const COutPoint &outpoint) const { CCoinsMap::const_iterator it = FetchCoin(outpoint); return it != cacheCoins.end() && !it->second.coin.IsSpent(); } bool CCoinsViewCache::HaveCoinInCache(const COutPoint &outpoint) const { CCoinsMap::const_iterator it = cacheCoins.find(outpoint); return (it != cacheCoins.end() && !it->second.coin.IsSpent()); } BlockHash CCoinsViewCache::GetBestBlock() const { if (hashBlock.IsNull()) { hashBlock = base->GetBestBlock(); } return hashBlock; } void CCoinsViewCache::SetBestBlock(const BlockHash &hashBlockIn) { hashBlock = hashBlockIn; } bool CCoinsViewCache::BatchWrite(CCoinsMap &mapCoins, const BlockHash &hashBlockIn) { for (CCoinsMap::iterator it = mapCoins.begin(); it != mapCoins.end(); it = mapCoins.erase(it)) { // Ignore non-dirty entries (optimization). if (!(it->second.flags & CCoinsCacheEntry::DIRTY)) { continue; } CCoinsMap::iterator itUs = cacheCoins.find(it->first); if (itUs == cacheCoins.end()) { // The parent cache does not have an entry, while the child does // We can ignore it if it's both FRESH and pruned in the child if (!(it->second.flags & CCoinsCacheEntry::FRESH && it->second.coin.IsSpent())) { // Otherwise we will need to create it in the parent and // move the data up and mark it as dirty CCoinsCacheEntry &entry = cacheCoins[it->first]; entry.coin = std::move(it->second.coin); cachedCoinsUsage += entry.coin.DynamicMemoryUsage(); entry.flags = CCoinsCacheEntry::DIRTY; // We can mark it FRESH in the parent if it was FRESH in the // child. Otherwise it might have just been flushed from the // parent's cache and already exist in the grandparent if (it->second.flags & CCoinsCacheEntry::FRESH) { entry.flags |= CCoinsCacheEntry::FRESH; } } } else { // Assert that the child cache entry was not marked FRESH if the // parent cache entry has unspent outputs. If this ever happens, // it means the FRESH flag was misapplied and there is a logic // error in the calling code. if ((it->second.flags & CCoinsCacheEntry::FRESH) && !itUs->second.coin.IsSpent()) { throw std::logic_error("FRESH flag misapplied to cache " "entry for base transaction with " "spendable outputs"); } // Found the entry in the parent cache if ((itUs->second.flags & CCoinsCacheEntry::FRESH) && it->second.coin.IsSpent()) { // The grandparent does not have an entry, and the child is // modified and being pruned. This means we can just delete // it from the parent. cachedCoinsUsage -= itUs->second.coin.DynamicMemoryUsage(); cacheCoins.erase(itUs); } else { // A normal modification. cachedCoinsUsage -= itUs->second.coin.DynamicMemoryUsage(); itUs->second.coin = std::move(it->second.coin); cachedCoinsUsage += itUs->second.coin.DynamicMemoryUsage(); itUs->second.flags |= CCoinsCacheEntry::DIRTY; // NOTE: It is possible the child has a FRESH flag here in // the event the entry we found in the parent is pruned. But // we must not copy that FRESH flag to the parent as that // pruned state likely still needs to be communicated to the // grandparent. } } } hashBlock = hashBlockIn; return true; } bool CCoinsViewCache::Flush() { bool fOk = base->BatchWrite(cacheCoins, hashBlock); cacheCoins.clear(); cachedCoinsUsage = 0; return fOk; } void CCoinsViewCache::Uncache(const COutPoint &outpoint) { CCoinsMap::iterator it = cacheCoins.find(outpoint); if (it != cacheCoins.end() && it->second.flags == 0) { cachedCoinsUsage -= it->second.coin.DynamicMemoryUsage(); cacheCoins.erase(it); } } unsigned int CCoinsViewCache::GetCacheSize() const { return cacheCoins.size(); } const CTxOut &CCoinsViewCache::GetOutputFor(const CTxIn &input) const { const Coin &coin = AccessCoin(input.prevout); assert(!coin.IsSpent()); return coin.GetTxOut(); } Amount CCoinsViewCache::GetValueIn(const CTransaction &tx) const { if (tx.IsCoinBase()) { return Amount::zero(); } Amount nResult = Amount::zero(); for (size_t i = 0; i < tx.vin.size(); i++) { nResult += GetOutputFor(tx.vin[i]).nValue; } return nResult; } bool CCoinsViewCache::HaveInputs(const CTransaction &tx) const { if (tx.IsCoinBase()) { return true; } for (size_t i = 0; i < tx.vin.size(); i++) { if (!HaveCoin(tx.vin[i].prevout)) { return false; } } return true; } double CCoinsViewCache::GetPriority(const CTransaction &tx, int nHeight, Amount &inChainInputValue) const { inChainInputValue = Amount::zero(); if (tx.IsCoinBase()) { return 0.0; } double dResult = 0.0; for (const CTxIn &txin : tx.vin) { const Coin &coin = AccessCoin(txin.prevout); if (coin.IsSpent()) { continue; } if (int64_t(coin.GetHeight()) <= nHeight) { dResult += double(coin.GetTxOut().nValue / SATOSHI) * (nHeight - coin.GetHeight()); inChainInputValue += coin.GetTxOut().nValue; } } return tx.ComputePriority(dResult); } // TODO: merge with similar definition in undo.h. static const size_t MAX_OUTPUTS_PER_TX = - MAX_TX_SIZE / ::GetSerializeSize(CTxOut(), SER_NETWORK, PROTOCOL_VERSION); + MAX_TX_SIZE / ::GetSerializeSize(CTxOut(), PROTOCOL_VERSION); const Coin &AccessByTxid(const CCoinsViewCache &view, const TxId &txid) { for (uint32_t n = 0; n < MAX_OUTPUTS_PER_TX; n++) { const Coin &alternate = view.AccessCoin(COutPoint(txid, n)); if (!alternate.IsSpent()) { return alternate; } } return coinEmpty; } diff --git a/src/consensus/tx_verify.cpp b/src/consensus/tx_verify.cpp index 65d3b505a3..f4acc9ce27 100644 --- a/src/consensus/tx_verify.cpp +++ b/src/consensus/tx_verify.cpp @@ -1,332 +1,331 @@ // Copyright (c) 2018 The Bitcoin 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 #include #include #include #include #include