Line data Source code
1 : // Copyright (c) 2012-2014 The Bitcoin developers 2 : // Copyright (c) 2017-2020 The PIVX Core developers 3 : // Distributed under the MIT software license, see the accompanying 4 : // file COPYING or http://www.opensource.org/licenses/mit-license.php. 5 : 6 : #ifndef PIVX_BLOOM_H 7 : #define PIVX_BLOOM_H 8 : 9 : #include "serialize.h" 10 : 11 : #include <vector> 12 : 13 : class COutPoint; 14 : class CTransaction; 15 : class uint256; 16 : 17 : //! 20,000 items with fp rate < 0.1% or 10,000 items and <0.0001% 18 : static const unsigned int MAX_BLOOM_FILTER_SIZE = 36000; // bytes 19 : static const unsigned int MAX_HASH_FUNCS = 50; 20 : 21 : /** 22 : * First two bits of nFlags control how much IsRelevantAndUpdate actually updates 23 : * The remaining bits are reserved 24 : */ 25 : enum bloomflags { 26 : BLOOM_UPDATE_NONE = 0, 27 : BLOOM_UPDATE_ALL = 1, 28 : // Only adds outpoints to the filter if the output is a pay-to-pubkey/pay-to-multisig script 29 : BLOOM_UPDATE_P2PUBKEY_ONLY = 2, 30 : BLOOM_UPDATE_MASK = 3, 31 : }; 32 : 33 : /** 34 : * BloomFilter is a probabilistic filter which SPV clients provide 35 : * so that we can filter the transactions we sends them. 36 : * 37 : * This allows for significantly more efficient transaction and block downloads. 38 : * 39 : * Because bloom filters are probabilistic, an SPV node can increase the false- 40 : * positive rate, making us send them transactions which aren't actually theirs, 41 : * allowing clients to trade more bandwidth for more privacy by obfuscating which 42 : * keys are owned by them. 43 : */ 44 2457 : class CBloomFilter 45 : { 46 : private: 47 : std::vector<unsigned char> vData; 48 : bool isFull; 49 : bool isEmpty; 50 : unsigned int nHashFuncs; 51 : unsigned int nTweak; 52 : unsigned char nFlags; 53 : 54 : unsigned int Hash(unsigned int nHashNum, const std::vector<unsigned char>& vDataToHash) const; 55 : 56 : public: 57 : /** 58 : * Creates a new bloom filter which will provide the given fp rate when filled with the given number of elements 59 : * Note that if the given parameters will result in a filter outside the bounds of the protocol limits, 60 : * the filter created will be as close to the given parameters as possible within the protocol limits. 61 : * This will apply if nFPRate is very low or nElements is unreasonably high. 62 : * nTweak is a constant which is added to the seed value passed to the hash function 63 : * It should generally always be a random value (and is largely only exposed for unit testing) 64 : * nFlags should be one of the BLOOM_UPDATE_* enums (not _MASK) 65 : */ 66 : CBloomFilter(unsigned int nElements, double nFPRate, unsigned int nTweak, unsigned char nFlagsIn); 67 1464 : CBloomFilter() : isFull(true), isEmpty(false), nHashFuncs(0), nTweak(0), nFlags(0) {} 68 : 69 3 : SERIALIZE_METHODS(CBloomFilter, obj) { READWRITE(obj.vData, obj.nHashFuncs, obj.nTweak, obj.nFlags); } 70 : 71 : void insert(const std::vector<unsigned char>& vKey); 72 : void insert(const COutPoint& outpoint); 73 : void insert(const uint256& hash); 74 : 75 : bool contains(const std::vector<unsigned char>& vKey) const; 76 : bool contains(const COutPoint& outpoint) const; 77 : bool contains(const uint256& hash) const; 78 : 79 : void clear(); 80 : void reset(unsigned int nNewTweak); 81 : 82 : //! True if the size is <= MAX_BLOOM_FILTER_SIZE and the number of hash functions is <= MAX_HASH_FUNCS 83 : //! (catch a filter which was just deserialized which was too big) 84 : bool IsWithinSizeConstraints() const; 85 : 86 : bool Merge(const CBloomFilter& filter); 87 : bool MatchesAll() const; 88 : 89 : //! Also adds any outputs which match the filter to the filter (to match their spending txes) 90 : bool IsRelevantAndUpdate(const CTransaction& tx); 91 : 92 : //! Checks for empty and full filters to avoid wasting cpu 93 : void UpdateEmptyFull(); 94 : }; 95 : 96 : /** 97 : * RollingBloomFilter is a probabilistic "keep track of most recently inserted" set. 98 : * Construct it with the number of items to keep track of, and a false-positive 99 : * rate. Unlike CBloomFilter, by default nTweak is set to a cryptographically 100 : * secure random value for you. Similarly rather than clear() the method 101 : * reset() is provided, which also changes nTweak to decrease the impact of 102 : * false-positives. 103 : * 104 : * contains(item) will always return true if item was one of the last N to 1.5*N 105 : * insert()'ed ... but may also return true for items that were not inserted. 106 : * 107 : * It needs around 1.8 bytes per element per factor 0.1 of false positive rate. 108 : * (More accurately: 3/(log(256)*log(2)) * log(1/fpRate) * nElements bytes) 109 : */ 110 5364 : class CRollingBloomFilter 111 : { 112 : public: 113 : // A random bloom filter calls GetRand() at creation time. 114 : // Don't create global CRollingBloomFilter objects, as they may be 115 : // constructed before the randomizer is properly initialized. 116 : CRollingBloomFilter(unsigned int nElements, double nFPRate); 117 : 118 : void insert(const std::vector<unsigned char>& vKey); 119 : void insert(const uint256& hash); 120 : bool contains(const std::vector<unsigned char>& vKey) const; 121 : bool contains(const uint256& hash) const; 122 : 123 : void reset(); 124 : 125 : private: 126 : int nEntriesPerGeneration; 127 : int nEntriesThisGeneration; 128 : int nGeneration; 129 : std::vector<uint64_t> data; 130 : unsigned int nTweak; 131 : int nHashFuncs; 132 : }; 133 : 134 : #endif // PIVX_BLOOM_H