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