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