Bitcoin Core  22.99.0
P2P Digital Currency
blockfilter.cpp
Go to the documentation of this file.
1 // Copyright (c) 2018-2021 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 uint64_t GCSFilter::HashToRange(const Element& element) const
28 {
30  .Write(element.data(), element.size())
31  .Finalize();
32  return FastRange64(hash, m_F);
33 }
34 
35 std::vector<uint64_t> GCSFilter::BuildHashedSet(const ElementSet& elements) const
36 {
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 
50 GCSFilter::GCSFilter(const Params& params, std::vector<unsigned char> encoded_filter)
51  : m_params(params), m_encoded(std::move(encoded_filter))
52 {
54 
55  uint64_t N = ReadCompactSize(stream);
56  m_N = static_cast<uint32_t>(N);
57  if (m_N != N) {
58  throw std::ios_base::failure("N must be <2^32");
59  }
60  m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M);
61 
62  // Verify that the encoded filter contains exactly N elements. If it has too much or too little
63  // data, a std::ios_base::failure exception will be raised.
64  BitStreamReader<SpanReader> bitreader{stream};
65  for (uint64_t i = 0; i < m_N; ++i) {
66  GolombRiceDecode(bitreader, m_params.m_P);
67  }
68  if (!stream.empty()) {
69  throw std::ios_base::failure("encoded_filter contains excess data");
70  }
71 }
72 
73 GCSFilter::GCSFilter(const Params& params, const ElementSet& elements)
74  : m_params(params)
75 {
76  size_t N = elements.size();
77  m_N = static_cast<uint32_t>(N);
78  if (m_N != N) {
79  throw std::invalid_argument("N must be <2^32");
80  }
81  m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M);
82 
84 
85  WriteCompactSize(stream, m_N);
86 
87  if (elements.empty()) {
88  return;
89  }
90 
91  BitStreamWriter<CVectorWriter> bitwriter(stream);
92 
93  uint64_t last_value = 0;
94  for (uint64_t value : BuildHashedSet(elements)) {
95  uint64_t delta = value - last_value;
96  GolombRiceEncode(bitwriter, m_params.m_P, delta);
97  last_value = value;
98  }
99 
100  bitwriter.Flush();
101 }
102 
103 bool GCSFilter::MatchInternal(const uint64_t* element_hashes, size_t size) const
104 {
106 
107  // Seek forward by size of N
108  uint64_t N = ReadCompactSize(stream);
109  assert(N == m_N);
110 
111  BitStreamReader<SpanReader> bitreader{stream};
112 
113  uint64_t value = 0;
114  size_t hashes_index = 0;
115  for (uint32_t i = 0; i < m_N; ++i) {
116  uint64_t delta = GolombRiceDecode(bitreader, m_params.m_P);
117  value += delta;
118 
119  while (true) {
120  if (hashes_index == size) {
121  return false;
122  } else if (element_hashes[hashes_index] == value) {
123  return true;
124  } else if (element_hashes[hashes_index] > value) {
125  break;
126  }
127 
128  hashes_index++;
129  }
130  }
131 
132  return false;
133 }
134 
135 bool GCSFilter::Match(const Element& element) const
136 {
137  uint64_t query = HashToRange(element);
138  return MatchInternal(&query, 1);
139 }
140 
141 bool GCSFilter::MatchAny(const ElementSet& elements) const
142 {
143  const std::vector<uint64_t> queries = BuildHashedSet(elements);
144  return MatchInternal(queries.data(), queries.size());
145 }
146 
147 const std::string& BlockFilterTypeName(BlockFilterType filter_type)
148 {
149  static std::string unknown_retval = "";
150  auto it = g_filter_types.find(filter_type);
151  return it != g_filter_types.end() ? it->second : unknown_retval;
152 }
153 
154 bool BlockFilterTypeByName(const std::string& name, BlockFilterType& filter_type) {
155  for (const auto& entry : g_filter_types) {
156  if (entry.second == name) {
157  filter_type = entry.first;
158  return true;
159  }
160  }
161  return false;
162 }
163 
164 const std::set<BlockFilterType>& AllBlockFilterTypes()
165 {
166  static std::set<BlockFilterType> types;
167 
168  static std::once_flag flag;
169  std::call_once(flag, []() {
170  for (auto entry : g_filter_types) {
171  types.insert(entry.first);
172  }
173  });
174 
175  return types;
176 }
177 
178 const std::string& ListBlockFilterTypes()
179 {
180  static std::string type_list;
181 
182  static std::once_flag flag;
183  std::call_once(flag, []() {
184  std::stringstream ret;
185  bool first = true;
186  for (auto entry : g_filter_types) {
187  if (!first) ret << ", ";
188  ret << entry.second;
189  first = false;
190  }
191  type_list = ret.str();
192  });
193 
194  return type_list;
195 }
196 
198  const CBlockUndo& block_undo)
199 {
200  GCSFilter::ElementSet elements;
201 
202  for (const CTransactionRef& tx : block.vtx) {
203  for (const CTxOut& txout : tx->vout) {
204  const CScript& script = txout.scriptPubKey;
205  if (script.empty() || script[0] == OP_RETURN) continue;
206  elements.emplace(script.begin(), script.end());
207  }
208  }
209 
210  for (const CTxUndo& tx_undo : block_undo.vtxundo) {
211  for (const Coin& prevout : tx_undo.vprevout) {
212  const CScript& script = prevout.out.scriptPubKey;
213  if (script.empty()) continue;
214  elements.emplace(script.begin(), script.end());
215  }
216  }
217 
218  return elements;
219 }
220 
221 BlockFilter::BlockFilter(BlockFilterType filter_type, const uint256& block_hash,
222  std::vector<unsigned char> filter)
223  : m_filter_type(filter_type), m_block_hash(block_hash)
224 {
225  GCSFilter::Params params;
226  if (!BuildParams(params)) {
227  throw std::invalid_argument("unknown filter_type");
228  }
229  m_filter = GCSFilter(params, std::move(filter));
230 }
231 
232 BlockFilter::BlockFilter(BlockFilterType filter_type, const CBlock& block, const CBlockUndo& block_undo)
233  : m_filter_type(filter_type), m_block_hash(block.GetHash())
234 {
235  GCSFilter::Params params;
236  if (!BuildParams(params)) {
237  throw std::invalid_argument("unknown filter_type");
238  }
239  m_filter = GCSFilter(params, BasicFilterElements(block, block_undo));
240 }
241 
243 {
244  switch (m_filter_type) {
246  params.m_siphash_k0 = m_block_hash.GetUint64(0);
247  params.m_siphash_k1 = m_block_hash.GetUint64(1);
248  params.m_P = BASIC_FILTER_P;
249  params.m_M = BASIC_FILTER_M;
250  return true;
252  return false;
253  }
254 
255  return false;
256 }
257 
259 {
260  const std::vector<unsigned char>& data = GetEncodedFilter();
261 
262  uint256 result;
263  CHash256().Write(data).Finalize(result);
264  return result;
265 }
266 
267 uint256 BlockFilter::ComputeHeader(const uint256& prev_header) const
268 {
269  const uint256& filter_hash = GetHash();
270 
271  uint256 result;
272  CHash256()
273  .Write(filter_hash)
274  .Write(prev_header)
275  .Finalize(result);
276  return result;
277 }
FastRange64
static uint64_t FastRange64(uint64_t x, uint64_t n)
Fast range reduction with 64-bit input and 64-bit range.
Definition: fastrange.h:25
BlockFilterTypeName
const std::string & BlockFilterTypeName(BlockFilterType filter_type)
Get the human-readable name for a filter type.
Definition: blockfilter.cpp:147
BitStreamReader
Definition: streams.h:437
BlockFilter::BuildParams
bool BuildParams(GCSFilter::Params &params) const
Definition: blockfilter.cpp:242
assert
assert(!tx.IsCoinBase())
GolombRiceDecode
uint64_t GolombRiceDecode(BitStreamReader< IStream > &bitreader, uint8_t P)
Definition: golombrice.h:32
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:135
BitStreamWriter::Flush
void Flush()
Flush any unwritten bits to the output stream, padding with 0's to the next byte boundary.
Definition: streams.h:525
BASIC_FILTER_M
constexpr uint32_t BASIC_FILTER_M
Definition: blockfilter.h:86
CHash256::Write
CHash256 & Write(Span< const unsigned char > input)
Definition: hash.h:37
CVectorWriter
Definition: streams.h:72
CTxUndo
Undo information for a CTransaction.
Definition: undo.h:53
streams.h
GCSFilter::m_params
Params m_params
Definition: blockfilter.h:43
transaction.h
BlockFilter::GetEncodedFilter
const std::vector< unsigned char > & GetEncodedFilter() const
Definition: blockfilter.h:134
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:32
base_blob::GetUint64
uint64_t GetUint64(int pos) const
Definition: uint256.h:83
BlockFilterTypeByName
bool BlockFilterTypeByName(const std::string &name, BlockFilterType &filter_type)
Find a filter type by its human-readable name.
Definition: blockfilter.cpp:154
AllBlockFilterTypes
const std::set< BlockFilterType > & AllBlockFilterTypes()
Get a list of known filter types.
Definition: blockfilter.cpp:164
BlockFilter::ComputeHeader
uint256 ComputeHeader(const uint256 &prev_header) const
Compute the filter header given the previous one.
Definition: blockfilter.cpp:267
golombrice.h
ReadCompactSize
uint64_t ReadCompactSize(Stream &is, bool range_check=true)
Decode a CompactSize-encoded variable-length integer.
Definition: serialize.h:282
CTransactionRef
std::shared_ptr< const CTransaction > CTransactionRef
Definition: transaction.h:386
GCSFilter::GCSFilter
GCSFilter(const Params &params=Params())
Constructs an empty filter.
Definition: blockfilter.cpp:46
BitStreamWriter
Definition: streams.h:480
CBlockUndo::vtxundo
std::vector< CTxUndo > vtxundo
Definition: undo.h:66
CSipHasher
SipHash-2-4.
Definition: siphash.h:13
Coin::out
CTxOut out
unspent transaction output
Definition: coins.h:34
GCSFilter::Params::m_M
uint32_t m_M
Inverse false positive rate.
Definition: blockfilter.h:35
GCSFilter
This implements a Golomb-coded set as defined in BIP 158.
Definition: blockfilter.h:24
prevector::end
iterator end()
Definition: prevector.h:292
siphash.h
GCSFilter::Params::m_P
uint8_t m_P
Golomb-Rice coding parameter.
Definition: blockfilter.h:34
OP_RETURN
@ OP_RETURN
Definition: script.h:104
blockfilter.h
CTxOut
An output of a transaction.
Definition: transaction.h:128
Coin
A UTXO entry.
Definition: coins.h:30
CSipHasher::Finalize
uint64_t Finalize() const
Compute the 64-bit SipHash-2-4 of the data written so far.
Definition: siphash.cpp:76
CTxOut::scriptPubKey
CScript scriptPubKey
Definition: transaction.h:132
BlockFilter::m_block_hash
uint256 m_block_hash
Definition: blockfilter.h:114
WriteCompactSize
void WriteCompactSize(CSizeComputer &os, uint64_t nSize)
Definition: serialize.h:1087
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:103
GCSFilter::m_encoded
std::vector< unsigned char > m_encoded
Definition: blockfilter.h:46
GCSFilter::MatchAny
bool MatchAny(const ElementSet &elements) const
Checks if any of the given elements may be in the set.
Definition: blockfilter.cpp:141
SpanReader
Minimal stream for reading from an existing byte array by Span.
Definition: streams.h:133
CHash256::Finalize
void Finalize(Span< unsigned char > output)
Definition: hash.h:30
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:124
GolombRiceEncode
void GolombRiceEncode(BitStreamWriter< OStream > &bitwriter, uint8_t P, uint64_t x)
Definition: golombrice.h:15
GCSFilter::Params::m_siphash_k1
uint64_t m_siphash_k1
Definition: blockfilter.h:33
BasicFilterElements
static GCSFilter::ElementSet BasicFilterElements(const CBlock &block, const CBlockUndo &block_undo)
Definition: blockfilter.cpp:197
BlockFilter::BlockFilter
BlockFilter()=default
ListBlockFilterTypes
const std::string & ListBlockFilterTypes()
Get a comma-separated list of known filter type names.
Definition: blockfilter.cpp:178
CScript
Serialized script, used inside transaction inputs and outputs.
Definition: script.h:405
script.h
BlockFilterType::BASIC
@ BASIC
BlockFilter::GetHash
uint256 GetHash() const
Compute the filter hash.
Definition: blockfilter.cpp:258
name
const char * name
Definition: rest.cpp:52
BlockFilter::m_filter
GCSFilter m_filter
Definition: blockfilter.h:115
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:27
CBlock
Definition: block.h:62
BlockFilterType::INVALID
@ INVALID
CTxUndo::vprevout
std::vector< Coin > vprevout
Definition: undo.h:57
CBlock::vtx
std::vector< CTransactionRef > vtx
Definition: block.h:66
BlockFilter::m_filter_type
BlockFilterType m_filter_type
Definition: blockfilter.h:113
GCSFilter::ElementSet
std::unordered_set< Element, ByteVectorHash > ElementSet
Definition: blockfilter.h:28
std
Definition: setup_common.h:33
prevector::begin
iterator begin()
Definition: prevector.h:290
GCS_SER_VERSION
static constexpr int GCS_SER_VERSION
Protocol version used to serialize parameters in GCS filter encoding.
Definition: blockfilter.cpp:21
GCSFilter::BuildHashedSet
std::vector< uint64_t > BuildHashedSet(const ElementSet &elements) const
Definition: blockfilter.cpp:35
hash.h
BASIC_FILTER_P
constexpr uint8_t BASIC_FILTER_P
Definition: blockfilter.h:85
BlockFilterType
BlockFilterType
Definition: blockfilter.h:88
prevector::empty
bool empty() const
Definition: prevector.h:286
SER_NETWORK
@ SER_NETWORK
Definition: serialize.h:138
CHash256
A hasher class for Bitcoin's 256-bit hash (double SHA-256).
Definition: hash.h:24
GCS_SER_TYPE
static constexpr int GCS_SER_TYPE
SerType used to serialize parameters in GCS filter encoding.
Definition: blockfilter.cpp:18
GCSFilter::Element
std::vector< unsigned char > Element
Definition: blockfilter.h:27
CBlockUndo
Undo information for a CBlock.
Definition: undo.h:63
CSipHasher::Write
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