Changeset View
Changeset View
Standalone View
Standalone View
src/blockencodings.cpp
| Show All 10 Lines | |||||
| #include "random.h" | #include "random.h" | ||||
| #include "streams.h" | #include "streams.h" | ||||
| #include "txmempool.h" | #include "txmempool.h" | ||||
| #include "util.h" | #include "util.h" | ||||
| #include "validation.h" | #include "validation.h" | ||||
| #include <unordered_map> | #include <unordered_map> | ||||
| CBlockHeaderAndShortTxIDs::CBlockHeaderAndShortTxIDs(const CBlock &block) | CBlockHeaderAndShortTxHashes::CBlockHeaderAndShortTxHashes(const CBlock &block) | ||||
| : nonce(GetRand(std::numeric_limits<uint64_t>::max())), | : nonce(GetRand(std::numeric_limits<uint64_t>::max())), | ||||
| shorttxids(block.vtx.size() - 1), prefilledtxn(1), header(block) { | shortTxHashes(block.vtx.size() - 1), prefilledtxn(1), header(block) { | ||||
| FillShortTxIDSelector(); | FillShortTxHashSelector(); | ||||
| // TODO: Use our mempool prior to block acceptance to predictively fill more | // TODO: Use our mempool prior to block acceptance to predictively fill more | ||||
| // than just the coinbase. | // than just the coinbase. | ||||
| prefilledtxn[0] = {0, block.vtx[0]}; | prefilledtxn[0] = {0, block.vtx[0]}; | ||||
| for (size_t i = 1; i < block.vtx.size(); i++) { | for (size_t i = 1; i < block.vtx.size(); i++) { | ||||
| const CTransaction &tx = *block.vtx[i]; | const CTransaction &tx = *block.vtx[i]; | ||||
| shorttxids[i - 1] = GetShortID(tx.GetHash()); | shortTxHashes[i - 1] = GetShortID(tx.GetHash()); | ||||
| } | } | ||||
| } | } | ||||
| void CBlockHeaderAndShortTxIDs::FillShortTxIDSelector() const { | void CBlockHeaderAndShortTxHashes::FillShortTxHashSelector() const { | ||||
| CDataStream stream(SER_NETWORK, PROTOCOL_VERSION); | CDataStream stream(SER_NETWORK, PROTOCOL_VERSION); | ||||
| stream << header << nonce; | stream << header << nonce; | ||||
| CSHA256 hasher; | CSHA256 hasher; | ||||
| hasher.Write((uint8_t *)&(*stream.begin()), stream.end() - stream.begin()); | hasher.Write((uint8_t *)&(*stream.begin()), stream.end() - stream.begin()); | ||||
| uint256 shorttxidhash; | uint256 shorttxhash; | ||||
| hasher.Finalize(shorttxidhash.begin()); | hasher.Finalize(shorttxhash.begin()); | ||||
| shorttxidk0 = shorttxidhash.GetUint64(0); | shorttxhashk0 = shorttxhash.GetUint64(0); | ||||
| shorttxidk1 = shorttxidhash.GetUint64(1); | shorttxhashk1 = shorttxhash.GetUint64(1); | ||||
| } | } | ||||
| uint64_t CBlockHeaderAndShortTxIDs::GetShortID(const uint256 &txhash) const { | uint64_t CBlockHeaderAndShortTxHashes::GetShortID(const uint256 &txhash) const { | ||||
| static_assert(SHORTTXIDS_LENGTH == 6, | static_assert(SHORTTXHASHES_LENGTH == 6, | ||||
| "shorttxids calculation assumes 6-byte shorttxids"); | "shorttxhashes calculation assumes 6-byte shorttxhashes"); | ||||
| return SipHashUint256(shorttxidk0, shorttxidk1, txhash) & 0xffffffffffffL; | return SipHashUint256(shorttxhashk0, shorttxhashk1, txhash) & | ||||
| 0xffffffffffffL; | |||||
| } | } | ||||
| ReadStatus PartiallyDownloadedBlock::InitData( | ReadStatus PartiallyDownloadedBlock::InitData( | ||||
| const CBlockHeaderAndShortTxIDs &cmpctblock, | const CBlockHeaderAndShortTxHashes &cmpctblock, | ||||
| const std::vector<std::pair<uint256, CTransactionRef>> &extra_txn) { | const std::vector<std::pair<uint256, CTransactionRef>> &extra_txn) { | ||||
| if (cmpctblock.header.IsNull() || | if (cmpctblock.header.IsNull() || | ||||
| (cmpctblock.shorttxids.empty() && cmpctblock.prefilledtxn.empty())) | (cmpctblock.shortTxHashes.empty() && cmpctblock.prefilledtxn.empty())) | ||||
| return READ_STATUS_INVALID; | return READ_STATUS_INVALID; | ||||
| if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > | if (cmpctblock.shortTxHashes.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() && txn_available.empty()); | assert(header.IsNull() && txn_available.empty()); | ||||
| header = cmpctblock.header; | header = cmpctblock.header; | ||||
| txn_available.resize(cmpctblock.BlockTxCount()); | txn_available.resize(cmpctblock.BlockTxCount()); | ||||
| int32_t lastprefilledindex = -1; | int32_t lastprefilledindex = -1; | ||||
| for (size_t i = 0; i < cmpctblock.prefilledtxn.size(); i++) { | for (size_t i = 0; i < cmpctblock.prefilledtxn.size(); i++) { | ||||
| if (cmpctblock.prefilledtxn[i].tx->IsNull()) return READ_STATUS_INVALID; | if (cmpctblock.prefilledtxn[i].tx->IsNull()) return READ_STATUS_INVALID; | ||||
| // index is a uint16_t, so can't overflow here. | // index is a uint16_t, so can't overflow here. | ||||
| lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1; | lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1; | ||||
| if (lastprefilledindex > std::numeric_limits<uint16_t>::max()) | if (lastprefilledindex > std::numeric_limits<uint16_t>::max()) | ||||
| return READ_STATUS_INVALID; | return READ_STATUS_INVALID; | ||||
| if ((uint32_t)lastprefilledindex > cmpctblock.shorttxids.size() + i) { | if ((uint32_t)lastprefilledindex > | ||||
| cmpctblock.shortTxHashes.size() + i) { | |||||
| // If we are inserting a tx at an index greater than our full list | // If we are inserting a tx at an index greater than our full list | ||||
| // of shorttxids plus the number of prefilled txn we've inserted, | // of shortTxHashes plus the number of prefilled txn we've inserted, | ||||
| // then we have txn for which we have neither a prefilled txn or a | // then we have txn for which we have neither a prefilled txn or a | ||||
| // shorttxid! | // shorttxhash! | ||||
| return READ_STATUS_INVALID; | return READ_STATUS_INVALID; | ||||
| } | } | ||||
| txn_available[lastprefilledindex] = cmpctblock.prefilledtxn[i].tx; | txn_available[lastprefilledindex] = cmpctblock.prefilledtxn[i].tx; | ||||
| } | } | ||||
| prefilled_count = cmpctblock.prefilledtxn.size(); | prefilled_count = cmpctblock.prefilledtxn.size(); | ||||
| // Calculate map of txids -> positions and check mempool to see what we have | // Calculate map of txhashes -> positions and check mempool to see what we | ||||
| // have | |||||
| // (or don't). Because well-formed cmpctblock messages will have a | // (or don't). Because well-formed cmpctblock messages will have a | ||||
| // (relatively) uniform distribution of short IDs, any highly-uneven | // (relatively) uniform distribution of short IDs, any highly-uneven | ||||
| // distribution of elements can be safely treated as a READ_STATUS_FAILED. | // distribution of elements can be safely treated as a READ_STATUS_FAILED. | ||||
| std::unordered_map<uint64_t, uint16_t> shorttxids( | std::unordered_map<uint64_t, uint16_t> shorttxhashes( | ||||
| cmpctblock.shorttxids.size()); | cmpctblock.shortTxHashes.size()); | ||||
| uint16_t index_offset = 0; | uint16_t index_offset = 0; | ||||
| for (size_t i = 0; i < cmpctblock.shorttxids.size(); i++) { | for (size_t i = 0; i < cmpctblock.shortTxHashes.size(); i++) { | ||||
| while (txn_available[i + index_offset]) | while (txn_available[i + index_offset]) | ||||
| index_offset++; | index_offset++; | ||||
| shorttxids[cmpctblock.shorttxids[i]] = i + index_offset; | shorttxhashes[cmpctblock.shortTxHashes[i]] = i + index_offset; | ||||
| // To determine the chance that the number of entries in a bucket | // To determine the chance that the number of entries in a bucket | ||||
| // exceeds N, we use the fact that the number of elements in a single | // exceeds N, we use the fact that the number of elements in a single | ||||
| // bucket is binomially distributed (with n = the number of shorttxids | // bucket is binomially distributed (with n = the number of | ||||
| // shorttxhashes | |||||
| // S, and p = 1 / the number of buckets), that in the worst case the | // S, and p = 1 / the number of buckets), that in the worst case the | ||||
| // number of buckets is equal to S (due to std::unordered_map having a | // number of buckets is equal to S (due to std::unordered_map having a | ||||
| // default load factor of 1.0), and that the chance for any bucket to | // default load factor of 1.0), and that the chance for any bucket to | ||||
| // exceed N elements is at most buckets * (the chance that any given | // exceed N elements is at most buckets * (the chance that any given | ||||
| // bucket is above N elements). Thus: P(max_elements_per_bucket > N) <= | // 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 | // 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 | // 16000, allowing 12 elements per bucket should only fail once per ~1 | ||||
| // million block transfers (per peer and connection). | // million block transfers (per peer and connection). | ||||
| if (shorttxids.bucket_size( | if (shorttxhashes.bucket_size( | ||||
| shorttxids.bucket(cmpctblock.shorttxids[i])) > 12) | shorttxhashes.bucket(cmpctblock.shortTxHashes[i])) > 12) | ||||
| return READ_STATUS_FAILED; | 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 is | ||||
| // overkill. | // overkill. | ||||
| if (shorttxids.size() != cmpctblock.shorttxids.size()) { | if (shorttxhashes.size() != cmpctblock.shortTxHashes.size()) { | ||||
| // Short ID collision | // Short ID collision | ||||
| return READ_STATUS_FAILED; | return READ_STATUS_FAILED; | ||||
| } | } | ||||
| std::vector<bool> have_txn(txn_available.size()); | std::vector<bool> have_txn(txn_available.size()); | ||||
| { | { | ||||
| LOCK(pool->cs); | LOCK(pool->cs); | ||||
| const std::vector<std::pair<uint256, CTxMemPool::txiter>> &vTxHashes = | const std::vector<std::pair<txhash_t, CTxMemPool::txiter>> &vTxHashes = | ||||
| pool->vTxHashes; | pool->vTxHashes; | ||||
| for (size_t i = 0; i < vTxHashes.size(); i++) { | for (size_t i = 0; i < vTxHashes.size(); i++) { | ||||
| uint64_t shortid = cmpctblock.GetShortID(vTxHashes[i].first); | uint64_t shortid = cmpctblock.GetShortID(vTxHashes[i].first); | ||||
| std::unordered_map<uint64_t, uint16_t>::iterator idit = | std::unordered_map<uint64_t, uint16_t>::iterator idit = | ||||
| shorttxids.find(shortid); | shorttxhashes.find(shortid); | ||||
| if (idit != shorttxids.end()) { | if (idit != shorttxhashes.end()) { | ||||
| if (!have_txn[idit->second]) { | if (!have_txn[idit->second]) { | ||||
| txn_available[idit->second] = | txn_available[idit->second] = | ||||
| vTxHashes[i].second->GetSharedTx(); | vTxHashes[i].second->GetSharedTx(); | ||||
| have_txn[idit->second] = true; | have_txn[idit->second] = true; | ||||
| mempool_count++; | mempool_count++; | ||||
| } else { | } else { | ||||
| // If we find two mempool txn that match the short id, just | // If we find two mempool txn that match the short id, just | ||||
| // request it. This should be rare enough that the extra | // request it. This should be rare enough that the extra | ||||
| // bandwidth doesn't matter, but eating a round-trip due to | // bandwidth doesn't matter, but eating a round-trip due to | ||||
| // FillBlock failure would be annoying. | // FillBlock failure would be annoying. | ||||
| if (txn_available[idit->second]) { | if (txn_available[idit->second]) { | ||||
| txn_available[idit->second].reset(); | txn_available[idit->second].reset(); | ||||
| mempool_count--; | mempool_count--; | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| // Though ideally we'd continue scanning for the | // Though ideally we'd continue scanning for the | ||||
| // two-txn-match-shortid case, the performance win of an early exit | // two-txn-match-shortid case, the performance win of an early exit | ||||
| // here is too good to pass up and worth the extra risk. | // here is too good to pass up and worth the extra risk. | ||||
| if (mempool_count == shorttxids.size()) break; | if (mempool_count == shorttxhashes.size()) break; | ||||
| } | } | ||||
| } | } | ||||
| for (size_t i = 0; i < extra_txn.size(); i++) { | for (size_t i = 0; i < extra_txn.size(); i++) { | ||||
| uint64_t shortid = cmpctblock.GetShortID(extra_txn[i].first); | uint64_t shortid = cmpctblock.GetShortID(extra_txn[i].first); | ||||
| std::unordered_map<uint64_t, uint16_t>::iterator idit = | std::unordered_map<uint64_t, uint16_t>::iterator idit = | ||||
| shorttxids.find(shortid); | shorttxhashes.find(shortid); | ||||
| if (idit != shorttxids.end()) { | if (idit != shorttxhashes.end()) { | ||||
| if (!have_txn[idit->second]) { | if (!have_txn[idit->second]) { | ||||
| txn_available[idit->second] = extra_txn[i].second; | txn_available[idit->second] = extra_txn[i].second; | ||||
| have_txn[idit->second] = true; | have_txn[idit->second] = true; | ||||
| mempool_count++; | mempool_count++; | ||||
| extra_count++; | extra_count++; | ||||
| } else { | } else { | ||||
| // If we find two mempool/extra txn that match the short id, | // If we find two mempool/extra txn that match the short id, | ||||
| // just request it. This should be rare enough that the extra | // just request it. This should be rare enough that the extra | ||||
| Show All 9 Lines | for (size_t i = 0; i < extra_txn.size(); i++) { | ||||
| extra_count--; | extra_count--; | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| // Though ideally we'd continue scanning for the two-txn-match-shortid | // 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 | // case, the performance win of an early exit here is too good to pass | ||||
| // up and worth the extra risk. | // up and worth the extra risk. | ||||
| if (mempool_count == shorttxids.size()) break; | if (mempool_count == shorttxhashes.size()) break; | ||||
| } | } | ||||
| LogPrint("cmpctblock", "Initialized PartiallyDownloadedBlock for block %s " | LogPrint("cmpctblock", "Initialized PartiallyDownloadedBlock for block %s " | ||||
| "using a cmpctblock of size %lu\n", | "using a cmpctblock of size %lu\n", | ||||
| cmpctblock.header.GetHash().ToString(), | cmpctblock.header.GetHash().ToString(), | ||||
| GetSerializeSize(cmpctblock, SER_NETWORK, PROTOCOL_VERSION)); | GetSerializeSize(cmpctblock, SER_NETWORK, PROTOCOL_VERSION)); | ||||
| return READ_STATUS_OK; | return READ_STATUS_OK; | ||||
| ▲ Show 20 Lines • Show All 44 Lines • ▼ Show 20 Lines | ReadStatus PartiallyDownloadedBlock::FillBlock( | ||||
| LogPrint("cmpctblock", "Successfully reconstructed block %s with %lu txn " | LogPrint("cmpctblock", "Successfully reconstructed block %s with %lu txn " | ||||
| "prefilled, %lu txn from mempool (incl at least %lu " | "prefilled, %lu txn from mempool (incl at least %lu " | ||||
| "from extra pool) and %lu txn requested\n", | "from extra pool) and %lu txn requested\n", | ||||
| hash.ToString(), prefilled_count, mempool_count, extra_count, | hash.ToString(), prefilled_count, mempool_count, extra_count, | ||||
| vtx_missing.size()); | vtx_missing.size()); | ||||
| if (vtx_missing.size() < 5) { | if (vtx_missing.size() < 5) { | ||||
| for (const auto &tx : vtx_missing) | for (const auto &tx : vtx_missing) | ||||
| LogPrint("cmpctblock", "Reconstructed block %s required tx %s\n", | LogPrint("cmpctblock", "Reconstructed block %s required tx %s\n", | ||||
| hash.ToString(), tx->GetId().ToString()); | hash.ToString(), tx->GetHash().ToString()); | ||||
| } | } | ||||
| return READ_STATUS_OK; | return READ_STATUS_OK; | ||||
| } | } | ||||