Bitcoin ABC  0.26.3
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/fastrange.h>
13 #include <util/golombrice.h>
14 
15 #include <mutex>
16 #include <sstream>
17 
19 static constexpr int GCS_SER_TYPE = SER_NETWORK;
20 
22 static constexpr int GCS_SER_VERSION = 0;
23 
24 static const std::map<BlockFilterType, std::string> g_filter_types = {
25  {BlockFilterType::BASIC, "basic"},
26 };
27 
28 uint64_t GCSFilter::HashToRange(const Element &element) const {
30  .Write(element.data(), element.size())
31  .Finalize();
32  return FastRange64(hash, m_F);
33 }
34 
35 std::vector<uint64_t>
37  std::vector<uint64_t> hashed_elements;
38  hashed_elements.reserve(elements.size());
39  for (const Element &element : elements) {
40  hashed_elements.push_back(HashToRange(element));
41  }
42  std::sort(hashed_elements.begin(), hashed_elements.end());
43  return hashed_elements;
44 }
45 
47  : m_params(params), m_N(0), m_F(0), m_encoded{0} {}
48 
49 GCSFilter::GCSFilter(const Params &params, std::vector<uint8_t> encoded_filter)
50  : m_params(params), m_encoded(std::move(encoded_filter)) {
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  // Verify that the encoded filter contains exactly N elements. If it has too
61  // much or too little data, a std::ios_base::failure exception will be
62  // raised.
63  BitStreamReader<SpanReader> bitreader{stream};
64  for (uint64_t i = 0; i < m_N; ++i) {
65  GolombRiceDecode(bitreader, m_params.m_P);
66  }
67  if (!stream.empty()) {
68  throw std::ios_base::failure("encoded_filter contains excess data");
69  }
70 }
71 
73  : m_params(params) {
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 
82 
83  WriteCompactSize(stream, m_N);
84 
85  if (elements.empty()) {
86  return;
87  }
88 
89  BitStreamWriter<CVectorWriter> 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,
102  size_t size) const {
104 
105  // Seek forward by size of N
106  uint64_t N = ReadCompactSize(stream);
107  assert(N == m_N);
108 
109  BitStreamReader<SpanReader> 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  uint64_t query = HashToRange(element);
135  return MatchInternal(&query, 1);
136 }
137 
139  const std::vector<uint64_t> queries = BuildHashedSet(elements);
140  return MatchInternal(queries.data(), queries.size());
141 }
142 
143 const std::string &BlockFilterTypeName(BlockFilterType filter_type) {
144  static std::string unknown_retval = "";
145  auto it = g_filter_types.find(filter_type);
146  return it != g_filter_types.end() ? it->second : unknown_retval;
147 }
148 
149 bool BlockFilterTypeByName(const std::string &name,
150  BlockFilterType &filter_type) {
151  for (const auto &entry : g_filter_types) {
152  if (entry.second == name) {
153  filter_type = entry.first;
154  return true;
155  }
156  }
157  return false;
158 }
159 
160 const std::set<BlockFilterType> &AllBlockFilterTypes() {
161  static std::set<BlockFilterType> types;
162 
163  static std::once_flag flag;
164  std::call_once(flag, []() {
165  for (auto entry : g_filter_types) {
166  types.insert(entry.first);
167  }
168  });
169 
170  return types;
171 }
172 
173 const std::string &ListBlockFilterTypes() {
174  static std::string type_list;
175 
176  static std::once_flag flag;
177  std::call_once(flag, []() {
178  std::stringstream ret;
179  bool first = true;
180  for (auto entry : g_filter_types) {
181  if (!first) {
182  ret << ", ";
183  }
184  ret << entry.second;
185  first = false;
186  }
187  type_list = ret.str();
188  });
189 
190  return type_list;
191 }
192 
194  const CBlockUndo &block_undo) {
196 
197  for (const CTransactionRef &tx : block.vtx) {
198  for (const CTxOut &txout : tx->vout) {
199  const CScript &script = txout.scriptPubKey;
200  if (script.empty() || script[0] == OP_RETURN) {
201  continue;
202  }
203  elements.emplace(script.begin(), script.end());
204  }
205  }
206 
207  for (const CTxUndo &tx_undo : block_undo.vtxundo) {
208  for (const Coin &prevout : tx_undo.vprevout) {
209  const CScript &script = prevout.GetTxOut().scriptPubKey;
210  if (script.empty()) {
211  continue;
212  }
213  elements.emplace(script.begin(), script.end());
214  }
215  }
216 
217  return elements;
218 }
219 
221  const BlockHash &block_hash,
222  std::vector<uint8_t> filter)
223  : m_filter_type(filter_type), m_block_hash(block_hash) {
224  GCSFilter::Params params;
225  if (!BuildParams(params)) {
226  throw std::invalid_argument("unknown filter_type");
227  }
228  m_filter = GCSFilter(params, std::move(filter));
229 }
230 
232  const CBlockUndo &block_undo)
233  : m_filter_type(filter_type), m_block_hash(block.GetHash()) {
234  GCSFilter::Params params;
235  if (!BuildParams(params)) {
236  throw std::invalid_argument("unknown filter_type");
237  }
238  m_filter = GCSFilter(params, BasicFilterElements(block, block_undo));
239 }
240 
242  switch (m_filter_type) {
244  params.m_siphash_k0 = m_block_hash.GetUint64(0);
245  params.m_siphash_k1 = m_block_hash.GetUint64(1);
246  params.m_P = BASIC_FILTER_P;
247  params.m_M = BASIC_FILTER_M;
248  return true;
250  return false;
251  }
252 
253  return false;
254 }
255 
257  const std::vector<uint8_t> &data = GetEncodedFilter();
258 
259  uint256 result;
260  CHash256().Write(data).Finalize(result);
261  return result;
262 }
263 
264 uint256 BlockFilter::ComputeHeader(const uint256 &prev_header) const {
265  const uint256 &filter_hash = GetHash();
266 
267  uint256 result;
268  CHash256().Write(filter_hash).Write(prev_header).Finalize(result);
269  return result;
270 }
const std::string & BlockFilterTypeName(BlockFilterType filter_type)
Get the human-readable name for a filter type.
static const std::map< BlockFilterType, std::string > g_filter_types
Definition: blockfilter.cpp:24
static constexpr int GCS_SER_VERSION
Protocol version used to serialize parameters in GCS filter encoding.
Definition: blockfilter.cpp:22
static GCSFilter::ElementSet BasicFilterElements(const CBlock &block, const CBlockUndo &block_undo)
static constexpr int GCS_SER_TYPE
SerType used to serialize parameters in GCS filter encoding.
Definition: blockfilter.cpp:19
const std::string & ListBlockFilterTypes()
Get a comma-separated list of known filter type names.
bool BlockFilterTypeByName(const std::string &name, BlockFilterType &filter_type)
Find a filter type by its human-readable name.
const std::set< BlockFilterType > & AllBlockFilterTypes()
Get a list of known filter types.
BlockFilterType
Definition: blockfilter.h:88
constexpr uint8_t BASIC_FILTER_P
Definition: blockfilter.h:85
constexpr uint32_t BASIC_FILTER_M
Definition: blockfilter.h:86
void Flush()
Flush any unwritten bits to the output stream, padding with 0's to the next byte boundary.
Definition: streams.h:510
GCSFilter m_filter
Definition: blockfilter.h:115
bool BuildParams(GCSFilter::Params &params) const
uint256 ComputeHeader(const uint256 &prev_header) const
Compute the filter header given the previous one.
const std::vector< uint8_t > & GetEncodedFilter() const
Definition: blockfilter.h:134
BlockFilterType m_filter_type
Definition: blockfilter.h:113
BlockHash m_block_hash
Definition: blockfilter.h:114
BlockFilter()=default
uint256 GetHash() const
Compute the filter hash.
Definition: block.h:60
std::vector< CTransactionRef > vtx
Definition: block.h:63
Undo information for a CBlock.
Definition: undo.h:73
std::vector< CTxUndo > vtxundo
Definition: undo.h:76
A hasher class for Bitcoin's 256-bit hash (double SHA-256).
Definition: hash.h:22
void Finalize(Span< uint8_t > output)
Definition: hash.h:29
CHash256 & Write(Span< const uint8_t > input)
Definition: hash.h:36
Serialized script, used inside transaction inputs and outputs.
Definition: script.h:431
SipHash-2-4.
Definition: siphash.h:13
uint64_t Finalize() const
Compute the 64-bit SipHash-2-4 of the data written so far.
Definition: siphash.cpp:82
CSipHasher & Write(uint64_t data)
Hash a 64-bit integer worth of data.
Definition: siphash.cpp:36
An output of a transaction.
Definition: transaction.h:128
CScript scriptPubKey
Definition: transaction.h:131
Restore the UTXO in a Coin at a given COutPoint.
Definition: undo.h:62
std::vector< Coin > vprevout
Definition: undo.h:65
Minimal stream for overwriting and/or appending to an existing byte vector.
Definition: streams.h:65
A UTXO entry.
Definition: coins.h:28
CTxOut & GetTxOut()
Definition: coins.h:49
This implements a Golomb-coded set as defined in BIP 158.
Definition: blockfilter.h:25
uint64_t m_F
Range of element hashes, F = N * M.
Definition: blockfilter.h:45
bool MatchInternal(const uint64_t *sorted_element_hashes, size_t size) const
Helper method used to implement Match and MatchAny.
std::unordered_set< Element, ByteVectorHash > ElementSet
Definition: blockfilter.h:28
uint64_t HashToRange(const Element &element) const
Hash a data element to an integer in the range [0, N * M).
Definition: blockfilter.cpp:28
std::vector< uint8_t > Element
Definition: blockfilter.h:27
uint32_t m_N
Number of elements in the filter.
Definition: blockfilter.h:44
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:46
bool MatchAny(const ElementSet &elements) const
Checks if any of the given elements may be in the set.
std::vector< uint64_t > BuildHashedSet(const ElementSet &elements) const
Definition: blockfilter.cpp:36
Params m_params
Definition: blockfilter.h:43
std::vector< uint8_t > m_encoded
Definition: blockfilter.h:46
Minimal stream for reading from an existing byte array by Span.
Definition: streams.h:129
uint64_t GetUint64(int pos) const
Definition: uint256.h:95
bool empty() const
Definition: prevector.h:388
iterator begin()
Definition: prevector.h:390
iterator end()
Definition: prevector.h:392
256-bit opaque blob.
Definition: uint256.h:129
static uint64_t FastRange64(uint64_t x, uint64_t n)
Fast range reduction with 64-bit input and 64-bit range.
Definition: fastrange.h:27
static uint64_t GolombRiceDecode(BitStreamReader< IStream > &bitreader, uint8_t P)
Definition: golombrice.h:30
static void GolombRiceEncode(BitStreamWriter< OStream > &bitwriter, uint8_t P, uint64_t x)
Definition: golombrice.h:13
static unsigned char elements[DATACOUNT][DATALEN]
Definition: tests_impl.h:36
Implement std::hash so RCUPtr can be used as a key for maps or sets.
Definition: rcu.h:257
const CChainParams & m_params
Definition: interfaces.cpp:786
std::shared_ptr< const CTransaction > CTransactionRef
Definition: transaction.h:315
const char * name
Definition: rest.cpp:47
@ OP_RETURN
Definition: script.h:84
@ SER_NETWORK
Definition: serialize.h:152
uint64_t ReadCompactSize(Stream &is, bool range_check=true)
Decode a CompactSize-encoded variable-length integer.
Definition: serialize.h:413
void WriteCompactSize(CSizeComputer &os, uint64_t nSize)
Definition: serialize.h:1254
A BlockHash is a unqiue identifier for a block.
Definition: blockhash.h:13
uint32_t m_M
Inverse false positive rate.
Definition: blockfilter.h:34
uint64_t m_siphash_k1
Definition: blockfilter.h:32
uint8_t m_P
Golomb-Rice coding parameter.
Definition: blockfilter.h:33
uint64_t m_siphash_k0
Definition: blockfilter.h:31
assert(!tx.IsCoinBase())