Bitcoin Core  0.20.99
P2P Digital Currency
blockfilter.cpp
Go to the documentation of this file.
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 #include <mutex>
6 #include <sstream>
7 #include <set>
8 
9 #include <blockfilter.h>
10 #include <crypto/siphash.h>
11 #include <hash.h>
12 #include <primitives/transaction.h>
13 #include <script/script.h>
14 #include <streams.h>
15 #include <util/golombrice.h>
16 
18 static constexpr int GCS_SER_TYPE = SER_NETWORK;
19 
21 static constexpr int GCS_SER_VERSION = 0;
22 
23 static const std::map<BlockFilterType, std::string> g_filter_types = {
24  {BlockFilterType::BASIC, "basic"},
25 };
26 
27 // Map a value x that is uniformly distributed in the range [0, 2^64) to a
28 // value uniformly distributed in [0, n) by returning the upper 64 bits of
29 // x * n.
30 //
31 // See: https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
32 static uint64_t MapIntoRange(uint64_t x, uint64_t n)
33 {
34 #ifdef __SIZEOF_INT128__
35  return (static_cast<unsigned __int128>(x) * static_cast<unsigned __int128>(n)) >> 64;
36 #else
37  // To perform the calculation on 64-bit numbers without losing the
38  // result to overflow, split the numbers into the most significant and
39  // least significant 32 bits and perform multiplication piece-wise.
40  //
41  // See: https://stackoverflow.com/a/26855440
42  uint64_t x_hi = x >> 32;
43  uint64_t x_lo = x & 0xFFFFFFFF;
44  uint64_t n_hi = n >> 32;
45  uint64_t n_lo = n & 0xFFFFFFFF;
46 
47  uint64_t ac = x_hi * n_hi;
48  uint64_t ad = x_hi * n_lo;
49  uint64_t bc = x_lo * n_hi;
50  uint64_t bd = x_lo * n_lo;
51 
52  uint64_t mid34 = (bd >> 32) + (bc & 0xFFFFFFFF) + (ad & 0xFFFFFFFF);
53  uint64_t upper64 = ac + (bc >> 32) + (ad >> 32) + (mid34 >> 32);
54  return upper64;
55 #endif
56 }
57 
58 uint64_t GCSFilter::HashToRange(const Element& element) const
59 {
61  .Write(element.data(), element.size())
62  .Finalize();
63  return MapIntoRange(hash, m_F);
64 }
65 
66 std::vector<uint64_t> GCSFilter::BuildHashedSet(const ElementSet& elements) const
67 {
68  std::vector<uint64_t> hashed_elements;
69  hashed_elements.reserve(elements.size());
70  for (const Element& element : elements) {
71  hashed_elements.push_back(HashToRange(element));
72  }
73  std::sort(hashed_elements.begin(), hashed_elements.end());
74  return hashed_elements;
75 }
76 
78  : m_params(params), m_N(0), m_F(0), m_encoded{0}
79 {}
80 
81 GCSFilter::GCSFilter(const Params& params, std::vector<unsigned char> encoded_filter)
82  : m_params(params), m_encoded(std::move(encoded_filter))
83 {
85 
86  uint64_t N = ReadCompactSize(stream);
87  m_N = static_cast<uint32_t>(N);
88  if (m_N != N) {
89  throw std::ios_base::failure("N must be <2^32");
90  }
91  m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M);
92 
93  // Verify that the encoded filter contains exactly N elements. If it has too much or too little
94  // data, a std::ios_base::failure exception will be raised.
95  BitStreamReader<VectorReader> bitreader(stream);
96  for (uint64_t i = 0; i < m_N; ++i) {
97  GolombRiceDecode(bitreader, m_params.m_P);
98  }
99  if (!stream.empty()) {
100  throw std::ios_base::failure("encoded_filter contains excess data");
101  }
102 }
103 
104 GCSFilter::GCSFilter(const Params& params, const ElementSet& elements)
105  : m_params(params)
106 {
107  size_t N = elements.size();
108  m_N = static_cast<uint32_t>(N);
109  if (m_N != N) {
110  throw std::invalid_argument("N must be <2^32");
111  }
112  m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M);
113 
115 
116  WriteCompactSize(stream, m_N);
117 
118  if (elements.empty()) {
119  return;
120  }
121 
122  BitStreamWriter<CVectorWriter> bitwriter(stream);
123 
124  uint64_t last_value = 0;
125  for (uint64_t value : BuildHashedSet(elements)) {
126  uint64_t delta = value - last_value;
127  GolombRiceEncode(bitwriter, m_params.m_P, delta);
128  last_value = value;
129  }
130 
131  bitwriter.Flush();
132 }
133 
134 bool GCSFilter::MatchInternal(const uint64_t* element_hashes, size_t size) const
135 {
137 
138  // Seek forward by size of N
139  uint64_t N = ReadCompactSize(stream);
140  assert(N == m_N);
141 
142  BitStreamReader<VectorReader> bitreader(stream);
143 
144  uint64_t value = 0;
145  size_t hashes_index = 0;
146  for (uint32_t i = 0; i < m_N; ++i) {
147  uint64_t delta = GolombRiceDecode(bitreader, m_params.m_P);
148  value += delta;
149 
150  while (true) {
151  if (hashes_index == size) {
152  return false;
153  } else if (element_hashes[hashes_index] == value) {
154  return true;
155  } else if (element_hashes[hashes_index] > value) {
156  break;
157  }
158 
159  hashes_index++;
160  }
161  }
162 
163  return false;
164 }
165 
166 bool GCSFilter::Match(const Element& element) const
167 {
168  uint64_t query = HashToRange(element);
169  return MatchInternal(&query, 1);
170 }
171 
172 bool GCSFilter::MatchAny(const ElementSet& elements) const
173 {
174  const std::vector<uint64_t> queries = BuildHashedSet(elements);
175  return MatchInternal(queries.data(), queries.size());
176 }
177 
178 const std::string& BlockFilterTypeName(BlockFilterType filter_type)
179 {
180  static std::string unknown_retval = "";
181  auto it = g_filter_types.find(filter_type);
182  return it != g_filter_types.end() ? it->second : unknown_retval;
183 }
184 
185 bool BlockFilterTypeByName(const std::string& name, BlockFilterType& filter_type) {
186  for (const auto& entry : g_filter_types) {
187  if (entry.second == name) {
188  filter_type = entry.first;
189  return true;
190  }
191  }
192  return false;
193 }
194 
195 const std::set<BlockFilterType>& AllBlockFilterTypes()
196 {
197  static std::set<BlockFilterType> types;
198 
199  static std::once_flag flag;
200  std::call_once(flag, []() {
201  for (auto entry : g_filter_types) {
202  types.insert(entry.first);
203  }
204  });
205 
206  return types;
207 }
208 
209 const std::string& ListBlockFilterTypes()
210 {
211  static std::string type_list;
212 
213  static std::once_flag flag;
214  std::call_once(flag, []() {
215  std::stringstream ret;
216  bool first = true;
217  for (auto entry : g_filter_types) {
218  if (!first) ret << ", ";
219  ret << entry.second;
220  first = false;
221  }
222  type_list = ret.str();
223  });
224 
225  return type_list;
226 }
227 
229  const CBlockUndo& block_undo)
230 {
231  GCSFilter::ElementSet elements;
232 
233  for (const CTransactionRef& tx : block.vtx) {
234  for (const CTxOut& txout : tx->vout) {
235  const CScript& script = txout.scriptPubKey;
236  if (script.empty() || script[0] == OP_RETURN) continue;
237  elements.emplace(script.begin(), script.end());
238  }
239  }
240 
241  for (const CTxUndo& tx_undo : block_undo.vtxundo) {
242  for (const Coin& prevout : tx_undo.vprevout) {
243  const CScript& script = prevout.out.scriptPubKey;
244  if (script.empty()) continue;
245  elements.emplace(script.begin(), script.end());
246  }
247  }
248 
249  return elements;
250 }
251 
252 BlockFilter::BlockFilter(BlockFilterType filter_type, const uint256& block_hash,
253  std::vector<unsigned char> filter)
254  : m_filter_type(filter_type), m_block_hash(block_hash)
255 {
256  GCSFilter::Params params;
257  if (!BuildParams(params)) {
258  throw std::invalid_argument("unknown filter_type");
259  }
260  m_filter = GCSFilter(params, std::move(filter));
261 }
262 
263 BlockFilter::BlockFilter(BlockFilterType filter_type, const CBlock& block, const CBlockUndo& block_undo)
264  : m_filter_type(filter_type), m_block_hash(block.GetHash())
265 {
266  GCSFilter::Params params;
267  if (!BuildParams(params)) {
268  throw std::invalid_argument("unknown filter_type");
269  }
270  m_filter = GCSFilter(params, BasicFilterElements(block, block_undo));
271 }
272 
274 {
275  switch (m_filter_type) {
277  params.m_siphash_k0 = m_block_hash.GetUint64(0);
278  params.m_siphash_k1 = m_block_hash.GetUint64(1);
279  params.m_P = BASIC_FILTER_P;
280  params.m_M = BASIC_FILTER_M;
281  return true;
283  return false;
284  }
285 
286  return false;
287 }
288 
290 {
291  const std::vector<unsigned char>& data = GetEncodedFilter();
292 
293  uint256 result;
294  CHash256().Write(data.data(), data.size()).Finalize(result.begin());
295  return result;
296 }
297 
298 uint256 BlockFilter::ComputeHeader(const uint256& prev_header) const
299 {
300  const uint256& filter_hash = GetHash();
301 
302  uint256 result;
303  CHash256()
304  .Write(filter_hash.begin(), filter_hash.size())
305  .Write(prev_header.begin(), prev_header.size())
306  .Finalize(result.begin());
307  return result;
308 }
std::shared_ptr< const CTransaction > CTransactionRef
Definition: transaction.h:387
std::vector< Coin > vprevout
Definition: undo.h:57
BlockFilter()=default
constexpr uint32_t BASIC_FILTER_M
Definition: blockfilter.h:86
CScript scriptPubKey
Definition: transaction.h:124
CSipHasher & Write(uint64_t data)
Hash a 64-bit integer worth of data It is treated as if this was the little-endian interpretation of ...
Definition: siphash.cpp:28
A UTXO entry.
Definition: coins.h:30
Definition: block.h:62
uint64_t ReadCompactSize(Stream &is)
Definition: serialize.h:308
bool BlockFilterTypeByName(const std::string &name, BlockFilterType &filter_type)
Find a filter type by its human-readable name.
void WriteCompactSize(CSizeComputer &os, uint64_t nSize)
Definition: serialize.h:1098
CHash256 & Write(const unsigned char *data, size_t len)
Definition: hash.h:34
CTxOut out
unspent transaction output
Definition: coins.h:34
constexpr uint8_t BASIC_FILTER_P
Definition: blockfilter.h:85
bool MatchAny(const ElementSet &elements) const
Checks if any of the given elements may be in the set.
const std::set< BlockFilterType > & AllBlockFilterTypes()
Get a list of known filter types.
A hasher class for Bitcoin&#39;s 256-bit hash (double SHA-256).
Definition: hash.h:22
std::vector< uint64_t > BuildHashedSet(const ElementSet &elements) const
Definition: blockfilter.cpp:66
GCSFilter m_filter
Definition: blockfilter.h:115
static const std::map< BlockFilterType, std::string > g_filter_types
Definition: blockfilter.cpp:23
unsigned char * begin()
Definition: uint256.h:54
uint256 GetHash() const
Compute the filter hash.
bool Match(const Element &element) const
Checks if the element may be in the set.
GCSFilter(const Params &params=Params())
Constructs an empty filter.
Definition: blockfilter.cpp:77
bool MatchInternal(const uint64_t *sorted_element_hashes, size_t size) const
Helper method used to implement Match and MatchAny.
iterator end()
Definition: prevector.h:292
BlockFilterType
Definition: blockfilter.h:88
uint64_t GolombRiceDecode(BitStreamReader< IStream > &bitreader, uint8_t P)
Definition: golombrice.h:30
const std::vector< unsigned char > & GetEncodedFilter() const
Definition: blockfilter.h:134
const std::string & ListBlockFilterTypes()
Get a comma-separated list of known filter type names.
Minimal stream for reading from an existing vector by reference.
Definition: streams.h:130
const char * name
Definition: rest.cpp:41
uint64_t HashToRange(const Element &element) const
Hash a data element to an integer in the range [0, N * M).
Definition: blockfilter.cpp:58
An output of a transaction.
Definition: transaction.h:120
unsigned int size() const
Definition: uint256.h:74
static GCSFilter::ElementSet BasicFilterElements(const CBlock &block, const CBlockUndo &block_undo)
This implements a Golomb-coded set as defined in BIP 158.
Definition: blockfilter.h:24
void Flush()
Flush any unwritten bits to the output stream, padding with 0&#39;s to the next byte boundary.
Definition: streams.h:582
std::unordered_set< Element, ByteVectorHash > ElementSet
Definition: blockfilter.h:28
uint32_t m_M
Inverse false positive rate.
Definition: blockfilter.h:35
uint256 ComputeHeader(const uint256 &prev_header) const
Compute the filter header given the previous one.
uint64_t m_siphash_k0
Definition: blockfilter.h:32
uint8_t m_P
Golomb-Rice coding parameter.
Definition: blockfilter.h:34
256-bit opaque blob.
Definition: uint256.h:120
std::vector< CTransactionRef > vtx
Definition: block.h:66
static constexpr int GCS_SER_TYPE
SerType used to serialize parameters in GCS filter encoding.
Definition: blockfilter.cpp:18
Undo information for a CBlock.
Definition: undo.h:63
Serialized script, used inside transaction inputs and outputs.
Definition: script.h:390
Undo information for a CTransaction.
Definition: undo.h:53
BlockFilterType m_filter_type
Definition: blockfilter.h:113
bool empty() const
Definition: prevector.h:286
void GolombRiceEncode(BitStreamWriter< OStream > &bitwriter, uint8_t P, uint64_t x)
Definition: golombrice.h:13
SipHash-2-4.
Definition: siphash.h:13
uint256 m_block_hash
Definition: blockfilter.h:114
Params m_params
Definition: blockfilter.h:43
iterator begin()
Definition: prevector.h:290
std::vector< unsigned char > Element
Definition: blockfilter.h:27
bool empty() const
Definition: streams.h:178
static constexpr int GCS_SER_VERSION
Protocol version used to serialize parameters in GCS filter encoding.
Definition: blockfilter.cpp:21
uint64_t m_siphash_k1
Definition: blockfilter.h:33
uint32_t m_N
Number of elements in the filter.
Definition: blockfilter.h:44
auto it
Definition: validation.cpp:380
uint64_t GetUint64(int pos) const
Definition: uint256.h:79
std::vector< CTxUndo > vtxundo
Definition: undo.h:66
uint64_t m_F
Range of element hashes, F = N * M.
Definition: blockfilter.h:45
bool BuildParams(GCSFilter::Params &params) const
std::vector< unsigned char > m_encoded
Definition: blockfilter.h:46
static uint64_t MapIntoRange(uint64_t x, uint64_t n)
Definition: blockfilter.cpp:32
const std::string & BlockFilterTypeName(BlockFilterType filter_type)
Get the human-readable name for a filter type.