LCOV - code coverage report
Current view: top level - src - blockfilter.cpp (source / functions) Hit Total Coverage
Test: fuzz_coverage.info Lines: 9 145 6.2 %
Date: 2023-10-05 12:38:51 Functions: 4 21 19.0 %
Branches: 9 161 5.6 %

           Branch data     Line data    Source code
       1                 :            : // Copyright (c) 2018-2022 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 <set>
       7                 :            : 
       8                 :            : #include <blockfilter.h>
       9                 :            : #include <crypto/siphash.h>
      10                 :            : #include <hash.h>
      11                 :            : #include <primitives/block.h>
      12                 :            : #include <primitives/transaction.h>
      13                 :            : #include <script/script.h>
      14                 :            : #include <streams.h>
      15                 :            : #include <undo.h>
      16                 :            : #include <util/golombrice.h>
      17                 :            : #include <util/string.h>
      18                 :            : 
      19                 :            : /// Protocol version used to serialize parameters in GCS filter encoding.
      20                 :            : static constexpr int GCS_SER_VERSION = 0;
      21                 :            : 
      22         [ +  - ]:          2 : static const std::map<BlockFilterType, std::string> g_filter_types = {
      23         [ +  - ]:          2 :     {BlockFilterType::BASIC, "basic"},
      24                 :            : };
      25                 :            : 
      26                 :          0 : uint64_t GCSFilter::HashToRange(const Element& element) const
      27                 :            : {
      28                 :          0 :     uint64_t hash = CSipHasher(m_params.m_siphash_k0, m_params.m_siphash_k1)
      29                 :          0 :         .Write(element)
      30                 :          0 :         .Finalize();
      31                 :          0 :     return FastRange64(hash, m_F);
      32                 :            : }
      33                 :            : 
      34                 :          0 : std::vector<uint64_t> GCSFilter::BuildHashedSet(const ElementSet& elements) const
      35                 :            : {
      36                 :          0 :     std::vector<uint64_t> hashed_elements;
      37         [ #  # ]:          0 :     hashed_elements.reserve(elements.size());
      38         [ #  # ]:          0 :     for (const Element& element : elements) {
      39   [ #  #  #  # ]:          0 :         hashed_elements.push_back(HashToRange(element));
      40                 :            :     }
      41         [ #  # ]:          0 :     std::sort(hashed_elements.begin(), hashed_elements.end());
      42                 :          0 :     return hashed_elements;
      43         [ #  # ]:          0 : }
      44                 :            : 
      45                 :          0 : GCSFilter::GCSFilter(const Params& params)
      46         [ #  # ]:          0 :     : m_params(params), m_N(0), m_F(0), m_encoded{0}
      47                 :          0 : {}
      48                 :            : 
      49                 :          0 : GCSFilter::GCSFilter(const Params& params, std::vector<unsigned char> encoded_filter, bool skip_decode_check)
      50                 :          0 :     : m_params(params), m_encoded(std::move(encoded_filter))
      51                 :            : {
      52   [ #  #  #  # ]:          0 :     SpanReader stream{GCS_SER_VERSION, m_encoded};
      53                 :            : 
      54         [ #  # ]:          0 :     uint64_t N = ReadCompactSize(stream);
      55                 :          0 :     m_N = static_cast<uint32_t>(N);
      56         [ #  # ]:          0 :     if (m_N != N) {
      57         [ #  # ]:          0 :         throw std::ios_base::failure("N must be <2^32");
      58                 :            :     }
      59                 :          0 :     m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M);
      60                 :            : 
      61         [ #  # ]:          0 :     if (skip_decode_check) return;
      62                 :            : 
      63                 :            :     // Verify that the encoded filter contains exactly N elements. If it has too much or too little
      64                 :            :     // data, a std::ios_base::failure exception will be raised.
      65         [ #  # ]:          0 :     BitStreamReader<SpanReader> bitreader{stream};
      66         [ #  # ]:          0 :     for (uint64_t i = 0; i < m_N; ++i) {
      67         [ #  # ]:          0 :         GolombRiceDecode(bitreader, m_params.m_P);
      68                 :          0 :     }
      69   [ #  #  #  # ]:          0 :     if (!stream.empty()) {
      70         [ #  # ]:          0 :         throw std::ios_base::failure("encoded_filter contains excess data");
      71                 :            :     }
      72                 :          0 : }
      73                 :            : 
      74                 :          0 : GCSFilter::GCSFilter(const Params& params, const ElementSet& elements)
      75                 :          0 :     : m_params(params)
      76                 :            : {
      77                 :          0 :     size_t N = elements.size();
      78                 :          0 :     m_N = static_cast<uint32_t>(N);
      79         [ #  # ]:          0 :     if (m_N != N) {
      80   [ #  #  #  # ]:          0 :         throw std::invalid_argument("N must be <2^32");
      81                 :            :     }
      82                 :          0 :     m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M);
      83                 :            : 
      84         [ #  # ]:          0 :     CVectorWriter stream(GCS_SER_VERSION, m_encoded, 0);
      85                 :            : 
      86         [ #  # ]:          0 :     WriteCompactSize(stream, m_N);
      87                 :            : 
      88         [ #  # ]:          0 :     if (elements.empty()) {
      89                 :          0 :         return;
      90                 :            :     }
      91                 :            : 
      92         [ #  # ]:          0 :     BitStreamWriter<CVectorWriter> bitwriter(stream);
      93                 :            : 
      94                 :          0 :     uint64_t last_value = 0;
      95   [ #  #  #  # ]:          0 :     for (uint64_t value : BuildHashedSet(elements)) {
      96                 :          0 :         uint64_t delta = value - last_value;
      97         [ #  # ]:          0 :         GolombRiceEncode(bitwriter, m_params.m_P, delta);
      98                 :          0 :         last_value = value;
      99                 :            :     }
     100                 :            : 
     101         [ #  # ]:          0 :     bitwriter.Flush();
     102                 :          0 : }
     103                 :            : 
     104                 :          0 : bool GCSFilter::MatchInternal(const uint64_t* element_hashes, size_t size) const
     105                 :            : {
     106                 :          0 :     SpanReader stream{GCS_SER_VERSION, m_encoded};
     107                 :            : 
     108                 :            :     // Seek forward by size of N
     109                 :          0 :     uint64_t N = ReadCompactSize(stream);
     110         [ #  # ]:          0 :     assert(N == m_N);
     111                 :            : 
     112                 :          0 :     BitStreamReader<SpanReader> bitreader{stream};
     113                 :            : 
     114                 :          0 :     uint64_t value = 0;
     115                 :          0 :     size_t hashes_index = 0;
     116         [ #  # ]:          0 :     for (uint32_t i = 0; i < m_N; ++i) {
     117                 :          0 :         uint64_t delta = GolombRiceDecode(bitreader, m_params.m_P);
     118                 :          0 :         value += delta;
     119                 :            : 
     120                 :          0 :         while (true) {
     121         [ #  # ]:          0 :             if (hashes_index == size) {
     122                 :          0 :                 return false;
     123         [ #  # ]:          0 :             } else if (element_hashes[hashes_index] == value) {
     124                 :          0 :                 return true;
     125         [ #  # ]:          0 :             } else if (element_hashes[hashes_index] > value) {
     126                 :          0 :                 break;
     127                 :            :             }
     128                 :            : 
     129                 :          0 :             hashes_index++;
     130                 :            :         }
     131                 :          0 :     }
     132                 :            : 
     133                 :          0 :     return false;
     134                 :          0 : }
     135                 :            : 
     136                 :          0 : bool GCSFilter::Match(const Element& element) const
     137                 :            : {
     138                 :          0 :     uint64_t query = HashToRange(element);
     139                 :          0 :     return MatchInternal(&query, 1);
     140                 :            : }
     141                 :            : 
     142                 :          0 : bool GCSFilter::MatchAny(const ElementSet& elements) const
     143                 :            : {
     144                 :          0 :     const std::vector<uint64_t> queries = BuildHashedSet(elements);
     145         [ #  # ]:          0 :     return MatchInternal(queries.data(), queries.size());
     146                 :          0 : }
     147                 :            : 
     148                 :          4 : const std::string& BlockFilterTypeName(BlockFilterType filter_type)
     149                 :            : {
     150   [ +  +  +  - ]:          4 :     static std::string unknown_retval;
     151                 :          4 :     auto it = g_filter_types.find(filter_type);
     152         [ +  - ]:          4 :     return it != g_filter_types.end() ? it->second : unknown_retval;
     153                 :            : }
     154                 :            : 
     155                 :          0 : bool BlockFilterTypeByName(const std::string& name, BlockFilterType& filter_type) {
     156         [ #  # ]:          0 :     for (const auto& entry : g_filter_types) {
     157         [ #  # ]:          0 :         if (entry.second == name) {
     158                 :          0 :             filter_type = entry.first;
     159                 :          0 :             return true;
     160                 :            :         }
     161                 :            :     }
     162                 :          0 :     return false;
     163                 :          0 : }
     164                 :            : 
     165                 :          0 : const std::set<BlockFilterType>& AllBlockFilterTypes()
     166                 :            : {
     167   [ #  #  #  # ]:          0 :     static std::set<BlockFilterType> types;
     168                 :            : 
     169                 :            :     static std::once_flag flag;
     170                 :          0 :     std::call_once(flag, []() {
     171         [ #  # ]:          0 :             for (const auto& entry : g_filter_types) {
     172                 :          0 :                 types.insert(entry.first);
     173                 :            :             }
     174                 :          0 :         });
     175                 :            : 
     176                 :          0 :     return types;
     177                 :            : }
     178                 :            : 
     179                 :          1 : const std::string& ListBlockFilterTypes()
     180                 :            : {
     181   [ +  -  -  +  :          2 :     static std::string type_list{Join(g_filter_types, ", ", [](const auto& entry) { return entry.second; })};
                   +  - ]
     182                 :            : 
     183                 :          1 :     return type_list;
     184                 :          0 : }
     185                 :            : 
     186                 :          0 : static GCSFilter::ElementSet BasicFilterElements(const CBlock& block,
     187                 :            :                                                  const CBlockUndo& block_undo)
     188                 :            : {
     189                 :          0 :     GCSFilter::ElementSet elements;
     190                 :            : 
     191         [ #  # ]:          0 :     for (const CTransactionRef& tx : block.vtx) {
     192         [ #  # ]:          0 :         for (const CTxOut& txout : tx->vout) {
     193                 :          0 :             const CScript& script = txout.scriptPubKey;
     194   [ #  #  #  #  :          0 :             if (script.empty() || script[0] == OP_RETURN) continue;
             #  #  #  # ]
     195   [ #  #  #  #  :          0 :             elements.emplace(script.begin(), script.end());
                   #  # ]
     196                 :            :         }
     197                 :            :     }
     198                 :            : 
     199         [ #  # ]:          0 :     for (const CTxUndo& tx_undo : block_undo.vtxundo) {
     200         [ #  # ]:          0 :         for (const Coin& prevout : tx_undo.vprevout) {
     201                 :          0 :             const CScript& script = prevout.out.scriptPubKey;
     202   [ #  #  #  # ]:          0 :             if (script.empty()) continue;
     203   [ #  #  #  #  :          0 :             elements.emplace(script.begin(), script.end());
                   #  # ]
     204                 :            :         }
     205                 :            :     }
     206                 :            : 
     207                 :          0 :     return elements;
     208         [ #  # ]:          0 : }
     209                 :            : 
     210                 :          0 : BlockFilter::BlockFilter(BlockFilterType filter_type, const uint256& block_hash,
     211                 :            :                          std::vector<unsigned char> filter, bool skip_decode_check)
     212                 :          0 :     : m_filter_type(filter_type), m_block_hash(block_hash)
     213                 :            : {
     214         [ #  # ]:          0 :     GCSFilter::Params params;
     215   [ #  #  #  # ]:          0 :     if (!BuildParams(params)) {
     216   [ #  #  #  # ]:          0 :         throw std::invalid_argument("unknown filter_type");
     217                 :            :     }
     218         [ #  # ]:          0 :     m_filter = GCSFilter(params, std::move(filter), skip_decode_check);
     219                 :          0 : }
     220                 :            : 
     221                 :          0 : BlockFilter::BlockFilter(BlockFilterType filter_type, const CBlock& block, const CBlockUndo& block_undo)
     222                 :          0 :     : m_filter_type(filter_type), m_block_hash(block.GetHash())
     223                 :            : {
     224         [ #  # ]:          0 :     GCSFilter::Params params;
     225   [ #  #  #  # ]:          0 :     if (!BuildParams(params)) {
     226   [ #  #  #  # ]:          0 :         throw std::invalid_argument("unknown filter_type");
     227                 :            :     }
     228   [ #  #  #  # ]:          0 :     m_filter = GCSFilter(params, BasicFilterElements(block, block_undo));
     229                 :          0 : }
     230                 :            : 
     231                 :          0 : bool BlockFilter::BuildParams(GCSFilter::Params& params) const
     232                 :            : {
     233      [ #  #  # ]:          0 :     switch (m_filter_type) {
     234                 :            :     case BlockFilterType::BASIC:
     235                 :          0 :         params.m_siphash_k0 = m_block_hash.GetUint64(0);
     236                 :          0 :         params.m_siphash_k1 = m_block_hash.GetUint64(1);
     237                 :          0 :         params.m_P = BASIC_FILTER_P;
     238                 :          0 :         params.m_M = BASIC_FILTER_M;
     239                 :          0 :         return true;
     240                 :            :     case BlockFilterType::INVALID:
     241                 :          0 :         return false;
     242                 :            :     }
     243                 :            : 
     244                 :          0 :     return false;
     245                 :          0 : }
     246                 :            : 
     247                 :          0 : uint256 BlockFilter::GetHash() const
     248                 :            : {
     249                 :          0 :     return Hash(GetEncodedFilter());
     250                 :            : }
     251                 :            : 
     252                 :          0 : uint256 BlockFilter::ComputeHeader(const uint256& prev_header) const
     253                 :            : {
     254                 :          0 :     return Hash(GetHash(), prev_header);
     255                 :            : }

Generated by: LCOV version 1.14