Branch data Line data Source code
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/categories.h>
13 : : #include <random.h>
14 : : #include <streams.h>
15 : : #include <txmempool.h>
16 : : #include <util/log.h>
17 : : #include <validation.h>
18 : :
19 : : #include <unordered_map>
20 : :
21 : 100552 : CBlockHeaderAndShortTxIDs::CBlockHeaderAndShortTxIDs(const CBlock& block, uint64_t nonce)
22 : 100552 : : nonce(nonce),
23 [ - + ]: 100552 : shorttxids(block.vtx.size() - 1),
24 [ + - ]: 100552 : prefilledtxn(1),
25 [ - + ]: 100552 : header(block)
26 : : {
27 [ + - ]: 100552 : FillShortTxIDSelector();
28 : : // TODO: Use our mempool prior to block acceptance to predictively fill more than just the coinbase
29 [ - + ]: 100552 : prefilledtxn[0] = {0, block.vtx[0]};
30 [ - + + + ]: 151863 : for (size_t i = 1; i < block.vtx.size(); i++) {
31 [ + - ]: 51311 : const CTransaction& tx = *block.vtx[i];
32 [ + - ]: 51311 : shorttxids[i - 1] = GetShortID(tx.GetWitnessHash());
33 : : }
34 [ + - ]: 301656 : }
35 : :
36 : 128679 : void CBlockHeaderAndShortTxIDs::FillShortTxIDSelector() const
37 : : {
38 : 128679 : DataStream stream{};
39 [ + - + - ]: 128679 : stream << header << nonce;
40 [ + - ]: 128679 : CSHA256 hasher;
41 [ + - ]: 128679 : hasher.Write((unsigned char*)&(*stream.begin()), stream.end() - stream.begin());
42 : 128679 : uint256 shorttxidhash;
43 [ + - ]: 128679 : hasher.Finalize(shorttxidhash.begin());
44 : 128679 : m_hasher.emplace(shorttxidhash.GetUint64(0), shorttxidhash.GetUint64(1));
45 : 128679 : }
46 : :
47 : 132858 : uint64_t CBlockHeaderAndShortTxIDs::GetShortID(const Wtxid& wtxid) const
48 : : {
49 : 132858 : static_assert(SHORTTXIDS_LENGTH == 6, "shorttxids calculation assumes 6-byte shorttxids");
50 [ - + ]: 132858 : return (*Assert(m_hasher))(wtxid.ToUint256()) & 0xffffffffffffL;
51 : : }
52 : :
53 : : /* Reconstructing a compact block is in the hot-path for block relay,
54 : : * so we want to do it as quickly as possible. Because this often
55 : : * involves iterating over the entire mempool, we put all the data we
56 : : * need (ie the wtxid and a reference to the actual transaction data)
57 : : * in a vector and iterate over the vector directly. This allows optimal
58 : : * CPU caching behaviour, at a cost of only 40 bytes per transaction.
59 : : */
60 : 21836 : ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& cmpctblock, const std::vector<std::pair<Wtxid, CTransactionRef>>& extra_txn)
61 : : {
62 [ + - + - ]: 21836 : LogDebug(BCLog::CMPCTBLOCK, "Initializing PartiallyDownloadedBlock for block %s using a cmpctblock of %u bytes\n", cmpctblock.header.GetHash().ToString(), GetSerializeSize(cmpctblock));
63 [ + - + + : 21836 : if (cmpctblock.header.IsNull() || (cmpctblock.shorttxids.empty() && cmpctblock.prefilledtxn.empty()))
+ - ]
64 : : return READ_STATUS_INVALID;
65 [ - + - + : 21836 : if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > MAX_BLOCK_WEIGHT / MIN_SERIALIZABLE_TRANSACTION_WEIGHT)
+ - ]
66 : : return READ_STATUS_INVALID;
67 : :
68 [ + - + - ]: 21836 : if (!header.IsNull() || !txn_available.empty()) return READ_STATUS_INVALID;
69 : :
70 : 21836 : header = cmpctblock.header;
71 [ - + ]: 43672 : txn_available.resize(cmpctblock.BlockTxCount());
72 : :
73 : 21836 : const bool debug_log{util::log::ShouldDebugLog(BCLog::CMPCTBLOCK)};
74 : : // Track the prefills which were not already present in the mempool or extrapool.
75 [ - + ]: 21836 : std::map<Wtxid, size_t> leftover_prefills;
76 : :
77 : 21836 : int32_t lastprefilledindex = -1;
78 [ - + ]: 21836 : prefilled_count = cmpctblock.prefilledtxn.size();
79 [ + + ]: 43679 : for (size_t i = 0; i < prefilled_count; i++) {
80 [ + - ]: 21845 : if (cmpctblock.prefilledtxn[i].tx->IsNull())
81 : : return READ_STATUS_INVALID;
82 : :
83 : 21845 : lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1; //index is a uint16_t, so can't overflow here
84 [ + - ]: 21845 : if (lastprefilledindex > std::numeric_limits<uint16_t>::max())
85 : : return READ_STATUS_INVALID;
86 [ - + + + ]: 21845 : if ((uint32_t)lastprefilledindex > cmpctblock.shorttxids.size() + i) {
87 : : // If we are inserting a tx at an index greater than our full list of shorttxids
88 : : // plus the number of prefilled txn we've inserted, then we have txn for which we
89 : : // have neither a prefilled txn or a shorttxid!
90 : : return READ_STATUS_INVALID;
91 : : }
92 : :
93 [ + - ]: 21843 : if (debug_log) {
94 : 21843 : const CTransactionRef& tx{cmpctblock.prefilledtxn[i].tx};
95 [ + - ]: 21843 : const size_t tx_size{tx->ComputeTotalSize()};
96 : 21843 : prefilled_size += tx_size;
97 : :
98 [ + - ]: 21843 : leftover_prefills.emplace(tx->GetWitnessHash(), tx_size);
99 : : }
100 : 21843 : txn_available[lastprefilledindex] = cmpctblock.prefilledtxn[i].tx;
101 : : }
102 : :
103 : :
104 : : // Calculate map of txids -> positions and check mempool to see what we have (or don't)
105 : : // Because well-formed cmpctblock messages will have a (relatively) uniform distribution
106 : : // of short IDs, any highly-uneven distribution of elements can be safely treated as a
107 : : // READ_STATUS_FAILED.
108 [ - + + - ]: 21834 : std::unordered_map<uint64_t, uint16_t> shorttxids(cmpctblock.shorttxids.size());
109 : : uint16_t index_offset = 0;
110 [ - + + + ]: 35782 : for (size_t i = 0; i < cmpctblock.shorttxids.size(); i++) {
111 [ + + ]: 14968 : while (txn_available[i + index_offset])
112 : 1020 : index_offset++;
113 [ + - ]: 13948 : shorttxids[cmpctblock.shorttxids[i]] = i + index_offset;
114 : : // To determine the chance that the number of entries in a bucket exceeds N,
115 : : // we use the fact that the number of elements in a single bucket is
116 : : // binomially distributed (with n = the number of shorttxids S, and p =
117 : : // 1 / the number of buckets), that in the worst case the number of buckets is
118 : : // equal to S (due to std::unordered_map having a default load factor of 1.0),
119 : : // and that the chance for any bucket to exceed N elements is at most
120 : : // buckets * (the chance that any given bucket is above N elements).
121 : : // Thus: P(max_elements_per_bucket > N) <= S * (1 - cdf(binomial(n=S,p=1/S), N)).
122 : : // If we assume blocks of up to 16000, allowing 12 elements per bucket should
123 : : // only fail once per ~1 million block transfers (per peer and connection).
124 [ + - ]: 13948 : if (shorttxids.bucket_size(shorttxids.bucket(cmpctblock.shorttxids[i])) > 12)
125 : : return READ_STATUS_FAILED;
126 : : }
127 [ + - ]: 21834 : if (shorttxids.size() != cmpctblock.shorttxids.size())
128 : : return READ_STATUS_FAILED; // Short ID collision
129 : :
130 : 21834 : enum class TxSource : uint8_t { NONE, MEMPOOL, EXTRA, COLLIDED };
131 [ - + + - ]: 21834 : std::vector<TxSource> tx_source(txn_available.size(), TxSource::NONE);
132 : 21834 : size_t available_count = 0;
133 : 21834 : {
134 [ + - ]: 21834 : LOCK(pool->cs);
135 [ + - ]: 21834 : if (debug_log) {
136 [ + + ]: 43677 : for (auto it{leftover_prefills.begin()}; it != leftover_prefills.end();) {
137 [ + - - + ]: 21843 : if (pool->GetIter(it->first)) {
138 : 0 : ++redundant_prefilled_mempool_count;
139 : 0 : redundant_prefilled_mempool_size += it->second;
140 : 0 : it = leftover_prefills.erase(it);
141 : : } else {
142 : 21843 : ++it;
143 : : }
144 : : }
145 : : }
146 : :
147 [ + - + + ]: 99538 : for (const auto& [wtxid, txit] : pool->txns_randomized) {
148 [ + - ]: 78355 : uint64_t shortid = cmpctblock.GetShortID(wtxid);
149 : 78355 : std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
150 [ + + ]: 78355 : if (idit != shorttxids.end()) {
151 [ + - ]: 11993 : if (tx_source[idit->second] == TxSource::NONE) {
152 [ + - - + ]: 23986 : txn_available[idit->second] = txit->GetSharedTx();
153 : 11993 : tx_source[idit->second] = TxSource::MEMPOOL;
154 : 11993 : ++available_count;
155 [ # # ]: 0 : } else if (tx_source[idit->second] != TxSource::COLLIDED) {
156 : : // If we find two mempool txn that match the short id, just 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 : 0 : txn_available[idit->second].reset();
160 : 0 : --available_count;
161 : 0 : tx_source[idit->second] = TxSource::COLLIDED;
162 : : }
163 : : }
164 : : // Though ideally we'd continue scanning for the two-txn-match-shortid case,
165 : : // the performance win of an early exit here is too good to pass up and worth
166 : : // the extra risk.
167 [ + + ]: 78355 : if (available_count == shorttxids.size())
168 : : break;
169 : : }
170 : 0 : }
171 : :
172 [ - + + + ]: 24361 : for (size_t i = 0; i < extra_txn.size(); i++) {
173 [ + - ]: 3189 : uint64_t shortid = cmpctblock.GetShortID(extra_txn[i].first);
174 : 3189 : std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
175 [ + + ]: 3189 : if (idit != shorttxids.end()) {
176 [ + + ]: 310 : if (tx_source[idit->second] == TxSource::NONE) {
177 : 295 : txn_available[idit->second] = extra_txn[i].second;
178 : 295 : tx_source[idit->second] = TxSource::EXTRA;
179 : 295 : ++available_count;
180 [ + + ]: 15 : } else if (tx_source[idit->second] != TxSource::COLLIDED &&
181 [ + + ]: 13 : txn_available[idit->second]->GetWitnessHash() != extra_txn[i].second->GetWitnessHash()) {
182 : : // If we find two mempool/extra txn that match the short id, just
183 : : // request it.
184 : : // This should be rare enough that the extra bandwidth doesn't matter,
185 : : // but eating a round-trip due to FillBlock failure would be annoying
186 : : // Note that we don't want duplication between extra_txn and mempool to
187 : : // trigger this case, so we compare witness hashes first
188 : 5 : txn_available[idit->second].reset();
189 : 5 : --available_count;
190 : 5 : tx_source[idit->second] = TxSource::COLLIDED;
191 : : }
192 : : }
193 : : // Though ideally we'd continue scanning for the two-txn-match-shortid case,
194 : : // the performance win of an early exit here is too good to pass up and worth
195 : : // the extra risk.
196 [ + + ]: 3189 : if (available_count == shorttxids.size())
197 : : break;
198 : : }
199 : :
200 : :
201 [ + - ]: 21834 : if (debug_log) {
202 [ + + + + ]: 35412 : for (const auto& [id, tx] : extra_txn) {
203 [ + + ]: 13578 : if (!tx) continue;
204 : 13543 : const auto it{leftover_prefills.find(id)};
205 [ + - ]: 13543 : if (it == leftover_prefills.end()) continue;
206 : 0 : ++redundant_prefilled_extrapool_count;
207 : 0 : redundant_prefilled_extrapool_size += it->second;
208 : 0 : leftover_prefills.erase(it);
209 : : }
210 : :
211 [ - + - + ]: 21834 : Assume(txn_available.size() == tx_source.size());
212 [ - + + + ]: 57625 : for (size_t i = 0; i < txn_available.size(); i++) {
213 [ + + + ]: 35791 : switch (tx_source[i]) {
214 : 11990 : case TxSource::MEMPOOL:
215 : 11990 : ++mempool_count;
216 [ + - ]: 11990 : Assume(txn_available[i]);
217 [ + - ]: 11990 : mempool_size += txn_available[i]->ComputeTotalSize();
218 : 11990 : break;
219 : 293 : case TxSource::EXTRA:
220 : 293 : ++extra_count;
221 [ + - ]: 293 : Assume(txn_available[i]);
222 [ + - ]: 293 : extra_size += txn_available[i]->ComputeTotalSize();
223 : 293 : break;
224 : : default:
225 : : break;
226 : : }
227 : : }
228 : : }
229 : :
230 [ + - + - : 21834 : LogDebug(BCLog::CMPCTBLOCK, "Initialized PartiallyDownloadedBlock for block %s using a cmpctblock of %u bytes\n", cmpctblock.header.GetHash().ToString(), GetSerializeSize(cmpctblock));
+ - + - +
- + - ]
231 : :
232 : 21834 : return READ_STATUS_OK;
233 : 65504 : }
234 : :
235 : 35782 : bool PartiallyDownloadedBlock::IsTxAvailable(size_t index) const
236 : : {
237 [ + - ]: 35782 : if (header.IsNull()) return false;
238 : :
239 [ - + - + ]: 35782 : assert(index < txn_available.size());
240 : 35782 : return txn_available[index] != nullptr;
241 : : }
242 : :
243 : 21807 : ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector<CTransactionRef>& vtx_missing, bool segwit_active)
244 : : {
245 [ + - ]: 21807 : if (header.IsNull()) return READ_STATUS_INVALID;
246 : :
247 : 21807 : block = header;
248 [ - + ]: 21807 : block.vtx.resize(txn_available.size());
249 : :
250 : 21807 : size_t tx_missing_offset = 0;
251 [ - + + + ]: 57428 : for (size_t i = 0; i < txn_available.size(); i++) {
252 [ + + ]: 35623 : if (!txn_available[i]) {
253 [ - + + + ]: 1534 : if (tx_missing_offset >= vtx_missing.size()) {
254 : : return READ_STATUS_INVALID;
255 : : }
256 : 1532 : block.vtx[i] = vtx_missing[tx_missing_offset++];
257 : : } else {
258 : 34089 : block.vtx[i] = std::move(txn_available[i]);
259 : : }
260 : : }
261 : :
262 : : // Make sure we can't call FillBlock again.
263 : 21805 : header.SetNull();
264 : 21805 : txn_available.clear();
265 : :
266 [ - + + - ]: 21805 : if (vtx_missing.size() != tx_missing_offset) {
267 : : return READ_STATUS_INVALID;
268 : : }
269 : :
270 : : // Check for possible mutations early now that we have a seemingly good block
271 [ - + ]: 21805 : IsBlockMutatedFn check_mutated{m_check_block_mutated_mock ? m_check_block_mutated_mock : IsBlockMutated};
272 [ + - + + ]: 21805 : if (check_mutated(/*block=*/block, /*check_witness_root=*/segwit_active)) {
273 : : return READ_STATUS_FAILED; // Possible Short ID collision
274 : : }
275 : :
276 [ + - + - ]: 21800 : if (util::log::ShouldDebugLog(BCLog::CMPCTBLOCK)) {
277 [ + - ]: 21800 : const uint256 hash{block.GetHash()};
278 : 21800 : uint32_t tx_missing_size{0};
279 [ + - + + ]: 23323 : for (const auto& tx : vtx_missing) { tx_missing_size += tx->ComputeTotalSize(); }
280 [ + - + - : 21800 : LogDebug(BCLog::CMPCTBLOCK,
- + + - +
- ]
281 : : "Successfully reconstructed block %s with %u txn prefilled (%u bytes), "
282 : : "%u txn from mempool (%u bytes), "
283 : : "%u txn from extrapool (%u bytes), "
284 : : "and %u txn requested (%u bytes)",
285 : : hash.ToString(),
286 : : prefilled_count, prefilled_size,
287 : : mempool_count, mempool_size,
288 : : extra_count, extra_size,
289 : : vtx_missing.size(), tx_missing_size);
290 [ + - + - : 21800 : LogDebug(BCLog::CMPCTBLOCK,
+ - + - ]
291 : : "Block %s prefill redundancy statistics: "
292 : : "%u txn (%u bytes) of the prefill were redundant, "
293 : : "%u txn (%u bytes) were present in the mempool, "
294 : : "%u txn (%u bytes) were present in the extrapool.",
295 : : hash.ToString(),
296 : : redundant_prefilled_mempool_count + redundant_prefilled_extrapool_count,
297 : : redundant_prefilled_mempool_size + redundant_prefilled_extrapool_size,
298 : : redundant_prefilled_mempool_count, redundant_prefilled_mempool_size,
299 : : redundant_prefilled_extrapool_count, redundant_prefilled_extrapool_size);
300 : :
301 [ + - + - ]: 21800 : if (util::log::ShouldTraceLog(BCLog::CMPCTBLOCK)) {
302 [ + - + - : 23323 : const std::string missing_txids{util::Join(vtx_missing, ", ", [](const auto& tx) { return tx->GetHash().ToString(); })};
- + ]
303 [ + - + - : 21800 : LogTrace(BCLog::CMPCTBLOCK, "Reconstructed block %s required requesting the following transactions: %s\n", hash.ToString(), missing_txids);
+ - + - ]
304 : 21800 : }
305 : : }
306 : :
307 : : return READ_STATUS_OK;
308 : 21805 : }
|
