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