| 53 | } |
| 54 | |
| 55 | ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& cmpctblock, const std::vector<std::pair<uint256, CTransactionRef>>& extra_txn) { |
| 56 | if (cmpctblock.header.IsNull() || (cmpctblock.shorttxids.empty() && cmpctblock.prefilledtxn.empty())) |
| 57 | return READ_STATUS_INVALID; |
| 58 | if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > MAX_BLOCK_WEIGHT / MIN_SERIALIZABLE_TRANSACTION_WEIGHT) |
| 59 | return READ_STATUS_INVALID; |
| 60 | |
| 61 | assert(header.IsNull() && txn_available.empty()); |
| 62 | header = cmpctblock.header; |
| 63 | txn_available.resize(cmpctblock.BlockTxCount()); |
| 64 | |
| 65 | int32_t lastprefilledindex = -1; |
| 66 | for (size_t i = 0; i < cmpctblock.prefilledtxn.size(); i++) { |
| 67 | if (cmpctblock.prefilledtxn[i].tx->IsNull()) |
| 68 | return READ_STATUS_INVALID; |
| 69 | |
| 70 | lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1; //index is a uint16_t, so can't overflow here |
| 71 | if (lastprefilledindex > std::numeric_limits<uint16_t>::max()) |
| 72 | return READ_STATUS_INVALID; |
| 73 | if ((uint32_t)lastprefilledindex > cmpctblock.shorttxids.size() + i) { |
| 74 | // If we are inserting a tx at an index greater than our full list of shorttxids |
| 75 | // plus the number of prefilled txn we've inserted, then we have txn for which we |
| 76 | // have neither a prefilled txn or a shorttxid! |
| 77 | return READ_STATUS_INVALID; |
| 78 | } |
| 79 | txn_available[lastprefilledindex] = cmpctblock.prefilledtxn[i].tx; |
| 80 | } |
| 81 | prefilled_count = cmpctblock.prefilledtxn.size(); |
| 82 | |
| 83 | // Calculate map of txids -> positions and check mempool to see what we have (or don't) |
| 84 | // Because well-formed cmpctblock messages will have a (relatively) uniform distribution |
| 85 | // of short IDs, any highly-uneven distribution of elements can be safely treated as a |
| 86 | // READ_STATUS_FAILED. |
| 87 | std::unordered_map<uint64_t, uint16_t> shorttxids(cmpctblock.shorttxids.size()); |
| 88 | uint16_t index_offset = 0; |
| 89 | for (size_t i = 0; i < cmpctblock.shorttxids.size(); i++) { |
| 90 | while (txn_available[i + index_offset]) |
| 91 | index_offset++; |
| 92 | shorttxids[cmpctblock.shorttxids[i]] = i + index_offset; |
| 93 | // To determine the chance that the number of entries in a bucket exceeds N, |
| 94 | // we use the fact that the number of elements in a single bucket is |
| 95 | // binomially distributed (with n = the number of shorttxids S, and p = |
| 96 | // 1 / the number of buckets), that in the worst case the number of buckets is |
| 97 | // equal to S (due to std::unordered_map having a default load factor of 1.0), |
| 98 | // and that the chance for any bucket to exceed N elements is at most |
| 99 | // buckets * (the chance that any given bucket is above N elements). |
| 100 | // Thus: P(max_elements_per_bucket > N) <= S * (1 - cdf(binomial(n=S,p=1/S), N)). |
| 101 | // If we assume blocks of up to 16000, allowing 12 elements per bucket should |
| 102 | // only fail once per ~1 million block transfers (per peer and connection). |
| 103 | if (shorttxids.bucket_size(shorttxids.bucket(cmpctblock.shorttxids[i])) > 12) |
| 104 | return READ_STATUS_FAILED; |
| 105 | } |
| 106 | // TODO: in the shortid-collision case, we should instead request both transactions |
| 107 | // which collided. Falling back to full-block-request here is overkill. |
| 108 | if (shorttxids.size() != cmpctblock.shorttxids.size()) |
| 109 | return READ_STATUS_FAILED; // Short ID collision |
| 110 | |
| 111 | std::vector<bool> have_txn(txn_available.size()); |
| 112 | { |