Branch data Line data Source code
# 1 : : // Copyright (c) 2018-2020 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 : :
# 17 : : /// SerType used to serialize parameters in GCS filter encoding.
# 18 : : static constexpr int GCS_SER_TYPE = SER_NETWORK;
# 19 : :
# 20 : : /// Protocol version used to serialize parameters in GCS filter encoding.
# 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 : 26038 : {
# 34 : 26038 : #ifdef __SIZEOF_INT128__
# 35 : 26038 : 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 : 26038 : }
# 57 : :
# 58 : : uint64_t GCSFilter::HashToRange(const Element& element) const
# 59 : 26038 : {
# 60 : 26038 : uint64_t hash = CSipHasher(m_params.m_siphash_k0, m_params.m_siphash_k1)
# 61 : 26038 : .Write(element.data(), element.size())
# 62 : 26038 : .Finalize();
# 63 : 26038 : return MapIntoRange(hash, m_F);
# 64 : 26038 : }
# 65 : :
# 66 : : std::vector<uint64_t> GCSFilter::BuildHashedSet(const ElementSet& elements) const
# 67 : 5584 : {
# 68 : 5584 : std::vector<uint64_t> hashed_elements;
# 69 : 5584 : hashed_elements.reserve(elements.size());
# 70 [ + + ]: 25820 : for (const Element& element : elements) {
# 71 : 25820 : hashed_elements.push_back(HashToRange(element));
# 72 : 25820 : }
# 73 : 5584 : std::sort(hashed_elements.begin(), hashed_elements.end());
# 74 : 5584 : return hashed_elements;
# 75 : 5584 : }
# 76 : :
# 77 : : GCSFilter::GCSFilter(const Params& params)
# 78 : : : m_params(params), m_N(0), m_F(0), m_encoded{0}
# 79 : 7004 : {}
# 80 : :
# 81 : : GCSFilter::GCSFilter(const Params& params, std::vector<unsigned char> encoded_filter)
# 82 : : : m_params(params), m_encoded(std::move(encoded_filter))
# 83 : 693 : {
# 84 : 693 : VectorReader stream(GCS_SER_TYPE, GCS_SER_VERSION, m_encoded, 0);
# 85 : :
# 86 : 693 : uint64_t N = ReadCompactSize(stream);
# 87 : 693 : m_N = static_cast<uint32_t>(N);
# 88 [ - + ]: 693 : if (m_N != N) {
# 89 : 0 : throw std::ios_base::failure("N must be <2^32");
# 90 : 0 : }
# 91 : 693 : 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 : 693 : BitStreamReader<VectorReader> bitreader(stream);
# 96 [ + + ]: 1394 : for (uint64_t i = 0; i < m_N; ++i) {
# 97 : 701 : GolombRiceDecode(bitreader, m_params.m_P);
# 98 : 701 : }
# 99 [ - + ]: 693 : if (!stream.empty()) {
# 100 : 0 : throw std::ios_base::failure("encoded_filter contains excess data");
# 101 : 0 : }
# 102 : 693 : }
# 103 : :
# 104 : : GCSFilter::GCSFilter(const Params& params, const ElementSet& elements)
# 105 : : : m_params(params)
# 106 : 5386 : {
# 107 : 5386 : size_t N = elements.size();
# 108 : 5386 : m_N = static_cast<uint32_t>(N);
# 109 [ - + ]: 5386 : if (m_N != N) {
# 110 : 0 : throw std::invalid_argument("N must be <2^32");
# 111 : 0 : }
# 112 : 5386 : m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M);
# 113 : :
# 114 : 5386 : CVectorWriter stream(GCS_SER_TYPE, GCS_SER_VERSION, m_encoded, 0);
# 115 : :
# 116 : 5386 : WriteCompactSize(stream, m_N);
# 117 : :
# 118 [ + + ]: 5386 : if (elements.empty()) {
# 119 : 2 : return;
# 120 : 2 : }
# 121 : :
# 122 : 5384 : BitStreamWriter<CVectorWriter> bitwriter(stream);
# 123 : :
# 124 : 5384 : uint64_t last_value = 0;
# 125 [ + + ]: 5652 : for (uint64_t value : BuildHashedSet(elements)) {
# 126 : 5652 : uint64_t delta = value - last_value;
# 127 : 5652 : GolombRiceEncode(bitwriter, m_params.m_P, delta);
# 128 : 5652 : last_value = value;
# 129 : 5652 : }
# 130 : :
# 131 : 5384 : bitwriter.Flush();
# 132 : 5384 : }
# 133 : :
# 134 : : bool GCSFilter::MatchInternal(const uint64_t* element_hashes, size_t size) const
# 135 : 418 : {
# 136 : 418 : VectorReader stream(GCS_SER_TYPE, GCS_SER_VERSION, m_encoded, 0);
# 137 : :
# 138 : : // Seek forward by size of N
# 139 : 418 : uint64_t N = ReadCompactSize(stream);
# 140 : 418 : assert(N == m_N);
# 141 : :
# 142 : 418 : BitStreamReader<VectorReader> bitreader(stream);
# 143 : :
# 144 : 418 : uint64_t value = 0;
# 145 : 418 : size_t hashes_index = 0;
# 146 [ + + ]: 18150 : for (uint32_t i = 0; i < m_N; ++i) {
# 147 : 18148 : uint64_t delta = GolombRiceDecode(bitreader, m_params.m_P);
# 148 : 18148 : value += delta;
# 149 : :
# 150 : 25882 : while (true) {
# 151 [ + + ]: 25882 : if (hashes_index == size) {
# 152 : 6 : return false;
# 153 [ + + ]: 25876 : } else if (element_hashes[hashes_index] == value) {
# 154 : 410 : return true;
# 155 [ + + ]: 25466 : } else if (element_hashes[hashes_index] > value) {
# 156 : 17732 : break;
# 157 : 17732 : }
# 158 : :
# 159 : 7734 : hashes_index++;
# 160 : 7734 : }
# 161 : 18148 : }
# 162 : :
# 163 : 418 : return false;
# 164 : 418 : }
# 165 : :
# 166 : : bool GCSFilter::Match(const Element& element) const
# 167 : 218 : {
# 168 : 218 : uint64_t query = HashToRange(element);
# 169 : 218 : return MatchInternal(&query, 1);
# 170 : 218 : }
# 171 : :
# 172 : : bool GCSFilter::MatchAny(const ElementSet& elements) const
# 173 : 200 : {
# 174 : 200 : const std::vector<uint64_t> queries = BuildHashedSet(elements);
# 175 : 200 : return MatchInternal(queries.data(), queries.size());
# 176 : 200 : }
# 177 : :
# 178 : : const std::string& BlockFilterTypeName(BlockFilterType filter_type)
# 179 : 26 : {
# 180 : 26 : static std::string unknown_retval = "";
# 181 : 26 : auto it = g_filter_types.find(filter_type);
# 182 [ + + ]: 26 : return it != g_filter_types.end() ? it->second : unknown_retval;
# 183 : 26 : }
# 184 : :
# 185 : 22 : bool BlockFilterTypeByName(const std::string& name, BlockFilterType& filter_type) {
# 186 [ + + ]: 22 : for (const auto& entry : g_filter_types) {
# 187 [ + + ]: 22 : if (entry.second == name) {
# 188 : 19 : filter_type = entry.first;
# 189 : 19 : return true;
# 190 : 19 : }
# 191 : 22 : }
# 192 : 22 : return false;
# 193 : 22 : }
# 194 : :
# 195 : : const std::set<BlockFilterType>& AllBlockFilterTypes()
# 196 : 7 : {
# 197 : 7 : static std::set<BlockFilterType> types;
# 198 : :
# 199 : 7 : static std::once_flag flag;
# 200 : 7 : std::call_once(flag, []() {
# 201 [ + + ]: 7 : for (auto entry : g_filter_types) {
# 202 : 7 : types.insert(entry.first);
# 203 : 7 : }
# 204 : 7 : });
# 205 : :
# 206 : 7 : return types;
# 207 : 7 : }
# 208 : :
# 209 : : const std::string& ListBlockFilterTypes()
# 210 : 1536 : {
# 211 : 1536 : static std::string type_list;
# 212 : :
# 213 : 1536 : static std::once_flag flag;
# 214 : 1536 : std::call_once(flag, []() {
# 215 : 690 : std::stringstream ret;
# 216 : 690 : bool first = true;
# 217 [ + + ]: 690 : for (auto entry : g_filter_types) {
# 218 [ - + ]: 690 : if (!first) ret << ", ";
# 219 : 690 : ret << entry.second;
# 220 : 690 : first = false;
# 221 : 690 : }
# 222 : 690 : type_list = ret.str();
# 223 : 690 : });
# 224 : :
# 225 : 1536 : return type_list;
# 226 : 1536 : }
# 227 : :
# 228 : : static GCSFilter::ElementSet BasicFilterElements(const CBlock& block,
# 229 : : const CBlockUndo& block_undo)
# 230 : 5384 : {
# 231 : 5384 : GCSFilter::ElementSet elements;
# 232 : :
# 233 [ + + ]: 5406 : for (const CTransactionRef& tx : block.vtx) {
# 234 [ + + ]: 10786 : for (const CTxOut& txout : tx->vout) {
# 235 : 10786 : const CScript& script = txout.scriptPubKey;
# 236 [ + + ][ + + ]: 10786 : if (script.empty() || script[0] == OP_RETURN) continue;
# 237 : 5420 : elements.emplace(script.begin(), script.end());
# 238 : 5420 : }
# 239 : 5406 : }
# 240 : :
# 241 [ + + ]: 5384 : for (const CTxUndo& tx_undo : block_undo.vtxundo) {
# 242 [ + + ]: 56 : for (const Coin& prevout : tx_undo.vprevout) {
# 243 : 56 : const CScript& script = prevout.out.scriptPubKey;
# 244 [ + + ]: 56 : if (script.empty()) continue;
# 245 : 48 : elements.emplace(script.begin(), script.end());
# 246 : 48 : }
# 247 : 22 : }
# 248 : :
# 249 : 5384 : return elements;
# 250 : 5384 : }
# 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 : 691 : {
# 256 : 691 : GCSFilter::Params params;
# 257 [ - + ]: 691 : if (!BuildParams(params)) {
# 258 : 0 : throw std::invalid_argument("unknown filter_type");
# 259 : 0 : }
# 260 : 691 : m_filter = GCSFilter(params, std::move(filter));
# 261 : 691 : }
# 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 : 5384 : {
# 266 : 5384 : GCSFilter::Params params;
# 267 [ - + ]: 5384 : if (!BuildParams(params)) {
# 268 : 0 : throw std::invalid_argument("unknown filter_type");
# 269 : 0 : }
# 270 : 5384 : m_filter = GCSFilter(params, BasicFilterElements(block, block_undo));
# 271 : 5384 : }
# 272 : :
# 273 : : bool BlockFilter::BuildParams(GCSFilter::Params& params) const
# 274 : 6077 : {
# 275 [ - + ]: 6077 : switch (m_filter_type) {
# 276 [ + - ]: 6077 : case BlockFilterType::BASIC:
# 277 : 6077 : params.m_siphash_k0 = m_block_hash.GetUint64(0);
# 278 : 6077 : params.m_siphash_k1 = m_block_hash.GetUint64(1);
# 279 : 6077 : params.m_P = BASIC_FILTER_P;
# 280 : 6077 : params.m_M = BASIC_FILTER_M;
# 281 : 6077 : return true;
# 282 [ - + ]: 0 : case BlockFilterType::INVALID:
# 283 : 0 : return false;
# 284 : 0 : }
# 285 : :
# 286 : 0 : return false;
# 287 : 0 : }
# 288 : :
# 289 : : uint256 BlockFilter::GetHash() const
# 290 : 11656 : {
# 291 : 11656 : const std::vector<unsigned char>& data = GetEncodedFilter();
# 292 : :
# 293 : 11656 : uint256 result;
# 294 : 11656 : CHash256().Write(data).Finalize(result);
# 295 : 11656 : return result;
# 296 : 11656 : }
# 297 : :
# 298 : : uint256 BlockFilter::ComputeHeader(const uint256& prev_header) const
# 299 : 5382 : {
# 300 : 5382 : const uint256& filter_hash = GetHash();
# 301 : :
# 302 : 5382 : uint256 result;
# 303 : 5382 : CHash256()
# 304 : 5382 : .Write(filter_hash)
# 305 : 5382 : .Write(prev_header)
# 306 : 5382 : .Finalize(result);
# 307 : 5382 : return result;
# 308 : 5382 : }
|
