blockfilter.cpp
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 #include <mutex> 6 #include <set> 7 #include <string_view> 8 9 #include <blockfilter.h> 10 #include <crypto/siphash.h> 11 #include <hash.h> 12 #include <primitives/block.h> 13 #include <primitives/transaction.h> 14 #include <script/script.h> 15 #include <streams.h> 16 #include <undo.h> 17 #include <util/golombrice.h> 18 #include <util/string.h> 19 20 using util::Join; 21 22 static const std::map<BlockFilterType, std::string> g_filter_types = { 23 {BlockFilterType::BASIC, "basic"}, 24 }; 25 26 uint64_t GCSFilter::HashToRange(const Element& element) const 27 { 28 uint64_t hash = CSipHasher(m_params.m_siphash_k0, m_params.m_siphash_k1) 29 .Write(element) 30 .Finalize(); 31 return FastRange64(hash, m_F); 32 } 33 34 std::vector<uint64_t> GCSFilter::BuildHashedSet(const ElementSet& elements) const 35 { 36 std::vector<uint64_t> hashed_elements; 37 hashed_elements.reserve(elements.size()); 38 for (const Element& element : elements) { 39 hashed_elements.push_back(HashToRange(element)); 40 } 41 std::sort(hashed_elements.begin(), hashed_elements.end()); 42 return hashed_elements; 43 } 44 45 GCSFilter::GCSFilter(const Params& params) 46 : m_params(params), m_N(0), m_F(0), m_encoded{0} 47 {} 48 49 GCSFilter::GCSFilter(const Params& params, std::vector<unsigned char> encoded_filter, bool skip_decode_check) 50 : m_params(params), m_encoded(std::move(encoded_filter)) 51 { 52 SpanReader stream{m_encoded}; 53 54 uint64_t N = ReadCompactSize(stream); 55 m_N = static_cast<uint32_t>(N); 56 if (m_N != N) { 57 throw std::ios_base::failure("N must be <2^32"); 58 } 59 m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M); 60 61 if (skip_decode_check) return; 62 63 // Verify that the encoded filter contains exactly N elements. If it has too much or too little 64 // data, a std::ios_base::failure exception will be raised. 65 BitStreamReader bitreader{stream}; 66 for (uint64_t i = 0; i < m_N; ++i) { 67 GolombRiceDecode(bitreader, m_params.m_P); 68 } 69 if (!stream.empty()) { 70 throw std::ios_base::failure("encoded_filter contains excess data"); 71 } 72 } 73 74 GCSFilter::GCSFilter(const Params& params, const ElementSet& elements) 75 : m_params(params) 76 { 77 size_t N = elements.size(); 78 m_N = static_cast<uint32_t>(N); 79 if (m_N != N) { 80 throw std::invalid_argument("N must be <2^32"); 81 } 82 m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M); 83 84 VectorWriter stream{m_encoded, 0}; 85 86 WriteCompactSize(stream, m_N); 87 88 if (elements.empty()) { 89 return; 90 } 91 92 BitStreamWriter bitwriter{stream}; 93 94 uint64_t last_value = 0; 95 for (uint64_t value : BuildHashedSet(elements)) { 96 uint64_t delta = value - last_value; 97 GolombRiceEncode(bitwriter, m_params.m_P, delta); 98 last_value = value; 99 } 100 101 bitwriter.Flush(); 102 } 103 104 bool GCSFilter::MatchInternal(const uint64_t* element_hashes, size_t size) const 105 { 106 SpanReader stream{m_encoded}; 107 108 // Seek forward by size of N 109 uint64_t N = ReadCompactSize(stream); 110 assert(N == m_N); 111 112 BitStreamReader bitreader{stream}; 113 114 uint64_t value = 0; 115 size_t hashes_index = 0; 116 for (uint32_t i = 0; i < m_N; ++i) { 117 uint64_t delta = GolombRiceDecode(bitreader, m_params.m_P); 118 value += delta; 119 120 while (true) { 121 if (hashes_index == size) { 122 return false; 123 } else if (element_hashes[hashes_index] == value) { 124 return true; 125 } else if (element_hashes[hashes_index] > value) { 126 break; 127 } 128 129 hashes_index++; 130 } 131 } 132 133 return false; 134 } 135 136 bool GCSFilter::Match(const Element& element) const 137 { 138 uint64_t query = HashToRange(element); 139 return MatchInternal(&query, 1); 140 } 141 142 bool GCSFilter::MatchAny(const ElementSet& elements) const 143 { 144 const std::vector<uint64_t> queries = BuildHashedSet(elements); 145 return MatchInternal(queries.data(), queries.size()); 146 } 147 148 const std::string& BlockFilterTypeName(BlockFilterType filter_type) 149 { 150 static std::string unknown_retval; 151 auto it = g_filter_types.find(filter_type); 152 return it != g_filter_types.end() ? it->second : unknown_retval; 153 } 154 155 bool BlockFilterTypeByName(std::string_view name, BlockFilterType& filter_type) 156 { 157 for (const auto& entry : g_filter_types) { 158 if (entry.second == name) { 159 filter_type = entry.first; 160 return true; 161 } 162 } 163 return false; 164 } 165 166 const std::set<BlockFilterType>& AllBlockFilterTypes() 167 { 168 static std::set<BlockFilterType> types; 169 170 static std::once_flag flag; 171 std::call_once(flag, []() { 172 for (const auto& entry : g_filter_types) { 173 types.insert(entry.first); 174 } 175 }); 176 177 return types; 178 } 179 180 const std::string& ListBlockFilterTypes() 181 { 182 static std::string type_list{Join(g_filter_types, ", ", [](const auto& entry) { return entry.second; })}; 183 184 return type_list; 185 } 186 187 static GCSFilter::ElementSet BasicFilterElements(const CBlock& block, 188 const CBlockUndo& block_undo) 189 { 190 GCSFilter::ElementSet elements; 191 192 for (const CTransactionRef& tx : block.vtx) { 193 for (const CTxOut& txout : tx->vout) { 194 const CScript& script = txout.scriptPubKey; 195 if (script.empty() || script[0] == OP_RETURN) continue; 196 elements.emplace(script.begin(), script.end()); 197 } 198 } 199 200 for (const CTxUndo& tx_undo : block_undo.vtxundo) { 201 for (const Coin& prevout : tx_undo.vprevout) { 202 const CScript& script = prevout.out.scriptPubKey; 203 if (script.empty()) continue; 204 elements.emplace(script.begin(), script.end()); 205 } 206 } 207 208 return elements; 209 } 210 211 BlockFilter::BlockFilter(BlockFilterType filter_type, const uint256& block_hash, 212 std::vector<unsigned char> filter, bool skip_decode_check) 213 : m_filter_type(filter_type), m_block_hash(block_hash) 214 { 215 GCSFilter::Params params; 216 if (!BuildParams(params)) { 217 throw std::invalid_argument("unknown filter_type"); 218 } 219 m_filter = GCSFilter(params, std::move(filter), skip_decode_check); 220 } 221 222 BlockFilter::BlockFilter(BlockFilterType filter_type, const CBlock& block, const CBlockUndo& block_undo) 223 : m_filter_type(filter_type), m_block_hash(block.GetHash()) 224 { 225 GCSFilter::Params params; 226 if (!BuildParams(params)) { 227 throw std::invalid_argument("unknown filter_type"); 228 } 229 m_filter = GCSFilter(params, BasicFilterElements(block, block_undo)); 230 } 231 232 bool BlockFilter::BuildParams(GCSFilter::Params& params) const 233 { 234 switch (m_filter_type) { 235 case BlockFilterType::BASIC: 236 params.m_siphash_k0 = m_block_hash.GetUint64(0); 237 params.m_siphash_k1 = m_block_hash.GetUint64(1); 238 params.m_P = BASIC_FILTER_P; 239 params.m_M = BASIC_FILTER_M; 240 return true; 241 case BlockFilterType::INVALID: 242 return false; 243 } 244 245 return false; 246 } 247 248 uint256 BlockFilter::GetHash() const 249 { 250 return Hash(GetEncodedFilter()); 251 } 252 253 uint256 BlockFilter::ComputeHeader(const uint256& prev_header) const 254 { 255 return Hash(GetHash(), prev_header); 256 }