blockfilter.cpp

Go to the documentation of this file.

// Copyright (c) 2018 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 <blockfilter.h>
 
#include <crypto/siphash.h>
#include <hash.h>
#include <primitives/transaction.h>
#include <script/script.h>
#include <streams.h>
#include <util/fastrange.h>
#include <util/golombrice.h>
 
#include <mutex>
#include <sstream>
 
static constexpr int GCS_SER_TYPE = SER_NETWORK;
 
static constexpr int GCS_SER_VERSION = 0;
 
static const std::map<BlockFilterType, std::string> g_filter_types = {
    {BlockFilterType::BASIC, "basic"},
};
 
uint64_t GCSFilter::HashToRange(const Element &element) const {
    uint64_t hash = CSipHasher(m_params.m_siphash_k0, m_params.m_siphash_k1)
                        .Write(element.data(), element.size())
                        .Finalize();
    return FastRange64(hash, m_F);
}
 
std::vector<uint64_t>
GCSFilter::BuildHashedSet(const ElementSet &elements) const {
    std::vector<uint64_t> hashed_elements;
    hashed_elements.reserve(elements.size());
    for (const Element &element : elements) {
        hashed_elements.push_back(HashToRange(element));
    }
    std::sort(hashed_elements.begin(), hashed_elements.end());
    return hashed_elements;
}
 
GCSFilter::GCSFilter(const Params &params)
    : m_params(params), m_N(0), m_F(0), m_encoded{0} {}
 
GCSFilter::GCSFilter(const Params &params, std::vector<uint8_t> encoded_filter)
    : m_params(params), m_encoded(std::move(encoded_filter)) {
    SpanReader stream{GCS_SER_TYPE, GCS_SER_VERSION, m_encoded};
 
    uint64_t N = ReadCompactSize(stream);
    m_N = static_cast<uint32_t>(N);
    if (m_N != N) {
        throw std::ios_base::failure("N must be <2^32");
    }
    m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M);
 
    // Verify that the encoded filter contains exactly N elements. If it has too
    // much or too little data, a std::ios_base::failure exception will be
    // raised.
    BitStreamReader<SpanReader> bitreader{stream};
    for (uint64_t i = 0; i < m_N; ++i) {
        GolombRiceDecode(bitreader, m_params.m_P);
    }
    if (!stream.empty()) {
        throw std::ios_base::failure("encoded_filter contains excess data");
    }
}
 
GCSFilter::GCSFilter(const Params &params, const ElementSet &elements)
    : m_params(params) {
    size_t N = elements.size();
    m_N = static_cast<uint32_t>(N);
    if (m_N != N) {
        throw std::invalid_argument("N must be <2^32");
    }
    m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M);
 
    CVectorWriter stream(GCS_SER_TYPE, GCS_SER_VERSION, m_encoded, 0);
 
    WriteCompactSize(stream, m_N);
 
    if (elements.empty()) {
        return;
    }
 
    BitStreamWriter<CVectorWriter> bitwriter(stream);
 
    uint64_t last_value = 0;
    for (uint64_t value : BuildHashedSet(elements)) {
        uint64_t delta = value - last_value;
        GolombRiceEncode(bitwriter, m_params.m_P, delta);
        last_value = value;
    }
 
    bitwriter.Flush();
}
 
bool GCSFilter::MatchInternal(const uint64_t *element_hashes,
                              size_t size) const {
    SpanReader stream{GCS_SER_TYPE, GCS_SER_VERSION, m_encoded};
 
    // Seek forward by size of N
    uint64_t N = ReadCompactSize(stream);
    assert(N == m_N);
 
    BitStreamReader<SpanReader> bitreader{stream};
 
    uint64_t value = 0;
    size_t hashes_index = 0;
    for (uint32_t i = 0; i < m_N; ++i) {
        uint64_t delta = GolombRiceDecode(bitreader, m_params.m_P);
        value += delta;
 
        while (true) {
            if (hashes_index == size) {
                return false;
            } else if (element_hashes[hashes_index] == value) {
                return true;
            } else if (element_hashes[hashes_index] > value) {
                break;
            }
 
            hashes_index++;
        }
    }
 
    return false;
}
 
