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 [ + - ]: 173 :
18 [ + - ]: 173 : #include <unordered_map>
19 : :
20 : 519 : CBlockHeaderAndShortTxIDs::CBlockHeaderAndShortTxIDs(const CBlock& block) :
21 : 519 : nonce(GetRand<uint64_t>()),
22 [ + - - + ]: 519 : shorttxids(block.vtx.size() - 1), prefilledtxn(1), header(block) {
23 [ + - ]: 519 : FillShortTxIDSelector();
24 : : //TODO: Use our mempool prior to block acceptance to predictively fill more than just the coinbase
25 : 519 : prefilledtxn[0] = {0, block.vtx[0]};
26 [ + + ]: 305082 : for (size_t i = 1; i < block.vtx.size(); i++) {
27 : 304563 : const CTransaction& tx = *block.vtx[i];
28 [ + - + - ]: 304563 : shorttxids[i - 1] = GetShortID(tx.GetWitnessHash());
29 : 304563 : }
30 : 519 : }
31 : :
32 : 17325 : void CBlockHeaderAndShortTxIDs::FillShortTxIDSelector() const {
33 : 17325 : DataStream stream{};
34 [ + - + - ]: 17325 : stream << header << nonce;
35 [ + - ]: 17325 : CSHA256 hasher;
36 [ + - + - : 17325 : hasher.Write((unsigned char*)&(*stream.begin()), stream.end() - stream.begin());
+ - + - ]
37 [ + - ]: 17325 : uint256 shorttxidhash;
38 [ + - + - ]: 17325 : hasher.Finalize(shorttxidhash.begin());
39 [ + - ]: 17325 : shorttxidk0 = shorttxidhash.GetUint64(0);
40 [ + - ]: 17325 : shorttxidk1 = shorttxidhash.GetUint64(1);
41 : 17325 : }
42 : :
43 : 307230 : uint64_t CBlockHeaderAndShortTxIDs::GetShortID(const uint256& txhash) const {
44 : : static_assert(SHORTTXIDS_LENGTH == 6, "shorttxids calculation assumes 6-byte shorttxids");
45 : 307230 : return SipHashUint256(shorttxidk0, shorttxidk1, txhash) & 0xffffffffffffL;
46 : : }
47 : :
48 : :
49 : :
50 : 457 : ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& cmpctblock, const std::vector<std::pair<uint256, CTransactionRef>>& extra_txn) {
51 [ + + + + : 457 : if (cmpctblock.header.IsNull() || (cmpctblock.shorttxids.empty() && cmpctblock.prefilledtxn.empty()))
+ + ]
52 : 15 : return READ_STATUS_INVALID;
53 [ - + ]: 442 : if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > MAX_BLOCK_WEIGHT / MIN_SERIALIZABLE_TRANSACTION_WEIGHT)
54 : 0 : return READ_STATUS_INVALID;
55 : :
56 [ + - - + ]: 442 : if (!header.IsNull() || !txn_available.empty()) return READ_STATUS_INVALID;
57 : :
58 : 442 : header = cmpctblock.header;
59 : 442 : txn_available.resize(cmpctblock.BlockTxCount());
60 : :
61 : 442 : int32_t lastprefilledindex = -1;
62 [ + + ]: 774 : for (size_t i = 0; i < cmpctblock.prefilledtxn.size(); i++) {
63 [ + + ]: 429 : if (cmpctblock.prefilledtxn[i].tx->IsNull())
64 : 96 : return READ_STATUS_INVALID;
65 : :
66 : 333 : lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1; //index is a uint16_t, so can't overflow here
67 [ + - ]: 333 : if (lastprefilledindex > std::numeric_limits<uint16_t>::max())
68 : 0 : return READ_STATUS_INVALID;
69 [ + + ]: 333 : if ((uint32_t)lastprefilledindex > cmpctblock.shorttxids.size() + i) {
70 : : // If we are inserting a tx at an index greater than our full list of shorttxids
71 : : // plus the number of prefilled txn we've inserted, then we have txn for which we
72 : : // have neither a prefilled txn or a shorttxid!
73 : 1 : return READ_STATUS_INVALID;
74 : 173 : }
75 : 332 : txn_available[lastprefilledindex] = cmpctblock.prefilledtxn[i].tx;
76 : 332 : }
77 : 345 : prefilled_count = cmpctblock.prefilledtxn.size();
78 : :
79 : : // Calculate map of txids -> positions and check mempool to see what we have (or don't)
80 : : // Because well-formed cmpctblock messages will have a (relatively) uniform distribution
81 : : // of short IDs, any highly-uneven distribution of elements can be safely treated as a
82 : : // READ_STATUS_FAILED.
83 [ + - ]: 345 : std::unordered_map<uint64_t, uint16_t> shorttxids(cmpctblock.shorttxids.size());
84 : 345 : uint16_t index_offset = 0;
85 [ + + ]: 84581 : for (size_t i = 0; i < cmpctblock.shorttxids.size(); i++) {
86 [ + - + + ]: 84566 : while (txn_available[i + index_offset])
87 : 330 : index_offset++;
88 [ + - ]: 84236 : shorttxids[cmpctblock.shorttxids[i]] = i + index_offset;
89 : : // To determine the chance that the number of entries in a bucket exceeds N,
90 : : // we use the fact that the number of elements in a single bucket is
91 : : // binomially distributed (with n = the number of shorttxids S, and p =
92 : : // 1 / the number of buckets), that in the worst case the number of buckets is
93 : : // equal to S (due to std::unordered_map having a default load factor of 1.0),
94 : : // and that the chance for any bucket to exceed N elements is at most
95 : : // buckets * (the chance that any given bucket is above N elements).
96 : : // Thus: P(max_elements_per_bucket > N) <= S * (1 - cdf(binomial(n=S,p=1/S), N)).
97 : : // If we assume blocks of up to 16000, allowing 12 elements per bucket should
98 : : // only fail once per ~1 million block transfers (per peer and connection).
99 [ + - + - : 84236 : if (shorttxids.bucket_size(shorttxids.bucket(cmpctblock.shorttxids[i])) > 12)
+ - ]
100 : 0 : return READ_STATUS_FAILED;
101 : 84236 : }
102 : : // TODO: in the shortid-collision case, we should instead request both transactions
103 : : // which collided. Falling back to full-block-request here is overkill.
104 [ + + ]: 345 : if (shorttxids.size() != cmpctblock.shorttxids.size())
105 : 272 : return READ_STATUS_FAILED; // Short ID collision
106 : :
107 [ + - ]: 73 : std::vector<bool> have_txn(txn_available.size());
108 : : {
109 [ + - + - ]: 73 : LOCK(pool->cs);
110 [ + + ]: 1130 : for (size_t i = 0; i < pool->vTxHashes.size(); i++) {
111 [ + - ]: 1080 : uint64_t shortid = cmpctblock.GetShortID(pool->vTxHashes[i].first);
112 [ + - ]: 1080 : std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
113 [ + - ]: 1080 : if (idit != shorttxids.end()) {
114 [ + - + + ]: 1080 : if (!have_txn[idit->second]) {
115 [ + - + - ]: 1073 : txn_available[idit->second] = pool->vTxHashes[i].second->GetSharedTx();
116 [ + - ]: 1073 : have_txn[idit->second] = true;
117 : 1073 : mempool_count++;
118 : 1073 : } else {
119 : : // If we find two mempool txn that match the short id, just request it.
120 : : // This should be rare enough that the extra bandwidth doesn't matter,
121 : : // but eating a round-trip due to FillBlock failure would be annoying
122 [ + - + + ]: 7 : if (txn_available[idit->second]) {
123 : 6 : txn_available[idit->second].reset();
124 : 6 : mempool_count--;
125 : 6 : }
126 : : }
127 : 1080 : }
128 : : // Though ideally we'd continue scanning for the two-txn-match-shortid case,
129 : : // the performance win of an early exit here is too good to pass up and worth
130 : : // the extra risk.
131 [ + + ]: 1080 : if (mempool_count == shorttxids.size())
132 : 23 : break;
133 : 1057 : }
134 : 73 : }
135 : :
136 [ + + ]: 1636 : for (size_t i = 0; i < extra_txn.size(); i++) {
137 [ + - ]: 1587 : uint64_t shortid = cmpctblock.GetShortID(extra_txn[i].first);
138 [ + - ]: 1587 : std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
139 [ + + ]: 1587 : if (idit != shorttxids.end()) {
140 [ + - + + ]: 986 : if (!have_txn[idit->second]) {
141 : 100 : txn_available[idit->second] = extra_txn[i].second;
142 [ + - ]: 100 : have_txn[idit->second] = true;
143 : 100 : mempool_count++;
144 : 100 : extra_count++;
145 : 100 : } else {
146 : : // If we find two mempool/extra txn that match the short id, just
147 : : // request it.
148 : : // This should be rare enough that the extra bandwidth doesn't matter,
149 : : // but eating a round-trip due to FillBlock failure would be annoying
150 : : // Note that we don't want duplication between extra_txn and mempool to
151 : : // trigger this case, so we compare witness hashes first
152 [ + - + + : 1766 : if (txn_available[idit->second] &&
+ - ]
153 [ + - + - : 880 : txn_available[idit->second]->GetWitnessHash() != extra_txn[i].second->GetWitnessHash()) {
+ - ]
154 : 0 : txn_available[idit->second].reset();
155 : 0 : mempool_count--;
156 : 0 : extra_count--;
157 : 0 : }
158 : : }
159 : 986 : }
160 : : // Though ideally we'd continue scanning for the two-txn-match-shortid case,
161 : : // the performance win of an early exit here is too good to pass up and worth
162 : : // the extra risk.
163 [ + + ]: 1587 : if (mempool_count == shorttxids.size())
164 : 24 : break;
165 : 1563 : }
166 : :
167 [ + - + - : 73 : LogPrint(BCLog::CMPCTBLOCK, "Initialized PartiallyDownloadedBlock for block %s using a cmpctblock of size %lu\n", cmpctblock.header.GetHash().ToString(), GetSerializeSize(cmpctblock, PROTOCOL_VERSION));
# # # # #
# # # # #
# # ]
168 : :
169 : 73 : return READ_STATUS_OK;
170 : 457 : }
171 : :
172 : 611804 : bool PartiallyDownloadedBlock::IsTxAvailable(size_t index) const
173 : : {
174 [ + + ]: 611804 : if (header.IsNull()) return false;
175 : :
176 [ + - ]: 609682 : assert(index < txn_available.size());
177 : 609682 : return txn_available[index] != nullptr;
178 : 611804 : }
179 : :
180 : 435 : ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector<CTransactionRef>& vtx_missing)
181 : : {
182 [ + + ]: 435 : if (header.IsNull()) return READ_STATUS_INVALID;
183 : :
184 : 421 : uint256 hash = header.GetHash();
185 : 421 : block = header;
186 : 421 : block.vtx.resize(txn_available.size());
187 : :
188 : 421 : size_t tx_missing_offset = 0;
189 [ + + ]: 285489 : for (size_t i = 0; i < txn_available.size(); i++) {
190 [ + + ]: 285273 : if (!txn_available[i]) {
191 [ + + ]: 284486 : if (vtx_missing.size() <= tx_missing_offset)
192 : 205 : return READ_STATUS_INVALID;
193 : 284281 : block.vtx[i] = vtx_missing[tx_missing_offset++];
194 : 284281 : } else
195 : 787 : block.vtx[i] = std::move(txn_available[i]);
196 : 285068 : }
197 : :
198 : : // Make sure we can't call FillBlock again.
199 : 216 : header.SetNull();
200 : 216 : txn_available.clear();
201 : :
202 [ - + ]: 216 : if (vtx_missing.size() != tx_missing_offset)
203 : 0 : return READ_STATUS_INVALID;
204 : :
205 : 216 : BlockValidationState state;
206 [ + + + - : 216 : CheckBlockFn check_block = m_check_block_mock ? m_check_block_mock : CheckBlock;
+ - ]
207 [ + - + - : 216 : if (!check_block(block, state, Params().GetConsensus(), /*fCheckPoW=*/true, /*fCheckMerkleRoot=*/true)) {
+ - + + ]
208 : : // TODO: We really want to just check merkle tree manually here,
209 : : // but that is expensive, and CheckBlock caches a block's
210 : : // "checked-status" (in the CBlock?). CBlock should be able to
211 : : // check its own merkle root and cache that check.
212 [ + - + + ]: 9 : if (state.GetResult() == BlockValidationResult::BLOCK_MUTATED)
213 : 2 : return READ_STATUS_FAILED; // Possible Short ID collision
214 : 7 : return READ_STATUS_CHECKBLOCK_FAILED;
215 : : }
216 : :
217 [ + - + - : 207 : LogPrint(BCLog::CMPCTBLOCK, "Successfully reconstructed block %s with %lu txn prefilled, %lu txn from mempool (incl at least %lu from extra pool) and %lu txn requested\n", hash.ToString(), prefilled_count, mempool_count, extra_count, vtx_missing.size());
# # # # #
# # # ]
218 [ + + ]: 207 : if (vtx_missing.size() < 5) {
219 [ + + ]: 111 : for (const auto& tx : vtx_missing) {
220 [ + - + - : 65 : LogPrint(BCLog::CMPCTBLOCK, "Reconstructed block %s required tx %s\n", hash.ToString(), tx->GetHash().ToString());
# # # # #
# # # # #
# # ]
221 : : }
222 : 46 : }
223 : :
224 : 207 : return READ_STATUS_OK;
225 : 435 : }
|
