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