Line data    Source code

       1             : // Copyright (c) 2016-2019 The Bitcoin Core developers
       2             : // Distributed under the MIT software license, see the accompanying
       3             : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       4             : 
       5             : #include <blockencodings.h>
       6             : #include <consensus/consensus.h>
       7             : #include <consensus/validation.h>
       8             : #include <chainparams.h>
       9             : #include <crypto/sha256.h>
      10             : #include <crypto/siphash.h>
      11             : #include <random.h>
      12             : #include <streams.h>
      13             : #include <txmempool.h>
      14             : #include <validation.h>
      15             : #include <util/system.h>
      16             : 
      17             : #include <unordered_map>
      18             : 
      19       71630 : CBlockHeaderAndShortTxIDs::CBlockHeaderAndShortTxIDs(const CBlock& block, bool fUseWTXID) :
      20       35815 :         nonce(GetRand(std::numeric_limits<uint64_t>::max())),
      21       71630 :         shorttxids(block.vtx.size() - 1), prefilledtxn(1), header(block) {
      22       35815 :     FillShortTxIDSelector();
      23             :     //TODO: Use our mempool prior to block acceptance to predictively fill more than just the coinbase
      24       35815 :     prefilledtxn[0] = {0, block.vtx[0]};
      25       83109 :     for (size_t i = 1; i < block.vtx.size(); i++) {
      26       47294 :         const CTransaction& tx = *block.vtx[i];
      27       47294 :         shorttxids[i - 1] = GetShortID(fUseWTXID ? tx.GetWitnessHash() : tx.GetHash());
      28             :     }
      29       71630 : }
      30             : 
      31       47800 : void CBlockHeaderAndShortTxIDs::FillShortTxIDSelector() const {
      32       47800 :     CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
      33       47800 :     stream << header << nonce;
      34       47800 :     CSHA256 hasher;
      35       47800 :     hasher.Write((unsigned char*)&(*stream.begin()), stream.end() - stream.begin());
      36       47800 :     uint256 shorttxidhash;
      37       47800 :     hasher.Finalize(shorttxidhash.begin());
      38       47800 :     shorttxidk0 = shorttxidhash.GetUint64(0);
      39       47800 :     shorttxidk1 = shorttxidhash.GetUint64(1);
      40       47800 : }
      41             : 
      42      190715 : uint64_t CBlockHeaderAndShortTxIDs::GetShortID(const uint256& txhash) const {
      43             :     static_assert(SHORTTXIDS_LENGTH == 6, "shorttxids calculation assumes 6-byte shorttxids");
      44      190715 :     return SipHashUint256(shorttxidk0, shorttxidk1, txhash) & 0xffffffffffffL;
      45             : }
      46             : 
      47             : 
      48             : 
      49       10119 : ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& cmpctblock, const std::vector<std::pair<uint256, CTransactionRef>>& extra_txn) {
      50       10119 :     if (cmpctblock.header.IsNull() || (cmpctblock.shorttxids.empty() && cmpctblock.prefilledtxn.empty()))
      51           0 :         return READ_STATUS_INVALID;
      52       10119 :     if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > MAX_BLOCK_WEIGHT / MIN_SERIALIZABLE_TRANSACTION_WEIGHT)
      53           0 :         return READ_STATUS_INVALID;
      54             : 
      55       10119 :     assert(header.IsNull() && txn_available.empty());
      56       10119 :     header = cmpctblock.header;
      57       10119 :     txn_available.resize(cmpctblock.BlockTxCount());
      58             : 
      59             :     int32_t lastprefilledindex = -1;
      60       20245 :     for (size_t i = 0; i < cmpctblock.prefilledtxn.size(); i++) {
      61       10127 :         if (cmpctblock.prefilledtxn[i].tx->IsNull())
      62           0 :             return READ_STATUS_INVALID;
      63             : 
      64       10127 :         lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1; //index is a uint16_t, so can't overflow here
      65       10127 :         if (lastprefilledindex > std::numeric_limits<uint16_t>::max())
      66           0 :             return READ_STATUS_INVALID;
      67       10127 :         if ((uint32_t)lastprefilledindex > cmpctblock.shorttxids.size() + i) {
      68             :             // If we are inserting a tx at an index greater than our full list of shorttxids
      69             :             // plus the number of prefilled txn we've inserted, then we have txn for which we
      70             :             // have neither a prefilled txn or a shorttxid!
      71           1 :             return READ_STATUS_INVALID;
      72             :         }
      73       10126 :         txn_available[lastprefilledindex] = cmpctblock.prefilledtxn[i].tx;
      74             :     }
      75       10118 :     prefilled_count = cmpctblock.prefilledtxn.size();
      76             : 
      77             :     // Calculate map of txids -> positions and check mempool to see what we have (or don't)
      78             :     // Because well-formed cmpctblock messages will have a (relatively) uniform distribution
      79             :     // of short IDs, any highly-uneven distribution of elements can be safely treated as a
      80             :     // READ_STATUS_FAILED.
      81       10118 :     std::unordered_map<uint64_t, uint16_t> shorttxids(cmpctblock.shorttxids.size());
      82       22989 :     uint16_t index_offset = 0;
      83       22989 :     for (size_t i = 0; i < cmpctblock.shorttxids.size(); i++) {
      84       15385 :         while (txn_available[i + index_offset])
      85        2514 :             index_offset++;
      86       12871 :         shorttxids[cmpctblock.shorttxids[i]] = i + index_offset;
      87             :         // To determine the chance that the number of entries in a bucket exceeds N,
      88             :         // we use the fact that the number of elements in a single bucket is
      89             :         // binomially distributed (with n = the number of shorttxids S, and p =
      90             :         // 1 / the number of buckets), that in the worst case the number of buckets is
      91             :         // equal to S (due to std::unordered_map having a default load factor of 1.0),
      92             :         // and that the chance for any bucket to exceed N elements is at most
      93             :         // buckets * (the chance that any given bucket is above N elements).
      94             :         // Thus: P(max_elements_per_bucket > N) <= S * (1 - cdf(binomial(n=S,p=1/S), N)).
      95             :         // If we assume blocks of up to 16000, allowing 12 elements per bucket should
      96             :         // only fail once per ~1 million block transfers (per peer and connection).
      97       12871 :         if (shorttxids.bucket_size(shorttxids.bucket(cmpctblock.shorttxids[i])) > 12)
      98           0 :             return READ_STATUS_FAILED;
      99             :     }
     100             :     // TODO: in the shortid-collision case, we should instead request both transactions
     101             :     // which collided. Falling back to full-block-request here is overkill.
     102       10118 :     if (shorttxids.size() != cmpctblock.shorttxids.size())
     103           0 :         return READ_STATUS_FAILED; // Short ID collision
     104             : 
     105       10118 :     std::vector<bool> have_txn(txn_available.size());
     106             :     {
     107       10118 :     LOCK(pool->cs);
     108       68017 :     for (size_t i = 0; i < pool->vTxHashes.size(); i++) {
     109       58227 :         uint64_t shortid = cmpctblock.GetShortID(pool->vTxHashes[i].first);
     110       58227 :         std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
     111       58227 :         if (idit != shorttxids.end()) {
     112        9179 :             if (!have_txn[idit->second]) {
     113        9179 :                 txn_available[idit->second] = pool->vTxHashes[i].second->GetSharedTx();
     114        9179 :                 have_txn[idit->second]  = true;
     115        9179 :                 mempool_count++;
     116        9179 :             } else {
     117             :                 // If we find two mempool txn that match the short id, just request it.
     118             :                 // This should be rare enough that the extra bandwidth doesn't matter,
     119             :                 // but eating a round-trip due to FillBlock failure would be annoying
     120           0 :                 if (txn_available[idit->second]) {
     121           0 :                     txn_available[idit->second].reset();
     122           0 :                     mempool_count--;
     123           0 :                 }
     124             :             }
     125             :         }
     126             :         // Though ideally we'd continue scanning for the two-txn-match-shortid case,
     127             :         // the performance win of an early exit here is too good to pass up and worth
     128             :         // the extra risk.
     129       58227 :         if (mempool_count == shorttxids.size())
     130         328 :             break;
     131       58227 :     }
     132       10118 :     }
     133             : 
     134       94972 :     for (size_t i = 0; i < extra_txn.size(); i++) {
     135       85191 :         uint64_t shortid = cmpctblock.GetShortID(extra_txn[i].first);
     136       85191 :         std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
     137       85191 :         if (idit != shorttxids.end()) {
     138         115 :             if (!have_txn[idit->second]) {
     139         115 :                 txn_available[idit->second] = extra_txn[i].second;
     140         115 :                 have_txn[idit->second]  = true;
     141         115 :                 mempool_count++;
     142         115 :                 extra_count++;
     143         115 :             } else {
     144             :                 // If we find two mempool/extra txn that match the short id, just
     145             :                 // request it.
     146             :                 // This should be rare enough that the extra bandwidth doesn't matter,
     147             :                 // but eating a round-trip due to FillBlock failure would be annoying
     148             :                 // Note that we don't want duplication between extra_txn and mempool to
     149             :                 // trigger this case, so we compare witness hashes first
     150           0 :                 if (txn_available[idit->second] &&
     151           0 :                         txn_available[idit->second]->GetWitnessHash() != extra_txn[i].second->GetWitnessHash()) {
     152           0 :                     txn_available[idit->second].reset();
     153           0 :                     mempool_count--;
     154           0 :                     extra_count--;
     155           0 :                 }
     156             :             }
     157             :         }
     158             :         // Though ideally we'd continue scanning for the two-txn-match-shortid case,
     159             :         // the performance win of an early exit here is too good to pass up and worth
     160             :         // the extra risk.
     161       85191 :         if (mempool_count == shorttxids.size())
     162         337 :             break;
     163       85191 :     }
     164             : 
     165       10118 :     LogPrint(BCLog::CMPCTBLOCK, "Initialized PartiallyDownloadedBlock for block %s using a cmpctblock of size %lu\n", cmpctblock.header.GetHash().ToString(), GetSerializeSize(cmpctblock, PROTOCOL_VERSION));
     166             : 
     167             :     return READ_STATUS_OK;
     168       20237 : }
     169             : 
     170       22876 : bool PartiallyDownloadedBlock::IsTxAvailable(size_t index) const {
     171       22876 :     assert(!header.IsNull());
     172       22876 :     assert(index < txn_available.size());
     173       22876 :     return txn_available[index] != nullptr;
     174             : }
     175             : 
     176       10121 : ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector<CTransactionRef>& vtx_missing) {
     177       10121 :     assert(!header.IsNull());
     178       10121 :     uint256 hash = header.GetHash();
     179       10121 :     block = header;
     180       10121 :     block.vtx.resize(txn_available.size());
     181             : 
     182       33074 :     size_t tx_missing_offset = 0;
     183       33074 :     for (size_t i = 0; i < txn_available.size(); i++) {
     184       22964 :         if (!txn_available[i]) {
     185        3570 :             if (vtx_missing.size() <= tx_missing_offset)
     186          11 :                 return READ_STATUS_INVALID;
     187        3559 :             block.vtx[i] = vtx_missing[tx_missing_offset++];
     188        3559 :         } else
     189       19394 :             block.vtx[i] = std::move(txn_available[i]);
     190             :     }
     191             : 
     192             :     // Make sure we can't call FillBlock again.
     193       10110 :     header.SetNull();
     194       10110 :     txn_available.clear();
     195             : 
     196       10110 :     if (vtx_missing.size() != tx_missing_offset)
     197           0 :         return READ_STATUS_INVALID;
     198             : 
     199       10110 :     BlockValidationState state;
     200       10110 :     if (!CheckBlock(block, state, Params().GetConsensus())) {
     201             :         // TODO: We really want to just check merkle tree manually here,
     202             :         // but that is expensive, and CheckBlock caches a block's
     203             :         // "checked-status" (in the CBlock?). CBlock should be able to
     204             :         // check its own merkle root and cache that check.
     205           3 :         if (state.GetResult() == BlockValidationResult::BLOCK_MUTATED)
     206           3 :             return READ_STATUS_FAILED; // Possible Short ID collision
     207           0 :         return READ_STATUS_CHECKBLOCK_FAILED;
     208             :     }
     209             : 
     210       10107 :     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());
     211       10107 :     if (vtx_missing.size() < 5) {
     212       12368 :         for (const auto& tx : vtx_missing) {
     213        2288 :             LogPrint(BCLog::CMPCTBLOCK, "Reconstructed block %s required tx %s\n", hash.ToString(), tx->GetHash().ToString());
     214             :         }
     215       10080 :     }
     216             : 
     217       10107 :     return READ_STATUS_OK;
     218       10121 : }