Changeset View
Changeset View
Standalone View
Standalone View
src/blockencodings.cpp
Show First 20 Lines • Show All 54 Lines • ▼ Show 20 Lines | if (cmpctblock.header.IsNull() || | ||||
(cmpctblock.shorttxids.empty() && cmpctblock.prefilledtxn.empty())) { | (cmpctblock.shorttxids.empty() && cmpctblock.prefilledtxn.empty())) { | ||||
return READ_STATUS_INVALID; | return READ_STATUS_INVALID; | ||||
} | } | ||||
if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > | if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > | ||||
config->GetMaxBlockSize() / MIN_TRANSACTION_SIZE) { | config->GetMaxBlockSize() / MIN_TRANSACTION_SIZE) { | ||||
return READ_STATUS_INVALID; | return READ_STATUS_INVALID; | ||||
} | } | ||||
assert(header.IsNull() && txns_available.empty()); | assert(header.IsNull()); | ||||
assert(shortidProcessor == nullptr); | |||||
header = cmpctblock.header; | header = cmpctblock.header; | ||||
txns_available.resize(cmpctblock.BlockTxCount()); | |||||
for (const auto &prefilledtxn : cmpctblock.prefilledtxn) { | for (const auto &prefilledtxn : cmpctblock.prefilledtxn) { | ||||
if (prefilledtxn.tx->IsNull()) { | if (prefilledtxn.tx->IsNull()) { | ||||
return READ_STATUS_INVALID; | return READ_STATUS_INVALID; | ||||
} | } | ||||
txns_available[prefilledtxn.index] = prefilledtxn.tx; | |||||
} | } | ||||
prefilled_count = cmpctblock.prefilledtxn.size(); | prefilled_count = cmpctblock.prefilledtxn.size(); | ||||
// Calculate map of txids -> positions and check mempool to see what we have | // To determine the chance that the number of entries in a bucket exceeds N, | ||||
// (or don't). Because well-formed cmpctblock messages will have a | // we use the fact that the number of elements in a single bucket is | ||||
// (relatively) uniform distribution of short IDs, any highly-uneven | // binomially distributed (with n = the number of shorttxids S, and | ||||
// distribution of elements can be safely treated as a READ_STATUS_FAILED. | // p = 1 / the number of buckets), that in the worst case the number of | ||||
std::unordered_map<uint64_t, uint32_t> shorttxids( | // buckets is equal to S (due to std::unordered_map having a default load | ||||
cmpctblock.shorttxids.size()); | // factor of 1.0), and that the chance for any bucket to exceed N elements | ||||
uint32_t index_offset = 0; | // is at most buckets * (the chance that any given bucket is above N | ||||
for (size_t i = 0; i < cmpctblock.shorttxids.size(); i++) { | // elements). Thus: | ||||
while (txns_available[i + index_offset]) { | // P(max_elements_per_bucket > N) <= S * (1 - cdf(binomial(n=S,p=1/S), N)) | ||||
index_offset++; | // If we assume blocks of up to 16000, allowing 12 elements per bucket | ||||
} | // should only fail once per ~1 million block transfers (per peer and | ||||
// connection). | |||||
shorttxids[cmpctblock.shorttxids[i]] = i + index_offset; | // FIXME the value of 16000 txs in a block should be re-evaluated. | ||||
// To determine the chance that the number of entries in a bucket | shortidProcessor = std::make_shared<TransactionShortIdProcessor>( | ||||
// exceeds N, we use the fact that the number of elements in a single | cmpctblock.prefilledtxn, cmpctblock.shorttxids, 12); | ||||
// bucket is binomially distributed (with n = the number of shorttxids | |||||
// S, and p = 1 / the number of buckets), that in the worst case the | if (!shortidProcessor->isEvenlyDistributed() || | ||||
// number of buckets is equal to S (due to std::unordered_map having a | shortidProcessor->hasShortIdCollision() || | ||||
// default load factor of 1.0), and that the chance for any bucket to | shortidProcessor->hasOutOfBoundIndex()) { | ||||
// exceed N elements is at most buckets * (the chance that any given | |||||
// bucket is above N elements). Thus: P(max_elements_per_bucket > N) <= | |||||
// S * (1 - cdf(binomial(n=S,p=1/S), N)). If we assume blocks of up to | |||||
// 16000, allowing 12 elements per bucket should only fail once per ~1 | |||||
// million block transfers (per peer and connection). | |||||
if (shorttxids.bucket_size( | |||||
shorttxids.bucket(cmpctblock.shorttxids[i])) > 12) { | |||||
return READ_STATUS_FAILED; | |||||
} | |||||
} | |||||
// TODO: in the shortid-collision case, we should instead request both | // TODO: in the shortid-collision case, we should instead request both | ||||
// transactions which collided. Falling back to full-block-request here is | // transactions which collided. Falling back to full-block-request here | ||||
// overkill. | // is overkill. | ||||
if (shorttxids.size() != cmpctblock.shorttxids.size()) { | |||||
// Short ID collision | |||||
return READ_STATUS_FAILED; | return READ_STATUS_FAILED; | ||||
} | } | ||||
std::vector<bool> have_txn(txns_available.size()); | |||||
{ | { | ||||
LOCK(pool->cs); | LOCK(pool->cs); | ||||
for (size_t i = 0; i < pool->vTxHashes.size(); i++) { | for (size_t i = 0; i < pool->vTxHashes.size(); i++) { | ||||
uint64_t shortid = cmpctblock.GetShortID(pool->vTxHashes[i].first); | uint64_t shortid = cmpctblock.GetShortID(pool->vTxHashes[i].first); | ||||
std::unordered_map<uint64_t, uint32_t>::iterator idit = | |||||
shorttxids.find(shortid); | mempool_count += shortidProcessor->matchKnownItem( | ||||
if (idit != shorttxids.end()) { | shortid, pool->vTxHashes[i].second->GetSharedTx()); | ||||
if (!have_txn[idit->second]) { | |||||
txns_available[idit->second] = | if (mempool_count == shortidProcessor->getShortIdCount()) { | ||||
pool->vTxHashes[i].second->GetSharedTx(); | |||||
have_txn[idit->second] = true; | |||||
mempool_count++; | |||||
} else { | |||||
// If we find two mempool txn that match the short id, just | |||||
// request it. This should be rare enough that the extra | |||||
// bandwidth doesn't matter, but eating a round-trip due to | |||||
// FillBlock failure would be annoying. | |||||
if (txns_available[idit->second]) { | |||||
txns_available[idit->second].reset(); | |||||
mempool_count--; | |||||
} | |||||
} | |||||
} | |||||
// Though ideally we'd continue scanning for the | |||||
// two-txn-match-shortid case, the performance win of an early exit | |||||
// here is too good to pass up and worth the extra risk. | |||||
if (mempool_count == shorttxids.size()) { | |||||
break; | break; | ||||
} | } | ||||
} | } | ||||
} | } | ||||
for (auto &extra_txn : extra_txns) { | for (auto &extra_txn : extra_txns) { | ||||
uint64_t shortid = cmpctblock.GetShortID(extra_txn.first); | uint64_t shortid = cmpctblock.GetShortID(extra_txn.first); | ||||
std::unordered_map<uint64_t, uint32_t>::iterator idit = | |||||
shorttxids.find(shortid); | |||||
if (idit != shorttxids.end()) { | |||||
if (!have_txn[idit->second]) { | |||||
txns_available[idit->second] = extra_txn.second; | |||||
have_txn[idit->second] = true; | |||||
mempool_count++; | |||||
extra_count++; | |||||
} else { | |||||
// If we find two mempool/extra txn that match the short id, | |||||
// just request it. This should be rare enough that the extra | |||||
// bandwidth doesn't matter, but eating a round-trip due to | |||||
// FillBlock failure would be annoying. Note that we don't want | |||||
// duplication between extra_txns and mempool to trigger this | |||||
// case, so we compare hashes first. | |||||
if (txns_available[idit->second] && | |||||
txns_available[idit->second]->GetHash() != | |||||
extra_txn.second->GetHash()) { | |||||
txns_available[idit->second].reset(); | |||||
mempool_count--; | |||||
extra_count--; | |||||
} | |||||
} | |||||
} | |||||
// Though ideally we'd continue scanning for the two-txn-match-shortid | int count = shortidProcessor->matchKnownItem(shortid, extra_txn.second); | ||||
// case, the performance win of an early exit here is too good to pass | mempool_count += count; | ||||
// up and worth the extra risk. | extra_count += count; | ||||
if (mempool_count == shorttxids.size()) { | |||||
if (mempool_count == shortidProcessor->getShortIdCount()) { | |||||
break; | break; | ||||
} | } | ||||
} | } | ||||
LogPrint(BCLog::CMPCTBLOCK, | LogPrint(BCLog::CMPCTBLOCK, | ||||
"Initialized PartiallyDownloadedBlock for block %s using a " | "Initialized PartiallyDownloadedBlock for block %s using a " | ||||
"cmpctblock of size %lu\n", | "cmpctblock of size %lu\n", | ||||
cmpctblock.header.GetHash().ToString(), | cmpctblock.header.GetHash().ToString(), | ||||
GetSerializeSize(cmpctblock, PROTOCOL_VERSION)); | GetSerializeSize(cmpctblock, PROTOCOL_VERSION)); | ||||
return READ_STATUS_OK; | return READ_STATUS_OK; | ||||
} | } | ||||
bool PartiallyDownloadedBlock::IsTxAvailable(size_t index) const { | bool PartiallyDownloadedBlock::IsTxAvailable(size_t index) const { | ||||
assert(!header.IsNull()); | assert(!header.IsNull()); | ||||
assert(index < txns_available.size()); | assert(shortidProcessor != nullptr); | ||||
return txns_available[index] != nullptr; | return shortidProcessor->getItem(index) != nullptr; | ||||
} | } | ||||
ReadStatus PartiallyDownloadedBlock::FillBlock( | ReadStatus PartiallyDownloadedBlock::FillBlock( | ||||
CBlock &block, const std::vector<CTransactionRef> &vtx_missing) { | CBlock &block, const std::vector<CTransactionRef> &vtx_missing) { | ||||
assert(!header.IsNull()); | assert(!header.IsNull()); | ||||
uint256 hash = header.GetHash(); | uint256 hash = header.GetHash(); | ||||
block = header; | block = header; | ||||
block.vtx.resize(txns_available.size()); | const size_t txnCount = shortidProcessor->getItemCount(); | ||||
block.vtx.resize(txnCount); | |||||
size_t tx_missing_offset = 0; | size_t tx_missing_offset = 0; | ||||
for (size_t i = 0; i < txns_available.size(); i++) { | for (size_t i = 0; i < txnCount; i++) { | ||||
auto &txn_available = txns_available[i]; | auto &txn_available = shortidProcessor->getItem(i); | ||||
if (!txn_available) { | if (!txn_available) { | ||||
if (vtx_missing.size() <= tx_missing_offset) { | if (vtx_missing.size() <= tx_missing_offset) { | ||||
return READ_STATUS_INVALID; | return READ_STATUS_INVALID; | ||||
} | } | ||||
block.vtx[i] = vtx_missing[tx_missing_offset++]; | block.vtx[i] = vtx_missing[tx_missing_offset++]; | ||||
} else { | } else { | ||||
block.vtx[i] = std::move(txn_available); | block.vtx[i] = std::move(txn_available); | ||||
} | } | ||||
} | } | ||||
// Make sure we can't call FillBlock again. | // Make sure we can't call FillBlock again. | ||||
header.SetNull(); | header.SetNull(); | ||||
txns_available.clear(); | shortidProcessor.reset(); | ||||
if (vtx_missing.size() != tx_missing_offset) { | if (vtx_missing.size() != tx_missing_offset) { | ||||
return READ_STATUS_INVALID; | return READ_STATUS_INVALID; | ||||
} | } | ||||
BlockValidationState state; | BlockValidationState state; | ||||
if (!CheckBlock(block, state, config->GetChainParams().GetConsensus(), | if (!CheckBlock(block, state, config->GetChainParams().GetConsensus(), | ||||
BlockValidationOptions(*config))) { | BlockValidationOptions(*config))) { | ||||
Show All 27 Lines |