Bitcoin Core 29.99.0
P2P Digital Currency
blockencodings.cpp
Go to the documentation of this file.
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>
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
21 nonce(nonce),
22 shorttxids(block.vtx.size() - 1), prefilledtxn(1), header(block) {
24 //TODO: Use our mempool prior to block acceptance to predictively fill more than just the coinbase
25 prefilledtxn[0] = {0, block.vtx[0]};
26 for (size_t i = 1; i < block.vtx.size(); i++) {
27 const CTransaction& tx = *block.vtx[i];
29 }
30}
31
33 DataStream stream{};
34 stream << header << nonce;
35 CSHA256 hasher;
36 hasher.Write((unsigned char*)&(*stream.begin()), stream.end() - stream.begin());
37 uint256 shorttxidhash;
38 hasher.Finalize(shorttxidhash.begin());
39 shorttxidk0 = shorttxidhash.GetUint64(0);
40 shorttxidk1 = shorttxidhash.GetUint64(1);
41}
42
43uint64_t CBlockHeaderAndShortTxIDs::GetShortID(const Wtxid& wtxid) const {
44 static_assert(SHORTTXIDS_LENGTH == 6, "shorttxids calculation assumes 6-byte shorttxids");
45 return SipHashUint256(shorttxidk0, shorttxidk1, wtxid) & 0xffffffffffffL;
46}
47
48ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& cmpctblock, const std::vector<CTransactionRef>& extra_txn) {
49 LogDebug(BCLog::CMPCTBLOCK, "Initializing PartiallyDownloadedBlock for block %s using a cmpctblock of %u bytes\n", cmpctblock.header.GetHash().ToString(), GetSerializeSize(cmpctblock));
50 if (cmpctblock.header.IsNull() || (cmpctblock.shorttxids.empty() && cmpctblock.prefilledtxn.empty()))
52 if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > MAX_BLOCK_WEIGHT / MIN_SERIALIZABLE_TRANSACTION_WEIGHT)
54
55 if (!header.IsNull() || !txn_available.empty()) return READ_STATUS_INVALID;
56
57 header = cmpctblock.header;
58 txn_available.resize(cmpctblock.BlockTxCount());
59
60 int32_t lastprefilledindex = -1;
61 for (size_t i = 0; i < cmpctblock.prefilledtxn.size(); i++) {
62 if (cmpctblock.prefilledtxn[i].tx->IsNull())
64
65 lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1; //index is a uint16_t, so can't overflow here
66 if (lastprefilledindex > std::numeric_limits<uint16_t>::max())
68 if ((uint32_t)lastprefilledindex > cmpctblock.shorttxids.size() + i) {
69 // If we are inserting a tx at an index greater than our full list of shorttxids
70 // plus the number of prefilled txn we've inserted, then we have txn for which we
71 // have neither a prefilled txn or a shorttxid!
73 }
74 txn_available[lastprefilledindex] = cmpctblock.prefilledtxn[i].tx;
75 }
76 prefilled_count = cmpctblock.prefilledtxn.size();
77
78 // Calculate map of txids -> positions and check mempool to see what we have (or don't)
79 // Because well-formed cmpctblock messages will have a (relatively) uniform distribution
80 // of short IDs, any highly-uneven distribution of elements can be safely treated as a
81 // READ_STATUS_FAILED.
82 std::unordered_map<uint64_t, uint16_t> shorttxids(cmpctblock.shorttxids.size());
83 uint16_t index_offset = 0;
84 for (size_t i = 0; i < cmpctblock.shorttxids.size(); i++) {
85 while (txn_available[i + index_offset])
86 index_offset++;
87 shorttxids[cmpctblock.shorttxids[i]] = i + index_offset;
88 // To determine the chance that the number of entries in a bucket exceeds N,
89 // we use the fact that the number of elements in a single bucket is
90 // binomially distributed (with n = the number of shorttxids S, and p =
91 // 1 / the number of buckets), that in the worst case the number of buckets is
92 // equal to S (due to std::unordered_map having a default load factor of 1.0),
93 // and that the chance for any bucket to exceed N elements is at most
94 // buckets * (the chance that any given bucket is above N elements).
95 // Thus: P(max_elements_per_bucket > N) <= S * (1 - cdf(binomial(n=S,p=1/S), N)).
96 // If we assume blocks of up to 16000, allowing 12 elements per bucket should
97 // only fail once per ~1 million block transfers (per peer and connection).
98 if (shorttxids.bucket_size(shorttxids.bucket(cmpctblock.shorttxids[i])) > 12)
99 return READ_STATUS_FAILED;
100 }
101 // TODO: in the shortid-collision case, we should instead request both transactions
102 // which collided. Falling back to full-block-request here is overkill.
103 if (shorttxids.size() != cmpctblock.shorttxids.size())
104 return READ_STATUS_FAILED; // Short ID collision
105
106 std::vector<bool> have_txn(txn_available.size());
107 {
108 LOCK(pool->cs);
109 for (const auto& tx : pool->txns_randomized) {
110 uint64_t shortid = cmpctblock.GetShortID(tx->GetWitnessHash());
111 std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
112 if (idit != shorttxids.end()) {
113 if (!have_txn[idit->second]) {
114 txn_available[idit->second] = tx;
115 have_txn[idit->second] = true;
117 } else {
118 // If we find two mempool txn that match the short id, just request it.
119 // This should be rare enough that the extra bandwidth doesn't matter,
120 // but eating a round-trip due to FillBlock failure would be annoying
121 if (txn_available[idit->second]) {
122 txn_available[idit->second].reset();
124 }
125 }
126 }
127 // Though ideally we'd continue scanning for the two-txn-match-shortid case,
128 // the performance win of an early exit here is too good to pass up and worth
129 // the extra risk.
130 if (mempool_count == shorttxids.size())
131 break;
132 }
133 }
134
135 for (size_t i = 0; i < extra_txn.size(); i++) {
136 if (extra_txn[i] == nullptr) {
137 continue;
138 }
139 uint64_t shortid = cmpctblock.GetShortID(extra_txn[i]->GetWitnessHash());
140 std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
141 if (idit != shorttxids.end()) {
142 if (!have_txn[idit->second]) {
143 txn_available[idit->second] = extra_txn[i];
144 have_txn[idit->second] = true;
146 extra_count++;
147 } else {
148 // If we find two mempool/extra txn that match the short id, just
149 // request it.
150 // This should be rare enough that the extra bandwidth doesn't matter,
151 // but eating a round-trip due to FillBlock failure would be annoying
152 // Note that we don't want duplication between extra_txn and mempool to
153 // trigger this case, so we compare witness hashes first
154 if (txn_available[idit->second] &&
155 txn_available[idit->second]->GetWitnessHash() != extra_txn[i]->GetWitnessHash()) {
156 txn_available[idit->second].reset();
158 extra_count--;
159 }
160 }
161 }
162 // Though ideally we'd continue scanning for the two-txn-match-shortid case,
163 // the performance win of an early exit here is too good to pass up and worth
164 // the extra risk.
165 if (mempool_count == shorttxids.size())
166 break;
167 }
168
169 LogDebug(BCLog::CMPCTBLOCK, "Initialized PartiallyDownloadedBlock for block %s using a cmpctblock of %u bytes\n", cmpctblock.header.GetHash().ToString(), GetSerializeSize(cmpctblock));
170
171 return READ_STATUS_OK;
172}
173
175{
176 if (header.IsNull()) return false;
177
178 assert(index < txn_available.size());
179 return txn_available[index] != nullptr;
180}
181
182ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector<CTransactionRef>& vtx_missing)
183{
184 if (header.IsNull()) return READ_STATUS_INVALID;
185
186 uint256 hash = header.GetHash();
187 block = header;
188 block.vtx.resize(txn_available.size());
189
190 unsigned int tx_missing_size = 0;
191 size_t tx_missing_offset = 0;
192 for (size_t i = 0; i < txn_available.size(); i++) {
193 if (!txn_available[i]) {
194 if (vtx_missing.size() <= tx_missing_offset)
195 return READ_STATUS_INVALID;
196 block.vtx[i] = vtx_missing[tx_missing_offset++];
197 tx_missing_size += block.vtx[i]->GetTotalSize();
198 } else
199 block.vtx[i] = std::move(txn_available[i]);
200 }
201
202 // Make sure we can't call FillBlock again.
203 header.SetNull();
204 txn_available.clear();
205
206 if (vtx_missing.size() != tx_missing_offset)
207 return READ_STATUS_INVALID;
208
211 if (!check_block(block, state, Params().GetConsensus(), /*fCheckPoW=*/true, /*fCheckMerkleRoot=*/true)) {
212 // TODO: We really want to just check merkle tree manually here,
213 // but that is expensive, and CheckBlock caches a block's
214 // "checked-status" (in the CBlock?). CBlock should be able to
215 // check its own merkle root and cache that check.
217 return READ_STATUS_FAILED; // Possible Short ID collision
219 }
220
221 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 if (vtx_missing.size() < 5) {
223 for (const auto& tx : vtx_missing) {
224 LogDebug(BCLog::CMPCTBLOCK, "Reconstructed block %s required tx %s\n", hash.ToString(), tx->GetHash().ToString());
225 }
226 }
227
228 return READ_STATUS_OK;
229}
@ READ_STATUS_OK
@ READ_STATUS_INVALID
@ READ_STATUS_CHECKBLOCK_FAILED
@ READ_STATUS_FAILED
enum ReadStatus_t ReadStatus
const CChainParams & Params()
Return the currently selected parameters.
CBlockHeaderAndShortTxIDs()=default
Dummy for deserialization.
void FillShortTxIDSelector() const
uint64_t GetShortID(const Wtxid &wtxid) const
std::vector< PrefilledTransaction > prefilledtxn
static constexpr int SHORTTXIDS_LENGTH
std::vector< uint64_t > shorttxids
void SetNull()
Definition: block.h:39
uint256 GetHash() const
Definition: block.cpp:11
bool IsNull() const
Definition: block.h:49
Definition: block.h:69
std::vector< CTransactionRef > vtx
Definition: block.h:72
A hasher class for SHA-256.
Definition: sha256.h:14
void Finalize(unsigned char hash[OUTPUT_SIZE])
Definition: sha256.cpp:725
CSHA256 & Write(const unsigned char *data, size_t len)
Definition: sha256.cpp:699
The basic transaction that is broadcasted on the network and contained in blocks.
Definition: transaction.h:296
const Wtxid & GetWitnessHash() const LIFETIMEBOUND
Definition: transaction.h:344
RecursiveMutex cs
This mutex needs to be locked when accessing mapTx or other members that are guarded by it.
Definition: txmempool.h:390
Double ended buffer combining vector and stream-like interfaces.
Definition: streams.h:148
const CTxMemPool * pool
CheckBlockFn m_check_block_mock
std::vector< CTransactionRef > txn_available
ReadStatus InitData(const CBlockHeaderAndShortTxIDs &cmpctblock, const std::vector< CTransactionRef > &extra_txn)
bool IsTxAvailable(size_t index) const
ReadStatus FillBlock(CBlock &block, const std::vector< CTransactionRef > &vtx_missing)
std::function< bool(const CBlock &, BlockValidationState &, const Consensus::Params &, bool, bool)> CheckBlockFn
Result GetResult() const
Definition: validation.h:108
constexpr uint64_t GetUint64(int pos) const
Definition: uint256.h:109
std::string ToString() const
Definition: uint256.cpp:21
constexpr unsigned char * begin()
Definition: uint256.h:101
transaction_identifier represents the two canonical transaction identifier types (txid,...
256-bit opaque blob.
Definition: uint256.h:196
@ BLOCK_MUTATED
the block's data didn't match the data committed to by the PoW
static const unsigned int MAX_BLOCK_WEIGHT
The maximum allowed weight for a block, see BIP 141 (network rule)
Definition: consensus.h:15
static const size_t MIN_SERIALIZABLE_TRANSACTION_WEIGHT
Definition: consensus.h:24
#define LogDebug(category,...)
Definition: logging.h:280
unsigned int nonce
Definition: miner_tests.cpp:75
@ CMPCTBLOCK
Definition: logging.h:55
size_t GetSerializeSize(const T &t)
Definition: serialize.h:1105
uint64_t SipHashUint256(uint64_t k0, uint64_t k1, const uint256 &val)
Optimized SipHash-2-4 implementation for uint256.
Definition: siphash.cpp:95
#define LOCK(cs)
Definition: sync.h:265
bool CheckBlock(const CBlock &block, BlockValidationState &state, const Consensus::Params &consensusParams, bool fCheckPOW, bool fCheckMerkleRoot)
Functions for validating blocks and updating the block tree.
assert(!tx.IsCoinBase())