1 // Copyright (c) 2012-2019 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 #ifndef BITCOIN_BLOOM_H 6 #define BITCOIN_BLOOM_H 7 8 #include <serialize.h> 9 10 #include <vector> 11 12 class COutPoint; 13 class CTransaction; 14 class uint256; 15 16 //! 20,000 items with fp rate < 0.1% or 10,000 items and <0.0001% 17 static const unsigned int MAX_BLOOM_FILTER_SIZE = 36000; // bytes 18 static const unsigned int MAX_HASH_FUNCS = 50; 19 20 /** 21 * First two bits of nFlags control how much IsRelevantAndUpdate actually updates 22 * The remaining bits are reserved 23 */ 24 enum bloomflags 25 { 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 send them. 36 * 37 * This allows for significantly more efficient transaction and block downloads. 38 * 39 * Because bloom filters are probabilistic, a SPV node can increase the false- 40 * positive rate, making us send it transactions which aren't actually its, 41 * allowing clients to trade more bandwidth for more privacy by obfuscating which 42 * keys are controlled by them. 43 */ 44 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(const unsigned int nElements, const double nFPRate, const unsigned int nTweak, unsigned char nFlagsIn); CBloomFilter()67 CBloomFilter() : isFull(true), isEmpty(false), nHashFuncs(0), nTweak(0), nFlags(0) {} 68 69 ADD_SERIALIZE_METHODS; 70 71 template <typename Stream, typename Operation> SerializationOp(Stream & s,Operation ser_action)72 inline void SerializationOp(Stream& s, Operation ser_action) { 73 READWRITE(vData); 74 READWRITE(nHashFuncs); 75 READWRITE(nTweak); 76 READWRITE(nFlags); 77 } 78 79 void insert(const std::vector<unsigned char>& vKey); 80 void insert(const COutPoint& outpoint); 81 void insert(const uint256& hash); 82 83 bool contains(const std::vector<unsigned char>& vKey) const; 84 bool contains(const COutPoint& outpoint) const; 85 bool contains(const uint256& hash) const; 86 87 void clear(); 88 void reset(const unsigned int nNewTweak); 89 90 //! True if the size is <= MAX_BLOOM_FILTER_SIZE and the number of hash functions is <= MAX_HASH_FUNCS 91 //! (catch a filter which was just deserialized which was too big) 92 bool IsWithinSizeConstraints() const; 93 94 //! Also adds any outputs which match the filter to the filter (to match their spending txes) 95 bool IsRelevantAndUpdate(const CTransaction& tx); 96 97 //! Checks for empty and full filters to avoid wasting cpu 98 void UpdateEmptyFull(); 99 }; 100 101 /** 102 * RollingBloomFilter is a probabilistic "keep track of most recently inserted" set. 103 * Construct it with the number of items to keep track of, and a false-positive 104 * rate. Unlike CBloomFilter, by default nTweak is set to a cryptographically 105 * secure random value for you. Similarly rather than clear() the method 106 * reset() is provided, which also changes nTweak to decrease the impact of 107 * false-positives. 108 * 109 * contains(item) will always return true if item was one of the last N to 1.5*N 110 * insert()'ed ... but may also return true for items that were not inserted. 111 * 112 * It needs around 1.8 bytes per element per factor 0.1 of false positive rate. 113 * (More accurately: 3/(log(256)*log(2)) * log(1/fpRate) * nElements bytes) 114 */ 115 class CRollingBloomFilter 116 { 117 public: 118 CRollingBloomFilter(const unsigned int nElements, const double nFPRate); 119 120 void insert(const std::vector<unsigned char>& vKey); 121 void insert(const uint256& hash); 122 bool contains(const std::vector<unsigned char>& vKey) const; 123 bool contains(const uint256& hash) const; 124 125 void reset(); 126 127 private: 128 int nEntriesPerGeneration; 129 int nEntriesThisGeneration; 130 int nGeneration; 131 std::vector<uint64_t> data; 132 unsigned int nTweak; 133 int nHashFuncs; 134 }; 135 136 #endif // BITCOIN_BLOOM_H 137