Branch data Line data Source code
# 1 : : // Copyright (c) 2016-2020 The Bitcoin Core developers
# 2 : : // Distributed under the MIT software license, see the accompanying
# 3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
# 4 : :
# 5 : : #include <blockencodings.h>
# 6 : : #include <consensus/consensus.h>
# 7 : : #include <consensus/validation.h>
# 8 : : #include <chainparams.h>
# 9 : : #include <crypto/sha256.h>
# 10 : : #include <crypto/siphash.h>
# 11 : : #include <random.h>
# 12 : : #include <streams.h>
# 13 : : #include <txmempool.h>
# 14 : : #include <validation.h>
# 15 : : #include <util/system.h>
# 16 : :
# 17 : : #include <unordered_map>
# 18 : :
# 19 : : CBlockHeaderAndShortTxIDs::CBlockHeaderAndShortTxIDs(const CBlock& block, bool fUseWTXID) :
# 20 : : nonce(GetRand(std::numeric_limits<uint64_t>::max())),
# 21 : 57245 : shorttxids(block.vtx.size() - 1), prefilledtxn(1), header(block) {
# 22 : 57245 : FillShortTxIDSelector();
# 23 : : //TODO: Use our mempool prior to block acceptance to predictively fill more than just the coinbase
# 24 : 57245 : prefilledtxn[0] = {0, block.vtx[0]};
# 25 [ + + ]: 111665 : for (size_t i = 1; i < block.vtx.size(); i++) {
# 26 : 54420 : const CTransaction& tx = *block.vtx[i];
# 27 [ + + ]: 54420 : shorttxids[i - 1] = GetShortID(fUseWTXID ? tx.GetWitnessHash() : tx.GetHash());
# 28 : 54420 : }
# 29 : 57245 : }
# 30 : :
# 31 : 77994 : void CBlockHeaderAndShortTxIDs::FillShortTxIDSelector() const {
# 32 : 77994 : CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
# 33 : 77994 : stream << header << nonce;
# 34 : 77994 : CSHA256 hasher;
# 35 : 77994 : hasher.Write((unsigned char*)&(*stream.begin()), stream.end() - stream.begin());
# 36 : 77994 : uint256 shorttxidhash;
# 37 : 77994 : hasher.Finalize(shorttxidhash.begin());
# 38 : 77994 : shorttxidk0 = shorttxidhash.GetUint64(0);
# 39 : 77994 : shorttxidk1 = shorttxidhash.GetUint64(1);
# 40 : 77994 : }
# 41 : :
# 42 : 95541 : uint64_t CBlockHeaderAndShortTxIDs::GetShortID(const uint256& txhash) const {
# 43 : 95541 : static_assert(SHORTTXIDS_LENGTH == 6, "shorttxids calculation assumes 6-byte shorttxids");
# 44 : 95541 : return SipHashUint256(shorttxidk0, shorttxidk1, txhash) & 0xffffffffffffL;
# 45 : 95541 : }
# 46 : :
# 47 : :
# 48 : :
# 49 : 16741 : ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& cmpctblock, const std::vector<std::pair<uint256, CTransactionRef>>& extra_txn) {
# 50 [ - + ][ + + ]: 16741 : if (cmpctblock.header.IsNull() || (cmpctblock.shorttxids.empty() && cmpctblock.prefilledtxn.empty()))
# [ - + ]
# 51 : 0 : return READ_STATUS_INVALID;
# 52 [ - + ]: 16741 : if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > MAX_BLOCK_WEIGHT / MIN_SERIALIZABLE_TRANSACTION_WEIGHT)
# 53 : 0 : return READ_STATUS_INVALID;
# 54 : :
# 55 : 16741 : assert(header.IsNull() && txn_available.empty());
# 56 : 16741 : header = cmpctblock.header;
# 57 : 16741 : txn_available.resize(cmpctblock.BlockTxCount());
# 58 : :
# 59 : 16741 : int32_t lastprefilledindex = -1;
# 60 [ + + ]: 33490 : for (size_t i = 0; i < cmpctblock.prefilledtxn.size(); i++) {
# 61 [ - + ]: 16750 : if (cmpctblock.prefilledtxn[i].tx->IsNull())
# 62 : 0 : return READ_STATUS_INVALID;
# 63 : :
# 64 : 16750 : lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1; //index is a uint16_t, so can't overflow here
# 65 [ - + ]: 16750 : if (lastprefilledindex > std::numeric_limits<uint16_t>::max())
# 66 : 0 : return READ_STATUS_INVALID;
# 67 [ + + ]: 16750 : if ((uint32_t)lastprefilledindex > cmpctblock.shorttxids.size() + i) {
# 68 : : // If we are inserting a tx at an index greater than our full list of shorttxids
# 69 : : // plus the number of prefilled txn we've inserted, then we have txn for which we
# 70 : : // have neither a prefilled txn or a shorttxid!
# 71 : 1 : return READ_STATUS_INVALID;
# 72 : 1 : }
# 73 : 16749 : txn_available[lastprefilledindex] = cmpctblock.prefilledtxn[i].tx;
# 74 : 16749 : }
# 75 : 16741 : prefilled_count = cmpctblock.prefilledtxn.size();
# 76 : :
# 77 : : // Calculate map of txids -> positions and check mempool to see what we have (or don't)
# 78 : : // Because well-formed cmpctblock messages will have a (relatively) uniform distribution
# 79 : : // of short IDs, any highly-uneven distribution of elements can be safely treated as a
# 80 : : // READ_STATUS_FAILED.
# 81 : 16740 : std::unordered_map<uint64_t, uint16_t> shorttxids(cmpctblock.shorttxids.size());
# 82 : 16740 : uint16_t index_offset = 0;
# 83 [ + + ]: 31929 : for (size_t i = 0; i < cmpctblock.shorttxids.size(); i++) {
# 84 [ + + ]: 19402 : while (txn_available[i + index_offset])
# 85 : 4213 : index_offset++;
# 86 : 15189 : shorttxids[cmpctblock.shorttxids[i]] = i + index_offset;
# 87 : : // To determine the chance that the number of entries in a bucket exceeds N,
# 88 : : // we use the fact that the number of elements in a single bucket is
# 89 : : // binomially distributed (with n = the number of shorttxids S, and p =
# 90 : : // 1 / the number of buckets), that in the worst case the number of buckets is
# 91 : : // equal to S (due to std::unordered_map having a default load factor of 1.0),
# 92 : : // and that the chance for any bucket to exceed N elements is at most
# 93 : : // buckets * (the chance that any given bucket is above N elements).
# 94 : : // Thus: P(max_elements_per_bucket > N) <= S * (1 - cdf(binomial(n=S,p=1/S), N)).
# 95 : : // If we assume blocks of up to 16000, allowing 12 elements per bucket should
# 96 : : // only fail once per ~1 million block transfers (per peer and connection).
# 97 [ - + ]: 15189 : if (shorttxids.bucket_size(shorttxids.bucket(cmpctblock.shorttxids[i])) > 12)
# 98 : 0 : return READ_STATUS_FAILED;
# 99 : 15189 : }
# 100 : : // TODO: in the shortid-collision case, we should instead request both transactions
# 101 : : // which collided. Falling back to full-block-request here is overkill.
# 102 [ - + ]: 16740 : if (shorttxids.size() != cmpctblock.shorttxids.size())
# 103 : 0 : return READ_STATUS_FAILED; // Short ID collision
# 104 : :
# 105 : 16740 : std::vector<bool> have_txn(txn_available.size());
# 106 : 16740 : {
# 107 : 16740 : LOCK(pool->cs);
# 108 [ + + ]: 47488 : for (size_t i = 0; i < pool->vTxHashes.size(); i++) {
# 109 : 31162 : uint64_t shortid = cmpctblock.GetShortID(pool->vTxHashes[i].first);
# 110 : 31162 : std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
# 111 [ + + ]: 31162 : if (idit != shorttxids.end()) {
# 112 [ + - ]: 9501 : if (!have_txn[idit->second]) {
# 113 : 9501 : txn_available[idit->second] = pool->vTxHashes[i].second->GetSharedTx();
# 114 : 9501 : have_txn[idit->second] = true;
# 115 : 9501 : mempool_count++;
# 116 : 9501 : } else {
# 117 : : // If we find two mempool txn that match the short id, just request it.
# 118 : : // This should be rare enough that the extra bandwidth doesn't matter,
# 119 : : // but eating a round-trip due to FillBlock failure would be annoying
# 120 [ # # ]: 0 : if (txn_available[idit->second]) {
# 121 : 0 : txn_available[idit->second].reset();
# 122 : 0 : mempool_count--;
# 123 : 0 : }
# 124 : 0 : }
# 125 : 9501 : }
# 126 : : // Though ideally we'd continue scanning for the two-txn-match-shortid case,
# 127 : : // the performance win of an early exit here is too good to pass up and worth
# 128 : : // the extra risk.
# 129 [ + + ]: 31162 : if (mempool_count == shorttxids.size())
# 130 : 414 : break;
# 131 : 31162 : }
# 132 : 16740 : }
# 133 : :
# 134 [ + + ]: 26152 : for (size_t i = 0; i < extra_txn.size(); i++) {
# 135 : 9953 : uint64_t shortid = cmpctblock.GetShortID(extra_txn[i].first);
# 136 : 9953 : std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
# 137 [ + + ]: 9953 : if (idit != shorttxids.end()) {
# 138 [ + - ]: 80 : if (!have_txn[idit->second]) {
# 139 : 80 : txn_available[idit->second] = extra_txn[i].second;
# 140 : 80 : have_txn[idit->second] = true;
# 141 : 80 : mempool_count++;
# 142 : 80 : extra_count++;
# 143 : 80 : } else {
# 144 : : // If we find two mempool/extra txn that match the short id, just
# 145 : : // request it.
# 146 : : // This should be rare enough that the extra bandwidth doesn't matter,
# 147 : : // but eating a round-trip due to FillBlock failure would be annoying
# 148 : : // Note that we don't want duplication between extra_txn and mempool to
# 149 : : // trigger this case, so we compare witness hashes first
# 150 [ # # ]: 0 : if (txn_available[idit->second] &&
# 151 [ # # ]: 0 : txn_available[idit->second]->GetWitnessHash() != extra_txn[i].second->GetWitnessHash()) {
# 152 : 0 : txn_available[idit->second].reset();
# 153 : 0 : mempool_count--;
# 154 : 0 : extra_count--;
# 155 : 0 : }
# 156 : 0 : }
# 157 : 80 : }
# 158 : : // Though ideally we'd continue scanning for the two-txn-match-shortid case,
# 159 : : // the performance win of an early exit here is too good to pass up and worth
# 160 : : // the extra risk.
# 161 [ + + ]: 9953 : if (mempool_count == shorttxids.size())
# 162 : 541 : break;
# 163 : 9953 : }
# 164 : :
# 165 [ + - ]: 16740 : LogPrint(BCLog::CMPCTBLOCK, "Initialized PartiallyDownloadedBlock for block %s using a cmpctblock of size %lu\n", cmpctblock.header.GetHash().ToString(), GetSerializeSize(cmpctblock, PROTOCOL_VERSION));
# 166 : :
# 167 : 16740 : return READ_STATUS_OK;
# 168 : 16740 : }
# 169 : :
# 170 : 31769 : bool PartiallyDownloadedBlock::IsTxAvailable(size_t index) const {
# 171 : 31769 : assert(!header.IsNull());
# 172 : 31769 : assert(index < txn_available.size());
# 173 : 31769 : return txn_available[index] != nullptr;
# 174 : 31769 : }
# 175 : :
# 176 : 16745 : ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector<CTransactionRef>& vtx_missing) {
# 177 : 16745 : assert(!header.IsNull());
# 178 : 16745 : uint256 hash = header.GetHash();
# 179 : 16745 : block = header;
# 180 : 16745 : block.vtx.resize(txn_available.size());
# 181 : :
# 182 : 16745 : size_t tx_missing_offset = 0;
# 183 [ + + ]: 48680 : for (size_t i = 0; i < txn_available.size(); i++) {
# 184 [ + + ]: 31944 : if (!txn_available[i]) {
# 185 [ + + ]: 5609 : if (vtx_missing.size() <= tx_missing_offset)
# 186 : 9 : return READ_STATUS_INVALID;
# 187 : 5600 : block.vtx[i] = vtx_missing[tx_missing_offset++];
# 188 : 5600 : } else
# 189 : 26335 : block.vtx[i] = std::move(txn_available[i]);
# 190 : 31944 : }
# 191 : :
# 192 : : // Make sure we can't call FillBlock again.
# 193 : 16745 : header.SetNull();
# 194 : 16736 : txn_available.clear();
# 195 : :
# 196 [ - + ]: 16736 : if (vtx_missing.size() != tx_missing_offset)
# 197 : 0 : return READ_STATUS_INVALID;
# 198 : :
# 199 : 16736 : BlockValidationState state;
# 200 [ + + ]: 16736 : if (!CheckBlock(block, state, Params().GetConsensus())) {
# 201 : : // TODO: We really want to just check merkle tree manually here,
# 202 : : // but that is expensive, and CheckBlock caches a block's
# 203 : : // "checked-status" (in the CBlock?). CBlock should be able to
# 204 : : // check its own merkle root and cache that check.
# 205 [ + - ]: 5 : if (state.GetResult() == BlockValidationResult::BLOCK_MUTATED)
# 206 : 5 : return READ_STATUS_FAILED; // Possible Short ID collision
# 207 : 0 : return READ_STATUS_CHECKBLOCK_FAILED;
# 208 : 0 : }
# 209 : :
# 210 [ + - ]: 16731 : LogPrint(BCLog::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());
# 211 [ + + ]: 16731 : if (vtx_missing.size() < 5) {
# 212 [ + + ]: 16674 : for (const auto& tx : vtx_missing) {
# 213 [ + - ]: 3903 : LogPrint(BCLog::CMPCTBLOCK, "Reconstructed block %s required tx %s\n", hash.ToString(), tx->GetHash().ToString());
# 214 : 3903 : }
# 215 : 16674 : }
# 216 : :
# 217 : 16731 : return READ_STATUS_OK;
# 218 : 16731 : }
|
