Bitcoin Core 28.99.0
P2P Digital Currency
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages Concepts
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
48
49
50ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& cmpctblock, const std::vector<CTransactionRef>& extra_txn) {
51 if (cmpctblock.header.IsNull() || (cmpctblock.shorttxids.empty() && cmpctblock.prefilledtxn.empty()))
53 if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > MAX_BLOCK_WEIGHT / MIN_SERIALIZABLE_TRANSACTION_WEIGHT)
55
56 if (!header.IsNull() || !txn_available.empty()) return READ_STATUS_INVALID;
57
58 header = cmpctblock.header;
59 txn_available.resize(cmpctblock.BlockTxCount());
60
61 int32_t lastprefilledindex = -1;
62 for (size_t i = 0; i < cmpctblock.prefilledtxn.size(); i++) {
63 if (cmpctblock.prefilledtxn[i].tx->IsNull())
65
66 lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1; //index is a uint16_t, so can't overflow here
67 if (lastprefilledindex > std::numeric_limits<uint16_t>::max())
69 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!
74 }
75 txn_available[lastprefilledindex] = cmpctblock.prefilledtxn[i].tx;
76 }
77 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 std::unordered_map<uint64_t, uint16_t> shorttxids(cmpctblock.shorttxids.size());
84 uint16_t index_offset = 0;
85 for (size_t i = 0; i < cmpctblock.shorttxids.size(); i++) {
86 while (txn_available[i + index_offset])
87 index_offset++;
88 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 if (shorttxids.bucket_size(shorttxids.bucket(cmpctblock.shorttxids[i])) > 12)
100 return READ_STATUS_FAILED;
101 }
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 if (shorttxids.size() != cmpctblock.shorttxids.size())
105 return READ_STATUS_FAILED; // Short ID collision
106
107 std::vector<bool> have_txn(txn_available.size());
108 {
109 LOCK(pool->cs);
110 for (const auto& tx : pool->txns_randomized) {
111 uint64_t shortid = cmpctblock.GetShortID(tx->GetWitnessHash());
112 std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
113 if (idit != shorttxids.end()) {
114 if (!have_txn[idit->second]) {
115 txn_available[idit->second] = tx;
116 have_txn[idit->second] = true;
118 } 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 if (txn_available[idit->second]) {
123 txn_available[idit->second].reset();
125 }
126 }
127 }
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 if (mempool_count == shorttxids.size())
132 break;
133 }
134 }
135
136 for (size_t i = 0; i < extra_txn.size(); i++) {
137 if (extra_txn[i] == nullptr) {
138 continue;
139 }
140 uint64_t shortid = cmpctblock.GetShortID(extra_txn[i]->GetWitnessHash());
141 std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
142 if (idit != shorttxids.end()) {
143 if (!have_txn[idit->second]) {
144 txn_available[idit->second] = extra_txn[i];
145 have_txn[idit->second] = true;
147 extra_count++;
148 } else {
149 // If we find two mempool/extra txn that match the short id, just
150 // request it.
151 // This should be rare enough that the extra bandwidth doesn't matter,
152 // but eating a round-trip due to FillBlock failure would be annoying
153 // Note that we don't want duplication between extra_txn and mempool to
154 // trigger this case, so we compare witness hashes first
155 if (txn_available[idit->second] &&
156 txn_available[idit->second]->GetWitnessHash() != extra_txn[i]->GetWitnessHash()) {
157 txn_available[idit->second].reset();
159 extra_count--;
160 }
161 }
162 }
163 // Though ideally we'd continue scanning for the two-txn-match-shortid case,
164 // the performance win of an early exit here is too good to pass up and worth
165 // the extra risk.
166 if (mempool_count == shorttxids.size())
167 break;
168 }
169
170 LogDebug(BCLog::CMPCTBLOCK, "Initialized PartiallyDownloadedBlock for block %s using a cmpctblock of size %lu\n", cmpctblock.header.GetHash().ToString(), GetSerializeSize(cmpctblock));
171
172 return READ_STATUS_OK;
173}
174
176{
177 if (header.IsNull()) return false;
178
179 assert(index < txn_available.size());
180 return txn_available[index] != nullptr;
181}
182
183ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector<CTransactionRef>& vtx_missing)
184{
185 if (header.IsNull()) return READ_STATUS_INVALID;
186
187 uint256 hash = header.GetHash();
188 block = header;
189 block.vtx.resize(txn_available.size());
190
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 } else
198 block.vtx[i] = std::move(txn_available[i]);
199 }
200
201 // Make sure we can't call FillBlock again.
202 header.SetNull();
203 txn_available.clear();
204
205 if (vtx_missing.size() != tx_missing_offset)
206 return READ_STATUS_INVALID;
207
210 if (!check_block(block, state, Params().GetConsensus(), /*fCheckPoW=*/true, /*fCheckMerkleRoot=*/true)) {
211 // TODO: We really want to just check merkle tree manually here,
212 // but that is expensive, and CheckBlock caches a block's
213 // "checked-status" (in the CBlock?). CBlock should be able to
214 // check its own merkle root and cache that check.
216 return READ_STATUS_FAILED; // Possible Short ID collision
218 }
219
220 LogDebug(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());
221 if (vtx_missing.size() < 5) {
222 for (const auto& tx : vtx_missing) {
223 LogDebug(BCLog::CMPCTBLOCK, "Reconstructed block %s required tx %s\n", hash.ToString(), tx->GetHash().ToString());
224 }
225 }
226
227 return READ_STATUS_OK;
228}
@ 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:727
CSHA256 & Write(const unsigned char *data, size_t len)
Definition: sha256.cpp:701
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:147
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:109
constexpr uint64_t GetUint64(int pos) const
Definition: uint256.h:112
std::string ToString() const
Definition: uint256.cpp:47
constexpr unsigned char * begin()
Definition: uint256.h:104
transaction_identifier represents the two canonical transaction identifier types (txid,...
256-bit opaque blob.
Definition: uint256.h:190
@ 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:74
@ CMPCTBLOCK
Definition: logging.h:55
size_t GetSerializeSize(const T &t)
Definition: serialize.h:1101
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:257
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())