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