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) m_siphash_k0Params38 : m_siphash_k0(siphash_k0), m_siphash_k1(siphash_k1), m_P(P), m_M(M) 39 {} 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 GetN()67 uint32_t GetN() const { return m_N; } GetParams()68 const Params& GetParams() const { return m_params; } GetEncoded()69 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 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 GetFilterType()130 BlockFilterType GetFilterType() const { return m_filter_type; } GetBlockHash()131 const uint256& GetBlockHash() const { return m_block_hash; } GetFilter()132 const GCSFilter& GetFilter() const { return m_filter; } 133 GetEncodedFilter()134 const std::vector<unsigned char>& GetEncodedFilter() const 135 { 136 return m_filter.GetEncoded(); 137 } 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> Serialize(Stream & s)146 void Serialize(Stream& s) const { 147 s << static_cast<uint8_t>(m_filter_type) 148 << m_block_hash 149 << m_filter.GetEncoded(); 150 } 151 152 template <typename Stream> Unserialize(Stream & s)153 void Unserialize(Stream& s) { 154 std::vector<unsigned char> encoded_filter; 155 uint8_t filter_type; 156 157 s >> filter_type 158 >> m_block_hash 159 >> encoded_filter; 160 161 m_filter_type = static_cast<BlockFilterType>(filter_type); 162 163 GCSFilter::Params params; 164 if (!BuildParams(params)) { 165 throw std::ios_base::failure("unknown filter_type"); 166 } 167 m_filter = GCSFilter(params, std::move(encoded_filter)); 168 } 169 }; 170 171 #endif // BITCOIN_BLOCKFILTER_H 172