Bitcoin ABC  0.26.3
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() >
60  return READ_STATUS_INVALID;
61  }
62 
63  assert(header.IsNull());
64  assert(shortidProcessor == nullptr);
65  header = cmpctblock.header;
66 
67  for (const auto &prefilledtxn : cmpctblock.prefilledtxn) {
68  if (prefilledtxn.tx->IsNull()) {
69  return READ_STATUS_INVALID;
70  }
71  }
72  prefilled_count = cmpctblock.prefilledtxn.size();
73 
74  // To determine the chance that the number of entries in a bucket exceeds N,
75  // we use the fact that the number of elements in a single bucket is
76  // binomially distributed (with n = the number of shorttxids S, and
77  // p = 1 / the number of buckets), that in the worst case the number of
78  // buckets is equal to S (due to std::unordered_map having a default load
79  // factor of 1.0), and that the chance for any bucket to exceed N elements
80  // is at most buckets * (the chance that any given bucket is above N
81  // elements). Thus:
82  // P(max_elements_per_bucket > N) <= S * (1 - cdf(binomial(n=S,p=1/S), N))
83  // If we assume blocks of up to 16000, allowing 12 elements per bucket
84  // should only fail once per ~1 million block transfers (per peer and
85  // connection).
86  // FIXME the value of 16000 txs in a block should be re-evaluated.
87  shortidProcessor = std::make_shared<TransactionShortIdProcessor>(
88  cmpctblock.prefilledtxn, cmpctblock.shorttxids, 12);
89 
90  if (!shortidProcessor->isEvenlyDistributed() ||
91  shortidProcessor->hasShortIdCollision() ||
92  shortidProcessor->hasOutOfBoundIndex()) {
93  // TODO: in the shortid-collision case, we should instead request both
94  // transactions which collided. Falling back to full-block-request here
95  // is overkill.
96  return READ_STATUS_FAILED;
97  }
98 
99  {
100  LOCK(pool->cs);
101  auto it = pool->mapTx.begin();
102  while (it != pool->mapTx.end()) {
103  uint64_t shortid = cmpctblock.GetShortID(it->GetTx().GetHash());
104 
105  mempool_count +=
106  shortidProcessor->matchKnownItem(shortid, it->GetSharedTx());
107  it++;
108 
109  if (mempool_count == shortidProcessor->getShortIdCount()) {
110  break;
111  }
112  }
113  }
114 
115  for (auto &extra_txn : extra_txns) {
116  uint64_t shortid = cmpctblock.GetShortID(extra_txn.first);
117 
118  int count = shortidProcessor->matchKnownItem(shortid, extra_txn.second);
119  mempool_count += count;
120  extra_count += count;
121 
122  if (mempool_count == shortidProcessor->getShortIdCount()) {
123  break;
124  }
125  }
126 
128  "Initialized PartiallyDownloadedBlock for block %s using a "
129  "cmpctblock of size %lu\n",
130  cmpctblock.header.GetHash().ToString(),
131  GetSerializeSize(cmpctblock, PROTOCOL_VERSION));
132 
133  return READ_STATUS_OK;
134 }
135 
136 bool PartiallyDownloadedBlock::IsTxAvailable(size_t index) const {
137  assert(!header.IsNull());
138  assert(shortidProcessor != nullptr);
139  return shortidProcessor->getItem(index) != nullptr;
140 }
141 
143  CBlock &block, const std::vector<CTransactionRef> &vtx_missing) {
144  assert(!header.IsNull());
145  uint256 hash = header.GetHash();
146  block = header;
147  const size_t txnCount = shortidProcessor->getItemCount();
148  block.vtx.resize(txnCount);
149 
150  size_t tx_missing_offset = 0;
151  for (size_t i = 0; i < txnCount; i++) {
152  auto &txn_available = shortidProcessor->getItem(i);
153  if (!txn_available) {
154  if (vtx_missing.size() <= tx_missing_offset) {
155  return READ_STATUS_INVALID;
156  }
157  block.vtx[i] = vtx_missing[tx_missing_offset++];
158  } else {
159  block.vtx[i] = std::move(txn_available);
160  }
161  }
162 
163  // Make sure we can't call FillBlock again.
164  header.SetNull();
165  shortidProcessor.reset();
166 
167  if (vtx_missing.size() != tx_missing_offset) {
168  return READ_STATUS_INVALID;
169  }
170 
171  BlockValidationState state;
172  if (!CheckBlock(block, state, config->GetChainParams().GetConsensus(),
174  // TODO: We really want to just check merkle tree manually here, but
175  // that is expensive, and CheckBlock caches a block's "checked-status"
176  // (in the CBlock?). CBlock should be able to check its own merkle root
177  // and cache that check.
179  // Possible Short ID collision.
180  return READ_STATUS_FAILED;
181  }
183  }
184 
186  "Successfully reconstructed block %s with %lu txn prefilled, %lu "
187  "txn from mempool (incl at least %lu from extra pool) and %lu txn "
188  "requested\n",
190  vtx_missing.size());
191  if (vtx_missing.size() < 5) {
192  for (const auto &tx : vtx_missing) {
194  "Reconstructed block %s required tx %s\n", hash.ToString(),
195  tx->GetId().ToString());
196  }
197  }
198 
199  return READ_STATUS_OK;
200 }
@ READ_STATUS_OK
@ READ_STATUS_INVALID
@ READ_STATUS_CHECKBLOCK_FAILED
@ READ_STATUS_FAILED
enum ReadStatus_t ReadStatus
uint64_t GetShortID(const TxHash &txhash) const
void FillShortTxIDSelector() const
std::vector< PrefilledTransaction > prefilledtxn
static constexpr int SHORTTXIDS_LENGTH
std::vector< uint64_t > shorttxids
BlockHash GetHash() const
Definition: block.cpp:11
void SetNull()
Definition: block.h:39
bool IsNull() const
Definition: block.h:48
Definition: block.h:55
std::vector< CTransactionRef > vtx
Definition: block.h:58
const Consensus::Params & GetConsensus() const
Definition: chainparams.h:86
Double ended buffer combining vector and stream-like interfaces.
Definition: streams.h:197
const_iterator begin() const
Definition: streams.h:276
const_iterator end() const
Definition: streams.h:278
A hasher class for SHA-256.
Definition: sha256.h:13
CSHA256 & Write(const uint8_t *data, size_t len)
Definition: sha256.cpp:819
void Finalize(uint8_t hash[OUTPUT_SIZE])
Definition: sha256.cpp:844
The basic transaction that is broadcasted on the network and contained in blocks.
Definition: transaction.h:194
const TxHash GetHash() const
Definition: transaction.h:245
RecursiveMutex cs
This mutex needs to be locked when accessing mapTx or other members that are guarded by it.
Definition: txmempool.h:521
virtual uint64_t GetMaxBlockSize() const =0
virtual const CChainParams & GetChainParams() const =0
ReadStatus InitData(const CBlockHeaderAndShortTxIDs &cmpctblock, const std::vector< std::pair< TxHash, CTransactionRef >> &extra_txn)
const CTxMemPool * pool
bool IsTxAvailable(size_t index) const
ReadStatus FillBlock(CBlock &block, const std::vector< CTransactionRef > &vtx_missing)
std::shared_ptr< TransactionShortIdProcessor > shortidProcessor
Result GetResult() const
Definition: validation.h:123
uint8_t * begin()
Definition: uint256.h:83
std::string ToString() const
Definition: uint256.h:78
uint64_t GetUint64(int pos) const
Definition: uint256.h:93
256-bit opaque blob.
Definition: uint256.h:127
@ BLOCK_MUTATED
the block's data didn't match the data committed to by the PoW
#define LogPrint(category,...)
Definition: logging.h:208
@ CMPCTBLOCK
Definition: logging.h:51
bool CheckBlock(const CCheckpointData &data, int nHeight, const BlockHash &hash)
Returns true if block passes checkpoint checks.
Definition: checkpoints.cpp:11
uint64_t GetRand(uint64_t nMax) noexcept
Generate a uniform random integer in the range [0..range).
Definition: random.cpp:650
@ SER_NETWORK
Definition: serialize.h:166
size_t GetSerializeSize(const T &t, int nVersion=0)
Definition: serialize.h:1259
uint64_t SipHashUint256(uint64_t k0, uint64_t k1, const uint256 &val)
Optimized SipHash-2-4 implementation for uint256.
Definition: siphash.cpp:99
A TxHash is the double sha256 hash of the full transaction data.
Definition: txid.h:22
#define LOCK(cs)
Definition: sync.h:243
static int count
Definition: tests.c:31
assert(!tx.IsCoinBase())
#define MIN_TRANSACTION_SIZE
Definition: validation.h:68
static const int PROTOCOL_VERSION
network protocol versioning
Definition: version.h:11