Line data    Source code

       1             : // Copyright (c) 2018-2022 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             : #ifndef BITCOIN_BLOCKFILTER_H
       6             : #define BITCOIN_BLOCKFILTER_H
       7             : 
       8             : #include <cstddef>
       9             : #include <cstdint>
      10             : #include <ios>
      11             : #include <set>
      12             : #include <string>
      13             : #include <unordered_set>
      14             : #include <utility>
      15             : #include <vector>
      16             : 
      17             : #include <attributes.h>
      18             : #include <uint256.h>
      19             : #include <util/bytevectorhash.h>
      20             : 
      21             : class CBlock;
      22             : class CBlockUndo;
      23             : 
      24             : /**
      25             :  * This implements a Golomb-coded set as defined in BIP 158. It is a
      26             :  * compact, probabilistic data structure for testing set membership.
      27             :  */
      28             : class GCSFilter
      29             : {
      30             : public:
      31             :     typedef std::vector<unsigned char> Element;
      32             :     typedef std::unordered_set<Element, ByteVectorHash> ElementSet;
      33             : 
      34             :     struct Params
      35             :     {
      36             :         uint64_t m_siphash_k0;
      37             :         uint64_t m_siphash_k1;
      38             :         uint8_t m_P;  //!< Golomb-Rice coding parameter
      39             :         uint32_t m_M;  //!< Inverse false positive rate
      40             : 
      41           0 :         Params(uint64_t siphash_k0 = 0, uint64_t siphash_k1 = 0, uint8_t P = 0, uint32_t M = 1)
      42           0 :             : m_siphash_k0(siphash_k0), m_siphash_k1(siphash_k1), m_P(P), m_M(M)
      43           0 :         {}
      44             :     };
      45             : 
      46             : private:
      47             :     Params m_params;
      48             :     uint32_t m_N;  //!< Number of elements in the filter
      49             :     uint64_t m_F;  //!< Range of element hashes, F = N * M
      50             :     std::vector<unsigned char> m_encoded;
      51             : 
      52             :     /** Hash a data element to an integer in the range [0, N * M). */
      53             :     uint64_t HashToRange(const Element& element) const;
      54             : 
      55             :     std::vector<uint64_t> BuildHashedSet(const ElementSet& elements) const;
      56             : 
      57             :     /** Helper method used to implement Match and MatchAny */
      58             :     bool MatchInternal(const uint64_t* sorted_element_hashes, size_t size) const;
      59             : 
      60             : public:
      61             : 
      62             :     /** Constructs an empty filter. */
      63             :     explicit GCSFilter(const Params& params = Params());
      64             : 
      65             :     /** Reconstructs an already-created filter from an encoding. */
      66             :     GCSFilter(const Params& params, std::vector<unsigned char> encoded_filter, bool skip_decode_check);
      67             : 
      68             :     /** Builds a new filter from the params and set of elements. */
      69             :     GCSFilter(const Params& params, const ElementSet& elements);
      70             : 
      71           0 :     uint32_t GetN() const { return m_N; }
      72           0 :     const Params& GetParams() const LIFETIMEBOUND { return m_params; }
      73           0 :     const std::vector<unsigned char>& GetEncoded() const LIFETIMEBOUND { return m_encoded; }
      74             : 
      75             :     /**
      76             :      * Checks if the element may be in the set. False positives are possible
      77             :      * with probability 1/M.
      78             :      */
      79             :     bool Match(const Element& element) const;
      80             : 
      81             :     /**
      82             :      * Checks if any of the given elements may be in the set. False positives
      83             :      * are possible with probability 1/M per element checked. This is more
      84             :      * efficient that checking Match on multiple elements separately.
      85             :      */
      86             :     bool MatchAny(const ElementSet& elements) const;
      87             : };
      88             : 
      89             : constexpr uint8_t BASIC_FILTER_P = 19;
      90             : constexpr uint32_t BASIC_FILTER_M = 784931;
      91             : 
      92             : enum class BlockFilterType : uint8_t
      93             : {
      94             :     BASIC = 0,
      95             :     INVALID = 255,
      96             : };
      97             : 
      98             : /** Get the human-readable name for a filter type. Returns empty string for unknown types. */
      99             : const std::string& BlockFilterTypeName(BlockFilterType filter_type);
     100             : 
     101             : /** Find a filter type by its human-readable name. */
     102             : bool BlockFilterTypeByName(const std::string& name, BlockFilterType& filter_type);
     103             : 
     104             : /** Get a list of known filter types. */
     105             : const std::set<BlockFilterType>& AllBlockFilterTypes();
     106             : 
     107             : /** Get a comma-separated list of known filter type names. */
     108             : const std::string& ListBlockFilterTypes();
     109             : 
     110             : /**
     111             :  * Complete block filter struct as defined in BIP 157. Serialization matches
     112             :  * payload of "cfilter" messages.
     113             :  */
     114             : class BlockFilter
     115             : {
     116             : private:
     117           0 :     BlockFilterType m_filter_type = BlockFilterType::INVALID;
     118             :     uint256 m_block_hash;
     119             :     GCSFilter m_filter;
     120             : 
     121             :     bool BuildParams(GCSFilter::Params& params) const;
     122             : 
     123             : public:
     124             : 
     125           0 :     BlockFilter() = default;
     126             : 
     127             :     //! Reconstruct a BlockFilter from parts.
     128             :     BlockFilter(BlockFilterType filter_type, const uint256& block_hash,
     129             :                 std::vector<unsigned char> filter, bool skip_decode_check);
     130             : 
     131             :     //! Construct a new BlockFilter of the specified type from a block.
     132             :     BlockFilter(BlockFilterType filter_type, const CBlock& block, const CBlockUndo& block_undo);
     133             : 
     134           0 :     BlockFilterType GetFilterType() const { return m_filter_type; }
     135           0 :     const uint256& GetBlockHash() const LIFETIMEBOUND { return m_block_hash; }
     136           0 :     const GCSFilter& GetFilter() const LIFETIMEBOUND { return m_filter; }
     137             : 
     138           0 :     const std::vector<unsigned char>& GetEncodedFilter() const LIFETIMEBOUND
     139             :     {
     140           0 :         return m_filter.GetEncoded();
     141             :     }
     142             : 
     143             :     //! Compute the filter hash.
     144             :     uint256 GetHash() const;
     145             : 
     146             :     //! Compute the filter header given the previous one.
     147             :     uint256 ComputeHeader(const uint256& prev_header) const;
     148             : 
     149             :     template <typename Stream>
     150           0 :     void Serialize(Stream& s) const {
     151           0 :         s << static_cast<uint8_t>(m_filter_type)
     152           0 :           << m_block_hash
     153           0 :           << m_filter.GetEncoded();
     154           0 :     }
     155             : 
     156             :     template <typename Stream>
     157           0 :     void Unserialize(Stream& s) {
     158           0 :         std::vector<unsigned char> encoded_filter;
     159             :         uint8_t filter_type;
     160             : 
     161           0 :         s >> filter_type
     162           0 :           >> m_block_hash
     163           0 :           >> encoded_filter;
     164             : 
     165           0 :         m_filter_type = static_cast<BlockFilterType>(filter_type);
     166             : 
     167           0 :         GCSFilter::Params params;
     168           0 :         if (!BuildParams(params)) {
     169           0 :             throw std::ios_base::failure("unknown filter_type");
     170             :         }
     171           0 :         m_filter = GCSFilter(params, std::move(encoded_filter), /*skip_decode_check=*/false);
     172           0 :     }
     173             : };
     174             : 
     175             : #endif // BITCOIN_BLOCKFILTER_H