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 <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 : 105205 : CBlockHeaderAndShortTxIDs::CBlockHeaderAndShortTxIDs(const CBlock& block, uint64_t nonce)
21 : 105205 : : nonce(nonce),
22 [ - + ]: 105205 : shorttxids(block.vtx.size() - 1),
23 [ + - ]: 105205 : prefilledtxn(1),
24 [ - + ]: 105205 : header(block)
25 : : {
26 [ + - ]: 105205 : FillShortTxIDSelector();
27 : : // TODO: Use our mempool prior to block acceptance to predictively fill more than just the coinbase
28 [ - + ]: 105205 : prefilledtxn[0] = {0, block.vtx[0]};
29 [ - + + + ]: 153537 : for (size_t i = 1; i < block.vtx.size(); i++) {
30 [ + - ]: 48332 : const CTransaction& tx = *block.vtx[i];
31 [ + - ]: 48332 : shorttxids[i - 1] = GetShortID(tx.GetWitnessHash());
32 : : }
33 [ + - ]: 315615 : }
34 : :
35 : 132578 : void CBlockHeaderAndShortTxIDs::FillShortTxIDSelector() const
36 : : {
37 : 132578 : DataStream stream{};
38 [ + - + - ]: 132578 : stream << header << nonce;
39 [ + - ]: 132578 : CSHA256 hasher;
40 [ + - ]: 132578 : hasher.Write((unsigned char*)&(*stream.begin()), stream.end() - stream.begin());
41 : 132578 : uint256 shorttxidhash;
42 [ + - ]: 132578 : hasher.Finalize(shorttxidhash.begin());
43 : 132578 : m_hasher.emplace(shorttxidhash.GetUint64(0), shorttxidhash.GetUint64(1));
44 : 132578 : }
45 : :
46 : 133060 : uint64_t CBlockHeaderAndShortTxIDs::GetShortID(const Wtxid& wtxid) const
47 : : {
48 : 133060 : static_assert(SHORTTXIDS_LENGTH == 6, "shorttxids calculation assumes 6-byte shorttxids");
49 [ - + ]: 133060 : 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 : 21919 : ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& cmpctblock, const std::vector<std::pair<Wtxid, CTransactionRef>>& extra_txn)
60 : : {
61 [ + - + - ]: 21919 : LogDebug(BCLog::CMPCTBLOCK, "Initializing PartiallyDownloadedBlock for block %s using a cmpctblock of %u bytes\n", cmpctblock.header.GetHash().ToString(), GetSerializeSize(cmpctblock));
62 [ + - + + : 21919 : if (cmpctblock.header.IsNull() || (cmpctblock.shorttxids.empty() && cmpctblock.prefilledtxn.empty()))
+ - ]
63 : : return READ_STATUS_INVALID;
64 [ - + - + : 21919 : if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > MAX_BLOCK_WEIGHT / MIN_SERIALIZABLE_TRANSACTION_WEIGHT)
+ - ]
65 : : return READ_STATUS_INVALID;
66 : :
67 [ + - + - ]: 21919 : if (!header.IsNull() || !txn_available.empty()) return READ_STATUS_INVALID;
68 : :
69 : 21919 : header = cmpctblock.header;
70 [ - + ]: 21919 : txn_available.resize(cmpctblock.BlockTxCount());
71 : :
72 : 21919 : int32_t lastprefilledindex = -1;
73 [ - + + + ]: 43845 : for (size_t i = 0; i < cmpctblock.prefilledtxn.size(); i++) {
74 [ + - ]: 21928 : if (cmpctblock.prefilledtxn[i].tx->IsNull())
75 : : return READ_STATUS_INVALID;
76 : :
77 : 21928 : lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1; //index is a uint16_t, so can't overflow here
78 [ + - ]: 21928 : if (lastprefilledindex > std::numeric_limits<uint16_t>::max())
79 : : return READ_STATUS_INVALID;
80 [ - + + + ]: 21928 : 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 : 21926 : txn_available[lastprefilledindex] = cmpctblock.prefilledtxn[i].tx;
87 : : }
88 : 21917 : 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 [ - + ]: 21917 : std::unordered_map<uint64_t, uint16_t> shorttxids(cmpctblock.shorttxids.size());
95 : : uint16_t index_offset = 0;
96 [ - + + + ]: 34791 : for (size_t i = 0; i < cmpctblock.shorttxids.size(); i++) {
97 [ + + ]: 13815 : while (txn_available[i + index_offset])
98 : 941 : index_offset++;
99 [ + - ]: 12874 : 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 [ + - ]: 12874 : if (shorttxids.bucket_size(shorttxids.bucket(cmpctblock.shorttxids[i])) > 12)
111 : : return READ_STATUS_FAILED;
112 : : }
113 [ + - ]: 21917 : if (shorttxids.size() != cmpctblock.shorttxids.size())
114 : : return READ_STATUS_FAILED; // Short ID collision
115 : :
116 : 21917 : enum class TxSource : uint8_t { NONE, MEMPOOL, EXTRA, COLLIDED };
117 [ - + + - ]: 21917 : std::vector<TxSource> tx_source(txn_available.size(), TxSource::NONE);
118 : 21917 : {
119 [ + - ]: 21917 : LOCK(pool->cs);
120 [ + - + + ]: 103803 : for (const auto& [wtxid, txit] : pool->txns_randomized) {
121 [ + - ]: 82259 : uint64_t shortid = cmpctblock.GetShortID(wtxid);
122 : 82259 : std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
123 [ + + ]: 82259 : if (idit != shorttxids.end()) {
124 [ + - ]: 10885 : if (tx_source[idit->second] == TxSource::NONE) {
125 [ + - - + ]: 21770 : txn_available[idit->second] = txit->GetSharedTx();
126 : 10885 : tx_source[idit->second] = TxSource::MEMPOOL;
127 : 10885 : mempool_count++;
128 [ # # ]: 0 : } else if (tx_source[idit->second] != TxSource::COLLIDED) {
129 : : // If we find two mempool txn that match the short id, just request it.
130 : : // This should be rare enough that the extra bandwidth doesn't matter,
131 : : // but eating a round-trip due to FillBlock failure would be annoying
132 : 0 : txn_available[idit->second].reset();
133 : 0 : mempool_count--;
134 : 0 : tx_source[idit->second] = TxSource::COLLIDED;
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 [ + + ]: 82259 : if (mempool_count == shorttxids.size())
141 : : break;
142 : : }
143 : 0 : }
144 : :
145 [ - + + + ]: 23761 : for (size_t i = 0; i < extra_txn.size(); i++) {
146 [ + - ]: 2466 : uint64_t shortid = cmpctblock.GetShortID(extra_txn[i].first);
147 : 2466 : std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
148 [ + + ]: 2466 : if (idit != shorttxids.end()) {
149 [ + + ]: 310 : if (tx_source[idit->second] == TxSource::NONE) {
150 : 294 : txn_available[idit->second] = extra_txn[i].second;
151 : 294 : tx_source[idit->second] = TxSource::EXTRA;
152 : 294 : mempool_count++;
153 : 294 : extra_count++;
154 [ + + + + ]: 16 : } else if (tx_source[idit->second] != TxSource::COLLIDED &&
155 [ + + ]: 14 : txn_available[idit->second]->GetWitnessHash() != extra_txn[i].second->GetWitnessHash()) {
156 : : // If we find two mempool/extra txn that match the short id, just
157 : : // request it.
158 : : // This should be rare enough that the extra bandwidth doesn't matter,
159 : : // but eating a round-trip due to FillBlock failure would be annoying
160 : : // Note that we don't want duplication between extra_txn and mempool to
161 : : // trigger this case, so we compare witness hashes first
162 : 5 : txn_available[idit->second].reset();
163 : 5 : mempool_count--;
164 : 5 : extra_count -= (tx_source[idit->second] == TxSource::EXTRA);
165 : 5 : tx_source[idit->second] = TxSource::COLLIDED;
166 : : }
167 : : }
168 : : // Though ideally we'd continue scanning for the two-txn-match-shortid case,
169 : : // the performance win of an early exit here is too good to pass up and worth
170 : : // the extra risk.
171 [ + + ]: 2466 : if (mempool_count == shorttxids.size())
172 : : break;
173 : : }
174 : :
175 [ + - + - : 21917 : LogDebug(BCLog::CMPCTBLOCK, "Initialized PartiallyDownloadedBlock for block %s using a cmpctblock of %u bytes\n", cmpctblock.header.GetHash().ToString(), GetSerializeSize(cmpctblock));
+ - + - +
- + - ]
176 : :
177 : 21917 : return READ_STATUS_OK;
178 : 43834 : }
179 : :
180 : 34791 : bool PartiallyDownloadedBlock::IsTxAvailable(size_t index) const
181 : : {
182 [ + - ]: 34791 : if (header.IsNull()) return false;
183 : :
184 [ - + - + ]: 34791 : assert(index < txn_available.size());
185 : 34791 : return txn_available[index] != nullptr;
186 : : }
187 : :
188 : 21880 : ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector<CTransactionRef>& vtx_missing, bool segwit_active)
189 : : {
190 [ + - ]: 21880 : if (header.IsNull()) return READ_STATUS_INVALID;
191 : :
192 : 21880 : block = header;
193 [ - + ]: 21880 : block.vtx.resize(txn_available.size());
194 : :
195 : 21880 : size_t tx_missing_offset = 0;
196 [ - + + + ]: 56466 : for (size_t i = 0; i < txn_available.size(); i++) {
197 [ + + ]: 34588 : if (!txn_available[i]) {
198 [ - + + + ]: 1550 : if (tx_missing_offset >= vtx_missing.size()) {
199 : : return READ_STATUS_INVALID;
200 : : }
201 : 1548 : block.vtx[i] = vtx_missing[tx_missing_offset++];
202 : : } else {
203 : 33038 : block.vtx[i] = std::move(txn_available[i]);
204 : : }
205 : : }
206 : :
207 : : // Make sure we can't call FillBlock again.
208 : 21878 : header.SetNull();
209 : 21878 : txn_available.clear();
210 : :
211 [ - + + - ]: 21878 : if (vtx_missing.size() != tx_missing_offset) {
212 : : return READ_STATUS_INVALID;
213 : : }
214 : :
215 : : // Check for possible mutations early now that we have a seemingly good block
216 [ - + ]: 21878 : IsBlockMutatedFn check_mutated{m_check_block_mutated_mock ? m_check_block_mutated_mock : IsBlockMutated};
217 [ + - + + ]: 21878 : if (check_mutated(/*block=*/block, /*check_witness_root=*/segwit_active)) {
218 : : return READ_STATUS_FAILED; // Possible Short ID collision
219 : : }
220 : :
221 [ + - + - ]: 21873 : if (util::log::ShouldDebugLog(BCLog::CMPCTBLOCK)) {
222 [ + - ]: 21873 : const uint256 hash{block.GetHash()};
223 : 21873 : uint32_t tx_missing_size{0};
224 [ + - + + ]: 23412 : for (const auto& tx : vtx_missing) tx_missing_size += tx->ComputeTotalSize();
225 [ + - + - : 21873 : 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);
- + + - +
- ]
226 [ - + + + ]: 21873 : if (vtx_missing.size() < 5) {
227 [ + + ]: 22543 : for (const auto& tx : vtx_missing) {
228 [ + - + - : 688 : LogDebug(BCLog::CMPCTBLOCK, "Reconstructed block %s required tx %s\n", hash.ToString(), tx->GetHash().ToString());
+ - + - +
- ]
229 : : }
230 : : }
231 : : }
232 : :
233 : : return READ_STATUS_OK;
234 : 21878 : }
|
