Bitcoin Core  0.19.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  const std::vector<std::pair<uint256, CTxMemPool::txiter> >& vTxHashes = pool->vTxHashes;
109  for (size_t i = 0; i < vTxHashes.size(); i++) {
110  uint64_t shortid = cmpctblock.GetShortID(vTxHashes[i].first);
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] = vTxHashes[i].second->GetSharedTx();
115  have_txn[idit->second] = true;
116  mempool_count++;
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();
123  mempool_count--;
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  uint64_t shortid = cmpctblock.GetShortID(extra_txn[i].first);
137  std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
138  if (idit != shorttxids.end()) {
139  if (!have_txn[idit->second]) {
140  txn_available[idit->second] = extra_txn[i].second;
141  have_txn[idit->second] = true;
142  mempool_count++;
143  extra_count++;
144  } else {
145  // If we find two mempool/extra txn that match the short id, just
146  // request it.
147  // This should be rare enough that the extra bandwidth doesn't matter,
148  // but eating a round-trip due to FillBlock failure would be annoying
149  // Note that we don't want duplication between extra_txn and mempool to
150  // trigger this case, so we compare witness hashes first
151  if (txn_available[idit->second] &&
152  txn_available[idit->second]->GetWitnessHash() != extra_txn[i].second->GetWitnessHash()) {
153  txn_available[idit->second].reset();
154  mempool_count--;
155  extra_count--;
156  }
157  }
158  }
159  // Though ideally we'd continue scanning for the two-txn-match-shortid case,
160  // the performance win of an early exit here is too good to pass up and worth
161  // the extra risk.
162  if (mempool_count == shorttxids.size())
163  break;
164  }
165 
166  LogPrint(BCLog::CMPCTBLOCK, "Initialized PartiallyDownloadedBlock for block %s using a cmpctblock of size %lu\n", cmpctblock.header.GetHash().ToString(), GetSerializeSize(cmpctblock, PROTOCOL_VERSION));
167 
168  return READ_STATUS_OK;
169 }
170 
171 bool PartiallyDownloadedBlock::IsTxAvailable(size_t index) const {
172  assert(!header.IsNull());
173  assert(index < txn_available.size());
174  return txn_available[index] != nullptr;
175 }
176 
177 ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector<CTransactionRef>& vtx_missing) {
178  assert(!header.IsNull());
179  uint256 hash = header.GetHash();
180  block = header;
181  block.vtx.resize(txn_available.size());
182 
183  size_t tx_missing_offset = 0;
184  for (size_t i = 0; i < txn_available.size(); i++) {
185  if (!txn_available[i]) {
186  if (vtx_missing.size() <= tx_missing_offset)
187  return READ_STATUS_INVALID;
188  block.vtx[i] = vtx_missing[tx_missing_offset++];
189  } else
190  block.vtx[i] = std::move(txn_available[i]);
191  }
192 
193  // Make sure we can't call FillBlock again.
194  header.SetNull();
195  txn_available.clear();
196 
197  if (vtx_missing.size() != tx_missing_offset)
198  return READ_STATUS_INVALID;
199 
200  BlockValidationState state;
201  if (!CheckBlock(block, state, Params().GetConsensus())) {
202  // TODO: We really want to just check merkle tree manually here,
203  // but that is expensive, and CheckBlock caches a block's
204  // "checked-status" (in the CBlock?). CBlock should be able to
205  // check its own merkle root and cache that check.
207  return READ_STATUS_FAILED; // Possible Short ID collision
209  }
210 
211  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());
212  if (vtx_missing.size() < 5) {
213  for (const auto& tx : vtx_missing) {
214  LogPrint(BCLog::CMPCTBLOCK, "Reconstructed block %s required tx %s\n", hash.ToString(), tx->GetHash().ToString());
215  }
216  }
217 
218  return READ_STATUS_OK;
219 }
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
Definition: random.cpp:588
ReadStatus FillBlock(CBlock &block, const std::vector< CTransactionRef > &vtx_missing)
#define LogPrint(category,...)
Definition: logging.h:179
uint64_t GetShortID(const uint256 &txhash) const
Definition: block.h:72
static const int SHORTTXIDS_LENGTH
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:1106
static const unsigned int MAX_BLOCK_WEIGHT
The maximum allowed weight for a block, see BIP 141 (network rule)
Definition: consensus.h:15
BlockValidationResult GetResult() const
Definition: validation.h:141
const uint256 & GetWitnessHash() const
Definition: transaction.h:323
#define LOCK(cs)
Definition: sync.h:179
const uint256 & GetHash() const
Definition: transaction.h:322
void Finalize(unsigned char hash[OUTPUT_SIZE])
Definition: sha256.cpp:663
void SetNull()
Definition: block.h:48
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:76
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:58
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:270
A hasher class for SHA-256.
Definition: sha256.h:13
uint64_t GetUint64(int pos) const
Definition: uint256.h:79