1 // Copyright (c) 2012-2015 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 // Private constructor for CRollingBloomFilter, no restrictions on size 57 CBloomFilter(unsigned int nElements, double nFPRate, unsigned int nTweak); 58 friend class CRollingBloomFilter; 59 60 public: 61 /** 62 * Creates a new bloom filter which will provide the given fp rate when filled with the given number of elements 63 * Note that if the given parameters will result in a filter outside the bounds of the protocol limits, 64 * the filter created will be as close to the given parameters as possible within the protocol limits. 65 * This will apply if nFPRate is very low or nElements is unreasonably high. 66 * nTweak is a constant which is added to the seed value passed to the hash function 67 * It should generally always be a random value (and is largely only exposed for unit testing) 68 * nFlags should be one of the BLOOM_UPDATE_* enums (not _MASK) 69 */ 70 CBloomFilter(unsigned int nElements, double nFPRate, unsigned int nTweak, unsigned char nFlagsIn); CBloomFilter()71 CBloomFilter() : isFull(true), isEmpty(false), nHashFuncs(0), nTweak(0), nFlags(0) {} 72 73 ADD_SERIALIZE_METHODS; 74 75 template <typename Stream, typename Operation> SerializationOp(Stream & s,Operation ser_action,int nType,int nVersion)76 inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) { 77 READWRITE(vData); 78 READWRITE(nHashFuncs); 79 READWRITE(nTweak); 80 READWRITE(nFlags); 81 } 82 83 void insert(const std::vector<unsigned char>& vKey); 84 void insert(const COutPoint& outpoint); 85 void insert(const uint256& hash); 86 87 bool contains(const std::vector<unsigned char>& vKey) const; 88 bool contains(const COutPoint& outpoint) const; 89 bool contains(const uint256& hash) const; 90 91 void clear(); 92 void reset(unsigned int nNewTweak); 93 94 //! True if the size is <= MAX_BLOOM_FILTER_SIZE and the number of hash functions is <= MAX_HASH_FUNCS 95 //! (catch a filter which was just deserialized which was too big) 96 bool IsWithinSizeConstraints() const; 97 98 //! Also adds any outputs which match the filter to the filter (to match their spending txes) 99 bool IsRelevantAndUpdate(const CTransaction& tx); 100 101 //! Checks for empty and full filters to avoid wasting cpu 102 void UpdateEmptyFull(); 103 }; 104 105 /** 106 * RollingBloomFilter is a probabilistic "keep track of most recently inserted" set. 107 * Construct it with the number of items to keep track of, and a false-positive 108 * rate. Unlike CBloomFilter, by default nTweak is set to a cryptographically 109 * secure random value for you. Similarly rather than clear() the method 110 * reset() is provided, which also changes nTweak to decrease the impact of 111 * false-positives. 112 * 113 * contains(item) will always return true if item was one of the last N to 1.5*N 114 * insert()'ed ... but may also return true for items that were not inserted. 115 * 116 * It needs around 1.8 bytes per element per factor 0.1 of false positive rate. 117 * (More accurately: 3/(log(256)*log(2)) * log(1/fpRate) * nElements bytes) 118 */ 119 class CRollingBloomFilter 120 { 121 public: 122 // A random bloom filter calls GetRand() at creation time. 123 // Don't create global CRollingBloomFilter objects, as they may be 124 // constructed before the randomizer is properly initialized. 125 CRollingBloomFilter(unsigned int nElements, double nFPRate); 126 127 void insert(const std::vector<unsigned char>& vKey); 128 void insert(const uint256& hash); 129 bool contains(const std::vector<unsigned char>& vKey) const; 130 bool contains(const uint256& hash) const; 131 132 void reset(); 133 134 private: 135 int nEntriesPerGeneration; 136 int nEntriesThisGeneration; 137 int nGeneration; 138 std::vector<uint64_t> data; 139 unsigned int nTweak; 140 int nHashFuncs; 141 }; 142 143 #endif // BITCOIN_BLOOM_H 144