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

#include <random.h>

#include <streams.h>

#include <txmempool.h>

#include <validation.h>

#include <unordered_map>

CBlockHeaderAndShortTxIDs::CBlockHeaderAndShortTxIDs(const CBlock& block, const 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 (26:24): [True: 0, False: 1.68k]

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

    shorttxidk0 = shorttxidhash.GetUint64(0);

    shorttxidk1 = shorttxidhash.GetUint64(1);

}

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

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

    return SipHashUint256(shorttxidk0, shorttxidk1, wtxid) & 0xffffffffffffL;

}

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

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

  Branch (51:9): [True: 0, False: 0]
  Branch (51:40): [True: 0, False: 0]
  Branch (51:73): [True: 0, False: 0]

        return READ_STATUS_INVALID;

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

  Branch (53:9): [True: 0, False: 0]

        return READ_STATUS_INVALID;

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

  Branch (56:9): [True: 0, False: 0]
  Branch (56:29): [True: 0, False: 0]

    header = cmpctblock.header;

    txn_available.resize(cmpctblock.BlockTxCount());

    int32_t lastprefilledindex = -1;

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

  Branch (62:24): [True: 0, False: 0]

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

  Branch (63:13): [True: 0, False: 0]

            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 (67:13): [True: 0, False: 0]

            return READ_STATUS_INVALID;

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

  Branch (69:13): [True: 0, False: 0]

            // 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 (85:24): [True: 0, False: 0]

        while (txn_available[i + index_offset])

  Branch (86:16): [True: 0, False: 0]

            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 (99:13): [True: 0, False: 0]

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

  Branch (104:9): [True: 0, False: 0]

        return READ_STATUS_FAILED; // Short ID collision

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

    {

    LOCK(pool->cs);

    for (const auto& tx : pool->txns_randomized) {

  Branch (110:25): [True: 0, False: 0]

        uint64_t shortid = cmpctblock.GetShortID(tx->GetWitnessHash());

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

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

  Branch (113:13): [True: 0, False: 0]

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

  Branch (114:17): [True: 0, False: 0]

                txn_available[idit->second] = tx;

                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 (122: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 (131:13): [True: 0, False: 0]

            break;

    }

    }

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

  Branch (136:24): [True: 0, False: 0]

        if (extra_txn[i] == nullptr) {

  Branch (137:13): [True: 0, False: 0]

            continue;

        }

        uint64_t shortid = cmpctblock.GetShortID(extra_txn[i]->GetWitnessHash());

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

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

  Branch (142:13): [True: 0, False: 0]

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

  Branch (143:17): [True: 0, False: 0]

                txn_available[idit->second] = extra_txn[i];

                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 (155:21): [True: 0, False: 0]

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

  Branch (156:25): [True: 0, False: 0]

                    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 (166:13): [True: 0, False: 0]

            break;

    }

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

    return READ_STATUS_OK;

}

bool PartiallyDownloadedBlock::IsTxAvailable(size_t index) const

{

    if (header.IsNull()) return false;

  Branch (177:9): [True: 0, False: 0]

    assert(index < txn_available.size());

    return txn_available[index] != nullptr;

}

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

{

    if (header.IsNull()) return READ_STATUS_INVALID;

  Branch (185:9): [True: 0, False: 0]

    uint256 hash = header.GetHash();

    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 (192:24): [True: 0, False: 0]

        if (!txn_available[i]) {

  Branch (193:13): [True: 0, False: 0]

            if (vtx_missing.size() <= tx_missing_offset)

  Branch (194:17): [True: 0, False: 0]

                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 (205:9): [True: 0, False: 0]

        return READ_STATUS_INVALID;

    BlockValidationState state;

    CheckBlockFn check_block = m_check_block_mock ? m_check_block_mock : CheckBlock;

  Branch (209:32): [True: 0, False: 0]

    if (!check_block(block, state, Params().GetConsensus(), /*fCheckPoW=*/true, /*fCheckMerkleRoot=*/true)) {

  Branch (210:9): [True: 0, False: 0]

        // 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.GetResult() == BlockValidationResult::BLOCK_MUTATED)

  Branch (215:13): [True: 0, False: 0]

            return READ_STATUS_FAILED; // Possible Short ID collision

        return READ_STATUS_CHECKBLOCK_FAILED;

    }

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

    if (vtx_missing.size() < 5) {

  Branch (221:9): [True: 0, False: 0]

        for (const auto& tx : vtx_missing) {

  Branch (222:29): [True: 0, False: 0]

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

        }

    }

    return READ_STATUS_OK;

}