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