git / moonbite-core / src/blockfilter.h · raw

// Copyright (c) 2018-2019 The Bitcoin Core developers// Distributed under the MIT software license, see the accompanying// file COPYING or http://www.opensource.org/licenses/mit-license.php.#ifndef BITCOIN_BLOCKFILTER_H#define BITCOIN_BLOCKFILTER_H#include <stdint.h>#include <string>#include <set>#include <unordered_set>#include <vector>#include <primitives/block.h>#include <serialize.h>#include <uint256.h>#include <undo.h>#include <util/bytevectorhash.h>/** * This implements a Golomb-coded set as defined in BIP 158. It is a * compact, probabilistic data structure for testing set membership. */class GCSFilter{public:    typedef std::vector<unsigned char> Element;    typedef std::unordered_set<Element, ByteVectorHash> ElementSet;    struct Params    {        uint64_t m_siphash_k0;        uint64_t m_siphash_k1;        uint8_t m_P;  //!< Golomb-Rice coding parameter        uint32_t m_M;  //!< Inverse false positive rate        Params(uint64_t siphash_k0 = 0, uint64_t siphash_k1 = 0, uint8_t P = 0, uint32_t M = 1)            : m_siphash_k0(siphash_k0), m_siphash_k1(siphash_k1), m_P(P), m_M(M)        {}    };private:    Params m_params;    uint32_t m_N;  //!< Number of elements in the filter    uint64_t m_F;  //!< Range of element hashes, F = N * M    std::vector<unsigned char> m_encoded;    /** Hash a data element to an integer in the range [0, N * M). */    uint64_t HashToRange(const Element& element) const;    std::vector<uint64_t> BuildHashedSet(const ElementSet& elements) const;    /** Helper method used to implement Match and MatchAny */    bool MatchInternal(const uint64_t* sorted_element_hashes, size_t size) const;public:    /** Constructs an empty filter. */    explicit GCSFilter(const Params& params = Params());    /** Reconstructs an already-created filter from an encoding. */    GCSFilter(const Params& params, std::vector<unsigned char> encoded_filter);    /** Builds a new filter from the params and set of elements. */    GCSFilter(const Params& params, const ElementSet& elements);    uint32_t GetN() const { return m_N; }    const Params& GetParams() const { return m_params; }    const std::vector<unsigned char>& GetEncoded() const { return m_encoded; }    /**     * Checks if the element may be in the set. False positives are possible     * with probability 1/M.     */    bool Match(const Element& element) const;    /**     * Checks if any of the given elements may be in the set. False positives     * are possible with probability 1/M per element checked. This is more     * efficient that checking Match on multiple elements separately.     */    bool MatchAny(const ElementSet& elements) const;};constexpr uint8_t BASIC_FILTER_P = 19;constexpr uint32_t BASIC_FILTER_M = 784931;enum class BlockFilterType : uint8_t{    BASIC = 0,    INVALID = 255,};/** Get the human-readable name for a filter type. Returns empty string for unknown types. */const std::string& BlockFilterTypeName(BlockFilterType filter_type);/** Find a filter type by its human-readable name. */bool BlockFilterTypeByName(const std::string& name, BlockFilterType& filter_type);/** Get a list of known filter types. */const std::set<BlockFilterType>& AllBlockFilterTypes();/** Get a comma-separated list of known filter type names. */const std::string& ListBlockFilterTypes();/** * Complete block filter struct as defined in BIP 157. Serialization matches * payload of "cfilter" messages. */class BlockFilter{private:    BlockFilterType m_filter_type = BlockFilterType::INVALID;    uint256 m_block_hash;    GCSFilter m_filter;    bool BuildParams(GCSFilter::Params& params) const;public:    BlockFilter() = default;    //! Reconstruct a BlockFilter from parts.    BlockFilter(BlockFilterType filter_type, const uint256& block_hash,                std::vector<unsigned char> filter);    //! Construct a new BlockFilter of the specified type from a block.    BlockFilter(BlockFilterType filter_type, const CBlock& block, const CBlockUndo& block_undo);    BlockFilterType GetFilterType() const { return m_filter_type; }    const uint256& GetBlockHash() const { return m_block_hash; }    const GCSFilter& GetFilter() const { return m_filter; }    const std::vector<unsigned char>& GetEncodedFilter() const    {        return m_filter.GetEncoded();    }    //! Compute the filter hash.    uint256 GetHash() const;    //! Compute the filter header given the previous one.    uint256 ComputeHeader(const uint256& prev_header) const;    template <typename Stream>    void Serialize(Stream& s) const {        s << static_cast<uint8_t>(m_filter_type)          << m_block_hash          << m_filter.GetEncoded();    }    template <typename Stream>    void Unserialize(Stream& s) {        std::vector<unsigned char> encoded_filter;        uint8_t filter_type;        s >> filter_type          >> m_block_hash          >> encoded_filter;        m_filter_type = static_cast<BlockFilterType>(filter_type);        GCSFilter::Params params;        if (!BuildParams(params)) {            throw std::ios_base::failure("unknown filter_type");        }        m_filter = GCSFilter(params, std::move(encoded_filter));    }};#endif // BITCOIN_BLOCKFILTER_H