Branch data Line data Source code
# 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 : :
# 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 : : uint64_t GCSFilter::HashToRange(const Element& element) const
# 28 : 27224 : {
# 29 : 27224 : uint64_t hash = CSipHasher(m_params.m_siphash_k0, m_params.m_siphash_k1)
# 30 : 27224 : .Write(element.data(), element.size())
# 31 : 27224 : .Finalize();
# 32 : 27224 : return FastRange64(hash, m_F);
# 33 : 27224 : }
# 34 : :
# 35 : : std::vector<uint64_t> GCSFilter::BuildHashedSet(const ElementSet& elements) const
# 36 : 6796 : {
# 37 : 6796 : std::vector<uint64_t> hashed_elements;
# 38 : 6796 : hashed_elements.reserve(elements.size());
# 39 [ + + ]: 27006 : for (const Element& element : elements) {
# 40 : 27006 : hashed_elements.push_back(HashToRange(element));
# 41 : 27006 : }
# 42 : 6796 : std::sort(hashed_elements.begin(), hashed_elements.end());
# 43 : 6796 : return hashed_elements;
# 44 : 6796 : }
# 45 : :
# 46 : : GCSFilter::GCSFilter(const Params& params)
# 47 : : : m_params(params), m_N(0), m_F(0), m_encoded{0}
# 48 : 8220 : {}
# 49 : :
# 50 : : GCSFilter::GCSFilter(const Params& params, std::vector<unsigned char> encoded_filter)
# 51 : : : m_params(params), m_encoded(std::move(encoded_filter))
# 52 : 695 : {
# 53 : 695 : SpanReader stream{GCS_SER_TYPE, GCS_SER_VERSION, m_encoded};
# 54 : :
# 55 : 695 : uint64_t N = ReadCompactSize(stream);
# 56 : 695 : m_N = static_cast<uint32_t>(N);
# 57 [ - + ]: 695 : if (m_N != N) {
# 58 : 0 : throw std::ios_base::failure("N must be <2^32");
# 59 : 0 : }
# 60 : 695 : 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 : 695 : BitStreamReader<SpanReader> bitreader{stream};
# 65 [ + + ]: 1398 : for (uint64_t i = 0; i < m_N; ++i) {
# 66 : 703 : GolombRiceDecode(bitreader, m_params.m_P);
# 67 : 703 : }
# 68 [ - + ]: 695 : if (!stream.empty()) {
# 69 : 0 : throw std::ios_base::failure("encoded_filter contains excess data");
# 70 : 0 : }
# 71 : 695 : }
# 72 : :
# 73 : : GCSFilter::GCSFilter(const Params& params, const ElementSet& elements)
# 74 : : : m_params(params)
# 75 : 6598 : {
# 76 : 6598 : size_t N = elements.size();
# 77 : 6598 : m_N = static_cast<uint32_t>(N);
# 78 [ - + ]: 6598 : if (m_N != N) {
# 79 : 0 : throw std::invalid_argument("N must be <2^32");
# 80 : 0 : }
# 81 : 6598 : m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M);
# 82 : :
# 83 : 6598 : CVectorWriter stream(GCS_SER_TYPE, GCS_SER_VERSION, m_encoded, 0);
# 84 : :
# 85 : 6598 : WriteCompactSize(stream, m_N);
# 86 : :
# 87 [ + + ]: 6598 : if (elements.empty()) {
# 88 : 2 : return;
# 89 : 2 : }
# 90 : :
# 91 : 6596 : BitStreamWriter<CVectorWriter> bitwriter(stream);
# 92 : :
# 93 : 6596 : uint64_t last_value = 0;
# 94 [ + + ]: 6868 : for (uint64_t value : BuildHashedSet(elements)) {
# 95 : 6868 : uint64_t delta = value - last_value;
# 96 : 6868 : GolombRiceEncode(bitwriter, m_params.m_P, delta);
# 97 : 6868 : last_value = value;
# 98 : 6868 : }
# 99 : :
# 100 : 6596 : bitwriter.Flush();
# 101 : 6596 : }
# 102 : :
# 103 : : bool GCSFilter::MatchInternal(const uint64_t* element_hashes, size_t size) const
# 104 : 418 : {
# 105 : 418 : SpanReader stream{GCS_SER_TYPE, GCS_SER_VERSION, m_encoded};
# 106 : :
# 107 : : // Seek forward by size of N
# 108 : 418 : uint64_t N = ReadCompactSize(stream);
# 109 : 418 : assert(N == m_N);
# 110 : :
# 111 : 0 : BitStreamReader<SpanReader> bitreader{stream};
# 112 : :
# 113 : 418 : uint64_t value = 0;
# 114 : 418 : size_t hashes_index = 0;
# 115 [ + + ]: 18208 : for (uint32_t i = 0; i < m_N; ++i) {
# 116 : 18206 : uint64_t delta = GolombRiceDecode(bitreader, m_params.m_P);
# 117 : 18206 : value += delta;
# 118 : :
# 119 : 26008 : while (true) {
# 120 [ + + ]: 26008 : if (hashes_index == size) {
# 121 : 6 : return false;
# 122 [ + + ]: 26002 : } else if (element_hashes[hashes_index] == value) {
# 123 : 410 : return true;
# 124 [ + + ]: 25592 : } else if (element_hashes[hashes_index] > value) {
# 125 : 17790 : break;
# 126 : 17790 : }
# 127 : :
# 128 : 7802 : hashes_index++;
# 129 : 7802 : }
# 130 : 18206 : }
# 131 : :
# 132 : 2 : return false;
# 133 : 418 : }
# 134 : :
# 135 : : bool GCSFilter::Match(const Element& element) const
# 136 : 218 : {
# 137 : 218 : uint64_t query = HashToRange(element);
# 138 : 218 : return MatchInternal(&query, 1);
# 139 : 218 : }
# 140 : :
# 141 : : bool GCSFilter::MatchAny(const ElementSet& elements) const
# 142 : 200 : {
# 143 : 200 : const std::vector<uint64_t> queries = BuildHashedSet(elements);
# 144 : 200 : return MatchInternal(queries.data(), queries.size());
# 145 : 200 : }
# 146 : :
# 147 : : const std::string& BlockFilterTypeName(BlockFilterType filter_type)
# 148 : 64 : {
# 149 : 64 : static std::string unknown_retval = "";
# 150 : 64 : auto it = g_filter_types.find(filter_type);
# 151 [ + + ]: 64 : return it != g_filter_types.end() ? it->second : unknown_retval;
# 152 : 64 : }
# 153 : :
# 154 : 27 : bool BlockFilterTypeByName(const std::string& name, BlockFilterType& filter_type) {
# 155 [ + + ]: 27 : for (const auto& entry : g_filter_types) {
# 156 [ + + ]: 27 : if (entry.second == name) {
# 157 : 24 : filter_type = entry.first;
# 158 : 24 : return true;
# 159 : 24 : }
# 160 : 27 : }
# 161 : 3 : return false;
# 162 : 27 : }
# 163 : :
# 164 : : const std::set<BlockFilterType>& AllBlockFilterTypes()
# 165 : 33 : {
# 166 : 33 : static std::set<BlockFilterType> types;
# 167 : :
# 168 : 33 : static std::once_flag flag;
# 169 : 33 : std::call_once(flag, []() {
# 170 [ + + ]: 33 : for (auto entry : g_filter_types) {
# 171 : 33 : types.insert(entry.first);
# 172 : 33 : }
# 173 : 33 : });
# 174 : :
# 175 : 33 : return types;
# 176 : 33 : }
# 177 : :
# 178 : : const std::string& ListBlockFilterTypes()
# 179 : 1662 : {
# 180 : 1662 : static std::string type_list;
# 181 : :
# 182 : 1662 : static std::once_flag flag;
# 183 : 1662 : std::call_once(flag, []() {
# 184 : 828 : std::stringstream ret;
# 185 : 828 : bool first = true;
# 186 [ + + ]: 828 : for (auto entry : g_filter_types) {
# 187 [ - + ]: 828 : if (!first) ret << ", ";
# 188 : 828 : ret << entry.second;
# 189 : 828 : first = false;
# 190 : 828 : }
# 191 : 828 : type_list = ret.str();
# 192 : 828 : });
# 193 : :
# 194 : 1662 : return type_list;
# 195 : 1662 : }
# 196 : :
# 197 : : static GCSFilter::ElementSet BasicFilterElements(const CBlock& block,
# 198 : : const CBlockUndo& block_undo)
# 199 : 6596 : {
# 200 : 6596 : GCSFilter::ElementSet elements;
# 201 : :
# 202 [ + + ]: 6623 : for (const CTransactionRef& tx : block.vtx) {
# 203 [ + + ]: 13215 : for (const CTxOut& txout : tx->vout) {
# 204 : 13215 : const CScript& script = txout.scriptPubKey;
# 205 [ + + ][ + + ]: 13215 : if (script.empty() || script[0] == OP_RETURN) continue;
# 206 : 6639 : elements.emplace(script.begin(), script.end());
# 207 : 6639 : }
# 208 : 6623 : }
# 209 : :
# 210 [ + + ]: 6596 : for (const CTxUndo& tx_undo : block_undo.vtxundo) {
# 211 [ + + ]: 61 : for (const Coin& prevout : tx_undo.vprevout) {
# 212 : 61 : const CScript& script = prevout.out.scriptPubKey;
# 213 [ + + ]: 61 : if (script.empty()) continue;
# 214 : 53 : elements.emplace(script.begin(), script.end());
# 215 : 53 : }
# 216 : 27 : }
# 217 : :
# 218 : 6596 : return elements;
# 219 : 6596 : }
# 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 : 693 : {
# 225 : 693 : GCSFilter::Params params;
# 226 [ - + ]: 693 : if (!BuildParams(params)) {
# 227 : 0 : throw std::invalid_argument("unknown filter_type");
# 228 : 0 : }
# 229 : 693 : m_filter = GCSFilter(params, std::move(filter));
# 230 : 693 : }
# 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 : 6596 : {
# 235 : 6596 : GCSFilter::Params params;
# 236 [ - + ]: 6596 : if (!BuildParams(params)) {
# 237 : 0 : throw std::invalid_argument("unknown filter_type");
# 238 : 0 : }
# 239 : 6596 : m_filter = GCSFilter(params, BasicFilterElements(block, block_undo));
# 240 : 6596 : }
# 241 : :
# 242 : : bool BlockFilter::BuildParams(GCSFilter::Params& params) const
# 243 : 7291 : {
# 244 [ - + ]: 7291 : switch (m_filter_type) {
# 245 [ + - ]: 7291 : case BlockFilterType::BASIC:
# 246 : 7291 : params.m_siphash_k0 = m_block_hash.GetUint64(0);
# 247 : 7291 : params.m_siphash_k1 = m_block_hash.GetUint64(1);
# 248 : 7291 : params.m_P = BASIC_FILTER_P;
# 249 : 7291 : params.m_M = BASIC_FILTER_M;
# 250 : 7291 : return true;
# 251 [ - + ]: 0 : case BlockFilterType::INVALID:
# 252 : 0 : return false;
# 253 : 7291 : }
# 254 : :
# 255 : 0 : return false;
# 256 : 7291 : }
# 257 : :
# 258 : : uint256 BlockFilter::GetHash() const
# 259 : 14080 : {
# 260 : 14080 : const std::vector<unsigned char>& data = GetEncodedFilter();
# 261 : :
# 262 : 14080 : uint256 result;
# 263 : 14080 : CHash256().Write(data).Finalize(result);
# 264 : 14080 : return result;
# 265 : 14080 : }
# 266 : :
# 267 : : uint256 BlockFilter::ComputeHeader(const uint256& prev_header) const
# 268 : 6594 : {
# 269 : 6594 : const uint256& filter_hash = GetHash();
# 270 : :
# 271 : 6594 : uint256 result;
# 272 : 6594 : CHash256()
# 273 : 6594 : .Write(filter_hash)
# 274 : 6594 : .Write(prev_header)
# 275 : 6594 : .Finalize(result);
# 276 : 6594 : return result;
# 277 : 6594 : }
|
