// Copyright (c) 2016-present 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 <chainparams.h>

#include <common/system.h>

#include <consensus/consensus.h>

#include <consensus/validation.h>

#include <crypto/sha256.h>

#include <crypto/siphash.h>

#include <random.h>

#include <streams.h>

#include <txmempool.h>

#include <util/log.h>

#include <validation.h>

#include <unordered_map>

CBlockHeaderAndShortTxIDs::CBlockHeaderAndShortTxIDs(const CBlock& block, uint64_t nonce)

    : nonce(nonce),

      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++) {

  Branch (29:24): [True: 116k, False: 22.1k]

        const CTransaction& tx = *block.vtx[i];

        shorttxids[i - 1] = GetShortID(tx.GetWitnessHash());

    }

}

void CBlockHeaderAndShortTxIDs::FillShortTxIDSelector() const

{

    DataStream stream{};

    stream << header << nonce;

    CSHA256 hasher;

    hasher.Write((unsigned char*)&(*stream.begin()), stream.end() - stream.begin());

    uint256 shorttxidhash;

    hasher.Finalize(shorttxidhash.begin());

    m_hasher.emplace(shorttxidhash.GetUint64(0), shorttxidhash.GetUint64(1));

}

uint64_t CBlockHeaderAndShortTxIDs::GetShortID(const Wtxid& wtxid) const

{

    static_assert(SHORTTXIDS_LENGTH == 6, "shorttxids calculation assumes 6-byte shorttxids");

    return (*Assert(m_hasher))(wtxid.ToUint256()) & 0xffffffffffffL;

}

/* Reconstructing a compact block is in the hot-path for block relay,

 * so we want to do it as quickly as possible. Because this often

 * involves iterating over the entire mempool, we put all the data we

 * need (ie the wtxid and a reference to the actual transaction data)

 * in a vector and iterate over the vector directly. This allows optimal

 * CPU caching behaviour, at a cost of only 40 bytes per transaction.

 */

ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& cmpctblock, const std::vector<std::pair<Wtxid, CTransactionRef>>& extra_txn)

