You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

blockencodings.cpp 10KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218
  1. // Copyright (c) 2016 The Starwels developers
  2. // Distributed under the MIT software license, see the accompanying
  3. // file COPYING or http://www.opensource.org/licenses/mit-license.php.
  4. #include "blockencodings.h"
  5. #include "consensus/consensus.h"
  6. #include "consensus/validation.h"
  7. #include "chainparams.h"
  8. #include "hash.h"
  9. #include "random.h"
  10. #include "streams.h"
  11. #include "txmempool.h"
  12. #include "validation.h"
  13. #include "util.h"
  14. #include <unordered_map>
  15. CBlockHeaderAndShortTxIDs::CBlockHeaderAndShortTxIDs(const CBlock& block, bool fUseWTXID) :
  16. nonce(GetRand(std::numeric_limits<uint64_t>::max())),
  17. shorttxids(block.vtx.size() - 1), prefilledtxn(1), header(block) {
  18. FillShortTxIDSelector();
  19. //TODO: Use our mempool prior to block acceptance to predictively fill more than just the coinbase
  20. prefilledtxn[0] = {0, block.vtx[0]};
  21. for (size_t i = 1; i < block.vtx.size(); i++) {
  22. const CTransaction& tx = *block.vtx[i];
  23. shorttxids[i - 1] = GetShortID(fUseWTXID ? tx.GetWitnessHash() : tx.GetHash());
  24. }
  25. }
  26. void CBlockHeaderAndShortTxIDs::FillShortTxIDSelector() const {
  27. CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
  28. stream << header << nonce;
  29. CSHA256 hasher;
  30. hasher.Write((unsigned char*)&(*stream.begin()), stream.end() - stream.begin());
  31. uint256 shorttxidhash;
  32. hasher.Finalize(shorttxidhash.begin());
  33. shorttxidk0 = shorttxidhash.GetUint64(0);
  34. shorttxidk1 = shorttxidhash.GetUint64(1);
  35. }
  36. uint64_t CBlockHeaderAndShortTxIDs::GetShortID(const uint256& txhash) const {
  37. static_assert(SHORTTXIDS_LENGTH == 6, "shorttxids calculation assumes 6-byte shorttxids");
  38. return SipHashUint256(shorttxidk0, shorttxidk1, txhash) & 0xffffffffffffL;
  39. }
  40. ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& cmpctblock, const std::vector<std::pair<uint256, CTransactionRef>>& extra_txn) {
  41. if (cmpctblock.header.IsNull() || (cmpctblock.shorttxids.empty() && cmpctblock.prefilledtxn.empty()))
  42. return READ_STATUS_INVALID;
  43. if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > MAX_BLOCK_WEIGHT / MIN_SERIALIZABLE_TRANSACTION_WEIGHT)
  44. return READ_STATUS_INVALID;
  45. assert(header.IsNull() && txn_available.empty());
  46. header = cmpctblock.header;
  47. txn_available.resize(cmpctblock.BlockTxCount());
  48. int32_t lastprefilledindex = -1;
  49. for (size_t i = 0; i < cmpctblock.prefilledtxn.size(); i++) {
  50. if (cmpctblock.prefilledtxn[i].tx->IsNull())
  51. return READ_STATUS_INVALID;
  52. lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1; //index is a uint16_t, so can't overflow here
  53. if (lastprefilledindex > std::numeric_limits<uint16_t>::max())
  54. return READ_STATUS_INVALID;
  55. if ((uint32_t)lastprefilledindex > cmpctblock.shorttxids.size() + i) {
  56. // If we are inserting a tx at an index greater than our full list of shorttxids
  57. // plus the number of prefilled txn we've inserted, then we have txn for which we
  58. // have neither a prefilled txn or a shorttxid!
  59. return READ_STATUS_INVALID;
  60. }
  61. txn_available[lastprefilledindex] = cmpctblock.prefilledtxn[i].tx;
  62. }
  63. prefilled_count = cmpctblock.prefilledtxn.size();
  64. // Calculate map of txids -> positions and check mempool to see what we have (or don't)
  65. // Because well-formed cmpctblock messages will have a (relatively) uniform distribution
  66. // of short IDs, any highly-uneven distribution of elements can be safely treated as a
  67. // READ_STATUS_FAILED.
  68. std::unordered_map<uint64_t, uint16_t> shorttxids(cmpctblock.shorttxids.size());
  69. uint16_t index_offset = 0;
  70. for (size_t i = 0; i < cmpctblock.shorttxids.size(); i++) {
  71. while (txn_available[i + index_offset])
  72. index_offset++;
  73. shorttxids[cmpctblock.shorttxids[i]] = i + index_offset;
  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 p =
  77. // 1 / the number of buckets), that in the worst case the number of buckets is
  78. // equal to S (due to std::unordered_map having a default load factor of 1.0),
  79. // and that the chance for any bucket to exceed N elements is at most
  80. // buckets * (the chance that any given bucket is above N elements).
  81. // Thus: P(max_elements_per_bucket > N) <= S * (1 - cdf(binomial(n=S,p=1/S), N)).
  82. // If we assume blocks of up to 16000, allowing 12 elements per bucket should
  83. // only fail once per ~1 million block transfers (per peer and connection).
  84. if (shorttxids.bucket_size(shorttxids.bucket(cmpctblock.shorttxids[i])) > 12)
  85. return READ_STATUS_FAILED;
  86. }
  87. // TODO: in the shortid-collision case, we should instead request both transactions
  88. // which collided. Falling back to full-block-request here is overkill.
  89. if (shorttxids.size() != cmpctblock.shorttxids.size())
  90. return READ_STATUS_FAILED; // Short ID collision
  91. std::vector<bool> have_txn(txn_available.size());
  92. {
  93. LOCK(pool->cs);
  94. const std::vector<std::pair<uint256, CTxMemPool::txiter> >& vTxHashes = pool->vTxHashes;
  95. for (size_t i = 0; i < vTxHashes.size(); i++) {
  96. uint64_t shortid = cmpctblock.GetShortID(vTxHashes[i].first);
  97. std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
  98. if (idit != shorttxids.end()) {
  99. if (!have_txn[idit->second]) {
  100. txn_available[idit->second] = vTxHashes[i].second->GetSharedTx();
  101. have_txn[idit->second] = true;
  102. mempool_count++;
  103. } else {
  104. // If we find two mempool txn that match the short id, just request it.
  105. // This should be rare enough that the extra bandwidth doesn't matter,
  106. // but eating a round-trip due to FillBlock failure would be annoying
  107. if (txn_available[idit->second]) {
  108. txn_available[idit->second].reset();
  109. mempool_count--;
  110. }
  111. }
  112. }
  113. // Though ideally we'd continue scanning for the two-txn-match-shortid case,
  114. // the performance win of an early exit here is too good to pass up and worth
  115. // the extra risk.
  116. if (mempool_count == shorttxids.size())
  117. break;
  118. }
  119. }
  120. for (size_t i = 0; i < extra_txn.size(); i++) {
  121. uint64_t shortid = cmpctblock.GetShortID(extra_txn[i].first);
  122. std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
  123. if (idit != shorttxids.end()) {
  124. if (!have_txn[idit->second]) {
  125. txn_available[idit->second] = extra_txn[i].second;
  126. have_txn[idit->second] = true;
  127. mempool_count++;
  128. extra_count++;
  129. } else {
  130. // If we find two mempool/extra txn that match the short id, just
  131. // request it.
  132. // This should be rare enough that the extra bandwidth doesn't matter,
  133. // but eating a round-trip due to FillBlock failure would be annoying
  134. // Note that we don't want duplication between extra_txn and mempool to
  135. // trigger this case, so we compare witness hashes first
  136. if (txn_available[idit->second] &&
  137. txn_available[idit->second]->GetWitnessHash() != extra_txn[i].second->GetWitnessHash()) {
  138. txn_available[idit->second].reset();
  139. mempool_count--;
  140. extra_count--;
  141. }
  142. }
  143. }
  144. // Though ideally we'd continue scanning for the two-txn-match-shortid case,
  145. // the performance win of an early exit here is too good to pass up and worth
  146. // the extra risk.
  147. if (mempool_count == shorttxids.size())
  148. break;
  149. }
  150. LogPrint(BCLog::CMPCTBLOCK, "Initialized PartiallyDownloadedBlock for block %s using a cmpctblock of size %lu\n", cmpctblock.header.GetHash().ToString(), GetSerializeSize(cmpctblock, SER_NETWORK, PROTOCOL_VERSION));
  151. return READ_STATUS_OK;
  152. }
  153. bool PartiallyDownloadedBlock::IsTxAvailable(size_t index) const {
  154. assert(!header.IsNull());
  155. assert(index < txn_available.size());
  156. return txn_available[index] != nullptr;
  157. }
  158. ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector<CTransactionRef>& vtx_missing) {
  159. assert(!header.IsNull());
  160. uint256 hash = header.GetHash();
  161. block = header;
  162. block.vtx.resize(txn_available.size());
  163. size_t tx_missing_offset = 0;
  164. for (size_t i = 0; i < txn_available.size(); i++) {
  165. if (!txn_available[i]) {
  166. if (vtx_missing.size() <= tx_missing_offset)
  167. return READ_STATUS_INVALID;
  168. block.vtx[i] = vtx_missing[tx_missing_offset++];
  169. } else
  170. block.vtx[i] = std::move(txn_available[i]);
  171. }
  172. // Make sure we can't call FillBlock again.
  173. header.SetNull();
  174. txn_available.clear();
  175. if (vtx_missing.size() != tx_missing_offset)
  176. return READ_STATUS_INVALID;
  177. CValidationState state;
  178. if (!CheckBlock(block, state, Params().GetConsensus())) {
  179. // TODO: We really want to just check merkle tree manually here,
  180. // but that is expensive, and CheckBlock caches a block's
  181. // "checked-status" (in the CBlock?). CBlock should be able to
  182. // check its own merkle root and cache that check.
  183. if (state.CorruptionPossible())
  184. return READ_STATUS_FAILED; // Possible Short ID collision
  185. return READ_STATUS_CHECKBLOCK_FAILED;
  186. }
  187. 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());
  188. if (vtx_missing.size() < 5) {
  189. for (const auto& tx : vtx_missing) {
  190. LogPrint(BCLog::CMPCTBLOCK, "Reconstructed block %s required tx %s\n", hash.ToString(), tx->GetHash().ToString());
  191. }
  192. }
  193. return READ_STATUS_OK;
  194. }