1  // Copyright (c) 2016-present 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 <chainparams.h>
  7  #include <common/system.h>
  8  #include <consensus/consensus.h>
  9  #include <consensus/validation.h>
 10  #include <crypto/sha256.h>
 11  #include <crypto/siphash.h>
 12  #include <logging.h>
 13  #include <random.h>
 14  #include <streams.h>
 15  #include <txmempool.h>
 16  #include <validation.h>
 17  
 18  #include <unordered_map>
 19  
 20  CBlockHeaderAndShortTxIDs::CBlockHeaderAndShortTxIDs(const CBlock& block, uint64_t nonce)
 21      : nonce(nonce),
 22        shorttxids(block.vtx.size() - 1),
 23        prefilledtxn(1),
 24        header(block)
 25  {
 26      FillShortTxIDSelector();
 27      // TODO: Use our mempool prior to block acceptance to predictively fill more than just the coinbase
 28      prefilledtxn[0] = {0, block.vtx[0]};
 29      for (size_t i = 1; i < block.vtx.size(); i++) {
 30          const CTransaction& tx = *block.vtx[i];
 31          shorttxids[i - 1] = GetShortID(tx.GetWitnessHash());
 32      }
 33  }
 34  
 35  void CBlockHeaderAndShortTxIDs::FillShortTxIDSelector() const
 36  {
 37      DataStream stream{};
 38      stream << header << nonce;
 39      CSHA256 hasher;
 40      hasher.Write((unsigned char*)&(*stream.begin()), stream.end() - stream.begin());
 41      uint256 shorttxidhash;
 42      hasher.Finalize(shorttxidhash.begin());
 43      m_hasher.emplace(shorttxidhash.GetUint64(0), shorttxidhash.GetUint64(1));
 44  }
 45  
 46  uint64_t CBlockHeaderAndShortTxIDs::GetShortID(const Wtxid& wtxid) const
 47  {
 48      static_assert(SHORTTXIDS_LENGTH == 6, "shorttxids calculation assumes 6-byte shorttxids");
 49      return (*Assert(m_hasher))(wtxid.ToUint256()) & 0xffffffffffffL;
 50  }
 51  
 52  /* Reconstructing a compact block is in the hot-path for block relay,
 53   * so we want to do it as quickly as possible. Because this often
 54   * involves iterating over the entire mempool, we put all the data we
 55   * need (ie the wtxid and a reference to the actual transaction data)
 56   * in a vector and iterate over the vector directly. This allows optimal
 57   * CPU caching behaviour, at a cost of only 40 bytes per transaction.
 58   */
 59  ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& cmpctblock, const std::vector<std::pair<Wtxid, CTransactionRef>>& extra_txn)
 60  {
 61      LogDebug(BCLog::CMPCTBLOCK, "Initializing PartiallyDownloadedBlock for block %s using a cmpctblock of %u bytes\n", cmpctblock.header.GetHash().ToString(), GetSerializeSize(cmpctblock));
 62      if (cmpctblock.header.IsNull() || (cmpctblock.shorttxids.empty() && cmpctblock.prefilledtxn.empty()))
 63          return READ_STATUS_INVALID;
 64      if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > MAX_BLOCK_WEIGHT / MIN_SERIALIZABLE_TRANSACTION_WEIGHT)
 65          return READ_STATUS_INVALID;
 66  
 67      if (!header.IsNull() || !txn_available.empty()) return READ_STATUS_INVALID;
 68  
 69      header = cmpctblock.header;
 70      txn_available.resize(cmpctblock.BlockTxCount());
 71  
 72      int32_t lastprefilledindex = -1;
 73      for (size_t i = 0; i < cmpctblock.prefilledtxn.size(); i++) {
 74          if (cmpctblock.prefilledtxn[i].tx->IsNull())
 75              return READ_STATUS_INVALID;
 76  
 77          lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1; //index is a uint16_t, so can't overflow here
 78          if (lastprefilledindex > std::numeric_limits<uint16_t>::max())
 79              return READ_STATUS_INVALID;
 80          if ((uint32_t)lastprefilledindex > cmpctblock.shorttxids.size() + i) {
 81              // If we are inserting a tx at an index greater than our full list of shorttxids
 82              // plus the number of prefilled txn we've inserted, then we have txn for which we
 83              // have neither a prefilled txn or a shorttxid!
 84              return READ_STATUS_INVALID;
 85          }
 86          txn_available[lastprefilledindex] = cmpctblock.prefilledtxn[i].tx;
 87      }
 88      prefilled_count = cmpctblock.prefilledtxn.size();
 89  
 90      // Calculate map of txids -> positions and check mempool to see what we have (or don't)
 91      // Because well-formed cmpctblock messages will have a (relatively) uniform distribution
 92      // of short IDs, any highly-uneven distribution of elements can be safely treated as a
 93      // READ_STATUS_FAILED.
 94      std::unordered_map<uint64_t, uint16_t> shorttxids(cmpctblock.shorttxids.size());
 95      uint16_t index_offset = 0;
 96      for (size_t i = 0; i < cmpctblock.shorttxids.size(); i++) {
 97          while (txn_available[i + index_offset])
 98              index_offset++;
 99          shorttxids[cmpctblock.shorttxids[i]] = i + index_offset;
100          // To determine the chance that the number of entries in a bucket exceeds N,
101          // we use the fact that the number of elements in a single bucket is
102          // binomially distributed (with n = the number of shorttxids S, and p =
103          // 1 / the number of buckets), that in the worst case the number of buckets is
104          // equal to S (due to std::unordered_map having a default load factor of 1.0),
105          // and that the chance for any bucket to exceed N elements is at most
106          // buckets * (the chance that any given bucket is above N elements).
107          // Thus: P(max_elements_per_bucket > N) <= S * (1 - cdf(binomial(n=S,p=1/S), N)).
108          // If we assume blocks of up to 16000, allowing 12 elements per bucket should
109          // only fail once per ~1 million block transfers (per peer and connection).
110          if (shorttxids.bucket_size(shorttxids.bucket(cmpctblock.shorttxids[i])) > 12)
111              return READ_STATUS_FAILED;
112      }
113      // TODO: in the shortid-collision case, we should instead request both transactions
114      // which collided. Falling back to full-block-request here is overkill.
115      if (shorttxids.size() != cmpctblock.shorttxids.size())
116          return READ_STATUS_FAILED; // Short ID collision
117  
118      std::vector<bool> have_txn(txn_available.size());
119      {
120      LOCK(pool->cs);
121      for (const auto& [wtxid, txit] : pool->txns_randomized) {
122          uint64_t shortid = cmpctblock.GetShortID(wtxid);
123          std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
124          if (idit != shorttxids.end()) {
125              if (!have_txn[idit->second]) {
126                  txn_available[idit->second] = txit->GetSharedTx();
127                  have_txn[idit->second]  = true;
128                  mempool_count++;
129              } else {
130                  // If we find two mempool txn that match the short id, just request it.
131                  // This should be rare enough that the extra bandwidth doesn't matter,
132                  // but eating a round-trip due to FillBlock failure would be annoying
133                  if (txn_available[idit->second]) {
134                      txn_available[idit->second].reset();
135                      mempool_count--;
136                  }
137              }
138          }
139          // Though ideally we'd continue scanning for the two-txn-match-shortid case,
140          // the performance win of an early exit here is too good to pass up and worth
141          // the extra risk.
142          if (mempool_count == shorttxids.size())
143              break;
144      }
145      }
146  
147      for (size_t i = 0; i < extra_txn.size(); i++) {
148          uint64_t shortid = cmpctblock.GetShortID(extra_txn[i].first);
149          std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
150          if (idit != shorttxids.end()) {
151              if (!have_txn[idit->second]) {
152                  txn_available[idit->second] = extra_txn[i].second;
153                  have_txn[idit->second]  = true;
154                  mempool_count++;
155                  extra_count++;
156              } else {
157                  // If we find two mempool/extra txn that match the short id, just
158                  // request it.
159                  // This should be rare enough that the extra bandwidth doesn't matter,
160                  // but eating a round-trip due to FillBlock failure would be annoying
161                  // Note that we don't want duplication between extra_txn and mempool to
162                  // trigger this case, so we compare witness hashes first
163                  if (txn_available[idit->second] &&
164                          txn_available[idit->second]->GetWitnessHash() != extra_txn[i].second->GetWitnessHash()) {
165                      txn_available[idit->second].reset();
166                      mempool_count--;
167                      extra_count--;
168                  }
169              }
170          }
171          // Though ideally we'd continue scanning for the two-txn-match-shortid case,
172          // the performance win of an early exit here is too good to pass up and worth
173          // the extra risk.
174          if (mempool_count == shorttxids.size())
175              break;
176      }
177  
178      LogDebug(BCLog::CMPCTBLOCK, "Initialized PartiallyDownloadedBlock for block %s using a cmpctblock of %u bytes\n", cmpctblock.header.GetHash().ToString(), GetSerializeSize(cmpctblock));
179  
180      return READ_STATUS_OK;
181  }
182  
183  bool PartiallyDownloadedBlock::IsTxAvailable(size_t index) const
184  {
185      if (header.IsNull()) return false;
186  
187      assert(index < txn_available.size());
188      return txn_available[index] != nullptr;
189  }
190  
191  ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector<CTransactionRef>& vtx_missing, bool segwit_active)
192  {
193      if (header.IsNull()) return READ_STATUS_INVALID;
194  
195      block = header;
196      block.vtx.resize(txn_available.size());
197  
198      size_t tx_missing_offset = 0;
199      for (size_t i = 0; i < txn_available.size(); i++) {
200          if (!txn_available[i]) {
201              if (tx_missing_offset >= vtx_missing.size()) {
202                  return READ_STATUS_INVALID;
203              }
204              block.vtx[i] = vtx_missing[tx_missing_offset++];
205          } else {
206              block.vtx[i] = std::move(txn_available[i]);
207          }
208      }
209  
210      // Make sure we can't call FillBlock again.
211      header.SetNull();
212      txn_available.clear();
213  
214      if (vtx_missing.size() != tx_missing_offset) {
215          return READ_STATUS_INVALID;
216      }
217  
218      // Check for possible mutations early now that we have a seemingly good block
219      IsBlockMutatedFn check_mutated{m_check_block_mutated_mock ? m_check_block_mutated_mock : IsBlockMutated};
220      if (check_mutated(/*block=*/block, /*check_witness_root=*/segwit_active)) {
221          return READ_STATUS_FAILED; // Possible Short ID collision
222      }
223  
224      if (LogAcceptCategory(BCLog::CMPCTBLOCK, BCLog::Level::Debug)) {
225          const uint256 hash{block.GetHash()};
226          uint32_t tx_missing_size{0};
227          for (const auto& tx : vtx_missing) tx_missing_size += tx->ComputeTotalSize();
228          LogDebug(BCLog::CMPCTBLOCK, "Successfully reconstructed block %s with %u txn prefilled, %u txn from mempool (incl at least %u from extra pool) and %u txn (%u bytes) requested\n", hash.ToString(), prefilled_count, mempool_count, extra_count, vtx_missing.size(), tx_missing_size);
229          if (vtx_missing.size() < 5) {
230              for (const auto& tx : vtx_missing) {
231                  LogDebug(BCLog::CMPCTBLOCK, "Reconstructed block %s required tx %s\n", hash.ToString(), tx->GetHash().ToString());
232              }
233          }
234      }
235  
236      return READ_STATUS_OK;
237  }