{

    LogDebug(BCLog::CMPCTBLOCK, "Initializing PartiallyDownloadedBlock for block %s using a cmpctblock of %u bytes\n", cmpctblock.header.GetHash().ToString(), GetSerializeSize(cmpctblock));

    if (cmpctblock.header.IsNull() || (cmpctblock.shorttxids.empty() && cmpctblock.prefilledtxn.empty()))

  Branch (62:9): [True: 18.4E, False: 16.2k]
  Branch (62:40): [True: 5.98k, False: 10.2k]
  Branch (62:73): [True: 0, False: 5.98k]

        return READ_STATUS_INVALID;

    if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > MAX_BLOCK_WEIGHT / MIN_SERIALIZABLE_TRANSACTION_WEIGHT)

  Branch (64:9): [True: 0, False: 16.2k]

        return READ_STATUS_INVALID;

    if (!header.IsNull() || !txn_available.empty()) return READ_STATUS_INVALID;

  Branch (67:9): [True: 18.4E, False: 16.2k]
  Branch (67:29): [True: 0, False: 16.2k]

    header = cmpctblock.header;

    txn_available.resize(cmpctblock.BlockTxCount());

    int32_t lastprefilledindex = -1;

    for (size_t i = 0; i < cmpctblock.prefilledtxn.size(); i++) {

  Branch (73:24): [True: 87.0k, False: 16.2k]

        if (cmpctblock.prefilledtxn[i].tx->IsNull())

  Branch (74:13): [True: 0, False: 87.0k]

            return READ_STATUS_INVALID;

        lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1; //index is a uint16_t, so can't overflow here

        if (lastprefilledindex > std::numeric_limits<uint16_t>::max())

  Branch (78:13): [True: 0, False: 87.0k]

            return READ_STATUS_INVALID;

        if ((uint32_t)lastprefilledindex > cmpctblock.shorttxids.size() + i) {

  Branch (80:13): [True: 0, False: 87.0k]

            // 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] = cmpctblock.prefilledtxn[i].tx;

    }

    prefilled_count = cmpctblock.prefilledtxn.size();

    // 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.

    std::unordered_map<uint64_t, uint16_t> shorttxids(cmpctblock.shorttxids.size());

    uint16_t index_offset = 0;

    for (size_t i = 0; i < cmpctblock.shorttxids.size(); i++) {

  Branch (96:24): [True: 266k, False: 16.2k]

        while (txn_available[i + index_offset])

  Branch (97:16): [True: 75.5k, False: 266k]

            index_offset++;

        shorttxids[cmpctblock.shorttxids[i]] = i + index_offset;

        // 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)

  Branch (110:13): [True: 0, False: 266k]

            return READ_STATUS_FAILED;

    }

    if (shorttxids.size() != cmpctblock.shorttxids.size())

  Branch (113:9): [True: 3.37k, False: 12.8k]

        return READ_STATUS_FAILED; // Short ID collision

    std::vector<bool> have_txn(txn_available.size());

    {

    LOCK(pool->cs);

    for (const auto& [wtxid, txit] : pool->txns_randomized) {

  Branch (119:36): [True: 39.5k, False: 10.2k]

        uint64_t shortid = cmpctblock.GetShortID(wtxid);

        std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);

        if (idit != shorttxids.end()) {

  Branch (122:13): [True: 4.80k, False: 34.7k]

            if (!have_txn[idit->second]) {

  Branch (123:17): [True: 4.80k, False: 0]

                txn_available[idit->second] = txit->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 (txn_available[idit->second]) {

  Branch (131:21): [True: 0, False: 0]

                    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())

  Branch (140:13): [True: 2.59k, False: 36.9k]

            break;

    }

    }

    for (size_t i = 0; i < extra_txn.size(); i++) {

  Branch (145:24): [True: 442k, False: 7.74k]

        uint64_t shortid = cmpctblock.GetShortID(extra_txn[i].first);

        std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);

        if (idit != shorttxids.end()) {

  Branch (148:13): [True: 18.1k, False: 424k]

            if (!have_txn[idit->second]) {

  Branch (149:17): [True: 17.2k, False: 918]

                txn_available[idit->second] = extra_txn[i].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_txn and mempool to

                // trigger this case, so we compare witness hashes first

                if (txn_available[idit->second] &&

  Branch (161:21): [True: 918, False: 0]

                        txn_available[idit->second]->GetWitnessHash() != extra_txn[i].second->GetWitnessHash()) {

  Branch (162:25): [True: 0, False: 918]

                    txn_available[idit->second].reset();

                    mempool_count--;

                    extra_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())

  Branch (172:13): [True: 5.10k, False: 437k]

            break;

    }

    LogDebug(BCLog::CMPCTBLOCK, "Initialized PartiallyDownloadedBlock for block %s using a cmpctblock of %u bytes\n", cmpctblock.header.GetHash().ToString(), GetSerializeSize(cmpctblock));

    return READ_STATUS_OK;

}

bool PartiallyDownloadedBlock::IsTxAvailable(size_t index) const

{

    if (header.IsNull()) return false;

  Branch (183:9): [True: 0, False: 79.8k]

    assert(index < txn_available.size());

  Branch (185:5): [True: 79.8k, False: 0]

    return txn_available[index] != nullptr;

}

ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector<CTransactionRef>& vtx_missing, bool segwit_active)

{

    if (header.IsNull()) return READ_STATUS_INVALID;

  Branch (191:9): [True: 0, False: 9.02k]

    block = header;

    block.vtx.resize(txn_available.size());

    size_t tx_missing_offset = 0;

    for (size_t i = 0; i < txn_available.size(); i++) {

  Branch (197:24): [True: 25.8k, False: 8.71k]

        if (!txn_available[i]) {

  Branch (198:13): [True: 2.18k, False: 23.6k]

            if (tx_missing_offset >= vtx_missing.size()) {

  Branch (199:17): [True: 308, False: 1.88k]

                return READ_STATUS_INVALID;

            }

            block.vtx[i] = vtx_missing[tx_missing_offset++];

        } else {

            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) {

  Branch (212:9): [True: 11, False: 8.70k]

        return READ_STATUS_INVALID;

    }

    // Check for possible mutations early now that we have a seemingly good block

    IsBlockMutatedFn check_mutated{m_check_block_mutated_mock ? m_check_block_mutated_mock : IsBlockMutated};

  Branch (217:36): [True: 0, False: 8.70k]

    if (check_mutated(/*block=*/block, /*check_witness_root=*/segwit_active)) {

  Branch (218:9): [True: 311, False: 8.39k]

        return READ_STATUS_FAILED; // Possible Short ID collision

    }

    if (util::log::ShouldDebugLog(BCLog::CMPCTBLOCK)) {

  Branch (222:9): [True: 8.39k, False: 0]

        const uint256 hash{block.GetHash()};

        uint32_t tx_missing_size{0};

        for (const auto& tx : vtx_missing) tx_missing_size += tx->ComputeTotalSize();

  Branch (225:29): [True: 914, False: 8.39k]

        LogDebug(BCLog::CMPCTBLOCK, "Successfully reconstructed block %s with %u txn prefilled, %u txn from mempool (incl at least %u from extra pool) and %u txn (%u bytes) requested\n", hash.ToString(), prefilled_count, mempool_count, extra_count, vtx_missing.size(), tx_missing_size);

        if (vtx_missing.size() < 5) {

  Branch (227:13): [True: 8.34k, False: 43]

            for (const auto& tx : vtx_missing) {

  Branch (228:33): [True: 231, False: 8.34k]

                LogDebug(BCLog::CMPCTBLOCK, "Reconstructed block %s required tx %s\n", hash.ToString(), tx->GetHash().ToString());

            }

        }

    }

    return READ_STATUS_OK;

}