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