blockencodings.cpp
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 if (shorttxids.size() != cmpctblock.shorttxids.size()) 114 return READ_STATUS_FAILED; // Short ID collision 115 116 std::vector<bool> have_txn(txn_available.size()); 117 { 118 LOCK(pool->cs); 119 for (const auto& [wtxid, txit] : pool->txns_randomized) { 120 uint64_t shortid = cmpctblock.GetShortID(wtxid); 121 std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid); 122 if (idit != shorttxids.end()) { 123 if (!have_txn[idit->second]) { 124 txn_available[idit->second] = txit->GetSharedTx(); 125 have_txn[idit->second] = true; 126 mempool_count++; 127 } else { 128 // If we find two mempool txn that match the short id, just request it. 129 // This should be rare enough that the extra bandwidth doesn't matter, 130 // but eating a round-trip due to FillBlock failure would be annoying 131 if (txn_available[idit->second]) { 132 txn_available[idit->second].reset(); 133 mempool_count--; 134 } 135 } 136 } 137 // Though ideally we'd continue scanning for the two-txn-match-shortid case, 138 // the performance win of an early exit here is too good to pass up and worth 139 // the extra risk. 140 if (mempool_count == shorttxids.size()) 141 break; 142 } 143 } 144 145 for (size_t i = 0; i < extra_txn.size(); i++) { 146 uint64_t shortid = cmpctblock.GetShortID(extra_txn[i].first); 147 std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid); 148 if (idit != shorttxids.end()) { 149 if (!have_txn[idit->second]) { 150 txn_available[idit->second] = extra_txn[i].second; 151 have_txn[idit->second] = true; 152 mempool_count++; 153 extra_count++; 154 } else { 155 // If we find two mempool/extra txn that match the short id, just 156 // request it. 157 // This should be rare enough that the extra bandwidth doesn't matter, 158 // but eating a round-trip due to FillBlock failure would be annoying 159 // Note that we don't want duplication between extra_txn and mempool to 160 // trigger this case, so we compare witness hashes first 161 if (txn_available[idit->second] && 162 txn_available[idit->second]->GetWitnessHash() != extra_txn[i].second->GetWitnessHash()) { 163 txn_available[idit->second].reset(); 164 mempool_count--; 165 extra_count--; 166 } 167 } 168 } 169 // Though ideally we'd continue scanning for the two-txn-match-shortid case, 170 // the performance win of an early exit here is too good to pass up and worth 171 // the extra risk. 172 if (mempool_count == shorttxids.size()) 173 break; 174 } 175 176 LogDebug(BCLog::CMPCTBLOCK, "Initialized PartiallyDownloadedBlock for block %s using a cmpctblock of %u bytes\n", cmpctblock.header.GetHash().ToString(), GetSerializeSize(cmpctblock)); 177 178 return READ_STATUS_OK; 179 } 180 181 bool PartiallyDownloadedBlock::IsTxAvailable(size_t index) const 182 { 183 if (header.IsNull()) return false; 184 185 assert(index < txn_available.size()); 186 return txn_available[index] != nullptr; 187 } 188 189 ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector<CTransactionRef>& vtx_missing, bool segwit_active) 190 { 191 if (header.IsNull()) return READ_STATUS_INVALID; 192 193 block = header; 194 block.vtx.resize(txn_available.size()); 195 196 size_t tx_missing_offset = 0; 197 for (size_t i = 0; i < txn_available.size(); i++) { 198 if (!txn_available[i]) { 199 if (tx_missing_offset >= vtx_missing.size()) { 200 return READ_STATUS_INVALID; 201 } 202 block.vtx[i] = vtx_missing[tx_missing_offset++]; 203 } else { 204 block.vtx[i] = std::move(txn_available[i]); 205 } 206 } 207 208 // Make sure we can't call FillBlock again. 209 header.SetNull(); 210 txn_available.clear(); 211 212 if (vtx_missing.size() != tx_missing_offset) { 213 return READ_STATUS_INVALID; 214 } 215 216 // Check for possible mutations early now that we have a seemingly good block 217 IsBlockMutatedFn check_mutated{m_check_block_mutated_mock ? m_check_block_mutated_mock : IsBlockMutated}; 218 if (check_mutated(/*block=*/block, /*check_witness_root=*/segwit_active)) { 219 return READ_STATUS_FAILED; // Possible Short ID collision 220 } 221 222 if (LogAcceptCategory(BCLog::CMPCTBLOCK, BCLog::Level::Debug)) { 223 const uint256 hash{block.GetHash()}; 224 uint32_t tx_missing_size{0}; 225 for (const auto& tx : vtx_missing) tx_missing_size += tx->ComputeTotalSize(); 226 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); 227 if (vtx_missing.size() < 5) { 228 for (const auto& tx : vtx_missing) { 229 LogDebug(BCLog::CMPCTBLOCK, "Reconstructed block %s required tx %s\n", hash.ToString(), tx->GetHash().ToString()); 230 } 231 } 232 } 233 234 return READ_STATUS_OK; 235 }