bool GCSFilter::Match(const Element &element) const {
    uint64_t query = HashToRange(element);
    return MatchInternal(&query, 1);
}
 
bool GCSFilter::MatchAny(const ElementSet &elements) const {
    const std::vector<uint64_t> queries = BuildHashedSet(elements);
    return MatchInternal(queries.data(), queries.size());
}
 
const std::string &BlockFilterTypeName(BlockFilterType filter_type) {
    static std::string unknown_retval = "";
    auto it = g_filter_types.find(filter_type);
    return it != g_filter_types.end() ? it->second : unknown_retval;
}
 
bool BlockFilterTypeByName(const std::string &name,
                           BlockFilterType &filter_type) {
    for (const auto &entry : g_filter_types) {
        if (entry.second == name) {
            filter_type = entry.first;
            return true;
        }
    }
    return false;
}
 
const std::set<BlockFilterType> &AllBlockFilterTypes() {
    static std::set<BlockFilterType> types;
 
    static std::once_flag flag;
    std::call_once(flag, []() {
        for (auto entry : g_filter_types) {
            types.insert(entry.first);
        }
    });
 
    return types;
}
 
const std::string &ListBlockFilterTypes() {
    static std::string type_list;
 
    static std::once_flag flag;
    std::call_once(flag, []() {
        std::stringstream ret;
        bool first = true;
        for (auto entry : g_filter_types) {
            if (!first) {
                ret << ", ";
            }
            ret << entry.second;
            first = false;
        }
        type_list = ret.str();
    });
 
    return type_list;
}
 
static GCSFilter::ElementSet BasicFilterElements(const CBlock &block,
                                                 const CBlockUndo &block_undo) {
    GCSFilter::ElementSet elements;
 
    for (const CTransactionRef &tx : block.vtx) {
        for (const CTxOut &txout : tx->vout) {
            const CScript &script = txout.scriptPubKey;
            if (script.empty() || script[0] == OP_RETURN) {
                continue;
            }
            elements.emplace(script.begin(), script.end());
        }
    }
 
    for (const CTxUndo &tx_undo : block_undo.vtxundo) {
        for (const Coin &prevout : tx_undo.vprevout) {
            const CScript &script = prevout.GetTxOut().scriptPubKey;
            if (script.empty()) {
                continue;
            }
            elements.emplace(script.begin(), script.end());
        }
    }
 
    return elements;
}
 
BlockFilter::BlockFilter(BlockFilterType filter_type,
                         const BlockHash &block_hash,
                         std::vector<uint8_t> filter)
    : m_filter_type(filter_type), m_block_hash(block_hash) {
    GCSFilter::Params params;
    if (!BuildParams(params)) {
        throw std::invalid_argument("unknown filter_type");
    }
    m_filter = GCSFilter(params, std::move(filter));
}
 
BlockFilter::BlockFilter(BlockFilterType filter_type, const CBlock &block,
                         const CBlockUndo &block_undo)
    : m_filter_type(filter_type), m_block_hash(block.GetHash()) {
    GCSFilter::Params params;
    if (!BuildParams(params)) {
        throw std::invalid_argument("unknown filter_type");
    }
    m_filter = GCSFilter(params, BasicFilterElements(block, block_undo));
}
 
bool BlockFilter::BuildParams(GCSFilter::Params &params) const {
    switch (m_filter_type) {
        case BlockFilterType::BASIC:
            params.m_siphash_k0 = m_block_hash.GetUint64(0);
            params.m_siphash_k1 = m_block_hash.GetUint64(1);
            params.m_P = BASIC_FILTER_P;
            params.m_M = BASIC_FILTER_M;
            return true;
        case BlockFilterType::INVALID:
            return false;
    }
 
    return false;
}
 
uint256 BlockFilter::GetHash() const {
    const std::vector<uint8_t> &data = GetEncodedFilter();
 
    uint256 result;
    CHash256().Write(data).Finalize(result);
    return result;
}
 
uint256 BlockFilter::ComputeHeader(const uint256 &prev_header) const {
    const uint256 &filter_hash = GetHash();
 
    uint256 result;
    CHash256().Write(filter_hash).Write(prev_header).Finalize(result);
    return result;
}