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 <random.h>
13 #include <streams.h>
14 #include <txmempool.h>
15 #include <util/log.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 (util::log::ShouldDebugLog(BCLog::CMPCTBLOCK)) {
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 }
236