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