From 85ad31ede7bc338079c8ae643542fde7ad83ce55 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Fri, 15 Apr 2016 12:23:57 -0700 Subject: Add partial-block block encodings API --- src/blockencodings.cpp | 158 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 158 insertions(+) create mode 100644 src/blockencodings.cpp (limited to 'src/blockencodings.cpp') diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp new file mode 100644 index 000000000..c6b79f420 --- /dev/null +++ b/src/blockencodings.cpp @@ -0,0 +1,158 @@ +// Copyright (c) 2016 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include "blockencodings.h" +#include "consensus/consensus.h" +#include "consensus/validation.h" +#include "chainparams.h" +#include "hash.h" +#include "random.h" +#include "streams.h" +#include "txmempool.h" +#include "main.h" + +#include + +#define MIN_TRANSACTION_SIZE (::GetSerializeSize(CTransaction(), SER_NETWORK, PROTOCOL_VERSION)) + +CBlockHeaderAndShortTxIDs::CBlockHeaderAndShortTxIDs(const CBlock& block) : + nonce(GetRand(std::numeric_limits::max())), + shorttxids(block.vtx.size() - 1), prefilledtxn(1), header(block) { + FillShortTxIDSelector(); + //TODO: Use our mempool prior to block acceptance to predictively fill more than just the coinbase + prefilledtxn[0] = {0, block.vtx[0]}; + for (size_t i = 1; i < block.vtx.size(); i++) { + const CTransaction& tx = block.vtx[i]; + shorttxids[i - 1] = GetShortID(tx.GetHash()); + } +} + +void CBlockHeaderAndShortTxIDs::FillShortTxIDSelector() const { + CDataStream stream(SER_NETWORK, PROTOCOL_VERSION); + stream << header << nonce; + CSHA256 hasher; + hasher.Write((unsigned char*)&(*stream.begin()), stream.end() - stream.begin()); + uint256 shorttxidhash; + hasher.Finalize(shorttxidhash.begin()); + shorttxidk0 = shorttxidhash.GetUint64(0); + shorttxidk1 = shorttxidhash.GetUint64(1); +} + +uint64_t CBlockHeaderAndShortTxIDs::GetShortID(const uint256& txhash) const { + static_assert(SHORTTXIDS_LENGTH == 6, "shorttxids calculation assumes 6-byte shorttxids"); + return SipHashUint256(shorttxidk0, shorttxidk1, txhash) & 0xffffffffffffL; +} + + + +ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& cmpctblock) { + if (cmpctblock.header.IsNull() || (cmpctblock.shorttxids.empty() && cmpctblock.prefilledtxn.empty())) + return READ_STATUS_INVALID; + if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > MAX_BLOCK_SIZE / MIN_TRANSACTION_SIZE) + return READ_STATUS_INVALID; + + assert(header.IsNull() && txn_available.empty()); + header = cmpctblock.header; + txn_available.resize(cmpctblock.BlockTxCount()); + + int32_t lastprefilledindex = -1; + for (size_t i = 0; i < cmpctblock.prefilledtxn.size(); i++) { + if (cmpctblock.prefilledtxn[i].tx.IsNull()) + return READ_STATUS_INVALID; + + lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1; //index is a uint16_t, so cant overflow here + if (lastprefilledindex > std::numeric_limits::max()) + return READ_STATUS_INVALID; + if ((uint32_t)lastprefilledindex > cmpctblock.shorttxids.size() + i) { + // 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, then we have txn for which we + // have neither a prefilled txn or a shorttxid! + return READ_STATUS_INVALID; + } + txn_available[lastprefilledindex] = std::make_shared(cmpctblock.prefilledtxn[i].tx); + } + + // Calculate map of txids -> positions and check mempool to see what we have (or dont) + // Because well-formed cmpctblock messages will have a (relatively) uniform distribution + // of short IDs, any highly-uneven distribution of elements can be safely treated as a + // READ_STATUS_FAILED. + std::unordered_map shorttxids(cmpctblock.shorttxids.size()); + uint16_t index_offset = 0; + for (size_t i = 0; i < cmpctblock.shorttxids.size(); i++) { + while (txn_available[i + index_offset]) + index_offset++; + shorttxids[cmpctblock.shorttxids[i]] = i + index_offset; + // Bucket selection is a simple Binomial distribution. If we assume blocks of + // 10,000 transactions, allowing up to 12 elements per bucket should only fail + // once every ~1.3 million blocks and once every 74,000 blocks in a worst-case + // 16,000-transaction block. + 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 transactions + // which collided. Falling back to full-block-request here is overkill. + if (shorttxids.size() != cmpctblock.shorttxids.size()) + return READ_STATUS_FAILED; // Short ID collision + + std::vector have_txn(txn_available.size()); + LOCK(pool->cs); + for (CTxMemPool::txiter it = pool->mapTx.begin(); it != pool->mapTx.end(); it++) { + std::unordered_map::iterator idit = shorttxids.find(cmpctblock.GetShortID(it->GetTx().GetHash())); + if (idit != shorttxids.end()) { + if (!have_txn[idit->second]) { + txn_available[idit->second] = it->GetSharedTx(); + have_txn[idit->second] = true; + } 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 + txn_available[idit->second].reset(); + } + } + // 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; + } + + return READ_STATUS_OK; +} + +bool PartiallyDownloadedBlock::IsTxAvailable(size_t index) const { + assert(!header.IsNull()); + assert(index < txn_available.size()); + return txn_available[index] ? true : false; +} + +ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector& vtx_missing) const { + assert(!header.IsNull()); + block = header; + block.vtx.resize(txn_available.size()); + + size_t tx_missing_offset = 0; + for (size_t i = 0; i < txn_available.size(); i++) { + if (!txn_available[i]) { + if (vtx_missing.size() <= tx_missing_offset) + return READ_STATUS_INVALID; + block.vtx[i] = vtx_missing[tx_missing_offset++]; + } else + block.vtx[i] = *txn_available[i]; + } + if (vtx_missing.size() != tx_missing_offset) + return READ_STATUS_INVALID; + + CValidationState state; + if (!CheckBlock(block, state, Params().GetConsensus())) { + // TODO: We really want to just check merkle tree manually here, + // but that is expensive, and CheckBlock caches a block's + // "checked-status" (in the CBlock?). CBlock should be able to + // check its own merkle root and cache that check. + if (state.CorruptionPossible()) + return READ_STATUS_FAILED; // Possible Short ID collision + return READ_STATUS_INVALID; + } + + return READ_STATUS_OK; +} -- cgit v1.2.3 From 56ba5167272bc5afa8629ad93f16ed5135490bf5 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Wed, 8 Jun 2016 15:43:50 -0700 Subject: Add reconstruction debug logging --- src/blockencodings.cpp | 16 +++++++++++++++- 1 file changed, 15 insertions(+), 1 deletion(-) (limited to 'src/blockencodings.cpp') diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp index c6b79f420..204de45c2 100644 --- a/src/blockencodings.cpp +++ b/src/blockencodings.cpp @@ -11,6 +11,7 @@ #include "streams.h" #include "txmempool.h" #include "main.h" +#include "util.h" #include @@ -72,6 +73,7 @@ ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& c } txn_available[lastprefilledindex] = std::make_shared(cmpctblock.prefilledtxn[i].tx); } + prefilled_count = cmpctblock.prefilledtxn.size(); // Calculate map of txids -> positions and check mempool to see what we have (or dont) // Because well-formed cmpctblock messages will have a (relatively) uniform distribution @@ -103,11 +105,15 @@ ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& c if (!have_txn[idit->second]) { txn_available[idit->second] = it->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 - txn_available[idit->second].reset(); + if (txn_available[idit->second]) { + txn_available[idit->second].reset(); + mempool_count--; + } } } // Though ideally we'd continue scanning for the two-txn-match-shortid case, @@ -117,6 +123,8 @@ ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& c break; } + LogPrint("cmpctblock", "Initialized PartiallyDownloadedBlock for block %s using a cmpctblock of size %lu\n", cmpctblock.header.GetHash().ToString(), cmpctblock.GetSerializeSize(SER_NETWORK, PROTOCOL_VERSION)); + return READ_STATUS_OK; } @@ -154,5 +162,11 @@ ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector< return READ_STATUS_INVALID; } + LogPrint("cmpctblock", "Successfully reconstructed block %s with %lu txn prefilled, %lu txn from mempool and %lu txn requested\n", header.GetHash().ToString(), prefilled_count, mempool_count, vtx_missing.size()); + if (vtx_missing.size() < 5) { + for(const CTransaction& tx : vtx_missing) + LogPrint("cmpctblock", "Reconstructed block %s required tx %s\n", header.GetHash().ToString(), tx.GetHash().ToString()); + } + return READ_STATUS_OK; } -- cgit v1.2.3 From 0d4cb48ef1b916679d9fad9f247a297c85c7fedf Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Sun, 19 Jun 2016 01:31:52 -0700 Subject: Use vTxHashes to optimize InitData significantly --- src/blockencodings.cpp | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) (limited to 'src/blockencodings.cpp') diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp index 204de45c2..9a0805e40 100644 --- a/src/blockencodings.cpp +++ b/src/blockencodings.cpp @@ -99,11 +99,13 @@ ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& c std::vector have_txn(txn_available.size()); LOCK(pool->cs); - for (CTxMemPool::txiter it = pool->mapTx.begin(); it != pool->mapTx.end(); it++) { - std::unordered_map::iterator idit = shorttxids.find(cmpctblock.GetShortID(it->GetTx().GetHash())); + const std::vector >& vTxHashes = pool->vTxHashes; + for (size_t i = 0; i < vTxHashes.size(); i++) { + uint64_t shortid = cmpctblock.GetShortID(vTxHashes[i].first); + std::unordered_map::iterator idit = shorttxids.find(shortid); if (idit != shorttxids.end()) { if (!have_txn[idit->second]) { - txn_available[idit->second] = it->GetSharedTx(); + txn_available[idit->second] = vTxHashes[i].second->GetSharedTx(); have_txn[idit->second] = true; mempool_count++; } else { -- cgit v1.2.3 From ccd06b94f69c3e7758c35ac4bcd36d0e9450e158 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Sat, 18 Jun 2016 01:36:23 +0200 Subject: Elaborate bucket size math --- src/blockencodings.cpp | 14 ++++++++++---- 1 file changed, 10 insertions(+), 4 deletions(-) (limited to 'src/blockencodings.cpp') diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp index 9a0805e40..7fd6a9cf5 100644 --- a/src/blockencodings.cpp +++ b/src/blockencodings.cpp @@ -85,10 +85,16 @@ ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& c while (txn_available[i + index_offset]) index_offset++; shorttxids[cmpctblock.shorttxids[i]] = i + index_offset; - // Bucket selection is a simple Binomial distribution. If we assume blocks of - // 10,000 transactions, allowing up to 12 elements per bucket should only fail - // once every ~1.3 million blocks and once every 74,000 blocks in a worst-case - // 16,000-transaction block. + // 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 bucket is + // binomially distributed (with n = the number of shorttxids 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 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 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; } -- cgit v1.2.3 From 2b1f6f9ccf36f1e0a2c9d99154e1642f796d7c2b Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Sun, 3 Jan 2016 18:54:50 +0100 Subject: BIP141: Other consensus critical limits, and BIP145 Includes changes by Suhas Daftuar, Luke-jr, and mruddy. --- src/blockencodings.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/blockencodings.cpp') diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp index 7fd6a9cf5..5c4c3bd27 100644 --- a/src/blockencodings.cpp +++ b/src/blockencodings.cpp @@ -15,7 +15,7 @@ #include -#define MIN_TRANSACTION_SIZE (::GetSerializeSize(CTransaction(), SER_NETWORK, PROTOCOL_VERSION)) +#define MIN_TRANSACTION_BASE_SIZE (::GetSerializeSize(CTransaction(), SER_NETWORK, PROTOCOL_VERSION | SERIALIZE_TRANSACTION_NO_WITNESS)) CBlockHeaderAndShortTxIDs::CBlockHeaderAndShortTxIDs(const CBlock& block) : nonce(GetRand(std::numeric_limits::max())), @@ -50,7 +50,7 @@ uint64_t CBlockHeaderAndShortTxIDs::GetShortID(const uint256& txhash) const { ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& cmpctblock) { if (cmpctblock.header.IsNull() || (cmpctblock.shorttxids.empty() && cmpctblock.prefilledtxn.empty())) return READ_STATUS_INVALID; - if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > MAX_BLOCK_SIZE / MIN_TRANSACTION_SIZE) + if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > MAX_BLOCK_BASE_SIZE / MIN_TRANSACTION_BASE_SIZE) return READ_STATUS_INVALID; assert(header.IsNull() && txn_available.empty()); -- cgit v1.2.3 From 1aacfc2da521a8e0d718e9ac561d9b2d7916eb0b Mon Sep 17 00:00:00 2001 From: leijurv Date: Sat, 13 Aug 2016 11:21:13 -0600 Subject: various typos --- src/blockencodings.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/blockencodings.cpp') diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp index 5c4c3bd27..df237f8f2 100644 --- a/src/blockencodings.cpp +++ b/src/blockencodings.cpp @@ -75,7 +75,7 @@ ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& c } prefilled_count = cmpctblock.prefilledtxn.size(); - // Calculate map of txids -> positions and check mempool to see what we have (or dont) + // Calculate map of txids -> positions and check mempool to see what we have (or don't) // Because well-formed cmpctblock messages will have a (relatively) uniform distribution // of short IDs, any highly-uneven distribution of elements can be safely treated as a // READ_STATUS_FAILED. -- cgit v1.2.3 From 6aa28abf53ef4694692474b4a3b0a8fa7559b50b Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Sat, 25 Jun 2016 19:17:45 +0200 Subject: Use cmpctblock type 2 for segwit-enabled transfer Contains version negotiation logic by Matt Corallo and bugfixes by Suhas Daftuar. --- src/blockencodings.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/blockencodings.cpp') diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp index df237f8f2..93d3fa372 100644 --- a/src/blockencodings.cpp +++ b/src/blockencodings.cpp @@ -17,7 +17,7 @@ #define MIN_TRANSACTION_BASE_SIZE (::GetSerializeSize(CTransaction(), SER_NETWORK, PROTOCOL_VERSION | SERIALIZE_TRANSACTION_NO_WITNESS)) -CBlockHeaderAndShortTxIDs::CBlockHeaderAndShortTxIDs(const CBlock& block) : +CBlockHeaderAndShortTxIDs::CBlockHeaderAndShortTxIDs(const CBlock& block, bool fUseWTXID) : nonce(GetRand(std::numeric_limits::max())), shorttxids(block.vtx.size() - 1), prefilledtxn(1), header(block) { FillShortTxIDSelector(); @@ -25,7 +25,7 @@ CBlockHeaderAndShortTxIDs::CBlockHeaderAndShortTxIDs(const CBlock& block) : prefilledtxn[0] = {0, block.vtx[0]}; for (size_t i = 1; i < block.vtx.size(); i++) { const CTransaction& tx = block.vtx[i]; - shorttxids[i - 1] = GetShortID(tx.GetHash()); + shorttxids[i - 1] = GetShortID(fUseWTXID ? tx.GetWitnessHash() : tx.GetHash()); } } -- cgit v1.2.3 From 88c35491ab19f9afdf9b3fa9356a072f70ef2f55 Mon Sep 17 00:00:00 2001 From: Suhas Daftuar Date: Mon, 31 Oct 2016 10:03:49 -0400 Subject: Fix compact block handling to not ban if block is invalid --- src/blockencodings.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/blockencodings.cpp') diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp index 93d3fa372..737102f16 100644 --- a/src/blockencodings.cpp +++ b/src/blockencodings.cpp @@ -167,7 +167,7 @@ ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector< // check its own merkle root and cache that check. if (state.CorruptionPossible()) return READ_STATUS_FAILED; // Possible Short ID collision - return READ_STATUS_INVALID; + return READ_STATUS_CHECKBLOCK_FAILED; } LogPrint("cmpctblock", "Successfully reconstructed block %s with %lu txn prefilled, %lu txn from mempool and %lu txn requested\n", header.GetHash().ToString(), prefilled_count, mempool_count, vtx_missing.size()); -- cgit v1.2.3 From 657e05ab2e87ff725723fe8a375fc3f8aad02126 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Fri, 28 Oct 2016 16:51:33 -0700 Subject: Make GetSerializeSize a wrapper on top of CSizeComputer Given that in default GetSerializeSize implementations created by ADD_SERIALIZE_METHODS we're already using CSizeComputer(), get rid of the specialized GetSerializeSize methods everywhere, and just use CSizeComputer. This removes a lot of code which isn't actually used anywhere. For CCompactSize and CVarInt this actually removes a more efficient size computing algorithm, which is brought back in a later commit. --- src/blockencodings.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/blockencodings.cpp') diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp index 93d3fa372..bde8463b3 100644 --- a/src/blockencodings.cpp +++ b/src/blockencodings.cpp @@ -131,7 +131,7 @@ ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& c break; } - LogPrint("cmpctblock", "Initialized PartiallyDownloadedBlock for block %s using a cmpctblock of size %lu\n", cmpctblock.header.GetHash().ToString(), cmpctblock.GetSerializeSize(SER_NETWORK, PROTOCOL_VERSION)); + LogPrint("cmpctblock", "Initialized PartiallyDownloadedBlock for block %s using a cmpctblock of size %lu\n", cmpctblock.header.GetHash().ToString(), GetSerializeSize(cmpctblock, SER_NETWORK, PROTOCOL_VERSION)); return READ_STATUS_OK; } -- cgit v1.2.3 From 1662b437b33b7ec5a1723f6ae6187d3bdd06f593 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Thu, 10 Nov 2016 17:26:00 -0800 Subject: Make CBlock::vtx a vector of shared_ptr --- src/blockencodings.cpp | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) (limited to 'src/blockencodings.cpp') diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp index dbed90583..fac52474e 100644 --- a/src/blockencodings.cpp +++ b/src/blockencodings.cpp @@ -24,7 +24,7 @@ CBlockHeaderAndShortTxIDs::CBlockHeaderAndShortTxIDs(const CBlock& block, bool f //TODO: Use our mempool prior to block acceptance to predictively fill more than just the coinbase prefilledtxn[0] = {0, block.vtx[0]}; 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(fUseWTXID ? tx.GetWitnessHash() : tx.GetHash()); } } @@ -59,7 +59,7 @@ ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& c int32_t lastprefilledindex = -1; for (size_t i = 0; i < cmpctblock.prefilledtxn.size(); i++) { - if (cmpctblock.prefilledtxn[i].tx.IsNull()) + if (cmpctblock.prefilledtxn[i].tx->IsNull()) return READ_STATUS_INVALID; lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1; //index is a uint16_t, so cant overflow here @@ -71,7 +71,7 @@ ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& c // have neither a prefilled txn or a shorttxid! return READ_STATUS_INVALID; } - txn_available[lastprefilledindex] = std::make_shared(cmpctblock.prefilledtxn[i].tx); + txn_available[lastprefilledindex] = cmpctblock.prefilledtxn[i].tx; } prefilled_count = cmpctblock.prefilledtxn.size(); @@ -142,7 +142,7 @@ bool PartiallyDownloadedBlock::IsTxAvailable(size_t index) const { return txn_available[index] ? true : false; } -ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector& vtx_missing) const { +ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector>& vtx_missing) const { assert(!header.IsNull()); block = header; block.vtx.resize(txn_available.size()); @@ -154,7 +154,7 @@ ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector< return READ_STATUS_INVALID; block.vtx[i] = vtx_missing[tx_missing_offset++]; } else - block.vtx[i] = *txn_available[i]; + block.vtx[i] = txn_available[i]; } if (vtx_missing.size() != tx_missing_offset) return READ_STATUS_INVALID; @@ -172,8 +172,8 @@ ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector< LogPrint("cmpctblock", "Successfully reconstructed block %s with %lu txn prefilled, %lu txn from mempool and %lu txn requested\n", header.GetHash().ToString(), prefilled_count, mempool_count, vtx_missing.size()); if (vtx_missing.size() < 5) { - for(const CTransaction& tx : vtx_missing) - LogPrint("cmpctblock", "Reconstructed block %s required tx %s\n", header.GetHash().ToString(), tx.GetHash().ToString()); + for (const auto& tx : vtx_missing) + LogPrint("cmpctblock", "Reconstructed block %s required tx %s\n", header.GetHash().ToString(), tx->GetHash().ToString()); } return READ_STATUS_OK; -- cgit v1.2.3 From b4e4ba475a5679e09f279aaf2a83dcf93c632bdb Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Thu, 10 Nov 2016 17:34:17 -0800 Subject: Introduce convenience type CTransactionRef --- src/blockencodings.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/blockencodings.cpp') diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp index fac52474e..f14ae1c41 100644 --- a/src/blockencodings.cpp +++ b/src/blockencodings.cpp @@ -142,7 +142,7 @@ bool PartiallyDownloadedBlock::IsTxAvailable(size_t index) const { return txn_available[index] ? true : false; } -ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector>& vtx_missing) const { +ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector& vtx_missing) const { assert(!header.IsNull()); block = header; block.vtx.resize(txn_available.size()); -- cgit v1.2.3 From 15fa95d7e576041a20d47907356a2be5a327b4ca Mon Sep 17 00:00:00 2001 From: fsb4000 Date: Mon, 28 Nov 2016 15:19:05 +0700 Subject: Fix some typos --- src/blockencodings.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/blockencodings.cpp') diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp index f14ae1c41..2efeda9cc 100644 --- a/src/blockencodings.cpp +++ b/src/blockencodings.cpp @@ -62,7 +62,7 @@ ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& c if (cmpctblock.prefilledtxn[i].tx->IsNull()) return READ_STATUS_INVALID; - lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1; //index is a uint16_t, so cant overflow here + lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1; //index is a uint16_t, so can't overflow here if (lastprefilledindex > std::numeric_limits::max()) return READ_STATUS_INVALID; if ((uint32_t)lastprefilledindex > cmpctblock.shorttxids.size() + i) { -- cgit v1.2.3 From 76faa3cdfedbd3fc91be4ecfff77fc6dc18134fb Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Thu, 1 Dec 2016 16:06:41 -0800 Subject: Rename the remaining main.{h,cpp} to validation.{h,cpp} --- src/blockencodings.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/blockencodings.cpp') diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp index 2efeda9cc..914af0c67 100644 --- a/src/blockencodings.cpp +++ b/src/blockencodings.cpp @@ -10,7 +10,7 @@ #include "random.h" #include "streams.h" #include "txmempool.h" -#include "main.h" +#include "validation.h" #include "util.h" #include -- cgit v1.2.3 From 6713f0f142d97b4608c95a3ea03b4b670fceab2b Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Fri, 11 Nov 2016 13:01:27 -0800 Subject: Make FillBlock consume txn_available to avoid shared_ptr copies --- src/blockencodings.cpp | 14 ++++++++++---- 1 file changed, 10 insertions(+), 4 deletions(-) (limited to 'src/blockencodings.cpp') diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp index 914af0c67..72fe17bdc 100644 --- a/src/blockencodings.cpp +++ b/src/blockencodings.cpp @@ -142,8 +142,9 @@ bool PartiallyDownloadedBlock::IsTxAvailable(size_t index) const { return txn_available[index] ? true : false; } -ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector& vtx_missing) const { +ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector& vtx_missing) { assert(!header.IsNull()); + uint256 hash = header.GetHash(); block = header; block.vtx.resize(txn_available.size()); @@ -154,8 +155,13 @@ ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector< return READ_STATUS_INVALID; block.vtx[i] = vtx_missing[tx_missing_offset++]; } else - block.vtx[i] = txn_available[i]; + block.vtx[i] = std::move(txn_available[i]); } + + // Make sure we can't call FillBlock again. + header.SetNull(); + txn_available.clear(); + if (vtx_missing.size() != tx_missing_offset) return READ_STATUS_INVALID; @@ -170,10 +176,10 @@ ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector< return READ_STATUS_CHECKBLOCK_FAILED; } - LogPrint("cmpctblock", "Successfully reconstructed block %s with %lu txn prefilled, %lu txn from mempool and %lu txn requested\n", header.GetHash().ToString(), prefilled_count, mempool_count, vtx_missing.size()); + LogPrint("cmpctblock", "Successfully reconstructed block %s with %lu txn prefilled, %lu txn from mempool and %lu txn requested\n", hash.ToString(), prefilled_count, mempool_count, vtx_missing.size()); if (vtx_missing.size() < 5) { for (const auto& tx : vtx_missing) - LogPrint("cmpctblock", "Reconstructed block %s required tx %s\n", header.GetHash().ToString(), tx->GetHash().ToString()); + LogPrint("cmpctblock", "Reconstructed block %s required tx %s\n", hash.ToString(), tx->GetHash().ToString()); } return READ_STATUS_OK; -- cgit v1.2.3 From 93380c5247526e2248248a7d539233ec48d11bdd Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Sun, 4 Dec 2016 20:44:37 -0800 Subject: Use replaced transactions in compact block reconstruction --- src/blockencodings.cpp | 32 +++++++++++++++++++++++++++++++- 1 file changed, 31 insertions(+), 1 deletion(-) (limited to 'src/blockencodings.cpp') diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp index 72fe17bdc..43b4cb9b8 100644 --- a/src/blockencodings.cpp +++ b/src/blockencodings.cpp @@ -47,7 +47,7 @@ uint64_t CBlockHeaderAndShortTxIDs::GetShortID(const uint256& txhash) const { -ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& cmpctblock) { +ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& cmpctblock, std::vector>& extra_txn) { if (cmpctblock.header.IsNull() || (cmpctblock.shorttxids.empty() && cmpctblock.prefilledtxn.empty())) return READ_STATUS_INVALID; if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > MAX_BLOCK_BASE_SIZE / MIN_TRANSACTION_BASE_SIZE) @@ -104,6 +104,7 @@ ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& c return READ_STATUS_FAILED; // Short ID collision std::vector have_txn(txn_available.size()); + { LOCK(pool->cs); const std::vector >& vTxHashes = pool->vTxHashes; for (size_t i = 0; i < vTxHashes.size(); i++) { @@ -130,6 +131,35 @@ ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& c if (mempool_count == shorttxids.size()) break; } + } + + for (size_t i = 0; i < extra_txn.size(); i++) { + uint64_t shortid = cmpctblock.GetShortID(extra_txn[i].first); + std::unordered_map::iterator idit = shorttxids.find(shortid); + if (idit != shorttxids.end()) { + if (!have_txn[idit->second]) { + txn_available[idit->second] = extra_txn[i].second; + 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 + // Note that we dont want duplication between extra_txn and mempool to + // trigger this case, so we compare witness hashes first + if (txn_available[idit->second] && + txn_available[idit->second]->GetWitnessHash() != extra_txn[i].second->GetWitnessHash()) { + txn_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; + } LogPrint("cmpctblock", "Initialized PartiallyDownloadedBlock for block %s using a cmpctblock of size %lu\n", cmpctblock.header.GetHash().ToString(), GetSerializeSize(cmpctblock, SER_NETWORK, PROTOCOL_VERSION)); -- cgit v1.2.3 From b55b4163462756cbb2341294b839a881333d8f1e Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Thu, 12 Jan 2017 12:19:14 -0800 Subject: Add extra_count lower bound to compact reconstruction debug print --- src/blockencodings.cpp | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'src/blockencodings.cpp') diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp index 43b4cb9b8..c27cde216 100644 --- a/src/blockencodings.cpp +++ b/src/blockencodings.cpp @@ -141,6 +141,7 @@ ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& c txn_available[idit->second] = extra_txn[i].second; have_txn[idit->second] = true; mempool_count++; + extra_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, @@ -151,6 +152,7 @@ ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& c txn_available[idit->second]->GetWitnessHash() != extra_txn[i].second->GetWitnessHash()) { txn_available[idit->second].reset(); mempool_count--; + extra_count--; } } } @@ -206,7 +208,7 @@ ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector< return READ_STATUS_CHECKBLOCK_FAILED; } - LogPrint("cmpctblock", "Successfully reconstructed block %s with %lu txn prefilled, %lu txn from mempool and %lu txn requested\n", hash.ToString(), prefilled_count, mempool_count, vtx_missing.size()); + LogPrint("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()); if (vtx_missing.size() < 5) { for (const auto& tx : vtx_missing) LogPrint("cmpctblock", "Reconstructed block %s required tx %s\n", hash.ToString(), tx->GetHash().ToString()); -- cgit v1.2.3 From fac4c78028d132ee7becc1dc54a0c881ae1a0287 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Thu, 12 Jan 2017 12:20:11 -0800 Subject: Make PartiallyDownloadedBlock::InitData's second param const --- src/blockencodings.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/blockencodings.cpp') diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp index c27cde216..48431cfb3 100644 --- a/src/blockencodings.cpp +++ b/src/blockencodings.cpp @@ -47,7 +47,7 @@ uint64_t CBlockHeaderAndShortTxIDs::GetShortID(const uint256& txhash) const { -ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& cmpctblock, std::vector>& extra_txn) { +ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& cmpctblock, const std::vector>& extra_txn) { if (cmpctblock.header.IsNull() || (cmpctblock.shorttxids.empty() && cmpctblock.prefilledtxn.empty())) return READ_STATUS_INVALID; if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > MAX_BLOCK_BASE_SIZE / MIN_TRANSACTION_BASE_SIZE) -- cgit v1.2.3 From 1ccfe9b1c93460e3d345948c3740cfeca45e2ee3 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Mon, 16 Jan 2017 22:58:06 -0500 Subject: Clarify comment about mempool/extra conflicts --- src/blockencodings.cpp | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'src/blockencodings.cpp') diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp index 48431cfb3..4a311cbba 100644 --- a/src/blockencodings.cpp +++ b/src/blockencodings.cpp @@ -143,7 +143,8 @@ ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& c mempool_count++; extra_count++; } else { - // If we find two mempool txn that match the short id, just request it. + // 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 dont want duplication between extra_txn and mempool to -- cgit v1.2.3 From 1be681a1b97b686f838af90682a57f2030d26015 Mon Sep 17 00:00:00 2001 From: Ross Nicoll Date: Thu, 28 Dec 2017 15:04:08 +0000 Subject: Modify chain consensus parameters to be height aware (#1396) * Modify chain consensus parameters to be height aware * Correct implementation of simplified rewards in parameters * Correct max money * Use base block version in IsSuperMajority() instead of full version * Correct mining of blocks in AuxPoW tests * Add in missing pre-AuxPoW consensus checks --- src/blockencodings.cpp | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'src/blockencodings.cpp') diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp index 4a311cbba..ef27877c6 100644 --- a/src/blockencodings.cpp +++ b/src/blockencodings.cpp @@ -199,7 +199,8 @@ ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector< return READ_STATUS_INVALID; CValidationState state; - if (!CheckBlock(block, state, Params().GetConsensus())) { + // TODO: Make sure lack of block height doesn't cause verification problems + if (!CheckBlock(block, state)) { // TODO: We really want to just check merkle tree manually here, // but that is expensive, and CheckBlock caches a block's // "checked-status" (in the CBlock?). CBlock should be able to -- cgit v1.2.3