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